[tree-ssa] More improvements for dominator optimizations

[law at redhat dot com]

When performing optimizations on the dominator tree, a COND_EXPR can create
an equivalence that should be recorded into the const_and_copies table.


Consider this test (20030703-1.c)


/* { dg-do compile */
/* { dg-options "-O1 -fdump-tree-ssa" } */
  

extern int blah[];

foo(int index)
{
  if (blah [(unsigned int)index] != 0)
    abort ();
  if (blah [(unsigned int)index] != 0)
    abort ();
}

/* There should be precisely one load of blah.  If there is
   more than one, then the dominator optimizations failed.  */
/* { dg-final { scan-tree-dump-times "blah" 1 "ssa"} } */
 
/* There should be exactly one IF conditional.  */
/* { dg-final { scan-tree-dump-times "if " 1 "ssa"} } */


Which in gimple form looks like this:

foo (index)
{
  unsigned int index.1;
  int T.2;
  extern  abort;
    
  index.1 = (unsigned int)index;
  T.2 = blah[index.1];
  if (T.2 != 0)
    {
      abort ()
    }
  else
    {
      (void)0
    };
  index.1 = (unsigned int)index;
  T.2 = blah[index.1];
  if (T.2 != 0)
    {
      abort ()
    }
  else
    {
      (void)0
    }
}

So a quick analysis of the function indicates that the only way we can
reach the second conditional is if T.2 == 0 (otherwise we would have
aborted after the first conditional).  Thus the second conditional is
always false.

The dominator optimizer already handled a limited set of these kinds of
cases (though not the one above).  This patch extends the optimizer to
recognize more equivalences and record them into the const_and_copies
table and extends the optimizer to propagate these kind of equivalences
into the false arm of conditionals (previously it propagated into the
true arm only).

Note there are a lot more cases that we can (and will) handle, but that
patch hasn't been fully tested yet :-) 

This patch also puts a call to cleanup_tree_cfg at the end of the tree-ssa
renamer.  Eventually that will move into the dominator optimizer since we
want/need to wipe unreachable code during the dominator walks.

In the immediate term we need to cleanup the CFG so that the tests don't
have to be rewritten (they do things like count the number of IF statements;
if you don't cleanup the CFG, then stuff like "if (0)" or "if (1)" will show
up in the dumps and muck up our statement counts.

This fixes 4 failures in the recently added tree-ssa tests.


	* tree-ssa.c (rewrite_into_ssa): If we have done dominator 
	optimizations, then call cleanup_tree_cfg after rewriting is
	complete.
	* tree-ssa-dom.c (optimize_block): Get eq_expr_value for the
	current block rather than having it passed in by the caller.
	Propagate eq_expr_value into the false arm of a COND_EXPR.
	(get_eq_expr_value): Return equivalences for the false
	arm of a COND_EXPR if requested.

Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.103
diff -c -3 -p -r1.1.4.103 tree-ssa.c
*** tree-ssa.c	15 Jul 2003 19:15:24 -0000	1.1.4.103
--- tree-ssa.c	16 Jul 2003 17:21:32 -0000
*************** rewrite_into_ssa (tree fndecl, sbitmap v
*** 388,393 ****
--- 388,398 ----
    if (vars == NULL)
      sbitmap_free (vars_to_rename);
  
+   /* The dominator optimizations may have made some blocks unreachable,
+      go ahead and clean things up.  */
+   if (flag_tree_dom)
+     cleanup_tree_cfg ();
+ 
    /* Debugging dumps.  */
    if (dump_file)
      {
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.2
diff -c -3 -p -r1.1.2.2 tree-ssa-dom.c
*** tree-ssa-dom.c	15 Jul 2003 19:35:19 -0000	1.1.2.2
--- tree-ssa-dom.c	16 Jul 2003 17:21:32 -0000
*************** static struct opt_stats_d opt_stats;
*** 81,94 ****
  static bool addr_expr_propagated_p;
  
  /* Local functions.  */
! static void optimize_block (basic_block, tree);
  static void optimize_stmt (block_stmt_iterator, varray_type *);
  static tree get_value_for (tree, htab_t);
  static void set_value_for (tree, tree, htab_t);
  static hashval_t var_value_hash (const void *);
  static int var_value_eq (const void *, const 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 *);
  static void htab_statistics (FILE *, htab_t);
--- 81,94 ----
  static bool addr_expr_propagated_p;
  
  /* Local functions.  */
! static void optimize_block (basic_block, tree, int);
  static void optimize_stmt (block_stmt_iterator, varray_type *);
  static tree get_value_for (tree, htab_t);
  static void set_value_for (tree, tree, htab_t);
  static hashval_t var_value_hash (const void *);
  static int var_value_eq (const void *, const void *);
  static tree lookup_avail_expr (tree, varray_type *, htab_t);
! static tree get_eq_expr_value (tree, int);
  static hashval_t avail_expr_hash (const void *);
  static int avail_expr_eq (const void *, const void *);
  static void htab_statistics (FILE *, htab_t);
*************** tree_ssa_dominator_optimize (FILE *file,
*** 117,123 ****
    addr_expr_propagated_p = false;
  
    /* Now optimize the dominator tree.  */
!   optimize_block (ENTRY_BLOCK_PTR, NULL);
  
    htab_delete (const_and_copies);
    htab_delete (avail_exprs);
--- 117,123 ----
    addr_expr_propagated_p = false;
  
    /* Now optimize the dominator tree.  */
!   optimize_block (ENTRY_BLOCK_PTR, NULL, 0);
  
    htab_delete (const_and_copies);
    htab_delete (avail_exprs);
*************** tree_ssa_dominator_optimize (FILE *file,
*** 130,136 ****
        if (dump_flags & TDF_STATS)
  	dump_dominator_optimization_stats (dump_file);
      }
-                                                                              

  
    return addr_expr_propagated_p;
  }
--- 130,135 ----
*************** tree_ssa_dominator_optimize (FILE *file,
*** 161,173 ****
     constant propagator can find more propagation opportunities.  */
  
  static void
! optimize_block (basic_block bb, tree eq_expr_value)
  {
    varray_type block_avail_exprs;
    bitmap children;
    unsigned long i;
    block_stmt_iterator si;
    tree prev_value = NULL_TREE;
  
    /* Initialize the local stacks.
       
--- 160,173 ----
     constant propagator can find more propagation opportunities.  */
  
  static void
! optimize_block (basic_block bb, tree parent_block_last_stmt, int edge_flags)
  {
    varray_type block_avail_exprs;
    bitmap children;
    unsigned long i;
    block_stmt_iterator si;
    tree prev_value = NULL_TREE;
+   tree eq_expr_value = NULL_TREE;
  
    /* Initialize the local stacks.
       
*************** optimize_block (basic_block bb, tree eq_
*** 182,187 ****
--- 182,194 ----
    if (dump_file && (dump_flags & TDF_DETAILS))
      fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
  
+   if (parent_block_last_stmt
+       && TREE_CODE (parent_block_last_stmt) == COND_EXPR
+       && (edge_flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
+     eq_expr_value = get_eq_expr_value (parent_block_last_stmt,
+ 				       (edge_flags & EDGE_TRUE_VALUE) != 0);
+                                                                              

+ 
    /* If EQ_EXPR_VALUE (VAR == VALUE) is given, register the VALUE as a
       new value for VAR, so that occurrences of VAR can be replaced with
       VALUE while re-writing the THEN arm of a COND_EXPR.  */
*************** optimize_block (basic_block bb, tree eq_
*** 206,222 ****
  	{
  	  tree last = last_stmt (bb);
  	  EXECUTE_IF_SET_IN_BITMAP (children, 0, i,
! 	    {
! 	      if (BASIC_BLOCK (i)->pred->flags & EDGE_TRUE_VALUE)
! 		optimize_block (BASIC_BLOCK (i), get_eq_expr_value (last));
! 	      else
! 		optimize_block (BASIC_BLOCK (i), NULL_TREE);
! 	    });
  	}
        else
  	{
  	  EXECUTE_IF_SET_IN_BITMAP (children, 0, i,
! 	    optimize_block (BASIC_BLOCK (i), NULL_TREE));
  	}
      }
  
--- 213,225 ----
  	{
  	  tree last = last_stmt (bb);
  	  EXECUTE_IF_SET_IN_BITMAP (children, 0, i,
! 	    optimize_block (BASIC_BLOCK (i), last,
! 			    BASIC_BLOCK (i)->pred->flags));
  	}
        else
  	{
  	  EXECUTE_IF_SET_IN_BITMAP (children, 0, i,
! 	    optimize_block (BASIC_BLOCK (i), NULL_TREE, 0));
  	}
      }
  
*************** lookup_avail_expr (tree stmt,
*** 573,595 ****
  }
  
  
! /* Given a conditional statement IF_STMT, return the assignment 'X = Y', if
!    the conditional is of the form 'X == Y'.  If the conditional is of the
!    form 'X'.  The assignment 'X = 1' is returned.  */
  
  static tree
! get_eq_expr_value (tree if_stmt)
  {
    tree cond, value;
  
    cond = COND_EXPR_COND (if_stmt);
  
!   /* If the conditional is a single variable 'X', return 'X = 1'.  */
    if (SSA_VAR_P (cond))
!     return build (MODIFY_EXPR, TREE_TYPE (cond), cond, integer_one_node);
  
!   /* If the conditional is of the form 'X == Y', return 'X = Y'.  */
!   else if (TREE_CODE (cond) == EQ_EXPR
  	   && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
  	   && (is_unchanging_value (TREE_OPERAND (cond, 1))
  	       || is_optimizable_addr_expr (TREE_OPERAND (cond, 1))
--- 576,616 ----
  }
  
  
! /* Given a conditional statement IF_STMT, return the assignment 'X = Y'
!    known to be true depending on which arm of IF_STMT is taken.
! 
!    Not all conditional statements will result in a useful assignment.
!    Return NULL_TREE in that case.  */
  
  static tree
! get_eq_expr_value (tree if_stmt, int true_arm)
  {
    tree cond, value;
  
    cond = COND_EXPR_COND (if_stmt);
  
!   /* If the conditional is a single variable 'X', return 'X = 1' for
!      the true arm and 'X = 0' on the false arm.   */
    if (SSA_VAR_P (cond))
!     return build (MODIFY_EXPR, TREE_TYPE (cond), cond,
! 		  (true_arm ? integer_one_node : integer_zero_node));
  
!   /* If the conditional is of the form 'X == Y', return 'X = Y' for the
!      true arm.  */
!   else if (true_arm
! 	   && TREE_CODE (cond) == EQ_EXPR
! 	   && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
! 	   && (is_unchanging_value (TREE_OPERAND (cond, 1))
! 	       || is_optimizable_addr_expr (TREE_OPERAND (cond, 1))
! 	       || TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME))
!     value = build (MODIFY_EXPR, TREE_TYPE (cond),
! 		   TREE_OPERAND (cond, 0),
! 		   TREE_OPERAND (cond, 1));
! 
!   /* If the conditional is of the form 'X != Y', return 'X = Y' for the
!      false arm.  */
!   else if (! true_arm
! 	   && TREE_CODE (cond) == NE_EXPR
  	   && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
  	   && (is_unchanging_value (TREE_OPERAND (cond, 1))
  	       || is_optimizable_addr_expr (TREE_OPERAND (cond, 1))