value range propagation for _bitwise_ OR

["Jérôme M. Berger"]

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
-- 
mailto:jeberger at free.fr
http://jeberger.free.fr
Jabber: jeberger at jabber.fr

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: OpenPGP digital signature
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20100412/45fd303f/attachment.pgp>