Re: PING^2: Fwd: SSA range class and removal of VR_ANTI_RANGEs

[Richard Biener <richard dot guenther at gmail dot com>]

On Tue, Jul 25, 2017 at 4:50 PM, Andrew MacLeod <amacleod@redhat.com> wrote:
> On 07/25/2017 03:12 AM, Richard Biener wrote:
>>
>> On Fri, Jul 21, 2017 at 9:30 PM, Aldy Hernandez <aldyh@redhat.com> wrote:
>>>
>>> On Mon, Jul 17, 2017 at 6:23 AM, Richard Biener
>>> <richard.guenther@gmail.com> wrote:
>>>>
>>>> On Mon, Jul 17, 2017 at 8:51 AM, Aldy Hernandez <aldyh@redhat.com>
>>>> wrote:
>>>>>
>>>>> How does this look?
>>>>
>>>> It's a change that on its own doesn't look worthwhile to me.
>>>>
>>>> So please post the changes that will build ontop of this.  Like removing
>>>> anti-ranges from VRP or your on-demand value-range stuff.
>>>>
>>>> Thanks,
>>>> Richard.
>>>
>>>  From the looks of it, we can have a variety of VRP ranges that are not
>>> representable at all with the an integer range class.  For instance, I
>>> see the following ranges built in set_value_range():
>>>
>>> [INT, (nop_expr SSA)]
>>>
>>> [INT, (plus_expr SSA INT)]
>>>
>>> [(negate_expr SSA), (negate_expr SSA)]
>>>
>>> [(plus_expr (negate_expr SSA INT)),
>>>   (plus_expr (negate_expr SSA) INT)]
>>>
>>> [SSA, SSA]
>>>
>>> So...I guess the first suggestion is out of the question ;-).
>>
>> Well.  We do not want range operations implemented twice (really!)
>> so range operations need to work on both representations.  So we
>> should think of a way to get rid of anti-ranges in VRP which, frankly,
>> means that for the sake symbolic ranges we have to trade them
>> with handling open/closed ranges which I'm not sure will be less of
>> a hassle to handle?
>
>
> I originally looked at ranges with symbolic expressions, but as soon as
> there are ranges comprised of more than 1 range, symbolics became a
> nightmare.  At best you can do endpoints, and even then you have to start
> adding complexity..  [0, 100] Union  [5, x_4]  now has to become  [0,
> max(100, x_4)] , and chained operations were making the expressions more and
> more complicated.  Trying to maintain these expression across optimizations
> was also very problematic as the IL changes and these expressions are not in
> the IL and don't suffer updates easily.
>
> At which point one asks themselves whether it actually makes sense to
> integrate that into the range representation, or try a different tactic.
>
> Seems to me its cleaner to have an integral range, and when appropriate
> track symbols separately to determine if their values can be refined.    If
> at some point you can resolve those symbols to an integral value,  then you
> simply update the integral range with the new range you've determined.
>
> VRP chooses to do this by creating a completely different structure for
> ranges, and representing endpoints as expression trees. It then updates the
> integral ranges at the end of the pass. It uses anti-ranges as a shorthand
> to handle a special case of a range comprised of 2 ranges.  As it stands
> right now, VRP's version of union and intersection can never have much in
> common with a general integral range implementation. They are 2 very
> different beasts.
>
> So we cant do much about VRP internally yet without some significant
> surgery.
>
> This issue seems orthogonal to me though.  irange is not intended to ever do
> anything with symbols, thus can never replace VRPs internal value_range
> class.    We're simply replacing "struct range_info_def" with a new range
> structure and API which can support more precise ranges than a pair of
> integral endpoints.  We'll then build on that by providing routines which
> can generate more precise range information as well.
>
> For the moment we provide an implementation with the same precision to
>   a) ensure code generation remains the same
>   b) allow the compiler to use it for a while to make sure no bugs have been
> introduced
>   c) and there is nothing that would utilize the additional precision yet
> anyway.
>
> I just think its important to get it in the code base so its being used and
> we can be sure its correct.

But nothing uses all the methods.

And we're ending up with two variants of range + range, etc.

irange is a nearly subset of what VRP can handle so it should be able to re-use
VRP workers.  The 'nearly' part is that VRP currently doesn't handle multiple
ranges.  For an unknown reason you didn't start with teaching VRP that bit.

Yes, symbolic ranges complicate that conversion a bit (getting rid of
anti-ranges
in VRP) but you could have either kept anti-ranges for symbolic ranges only
or have open/closed ranges.  The issue with symbolic ranges here is that
from

  if (a != b)

we derive a symbolic range for a that is ~[b, b].  If you want to make that
a union of two ranges you have [MIN, b - 1] U [b + 1, MAX] _but_ both
b - 1 or b + 1 might actually overflow!  So you need to use [MIN, b[ U ]b, MAX]
here (which means both can be empty if b == MIN or b == MAX).

As said I don't like introducing new stuff without fixing existing
stuff.  Handling
open/closed ranges shouldn't be too difficult if you assert that only a symbolic
end can be open.  Then you can re-use the workers from VRP in irange.

Double-win.

> On its own it is an improvement to "struct range_info_def" as it
> encapsulates the activity in one place and provides a standard API any
> optimization can utilize.  It allows us to improve the precision of ranges
> in the future without changing any client code., and it does not appear to
> have any measurable compile time storage or speed issues.  It is simply an
> infrastructure improvement.

How does it allow us to improve ranges when the very first range propagation
pass that computes the ranges is limited to 1 sub-range?!

Richard.

>
> Andrew
>