[Patch] PR tree-optimization/68234 Improve range info for loop Phi node

[Patch] PR tree-optimization/68234 Improve range info for loop Phi node

[Jiong Wang]

[-- Attachment #1: Type: text/plain, Size: 1360 bytes --]

As discussed at https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68234, this
patch haven't touch the existed code logic in vrp_visit_phi_node, it
only entends SCEV check to those VR_VARYING loop PHI node.

Previously, we only do this check if the PHI node is with valid range
info but later dropped either side to infinite. The miss of those PHI
node with initial estimiation of VR_VARYING caused the missing of some
further optimization opportunity, for example the testcase included in
this patch, with improved range info, we can efficient turn the signed
divide into right shift.

This patch pass x86-64 and AArch64 boostrap, no regression on both.
Meanwhile a simple benchmaring shows there are quite a few new VR_RANGE
found after this patch during gcc bootstrapping. There is no performance
regression on spec2006 int on aarch64.

During gcc bootstrapping, on x86-64 there are 4828 new VR_VARYING -> 
VR_RANGE
found by vrp1, and 5008 new by vrp2.

While on AArch64 there are 44756 new by vrp1, and 6047 new by vrp2.

OK for trunk?

2015-11-11  Richard Biener  <rguenth@gcc.gnu.org>
             Jiong Wang      <jiong.wang@arm.com>
gcc/
   PR tree-optimization/68234
   * tree-vrp.c (vrp_visit_phi_node): Extend SCEV check to those loop PHI
   node which estimiated to be VR_VARYING initially.

gcc/testsuite/
   * gcc.dg/tree-ssa/pr68234.c: New testcase.


[-- Attachment #2: vrp-new.patch --]
[-- Type: text/x-patch, Size: 3044 bytes --]

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr68234.c b/gcc/testsuite/gcc.dg/tree-ssa/pr68234.c
new file mode 100644
index 0000000..e7c2a95
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr68234.c
@@ -0,0 +1,24 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-vrp2" } */
+
+extern int nc;
+void ff (unsigned long long);
+
+void
+f (void)
+{
+  unsigned char resp[1024];
+  int c;
+  int bl = 0;
+  unsigned long long *dwords = (unsigned long long *) (resp + 5);
+  for (c = 0; c < nc; c++)
+    {
+      /* PR middle-end/68234, this signed division should be optimized into
+	 right shift as vrp pass should deduct range info of 'bl' falls into
+	 positive number.  */
+      ff (dwords[bl / 64]);
+      bl++;
+    }
+}
+
+/* { dg-final { scan-tree-dump ">> 6" "vrp2" } } */
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index f7c3168..a6f93f9 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -8789,20 +8789,11 @@ vrp_visit_phi_node (gphi *phi)
 
       /* If we dropped either bound to +-INF then if this is a loop
 	 PHI node SCEV may known more about its value-range.  */
-      if ((cmp_min > 0 || cmp_min < 0
+      if (cmp_min > 0 || cmp_min < 0
 	   || cmp_max < 0 || cmp_max > 0)
-	  && (l = loop_containing_stmt (phi))
-	  && l->header == gimple_bb (phi))
-	adjust_range_with_scev (&vr_result, l, phi, lhs);
-
-      /* If we will end up with a (-INF, +INF) range, set it to
-	 VARYING.  Same if the previous max value was invalid for
-	 the type and we end up with vr_result.min > vr_result.max.  */
-      if ((vrp_val_is_max (vr_result.max)
-	   && vrp_val_is_min (vr_result.min))
-	  || compare_values (vr_result.min,
-			     vr_result.max) > 0)
-	goto varying;
+	goto scev_check;
+
+      goto infinite_check;
     }
 
   /* If the new range is different than the previous value, keep
@@ -8828,8 +8819,28 @@ update_range:
   /* Nothing changed, don't add outgoing edges.  */
   return SSA_PROP_NOT_INTERESTING;
 
-  /* No match found.  Set the LHS to VARYING.  */
 varying:
+  set_value_range_to_varying (&vr_result);
+
+scev_check:
+  /* If this is a loop PHI node SCEV may known more about its value-range.
+     scev_check can be reached from two paths, one is a fall through from above
+     "varying" label, the other is direct goto from code block which tries to
+     avoid infinite simulation.  */
+  if ((l = loop_containing_stmt (phi))
+      && l->header == gimple_bb (phi))
+    adjust_range_with_scev (&vr_result, l, phi, lhs);
+
+infinite_check:
+  /* If we will end up with a (-INF, +INF) range, set it to
+     VARYING.  Same if the previous max value was invalid for
+     the type and we end up with vr_result.min > vr_result.max.  */
+  if ((vr_result.type == VR_RANGE || vr_result.type == VR_ANTI_RANGE)
+      && !((vrp_val_is_max (vr_result.max) && vrp_val_is_min (vr_result.min))
+	   || compare_values (vr_result.min, vr_result.max) > 0))
+    goto update_range;
+
+  /* No match found.  Set the LHS to VARYING.  */
   set_value_range_to_varying (lhs_vr);
   return SSA_PROP_VARYING;
 }

Re: [Patch] PR tree-optimization/68234 Improve range info for loop Phi node

[Richard Biener]

On Wed, 11 Nov 2015, Jiong Wang wrote:

> As discussed at https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68234, this
> patch haven't touch the existed code logic in vrp_visit_phi_node, it
> only entends SCEV check to those VR_VARYING loop PHI node.
> 
> Previously, we only do this check if the PHI node is with valid range
> info but later dropped either side to infinite. The miss of those PHI
> node with initial estimiation of VR_VARYING caused the missing of some
> further optimization opportunity, for example the testcase included in
> this patch, with improved range info, we can efficient turn the signed
> divide into right shift.
> 
> This patch pass x86-64 and AArch64 boostrap, no regression on both.
> Meanwhile a simple benchmaring shows there are quite a few new VR_RANGE
> found after this patch during gcc bootstrapping. There is no performance
> regression on spec2006 int on aarch64.
> 
> During gcc bootstrapping, on x86-64 there are 4828 new VR_VARYING -> VR_RANGE
> found by vrp1, and 5008 new by vrp2.
> 
> While on AArch64 there are 44756 new by vrp1, and 6047 new by vrp2.
> 
> OK for trunk?

Ok.

Thanks,
Richard.

> 2015-11-11  Richard Biener  <rguenth@gcc.gnu.org>
>             Jiong Wang      <jiong.wang@arm.com>
> gcc/
>   PR tree-optimization/68234
>   * tree-vrp.c (vrp_visit_phi_node): Extend SCEV check to those loop PHI
>   node which estimiated to be VR_VARYING initially.
> 
> gcc/testsuite/
>   * gcc.dg/tree-ssa/pr68234.c: New testcase.