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

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

[Andrew MacLeod]

There is a functioning prototype in branch “ssa-range” which is a proof 
of concept that the approach is functional as well as quick, and can be 
used to answer questions which come up regarding what it can and can’t 
do.  Our last merge was on April 13th, so it's fairly up to date.

We have implemented a flexible range class (irange) which allows for 
multiple subranges to represent a range, and which can be extended in 
the future to types other than integral. We use this throughout, but it 
could be replaced in the ranger with any similar API. Conversion 
routines are also provided to convert from irange to value_range and 
value_range to irange.

A full set of tree_code range-op routines are implemented.  We have 
commoned as much code as possible with the existing VRP range extraction 
code.  Also, we have added additional code for calculating the other 
operands from a known result in numerous cases.

The code base in VRP has been modified (via a flag) to
     - Work completely with the native value_range like it does today.
     - Use irange and the range-ops component under the covers to 
extract ranges. Requests in VRP are then converted from value_ranges to 
irange, called into the range-op routines, and then converted back to 
value_range for VRP/EVRP’s use.
     - Do operations both ways and compare the results to make sure both 
agree on the range, and trap if they do not.

The branch defaults to the compare and trap mode to ensure everything is 
working correctly. This has been our correctness model for statement 
range extraction and was active during the Fedora package builds. The 
only time we disabled it was to do performance runs vs RVRP, and were 
looking at both branch and trunk times for EVRP and VRP.

Of note, we drop all symbolics in ranges to VARYING on everything except 
PLUS and MINUS, which we leave as native calculations if there are 
symbolics present.  More on symbolics later.

A VRP like pass called RVRP has been implemented.
     - The vr-values statement simplification code has been factored out 
to be range agnostic, meaning that these routines can operate on either 
value_range or irange. Thus, we are using a common code base to perform 
statement simplification as well.
     - For complete compatibility with EVRP, the RVRP pass builds 
dominators and instantiates the SCEV loop information so we have loop 
range info available. RVRP does not need this info to run, but would 
miss some of the test cases which depend on loop ranges.
     - RVRP is set up to demonstrate it can process the IL in multiple 
directions and bootstraps/passes all tests in all directions.
         * Dominator order
         * Post-dominator order
         * BB1 thru BBn
         * BBn thru BB1
         * branch-only mode where only branches at the end of each BB 
are examined for folding opportunities

4 additional passes have been converted to use the ranger model:
     - sprintf - removed the dominator building/walking
     - warn alloca - replaced calls to get global ranges with calls that 
now return context sensitive ranges.
     - warn restrict - just replaced EVRP range calls with ranger calls.
     - backwards threader - enhanced to use contextual range information 
to make additional threading decisions.


Symbolic Ranges

One big concern last year expressed was my decision to abolish symbolic 
ranges.

I continue to maintain that there is no need to track the range of x_2 
as [y_3 + 5, MAX] for x_2 = y_3 + 5.   All you need to do is look at the 
definition of x_2, and the same information is exposed right there in 
the IL.  If one requires the symbolic information, the same on-demand 
process could lookup that information as well. This in turn, makes the 
code for ranges much simpler, easier to maintain, and less likely to 
introduce bugs.

We have found through our prototype that symbolics in ranges are not 
nearly as prevalent as one would think.   During the work to share a 
common code base with VRP, we found that symbolic ranges are irrelevant 
for everything except PLUS_EXPR and MINUS_EXPR. The shared code in our 
branch drops symbolics to varying immediately for everything else, and 
it has no impact on EVRP, or VRP or any tests we can find anywhere.  
Furthermore, we never trapped while comparing ranges generated by VRP 
versus generating them with range-ops which drops symbolics to varying.

We tried modifying VRP such that we don’t even create symbolic 
endpoints, but rather revert to VARYING always.  We can find no test 
case that fails because a range is not calculated properly due to 
resolving these endpoints.

There are a few that fail due to the symbolic being used to help track 
relationals.. Ie

      x_2 = y_3 + 5
     If (x_2 > y_3)     // can be folded since we know x_2 must be < y_3

VRP generates a range for x of  [ y_3+5, MAX ] and at various points 
uses that to infer a relational or equivalence.   Ie, it becomes easy to 
tell that the condition must always be true since the lower bound of the 
range is y_3 + 5.

I argue this is not a range question, but rather a different problem 
which VRP has chosen to solve by piggybacking on the range 
representation.  This leads to complications/complexity when trying to 
evaluate ranges because they must constantly be on the lookout for 
symbolics.  This information is then carried around for the life of the 
pass, even if it is never used.  It also forces any 
relational/equivalency queries to be handled within the context of the 
VRP pass.

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.

Comments and feedback always welcome!
Thanks
Andrew

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

[Richard Biener]

On Thu, May 23, 2019 at 3:29 AM Andrew MacLeod <amacleod@redhat.com> wrote:
>
> There is a functioning prototype in branch “ssa-range” which is a proof
> of concept that the approach is functional as well as quick, and can be
> used to answer questions which come up regarding what it can and can’t
> do.  Our last merge was on April 13th, so it's fairly up to date.
>
> We have implemented a flexible range class (irange) which allows for
> multiple subranges to represent a range, and which can be extended in
> the future to types other than integral. We use this throughout, but it
> could be replaced in the ranger with any similar API. Conversion
> routines are also provided to convert from irange to value_range and
> value_range to irange.
>
> A full set of tree_code range-op routines are implemented.  We have
> commoned as much code as possible with the existing VRP range extraction
> code.  Also, we have added additional code for calculating the other
> operands from a known result in numerous cases.
>
> The code base in VRP has been modified (via a flag) to
>      - Work completely with the native value_range like it does today.
>      - Use irange and the range-ops component under the covers to
> extract ranges. Requests in VRP are then converted from value_ranges to
> irange, called into the range-op routines, and then converted back to
> value_range for VRP/EVRP’s use.
>      - Do operations both ways and compare the results to make sure both
> agree on the range, and trap if they do not.
>
> The branch defaults to the compare and trap mode to ensure everything is
> working correctly. This has been our correctness model for statement
> range extraction and was active during the Fedora package builds. The
> only time we disabled it was to do performance runs vs RVRP, and were
> looking at both branch and trunk times for EVRP and VRP.
>
> Of note, we drop all symbolics in ranges to VARYING on everything except
> PLUS and MINUS, which we leave as native calculations if there are
> symbolics present.  More on symbolics later.
>
> A VRP like pass called RVRP has been implemented.
>      - The vr-values statement simplification code has been factored out
> to be range agnostic, meaning that these routines can operate on either
> value_range or irange. Thus, we are using a common code base to perform
> statement simplification as well.
>      - For complete compatibility with EVRP, the RVRP pass builds
> dominators and instantiates the SCEV loop information so we have loop
> range info available. RVRP does not need this info to run, but would
> miss some of the test cases which depend on loop ranges.
>      - RVRP is set up to demonstrate it can process the IL in multiple
> directions and bootstraps/passes all tests in all directions.
>          * Dominator order
>          * Post-dominator order
>          * BB1 thru BBn
>          * BBn thru BB1
>          * branch-only mode where only branches at the end of each BB
> are examined for folding opportunities
>
> 4 additional passes have been converted to use the ranger model:
>      - sprintf - removed the dominator building/walking
>      - warn alloca - replaced calls to get global ranges with calls that
> now return context sensitive ranges.
>      - warn restrict - just replaced EVRP range calls with ranger calls.
>      - backwards threader - enhanced to use contextual range information
> to make additional threading decisions.
>
>
> Symbolic Ranges
>
> One big concern last year expressed was my decision to abolish symbolic
> ranges.
>
> I continue to maintain that there is no need to track the range of x_2
> as [y_3 + 5, MAX] for x_2 = y_3 + 5.   All you need to do is look at the
> definition of x_2, and the same information is exposed right there in
> the IL.  If one requires the symbolic information, the same on-demand
> process could lookup that information as well. This in turn, makes the
> code for ranges much simpler, easier to maintain, and less likely to
> introduce bugs.
>
> We have found through our prototype that symbolics in ranges are not
> nearly as prevalent as one would think.   During the work to share a
> common code base with VRP, we found that symbolic ranges are irrelevant
> for everything except PLUS_EXPR and MINUS_EXPR. The shared code in our
> branch drops symbolics to varying immediately for everything else, and
> it has no impact on EVRP, or VRP or any tests we can find anywhere.
> Furthermore, we never trapped while comparing ranges generated by VRP
> versus generating them with range-ops which drops symbolics to varying.
>
> We tried modifying VRP such that we don’t even create symbolic
> endpoints, but rather revert to VARYING always.  We can find no test
> case that fails because a range is not calculated properly due to
> resolving these endpoints.
>
> There are a few that fail due to the symbolic being used to help track
> relationals.. Ie
>
>       x_2 = y_3 + 5
>      If (x_2 > y_3)     // can be folded since we know x_2 must be < y_3
>
> VRP generates a range for x of  [ y_3+5, MAX ] and at various points
> uses that to infer a relational or equivalence.   Ie, it becomes easy to
> tell that the condition must always be true since the lower bound of the
> range is y_3 + 5.
>
> I argue this is not a range question, but rather a different problem
> which VRP has chosen to solve by piggybacking on the range
> representation.  This leads to complications/complexity when trying to
> evaluate ranges because they must constantly be on the lookout for
> symbolics.  This information is then carried around for the life of the
> pass, even if it is never used.  It also forces any
> relational/equivalency queries to be handled within the context of the
> VRP pass.
>
> 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.

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).

Richard.

> Comments and feedback always welcome!
> Thanks
> Andrew

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

[Eric Botcazou]

> 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:

  if (x >= y)
    return 1;

  z = y - x;
  if (z <= 0)
    abort ();

  return z;

where we want to eliminate the abort.  Of course the C version doesn't really 
make sense on its own, but it's the translation of the Ada version where the

  if (z <= 0)
    abort ();

is generated by the compiler (it's a range check in Ada parlance).

I also agree that symbolic ranges are a complication but I don't understand 
why they would conceptually be treated differently from literal ranges.  Of 
course things may been different practically speaking because I also agree 
that they are of lesser importance than literal ranges in most cases.

> 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].

Yes, the current implementation is restricted to additive operations.

-- 
Eric Botcazou

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

[Toon Moene]

On 5/24/19 12:27 AM, Eric Botcazou wrote:

> 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:
> 
>    if (x >= y)
>      return 1;
> 
>    z = y - x;
>    if (z <= 0)
>      abort ();
> 
>    return z;
> 
> where we want to eliminate the abort.  Of course the C version doesn't really
> make sense on its own, but it's the translation of the Ada version where the
> 
>    if (z <= 0)
>      abort ();
> 
> is generated by the compiler (it's a range check in Ada parlance).

I bet compiling anything Fortran-y with array bound checking on 
(-fbounds-check) would generate ginormous numbers of opportunities for 
symbolic range checking ...

-- 
Toon Moene - e-mail: toon@moene.org - phone: +31 346 214290
Saturnushof 14, 3738 XG  Maartensdijk, The Netherlands
At home: http://moene.org/~toon/; weather: http://moene.org/~hirlam/
Progress of GNU Fortran: http://gcc.gnu.org/wiki/GFortran#news

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

[Richard Biener]

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:

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...

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.

Richard.

>   return z;
>
> where we want to eliminate the abort.  Of course the C version doesn't really
> make sense on its own, but it's the translation of the Ada version where the
>
>   if (z <= 0)
>     abort ();
>
> is generated by the compiler (it's a range check in Ada parlance).
>
> I also agree that symbolic ranges are a complication but I don't understand
> why they would conceptually be treated differently from literal ranges.  Of
> course things may been different practically speaking because I also agree
> that they are of lesser importance than literal ranges in most cases.
>
> > 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].
>
> Yes, the current implementation is restricted to additive operations.
>
> --
> Eric Botcazou

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

[Andrew MacLeod]

On 5/23/19 9:10 AM, Richard Biener wrote:
> On Thu, May 23, 2019 at 3:29 AM Andrew MacLeod <amacleod@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.

sure, I'd love to see a case we can't get that having symbolics in the 
range helps with.  (note I see you guys have replied with an example.  
I'll reply there, but will note it is actually a relation issue, so my 
assertion stands)

And we aren't talking about utting this code in and someday getting 
around to it.   Equivalencies/relations are the very next thing to 
tackle,  and I expected at least a proof of concept as a requirement.  I 
just don't want to proceed with any follow up work until a direction is 
set for the core aspects.

> 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.

Other than for equivalences?  it appears to still track them via ranges 
to eliminate things like :

if (a == b && b == c)
      if (a == c)

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

I noticed this is how it continues to handle relational problems, so 
they are there.

>
> 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).
>
I also consider symbolics an obstacle, only in a different way :-)

Andrew

Re: 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

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

[Jeff Law]

On 5/23/19 7:10 AM, Richard Biener wrote:
> On Thu, May 23, 2019 at 3:29 AM Andrew MacLeod <amacleod@redhat.com> wrote:
>>
>> There is a functioning prototype in branch “ssa-range” which is a proof
>> of concept that the approach is functional as well as quick, and can be
>> used to answer questions which come up regarding what it can and can’t
>> do.  Our last merge was on April 13th, so it's fairly up to date.
>>
>> We have implemented a flexible range class (irange) which allows for
>> multiple subranges to represent a range, and which can be extended in
>> the future to types other than integral. We use this throughout, but it
>> could be replaced in the ranger with any similar API. Conversion
>> routines are also provided to convert from irange to value_range and
>> value_range to irange.
>>
>> A full set of tree_code range-op routines are implemented.  We have
>> commoned as much code as possible with the existing VRP range extraction
>> code.  Also, we have added additional code for calculating the other
>> operands from a known result in numerous cases.
>>
>> The code base in VRP has been modified (via a flag) to
>>      - Work completely with the native value_range like it does today.
>>      - Use irange and the range-ops component under the covers to
>> extract ranges. Requests in VRP are then converted from value_ranges to
>> irange, called into the range-op routines, and then converted back to
>> value_range for VRP/EVRP’s use.
>>      - Do operations both ways and compare the results to make sure both
>> agree on the range, and trap if they do not.
>>
>> The branch defaults to the compare and trap mode to ensure everything is
>> working correctly. This has been our correctness model for statement
>> range extraction and was active during the Fedora package builds. The
>> only time we disabled it was to do performance runs vs RVRP, and were
>> looking at both branch and trunk times for EVRP and VRP.
>>
>> Of note, we drop all symbolics in ranges to VARYING on everything except
>> PLUS and MINUS, which we leave as native calculations if there are
>> symbolics present.  More on symbolics later.
>>
>> A VRP like pass called RVRP has been implemented.
>>      - The vr-values statement simplification code has been factored out
>> to be range agnostic, meaning that these routines can operate on either
>> value_range or irange. Thus, we are using a common code base to perform
>> statement simplification as well.
>>      - For complete compatibility with EVRP, the RVRP pass builds
>> dominators and instantiates the SCEV loop information so we have loop
>> range info available. RVRP does not need this info to run, but would
>> miss some of the test cases which depend on loop ranges.
>>      - RVRP is set up to demonstrate it can process the IL in multiple
>> directions and bootstraps/passes all tests in all directions.
>>          * Dominator order
>>          * Post-dominator order
>>          * BB1 thru BBn
>>          * BBn thru BB1
>>          * branch-only mode where only branches at the end of each BB
>> are examined for folding opportunities
>>
>> 4 additional passes have been converted to use the ranger model:
>>      - sprintf - removed the dominator building/walking
>>      - warn alloca - replaced calls to get global ranges with calls that
>> now return context sensitive ranges.
>>      - warn restrict - just replaced EVRP range calls with ranger calls.
>>      - backwards threader - enhanced to use contextual range information
>> to make additional threading decisions.
>>
>>
>> Symbolic Ranges
>>
>> One big concern last year expressed was my decision to abolish symbolic
>> ranges.
>>
>> I continue to maintain that there is no need to track the range of x_2
>> as [y_3 + 5, MAX] for x_2 = y_3 + 5.   All you need to do is look at the
>> definition of x_2, and the same information is exposed right there in
>> the IL.  If one requires the symbolic information, the same on-demand
>> process could lookup that information as well. This in turn, makes the
>> code for ranges much simpler, easier to maintain, and less likely to
>> introduce bugs.
>>
>> We have found through our prototype that symbolics in ranges are not
>> nearly as prevalent as one would think.   During the work to share a
>> common code base with VRP, we found that symbolic ranges are irrelevant
>> for everything except PLUS_EXPR and MINUS_EXPR. The shared code in our
>> branch drops symbolics to varying immediately for everything else, and
>> it has no impact on EVRP, or VRP or any tests we can find anywhere.
>> Furthermore, we never trapped while comparing ranges generated by VRP
>> versus generating them with range-ops which drops symbolics to varying.
>>
>> We tried modifying VRP such that we don’t even create symbolic
>> endpoints, but rather revert to VARYING always.  We can find no test
>> case that fails because a range is not calculated properly due to
>> resolving these endpoints.
>>
>> There are a few that fail due to the symbolic being used to help track
>> relationals.. Ie
>>
>>       x_2 = y_3 + 5
>>      If (x_2 > y_3)     // can be folded since we know x_2 must be < y_3
>>
>> VRP generates a range for x of  [ y_3+5, MAX ] and at various points
>> uses that to infer a relational or equivalence.   Ie, it becomes easy to
>> tell that the condition must always be true since the lower bound of the
>> range is y_3 + 5.
>>
>> I argue this is not a range question, but rather a different problem
>> which VRP has chosen to solve by piggybacking on the range
>> representation.  This leads to complications/complexity when trying to
>> evaluate ranges because they must constantly be on the lookout for
>> symbolics.  This information is then carried around for the life of the
>> pass, even if it is never used.  It also forces any
>> relational/equivalency queries to be handled within the context of the
>> VRP pass.
>>
>> 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.
> 
> 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.

jeff

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

[Aldy Hernandez]

On 5/28/19 10:40 AM, Jeff Law wrote:
> On 5/23/19 7:10 AM, Richard Biener wrote:
>> On Thu, May 23, 2019 at 3:29 AM Andrew MacLeod <amacleod@redhat.com> wrote:
>>>
>>> There is a functioning prototype in branch “ssa-range” which is a proof
>>> of concept that the approach is functional as well as quick, and can be
>>> used to answer questions which come up regarding what it can and can’t
>>> do.  Our last merge was on April 13th, so it's fairly up to date.
>>>
>>> We have implemented a flexible range class (irange) which allows for
>>> multiple subranges to represent a range, and which can be extended in
>>> the future to types other than integral. We use this throughout, but it
>>> could be replaced in the ranger with any similar API. Conversion
>>> routines are also provided to convert from irange to value_range and
>>> value_range to irange.
>>>
>>> A full set of tree_code range-op routines are implemented.  We have
>>> commoned as much code as possible with the existing VRP range extraction
>>> code.  Also, we have added additional code for calculating the other
>>> operands from a known result in numerous cases.
>>>
>>> The code base in VRP has been modified (via a flag) to
>>>       - Work completely with the native value_range like it does today.
>>>       - Use irange and the range-ops component under the covers to
>>> extract ranges. Requests in VRP are then converted from value_ranges to
>>> irange, called into the range-op routines, and then converted back to
>>> value_range for VRP/EVRP’s use.
>>>       - Do operations both ways and compare the results to make sure both
>>> agree on the range, and trap if they do not.
>>>
>>> The branch defaults to the compare and trap mode to ensure everything is
>>> working correctly. This has been our correctness model for statement
>>> range extraction and was active during the Fedora package builds. The
>>> only time we disabled it was to do performance runs vs RVRP, and were
>>> looking at both branch and trunk times for EVRP and VRP.
>>>
>>> Of note, we drop all symbolics in ranges to VARYING on everything except
>>> PLUS and MINUS, which we leave as native calculations if there are
>>> symbolics present.  More on symbolics later.
>>>
>>> A VRP like pass called RVRP has been implemented.
>>>       - The vr-values statement simplification code has been factored out
>>> to be range agnostic, meaning that these routines can operate on either
>>> value_range or irange. Thus, we are using a common code base to perform
>>> statement simplification as well.
>>>       - For complete compatibility with EVRP, the RVRP pass builds
>>> dominators and instantiates the SCEV loop information so we have loop
>>> range info available. RVRP does not need this info to run, but would
>>> miss some of the test cases which depend on loop ranges.
>>>       - RVRP is set up to demonstrate it can process the IL in multiple
>>> directions and bootstraps/passes all tests in all directions.
>>>           * Dominator order
>>>           * Post-dominator order
>>>           * BB1 thru BBn
>>>           * BBn thru BB1
>>>           * branch-only mode where only branches at the end of each BB
>>> are examined for folding opportunities
>>>
>>> 4 additional passes have been converted to use the ranger model:
>>>       - sprintf - removed the dominator building/walking
>>>       - warn alloca - replaced calls to get global ranges with calls that
>>> now return context sensitive ranges.
>>>       - warn restrict - just replaced EVRP range calls with ranger calls.
>>>       - backwards threader - enhanced to use contextual range information
>>> to make additional threading decisions.
>>>
>>>
>>> Symbolic Ranges
>>>
>>> One big concern last year expressed was my decision to abolish symbolic
>>> ranges.
>>>
>>> I continue to maintain that there is no need to track the range of x_2
>>> as [y_3 + 5, MAX] for x_2 = y_3 + 5.   All you need to do is look at the
>>> definition of x_2, and the same information is exposed right there in
>>> the IL.  If one requires the symbolic information, the same on-demand
>>> process could lookup that information as well. This in turn, makes the
>>> code for ranges much simpler, easier to maintain, and less likely to
>>> introduce bugs.
>>>
>>> We have found through our prototype that symbolics in ranges are not
>>> nearly as prevalent as one would think.   During the work to share a
>>> common code base with VRP, we found that symbolic ranges are irrelevant
>>> for everything except PLUS_EXPR and MINUS_EXPR. The shared code in our
>>> branch drops symbolics to varying immediately for everything else, and
>>> it has no impact on EVRP, or VRP or any tests we can find anywhere.
>>> Furthermore, we never trapped while comparing ranges generated by VRP
>>> versus generating them with range-ops which drops symbolics to varying.
>>>
>>> We tried modifying VRP such that we don’t even create symbolic
>>> endpoints, but rather revert to VARYING always.  We can find no test
>>> case that fails because a range is not calculated properly due to
>>> resolving these endpoints.
>>>
>>> There are a few that fail due to the symbolic being used to help track
>>> relationals.. Ie
>>>
>>>        x_2 = y_3 + 5
>>>       If (x_2 > y_3)     // can be folded since we know x_2 must be < y_3
>>>
>>> VRP generates a range for x of  [ y_3+5, MAX ] and at various points
>>> uses that to infer a relational or equivalence.   Ie, it becomes easy to
>>> tell that the condition must always be true since the lower bound of the
>>> range is y_3 + 5.
>>>
>>> I argue this is not a range question, but rather a different problem
>>> which VRP has chosen to solve by piggybacking on the range
>>> representation.  This leads to complications/complexity when trying to
>>> evaluate ranges because they must constantly be on the lookout for
>>> symbolics.  This information is then carried around for the life of the
>>> pass, even if it is never used.  It also forces any
>>> relational/equivalency queries to be handled within the context of the
>>> VRP pass.
>>>
>>> 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.
>>
>> 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.

Which in theory is already done, working, and in the ranger branch.  It 
may need some more thorough testing to make sure we handle everything we 
catch in VRP (presumably sans the equivalences y'all are hashing out).

As it stands in the branch, I had to disable the backwards threader for 
a bunch of tests, because the threading opportunities were no longer 
there by evrp/vrp time :).

Aldy

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

[Richard Biener]

On Tue, May 28, 2019 at 4:41 PM Jeff Law <law@redhat.com> wrote:
>
> On 5/23/19 7:10 AM, Richard Biener wrote:
> > On Thu, May 23, 2019 at 3:29 AM Andrew MacLeod <amacleod@redhat.com> wrote:
> >>
> >> There is a functioning prototype in branch “ssa-range” which is a proof
> >> of concept that the approach is functional as well as quick, and can be
> >> used to answer questions which come up regarding what it can and can’t
> >> do.  Our last merge was on April 13th, so it's fairly up to date.
> >>
> >> We have implemented a flexible range class (irange) which allows for
> >> multiple subranges to represent a range, and which can be extended in
> >> the future to types other than integral. We use this throughout, but it
> >> could be replaced in the ranger with any similar API. Conversion
> >> routines are also provided to convert from irange to value_range and
> >> value_range to irange.
> >>
> >> A full set of tree_code range-op routines are implemented.  We have
> >> commoned as much code as possible with the existing VRP range extraction
> >> code.  Also, we have added additional code for calculating the other
> >> operands from a known result in numerous cases.
> >>
> >> The code base in VRP has been modified (via a flag) to
> >>      - Work completely with the native value_range like it does today.
> >>      - Use irange and the range-ops component under the covers to
> >> extract ranges. Requests in VRP are then converted from value_ranges to
> >> irange, called into the range-op routines, and then converted back to
> >> value_range for VRP/EVRP’s use.
> >>      - Do operations both ways and compare the results to make sure both
> >> agree on the range, and trap if they do not.
> >>
> >> The branch defaults to the compare and trap mode to ensure everything is
> >> working correctly. This has been our correctness model for statement
> >> range extraction and was active during the Fedora package builds. The
> >> only time we disabled it was to do performance runs vs RVRP, and were
> >> looking at both branch and trunk times for EVRP and VRP.
> >>
> >> Of note, we drop all symbolics in ranges to VARYING on everything except
> >> PLUS and MINUS, which we leave as native calculations if there are
> >> symbolics present.  More on symbolics later.
> >>
> >> A VRP like pass called RVRP has been implemented.
> >>      - The vr-values statement simplification code has been factored out
> >> to be range agnostic, meaning that these routines can operate on either
> >> value_range or irange. Thus, we are using a common code base to perform
> >> statement simplification as well.
> >>      - For complete compatibility with EVRP, the RVRP pass builds
> >> dominators and instantiates the SCEV loop information so we have loop
> >> range info available. RVRP does not need this info to run, but would
> >> miss some of the test cases which depend on loop ranges.
> >>      - RVRP is set up to demonstrate it can process the IL in multiple
> >> directions and bootstraps/passes all tests in all directions.
> >>          * Dominator order
> >>          * Post-dominator order
> >>          * BB1 thru BBn
> >>          * BBn thru BB1
> >>          * branch-only mode where only branches at the end of each BB
> >> are examined for folding opportunities
> >>
> >> 4 additional passes have been converted to use the ranger model:
> >>      - sprintf - removed the dominator building/walking
> >>      - warn alloca - replaced calls to get global ranges with calls that
> >> now return context sensitive ranges.
> >>      - warn restrict - just replaced EVRP range calls with ranger calls.
> >>      - backwards threader - enhanced to use contextual range information
> >> to make additional threading decisions.
> >>
> >>
> >> Symbolic Ranges
> >>
> >> One big concern last year expressed was my decision to abolish symbolic
> >> ranges.
> >>
> >> I continue to maintain that there is no need to track the range of x_2
> >> as [y_3 + 5, MAX] for x_2 = y_3 + 5.   All you need to do is look at the
> >> definition of x_2, and the same information is exposed right there in
> >> the IL.  If one requires the symbolic information, the same on-demand
> >> process could lookup that information as well. This in turn, makes the
> >> code for ranges much simpler, easier to maintain, and less likely to
> >> introduce bugs.
> >>
> >> We have found through our prototype that symbolics in ranges are not
> >> nearly as prevalent as one would think.   During the work to share a
> >> common code base with VRP, we found that symbolic ranges are irrelevant
> >> for everything except PLUS_EXPR and MINUS_EXPR. The shared code in our
> >> branch drops symbolics to varying immediately for everything else, and
> >> it has no impact on EVRP, or VRP or any tests we can find anywhere.
> >> Furthermore, we never trapped while comparing ranges generated by VRP
> >> versus generating them with range-ops which drops symbolics to varying.
> >>
> >> We tried modifying VRP such that we don’t even create symbolic
> >> endpoints, but rather revert to VARYING always.  We can find no test
> >> case that fails because a range is not calculated properly due to
> >> resolving these endpoints.
> >>
> >> There are a few that fail due to the symbolic being used to help track
> >> relationals.. Ie
> >>
> >>       x_2 = y_3 + 5
> >>      If (x_2 > y_3)     // can be folded since we know x_2 must be < y_3
> >>
> >> VRP generates a range for x of  [ y_3+5, MAX ] and at various points
> >> uses that to infer a relational or equivalence.   Ie, it becomes easy to
> >> tell that the condition must always be true since the lower bound of the
> >> range is y_3 + 5.
> >>
> >> I argue this is not a range question, but rather a different problem
> >> which VRP has chosen to solve by piggybacking on the range
> >> representation.  This leads to complications/complexity when trying to
> >> evaluate ranges because they must constantly be on the lookout for
> >> symbolics.  This information is then carried around for the life of the
> >> pass, even if it is never used.  It also forces any
> >> relational/equivalency queries to be handled within the context of the
> >> VRP pass.
> >>
> >> 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.

> > 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.

> jeff

Re: 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