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@eldwood.com

On Sun, 11 Apr 2010 22:36:33 -0400, Rainer Deyke <rainerd@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

On Sun, 11 Apr 2010 00:30:07 -0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:

> Couldn't help it, this seems like such a fun problem, I had to solve it :)
>
> uint maxor(uint mina, uint maxa, uint minb, uint maxb)
> {
>      uint bt = 1 << 31;
>      uint result = 0;
>      while(bt)
>      {
>          if((bt & maxa) && (bt & mina))
>          {
>              result |= bt;
>              if((bt & minb) ^ (bt & maxb))
>              {
>                  return result | (bt-1);// always can choose all 1s for rest of b
>              }
>          }
>          else if((bt & maxb) && (bt & minb))
>          {
>              result |= bt;
>              if((bt & mina) ^ (bt & maxa))
>              {
>                  return result | (bt-1);// always can choose all 1s for rest of a
>              }
>          }
>          else if(bt & (maxa | maxb))
>          {
>              result |= bt;
>              if(bt & (maxa & maxb))
>              {
>                  // both maxa and maxb have bt set, and both mina and minb have
>                  // bt unset.  This means we can choose this bit to be set on
>                  // either, and it is possible to have all 1s set for the other
>                  // for the rest of the bits.
>                  return result | (bt - 1);
>              }
>              else if(bt & maxa)
>              {
>                  // now that we are using this bit from maxa, we need to raise
>                  // mina so it becomes the smallest value with bt set.  However,
>                  // we don't really care about bits above bt, so setting
>                  // it to 0 is fine.
>                  mina = 0;
>              }
>              else
>              {
>                  minb = 0;
>              }
>          }
>          // else, neither maxa or maxb have bt set, continue to next bit.
>          bt >>= 1;
>      }
>      return result;
> }

And the complementary minor:


uint minor(uint mina, uint maxa, uint minb, uint maxb)
{
    uint bt = 1 << 31;
    uint result = 0;
    while(bt)
    {
        if((bt & maxa) && (bt & mina))
        {
            result |= bt;
            if((bt & minb) ^ (bt & maxb))
            {
                // bt will already be set for a, so set it also for b, this
                // allows us to have all 0s for the rest of b.  Then we use
                // mina to get the minimum for the rest of a
                return result | ((bt-1) & mina);
            }
        }
        else if((bt & maxb) && (bt & minb))
        {
            result |= bt;
            if((bt & mina) ^ (bt & maxa))
            {
                // ditto for b
                return result | ((bt-1) & minb);
            }
        }
        else
        {
            if(bt & maxa)
            {
                // we never want to choose a 1 here, so we want a zero, which
                // makes the max for the rest of the bits all 1s.
                maxa = ~0;
            }

            if(bt & maxb)
            {
                // ditto for b
                maxb = ~0;
            }
        }
        bt >>=1;
    }
    return result;
}

I tried to combine these into one function, but the cases are subtly different, so you end up just doing each in sequence.  The only thing you save is an extra function call and you can combine both loops into one.

I'll work on signed values tomorrow :)

-Steve

On 4/11/2010 20:51, Steven Schveighoffer wrote:
> 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.

Technically, you don't even need min and max at that point.  A bit mask would be enough.

> 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...

I was think about two masks (min_mask and max_mask) such that
'(min_mask & x) == min_mask' and '(max_mask | x) == max_mask'.  In other
words, 'min_mask' contains the bits that are definitely 1 in 'x' while
'max_mask' contains the bits that /could/ be 1 in 'x'.  This avoids loss
of information in the presence of the bitwise inverse operator (unary '~').


-- 
Rainer Deyke - rainerd@eldwood.com

On Sun, 11 Apr 2010 00:30:07 -0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:

> Signed is probably trickier, suppose one is always negative and one is always positive!

Turns out signed is really easy once you have unsigned solved.

Here is minor and maxor for signed assuming unsigned is solved:

int maxor(int mina, int maxa, int minb, int maxb)
{
    if(mina < 0 && maxa >= 0)
    {
        int result = maxor(0, maxa, minb, maxb);
        return result > -1 ? result : -1;
    }
    if(minb < 0 && maxb >= 0)
    {
        int result = maxor(mina, maxa, 0, maxb);
        return result > -1 ? result : -1;
    }
    return cast(int)maxor(cast(uint)mina, cast(uint)maxa, cast(uint)minb, cast(uint)maxb);
}

int minor(int mina, int maxa, int minb, int maxb)
{
    if(mina < 0 && maxa >= 0)
    {
        int result = minor(mina, -1, minb, maxb);
        return result < minb ? result : minb;
    }
    if(minb < 0 && maxb >= 0)
    {
        int result = minor(mina, maxa, minb, -1);
        return result < mina ? result : mina;
    }
    return cast(int)minor(cast(uint)mina, cast(uint)maxa, cast(uint)minb, cast(uint)maxb);
}

The trick is to avoid dealing with a range that crosses the 0 boundary.  The negative range isn't any different than an unsigned range -- set the most possible bits for max, unset the most possible bits for min.  The sign bit simply becomes a hard-wired bit.

BTW, I release this code into the public domain, use it for any purpose you wish.

-Steve

On 04/11/2010 10:07 PM, Steven Schveighoffer wrote:
[snip]
> I'll work on signed values tomorrow :)

This is great work, Steve!

Andrei

On Mon, 12 Apr 2010 01:11:37 -0400, Rainer Deyke <rainerd@eldwood.com> wrote:

> On 4/11/2010 20:51, Steven Schveighoffer wrote:
>> 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.
>
> Technically, you don't even need min and max at that point.  A bit mask
> would be enough.

Only for unsigned types...

-Steve

Steven Schveighoffer wrote:
> On Sun, 11 Apr 2010 22:36:33 -0400, Rainer Deyke <rainerd@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@free.fr
http://jeberger.free.fr
Jabber: jeberger@jabber.fr

Jérôme M. Berger wrote:
> Steven Schveighoffer wrote:
>> On Sun, 11 Apr 2010 22:36:33 -0400, Rainer Deyke <rainerd@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;

Don wrote:
> Jérôme M. Berger wrote:
>> Steven Schveighoffer wrote:
>>> On Sun, 11 Apr 2010 22:36:33 -0400, Rainer Deyke <rainerd@eldwood.com> wrote:
>>>> On 4/11/2010 13:16, Ali Çehreli wrote:
>>>>> Rainer Deyke wrote:
>>>> 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;
> 
	That is why I started my reply with "if that was all we wanted"...

		Jerome
-- 
mailto:jeberger@free.fr
http://jeberger.free.fr
Jabber: jeberger@jabber.fr