[PATCH][algorithmic] Fix PRs 30965 and 30978, make forwprop stronger and simpler

Richard Guenther rguenther@suse.de
Fri Mar 2 16:15:00 GMT 2007


This (unfortunately big) patch fixes the above two missed-optimization PRs
by restructuring the current COND_EXPR backward propagation into a
forward propagation of comparisons and a backward propagation into 
COND_EXPRs using (mostly) fold instead of re-implementing stuff.  It also
strengthens the backward propagation by doing full tree-combining on
both comparison arguments instead of just handling the X != 0 case.
This allows us to fold for example

  foo_1 = var_2 + 5
  if (foo_1 > var_2)

to a simple if (1).  Simplifying conditional statements is always worth
some minor extra work.

As I split out most of the generic stuff into helper functions this
final patch doesn't shrink tree-ssa-forwprop.c overall size anymore
(a previous version removed ~100 lines), but in this way the code is
easier to read.

Bootstrapped and tested on x86_64-unknown-linux-gnu.  The patch will be
on the vangelis C++/SPEC x86_64 tester tonight.

Ok for mainline?

Thanks,
Richard.

:ADDPATCH middle-end:

2007-03-02  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/30965
	PR tree-optimization/30978
	* Makefile.in (tree-ssa-forwprop.o): Depend on $(FLAGS_H).
        * tree-ssa-forwprop.c (forward_propagate_into_cond_1): Remove.
        (find_equivalent_equality_comparison): Likewise.
        (simplify_cond): Likewise.
        (get_prop_source_stmt): New helper.
        (get_prop_dest_stmt): Likewise.
	(can_propagate_from): Likewise.
	(remove_prop_source_from_use): Likewise.
        (combine_cond_expr_cond): Likewise.
        (forward_propagate_comparison): New function.
        (forward_propagate_into_cond): Rewrite to use fold for
        tree combining.
	(tree_ssa_forward_propagate_single_use_vars): Call
	forward_propagate_comparison to propagate comparisons.

	* gcc.dg/tree-ssa/pr30978.c: New testcase.
	* gcc.dg/tree-ssa/bool-3.c: Remove XFAIL, explain why.
	* gcc.dg/tree-ssa/ssa-fre-4.c: Use char instead of bool
	* gcc.dg/strict-overflow-5.c: Adjust tree dump scanning.


Index: testsuite/gcc.dg/tree-ssa/bool-3.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/bool-3.c	(revision 122428)
--- testsuite/gcc.dg/tree-ssa/bool-3.c	(working copy)
*************** int f(_Bool x)
*** 11,18 ****
    return y;
  }
  
! /* There should be no == 0. Though PHI-OPT or invert_truth does not
!    fold its tree.  */
! /* { dg-final { scan-tree-dump-times "== 0" 0 "optimized" { xfail *-*-* } } } */
  
  /* { dg-final { cleanup-tree-dump "optimized" } } */
--- 11,18 ----
    return y;
  }
  
! /* There should be no == 0.  Though PHI-OPT or invert_truth does not
!    fold its tree forwprop is able to clean up the mess.  */
! /* { dg-final { scan-tree-dump-times "== 0" 0 "optimized" } } */
  
  /* { dg-final { cleanup-tree-dump "optimized" } } */
Index: testsuite/gcc.dg/tree-ssa/ssa-fre-4.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/ssa-fre-4.c	(revision 122428)
--- testsuite/gcc.dg/tree-ssa/ssa-fre-4.c	(working copy)
***************
*** 3,15 ****
  
  /* From PR21608.  */
  
! #define bool _Bool
! static inline bool wrap(bool f) { return f; }
! bool bar(bool f)
  {
          return wrap(f);
  }
  
! /* { dg-final { scan-tree-dump "Replaced \\\(_Bool\\\) .*with " "fre" } } */
  /* { dg-final { scan-tree-dump "Replaced \\\(int\\\) .*with " "fre" } } */
  /* { dg-final { cleanup-tree-dump "fre" } } */
--- 3,14 ----
  
  /* From PR21608.  */
  
! static inline char wrap(char f) { return f; }
! char bar(char f)
  {
          return wrap(f);
  }
  
! /* { dg-final { scan-tree-dump "Replaced \\\(char\\\) .*with " "fre" } } */
  /* { dg-final { scan-tree-dump "Replaced \\\(int\\\) .*with " "fre" } } */
  /* { dg-final { cleanup-tree-dump "fre" } } */
Index: testsuite/gcc.dg/tree-ssa/pr30978.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/pr30978.c	(revision 0)
--- testsuite/gcc.dg/tree-ssa/pr30978.c	(revision 0)
***************
*** 0 ****
--- 1,14 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fdump-tree-optimized" } */
+ 
+ int foo(int a)
+ {
+   unsigned int b = a > 0;
+   char c = b;
+   _Bool d = c == 0;
+   int e = !d;
+   return e;
+ }
+ 
+ /* { dg-final { scan-tree-dump "return a > 0;" "optimized" } } */
+ /* { dg-final { cleanup-tree-dump "optimized" } } */
Index: testsuite/gcc.dg/strict-overflow-5.c
===================================================================
*** testsuite/gcc.dg/strict-overflow-5.c	(revision 122428)
--- testsuite/gcc.dg/strict-overflow-5.c	(working copy)
***************
*** 1,5 ****
  /* { dg-do compile } */
! /* { dg-options "-fstrict-overflow -O2 -fdump-tree-final_cleanup" } */
  
  /* We can only unroll when using strict overflow semantics.  */
  
--- 1,5 ----
  /* { dg-do compile } */
! /* { dg-options "-fstrict-overflow -O2 -fdump-tree-optimized" } */
  
  /* We can only unroll when using strict overflow semantics.  */
  
*************** int foo (int i)
*** 14,19 ****
    return r;
  }
  
! /* { dg-final { scan-tree-dump-times "r = 3" 1 "final_cleanup" } } */
! /* { dg-final { cleanup-tree-dump "final_cleanup" } } */
  
--- 14,19 ----
    return r;
  }
  
! /* { dg-final { scan-tree-dump "return 3" "optimized" } } */
! /* { dg-final { cleanup-tree-dump "optimized" } } */
  
Index: tree-ssa-forwprop.c
===================================================================
*** tree-ssa-forwprop.c	(revision 122428)
--- tree-ssa-forwprop.c	(working copy)
*************** Boston, MA 02110-1301, USA.  */
*** 33,38 ****
--- 33,39 ----
  #include "tree-pass.h"
  #include "tree-dump.h"
  #include "langhooks.h"
+ #include "flags.h"
  
  /* This pass propagates the RHS of assignment statements into use
     sites of the LHS of the assignment.  It's basically a specialized
*************** Boston, MA 02110-1301, USA.  */
*** 154,577 ****
  static bool cfg_changed;
  
  
! /* Given an SSA_NAME VAR, return true if and only if VAR is defined by
!    a comparison.  */
  
! static bool
! ssa_name_defined_by_comparison_p (tree var)
  {
!   tree def = SSA_NAME_DEF_STMT (var);
  
!   if (TREE_CODE (def) == GIMPLE_MODIFY_STMT)
!     {
!       tree rhs = GIMPLE_STMT_OPERAND (def, 1);
!       return COMPARISON_CLASS_P (rhs);
!     }
  
!   return 0;
  }
  
! /* Forward propagate a single-use variable into COND once.  Return a
!    new condition if successful.  Return NULL_TREE otherwise.  */
  
  static tree
! forward_propagate_into_cond_1 (tree cond, tree *test_var_p)
  {
!   tree new_cond = NULL_TREE;
!   enum tree_code cond_code = TREE_CODE (cond);
!   tree test_var = NULL_TREE;
!   tree def;
!   tree def_rhs;
! 
!   /* If the condition is not a lone variable or an equality test of an
!      SSA_NAME against an integral constant, then we do not have an
!      optimizable case.
! 
!      Note these conditions also ensure the COND_EXPR has no
!      virtual operands or other side effects.  */
!   if (cond_code != SSA_NAME
!       && !((cond_code == EQ_EXPR || cond_code == NE_EXPR)
! 	   && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
! 	   && CONSTANT_CLASS_P (TREE_OPERAND (cond, 1))
! 	   && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))))
!     return NULL_TREE;
! 
!   /* Extract the single variable used in the test into TEST_VAR.  */
!   if (cond_code == SSA_NAME)
!     test_var = cond;
!   else
!     test_var = TREE_OPERAND (cond, 0);
! 
!   /* Now get the defining statement for TEST_VAR.  Skip this case if
!      it's not defined by some GIMPLE_MODIFY_STMT.  */
!   def = SSA_NAME_DEF_STMT (test_var);
!   if (TREE_CODE (def) != GIMPLE_MODIFY_STMT)
!     return NULL_TREE;
  
!   def_rhs = GIMPLE_STMT_OPERAND (def, 1);
  
!   /* If TEST_VAR is set by adding or subtracting a constant
!      from an SSA_NAME, then it is interesting to us as we
!      can adjust the constant in the conditional and thus
!      eliminate the arithmetic operation.  */
!   if (TREE_CODE (def_rhs) == PLUS_EXPR
!       || TREE_CODE (def_rhs) == MINUS_EXPR)
!     {
!       tree op0 = TREE_OPERAND (def_rhs, 0);
!       tree op1 = TREE_OPERAND (def_rhs, 1);
! 
!       /* The first operand must be an SSA_NAME and the second
! 	 operand must be a constant.  */
!       if (TREE_CODE (op0) != SSA_NAME
! 	  || !CONSTANT_CLASS_P (op1)
! 	  || !INTEGRAL_TYPE_P (TREE_TYPE (op1)))
! 	return NULL_TREE;
! 
!       /* Don't propagate if the first operand occurs in
! 	 an abnormal PHI.  */
!       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
! 	return NULL_TREE;
! 
!       if (has_single_use (test_var))
! 	{
! 	  enum tree_code new_code;
! 	  tree t;
  
! 	  /* If the variable was defined via X + C, then we must
! 	     subtract C from the constant in the conditional.
! 	     Otherwise we add C to the constant in the
! 	     conditional.  The result must fold into a valid
! 	     gimple operand to be optimizable.  */
! 	  new_code = (TREE_CODE (def_rhs) == PLUS_EXPR
! 		      ? MINUS_EXPR : PLUS_EXPR);
! 	  t = int_const_binop (new_code, TREE_OPERAND (cond, 1), op1, 0);
! 	  if (!is_gimple_val (t))
! 	    return NULL_TREE;
  
! 	  new_cond = build2 (cond_code, boolean_type_node, op0, t);
! 	}
!     }
  
!   /* These cases require comparisons of a naked SSA_NAME or
!      comparison of an SSA_NAME against zero or one.  */
!   else if (TREE_CODE (cond) == SSA_NAME
! 	   || integer_zerop (TREE_OPERAND (cond, 1))
! 	   || integer_onep (TREE_OPERAND (cond, 1)))
      {
!       /* If TEST_VAR is set from a relational operation
! 	 between two SSA_NAMEs or a combination of an SSA_NAME
! 	 and a constant, then it is interesting.  */
!       if (COMPARISON_CLASS_P (def_rhs))
! 	{
! 	  tree op0 = TREE_OPERAND (def_rhs, 0);
! 	  tree op1 = TREE_OPERAND (def_rhs, 1);
! 
! 	  /* Both operands of DEF_RHS must be SSA_NAMEs or
! 	     constants.  */
! 	  if ((TREE_CODE (op0) != SSA_NAME
! 	       && !is_gimple_min_invariant (op0))
! 	      || (TREE_CODE (op1) != SSA_NAME
! 		  && !is_gimple_min_invariant (op1)))
! 	    return NULL_TREE;
! 
! 	  /* Don't propagate if the first operand occurs in
! 	     an abnormal PHI.  */
! 	  if (TREE_CODE (op0) == SSA_NAME
! 	      && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
! 	    return NULL_TREE;
! 
! 	  /* Don't propagate if the second operand occurs in
! 	     an abnormal PHI.  */
! 	  if (TREE_CODE (op1) == SSA_NAME
! 	      && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1))
! 	    return NULL_TREE;
! 
! 	  if (has_single_use (test_var))
! 	    {
! 	      /* TEST_VAR was set from a relational operator.  */
! 	      new_cond = build2 (TREE_CODE (def_rhs),
! 				 boolean_type_node, op0, op1);
! 
! 	      /* Invert the conditional if necessary.  */
! 	      if ((cond_code == EQ_EXPR
! 		   && integer_zerop (TREE_OPERAND (cond, 1)))
! 		  || (cond_code == NE_EXPR
! 		      && integer_onep (TREE_OPERAND (cond, 1))))
! 		{
! 		  new_cond = invert_truthvalue (new_cond);
! 
! 		  /* If we did not get a simple relational
! 		     expression or bare SSA_NAME, then we can
! 		     not optimize this case.  */
! 		  if (!COMPARISON_CLASS_P (new_cond)
! 		      && TREE_CODE (new_cond) != SSA_NAME)
! 		    new_cond = NULL_TREE;
! 		}
! 	    }
! 	}
! 
!       /* If TEST_VAR is set from a TRUTH_NOT_EXPR, then it
! 	 is interesting.  */
!       else if (TREE_CODE (def_rhs) == TRUTH_NOT_EXPR)
! 	{
! 	  enum tree_code new_code;
! 
! 	  def_rhs = TREE_OPERAND (def_rhs, 0);
! 
! 	  /* DEF_RHS must be an SSA_NAME or constant.  */
! 	  if (TREE_CODE (def_rhs) != SSA_NAME
! 	      && !is_gimple_min_invariant (def_rhs))
! 	    return NULL_TREE;
! 
! 	  /* Don't propagate if the operand occurs in
! 	     an abnormal PHI.  */
! 	  if (TREE_CODE (def_rhs) == SSA_NAME
! 	      && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_rhs))
! 	    return NULL_TREE;
! 
! 	  if (cond_code == SSA_NAME
! 	      || (cond_code == NE_EXPR
! 		  && integer_zerop (TREE_OPERAND (cond, 1)))
! 	      || (cond_code == EQ_EXPR
! 		  && integer_onep (TREE_OPERAND (cond, 1))))
! 	    new_code = EQ_EXPR;
! 	  else
! 	    new_code = NE_EXPR;
! 
! 	  new_cond = build2 (new_code, boolean_type_node, def_rhs,
! 			     fold_convert (TREE_TYPE (def_rhs),
! 					   integer_zero_node));
! 	}
! 
!       /* If TEST_VAR was set from a cast of an integer type
! 	 to a boolean type or a cast of a boolean to an
! 	 integral, then it is interesting.  */
!       else if (TREE_CODE (def_rhs) == NOP_EXPR
! 	       || TREE_CODE (def_rhs) == CONVERT_EXPR)
! 	{
! 	  tree outer_type;
! 	  tree inner_type;
! 
! 	  outer_type = TREE_TYPE (def_rhs);
! 	  inner_type = TREE_TYPE (TREE_OPERAND (def_rhs, 0));
! 
! 	  if ((TREE_CODE (outer_type) == BOOLEAN_TYPE
! 	       && INTEGRAL_TYPE_P (inner_type))
! 	      || (TREE_CODE (inner_type) == BOOLEAN_TYPE
! 		  && INTEGRAL_TYPE_P (outer_type)))
! 	    ;
! 	  else if (INTEGRAL_TYPE_P (outer_type)
! 		   && INTEGRAL_TYPE_P (inner_type)
! 		   && TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME
! 		   && ssa_name_defined_by_comparison_p (TREE_OPERAND (def_rhs,
! 								      0)))
! 	    ;
! 	  else
! 	    return NULL_TREE;
! 
! 	  /* Don't propagate if the operand occurs in
! 	     an abnormal PHI.  */
! 	  if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME
! 	      && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND
! 						  (def_rhs, 0)))
! 	    return NULL_TREE;
! 
! 	  if (has_single_use (test_var))
! 	    {
! 	      enum tree_code new_code;
! 	      tree new_arg;
! 
! 	      if (cond_code == SSA_NAME
! 		  || (cond_code == NE_EXPR
! 		      && integer_zerop (TREE_OPERAND (cond, 1)))
! 		  || (cond_code == EQ_EXPR
! 		      && integer_onep (TREE_OPERAND (cond, 1))))
! 		new_code = NE_EXPR;
! 	      else
! 		new_code = EQ_EXPR;
  
! 	      new_arg = TREE_OPERAND (def_rhs, 0);
! 	      new_cond = build2 (new_code, boolean_type_node, new_arg,
! 				 fold_convert (TREE_TYPE (new_arg),
! 					       integer_zero_node));
! 	    }
! 	}
      }
  
!   *test_var_p = test_var;
!   return new_cond;
! }
  
! /* COND is a condition of the form:
  
!      x == const or x != const
  
!    Look back to x's defining statement and see if x is defined as
  
!      x = (type) y;
  
!    If const is unchanged if we convert it to type, then we can build
!    the equivalent expression:
  
  
!       y == const or y != const
  
!    Which may allow further optimizations.
  
!    Return the equivalent comparison or NULL if no such equivalent comparison
!    was found.  */
  
  static tree
! find_equivalent_equality_comparison (tree cond)
  {
!   tree op0 = TREE_OPERAND (cond, 0);
!   tree op1 = TREE_OPERAND (cond, 1);
!   tree def_stmt = SSA_NAME_DEF_STMT (op0);
! 
!   while (def_stmt
! 	 && TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
! 	 && TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == SSA_NAME)
!     def_stmt = SSA_NAME_DEF_STMT (GIMPLE_STMT_OPERAND (def_stmt, 1));
! 
!   /* OP0 might have been a parameter, so first make sure it
!      was defined by a GIMPLE_MODIFY_STMT.  */
!   if (def_stmt && TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT)
!     {
!       tree def_rhs = GIMPLE_STMT_OPERAND (def_stmt, 1);
! 
!       /* If either operand to the comparison is a pointer to
! 	 a function, then we can not apply this optimization
! 	 as some targets require function pointers to be
! 	 canonicalized and in this case this optimization would
! 	 eliminate a necessary canonicalization.  */
!       if ((POINTER_TYPE_P (TREE_TYPE (op0))
! 	   && TREE_CODE (TREE_TYPE (TREE_TYPE (op0))) == FUNCTION_TYPE)
! 	  || (POINTER_TYPE_P (TREE_TYPE (op1))
! 	      && TREE_CODE (TREE_TYPE (TREE_TYPE (op1))) == FUNCTION_TYPE))
! 	return NULL;
! 	      
!       /* Now make sure the RHS of the GIMPLE_MODIFY_STMT is a typecast.  */
!       if ((TREE_CODE (def_rhs) == NOP_EXPR
! 	   || TREE_CODE (def_rhs) == CONVERT_EXPR)
! 	  && TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME)
! 	{
! 	  tree def_rhs_inner = TREE_OPERAND (def_rhs, 0);
! 	  tree def_rhs_inner_type = TREE_TYPE (def_rhs_inner);
! 	  tree new;
! 
! 	  if (TYPE_PRECISION (def_rhs_inner_type)
! 	      > TYPE_PRECISION (TREE_TYPE (def_rhs)))
! 	    return NULL;
! 
! 	  /* If the inner type of the conversion is a pointer to
! 	     a function, then we can not apply this optimization
! 	     as some targets require function pointers to be
! 	     canonicalized.  This optimization would result in
! 	     canonicalization of the pointer when it was not originally
! 	     needed/intended.  */
! 	  if (POINTER_TYPE_P (def_rhs_inner_type)
! 	      && TREE_CODE (TREE_TYPE (def_rhs_inner_type)) == FUNCTION_TYPE)
! 	    return NULL;
! 
! 	  /* What we want to prove is that if we convert OP1 to
! 	     the type of the object inside the NOP_EXPR that the
! 	     result is still equivalent to SRC. 
! 
! 	     If that is true, the build and return new equivalent
! 	     condition which uses the source of the typecast and the
! 	     new constant (which has only changed its type).  */
! 	  new = fold_build1 (TREE_CODE (def_rhs), def_rhs_inner_type, op1);
! 	  STRIP_USELESS_TYPE_CONVERSION (new);
! 	  if (is_gimple_val (new) && tree_int_cst_equal (new, op1))
! 	    return build2 (TREE_CODE (cond), TREE_TYPE (cond),
! 			   def_rhs_inner, new);
! 	}
!     }
!   return NULL;
! }
  
! /* EXPR is a COND_EXPR
!    STMT is the statement containing EXPR.
  
!    This routine attempts to find equivalent forms of the condition
!    which we may be able to optimize better.  */
  
! static void
! simplify_cond (tree cond_expr, tree stmt)
! {
!   tree cond = COND_EXPR_COND (cond_expr);
  
!   if (COMPARISON_CLASS_P (cond))
      {
!       tree op0 = TREE_OPERAND (cond, 0);
!       tree op1 = TREE_OPERAND (cond, 1);
  
!       if (TREE_CODE (op0) == SSA_NAME && is_gimple_min_invariant (op1))
! 	{
! 	  /* First see if we have test of an SSA_NAME against a constant
! 	     where the SSA_NAME is defined by an earlier typecast which
! 	     is irrelevant when performing tests against the given
! 	     constant.  */
! 	  if (TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
! 	    {
! 	      tree new_cond = find_equivalent_equality_comparison (cond);
  
! 	      if (new_cond)
! 		{
! 		  COND_EXPR_COND (cond_expr) = new_cond;
! 		  update_stmt (stmt);
! 		}
! 	    }
! 	}
!     }
  }
  
! /* Forward propagate a single-use variable into COND_EXPR as many
!    times as possible.  */
  
  static void
  forward_propagate_into_cond (tree cond_expr, tree stmt)
  {
!   gcc_assert (TREE_CODE (cond_expr) == COND_EXPR);
! 
!   while (1)
!     {
!       tree test_var = NULL_TREE;
!       tree cond = COND_EXPR_COND (cond_expr);
!       tree new_cond = forward_propagate_into_cond_1 (cond, &test_var);
! 
!       /* Return if unsuccessful.  */
!       if (new_cond == NULL_TREE)
! 	break;
  
!       /* Dump details.  */
!       if (dump_file && (dump_flags & TDF_DETAILS))
! 	{
! 	  fprintf (dump_file, "  Replaced '");
! 	  print_generic_expr (dump_file, cond, dump_flags);
! 	  fprintf (dump_file, "' with '");
! 	  print_generic_expr (dump_file, new_cond, dump_flags);
! 	  fprintf (dump_file, "'\n");
! 	}
! 
!       COND_EXPR_COND (cond_expr) = new_cond;
!       update_stmt (stmt);
! 
!       if (has_zero_uses (test_var))
! 	{
! 	  tree def = SSA_NAME_DEF_STMT (test_var);
! 	  block_stmt_iterator bsi = bsi_for_stmt (def);
! 	  bsi_remove (&bsi, true);
! 	  release_defs (def);
! 	}
!     }
! 
!   /* There are further simplifications that can be performed
!      on COND_EXPRs.  Specifically, when comparing an SSA_NAME
!      against a constant where the SSA_NAME is the result of a
!      conversion.  Perhaps this should be folded into the rest
!      of the COND_EXPR simplification code.  */
!   simplify_cond (cond_expr, stmt);
  }
  
  /* We've just substituted an ADDR_EXPR into stmt.  Update all the 
--- 155,457 ----
  static bool cfg_changed;
  
  
! /* Get the next statement we can propagate NAMEs value into skipping
!    trivial copies.  Returns the statement that is suitable as a
!    propagation destination or NULL_TREE if there is no such one.
!    This only returns destinations in a single-use chain.  FINAL_NAME_P
!    if non-NULL is written to the ssa name that represents the use.  */
  
! static tree
! get_prop_dest_stmt (tree name, tree *final_name_p)
  {
!   use_operand_p use;
!   tree use_stmt;
  
!   do {
!     /* If name has multiple uses, bail out.  */
!     if (!single_imm_use (name, &use, &use_stmt))
!       return NULL_TREE;
! 
!     /* If this is not a trivial copy, we found it.  */
!     if (TREE_CODE (use_stmt) != GIMPLE_MODIFY_STMT
! 	|| TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 0)) != SSA_NAME
! 	|| GIMPLE_STMT_OPERAND (use_stmt, 1) != name)
!       break;
! 
!     /* Continue searching uses of the copy destination.  */
!     name = GIMPLE_STMT_OPERAND (use_stmt, 0);
!   } while (1);
  
!   if (final_name_p)
!     *final_name_p = name;
! 
!   return use_stmt;
  }
  
! /* Get the statement we can propagate from into NAME skipping
!    trivial copies.  Returns the statement which defines the
!    propagation source or NULL_TREE if there is no such one.
!    If SINGLE_USE_ONLY is set considers only sources which have
!    a single use chain up to NAME.  If SINGLE_USE_P is non-null,
!    it is set to whether the chain to NAME is a single use chain
!    or not.  SINGLE_USE_P is not written to if SINGLE_USE_ONLY is set.  */
  
  static tree
! get_prop_source_stmt (tree name, bool single_use_only, bool *single_use_p)
  {
!   bool single_use = true;
  
!   do {
!     tree def_stmt = SSA_NAME_DEF_STMT (name);
  
!     if (!has_single_use (name))
!       {
! 	single_use = false;
! 	if (single_use_only)
! 	  return NULL_TREE;
!       }
! 
!     /* If name is defined by a PHI node or is the default def, bail out.  */
!     if (TREE_CODE (def_stmt) != GIMPLE_MODIFY_STMT)
!       return NULL_TREE;
! 
!     /* 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);
! }
  
! /* Checks if the destination ssa name in DEF_STMT can be used as
!    propagation source.  Returns true if so, otherwise false.  */
  
! static bool
! can_propagate_from (tree def_stmt)
! {
!   tree rhs = GIMPLE_STMT_OPERAND (def_stmt, 1);
  
!   /* We cannot propagate ssa names that occur in abnormal phi nodes.  */
!   switch (TREE_CODE_LENGTH (TREE_CODE (rhs)))
      {
!     case 3:
!       if (TREE_OPERAND (rhs, 2) != NULL_TREE
! 	  && TREE_CODE (TREE_OPERAND (rhs, 2)) == SSA_NAME
! 	  && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (rhs, 2)))
! 	return false;
!     case 2:
!       if (TREE_OPERAND (rhs, 1) != NULL_TREE
! 	  && TREE_CODE (TREE_OPERAND (rhs, 1)) == SSA_NAME
! 	  && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (rhs, 1)))
! 	return false;
!     case 1:
!       if (TREE_OPERAND (rhs, 0) != NULL_TREE
! 	  && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
! 	  && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (rhs, 0)))
! 	return false;
!       break;
  
!     default:
!       return false;
      }
  
!   /* If the definition is a conversion of a pointer to a function type,
!      then we can not apply optimizations as some targets require function
!      pointers to be canonicalized and in this case this optimization could
!      eliminate a necessary canonicalization.  */
!   if ((TREE_CODE (rhs) == NOP_EXPR
!        || TREE_CODE (rhs) == CONVERT_EXPR)
!       && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))
!       && TREE_CODE (TREE_TYPE (TREE_TYPE
! 			        (TREE_OPERAND (rhs, 0)))) == FUNCTION_TYPE)
!     return false;
  
!   return true;
! }
  
! /* Remove a copy chain ending in NAME along the defs but not
!    further or including UP_TO_STMT.  If NAME was replaced in
!    its only use then this function can be used to clean up
!    dead stmts.  Returns true if UP_TO_STMT can be removed
!    as well, otherwise false.  */
  
! static bool
! remove_prop_source_from_use (tree name, tree up_to_stmt)
! {
!   block_stmt_iterator bsi;
!   tree stmt;
  
!   do {
!     if (!has_zero_uses (name))
!       return false;
  
!     stmt = SSA_NAME_DEF_STMT (name);
!     if (stmt == up_to_stmt)
!       return true;
  
+     bsi = bsi_for_stmt (stmt);
+     release_defs (stmt);
+     bsi_remove (&bsi, true);
  
!     name = GIMPLE_STMT_OPERAND (stmt, 1);
!   } while (TREE_CODE (name) == SSA_NAME);
  
!   return false;
! }
  
! /* Combine OP0 CODE OP1 in the context of a COND_EXPR.  Returns
!    the folded result in a form suitable for COND_EXPR_COND or
!    NULL_TREE, if there is no suitable simplified form.  If
!    INVARIANT_ONLY is true only gimple_min_invariant results are
!    considered simplified.  */
  
  static tree
! combine_cond_expr_cond (enum tree_code code, tree type,
! 			tree op0, tree op1, bool invariant_only)
  {
!   tree t;
  
!   gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
  
!   t = fold_binary (code, type, op0, op1);
!   if (!t)
!     return NULL_TREE;
  
!   /* Require that we got a boolean type out if we put one in.  */
!   gcc_assert (TREE_CODE (TREE_TYPE (t)) == TREE_CODE (type));
  
!   /* For (bool)x use x != 0.  */
!   if (TREE_CODE (t) == NOP_EXPR
!       && TREE_TYPE (t) == boolean_type_node)
!     {
!       tree top0 = TREE_OPERAND (t, 0);
!       t = build2 (NE_EXPR, type,
! 		  top0, build_int_cst (TREE_TYPE (top0), 0));
!     }
!   /* For !x use x == 0.  */
!   else if (TREE_CODE (t) == TRUTH_NOT_EXPR)
!     {
!       tree top0 = TREE_OPERAND (t, 0);
!       t = build2 (EQ_EXPR, type,
! 		  top0, build_int_cst (TREE_TYPE (top0), 0));
!     }
!   /* For cmp ? 1 : 0 use cmp.  */
!   else if (TREE_CODE (t) == COND_EXPR
! 	   && COMPARISON_CLASS_P (TREE_OPERAND (t, 0))
! 	   && integer_onep (TREE_OPERAND (t, 1))
! 	   && integer_zerop (TREE_OPERAND (t, 2)))
      {
!       tree top0 = TREE_OPERAND (t, 0);
!       t = build2 (TREE_CODE (top0), type,
! 		  TREE_OPERAND (top0, 0), TREE_OPERAND (top0, 1));
!     }
  
!   /* Bail out if we required an invariant but didn't get one.  */
!   if (invariant_only
!       && !is_gimple_min_invariant (t))
!     return NULL_TREE;
  
!   /* A valid conditional for a COND_EXPR is either a gimple value
!      or a comparison with two gimple value operands.  */
!   if (is_gimple_val (t)
!       || (COMPARISON_CLASS_P (t)
! 	  && is_gimple_val (TREE_OPERAND (t, 0))
! 	  && is_gimple_val (TREE_OPERAND (t, 1))))
!     return t;
! 
!   return NULL_TREE;
  }
  
! /* Propagate from the ssa name definition statements of COND_EXPR
!    in statement STMT into the conditional if that simplifies it.  */
  
  static void
  forward_propagate_into_cond (tree cond_expr, tree stmt)
  {
!   do {
!     tree tmp = NULL_TREE;
!     tree cond = COND_EXPR_COND (cond_expr);
!     tree name, def_stmt, rhs;
!     bool single_use_p;
! 
!     /* We can do tree combining on SSA_NAME and comparison expressions.  */
!     if (COMPARISON_CLASS_P (cond)
! 	&& TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME)
!       {
! 	/* For comparisons use the first operand, that is likely to
! 	   simplify comparisons against constants.  */
! 	name = TREE_OPERAND (cond, 0);
! 	def_stmt = get_prop_source_stmt (name, false, &single_use_p);
! 	if (def_stmt != NULL_TREE
! 	    && can_propagate_from (def_stmt))
! 	  {
! 	    tree op1 = TREE_OPERAND (cond, 1);
! 	    rhs = GIMPLE_STMT_OPERAND (def_stmt, 1);
! 	    tmp = combine_cond_expr_cond (TREE_CODE (cond), boolean_type_node,
! 				          fold_convert (TREE_TYPE (op1), rhs),
! 				          op1, !single_use_p);
! 	  }
! 	/* If that wasn't successful, try the second operand.  */
! 	if (tmp == NULL_TREE
! 	    && TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME)
! 	  {
! 	    tree op0 = TREE_OPERAND (cond, 0);
! 	    name = TREE_OPERAND (cond, 1);
! 	    def_stmt = get_prop_source_stmt (name, false, &single_use_p);
! 	    if (def_stmt == NULL_TREE
! 	        || !can_propagate_from (def_stmt))
! 	      return;
! 
! 	    rhs = GIMPLE_STMT_OPERAND (def_stmt, 1);
! 	    tmp = combine_cond_expr_cond (TREE_CODE (cond), boolean_type_node,
! 					  op0,
! 				          fold_convert (TREE_TYPE (op0), rhs),
! 					  !single_use_p);
! 	  }
!       }
!     else if (TREE_CODE (cond) == SSA_NAME)
!       {
! 	name = cond;
! 	def_stmt = get_prop_source_stmt (name, true, NULL);
! 	if (def_stmt == NULL_TREE
! 	    || !can_propagate_from (def_stmt))
! 	  return;
! 
! 	rhs = GIMPLE_STMT_OPERAND (def_stmt, 1);
! 	tmp = combine_cond_expr_cond (NE_EXPR, boolean_type_node, rhs,
! 				      build_int_cst (TREE_TYPE (rhs), 0),
! 				      false);
!       }
! 
!     if (tmp)
!       {
! 	if (dump_file && tmp)
! 	  {
! 	    fprintf (dump_file, "  Replaced '");
! 	    print_generic_expr (dump_file, cond, 0);
! 	    fprintf (dump_file, "' with '");
! 	    print_generic_expr (dump_file, tmp, 0);
! 	    fprintf (dump_file, "'\n");
! 	  }
! 
! 	COND_EXPR_COND (cond_expr) = unshare_expr (tmp);
! 	update_stmt (stmt);
! 
! 	/* Remove defining statements.  */
! 	remove_prop_source_from_use (name, NULL);
! 
! 	/* Continue combining.  */
! 	continue;
!       }
  
!     break;
!   } while (1);
  }
  
  /* We've just substituted an ADDR_EXPR into stmt.  Update all the 
*************** forward_propagate_addr_expr (tree stmt, 
*** 870,875 ****
--- 750,853 ----
    return all;
  }
  
+ /* Forward propagate the comparison COND defined in STMT like
+    cond_1 = x CMP y to uses of the form
+      a_1 = (T')cond_1
+      a_1 = !cond_1
+      a_1 = cond_1 != 0
+    Returns true if stmt is now unused.  */
+ 
+ static bool
+ forward_propagate_comparison (tree cond, tree stmt)
+ {
+   tree name = GIMPLE_STMT_OPERAND (stmt, 0);
+   tree use_stmt, tmp = NULL_TREE;
+ 
+   /* Don't propagate ssa names that occur in abnormal phis.  */
+   if ((TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
+        && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (cond, 0)))
+       || (TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME
+ 	  && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (cond, 1))))
+     return false;
+ 
+   /* Do not un-cse comparisons.  But propagate through copies.  */
+   use_stmt = get_prop_dest_stmt (name, &name);
+   if (use_stmt == NULL_TREE)
+     return false;
+ 
+   /* Conversion of the condition result to another integral type.  */
+   if (TREE_CODE (use_stmt) == GIMPLE_MODIFY_STMT
+       && (TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) == CONVERT_EXPR
+ 	  || TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) == NOP_EXPR
+           || COMPARISON_CLASS_P (GIMPLE_STMT_OPERAND (use_stmt, 1))
+           || TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) == TRUTH_NOT_EXPR)
+       && INTEGRAL_TYPE_P (TREE_TYPE (GIMPLE_STMT_OPERAND (use_stmt, 0))))
+     {
+       tree lhs = GIMPLE_STMT_OPERAND (use_stmt, 0);
+       tree rhs = GIMPLE_STMT_OPERAND (use_stmt, 1);
+ 
+       /* We can propagate the condition into a conversion.  */
+       if (TREE_CODE (rhs) == CONVERT_EXPR
+ 	  || TREE_CODE (rhs) == NOP_EXPR)
+ 	{
+ 	  /* Avoid using fold here as that may create a COND_EXPR with
+ 	     non-boolean condition as canonical form.  */
+ 	  tmp = build2 (TREE_CODE (cond), TREE_TYPE (lhs), 
+ 			TREE_OPERAND (cond, 0), TREE_OPERAND (cond, 1));
+ 	}
+       /* We can propagate the condition into X op CST where op
+ 	 is EQ_EXRP or NE_EXPR and CST is either one or zero.  */
+       else if (COMPARISON_CLASS_P (rhs)
+ 	       && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
+ 	       && TREE_CODE (TREE_OPERAND (rhs, 1)) == INTEGER_CST)
+ 	{
+ 	  enum tree_code code = TREE_CODE (rhs);
+ 	  tree cst = TREE_OPERAND (rhs, 1);
+ 
+ 	  tmp = combine_cond_expr_cond (code, TREE_TYPE (lhs),
+ 					fold_convert (TREE_TYPE (cst), cond),
+ 					cst, false);
+ 	  if (tmp == NULL_TREE)
+ 	    return false;
+ 	}
+       /* We can propagate the condition into a statement that
+ 	 computes the logical negation of the comparison result.  */
+       else if (TREE_CODE (rhs) == TRUTH_NOT_EXPR)
+ 	{
+ 	  tree type = TREE_TYPE (TREE_OPERAND (cond, 0));
+ 	  bool nans = HONOR_NANS (TYPE_MODE (type));
+ 	  enum tree_code code;
+ 	  code = invert_tree_comparison (TREE_CODE (cond), nans);
+ 	  if (code == ERROR_MARK)
+ 	    return false;
+ 
+ 	  tmp = build2 (code, TREE_TYPE (lhs), TREE_OPERAND (cond, 0),
+ 			TREE_OPERAND (cond, 1));
+ 	}
+       else
+ 	return false;
+ 
+       GIMPLE_STMT_OPERAND (use_stmt, 1) = unshare_expr (tmp);
+       update_stmt (use_stmt);
+ 
+       /* Remove defining statements.  */
+       remove_prop_source_from_use (name, stmt);
+ 
+       if (dump_file && (dump_flags & TDF_DETAILS))
+ 	{
+ 	  fprintf (dump_file, "  Replaced '");
+ 	  print_generic_expr (dump_file, rhs, dump_flags);
+ 	  fprintf (dump_file, "' with '");
+ 	  print_generic_expr (dump_file, tmp, dump_flags);
+ 	  fprintf (dump_file, "'\n");
+ 	}
+ 
+       return true;
+     }
+ 
+   return false;
+ }
+ 
  /* If we have lhs = ~x (STMT), look and see if earlier we had x = ~y.
     If so, we can change STMT into lhs = y which can later be copy
     propagated.  Similarly for negation. 
*************** tree_ssa_forward_propagate_single_use_va
*** 1023,1028 ****
--- 1001,1017 ----
                    forward_propagate_into_cond (rhs, stmt);
  		  bsi_next (&bsi);
                  }
+ 	      else if (COMPARISON_CLASS_P (rhs))
+ 		{
+ 		  if (forward_propagate_comparison (rhs, stmt))
+ 		    {
+ 		      release_defs (stmt);
+ 		      todoflags |= TODO_remove_unused_locals;
+ 		      bsi_remove (&bsi, true);
+ 		    }
+ 		  else
+ 		    bsi_next (&bsi);
+ 		}
  	      else
  		bsi_next (&bsi);
  	    }
Index: Makefile.in
===================================================================
*** Makefile.in	(revision 122428)
--- Makefile.in	(working copy)
*************** tree-ssa-dse.o : tree-ssa-dse.c $(CONFIG
*** 1990,1996 ****
  tree-ssa-forwprop.o : tree-ssa-forwprop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
     $(TM_H) $(GGC_H) $(TREE_H) $(RTL_H) $(TM_P_H) $(BASIC_BLOCK_H) \
     $(TREE_FLOW_H) tree-pass.h $(TREE_DUMP_H) $(DIAGNOSTIC_H) $(TIMEVAR_H) \
!    langhooks.h
  tree-ssa-phiopt.o : tree-ssa-phiopt.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
     $(TM_H) $(GGC_H) $(TREE_H) $(RTL_H) $(TM_P_H) $(BASIC_BLOCK_H) \
     $(TREE_FLOW_H) tree-pass.h $(TREE_DUMP_H) langhooks.h $(FLAGS_H) \
--- 1990,1996 ----
  tree-ssa-forwprop.o : tree-ssa-forwprop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
     $(TM_H) $(GGC_H) $(TREE_H) $(RTL_H) $(TM_P_H) $(BASIC_BLOCK_H) \
     $(TREE_FLOW_H) tree-pass.h $(TREE_DUMP_H) $(DIAGNOSTIC_H) $(TIMEVAR_H) \
!    langhooks.h $(FLAGS_H)
  tree-ssa-phiopt.o : tree-ssa-phiopt.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
     $(TM_H) $(GGC_H) $(TREE_H) $(RTL_H) $(TM_P_H) $(BASIC_BLOCK_H) \
     $(TREE_FLOW_H) tree-pass.h $(TREE_DUMP_H) langhooks.h $(FLAGS_H) \



More information about the Gcc-patches mailing list