value range propagation for _bitwise_ OR

[Ali Çehreli]

Rainer Deyke wrote:
> How about this?
> 
> uint fill_bits(uint min_v, uint max_v) {
>   uint mask = 0;
>   for (int i = 0; i < 32; ++i) {
>     if ((min_v | (1 << i)) <= max_v) mask |= (1 << i);
>   }
>   return mask;
> }
> 
> max_c = min(
>   max_a | fill_bits(min_b, max_b),
>   max_b | fill_bits(min_a, max_a));
> 
> 

That proposal looks at the two pairs of a and b separately. For example, 
works with min_a and max_a, and decides a bit pattern.

What if the allowable bit pattern for the b pair has 0 bits that would 
be filled with an value of a that was missed by fill_bits for a? Imagine 
a value of a, that has little number of 1 bits, but one of those bits 
happen to be the one that fills the hole in b...

This problem has nothing directly to do with values, it has something to 
do with parts of values. The parts of values cannot be decided by 
looking at only a pair.

Here are some values that the algorithm fails with ("mask" is printed 
before returning from fill_bits) :

                  binary     decimal
-----------------------------------
             mask 0000000011     3
             mask 0111111111   511
            min_a 0000100100    36
            max_a 0101100011   355
            min_b 0000000001     1
            max_b 0000000100     4
       calculated 0101100011   355
WRONG! empirical 0101100111   359
        emp_max_a 0101100011   355
        emp_max_b 0000000100     4

The last two lines are telling: An unsuspected value of b happens to be 
the one that produces the maximum value of a|b.

Ali