[PATCH] More simple early optimization opportunities

[Richard Guenther <rguenther at suse dot de>]

SCCVN cannot value-number conditionals in COND_EXPRs (there is no
SSA_NAME def for the condition), so those get not eliminated by
constants even if that would be possible.  Fixed by simply "folding"
COND_EXPRs at elimination time and scheduling cleanup_cfg appropriately.

SCCVN didn't record an expression for further simplification at
load elimination time (might be caused by some of my earlier
simplification patches), thus fixed as well.

I missed to allow forwprop to use constants in combining arguments
of COND_EXPR conditionals.  Fixed.

forwprop can look through conversions of pointers in finding a
suitable statement for combining comparisions, this helps removing
NULL pointer checks in C++ code early (it's the 2nd pass after all,
previously that had to wait until VRP).

Boostrapped and tested on x86_64-unknown-linux-gnu, applied to trunk.

Richard.

2008-03-18  Richard Guenther  <rguenther@suse.de>

	* tree-ssa-sccvn.c (visit_reference_op_load): If the lookup
	found an expression with constants, note that in the VN for the lhs.
	* tree-ssa-pre.c (eliminate): Visit COND_EXPR statements and
	fold them to constants if possible.  Run cleanup_cfg if done so.
	(execute_pre): Return todo.
	(do_pre): Likewise.
	(execute_fre): Likewise.
	* tree-ssa-forwprop.c (can_propagate_from): Allow propagation
	of constants.
	(get_prop_source_stmt): Look through pointer conversions.

	* gcc.dg/tree-ssa/forwprop-4.c: New testcase.
	* gcc.dg/tree-ssa/ssa-fre-16.c: Likewise.

Index: tree-ssa-sccvn.c
===================================================================
*** tree-ssa-sccvn.c	(revision 133310)
--- tree-ssa-sccvn.c	(working copy)
*************** visit_reference_op_load (tree lhs, tree 
*** 1251,1256 ****
--- 1251,1262 ----
    if (result)
      {
        changed = set_ssa_val_to (lhs, result);
+       if (TREE_CODE (result) == SSA_NAME
+ 	  && VN_INFO (result)->has_constants)
+ 	{
+ 	  VN_INFO (lhs)->expr = VN_INFO (result)->expr;
+ 	  VN_INFO (lhs)->has_constants = true;
+ 	}
      }
    else
      {
Index: tree-ssa-forwprop.c
===================================================================
*** tree-ssa-forwprop.c	(revision 133310)
--- tree-ssa-forwprop.c	(working copy)
*************** get_prop_source_stmt (tree name, bool si
*** 218,231 ****
      /* If name is not a simple copy destination, we found it.  */
      if (TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) != SSA_NAME)
        {
  	if (!single_use_only && single_use_p)
  	  *single_use_p = single_use;
  
! 	return def_stmt;
        }
- 
-     /* Continue searching the def of the copy source name.  */
-     name = GIMPLE_STMT_OPERAND (def_stmt, 1);
    } while (1);
  }
  
--- 218,245 ----
      /* If name is not a simple copy destination, we found it.  */
      if (TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) != SSA_NAME)
        {
+ 	tree rhs;
+ 
  	if (!single_use_only && single_use_p)
  	  *single_use_p = single_use;
  
! 	/* We can look through pointer conversions in the search
! 	   for a useful stmt for the comparison folding.  */
! 	rhs = GIMPLE_STMT_OPERAND (def_stmt, 1);
! 	if ((TREE_CODE (rhs) == NOP_EXPR
! 	     || TREE_CODE (rhs) == CONVERT_EXPR)
! 	    && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
! 	    && POINTER_TYPE_P (TREE_TYPE (rhs))
! 	    && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))))
! 	  name = TREE_OPERAND (rhs, 0);
! 	else
! 	  return def_stmt;
!       }
!     else
!       {
! 	/* Continue searching the def of the copy source name.  */
! 	name = GIMPLE_STMT_OPERAND (def_stmt, 1);
        }
    } while (1);
  }
  
*************** can_propagate_from (tree def_stmt)
*** 245,250 ****
--- 259,268 ----
    if (REFERENCE_CLASS_P (rhs))
      return false;
  
+   /* Constants can be always propagated.  */
+   if (is_gimple_min_invariant (rhs))
+     return true;
+ 
    /* We cannot propagate ssa names that occur in abnormal phi nodes.  */
    switch (TREE_CODE_LENGTH (TREE_CODE (rhs)))
      {
Index: testsuite/gcc.dg/tree-ssa/ssa-fre-16.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/ssa-fre-16.c	(revision 0)
--- testsuite/gcc.dg/tree-ssa/ssa-fre-16.c	(revision 0)
***************
*** 0 ****
--- 1,18 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fdump-tree-fre" } */
+ 
+ /* FRE should be able to combine i and j and perform simplification
+    on the condition.  */
+ 
+ extern void link_error (void);
+ int i;
+ int foo(int b, int c)
+ {
+   i = b + 1;
+   int j = i - 1;
+   if (b != j)
+     link_error ();
+ }
+ 
+ /* { dg-final { scan-tree-dump-not "link_error" "fre" } } */
+ /* { dg-final { cleanup-tree-dump "fre" } } */
Index: testsuite/gcc.dg/tree-ssa/forwprop-4.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/forwprop-4.c	(revision 0)
--- testsuite/gcc.dg/tree-ssa/forwprop-4.c	(revision 0)
***************
*** 0 ****
--- 1,18 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fdump-tree-forwprop1" } */
+ 
+ /* We should be able to fold the comparison at least with the
+    first forwprop pass, if not a ccp pass before.  */
+ 
+ extern void link_error (void);
+ void foo()
+ {
+   int i;
+   char *p = (char *)&i;
+   long *q = (long *)p;
+   if (q == 0)
+     link_error ();
+ }
+ 
+ /* { dg-final { scan-tree-dump-not "link_error" "forwprop1" } } */
+ /* { dg-final { cleanup-tree-dump "forwprop1" } } */
Index: tree-ssa-pre.c
===================================================================
*** tree-ssa-pre.c	(revision 133310)
--- tree-ssa-pre.c	(working copy)
*************** do_SCCVN_insertion (tree stmt, tree ssa_
*** 3605,3614 ****
  
  /* Eliminate fully redundant computations.  */
  
! static void
  eliminate (void)
  {
    basic_block b;
  
    FOR_EACH_BB (b)
      {
--- 3605,3615 ----
  
  /* Eliminate fully redundant computations.  */
  
! static unsigned int
  eliminate (void)
  {
    basic_block b;
+   unsigned int todo = 0;
  
    FOR_EACH_BB (b)
      {
*************** eliminate (void)
*** 3689,3696 ****
--- 3690,3735 ----
  		    }
  		}
  	    }
+ 	  /* Visit COND_EXPRs and fold the comparison with the
+ 	     available value-numbers.  */
+ 	  else if (TREE_CODE (stmt) == COND_EXPR
+ 		   && COMPARISON_CLASS_P (COND_EXPR_COND (stmt)))
+ 	    {
+ 	      tree cond = COND_EXPR_COND (stmt);
+ 	      tree op0 = TREE_OPERAND (cond, 0);
+ 	      tree op1 = TREE_OPERAND (cond, 1);
+ 	      tree result;
+ 
+ 	      if (TREE_CODE (op0) == SSA_NAME)
+ 		op0 = VN_INFO (op0)->valnum;
+ 	      if (TREE_CODE (op1) == SSA_NAME)
+ 		op1 = VN_INFO (op1)->valnum;
+ 	      result = fold_binary (TREE_CODE (cond), TREE_TYPE (cond),
+ 				    op0, op1);
+ 	      if (result && TREE_CODE (result) == INTEGER_CST)
+ 		{
+ 		  COND_EXPR_COND (stmt) = result;
+ 		  update_stmt (stmt);
+ 		  todo = TODO_cleanup_cfg;
+ 		}
+ 	    }
+ 	  else if (TREE_CODE (stmt) == COND_EXPR
+ 		   && TREE_CODE (COND_EXPR_COND (stmt)) == SSA_NAME)
+ 	    {
+ 	      tree op = COND_EXPR_COND (stmt);
+ 	      op = VN_INFO (op)->valnum;
+ 	      if (TREE_CODE (op) == INTEGER_CST)
+ 		{
+ 		  COND_EXPR_COND (stmt) = integer_zerop (op)
+ 		    ? boolean_false_node : boolean_true_node;
+ 		  update_stmt (stmt);
+ 		  todo = TODO_cleanup_cfg;
+ 		}
+ 	    }
  	}
      }
+ 
+   return todo;
  }
  
  /* Borrow a bit of tree-ssa-dce.c for the moment.
*************** fini_pre (void)
*** 3931,3939 ****
  /* Main entry point to the SSA-PRE pass.  DO_FRE is true if the caller
     only wants to do full redundancy elimination.  */
  
! static void
  execute_pre (bool do_fre)
  {
  
    do_partial_partial = optimize > 2;
    init_pre (do_fre);
--- 3970,3979 ----
  /* Main entry point to the SSA-PRE pass.  DO_FRE is true if the caller
     only wants to do full redundancy elimination.  */
  
! static unsigned int
  execute_pre (bool do_fre)
  {
+   unsigned int todo = 0;
  
    do_partial_partial = optimize > 2;
    init_pre (do_fre);
*************** execute_pre (bool do_fre)
*** 3947,3953 ****
        if (!do_fre)
  	remove_dead_inserted_code ();
        fini_pre ();
!       return;
      }
    switch_to_PRE_table ();
    compute_avail ();
--- 3987,3993 ----
        if (!do_fre)
  	remove_dead_inserted_code ();
        fini_pre ();
!       return 0;
      }
    switch_to_PRE_table ();
    compute_avail ();
*************** execute_pre (bool do_fre)
*** 3978,3984 ****
      }
  
    /* Remove all the redundant expressions.  */
!   eliminate ();
  
    if (dump_file && (dump_flags & TDF_STATS))
      {
--- 4018,4024 ----
      }
  
    /* Remove all the redundant expressions.  */
!   todo |= eliminate ();
  
    if (dump_file && (dump_flags & TDF_STATS))
      {
*************** execute_pre (bool do_fre)
*** 3999,4004 ****
--- 4039,4046 ----
      }
  
    fini_pre ();
+ 
+   return todo;
  }
  
  /* Gate and execute functions for PRE.  */
*************** execute_pre (bool do_fre)
*** 4006,4013 ****
  static unsigned int
  do_pre (void)
  {
!   execute_pre (false);
!   return TODO_rebuild_alias;
  }
  
  static bool
--- 4048,4054 ----
  static unsigned int
  do_pre (void)
  {
!   return TODO_rebuild_alias | execute_pre (false);
  }
  
  static bool
*************** struct tree_opt_pass pass_pre =
*** 4041,4048 ****
  static unsigned int
  execute_fre (void)
  {
!   execute_pre (true);
!   return 0;
  }
  
  static bool
--- 4082,4088 ----
  static unsigned int
  execute_fre (void)
  {
!   return execute_pre (true);
  }
  
  static bool