On-Demand range technology [6/5] - Integration

On-Demand range technology [6/5] - Integration

[Andrew MacLeod]

After the various discussions, I've evaluated how I think everything can 
fit together, so this is my proposal for integration with trunk.


The complete Ranger prototype consists of 5 major  components, one of 
which is missing/un-implemented as yet :-)

1 - irange -      This is the non-symbolic range implementation we've 
been using which represents ranges as groups of ordered sub-ranges.
2 - range-ops -  This is the component which extracts ranges from 
statements, and so performs the functionality of extract_range_from_*,  
except it operates on the irange API and also allows for solving of 
operands other than just the LHS of the expression.
3 - GORI-computes -  This is the component which utilizes range-ops to 
compute a range on an outgoing edge for any ssa-name in the definition 
chain of the branch
       a_3 = b_6 * 2
       d_8 = a_3 - 20
      if (d_8 < 30)
    the GORI-compute component can generate ranges for d_8, a_3 and b_6.
4 - GORI-Cache and the Ranger.  Working together, this provides the 
on-demand range functionality to resolve ranges
5 - relational/equivalency tracker - This is the sketched out but 
unimplemented bit which tracks the symbolic relationships, and remove 
the need for ranges to support symbolics. ( <,<=, >, >=, ==, != and none).

The consensus appears to be that range-ops and gori-computes are good 
candidates to replace aspects of vr-values and assert generation.

A)
Until I get to (5) (relational tracker), using (1) (irange) is a 
non-starter since it doesn't handle symbolics.

To eliminate the range issue from the equation,  Aldy is currently 
working on unifying the irange and value_range APIs.   This will allow 
the rest of the ranger code base to use the value_range implementation 
transparently.   We can talk about irange or some alternate 
implementation of ranges at some later point, but there'll be an API 
that works for all clients.

The existing value_range API gets a few tweaks/cleanups, but mostly 
there is an additional set of calls to query sub-ranges which the ranger 
and range-ops require. These routines basically translate the various 
value ranges formats into discrete sub-ranges.  Thru these rotuines, 
ANTI_RANGE will appear as 2 sub-ranges, VARYING as a [MIN, MAX] range, 
and UNDEFINED as an empty range [].  These additions should allow 
value_range to function as the range implementation for both the ranger 
and VRP.

I suspect he will have patches coming shortly that will help to unify 
the 2 range implementations, we can discuss details over those patches..

B)
A Unified range API then allows us to work on integrating the range-ops 
and GORI-computes component into the code base.   Range ops would 
replace the various extract_range_from_*_ routines in vr_values for 
statement level ranges.  GORI-computes would then replace the assert 
building code for calculating outgoing ranges on edges.  In theory EVRP 
then simply calls range_on_edge() from gori_compute instead of 
register_edge_assert() .

The range ops code is designed to perform all evaluations assuming an 
arbitrary number of sub-ranges.  Aldy spent a lot of time last year 
unifying the VRP code and the range-ops code to get the identical 
results, and they frequently share a common base. He  has gone thru 
excruciating care to ensure the calculations are identical and verifies 
it by calculating everything using both code bases, comparing them, and 
aborting if the results ever get diverge.

We will need to adjust the range-ops code to work with symbolics in 
certain place. This means PLUS, MINUS, all the relations (<,>, etc), and 
copy. Probably something else as it is encountered. This is un-sized as 
yet, but I'm hoping won't be too bad assuming we can utilize some of the 
existing code for those bits..  More details when we actually start 
doing this and find the lurking dragons.

we'll worry about bitmasks and equivalencies when we get closer to 
functioning, but I don't foresee too much problem since value_range_base 
is still being used.


C)  That will keep us busy for a while, and should result in the core 
integration.   Meanwhile, we'll try to figure out the relational code 
design. I'll go back to my original design, adjust that, then we can 
figure out how best to proceed to address the various needs.

D) Finally, the GORI-cache and on-demand ranger are blocked until the 
above work is finished.


One additional thing I would like to do eventually is tweak EVRP 
slightly to align with the ranger model.

The ranger API is basically just 5 entry points which the ranger uses to 
determine ranges.
     range_of_expr  - range of a use on a statement
     range_of_stmt  - range of the result of the statement, (calculated 
by range-ops).
     range_on_edge - range on an edge - (provided by gori_computes)
     range_on_entry - range on entry to a block (provided by gori-cache)
     range_on_exit - range after the last statement in a block

Abstracted and simplified, I believe EVRP functions more or less like 
this? :

- EVRP  starts a block with it's "current range" vector initialized to 
the range on entry values. (provided as you step into the block),
- It then walks the IL for the block, evaluating each statement, 
possibly simplifying,  and updating this current range vector.
- when it reaches the bottom of the block, it calculates outgoing ranges 
on each edge and updates those  to provide a current range at the start 
each successor block.


If one considers EVRP without making any IL changes, it can be viewed as 
another range calculator.  If that is mapped that to the ranger API:

     range_of_expr  - This is always the current value in the 
current-range vector as you walk the IL.
     range_of_stmt  - range of the result of the statement (to be 
provided by range_ops).   so this is identical
     range_on_edge - this is also identical,  to be provided by 
gori_computes.
     range_on_entry - Provided at the start of block processing, never 
needed again since it is updated on the fly.
     range_on_exit - range after the last statement in a block. when 
EVRP reaches the end of the block, current value is this as well.

EVRP and the ranger have now become alternate implementations of the 
same model, the ranger is on-demand and EVRP just requires processing 
everything linearly through a basic block.

We can tweak the interface's to align a bit better, and then adjust the 
simplification code so it works with that API. That should make EVRP and 
the on-demand Ranger interchangeable during a forward walk.

This would allow a much more accurate comparison of how the 2 
implementations behave and what kinds of results they can get.

It also opens up the unexplored possibility of some sort of hybrid 
version which can resolve some of the drawbacks to each approach.

===================

    Short summary:

a) we'll unify value_range and the irange API, confirm there are no new 
bugs nor performance issue.  This would considered complete when the 
ranger is able to fully run using value_range instead of irange.

b) we'll then port the required parts of range-ops and gori-computes to 
handle basic symbolics in value_range so that the VRPs' will see the 
same results with range-ops as it does with the extract and assert 
code.  Then we will integrate it with vr_values and EVRP. This would be 
considered complete when results are identical and there is no 
unacceptable performance impact.

c) meanwhile we'll work on the relational tracking mechanism.

d) Then we can revisit the on-demand engine vs the EVRP walk mechanism 
and any other things dreamed up between now and then.


Does this seem reasonable?

Andrew

Re: On-Demand range technology [6/5] - Integration

[Richard Biener]

On Wed, Jun 5, 2019 at 10:56 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>
> After the various discussions, I've evaluated how I think everything can
> fit together, so this is my proposal for integration with trunk.
>
>
> The complete Ranger prototype consists of 5 major  components, one of
> which is missing/un-implemented as yet :-)
>
> 1 - irange -      This is the non-symbolic range implementation we've
> been using which represents ranges as groups of ordered sub-ranges.
> 2 - range-ops -  This is the component which extracts ranges from
> statements, and so performs the functionality of extract_range_from_*,
> except it operates on the irange API and also allows for solving of
> operands other than just the LHS of the expression.
> 3 - GORI-computes -  This is the component which utilizes range-ops to
> compute a range on an outgoing edge for any ssa-name in the definition
> chain of the branch
>        a_3 = b_6 * 2
>        d_8 = a_3 - 20
>       if (d_8 < 30)
>     the GORI-compute component can generate ranges for d_8, a_3 and b_6.
> 4 - GORI-Cache and the Ranger.  Working together, this provides the
> on-demand range functionality to resolve ranges
> 5 - relational/equivalency tracker - This is the sketched out but
> unimplemented bit which tracks the symbolic relationships, and remove
> the need for ranges to support symbolics. ( <,<=, >, >=, ==, != and none).
>
> The consensus appears to be that range-ops and gori-computes are good
> candidates to replace aspects of vr-values and assert generation.
>
> A)
> Until I get to (5) (relational tracker), using (1) (irange) is a
> non-starter since it doesn't handle symbolics.
>
> To eliminate the range issue from the equation,  Aldy is currently
> working on unifying the irange and value_range APIs.   This will allow
> the rest of the ranger code base to use the value_range implementation
> transparently.   We can talk about irange or some alternate
> implementation of ranges at some later point, but there'll be an API
> that works for all clients.
>
> The existing value_range API gets a few tweaks/cleanups, but mostly
> there is an additional set of calls to query sub-ranges which the ranger
> and range-ops require. These routines basically translate the various
> value ranges formats into discrete sub-ranges.  Thru these rotuines,
> ANTI_RANGE will appear as 2 sub-ranges, VARYING as a [MIN, MAX] range,
> and UNDEFINED as an empty range [].  These additions should allow
> value_range to function as the range implementation for both the ranger
> and VRP.
>
> I suspect he will have patches coming shortly that will help to unify
> the 2 range implementations, we can discuss details over those patches..
>
> B)
> A Unified range API then allows us to work on integrating the range-ops
> and GORI-computes component into the code base.   Range ops would
> replace the various extract_range_from_*_ routines in vr_values for
> statement level ranges.  GORI-computes would then replace the assert
> building code for calculating outgoing ranges on edges.  In theory EVRP
> then simply calls range_on_edge() from gori_compute instead of
> register_edge_assert() .
>
> The range ops code is designed to perform all evaluations assuming an
> arbitrary number of sub-ranges.  Aldy spent a lot of time last year
> unifying the VRP code and the range-ops code to get the identical
> results, and they frequently share a common base. He  has gone thru
> excruciating care to ensure the calculations are identical and verifies
> it by calculating everything using both code bases, comparing them, and
> aborting if the results ever get diverge.
>
> We will need to adjust the range-ops code to work with symbolics in
> certain place. This means PLUS, MINUS, all the relations (<,>, etc), and
> copy. Probably something else as it is encountered. This is un-sized as
> yet, but I'm hoping won't be too bad assuming we can utilize some of the
> existing code for those bits..  More details when we actually start
> doing this and find the lurking dragons.
>
> we'll worry about bitmasks and equivalencies when we get closer to
> functioning, but I don't foresee too much problem since value_range_base
> is still being used.
>
>
> C)  That will keep us busy for a while, and should result in the core
> integration.   Meanwhile, we'll try to figure out the relational code
> design. I'll go back to my original design, adjust that, then we can
> figure out how best to proceed to address the various needs.
>
> D) Finally, the GORI-cache and on-demand ranger are blocked until the
> above work is finished.
>
>
> One additional thing I would like to do eventually is tweak EVRP
> slightly to align with the ranger model.
>
> The ranger API is basically just 5 entry points which the ranger uses to
> determine ranges.
>      range_of_expr  - range of a use on a statement
>      range_of_stmt  - range of the result of the statement, (calculated
> by range-ops).
>      range_on_edge - range on an edge - (provided by gori_computes)
>      range_on_entry - range on entry to a block (provided by gori-cache)
>      range_on_exit - range after the last statement in a block
>
> Abstracted and simplified, I believe EVRP functions more or less like
> this? :
>
> - EVRP  starts a block with it's "current range" vector initialized to
> the range on entry values. (provided as you step into the block),
> - It then walks the IL for the block, evaluating each statement,
> possibly simplifying,  and updating this current range vector.
> - when it reaches the bottom of the block, it calculates outgoing ranges
> on each edge and updates those  to provide a current range at the start
> each successor block.

Actually EVRP computes range on entry when starting a block
from "current range" vector plus the ranges derived from a
controlling expression on a single predecessor edge.
It does not push any ranges for outgoing edges.  This is because
it uses the simple DOM-walk stack to push/pop conditional info.

>
> If one considers EVRP without making any IL changes, it can be viewed as
> another range calculator.  If that is mapped that to the ranger API:
>
>      range_of_expr  - This is always the current value in the
> current-range vector as you walk the IL.
>      range_of_stmt  - range of the result of the statement (to be
> provided by range_ops).   so this is identical
>      range_on_edge - this is also identical,  to be provided by
> gori_computes.
>      range_on_entry - Provided at the start of block processing, never
> needed again since it is updated on the fly.
>      range_on_exit - range after the last statement in a block. when
> EVRP reaches the end of the block, current value is this as well.
>
> EVRP and the ranger have now become alternate implementations of the
> same model, the ranger is on-demand and EVRP just requires processing
> everything linearly through a basic block.
>
> We can tweak the interface's to align a bit better, and then adjust the
> simplification code so it works with that API. That should make EVRP and
> the on-demand Ranger interchangeable during a forward walk.
>
> This would allow a much more accurate comparison of how the 2
> implementations behave and what kinds of results they can get.
>
> It also opens up the unexplored possibility of some sort of hybrid
> version which can resolve some of the drawbacks to each approach.
>
> ===================
>
>     Short summary:
>
> a) we'll unify value_range and the irange API, confirm there are no new
> bugs nor performance issue.  This would considered complete when the
> ranger is able to fully run using value_range instead of irange.
>
> b) we'll then port the required parts of range-ops and gori-computes to
> handle basic symbolics in value_range so that the VRPs' will see the
> same results with range-ops as it does with the extract and assert
> code.  Then we will integrate it with vr_values and EVRP. This would be
> considered complete when results are identical and there is no
> unacceptable performance impact.
>
> c) meanwhile we'll work on the relational tracking mechanism.
>
> d) Then we can revisit the on-demand engine vs the EVRP walk mechanism
> and any other things dreamed up between now and then.
>
>
> Does this seem reasonable?

I think that's a reasonable plan.  You may be aware that we added a
very "simple" (implementation-wise) on-demand query to VRP
called determine_value_range () that computes a range for a
GENERIC expression rather than an SSA name.  On the bottom
it relies on SSA name range info in the IL instead of walking
use-def chains and controlling conditions there (but I even had a
patch to add that ability at some point).

Ranger probably lacks the parsing of GENERIC expressions
at the moment?

Richard.

> Andrew
>

Re: On-Demand range technology [6/5] - Integration

[Aldy Hernandez]

>>      Short summary:
>>
>> a) we'll unify value_range and the irange API, confirm there are no new
>> bugs nor performance issue.  This would considered complete when the
>> ranger is able to fully run using value_range instead of irange.

[snip]

>> Does this seem reasonable?
> 
> I think that's a reasonable plan.  You may be aware that we added a

I guess this means I'm first at bat :).

My first patch is the intersect() implementation for value_range_base 
which I posted yesterday.  I'll be sending more throughout the next week 
or two.

Aldy

Re: On-Demand range technology [6/5] - Integration

[Andrew MacLeod]

On 6/7/19 8:25 AM, Richard Biener wrote:
> On Wed, Jun 5, 2019 at 10:56 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>> After the various discussions, I've evaluated how I think everything can
>> fit together, so this is my proposal for integration with trunk.
>>
>>
>> The complete Ranger prototype consists of 5 major  components, one of
>> which is missing/un-implemented as yet :-)
>>
>> 1 - irange -      This is the non-symbolic range implementation we've
>> been using which represents ranges as groups of ordered sub-ranges.
>> 2 - range-ops -  This is the component which extracts ranges from
>> statements, and so performs the functionality of extract_range_from_*,
>> except it operates on the irange API and also allows for solving of
>> operands other than just the LHS of the expression.
>> 3 - GORI-computes -  This is the component which utilizes range-ops to
>> compute a range on an outgoing edge for any ssa-name in the definition
>> chain of the branch
>>         a_3 = b_6 * 2
>>         d_8 = a_3 - 20
>>        if (d_8 < 30)
>>      the GORI-compute component can generate ranges for d_8, a_3 and b_6.
>> 4 - GORI-Cache and the Ranger.  Working together, this provides the
>> on-demand range functionality to resolve ranges
>> 5 - relational/equivalency tracker - This is the sketched out but
>> unimplemented bit which tracks the symbolic relationships, and remove
>> the need for ranges to support symbolics. ( <,<=, >, >=, ==, != and none).
>>
>> The consensus appears to be that range-ops and gori-computes are good
>> candidates to replace aspects of vr-values and assert generation.
>>
>> A)
>> Until I get to (5) (relational tracker), using (1) (irange) is a
>> non-starter since it doesn't handle symbolics.
>>
>> To eliminate the range issue from the equation,  Aldy is currently
>> working on unifying the irange and value_range APIs.   This will allow
>> the rest of the ranger code base to use the value_range implementation
>> transparently.   We can talk about irange or some alternate
>> implementation of ranges at some later point, but there'll be an API
>> that works for all clients.
>>
>> The existing value_range API gets a few tweaks/cleanups, but mostly
>> there is an additional set of calls to query sub-ranges which the ranger
>> and range-ops require. These routines basically translate the various
>> value ranges formats into discrete sub-ranges.  Thru these rotuines,
>> ANTI_RANGE will appear as 2 sub-ranges, VARYING as a [MIN, MAX] range,
>> and UNDEFINED as an empty range [].  These additions should allow
>> value_range to function as the range implementation for both the ranger
>> and VRP.
>>
>> I suspect he will have patches coming shortly that will help to unify
>> the 2 range implementations, we can discuss details over those patches..
>>
>> B)
>> A Unified range API then allows us to work on integrating the range-ops
>> and GORI-computes component into the code base.   Range ops would
>> replace the various extract_range_from_*_ routines in vr_values for
>> statement level ranges.  GORI-computes would then replace the assert
>> building code for calculating outgoing ranges on edges.  In theory EVRP
>> then simply calls range_on_edge() from gori_compute instead of
>> register_edge_assert() .
>>
>> The range ops code is designed to perform all evaluations assuming an
>> arbitrary number of sub-ranges.  Aldy spent a lot of time last year
>> unifying the VRP code and the range-ops code to get the identical
>> results, and they frequently share a common base. He  has gone thru
>> excruciating care to ensure the calculations are identical and verifies
>> it by calculating everything using both code bases, comparing them, and
>> aborting if the results ever get diverge.
>>
>> We will need to adjust the range-ops code to work with symbolics in
>> certain place. This means PLUS, MINUS, all the relations (<,>, etc), and
>> copy. Probably something else as it is encountered. This is un-sized as
>> yet, but I'm hoping won't be too bad assuming we can utilize some of the
>> existing code for those bits..  More details when we actually start
>> doing this and find the lurking dragons.
>>
>> we'll worry about bitmasks and equivalencies when we get closer to
>> functioning, but I don't foresee too much problem since value_range_base
>> is still being used.
>>
>>
>> C)  That will keep us busy for a while, and should result in the core
>> integration.   Meanwhile, we'll try to figure out the relational code
>> design. I'll go back to my original design, adjust that, then we can
>> figure out how best to proceed to address the various needs.
>>
>> D) Finally, the GORI-cache and on-demand ranger are blocked until the
>> above work is finished.
>>
>>
>> One additional thing I would like to do eventually is tweak EVRP
>> slightly to align with the ranger model.
>>
>> The ranger API is basically just 5 entry points which the ranger uses to
>> determine ranges.
>>       range_of_expr  - range of a use on a statement
>>       range_of_stmt  - range of the result of the statement, (calculated
>> by range-ops).
>>       range_on_edge - range on an edge - (provided by gori_computes)
>>       range_on_entry - range on entry to a block (provided by gori-cache)
>>       range_on_exit - range after the last statement in a block
>>
>> Abstracted and simplified, I believe EVRP functions more or less like
>> this? :
>>
>> - EVRP  starts a block with it's "current range" vector initialized to
>> the range on entry values. (provided as you step into the block),
>> - It then walks the IL for the block, evaluating each statement,
>> possibly simplifying,  and updating this current range vector.
>> - when it reaches the bottom of the block, it calculates outgoing ranges
>> on each edge and updates those  to provide a current range at the start
>> each successor block.
> Actually EVRP computes range on entry when starting a block
> from "current range" vector plus the ranges derived from a
> controlling expression on a single predecessor edge.
> It does not push any ranges for outgoing edges.  This is because
> it uses the simple DOM-walk stack to push/pop conditional info.

ah, ok. so it just pulls the range from an incoming edge rather than 
pushing on outgoing edges.

It should not be too difficult to pull aditional incoming ranges when 
they are available then.
>
>>
>>
>> Does this seem reasonable?
> I think that's a reasonable plan.  You may be aware that we added a
> very "simple" (implementation-wise) on-demand query to VRP
> called determine_value_range () that computes a range for a
> GENERIC expression rather than an SSA name.  On the bottom
> it relies on SSA name range info in the IL instead of walking
> use-def chains and controlling conditions there (but I even had a
> patch to add that ability at some point).
>
> Ranger probably lacks the parsing of GENERIC expressions
> at the moment?
>
no such facility right now...  but I would expect it to be mostly driven 
by calls into the range-ops code.   Who is the consumer of that?
>

Re: On-Demand range technology [6/5] - Integration

[Richard Biener]

On Fri, Jun 7, 2019 at 4:54 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>
> On 6/7/19 8:25 AM, Richard Biener wrote:
> > On Wed, Jun 5, 2019 at 10:56 PM Andrew MacLeod <amacleod@redhat.com> wrote:
> >> After the various discussions, I've evaluated how I think everything can
> >> fit together, so this is my proposal for integration with trunk.
> >>
> >>
> >> The complete Ranger prototype consists of 5 major  components, one of
> >> which is missing/un-implemented as yet :-)
> >>
> >> 1 - irange -      This is the non-symbolic range implementation we've
> >> been using which represents ranges as groups of ordered sub-ranges.
> >> 2 - range-ops -  This is the component which extracts ranges from
> >> statements, and so performs the functionality of extract_range_from_*,
> >> except it operates on the irange API and also allows for solving of
> >> operands other than just the LHS of the expression.
> >> 3 - GORI-computes -  This is the component which utilizes range-ops to
> >> compute a range on an outgoing edge for any ssa-name in the definition
> >> chain of the branch
> >>         a_3 = b_6 * 2
> >>         d_8 = a_3 - 20
> >>        if (d_8 < 30)
> >>      the GORI-compute component can generate ranges for d_8, a_3 and b_6.
> >> 4 - GORI-Cache and the Ranger.  Working together, this provides the
> >> on-demand range functionality to resolve ranges
> >> 5 - relational/equivalency tracker - This is the sketched out but
> >> unimplemented bit which tracks the symbolic relationships, and remove
> >> the need for ranges to support symbolics. ( <,<=, >, >=, ==, != and none).
> >>
> >> The consensus appears to be that range-ops and gori-computes are good
> >> candidates to replace aspects of vr-values and assert generation.
> >>
> >> A)
> >> Until I get to (5) (relational tracker), using (1) (irange) is a
> >> non-starter since it doesn't handle symbolics.
> >>
> >> To eliminate the range issue from the equation,  Aldy is currently
> >> working on unifying the irange and value_range APIs.   This will allow
> >> the rest of the ranger code base to use the value_range implementation
> >> transparently.   We can talk about irange or some alternate
> >> implementation of ranges at some later point, but there'll be an API
> >> that works for all clients.
> >>
> >> The existing value_range API gets a few tweaks/cleanups, but mostly
> >> there is an additional set of calls to query sub-ranges which the ranger
> >> and range-ops require. These routines basically translate the various
> >> value ranges formats into discrete sub-ranges.  Thru these rotuines,
> >> ANTI_RANGE will appear as 2 sub-ranges, VARYING as a [MIN, MAX] range,
> >> and UNDEFINED as an empty range [].  These additions should allow
> >> value_range to function as the range implementation for both the ranger
> >> and VRP.
> >>
> >> I suspect he will have patches coming shortly that will help to unify
> >> the 2 range implementations, we can discuss details over those patches..
> >>
> >> B)
> >> A Unified range API then allows us to work on integrating the range-ops
> >> and GORI-computes component into the code base.   Range ops would
> >> replace the various extract_range_from_*_ routines in vr_values for
> >> statement level ranges.  GORI-computes would then replace the assert
> >> building code for calculating outgoing ranges on edges.  In theory EVRP
> >> then simply calls range_on_edge() from gori_compute instead of
> >> register_edge_assert() .
> >>
> >> The range ops code is designed to perform all evaluations assuming an
> >> arbitrary number of sub-ranges.  Aldy spent a lot of time last year
> >> unifying the VRP code and the range-ops code to get the identical
> >> results, and they frequently share a common base. He  has gone thru
> >> excruciating care to ensure the calculations are identical and verifies
> >> it by calculating everything using both code bases, comparing them, and
> >> aborting if the results ever get diverge.
> >>
> >> We will need to adjust the range-ops code to work with symbolics in
> >> certain place. This means PLUS, MINUS, all the relations (<,>, etc), and
> >> copy. Probably something else as it is encountered. This is un-sized as
> >> yet, but I'm hoping won't be too bad assuming we can utilize some of the
> >> existing code for those bits..  More details when we actually start
> >> doing this and find the lurking dragons.
> >>
> >> we'll worry about bitmasks and equivalencies when we get closer to
> >> functioning, but I don't foresee too much problem since value_range_base
> >> is still being used.
> >>
> >>
> >> C)  That will keep us busy for a while, and should result in the core
> >> integration.   Meanwhile, we'll try to figure out the relational code
> >> design. I'll go back to my original design, adjust that, then we can
> >> figure out how best to proceed to address the various needs.
> >>
> >> D) Finally, the GORI-cache and on-demand ranger are blocked until the
> >> above work is finished.
> >>
> >>
> >> One additional thing I would like to do eventually is tweak EVRP
> >> slightly to align with the ranger model.
> >>
> >> The ranger API is basically just 5 entry points which the ranger uses to
> >> determine ranges.
> >>       range_of_expr  - range of a use on a statement
> >>       range_of_stmt  - range of the result of the statement, (calculated
> >> by range-ops).
> >>       range_on_edge - range on an edge - (provided by gori_computes)
> >>       range_on_entry - range on entry to a block (provided by gori-cache)
> >>       range_on_exit - range after the last statement in a block
> >>
> >> Abstracted and simplified, I believe EVRP functions more or less like
> >> this? :
> >>
> >> - EVRP  starts a block with it's "current range" vector initialized to
> >> the range on entry values. (provided as you step into the block),
> >> - It then walks the IL for the block, evaluating each statement,
> >> possibly simplifying,  and updating this current range vector.
> >> - when it reaches the bottom of the block, it calculates outgoing ranges
> >> on each edge and updates those  to provide a current range at the start
> >> each successor block.
> > Actually EVRP computes range on entry when starting a block
> > from "current range" vector plus the ranges derived from a
> > controlling expression on a single predecessor edge.
> > It does not push any ranges for outgoing edges.  This is because
> > it uses the simple DOM-walk stack to push/pop conditional info.
>
> ah, ok. so it just pulls the range from an incoming edge rather than
> pushing on outgoing edges.
>
> It should not be too difficult to pull aditional incoming ranges when
> they are available then.
> >
> >>
> >>
> >> Does this seem reasonable?
> > I think that's a reasonable plan.  You may be aware that we added a
> > very "simple" (implementation-wise) on-demand query to VRP
> > called determine_value_range () that computes a range for a
> > GENERIC expression rather than an SSA name.  On the bottom
> > it relies on SSA name range info in the IL instead of walking
> > use-def chains and controlling conditions there (but I even had a
> > patch to add that ability at some point).
> >
> > Ranger probably lacks the parsing of GENERIC expressions
> > at the moment?
> >
> no such facility right now...  but I would expect it to be mostly driven
> by calls into the range-ops code.   Who is the consumer of that?

IIRC some warning code at expansion time, niter analysis and
IVOPTs (by being fed analysis results from scalar evolution analysis).

Richard.

>