[tree-ssa] PATCH for expression temporary optimization

[Jason Merrill <jason at redhat dot com>]

This patch implements a basic formal temporary table:  Multiple evaluations
of the same expression will be stored into the same temporary, rather than
one per evaluation.  Informal testing on a gcc source file showed a 5%
compile time improvement from this patch.

The conditions for using an expression temporary may be adjusted in
future.  Currently we don't use one if we will be emitting a postqueue
between the temporary's initialization and use, as the postqueue might
change the value of the expression represented by the temporary.  We also
don't use them for expressions with side-effects.  I'm not sure whether or
not these restrictions are necessary.

Also, the table is currently destroyed after gimplification.  We may want
to keep it around until we're done compiling the function; if for no other
reason, so that mudflap gimplification can use it.

Tested i686-pc-linux-gnu, applied to tree-ssa.

2003-05-13  Jason Merrill  <jason@redhat.com>

        Implement expression temporary optimization.
        * gimplify.c (gimplify_ctx): Add temp_htab field.
        (push_gimplify_context): Initialize it.
        (pop_gimplify_context): Destroy it.
        (simplify_expr): If there's no internal postqueue, generate an
        expression temporary.
        (gimple_tree_hash, gimple_tree_eq): New fns.
        (create_tmp_from_val, lookup_tmp_var): New fns.
        (get_formal_tmp_var): New fn.
        (internal_get_tmp_var): New fn.
        (get_initialized_tmp_var): Use it.
        * tree-simple.h: Declare it.

*** gimplify.c.~1~	Mon May 12 05:17:57 2003
--- gimplify.c	Tue May 13 15:15:10 2003
*************** Software Foundation, 59 Temple Place - S
*** 37,43 ****
--- 37,45 ----
  #include "tree-flow.h"
  #include "timevar.h"
  #include "except.h"
+ #include "hashtab.h"
  #include "flags.h"
+ #include "real.h"
  
  static void simplify_constructor     PARAMS ((tree, tree *, tree *));
  static void simplify_array_ref       PARAMS ((tree *, tree *, tree *));
*************** static void gimplify_loop_expr		PARAMS (
*** 77,82 ****
--- 79,89 ----
  static void gimplify_exit_expr		PARAMS ((tree *, tree *));
  static void gimplify_switch_expr (tree *, tree *);
  static void gimple_add_case_label (tree);
+ static hashval_t gimple_tree_hash (const void *);
+ static int gimple_tree_eq (const void *, const void *);
+ static tree lookup_tmp_var (tree, bool);
+ static tree internal_get_tmp_var (tree, tree *, bool);
+ static tree build_and_jump (tree *);
  
  static struct gimplify_ctx
  {
*************** static struct gimplify_ctx
*** 86,91 ****
--- 93,100 ----
    int conditions;
    tree exit_label;
    varray_type case_labels;
+   /* The formal temporary table.  Should this be persistent?  */
+   htab_t temp_htab;
  } *gimplify_ctxp;
  
  static void
*************** push_gimplify_context ()
*** 93,99 ****
  {
    if (gimplify_ctxp)
      abort ();
!   gimplify_ctxp = (struct gimplify_ctx *) xcalloc (1, sizeof (struct gimplify_ctx));
  }
  
  static void
--- 102,111 ----
  {
    if (gimplify_ctxp)
      abort ();
!   gimplify_ctxp
!     = (struct gimplify_ctx *) xcalloc (1, sizeof (struct gimplify_ctx));
!   gimplify_ctxp->temp_htab
!     = htab_create (1000, gimple_tree_hash, gimple_tree_eq, free);
  }
  
  static void
*************** pop_gimplify_context ()
*** 101,106 ****
--- 113,124 ----
  {
    if (!gimplify_ctxp || gimplify_ctxp->current_bind_expr)
      abort ();
+ #if 0
+   if (!quiet_flag)
+     fprintf (stderr, " collisions: %f ",
+ 	     htab_collisions (gimplify_ctxp->temp_htab));
+ #endif
+   htab_delete (gimplify_ctxp->temp_htab);
    free (gimplify_ctxp);
    gimplify_ctxp = NULL;
  }
*************** simplify_expr (expr_p, pre_p, post_p, si
*** 706,712 ****
  
        /* An rvalue will do.  Assign the simplified expression into a new
  	 temporary TMP and replace the original expression with TMP.  */
!       *expr_p = get_initialized_tmp_var (*expr_p, pre_p);
      }
    else
      {
--- 731,744 ----
  
        /* An rvalue will do.  Assign the simplified expression into a new
  	 temporary TMP and replace the original expression with TMP.  */
! 
!       if (internal_post)
! 	/* The postqueue might change the value of the expression between
! 	   the initialization and use of the temporary, so we can't use a
! 	   formal temp.  FIXME do we care?  */
! 	*expr_p = get_initialized_tmp_var (*expr_p, pre_p);
!       else
! 	*expr_p = get_formal_tmp_var (*expr_p, pre_p);
      }
    else
      {
*************** get_name (t)
*** 2002,2022 ****
      }
  }
  
  
! /*  Returns a new temporary variable, initialized with VAL.  PRE_P and STMT
!     are as in simplify_expr.  */
  
  tree
! get_initialized_tmp_var (val, pre_p)
!      tree val;
!      tree *pre_p;
  {
    tree t, mod;
!   const char *prefix = NULL;
!   
!   prefix = get_name (val);
    simplify_expr (&val, pre_p, NULL, is_simple_rhs, fb_rvalue);
!   t = create_tmp_var (TREE_TYPE (val), prefix);
    mod = build (MODIFY_EXPR, TREE_TYPE (t), t, val);
    if (TREE_LOCUS (val))
      TREE_LOCUS (mod) = TREE_LOCUS (val);
--- 2128,2249 ----
      }
  }
  
+ /* Formal (expression) temporary table handling: Multiple occurrences of
+    the same expression are evaluated into the same temporary.  */
  
! typedef struct gimple_temp_hash_elt
! {
!   tree val;   /* Key */
!   tree temp;  /* Value */
! } elt_t;
! 
! /* Return a hash value for a formal temporary table entry.  */
! 
! static hashval_t
! gimple_tree_hash (const void *p)
! {
!   tree t = ((const elt_t *)p)->val;
!   return iterative_hash_expr (t, 0);
! }
! 
! /* Compare two formal temporary table entries.  */
! 
! static int
! gimple_tree_eq (const void *p1, const void *p2)
! {
!   tree t1 = ((const elt_t *)p1)->val;
!   tree t2 = ((const elt_t *)p2)->val;
!   enum tree_code code = TREE_CODE (t1);
! 
!   if (TREE_CODE (t2) != code
!       || TREE_TYPE (t1) != TREE_TYPE (t2))
!     return 0;
! 
!   if (!operand_equal_p (t1, t2, 0))
!     return 0;
! 
!   /* Only allow them to compare equal if they also hash equal; otherwise
!      results are nondeterminate, and we fail bootstrap comparison.  */
!   if (gimple_tree_hash (p1) != gimple_tree_hash (p2))
!     abort ();
! 
!   return 1;
! }
! 
! /* Create a temporary with a name derived from VAL.  Subroutine of
!    lookup_tmp_var; nobody else should call this function.  */
! 
! static inline tree
! create_tmp_from_val (tree val)
! {
!   return create_tmp_var (TREE_TYPE (val), get_name (val));
! }
! 
! /* Create a temporary to hold the value of VAL.  If IS_FORMAL, try to reuse
!    an existing expression temporary.  */
! 
! static tree
! lookup_tmp_var (tree val, bool is_formal)
! {
!   if (!is_formal || TREE_SIDE_EFFECTS (val))
!     return create_tmp_from_val (val);
!   else
!     {
!       elt_t elt, *elt_p;
!       void **slot;
! 
!       elt.val = val;
!       slot = htab_find_slot (gimplify_ctxp->temp_htab, (void *)&elt, INSERT);
!       if (*slot == NULL)
! 	{
! 	  elt_p = xmalloc (sizeof (*elt_p));
! 	  elt_p->val = val;
! 	  elt_p->temp = create_tmp_from_val (val);
! 	  *slot = (void *)elt_p;
! 	}
!       else
! 	elt_p = (elt_t *) *slot;
! 
!       return elt_p->temp;
!     }
! }
! 
! /* Returns a formal temporary variable initialized with VAL.  PRE_P and
!    STMT are as in simplify_expr.  Only use this function if:
! 
!    1) The value of the unfactored expression represented by VAL will not
!       change between the initialization and use of the temporary, and
!    2) The temporary will not be otherwise modified.
! 
!    For instance, #1 means that this is inappropriate for SAVE_EXPR temps,
!    and #2 means it is inappropriate for && temps.
! 
!    For other cases, use get_initialized_tmp_var instead.  */
  
  tree
! get_formal_tmp_var (tree val, tree *pre_p)
! {
!   return internal_get_tmp_var (val, pre_p, true);
! }
! 
! /* Returns a temporary variable initialized with VAL.  PRE_P and STMT
!    are as in simplify_expr.  */
! 
! tree
! get_initialized_tmp_var (tree val, tree *pre_p)
! {
!   return internal_get_tmp_var (val, pre_p, false);
! }
! 
! static tree
! internal_get_tmp_var (tree val, tree *pre_p, bool is_formal)
  {
    tree t, mod;
! 
    simplify_expr (&val, pre_p, NULL, is_simple_rhs, fb_rvalue);
! 
!   t = lookup_tmp_var (val, is_formal);
! 
    mod = build (MODIFY_EXPR, TREE_TYPE (t), t, val);
    if (TREE_LOCUS (val))
      TREE_LOCUS (mod) = TREE_LOCUS (val);
*** tree-simple.h.~1~	Mon May 12 05:17:57 2003
--- tree-simple.h	Tue May 13 03:41:30 2003
*************** extern tree create_tmp_var             P
*** 32,37 ****
--- 32,38 ----
  extern tree create_tmp_alias_var       PARAMS ((tree, const char *));
  extern bool is_simple_tmp_var	       PARAMS ((tree));
  extern tree get_initialized_tmp_var    PARAMS ((tree, tree *));
+ extern tree get_formal_tmp_var         PARAMS ((tree, tree *));
  extern void declare_tmp_vars           PARAMS ((tree, tree));
  extern tree deep_copy_list             PARAMS ((tree));
  extern tree deep_copy_node             PARAMS ((tree));