value range propagation for _bitwise_ OR

[Andrei Alexandrescu]

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