[PATCH] Fix PR23744, VRP not merging discontinuous ranges of PHIs
Duncan Sands
baldrick@free.fr
Fri May 5 09:10:00 GMT 2006
This patch teaches vrp_meet to merge non-intersecting ranges by
forming their convex hull. The convex hull is the smallest range
containing the given ranges, so this is exactly what is meant
by "meet" in this context. This is done by removing the check
that the ranges intersect: the remaining code was already forming
the convex hull. One complication is that intersection check
would also fire for (symbolic) ranges that cannot be compared at
compile time; this case is now caught later.
The logic for anti-ranges could also be taught to handle more
cases, but since the current code correctly handles the main
case of anti-one-point ranges I left it alone. I chose instead
to update the comments to make clearer that the code gives up
by choice, and not because useful merging is mathematically
impossible.
Bootstrapped and regtested on i686-pc-linux-gnu for all default
languages plus Ada.
There is one testsuite failure: update-threading.c, which checks
that basic block frequencies are consistent at the end of
optimization ("Invalid sum of incoming frequencies"). The
inconsistency occurs during CFG cleanup after the DOM pass
following VRP: with this patch VRP optimizes the testcase
mightily but correctly, and DOM then removes/merges a bunch of
basic blocks. While the CFG cleanup code updates edge
probabilities, it makes no attempt to update basic block
frequencies (which is not surprising, because it would be hard
and expensive to do). In fact no code anywhere seems to try to
update basic block frequencies, so as far as I can see any
late optimization which changes the CFG would cause this test
to fail. Indeed, without this patch I regularly see "Invalid
sum of incoming frequencies" on other code when the optimizers
change the CFG. In short, the patch causes the test case to
fail apparently because the test case is not expecting to be
optimized that much. I decided that the best thing to do was
to XFAIL it.
Best wishes,
Duncan.
----
2006-05-05 Duncan Sands <baldrick@free.fr>
PR tree-optimization/23744
* tree-vrp.c (vrp_meet): do not require ranges to intersect.
2006-05-05 Duncan Sands <baldrick@free.fr>
PR tree-optimization/23744
* testsuite/gcc.dg/tree-ssa/pr23744.c: new test.
2006-05-05 Duncan Sands <baldrick@free.fr>
PR tree-optimization/23744
* testsuite/gcc.dg/tree-ssa/update-threading.c: xfail.
Index: tree-vrp.c
===================================================================
--- tree-vrp.c (revision 113416)
+++ tree-vrp.c (working copy)
@@ -3795,14 +3795,8 @@ vrp_visit_stmt (tree stmt, edge *taken_e
/* Meet operation for value ranges. Given two value ranges VR0 and
- VR1, store in VR0 the result of meeting VR0 and VR1.
-
- The meeting rules are as follows:
-
- 1- If VR0 and VR1 have an empty intersection, set VR0 to VR_VARYING.
-
- 2- If VR0 and VR1 have a non-empty intersection, set VR0 to the
- union of VR0 and VR1. */
+ VR1, store in VR0 a range that contains both VR0 and VR1. This
+ may not be the smallest possible such range. */
static void
vrp_meet (value_range_t *vr0, value_range_t *vr1)
@@ -3833,56 +3827,44 @@ vrp_meet (value_range_t *vr0, value_rang
if (vr0->type == VR_RANGE && vr1->type == VR_RANGE)
{
- /* If VR0 and VR1 have a non-empty intersection, compute the
- union of both ranges. */
- if (value_ranges_intersect_p (vr0, vr1))
- {
- int cmp;
- tree min, max;
+ int cmp;
+ tree min, max;
- /* The lower limit of the new range is the minimum of the
- two ranges. If they cannot be compared, the result is
- VARYING. */
- cmp = compare_values (vr0->min, vr1->min);
- if (cmp == 0 || cmp == 1)
- min = vr1->min;
- else if (cmp == -1)
- min = vr0->min;
- else
- {
- set_value_range_to_varying (vr0);
- return;
- }
+ /* Compute the convex hull of the ranges. The lower limit of
+ the new range is the minimum of the two ranges. If they
+ cannot be compared, then give up. */
+ cmp = compare_values (vr0->min, vr1->min);
+ if (cmp == 0 || cmp == 1)
+ min = vr1->min;
+ else if (cmp == -1)
+ min = vr0->min;
+ else
+ goto give_up;
- /* Similarly, the upper limit of the new range is the
- maximum of the two ranges. If they cannot be compared,
- the result is VARYING. */
- cmp = compare_values (vr0->max, vr1->max);
- if (cmp == 0 || cmp == -1)
- max = vr1->max;
- else if (cmp == 1)
- max = vr0->max;
- else
- {
- set_value_range_to_varying (vr0);
- return;
- }
+ /* Similarly, the upper limit of the new range is the maximum
+ of the two ranges. If they cannot be compared, then
+ give up. */
+ cmp = compare_values (vr0->max, vr1->max);
+ if (cmp == 0 || cmp == -1)
+ max = vr1->max;
+ else if (cmp == 1)
+ max = vr0->max;
+ else
+ goto give_up;
- /* The resulting set of equivalences is the intersection of
- the two sets. */
- if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
- bitmap_and_into (vr0->equiv, vr1->equiv);
- else if (vr0->equiv && !vr1->equiv)
- bitmap_clear (vr0->equiv);
+ /* The resulting set of equivalences is the intersection of
+ the two sets. */
+ if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
+ bitmap_and_into (vr0->equiv, vr1->equiv);
+ else if (vr0->equiv && !vr1->equiv)
+ bitmap_clear (vr0->equiv);
- set_value_range (vr0, vr0->type, min, max, vr0->equiv);
- }
- else
- goto no_meet;
+ set_value_range (vr0, vr0->type, min, max, vr0->equiv);
}
else if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
{
- /* Two anti-ranges meet only if they are both identical. */
+ /* Two anti-ranges meet only if their complements intersect.
+ Only handle the case of identical ranges. */
if (compare_values (vr0->min, vr1->min) == 0
&& compare_values (vr0->max, vr1->max) == 0
&& compare_values (vr0->min, vr0->max) == 0)
@@ -3895,13 +3877,13 @@ vrp_meet (value_range_t *vr0, value_rang
bitmap_clear (vr0->equiv);
}
else
- goto no_meet;
+ goto give_up;
}
else if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
{
- /* A numeric range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4]
- meet only if the ranges have an empty intersection. The
- result of the meet operation is the anti-range. */
+ /* For a numeric range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4],
+ only handle the case where the ranges have an empty intersection.
+ The result of the meet operation is the anti-range. */
if (!symbolic_range_p (vr0)
&& !symbolic_range_p (vr1)
&& !value_ranges_intersect_p (vr0, vr1))
@@ -3920,17 +3902,17 @@ vrp_meet (value_range_t *vr0, value_rang
bitmap_clear (vr0->equiv);
}
else
- goto no_meet;
+ goto give_up;
}
else
gcc_unreachable ();
return;
-no_meet:
- /* The two range VR0 and VR1 do not meet. Before giving up and
- setting the result to VARYING, see if we can at least derive a
- useful anti-range. FIXME, all this nonsense about distinguishing
+give_up:
+ /* Failed to find an efficient meet. Before giving up and setting
+ the result to VARYING, see if we can at least derive a useful
+ anti-range. FIXME, all this nonsense about distinguishing
anti-ranges from ranges is necessary because of the odd
semantics of range_includes_zero_p and friends. */
if (!symbolic_range_p (vr0)
Index: testsuite/gcc.dg/tree-ssa/pr23744.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/pr23744.c (revision 0)
+++ testsuite/gcc.dg/tree-ssa/pr23744.c (revision 0)
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-vrp1" } */
+
+int g (int i, int j)
+{
+ int t = 0;
+ int i1;
+
+ if (i == j)
+ t = 3;
+ for (i1 = 0; i1 < 10000; i1++) h();
+ if (t != 5)
+ return 0;
+ else
+ return 1;
+}
+
+/* { dg-final { scan-tree-dump-times "Folding predicate.*to 1" 1 "vrp1" } } */
+/* { dg-final { cleanup-tree-dump "vrp1" } } */
Index: testsuite/gcc.dg/tree-ssa/update-threading.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/update-threading.c (revision 113416)
+++ testsuite/gcc.dg/tree-ssa/update-threading.c (working copy)
@@ -20,5 +20,5 @@ main (int argc, char **argv)
foo (((A) { ((!(i >> 4) ? 8 : 64 + (i >> 4)) << 8) + (i << 4) } ).a);
exit (0);
}
-/* { dg-final { scan-tree-dump-times "Invalid sum" 0 "optimized"} } */
+/* { dg-final { scan-tree-dump-times "Invalid sum" 0 "optimized" { xfail *-*-* } } } */
/* { dg-final { cleanup-tree-dump "optimized" } } */
More information about the Gcc-patches
mailing list