[VRP][PATCH] Improve value range for loop index

[Kugan]

Value range propagation simplifies convergence in vrp_visit_phi_node by
setting minimum to TYPE_MIN when the computed minimum is smaller than
the previous minimum. This can however result in pessimistic value
ranges in some cases.

for example,

        unsigned int i;
        for (i = 0; i < 8; i++)
        {
          ....
        }

        # ivtmp_19 = PHI <ivtmp_17(5), 8(2)>
        ...
        <bb 5>:
        ivtmp_17 = ivtmp_19 - 1;
        if (ivtmp_17 != 0)
        ....
        goto <bb 5>;

min value of ivtmp_19  is simplified to 0 (in tree-vrp.c:8465) where as
it should have been 1. This prevents correct value ranges being
calculated for ivtmp_17 in the example.

We should be able to see the step (the difference from previous minimum
to computed minimum) and if there is scope for more iterations (computed
minimum is greater than step), and then we should be able set minimum to
do one more iteration and converge to the right minimum value.

Attached patch fixes this. Is this OK for stage-1?

Bootstrapped and regression tested on X86_64-unknown-linux-gnu with no
new regressions.

Thanks,
Kugan

gcc/

+2014-04-09  Kugan Vivekanandarajah  <kug...@linaro.org>
+
+       * tree-vrp.c (vrp_visit_phi_node) : Improve value ranges of loop
+       index when simplifying convergence towards minimum.
+

gcc/testsuite

+2014-04-09  Kugan Vivekanandarajah  <kug...@linaro.org>
+
+       * gcc.dg/tree-ssa/vrp91.c: New test
+

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp91.c 
b/gcc/testsuite/gcc.dg/tree-ssa/vrp91.c
index e69de29..26e857c 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp91.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp91.c
@@ -0,0 +1,23 @@
+/* { dg-do compile } */
+/* { dg-options "-S -O2 -fdump-tree-vrp2" } */
+
+unsigned short data;
+void foo ()
+{
+  unsigned char  x16;
+  unsigned int i;
+  for (i = 0; i < 8; i++)
+    {
+      x16 = data & 1;
+      data >>= 1;
+      if (x16 == 1)
+       {
+         data ^= 0x4;
+       }
+      data >>= 1;
+    }
+}
+
+/* { dg-final { scan-tree-dump "\\\[0, 7\\\]" "vrp2" } } */
+/* { dg-final { cleanup-tree-dump "vrp2" } } */
+
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 14f1526..c63f794 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -8461,7 +8461,30 @@ vrp_visit_phi_node (gimple phi)
        {
          if (!needs_overflow_infinity (TREE_TYPE (vr_result.min))
              || !vrp_var_may_overflow (lhs, phi))
-           vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min));
+           {
+             tree step = ((cmp_min > 0) && TYPE_UNSIGNED (TREE_TYPE (lhs))) ?
+               int_const_binop (MINUS_EXPR, lhs_vr->min, vr_result.min) : 
NULL_TREE;
+
+             /* If the type minimum is zero, while avoiding repeated
+                iterations, let us stop at step and let the iterations take
+                it to zero (if necessary) from there.  This will improve
+                value ranges for cases like below, when the value range
+                for ivtemp_17 is [0, 7] and range for ivtmp_19 is [1, 8].
+
+               # ivtmp_19 = PHI <ivtmp_17(5), 8(2)>
+               ...
+               <bb 5>:
+               ivtmp_17 = ivtmp_19 - 1;
+               if (ivtmp_17 != 0)
+               ....
+               goto <bb 5>;
+             */
+             if ((cmp_min > 0) && (TYPE_UNSIGNED (TREE_TYPE (lhs)))
+                 && (tree_int_cst_compare (vr_result.min, step) != -1))
+               vr_result.min = step;
+             else
+               vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min));
+           }
          else if (supports_overflow_infinity (TREE_TYPE (vr_result.min)))
            vr_result.min =
                negative_overflow_infinity (TREE_TYPE (vr_result.min));