Richard Kenner wrote on 06/09/2005 00:27:51:
> I'm watching it deal with
>
> # small_1 = PHI <32(0), 1(1)>
>
> vrp_meet is called with [32, 32] and [1,1].
>
> It determines that the ranges don't intersect and then comes up with
> ~[0,0] since neither contain zero. But wouldn't [1,32] be a better
> result?
That can be tricky. Consider the following:
[-2147483648, -10] and [10, 2147483647]
You would like to get (assuming 32 bit signed integer)
~[-9,9] rather than [-2147483648, 2147483647].
When working with ranges, you may want to work with sorted
lists of ranges rather than with a simple range (this is what we
have been doing for years).
By using sorted lists of ranges, your example becomes:
(1) [1,1] ; [32,32]
And the complement list:
(2) ~ { [MIN,0] ; [2, 31] ; [33, MAX] }
When you convert these to a single range, you can choose the
best approximation:
(3) superset of the normal list (1):
[1,32] (as you proposed).
(4) Biggest subset of the complement list (2):
~[MIN,0]
(or maybe [33,MAX], or [2,31] depending on cost).
A heuristic cost function can be used to choose among alternatives.
The simplest heuristics is to find the representation that enlarges
the represented set as less as possible . Other things to consider
may be the presence of zero and other interesting values, or
range's mean (to be as close as possible to the original list of
ranges).
Michael
