Project Ranger

[Andrew MacLeod]

On 06/04/2018 11:17 AM, Richard Biener wrote:
>
>> It wont be perfect however as many of those routines are written with the assumption that ranges are either a single range or an anti range. we no longer have that restriction and we will diverge in those cases.
> But having 1 single range or N ranges isn't different when it comes to
> the core working routines.  Because if you have N ranges it's simply
> apply the op N times and union the result.  Yes - the special case is


> now that OP (range) can result in multiple ranges but currently
> all interesting cases you likely implement are simply covered by
> returning either a range or an anti-range.  Because more generally
Yeah, This applies to most of the arithmetic operations in particular. Â  
The range code indeed loops through the sub-ranges applying the 
operation to each one.
And yes most cases do result in a single range, which is why it is ripe 
for sharing.  But we also aren't limited to it.  There are times where 
we can provide different results, such as with AND.  for signed char X:
(X & 0xF0)    vrp produces   [-128, 112]  because it has to be a range 
or an anti range, and has to include 0. Â  with the 3 ranges we use right 
now, we generate  [-128, -16][0, 0][16, 112]
Even with 2 ranges, we could generate [-128,0][16,112]Â  (or 
[-128,-16][0,112]) , both of which are somewhat better.

And we can also do better in cases when ranges are combined, like
      if (x != 20 && x != 30) by producing  [-128, 19][21, 29][31, 127] 
signed char
> you'd not want N ranges but some affine thing so you can handle even
> more cases without blowing up storage.
Why don't we want N ranges?    when we exceed the  number of supported 
ranges in irange, it simply starts merging ranges.  In the AND example 
with 3 sub-ranges supported,  we produce [-128, -16][0, 0][16, 112] .  
If we try to add more sub-ranges than are supported, it simply starts 
merging them.  If we only supported 2 ranges instead of 3, the AND code 
would end up producing [-128,0][16,112]  or [-128,-16][0,112].  both of 
which are correct, just not as precise as if irange supported more. 
Class irange takes care of managing the storage and exact number of 
ranges, so none of the code in range-ops changes to deal with this.. it 
is just works on whatever it is given to produce the best result it can.

>> Extricating the code from the symbolic handling is also not straightforward some times as there are big switches which mix and match various bits of each case.
> Yes.  Which is why I never really got far with dumping the symbolic
> stuff because it's hard to come up with a replacement.  I guess
> in reality you want to model symbolic ranges as constraints on affine
> expressions and then have some constraint solver to
> answer queries -- at least for symbolic ranges the interesting
> transforms involve comparison simplifications (aka jump threading)
> only.
>
Yeah its not trivial. The model I'm pursuing tracks  the symbolic 
relationships separately from the range constraints. It can use the 
range constraints if they are useful, but only if they help.

It focuses on the relationships between symbols generated by statements 
and combines sequentially encountered relationships together to 
determine a new relationship and make decisions.  And yes those are 
primarily are comparison points where we'll try to simplify the condition.

for instance
 Â  i = j + 1
 Â  if (i == j)

we don't need a range for 'i' or 'j' to determine this is never true, 
the relationship established in i = j + 1Â  is either (i != j) or (i < j) 
depending on the type and range of 'i' or 'j'.  Either result applied to 
the following (i == j) relationship makes it clear that the second 
condition can never be true.  We'll do it in the reverse order like the 
rangers current model...see the condition, decide it merits looking at 
for simplification, and look back to see if there are any relationships 
feeding it which can simplify it.

Anyway, thats the general direction I'm working in to resolve that set 
of problems.  And I plan to  integrate it with a copy/cast tracker which 
will allow us to see through copies and "equivalent" equivalencies so we 
don't get tricked :-)


>>
>> Anyway, the "lateness" of he introduction is purely on me.  I like to get things working before talking about them especially when they start with half baked ideas.
> I would have liked to see factoring out from current code first and
> actually enhancing the current value-range represenation by removing
> the
> restriction on single ranges.

we started with something like that in mind, but the presence of 
symbolics embedded in the range made it incredibly awkward to add 
support for non-single ranges to the existing representation.

Factoring out the constant bounds aspects of the code is what Aldy is 
currently working on.  When he's finished the existing functions should 
contain just the symbolic processing part of the code, and they will 
call a common base to handle the constant bounds cases.

>
>   I don't very much believe in the "start from scratch" approach.
> Because history shows we always end up with both, the old and the new
> afterwards.

I will try very, very hard to make sure we don't get stuck with both.
Think of it this way... this is a path to being able to hand off all 
range and vrp-related problems to someone else :-)

Andrew

PS. I tried manually overriding thunderbird settings on this to make 
this plain text. Hope it worked :-P.