On Fri, Jun 7, 2019 at 4:54 PM Andrew MacLeod <amacl...@redhat.com> wrote: > > On 6/7/19 8:25 AM, Richard Biener wrote: > > On Wed, Jun 5, 2019 at 10:56 PM Andrew MacLeod <amacl...@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. >
