[tree-ssa] Improve dominator optimizations

[law at redhat dot com]

This patch improves our dominator optimization in a couple ways.

First (and simplest) we enter NOP_EXPRs into the available expression 
table -- which allows us to eliminate redundant NOP_EXPRs.  You might,
hey, this is a NOP_EXPR, who cares?

Well, the gimplification process *really* likes to break out type casts
into distinct statements.  This results in unnecessary copies appearing
in the INSN stream later.  In fact, these copies are the single biggest
reason why we get more INSNs when using the tree-ssa optimizers.  Each
redundant type cast we remove is one less statement for the tree-ssa
optimizers to examine and one less copy for the RTL optimizers to deal
with later.

The second change allows us to eliminate more statements by noting that
when we find a redundant expression in the available expression hash
table that the LHS of that expression may have a known value in the
const_and_copies table.

Both of these cases occur in things like our tree-checking code.  In fact,
I'm using simplified tree-checking code as a quality test for the dominator
optimizations.  Expect tests for the testsuite to follow once I've got
the other changes in-place necessary allow us to optimize them fully.
These changes are also necessary if we're going to be able to zap the
path following crud in cse.c in the future...

These have (of course) bootstrapped and regression tested.  I've also
verified that they improve code *without* requiring the additional 
patches I'm still developing.


	* tree-ssa.c (lookup_avail_expr): Accept new argument containing the
	const_and_copies table.  All callers changed.  If we find the
	given expression in the availe expression hash table, then lookup
	the LHS of the hash table's entry in the const_and_copies_table.
	Do record type casts into the available expression table.

Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.99
diff -c -3 -p -r1.1.4.99 tree-ssa.c
*** tree-ssa.c	1 Jul 2003 04:04:32 -0000	1.1.4.99
--- tree-ssa.c	3 Jul 2003 17:38:40 -0000
*************** static hashval_t var_value_hash (const v
*** 180,186 ****
  static int var_value_eq (const void *, const void *);
  static void def_blocks_free (void *);
  static int debug_def_blocks_r (void **, void *);
! static tree lookup_avail_expr (tree, varray_type *);
  static tree get_eq_expr_value (tree);
  static hashval_t avail_expr_hash (const void *);
  static int avail_expr_eq (const void *, const void *);
--- 180,186 ----
  static int var_value_eq (const void *, const void *);
  static void def_blocks_free (void *);
  static int debug_def_blocks_r (void **, void *);
! static tree lookup_avail_expr (tree, varray_type *, htab_t);
  static tree get_eq_expr_value (tree);
  static hashval_t avail_expr_hash (const void *);
  static int avail_expr_eq (const void *, const void *);
*************** rewrite_and_optimize_stmt (block_stmt_it
*** 2118,2124 ****
        /* Check if the RHS of the assignment has been computed before.  If
  	 so, use the LHS of the previously computed statement as the
  	 reaching definition for the variable defined by this statement.  */
!       tree cached_lhs = lookup_avail_expr (stmt, block_avail_exprs_p);
        ssa_stats.num_exprs_considered++;
        if (cached_lhs && TREE_TYPE (cached_lhs) == TREE_TYPE (*def_p))
  	{
--- 2118,2126 ----
        /* Check if the RHS of the assignment has been computed before.  If
  	 so, use the LHS of the previously computed statement as the
  	 reaching definition for the variable defined by this statement.  */
!       tree cached_lhs = lookup_avail_expr (stmt,
! 					   block_avail_exprs_p,
! 					   const_and_copies);
        ssa_stats.num_exprs_considered++;
        if (cached_lhs && TREE_TYPE (cached_lhs) == TREE_TYPE (*def_p))
  	{
*************** set_value_for (tree var, tree value, hta
*** 2569,2586 ****
  	 aliased references.  */
  
  static tree
! lookup_avail_expr (tree stmt, varray_type *block_avail_exprs_p)
  {
    void **slot;
    tree rhs;
  
!   /* Don't bother remembering constant assignments, type cast expressions
!      and copy operations.  Constants and copy operations are handled by the
!      constant/copy propagator in rewrite_and_optimize_stmt.  */
    rhs = TREE_OPERAND (stmt, 1);
    if (TREE_CONSTANT (rhs)
!       || TREE_CODE (rhs) == SSA_NAME
!       || is_gimple_cast (rhs))
      return NULL_TREE;
  
    slot = htab_find_slot (avail_exprs, stmt, INSERT);
--- 2571,2591 ----
  	 aliased references.  */
  
  static tree
! lookup_avail_expr (tree stmt,
! 		   varray_type *block_avail_exprs_p,
! 		   htab_t const_and_copies)
  {
    void **slot;
    tree rhs;
+   tree lhs;
+   tree temp;
  
!   /* Don't bother remembering constant assignments and copy operations.
!      Constants and copy operations are handled by the constant/copy propagator
!      in rewrite_and_optimize_stmt.  */
    rhs = TREE_OPERAND (stmt, 1);
    if (TREE_CONSTANT (rhs)
!       || TREE_CODE (rhs) == SSA_NAME)
      return NULL_TREE;
  
    slot = htab_find_slot (avail_exprs, stmt, INSERT);
*************** lookup_avail_expr (tree stmt, varray_typ
*** 2591,2599 ****
        return NULL_TREE;
      }
  
!   /* Return the LHS of the assignment so that it can be used as the current
       definition of another variable.  */
!   return TREE_OPERAND ((tree) *slot, 0);
  }
  
  
--- 2596,2612 ----
        return NULL_TREE;
      }
  
!   /* Extract the LHS of the assignment so that it can be used as the current
       definition of another variable.  */
!   lhs = TREE_OPERAND ((tree) *slot, 0);
! 
!   /* See if the LHS appears in the const_and_copies table.  If it does, then
!      use the value from the const_and_copies table.  */
!   temp = get_value_for (lhs, const_and_copies);
!   if (temp)
!     lhs = temp;
! 
!   return lhs;
  }