llvm dev - May 2016 - Reasoning about known bits of the absolute value of a signed integer

I'm trying to reason about how to find certain bit positions of the absolute
value of a given integer value. Specifically, I want to know the highest
possibly set bit and lowest possibly set bit of the absolute value, in order to
find the range between the two.

Note that I'm specifically trying to be as conservative as possible.

This is what I have so far:

If the sign bit of the original integer is a known 0 (known positive) - the
highest possibly set bit is the highest bit not known to be zero, and the lowest
possibly set bit is the lowest bit not known to be zero.

If the sign bit of the original integer is a known 1 (known negative) - the
highest possibly set bit is the one *to the left of* the *lowest* bit not known
to be one (unless that would be the sign bit, in which case it is replaced with
the bit to the right of the sign bit), and the lowest possibly set bit is the
lowest bit not known to be zero, UNLESS *every* bit other than the sign bit is
not known to be one, in which case the highest possibly set bit is the sign bit.

If the sign bit of the original integer is unknown - same as if known negative,
except the highest possibly set bit is initially the higher of the two rules for
highest possibly set bit.

Is this correct? Can it be less conservative in certain situations? Are there
any times where we know that only one of the highest and lowest possibly set
bits can actually be set?

I apologize for any headaches this causes.

 - CL

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160503/e9550cc2/attachment.html>

Hi Carlos,

Carlos Liam via llvm-dev wrote:
 > I'm trying to reason about how to find certain bit positions of the
 > absolute value of a given integer value. Specifically, I want to know
 > the highest possibly set bit and lowest possibly set bit of the absolute
 > value, in order to find the range between the two.
 >
 > Note that I'm specifically trying to be as conservative as possible.

I don't think you are or want to be as conservative as possible. :P

The most conservative answer will always be "highest possibly set bit"
== WordSize-1, "lowest possibly set bit" == 0.  I think you want you
want to be as *precise* as possible while still being correct.


I would approach the problem slightly differently than you have: the
KnownZero and KnownOne bitvectors are really approximations to the
actual integer you'll see at runtime.  I'd try to think of how you
can map the 100% precise runtime notion of ABS into this imperfect
approximation.  Once you can pipe KnownZero and KnownOne through an
approximation of ABS, then you know what bits of the absolute value are
known, and can compute the highest and lowest "possibly set" bit
positions from that (basically just by looking at CLZ(KnownZero) and
CTZ(KnownZero)).

A rough sketch of how to map ABS to KnownZero and KnownOne (let's call
the result ApproxABS) is (please _carefully_ verify this :) ):

We know:

ABS(x) == NOT(x) + 1

Giving:

Let {A, B} denote the approximation KnownZero = A, KnownOne = B

ApproxABS({A, B}) == ApproxIncrement(ApproxNot({A, B}))

== ApproxIncrement(({B, A}))

`ApproxIncrement` is a little trickier:

   Carry = 1;  // since we're adding 1. This can be 0, 1 or unknown
   for i = 0 to wordSize-1:
     if KnownZero[i]:
       if Carry is 1:
         Result.KnownOne[i] = 1
       else if Carry is 0:
         Result.KnownZero[i] = 1
       Carry = 0
       continue  // never any carry
     if KnownOne[i]:
       if Carry is 1:
         Result.KnownZero[i] = 1
	Carry = 1
       else if Carry is 0:
         Result.KnownOne[i] = 1
	Carry = 0
       else if Carry is unknown:
         Carry = unknown
       continue
     // if neither one or zero is known:
     if Carry == 1:
       Carry = unknown

-- Sanjoy

Hi Carlos,

I made a notational mistake here, ABS everywhere should be NEG (i.e. negate). 
To get ABS from Neg, you should be able
to do:

ABS({A,B}) = if A.hasSignBitSet(): {A, B}  // positive
              else if B.hasSignBitSet(): NEG({A,B})  // negative
              else {
                {P, Q} = NEG({A, B})
                return {P & Q, Q & B}
              }

Or something better.

-- Sanjoy



>
> Giving:
>
> Let {A, B} denote the approximation KnownZero = A, KnownOne = B
>
> ApproxABS({A, B}) == ApproxIncrement(ApproxNot({A, B}))
>
> == ApproxIncrement(({B, A}))
>
> `ApproxIncrement` is a little trickier:
>
> Carry = 1; // since we're adding 1. This can be 0, 1 or unknown
> for i = 0 to wordSize-1:
> if KnownZero[i]:
> if Carry is 1:
> Result.KnownOne[i] = 1
> else if Carry is 0:
> Result.KnownZero[i] = 1
> Carry = 0
> continue // never any carry
> if KnownOne[i]:
> if Carry is 1:
> Result.KnownZero[i] = 1
> Carry = 1
> else if Carry is 0:
> Result.KnownOne[i] = 1
> Carry = 0
> else if Carry is unknown:
> Carry = unknown
> continue
> // if neither one or zero is known:
> if Carry == 1:
> Carry = unknown
>
> -- Sanjoy

Carlos, if you're trying to answer a question about integer ranges, 
maybe LVI is a better match than ValueTracking?  I recently added a 
method that lets you ask LVI for the ConstantRange associated with a 
value-- from there you might be able to figure out the thing that you 
actually want.

John


On 5/3/16 6:31 PM, Carlos Liam via llvm-dev wrote:
> I'm trying to reason about how to find certain bit positions of the
> absolute value of a given integer value. Specifically, I want to know
> the highest possibly set bit and lowest possibly set bit of the absolute
> value, in order to find the range between the two.
>
> Note that I'm specifically trying to be as conservative as possible.
>
> This is what I have so far:
>
> If the sign bit of the original integer is a known 0 (known positive) -
> the highest possibly set bit is the highest bit not known to be zero,
> and the lowest possibly set bit is the lowest bit not known to be zero.
>
> If the sign bit of the original integer is a known 1 (known negative) -
> the highest possibly set bit is the one *to the left of* the *lowest*
> bit not known to be one (unless that would be the sign bit, in which
> case it is replaced with the bit to the right of the sign bit), and the
> lowest possibly set bit is the lowest bit not known to be zero, UNLESS
> *every* bit other than the sign bit is not known to be one, in which
> case the highest possibly set bit is the sign bit.
>
> If the sign bit of the original integer is unknown - same as if known
> negative, except the highest possibly set bit is initially the higher of
> the two rules for highest possibly set bit.
>
> Is this correct? Can it be less conservative in certain situations? Are
> there any times where we know that only one of the highest and lowest
> possibly set bits can actually be set?
>
> I apologize for any headaches this causes.
>
>  - CL
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>