value range propagation for _bitwise_ OR

[Rainer Deyke]

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.

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.  For example:

uint a = x & 0x8000_0000;

Here, the compiler can know a lot about 'a'.  'a' must have one of
exactly two values: 0 and 0x8000_0000.  However, if the compiler
represents this information the form of a (min, max) pair, then all it
knows is that 'a' is somewhere in the range from 0 to 0x8000_0000.  This
is especially an issue when bitwise operations are chained.  Consider:

uint b = a & 0x7fff_ffff;

Now you and I know that 'b' must be exactly 0, given the above
assignment to 'a'.  However, using (min, max) range tracking, all that
the compiler knows is that 'b' is somewhere in the range from 0 to
0x7fff_ffff.


-- 
Rainer Deyke - rainerd at eldwood.com