value range propagation for _bitwise_ OR

[Don]

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.