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