On-Demand range technology [5/5] - Looking to the future.

[Andrew MacLeod <amacleod@redhat.com>]

A primary goal of this approach is to try to pull the various aspects of 
VRP apart and make them individually viable so they can be used at 
appropriate places as needed.  The various components of VRP were 
identified as:
     - Ranges
     - Relational queries
     - Equivalencies
     - Bitmask tracking
     - Symbolic range endpoint resolution

This prototype implementation tackles only the range component. It makes 
ranges easily accessible from anywhere in the compiler.

I have plans for addressing these components within the same model, but 
maintaining their independence.  This should make maintenance easier, 
less error prone, and ultimately be far more flexible as other passes 
can utilize whichever aspects they need.


Symbolic range endpoint resolution
--------------------------------------------------

I touched on this in the prototype section, and maintain that the only 
requirement for symbols falls under the equivalence and relational tracking.
     x_2 = y_3 + 5
     If (x_2 > y_3)
Ranges themselves in VRP are eventually resolved to a constant for 
export to the global range table.  At this point, whatever range is 
known for the symbolic is substituted into the value_range, and any 
expression resolved to come up with the final non-symbolic range.
     X_2 = [y_3 + 5, MAX]
If y_3 evaluates to [20, 30], then x_2 is resolved as [25, MAX].

The ranger does this by default on the fly due to its nature. When the 
range of x_2 is requested the first time, it evaluates y_3 , comes up 
with the same [20, 30] range for y_3, and evaluates it to [25,max] 
immediately.

The facility is there to reevaluate the range if the range of y_3 
changes, but to this point it has not been needed. Typically it involves 
y_3 derived in some way from a back edge, and also being derived by yet 
another ssa-name from a different back edge. So, not super common.    
However, I do plan to get to this eventually to enable those 
re-calculations. For the protype, it has not been deemed critical since 
EVRP doesn't even do back edges.

Equivalencies and other Relationals
--------------------------------------------------

The relationship between ssa names are the primary use of symbols in 
ranges today, but the actual property of relations and equivalencies has 
little to do with ranges.

I propose that we utilize the exact same model as the range operation 
database to track relationships. Both equivalencies and relationals can 
be combined as “==” and “!=” is merely another relation.   Each tree 
code has a query to ask for the relationship between any of its 
operands. Ie:
     y_2 = x_3
     j_4 = y_2 + 6
     If (j_4 > x_3)
Knowing the ranges of j_4 and x_3 don’t really help resolve the 
condition.  If x_3 is varying, or even a non-constant, we know nothing 
at all, at least from a range perspective.

Applying the same calculation model the ranger uses from a relational 
point of view, range-ops can be given a relational interface in which 
each tree code can evaluate the relation between its operands.   A copy 
would return “==” for the relation between the LHS and op1, so we’d have 
the relation y_2 == x_3

Operator plus would look at its operands, and be able to indicate J_4 < 
Y_2 because operand 2 is a positive constant.

The branch is the one we care about, and a query would be made for the 
relation between j_4 and x_3.  By combining the relations that feed it, 
we’d get the j_4 < (y_2 == x_3), and the relational result would be j_4 
< x_3.  When applied to (j_4 > x_3) the result is false.

So the relational query would be able to answer the question without 
ever looking at a range, although if a range is available, it may help 
refine the answer.  The lookup process is identical to the way ranges 
are currently handled, which means the same query infrastructure can be 
leveraged and used independently or in concert with ranges.

This would also benefit from not carrying information around unless it 
is requested/required. Currently all equivalences must be stored in case 
we need to know if there is an equivalency. Just like with ranges, this 
model would have no need to even look at an equivalency unless there is 
an actual need to know.

Clearly there is work to do, but this has a lot of potential as a follow 
up to the range work since it uses the same infrastructure. Any pass 
could cheaply ask about the equivalence/relation between any 2 ssa_names.


Bitmask tracking
------------------------
Not to sound like a broken record, but the exact same process can also 
be applied to bitmasks.
     X_2 = y_1 | 0x01
     If (x_2 == 2)    // can never be true

Bitwise operators, as well as other operators like *, /, shifts, etc can 
calculate bitmasks  in exactly the same way ranges are calculated. I 
also considered adding them as an element of the range class, but that 
would complicate the range class, and I maintain that keeping this all 
independant is better from both a maintainability and correctness point 
of view.

If the bitmask becomes part of the range, then we will have to deal with 
the interactions between the two whenever one changes.. Ie if the range 
is [0,45] and we OR  it with 0xF00  what is the resulting range?   We 
don’t care if the only use if to then check a bit,  but it matters a lot 
if we check to see if its < 44.

If the two are kept separate, we will only calculate the range if we 
care (ie we see (x_2 < 44).  If we see a bit check, then we will only 
look back to see what bits might be set.  I would also add that this 
would give us an easy ability to check for bits that are known 0 as well 
as bits that are known 1.

If both are available, then the combination of the 2 could be applied 
together to answer a query if so desired.

Putting it all together.
------------------------------
All these components of current VRP would now be available, but 
maintained, tested, and available anywhere either independently or 
together in whatever combination desired.  They all utilize the same 
basic query engine, so a unifying pass like VRP can track/query all 3 as 
needed.  But ONLY as needed saving overall computation time

Arbitrarily complex situations like
     If (b_4 > 7)                  // b_4 range [8, MAX]
     X_2 = b_4 & 0x0E    // x_2 has range [8, 14], known 0s’ 0xF1
     Y_4 = x_2 + 3           // y_4 has range [11, 17], known 0’s 0xE0,  
known 1’s 0x01, Rel y_4 < x_2
     Z_5 = y_4                // Rel   z_5 == y_4
     If ((z_5 & 0x01) && z_5 < 20)

Could solve the condition as always being TRUE  with little effort 
because each of the simple building blocks combine to work together.

*blink*.  The less than obvious piece here would be teaching the bitmask 
routine for operator PLUS_EXPR that adding a number with trailing 1’s 
(0x03) to a bitmask with trailing 0;s will fill some of those  known 0’s 
with known 1’s.   Missed opportunities are usually as simple as 
enhancing the evaluation routine for an op-code.   This will then be 
applied everywhere it is encountered as its just a basic property of 
PLUS and how it affects bitmasks.

This aspect of all calculations being driven from the opcode and 
combined generically without special casing at  a higher level is both 
very powerful and less prone to produce errors. Our initial experiences  
involved debugging a lot of ranges because they didn’t look right… but 
it would inevitably turn out that a sequence of statements and 
conditions ended up determining an unexpected range, we just couldn’t 
understand from looking at it how it was arrived at.

Comments and feedback always welcome!
Thanks
Andrew