[patch] tree-vrp.c: Insert more ASSERT_EXPRs.

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

Hi,

Attached is a patch to improve VRP by inserting more ASSERT_EXPRs
where we should be inserting.

maybe_add_assert_expr inserts ASSERT_EXPRs while walking the dominator
tree in the depth first manner.

The problem is that we don't walk the entire dominator tree due to a
bug, preventing some ASSERT_EXPRs from being inserted.  Specifically,
when we are at a COND_EXPR of a basic block BB, we only recurse into
dominator children that are CFG successors of BB.  For example,
consider a typical if-then-else diamond.

    A (ending with a COND_EXPR)
   / \
  B   C
   \ /
    D
    :
    :

In this case, we would recurse into B and C but not D.  Since B and C
do not dominate D, and D is not a CFG successor of A, the dominator
walk ends there.

The patch fixes this problem by recursing into dominator children that
are not CFG successors after we are done with walking the "then" and
"else" arms of the COND_EXPR.

With the current pass ordering, the number of COND_EXPRs that VRP
folds into unconditional jumps does increase from 29 to 50 or so, but
that's not as interesting as DOM does some of what VRP does.

With a TCB-like pass ordering

  NEXT_PASS (pass_ccp);
  NEXT_PASS (pass_copy_prop);
  NEXT_PASS (pass_fre);
  NEXT_PASS (pass_dce);
  NEXT_PASS (pass_vrp);

but without this patch, VRP folds 348 COND_EXPRs into unconditonal
jumps while compiling cc1-i files.  With this patch, VRP folds 658
COND_EXPRs into unconditional jumps.  An 89% improvement!  (There are
other cases where we fold COND_EXPRs into an SSA_NAME, but I am not
including those as they are not as cool as folding them into
unconditonal jumps.)

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

Kazu Hirata

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

	PR tree-optimization/20702
	* tree-vrp.c (maybe_add_assert_expr): Recurse into
	dominator children that haven't been walked into.

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

	PR tree-optimization/20702
	* gcc.dg/tree-ssa/pr20702.c: New.

Index: tree-vrp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-vrp.c,v
retrieving revision 2.3
diff -u -d -p -r2.3 tree-vrp.c
--- tree-vrp.c	11 Apr 2005 15:05:31 -0000	2.3
+++ tree-vrp.c	11 Apr 2005 15:25:09 -0000
@@ -1500,6 +1500,7 @@ maybe_add_assert_expr (basic_block bb)
       edge e;
       edge_iterator ei;
       tree op, cond;
+      basic_block son;
       
       cond = COND_EXPR_COND (last);
 
@@ -1554,6 +1555,17 @@ maybe_add_assert_expr (basic_block bb)
 
       /* Finally, mark all the COND_EXPR operands as found.  */
       SET_BIT (found, SSA_NAME_VERSION (op));
+
+      /* Recurse into the dominator children of BB that are not BB's
+	 immediate successors.  Note that we have already visited BB's
+	 other dominator children above.  */
+      for (son = first_dom_son (CDI_DOMINATORS, bb);
+	   son;
+	   son = next_dom_son (CDI_DOMINATORS, son))
+	{
+	  if (find_edge (bb, son) == NULL)
+	    added |= maybe_add_assert_expr (son);
+	}
     }
   else
     {
--- /dev/null	2005-04-11 14:38:08.227034184 -0400
+++ testsuite/gcc.dg/tree-ssa/pr20702.c	2005-04-08 23:38:22.000000000 -0400
@@ -0,0 +1,28 @@
+/* PR tree-optimization/20702
+   VRP did not insert ASSERT_EXPRs into dominator dominator children
+   of a basic block ending with COND_EXPR unless the children are also
+   immediate successors of the basic block.  */
+
+/* { dg-do compile } */
+/* { dg-options "-O2 -fno-tree-dominator-opts -fdump-tree-vrp-details" } */
+
+extern void bar (int);
+
+int
+foo (int *p, int b)
+{
+  int a;
+
+  if (b)
+    bar (123);
+  else
+    bar (321);
+
+  a = *p;
+  if (p == 0)
+    return 0;
+
+  return a;
+}
+
+/* { dg-final { scan-tree-dump-times "Folding predicate" 1 "vrp"} } */