[patch] tree-ssa-forwprop.c: Catch more forward propagationopportunities.

[Kazu Hirata <kazu at cs dot umass dot edu>]

Hi,

Attached is a patch to catch more forward propagation opportunities.

Consider

int
foo (int a)
{
  int b = a != 0;
  unsigned char c = b;
  if (c)
    return 1;
  else
    return 0;
}

After the first forwprop, we get

  b_3 = a_2 != 0;
  c_4 = (unsigned char) b_3;
  if (c_4 != 0) goto <L0>; else goto <L2>;

Note that we can actually propagate the preceding two statements into
the COND_EXPR and obtain much shorter

  if (a_2 != 0) goto <L0>; else goto <L2>;

The patch solves this problem by having a COND_EXPR "eat" an
integer-integer cast if the rhs of the cast is defined by a
comparison.  In the example above, b_3 is defined by a comparison, so
we first propagate the cast into the COND_EXPR and get

  if (b_3 != 0) goto <L0>; else goto <L2>;

After that, the existing code in tree-ssa-forwprop.c can forward
propagate a_2 != 0 into the COND_EXPR and get

  if (a_2 != 0) goto <L0>; else goto <L2>;

as desired.

Without this patch, we forward propagate 4983 statements while
compiling cc1-i files.  With this patch, we do 6297 statements.  An
impressive 26% improvement!

Note that forward propagation into COND_EXPRs is important for both
jump threading and VRP so that we can create useful conditoinal
equivalences and add ASSERT_EXPRs, respectively.  I'll post a message
on this later.

Although I am working on a more generic combiner that's not restricted
to COND_EXPRs, and I expect much of the code in tree-ssa-forwprop.c
will be replaced by fold, I would like to get this patch in anyway as
a 26% improvement is too good to miss.

Tested on i686-pc-linux-gnu.  OK to apply?

Kazu Hirata

2005-04-15  Kazu Hirata  <kazu@cs.umass.edu>

	PR tree-optimization/21031
	* tree-ssa-forwprop.c (ssa_name_defined_by_comparison_p): New.
	(forward_propagate_into_cond_1): Call it.  Forward propagate
	integer-integer casts into COND_EXPRs.

2005-04-15  Kazu Hirata  <kazu@cs.umass.edu>

	PR tree-optimization/21031
	* gcc.dg/tree-ssa/pr21031.c: New.

Index: tree-ssa-forwprop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-forwprop.c,v
retrieving revision 2.13
diff -u -d -p -r2.13 tree-ssa-forwprop.c
--- tree-ssa-forwprop.c	13 Apr 2005 06:07:03 -0000	2.13
+++ tree-ssa-forwprop.c	14 Apr 2005 19:55:18 -0000
@@ -109,6 +109,23 @@ Boston, MA 02111-1307, USA.  */
 
    This will (of course) be extended as other needs arise.  */
 
+/* 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) == MODIFY_EXPR)
+    {
+      tree rhs = TREE_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.  */
 
@@ -303,6 +320,12 @@ forward_propagate_into_cond_1 (tree cond
 	      || (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;
 
--- /dev/null	2005-04-13 14:59:22.325563136 -0400
+++ testsuite/gcc.dg/tree-ssa/pr21031.c	2005-04-14 21:51:08.000000000 -0400
@@ -0,0 +1,20 @@
+/* PR tree-optimization/21031
+
+   Make sure that a != 0 is propagated into the "if" statement.  */
+
+/* { dg-do compile } */
+/* { dg-options "-O1 -fdump-tree-forwprop1-details" } */
+
+int
+foo (int a)
+{
+  int b = a != 0;
+  unsigned char c = b;
+  if (c)
+    return 1;
+  else
+    return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "Replaced" 2 "forwprop1"} } */
+/* { dg-final { cleanup-tree-dump "forwprop1" } } */