Patchwork Improve jump threading using VRP information

login
register
mail settings
Submitter Jeff Law
Date Aug. 21, 2013, 12:37 p.m.
Message ID <5214B498.5060709@redhat.com>
Download mbox | patch
Permalink /patch/268803/
State New
Headers show

Comments

Jeff Law - Aug. 21, 2013, 12:37 p.m.
Just something else I saw while analyzing dumps from an unrelated set of 
changes.

It's relatively common to see sequences like this:

   # parent_1 = PHI <parent_7(3), parent_6(D)(4), parent_6(D)(5)>
   _11 = single_tree_10(D) != 0;
   _12 = parent_1 == 0B;
   _13 = _11 & _12;
   if (_13 != 0)
     goto <bb 8>;
   else
     goto <bb 7>;

Where VRP can deduce that the value of parent_6 has a nonzero value on 
one (or more) of the paths reaching this block (because those paths 
dereference parent_6).

Obviously when VRP knows parent_6 is nonzero, then we know the current 
block will always transfer control to BB 7.

Or something like this:

  <bb 6>:
   # prephitmp_49 = PHI <1(4), pretmp_48(5)>
   prev_line.31_6 = prev_line;
   _8 = prev_line.31_6 != line_7(D);
   line_differs_9 = (unsigned char) _8;
   _10 = prephitmp_49 | line_differs_9;
   if (_10 != 0)
     goto <bb 8>;
   else
     goto <bb 7>;


We may not know the exact value of _10, but VRP can determine that when 
BB6 is reached from BB4 that BB6 will always transfer control to BB8.


I never coded up the bits to utilize VRP information to simplify 
statements for threading except for COND_EXPRs.  It wasn't clear how 
often it would be useful, thus I took the easy way out.  This picks up a 
hundred or so additional threading opportunities in my testfiles.  Not 
huge, but worth it IMHO.

Bootstrapped and regression tested on x86_64-unknown-linux-gnu. 
Installed onto the trunk.
* tree-vrp.c (simplify_stmt_for_jump_threading): Try to
	simplify assignments too.  If the RHS collapses to a singleton
	range, then return the value for the range.

	* gcc.dg/tree-ssa/ssa-vrp-thread-1.c: New test.

Patch

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-vrp-thread-1.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-vrp-thread-1.c
new file mode 100644
index 0000000..9d9473e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-vrp-thread-1.c
@@ -0,0 +1,31 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-vrp1-details" } */
+
+
+struct basic_block_def;
+typedef struct basic_block_def *basic_block;
+enum gimple_code
+{
+  LAST_AND_UNUSED_GIMPLE_CODE
+};
+struct omp_region
+{
+  struct omp_region *outer;
+  basic_block cont;
+};
+void
+build_omp_regions_1 (basic_block bb, struct omp_region *parent,
+		     unsigned char single_tree, enum gimple_code code)
+{
+  if (code == 25)
+    parent = parent->outer;
+  else if (code == 42)
+    parent->cont = bb;
+  if (single_tree && !parent)
+    return;
+  oof ();
+}
+
+/* { dg-final { scan-tree-dump-times "Threaded" 1 "vrp1" }  } */
+/* { dg-final { cleanup-tree-dump "vrp1" } } */
+
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index ec7ef8f..683a3db 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -9109,15 +9109,27 @@  static vec<tree> equiv_stack;
 static tree
 simplify_stmt_for_jump_threading (gimple stmt, gimple within_stmt)
 {
-  /* We only use VRP information to simplify conditionals.  This is
-     overly conservative, but it's unclear if doing more would be
-     worth the compile time cost.  */
-  if (gimple_code (stmt) != GIMPLE_COND)
-    return NULL;
+  if (gimple_code (stmt) == GIMPLE_COND)
+    return vrp_evaluate_conditional (gimple_cond_code (stmt),
+				     gimple_cond_lhs (stmt),
+				     gimple_cond_rhs (stmt), within_stmt);
+
+  if (gimple_code (stmt) == GIMPLE_ASSIGN)
+    {
+      value_range_t new_vr = VR_INITIALIZER;
+      tree lhs = gimple_assign_lhs (stmt);
+
+      if (TREE_CODE (lhs) == SSA_NAME
+	  && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+	      || POINTER_TYPE_P (TREE_TYPE (lhs))))
+	{
+	  extract_range_from_assignment (&new_vr, stmt);
+	  if (range_int_cst_singleton_p (&new_vr))
+	    return new_vr.min;
+	}
+    }
 
-  return vrp_evaluate_conditional (gimple_cond_code (stmt),
-				   gimple_cond_lhs (stmt),
-				   gimple_cond_rhs (stmt), within_stmt);
+  return NULL_TREE;
 }
 
 /* Blocks which have more than one predecessor and more than