On Thu, May 23, 2019 at 3:28 AM Andrew MacLeod <amacl...@redhat.com> wrote: > > *This note will talk about the 4 major components of the prototype and > explain how they work together. I will be fairly light on detail just > to give an overview, we can delve into whatever details are needed. > - Range-ops : Range operations at the statement level > - GORI - Generates Outgoing Range Info : Ranges generated by basic blocks > - GORI Cache - combining and caching basic-block range info > - Ranger - API and query control > > 1 * Range-ops > -------------------- > The first major component is the centralized range operation database. > This is where range operations for tree-codes are implemented. The > compiler currently has code which can fold ranges, but the new mechanism > is a general purpose solver which can solve for other operands. If there > are N input/output operands, and we have ranges for N-1, It is often > possible to derive the missing range. ie > lhs = op1 + op2 > The existing code in the compiler can solve for LHS given ranges for OP1 > and OP2. This has been extended so that we can also sometimes solve for > either op1 or op2 e, ie > [20,40] = op1 + [5, 10] > ...can calculate that op1 has the range [15, 30] > > This ability to solve for the other operands provides the ability to > calculate ranges in the reverse order we are accustomed to, and is key > to enabling the on-demand range approach. > a_2 = b_1 - 20 > if (a_2 < 40) > A conditional jump has an implicit boolean LHS depending on which edge > is taken. To evaluate ranges on the TRUE edge of the branch, the LHS is > [1,1]. To calculate the range for a_2 we simply solve the equation: > [1,1] = a_2 < 40 > which provides the answer as [0,39]. Furthermore, substituting this > range for a_2 as the LHS of it’s definition statement: > [0,39] = b_1 - 20 > The same evaluation mechanism can calculate a result for b_1 on the > true edge as [20,59]. This is the key feature which allows the rest of > the algorithm to work in a general way. > > All operations are driven from this component, and the only thing > required to add support for another tree code is to implement one or > more methods for it here, and the rest of the range mechanism will > simply work with it. > > > 2 * GORI > ------------ > The second component is the “Generates Outgoing Range Info” engine. > This is a basic-block oriented component which determines what ssa-names > have ranges created on outgoing edges, and how to calculate those ranges. > > The last statement in the block is examined to see if it is a branch > which generates range info, and then determines which ssa-names in the > block can have ranges calculated. It quickly walks the use-def chain > from the branch to find other definitions within the block that can > impact the branch and could also have their ranges calculated. This > summary is then cached for future use. > > The GORI component also uses this summary info to perform the > calculations necessary to determine the outgoing range for any ssa_name > which can be determined. For example: > c_3 = foo () > a_2 = b_1 - 20 > If (a_2 < 40) > The summary information would indicate that b_1 and a_2 can have their > outgoing ranges calculated for this block, and uses the cached > information to quickly calculate them when required. > The API consists of 2 basic methods, query and calculate: > - bool has_edge_range_p (edge, name); > - range outgoing_edge_range (edge, name); > If a query is made for any other ssa-name, it simply returns false and > says this block does not generate a range for that name. This is a key > rationale for the summary so we only spend time processing names for > blocks that actually have ranges generated.
So the current code (in a few cases) derives ranges for SSA uses when they see for example _3 = _4 / _5; here _5 != 0 for the stmts following this one (OK, this is a bad example because for divisions we don't do this, but we do it for derefs and ~[0,0]). The above suggests that iff this is done at all it is not in GORI because those are not conditional stmts or ranges from feeding those. The machinery doing the use-def walking from stmt context also cannot come along these so I have the suspicion that Ranger cannot handle telling us that for the stmt following above, for example if (_5 != 0) that _5 is not zero? Can you clarify? > > 3 * GORI cache > --------------------- > The third component builds on the basic block GORI component, and adds > the ability to traverse the CFG and combine the various ranges provided > by each basic block into a cache. > > It provides both a global-range cache and a range-on-entry cache > summarizing the range of an ssa_name on entry to the block. > > The range-on-entry cache is self filling, and iteratively evaluates back > edges. There is a single API entry point which asks for the range on > entry, and if the data has not been calculated/cached already, it spawns > the following process to calculate the data. : > * Walk the CFG from the current block to the definition block, > and/or any block which has range-on-entry information already > calculated. These end points are the source blocks. > * Any non-source blocks visited are added to a worklist to be updated. > * Starting with the source blocks, push the known outgoing range > from each block to each successor and update their live-on-entry values > when they are visited. If the incoming range changes, mark this block’s > successors as requiring updating. > * Continue iterating until no more updates are required. > > The ordering is planned by the ranger such that if there are no back > edges, it is typically a straightforward single pass. When back edges > are involved, the amount of iterating is typically very small. The > updating is restricted to a single ssa-name, meaning it doesn’t get into > feedback loops with other names nor PHIs. . . It usually converges very > quickly. > > It is important to note that this works exclusively with static ranges > of only a single ssa-name at a time. Ie, ranges which are implicitly > exposed in the IL, and only name being examined. The values returned by > these queries are not dependent on changes in other ssa-names, which is > how the iteration process never gets out of control. > > The ranger making the calls to fill this cache has a higher level > overview, and requests these ranges in definition order such that any > ssa-names feeding the definition of a name having its cache filled are > resolved first, providing the best possible results the first time. > a_2 = b_1 - 20 > If (a_2 < 40) > If the range for a_2 is requested on the true side, the ranger will > first calculate the range of b_1 on entry to the block. Then use this to > calculate the global range of a_2, and finally for the outgoing range on > the desired edge. > > If at some later point, it is discovered that the incoming range of b_1 > has changed in such a way that it has an impact on the outgoing range of > a_2, the iterative update process can be reapplied by the ranger to > update the relevant cache entries. This is usually only required in > cases where multiple ssa-names are affected by back edges and feed each > other. > > 4 * Ranger > ---------------- > The final component is the Ranger which provides a simple API to clients > where they can make various simple requests: > - Range of an ssa-name at a statement location > - Range of the result of a stmt > - Range of an ssa-name on an edge > - Range of an ssa-name after the last statement in a block > - Range of an ssa name on entry to a block > > The ranger is responsible for processing the IL, walking use/def chains > and coordinating the various calls into the GORI components to > pre-satisfy as many conditions as possible before any cache filling is > performed. It is also responsible for triggering any additional updates > which may be required due to newly discovered ranges. We in fact don’t > do this yet, but is rarely required as it turns out. > > Summary > --------------- > All evaluations are done on-demand. If no queries are made, there is no > cost. The Ranger has no prerequisites other than a valid IL and CFG. It > does not need dominators, nor does it require any other changes within > an optimization pass in order to be used. Does it need fully up-to-date SSA form or does it only rely on appropriate SSA uses on stmts in the use-def chain of the SSA name we query range-info for? Does it use immediate uses or stmt operands at all or just use-def chains? I'm asking because some passes leave parts of the CFG not updated while working on other parts to reduce the number of update_ssa calls (ideally to a single one). > When queries are made, only the minimum effort required is made to > satisfy the request. This is a big win when it comes to passes which > only need occasional range information such as warning passes. Some of > these passes actually instantiate a new ranger each time they make a > request, as a demonstration of the low overhead. > > As for passes such as VRP which require complete range information, the > caching process prevents the same information from being calculated more > than once. This means a similar amount of work is done with this > approach, as with the traditional top-down approach currently being > used, except we also process the back edges and iteratively solve for them. What's the storage requirement for the cache when doing VRP pass like processing? What's the compile-time complexity? I read you are saying "similar amount of work" but I guess that's from empirical data comparing to the existing VRP implementations (SSA VRP and EVRP) rather than theoretical bounds? Not sure where to put it so let me put it here: I'd like to see the SSA based VRP pass to die (in fact I'd like all ssa-propagator based passes to die...). EVRP is the future here and I can see EVRP making use of the reverse part of Range-Ops to replace the ad-hoc pattern matching in register_edge_assert_for (badly named function that now gets you back a list of assertions hold on an edge). So I hope to see VRP yanked (it performing jump threading is the major obstackle) and Range-Ops being used as common infrastructure for ranges (that leaves EVRP). I don't really want something "additional" leaving things for other people to cleanup / merge - honestly you don't have the very best track record in this area (it might be your main area of work is not GCC, still the @redhat tag on your mail is an obligation here). Now I've said the above let me continue with 3/n. Richard. > **Comments and feedback always welcome!Thanks > Andrew > *
