[range-ops] patch 05/04: bonus round!
diff mbox series

Message ID 701c918d-aa9a-11e2-dfcb-9c7507497e85@redhat.com
State New
Headers show
Series
  • [range-ops] patch 05/04: bonus round!
Related show

Commit Message

Aldy Hernandez July 1, 2019, 10:24 a.m. UTC
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

Comments

Jeff Law July 3, 2019, 11:12 p.m. UTC | #1
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
Aldy Hernandez July 6, 2019, 9:26 a.m. UTC | #2
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
Jeff Law July 9, 2019, 10:05 p.m. UTC | #3
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

Patch
diff mbox series

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