[tree-ssa] PATCH to improve optimization at ssa rewrite time

[Jason Merrill <jason at redhat dot com>]

For the testcase

  int j;
  int main()
  { 
    int i;

    i = j + 42;
    i = j + 42;
  }

currently the SSA rewriter produces

  int main()
  { 
    int i;

    i_2 = j + 42;
    i_3 = j + 42;
  }

After the avail_expr_eq patch, it produces

  int main()
  { 
    int i;

    i_2 = j + 42;
    i_3 = i_2;
  }

After the rewrite_stmt patch, it produces

  int main()
  { 
    int i;

    i = j + 42;
    (void)0;
  }

This is very useful in conjunction with expression temporaries, which
produce a lot of redundant statements.

Oddly, this doesn't work for plain "i = 42".  Something to look into.

The avail_expr_hash hunk just switches to using the iterative hash function
I recently added to the libiberty hash table code.

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

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

        * tree-ssa.c (rewrite_stmt): Discard redundant assignments.
        (avail_expr_eq): Don't test ops1 == ops2.
        (avail_expr_hash): Use iterative_hash_object.

*** tree-ssa.c.~1~	Mon May 12 05:17:57 2003
--- tree-ssa.c	Tue May 13 15:08:09 2003
*************** Boston, MA 02111-1307, USA.  */
*** 51,57 ****
  /* This file builds the SSA form for a function as described in:
  
     R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
!    Computing Static Single Sssignment Form and the Control Dependence
     Graph. ACM Transactions on Programming Languages and Systems,
     13(4):451-490, October 1991.  */
  
--- 51,57 ----
  /* This file builds the SSA form for a function as described in:
  
     R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
!    Computing Static Single Assignment Form and the Control Dependence
     Graph. ACM Transactions on Programming Languages and Systems,
     13(4):451-490, October 1991.  */
  
*************** rewrite_stmt (si, block_defs_p, block_av
*** 2230,2235 ****
--- 2230,2244 ----
  	  TREE_OPERAND (stmt, 1) = cached_lhs;
  	  ann->modified = 1;
  #else
+ 	  if (cached_lhs && get_value_for (*def_p, currdefs) == cached_lhs)
+ 	    {
+ 	      /* A redundant assignment to the same lhs, perhaps a new
+                  evaluation of an expression temporary that is still live.
+                  Just discard it.  */
+ 	      ssa_stats.num_re++;
+ 	      bsi_remove (&si);
+ 	      return;
+ 	    }
  	  if (var_is_live (cached_lhs, ann->bb))
  	    {
  	      register_new_def (*def_p, cached_lhs, block_defs_p);
*************** static hashval_t
*** 2747,2760 ****
  avail_expr_hash (p)
       const void *p;
  {
!   hashval_t val;
    tree rhs;
    size_t i;
    varray_type ops;
    tree stmt = (tree) p;
  
    rhs = TREE_OPERAND (stmt, 1);
!   val = (hashval_t) TREE_CODE (rhs);
  
    /* Add the SSA version numbers of every use operand.  */
    ops = use_ops (stmt);
--- 2756,2771 ----
  avail_expr_hash (p)
       const void *p;
  {
!   hashval_t val = 0;
    tree rhs;
    size_t i;
    varray_type ops;
    tree stmt = (tree) p;
+   enum tree_code code;
  
    rhs = TREE_OPERAND (stmt, 1);
!   code = TREE_CODE (rhs);
!   val = iterative_hash_object (code, val);
  
    /* Add the SSA version numbers of every use operand.  */
    ops = use_ops (stmt);
*************** avail_expr_hash (p)
*** 2762,2770 ****
      {
        tree op = *((tree *) VARRAY_GENERIC_PTR (ops, i));
        if (TREE_CODE (op) == SSA_NAME)
! 	val += (hashval_t) SSA_NAME_VERSION (op);
        else
! 	val += htab_hash_pointer (op);
      }
  
    /* Add the SSA version numbers of every vuse operand.  This is important
--- 2773,2781 ----
      {
        tree op = *((tree *) VARRAY_GENERIC_PTR (ops, i));
        if (TREE_CODE (op) == SSA_NAME)
! 	val = iterative_hash_object (SSA_NAME_VERSION (op), val);
        else
! 	val = iterative_hash_object (op, val);
      }
  
    /* Add the SSA version numbers of every vuse operand.  This is important
*************** avail_expr_hash (p)
*** 2773,2779 ****
       representing all the elements of the array.  */
    ops = vuse_ops (stmt);
    for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
!     val += (hashval_t) SSA_NAME_VERSION (VARRAY_TREE (ops, i));
  
    return val;
  }
--- 2784,2790 ----
       representing all the elements of the array.  */
    ops = vuse_ops (stmt);
    for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
!     val = iterative_hash_object (SSA_NAME_VERSION (VARRAY_TREE (ops, i)), val);
  
    return val;
  }
*************** avail_expr_eq (p1, p2)
*** 2803,2810 ****
        if (ops1 == NULL && ops2 == NULL)
  	return true;
  
!       if (ops1 == ops2
! 	  && VARRAY_ACTIVE_SIZE (ops1) == VARRAY_ACTIVE_SIZE (ops2))
  	{
  	  size_t i;
  	  for (i = 0; i < VARRAY_ACTIVE_SIZE (ops1); i++)
--- 2814,2820 ----
        if (ops1 == NULL && ops2 == NULL)
  	return true;
  
!       if (VARRAY_ACTIVE_SIZE (ops1) == VARRAY_ACTIVE_SIZE (ops2))
  	{
  	  size_t i;
  	  for (i = 0; i < VARRAY_ACTIVE_SIZE (ops1); i++)