On-Demand range technology [3/5] - The Prototype

[Andrew MacLeod]

On 5/29/19 9:11 AM, Richard Biener wrote:
> On Tue, May 28, 2019 at 4:41 PM Jeff Law <law@redhat.com> wrote:
>>
>>>> This aspect of symbolics would be handled by a relational/equivalence
>>>> processing engine that would be follow on work.  Using the same basic
>>>> model as ranges, each tree code is taught to understand the relation
>>>> between its operands, and then we can answer equivalency and relational
>>>> accurately as well.  It would be available for any pass to use
>>>> independent of ranges. I will expound upon that a bit in the future
>>>> directions section.
>>> While I agree that symbolic ranges are a complication and that most
>>> cases it currently handles are not "value-range" things I do not agree
>>> with the idea that we can simply remove handling them and deal
>>> with the fallout in some later point in the future.  Eric may also be
>>> able to show you "real" symbolic value-range magic.
>>>
>>> Note that symbolic ranges are already restricted to PLUS_EXPR
>>> and MINUS_EXPR (and NEGATE_EXPR I think).  There are
>>> also "symbolic" (non-integer constant) ranges like [&a, &a].
>>> I've never seen [&a, &MEM[&a + 4]] but we wouldn't reject those
>>> I think.
>>>
>>> You may have noticed that EVRP does not use symbolic ranges.
> Btw, I probably misremembered this part - it is equivalences that
> EVRP doesn't use.  equivalences are the "other half" of relations
> besides symbolic ranges.
>
I do get confused by this assertion...   From the EVRP dumps :

Intersecting
 Â  int [b_6(D), b_6(D)]Â  EQUIVALENCES: { a_5(D) b_6(D) } (2 elements)
and
 Â  VARYING
to
 Â  int [b_6(D), b_6(D)]Â  EQUIVALENCES: { a_5(D) b_6(D) } (2 elements)
Intersecting
 Â  int [a_5(D), a_5(D)]Â  EQUIVALENCES: { a_5(D) b_6(D) } (2 elements)
and
 Â  VARYING

and

pushing new range for c_7(D): int [b_6(D), b_6(D)]Â  EQUIVALENCES: { 
b_6(D) c_7(D) } (2 elements)
Visiting stmt if (a_5(D) == c_7(D))


it certainly does seem to have symbolics in the range..   ( [b_6, b_6]  
) and it does use equivalencies... presumably thats why its in the 
range, to help track them..  regardless, thats is how it gets cases we 
dont right now like
 Â  if (a == b && b == c)
 Â Â Â Â  if (a == c)

It may not have symbolic expressions like [0, b_6 + 1] as end points 
like VRP does, or maybe it doesn't resolve them to anything other than 
varying, but it does appear to have symbolics?  Perhaps it resolves them 
immediately, but it does appear to use some partial bits of the symbolic 
machinery.

We'd like to make this consistent everywhere and track the equivalencies 
outside of the range via a separate mechanism.


>>> As already said I'd like to see VRP go but obstackles are
>>> symbolic ranges and jump-threading (with Jeff promising
>>> to handle the jump-threading part in the past).
>> Right.  FWIW, one of the follow-on items to this work is Aldy's
>> improvements to backwards jump threading which utilizes the ranger
>> framework -- the primary purpose of that work is to eliminate the need
>> for jump threading in VRP.
> But without relations it won't catch most of the cases...
>
> Richard.
its catching what it quite a few new things....  and the 
relations/equivalencies are coming...  I haven't heard of any issues 
regarding equivalencies, but Aldy's  the one that been working with it, 
so he can speak to it better.

Andrew