value range propagation for _bitwise_ OR

Don nospam at nospam.com
Mon Apr 12 12:35:50 PDT 2010


Jérôme M. Berger wrote:
> Steven Schveighoffer wrote:
>> 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.
> 
> 	If that was all we wanted, we wouldn't need to have a precise maxOr
> since the output of the "or" operation is guaranteed to fit in the
> same width as the operands. The reason we need to be precise is for
> future propagation, at which point being able to handle holes in the
> range could be useful (but too expensive in both time and memory to
> be practical in a compiler).
> 
> 		Jerome

Remember that the OR may be part of a larger expression. There may be 
something like:

uint a, b;
ubyte c = (a|b) + 6;




More information about the Digitalmars-d mailing list