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.
