| Message ID | 701c918d-aa9a-11e2-dfcb-9c7507497e85@redhat.com |
|---|---|
| State | New |
| Headers | show |
| Series | [range-ops] patch 05/04: bonus round! | expand |
On 7/1/19 4:24 AM, Aldy Hernandez wrote: > This is completely unrelated to range-ops itself, but may yield better > results in value_range intersections. It's just something I found while > working on VRP, and have been dragging around on our branch. > > If we know the intersection of two ranges is the empty set, there is no > need to conservatively add anything to the result. > > Tested on x86-64 Linux with --enable-languages=all. > > Aldy > > range-ops-intersect-undefined.patch > > commit 4f9aa7bd1066267eee92f622ff29d78534158e20 > Author: Aldy Hernandez <aldyh@redhat.com> > Date: Fri Jun 28 11:34:19 2019 +0200 > > Do not try to further refine a VR_UNDEFINED result when intersecting > value_ranges. > > diff --git a/gcc/ChangeLog b/gcc/ChangeLog > index 01fb97cedb2..b0d78ee6871 100644 > --- a/gcc/ChangeLog > +++ b/gcc/ChangeLog > @@ -1,3 +1,9 @@ > +2019-07-01 Aldy Hernandez <aldyh@redhat.com> > + > + * tree-vrp.c (intersect_ranges): If we know the intersection is > + empty, there is no need to conservatively add anything else to > + the set. Do we have a test where this improves the code or at least the computed ranges? jeff
On 7/3/19 7:12 PM, Jeff Law wrote: > On 7/1/19 4:24 AM, Aldy Hernandez wrote: >> This is completely unrelated to range-ops itself, but may yield better >> results in value_range intersections. It's just something I found while >> working on VRP, and have been dragging around on our branch. >> >> If we know the intersection of two ranges is the empty set, there is no >> need to conservatively add anything to the result. >> >> Tested on x86-64 Linux with --enable-languages=all. >> >> Aldy >> >> range-ops-intersect-undefined.patch >> >> commit 4f9aa7bd1066267eee92f622ff29d78534158e20 >> Author: Aldy Hernandez <aldyh@redhat.com> >> Date: Fri Jun 28 11:34:19 2019 +0200 >> >> Do not try to further refine a VR_UNDEFINED result when intersecting >> value_ranges. >> >> diff --git a/gcc/ChangeLog b/gcc/ChangeLog >> index 01fb97cedb2..b0d78ee6871 100644 >> --- a/gcc/ChangeLog >> +++ b/gcc/ChangeLog >> @@ -1,3 +1,9 @@ >> +2019-07-01 Aldy Hernandez <aldyh@redhat.com> >> + >> + * tree-vrp.c (intersect_ranges): If we know the intersection is >> + empty, there is no need to conservatively add anything else to >> + the set. > Do we have a test where this improves the code or at least the computed > ranges? I have long since lost the testcase, but a little hacking around to dump all the cases where we are trying to conservatively refine a VR_UNDEFINED, yields tons of hits. See attached hack. By far, the most common is the intersection of ~[0,0] and [0,0], which yields VR_UNDEFINED. We then conservatively drop to VR1, which is [0,0], basically pessimizing the result. Other examples include: unsigned char [38, +INF], unsigned char [22, 22] unsigned char [4, 4], unsigned char [1, 1] unsigned char [4, 4], unsigned char [2, 2] unsigned int [0, 64], unsigned int [128, 128] unsigned int [0, 6], unsigned int [4294967275, 4294967275] unsigned int ~[35, 35], unsigned int [35, 35] unsigned int [46, 52], unsigned int [25, 25] etc Within 7 minutes of building a compiler (up to stage2), this incorrect refinement of VR_UNDEFINED has been triggered 29000 times. If we know it's VR_UNDEFINED (the empty set), I think we should leave it empty :). Aldy
On 7/6/19 3:26 AM, Aldy Hernandez wrote: > > > On 7/3/19 7:12 PM, Jeff Law wrote: >> On 7/1/19 4:24 AM, Aldy Hernandez wrote: >>> This is completely unrelated to range-ops itself, but may yield better >>> results in value_range intersections. It's just something I found while >>> working on VRP, and have been dragging around on our branch. >>> >>> If we know the intersection of two ranges is the empty set, there is no >>> need to conservatively add anything to the result. >>> >>> Tested on x86-64 Linux with --enable-languages=all. >>> >>> Aldy >>> >>> range-ops-intersect-undefined.patch >>> >>> commit 4f9aa7bd1066267eee92f622ff29d78534158e20 >>> Author: Aldy Hernandez <aldyh@redhat.com> >>> Date: Fri Jun 28 11:34:19 2019 +0200 >>> >>> Do not try to further refine a VR_UNDEFINED result when intersecting >>> >>> value_ranges. >>> >>> diff --git a/gcc/ChangeLog b/gcc/ChangeLog >>> index 01fb97cedb2..b0d78ee6871 100644 >>> --- a/gcc/ChangeLog >>> +++ b/gcc/ChangeLog >>> @@ -1,3 +1,9 @@ >>> +2019-07-01 Aldy Hernandez <aldyh@redhat.com> >>> + >>> + * tree-vrp.c (intersect_ranges): If we know the intersection is >>> + empty, there is no need to conservatively add anything else to >>> + the set. >> Do we have a test where this improves the code or at least the computed >> ranges? > > I have long since lost the testcase, but a little hacking around to dump > all the cases where we are trying to conservatively refine a > VR_UNDEFINED, yields tons of hits. See attached hack. > > By far, the most common is the intersection of ~[0,0] and [0,0], which > yields VR_UNDEFINED. We then conservatively drop to VR1, which is > [0,0], basically pessimizing the result. > > Other examples include: > > unsigned char [38, +INF], unsigned char [22, 22] > unsigned char [4, 4], unsigned char [1, 1] > unsigned char [4, 4], unsigned char [2, 2] > unsigned int [0, 64], unsigned int [128, 128] > unsigned int [0, 6], unsigned int [4294967275, 4294967275] > unsigned int ~[35, 35], unsigned int [35, 35] > unsigned int [46, 52], unsigned int [25, 25] > etc > > Within 7 minutes of building a compiler (up to stage2), this incorrect > refinement of VR_UNDEFINED has been triggered 29000 times. > > If we know it's VR_UNDEFINED (the empty set), I think we should leave it > empty :). So my guess is this happens mostly as a result of the way EVRP works. It refines ranges as it does its domwalk through the CFG via the intersection method. I suspect a lot of the time it's coming from stuff like this: ;; basic block 11, loop depth 1 ;; pred: 9 ;; 10 # h_14 = PHI <0B(9), &f(10)> *h_14 = 0; Where the dereference creates ~[0,0] that we want to intersect with [0,0] coming from the PHI for h_14 (this happens when threading jumps). I think creating VR_UNDEFINED for this is fine. One might argue that when we get into this situation what we've found is an infeasible path, but I'm far from being confident that's always the case. The other case that's likely common is -O1 where we don't run VRP to clean a bunch of this stuff up. Then later the sprintf warning pass comes along and given the crud still in the IL we trigger similar stuff. FWIW, at least in cases like above the path isolation code will kick in and isolate the path 9->11 where block 11' would just trap. The original block 11 would change into *&f = 0 as a result of the path isolation. I'm slightly concerned about the optimistic handling of VR_UNDEFINED in vrp_meet and how that might interact with this patch. But I think we'd be in the realm of invalid/undefined code in those cases. So OK for the trunk. jeff
commit 4f9aa7bd1066267eee92f622ff29d78534158e20
Author: Aldy Hernandez <aldyh@redhat.com>
Date: Fri Jun 28 11:34:19 2019 +0200
Do not try to further refine a VR_UNDEFINED result when intersecting
value_ranges.
diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 01fb97cedb2..b0d78ee6871 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,9 @@
+2019-07-01 Aldy Hernandez <aldyh@redhat.com>
+
+ * tree-vrp.c (intersect_ranges): If we know the intersection is
+ empty, there is no need to conservatively add anything else to
+ the set.
+
2019-06-26 Jeff Law <law@redhat.com>
PR tree-optimization/90883
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index dc7f825efc8..594ee9adc17 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -5977,6 +5977,11 @@ intersect_ranges (enum value_range_kind *vr0type,
gcc_unreachable ();
}
+ /* If we know the intersection is empty, there's no need to
+ conservatively add anything else to the set. */
+ if (*vr0type == VR_UNDEFINED)
+ return;
+
/* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as
result for the intersection. That's always a conservative
correct estimate unless VR1 is a constant singleton range