Project Ranger

[Andrew MacLeod]

On 05/30/2018 03:41 AM, Eric Botcazou wrote:
>> The Ranger is far enough along now that we have confidence in both its
>> approach and ability to perform, and would like to solicit feedback on
>> what you think of it,  any questions, possible uses,  as well as
>> potential requirements to integrate with trunk later this stage.
> The PDF document mentions that you first intended to support symbolic ranges
> but eventually dropped them as "too complex, and ultimately not necessary".
>
> I don't entirely disagree with the former part, but I'm curious about the
> latter part: how do you intent to deal in the long term with cases that do
> require symbolic information to optimize things?  The TODO page seems to
> acknowledge the loophole but only mentions a plan to deal with equivalences,
> which is not sufficient in the general case (as acknowledged too on the page).
>
First, we'll collect the cases that demonstrate a unique situation we 
care about.  I have 4 very specific case that show current 
shortcomings.. Not just with the Ranger, but a couple we don't handle 
with VRP today. .. I'll eventually get those put onto the wiki so the 
list can be updated.

I think most of these cases that care about symbolics are not so much 
range related, but rather an algorithmic layer on top. Any follow on 
optimization to either enhance or replace vrp or anything similar will 
simply use the ranger as a client.  If it turns out there are cases 
where we *have* to remember the end point of a range as a symbolic, then 
the algorithm to track that symbolic along with the range, and request a 
re-evaluation of the range when the value of that symbolic is changes.

Thats the high-level view.  I'm not convinced the symbolic has to be in 
the range in order to solve problems for 2 reasons:

 Â 1)Â  The Ranger maintains some definition chains internally and has a 
clear idea of what ssa_names can affect the outcome of a range. It 
tracks all these dependencies on a per-bb basis in the gori-map 
structure as imports and exports. .  The iterative approach I mentioned 
in the document would use this info to decide that ranges in a block 
need to be re-evaluated because an input to this block has changed.  
This is similar to the way VRP and other passes iterate until nothing 
changes.  If we get a better range for an ssa_name than we had before, 
push it on the stack to look for potential re-evaluation, and keep going.

ThIs is what I referred to as the Level 4 ranger in the document. I kind 
of glossed over it because I didn't want to get into the full-blown 
design I originally had, nor to rework it based on the current 
incarnation of the Ranger.  I wanted to primarily focus on what we 
currently have that is working so we can move forward with it.

I don't think we need to track the symbolic name in the range because 
the Ranger tracks these dependencies for each ssa-name and can indicate 
when we may need to reevaluate them.  There is an exported routine from 
the block ranger :
 Â Â Â Â Â  tree single_import (tree name);
If there is a sole import, it will return the ssa-name that NAME is 
dependent on that can affect the range of  NAME.   We added that API so 
Aldy's new threading code could utilizes this ability to a small degree..

Bottom line: The ranger has information that a pass can use to decide 
that a range could benefit from being reevaluated. This identifies any 
symbolic component of a range from that block.

 Â 2) This entire approach is modeled on walking the IL to evaluate a 
range.  If we put symbolics and expressions in the range, we are really 
duplicating information that is already in the IL, and have to make a 
choice of exactly what and how we do it..
BB3:
 Â Â  j_1 = q_6 / 2
 Â Â  i_2 = j_1 + 3
 Â Â  if ( i_2 < k_4)

we could store the range of k_4 as [i_2 + 1, MAX]Â  (which seems the 
obvious one)
we could also store it as [j_1 + 4, MAX]
or even [q_6 / 2 + 4, MAX].  But we have to decide in advance, and we 
have extra work to do if it turns out to be one of the other names we 
ended up wanting..

At some point later on we decide we either don't know anything about i_2 
(or j_1, or q_6), or we have found a range for it, and now need to take 
that value and evaluate the expression stashed in the range in order to 
get the final result.   Note that whatever algorithm is doing this must 
also keep track of this range somehow in order to use it later.

With the Ranger model, the same algorithm gets a range, and if it thinks 
it might need to be re-evaluated for whatever reason can just track the 
an extra bit of info (like i_2 for instance) along side the range 
(rather than in it).  If we thinks the range needs to be re-evaluated , 
it can simply request a new range from the ranger.

You also don't have to decide whether to track the range with i_2 or j_1 
(or even q_6). The Ranger can tell you that the range it gives you for 
k_4 is accurate unless you get a new value for q_6. That is really what 
you want to track.  You might later want to reevaluate the range only if 
q_6 changes.  If it doesn't, you are done.  .

Bottom line:The ranger indicates what the symbolic aspect of the range 
is with the import. The net effect is the symbolic expression using that 
import is also the longest possible expression in the block 
available...  it just picks it up from the IL rather than storing it in 
the range.

I would also note that we track multiple imports, they just aren't 
really exposed as yet since they aren't really being used by anyone.  
k_4 is also tagged as an import to that block, and if you ask for the 
range of i_2, you'd get a range, and  k_4 would be listed as the import.

Also note more complexity is available.  Once we hit statements with 
multiple ssa_names, we stop tracking currently, but we do note the 
imports at that point:
BB4:
 Â  z_4 = a_3 + c_2
 Â  z_5 = z_4 + 3
 Â  if (Â  q_8 < z_5)
we can get a range for q_8, and the ranger does know that a_3 and c_2 
are both imports to defining z_5.  By using the import information, we 
effectively get a "symbolic" range of
[MIN, a_3 + c_2 + 3] for q_8 in this case.

Which means I think the import approach of the Ranger has the benefit of 
being simpler in many ways,  yet more powerful should we wish to explore 
that route.


The one place this falls down is if you get a range back from a call and 
you have no idea where it came from, but want to be able to re-evaluate 
it later. .  I am not sure what this use case looks like (if it exists 
:-), but I would be surprised if it wasn't something that could be 
handled with an algorithm changed.  I know if discussions with Aldy and 
Jeff as we went through various use cases, this model does sometimes 
require a bit of rethinking of how you approach using the information 
since a lot of things we're use to worrying about just happen under the 
covers.


Does that help?   If it does, I'll add this to the coverage in the wiki 
page.

Andrew