This is the mail archive of the
`gcc@gcc.gnu.org`
mailing list for the GCC project.

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |

Other format: | [Raw text] |

*From*: Andrew MacLeod <amacleod at redhat dot com>*To*: Richard Biener <richard dot guenther at gmail dot com>*Cc*: GCC <gcc at gcc dot gnu dot org>, Jeff Law <law at redhat dot com>, Aldy Hernandez <aldyh at redhat dot com>*Date*: Fri, 7 Jun 2019 10:54:05 -0400*Subject*: Re: On-Demand range technology [6/5] - Integration*References*: <410b6023-a9eb-36ba-8808-f29ce0ccb39e@redhat.com> <CAFiYyc0BQMB8nsyAn_oOP9a18Fq8JUGAMmwD4NNp2s=B+6X43w@mail.gmail.com>

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.

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?

**Follow-Ups**:**Re: On-Demand range technology [6/5] - Integration***From:*Richard Biener

**References**:**On-Demand range technology [6/5] - Integration***From:*Andrew MacLeod

**Re: On-Demand range technology [6/5] - Integration***From:*Richard Biener

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |