[LLVMdev] The nsw story

[Dan Gohman]

On Dec 5, 2011, at 5:50 PM, me22 wrote:

> On Thu, Dec 1, 2011 at 09:23, Dan Gohman <gohman at apple.com> wrote:
>> 
>> int a = INT_MAX, b = 1;
>> long c = (long)(a + b);
>> 
>> What is the value of c, on an LP64 target?
>> 
>> If a and b are promoted to 64-bit, c is 0x0000000080000000.
>> 
>> In a world where signed add overflow returns undef, c could be any of
>>  0x0000000000000000
>>  ...
>>  0xffffffffffffffff
>> however it can't ever be 0x0000000080000000, because there's no 32-bit value
>> the undef could take which sign-extends into that 64-bit value.
>> 
> 
> But since the add nsw returns undef, then isn't c "sext i32 undef to
> i64", and thus also undef?

No; sext i32 undef to i64 returns an extraordinary thing. It's a
64-bit value where the low 32 bits are undef, and the high
32 bits are sign extension from whatever bit 31 happened to be.
And the low 32 bits in this new value also fluctuate, and the
high 31 bits in this value fluctuate with them in concert with
bit 31 of the new value.

FWIW, you can also get non-bitwise fluctuation, such as (undef*3), which
is a value which fluctuates around multiples of 3. Or (undef*3)/5+1,
which fluctuates around, well, any value which could be computed by
that expression. You can build arbitrarily complex expression trees
around undef, and everything fluctuates according to the constraints of
operands and opcodes. It's quite magical.

> 
> I read it like this example from LangRef:
>      %B = undef
>      %C = xor %B, %B
>    Safe:
>      %C = undef
> 
> %C is undef, so can be later (in a bitwise or, for example) assumed to
> be -1, even though there's no possible choice of value for %B such
> that %B xor %B gives -1.

The reason this example works is that undef fluctuates, and further, it
causes things that use it to fluctuate (within their constraints, as I
discussed above). Since the xor reads %B twice, it could get two different
values, so %C can be an unconstrained undef.

Dan