April 20, 2010 Re: value range propagation for _bitwise_ OR | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | Andrei Alexandrescu wrote:
> On 04/12/2010 12:57 PM, "Jérôme M. Berger" wrote:
>> Andrei Alexandrescu wrote:
>>> On 04/11/2010 09:18 PM, Adam D. Ruppe wrote:
>>>> On Sun, Apr 11, 2010 at 10:00:41PM -0400, Steven Schveighoffer wrote:
>>>>> We are talking about range propagation, a function of the compiler,
>>>>> not a function of the compiled program. Therefore, slower but more
>>>>> exact functions should be preferred, since they only affect the
>>>>> compile time.
>>>>
>>>> I agree with this. While my solution has a certain beauty to it and is
>>>> fast, your solution accurately covers all the bases, whereas mine
>>>> fails with
>>>> min> 1. I say we go with your's.
>>>
>>> Agreed. Steve's solution is the best we have for unsigned numbers.
>>>
>>> Andrei
>>>
>> Nope, not anymore...
>>
>> Jerome
>
> Looks great, thanks Jerome!
>
> Now, how about that case in which some or all of the ranges involved include negative values? A simple approach is to define them in terms of ranges for unsigned numbers. Here are the cases I identified:
>
> a) If both ranges cross zero, then:
>
> minOR == setmsb(min(
> minOR(nomsb(min_a), nomsb(-1), nomsb(min_b), nomsb(max_b)),
> minOR(nomsb(min_a), nomsb(max_a), nomsb(min_b), nomsb(-1))))
> maxOR == maxOR(0, max_a, 0, max_b)
>
> b) If both ranges are negative, then:
>
> minOR == setmsb(minOR(nomsb(max_a), nomsb(min_a), nomsb(max_b), nomsb(min_b)))
> maxOR == setmsb(maxOR(nomsb(max_a), nomsb(min_a), nomsb(max_b), nomsb(min_b)))
>
> c) If a crosses zero and b doesn't:
>
> minOR == setmsb(minOR(nomsb(min_a), nomsb(-1), min_b, max_b))
> maxOR == maxOR(0, max_a, min_b, max_b)
>
> The primitive nomsb clears off the sign bit in a number, and setmsb sets it.
>
> Makes sense?
>
>
>
> Andrei
A comment: The way DMD currently does range propagation (storing range as union{long, ulong}) is wrong. Currently when mixed signed+-unsigned operations happen, it gives very pessimistic results.
The sign bit should be stored separately.
sign value
1 1xxxxx Negative, long.min..-1
1 0xxxxx (Never occurs)
0 0xxxxx 0..long.max
0 1xxxxx long.max+1..ulong.max
I'm not sure if that makes this case a little more, or a little less complicated. But this defines the problem a bit better.
|
December 04, 2010 Re: value range propagation for _bitwise_ OR | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jérôme M. Berger | is it just me, or does this fail for minA = 0 minB = 0 maxA = 0x80_00_00_00 maxB = 0x80_00_00_00 I'm pretty sure you need to handle 1 << 32 specially |
December 04, 2010 Re: value range propagation for _bitwise_ OR | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ellery Newcomer | On 12/04/2010 01:21 PM, Ellery Newcomer wrote:
> is it just me, or does this fail for
>
> minA = 0
> minB = 0
> maxA = 0x80_00_00_00
> maxB = 0x80_00_00_00
>
> I'm pretty sure you need to handle 1<< 32 specially
i'm thinking this is better:
uint32_t maxOr (uint32_t minA, uint32_t minB,
uint32_t maxA, uint32_t maxB)
{
assert (minA <= maxA);
assert (minB <= maxB);
if (maxA == 0) return maxB;
if (maxB == 0) return maxA;
uint32_t a = maxA ^ minA;
if (a != 0) {
a |= (1 << highbit (a)) - 1;
a = a & maxA & maxB;
if (a != 0)
a = (1 << highbit (a)) - 1;
}
uint32_t b = maxB ^ minB;
if (b != 0) {
b |= (1 << highbit (b)) - 1;
b = b & maxA & maxB;
if (b != 0)
b = (1 << highbit (b)) - 1;
}
return maxA|maxB|a|b;
}
|
Copyright © 1999-2021 by the D Language Foundation