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

[Richard Biener <richard.guenther@gmail.com>]

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.

>