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

[Andrew MacLeod]

On 5/24/19 5:36 AM, Richard Biener wrote:
> On Fri, May 24, 2019 at 12:27 AM Eric Botcazou <ebotcazou@adacore.com> wrote:
>>> 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.
>> There are a couple of testcases in the testsuite that, I believe, require a
>> minimal form of support for symbolic ranges: gcc.dg/tree-ssa/vrp94.c and
>> gnat.dg/opt40.adb.  They deal with the following pattern in C:


yes, I have looked at this exact testcase when working out the 
relational issues :-)

> And modified a bit in the quoting
>
>>    if (x > y)
>>      return 1;
>>
>>    z = y - x;
>       z = z - 1;
>>    if (z < 0)
>>      abort ();
> otherwise it would be just forming a relation and then using
> the relational information when deriving a range for z = y - x.
>
> It's of course still possible to derive z = [1, +INF] from the
> relation and the op...


When used together,  we can refine ranges based on known relations.

So given we know that y > x, and
 Â Â Â Â Â  z = y - x
the range calculation for MINUS_EXPR would be able to apply this 
relation (op1 > op2) and recognize that the result must be >0 
(represented by the range [1, MAX]).  It would then apply this range 
mask to the calculated result.

so assuming we know nothing about x or y,  we'd get
 Â Â  z = [MIN, MAX] - [MIN, MAX]Â Â  = [MIN, MAX] , apply relational by 
intersecting [1, MAX]  ,  and come up with a range for z of [1, MAX]

z = z - 1Â  would then trivially result in [0, MAX-1]

and still allow removal of the conditional.


What I propose for the relational processing is to utilize the range-ops 
machinery  to evaluate and expose relations in a generic way.

the relations would be  ==, !=,  <, <=, >, >= , and none.  You can query 
the relation between any 2 operands, and range operations can apply 
relational knowledge to refine their ranges. This would then cover both 
equivalencies and the other relations in the same framework.




>
> so eventually the representation of symbolic ranges as ranges
> isn't really necessary (or we need even more obscure testcases
> showing that).  But tracking relations alongside VRP and using
> them for deriving ranges is quite important.

Right. So are we agreed that if we can track relations independently, 
and coordinate that with range calculations,  we no longer need 
symbolics in ranges?

Give me a bit of time to flesh out the relations proposal in a bit more 
depth.

Andrew