value range propagation for _bitwise_ OR

[Steven Schveighoffer]

On Sun, 11 Apr 2010 22:36:33 -0400, Rainer Deyke <rainerd at eldwood.com>  
wrote:

> On 4/11/2010 13:16, Ali Çehreli wrote:
>> Rainer Deyke wrote:
>>
>>> The intention of fill_bits is to create a number that contains all of
>>> the bits of all of the numbers from min_v to max_v.
>>
>> But no value in the range may have all those bits set. As a result, a|b
>> may have less bits set than fill_bits returns.
>
> Yes, my (revised) function is (still) conservative.  It may result in a
> larger range than strictly necessary, but it should never result in a
> smaller range.

It is possible to get an exact range in O(lgn) time.

>
> If you want 100% percent accuracy then you probably shouldn't be using
> (min, max) pairs to represent your ranges anyway, since this is already
> a simplification.

Range propagation is needed to determine if you can put a value into a  
smaller type.  At that point, all that is needed is the min and max.   
However, you are correct that without more data, the compiler might reject  
legitimate implicit casts that are easily proven.

Would (min, max, mask) be enough to allow this?  Or do we need an exact  
list...

-Steve