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
On Dec 5, 2011, at 7:44 PM, Dan Gohman wrote:> > 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.More precisely, the high 33 bits are known to be the same.> operands and opcodes. It's quite magical.It's actually not that magical. It's also essential that we have this behavior, otherwise normal bitfield code has "undefined" behavior and is misoptimized. This is why the result of "undef & 1" is known to have high bits zero. -Chris
Dan Gohman <gohman at apple.com> writes:> 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 thus they are undef because the low 32 bits were/are undef.> 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.That's just ridiculous. Undef is undef. We don't know anything special about it.> 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.This is silly. We can't count on undef having any special properties at all. If we do, IMHO it's a bug. -Dave
Chris Lattner <clattner at apple.com> writes:>> 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. > > More precisely, the high 33 bits are known to be the same.I think that's a very risky assumption. The name "undef" does not convey that at all.>> operands and opcodes. It's quite magical. > > It's actually not that magical. It's also essential that we have this > behavior, otherwise normal bitfield code has "undefined" behavior and > is misoptimized. This is why the result of "undef & 1" is known to > have high bits zero.Well sure, because we know (x & 1) has the high bits set to zero for any value of x. In the sext case, we know nothing about the high bits because we don't know what bit 32 was/is. Yes, we know the high bits are the same but it's surprising to me that this would be represented as "undef." "undef" to me means I can assume any value at all, not restricted to "all the bits are the same." -Dave
On Dec 6, 2011, at 12:32 AM, Chris Lattner wrote:> > On Dec 5, 2011, at 7:44 PM, Dan Gohman wrote: > >> operands and opcodes. It's quite magical. > > It's actually not that magical.It's not magical from an LLVM perspective. But it is one of the areas where the popular mental model of LLVM IR as an assembly language breaks down. Undef is weirder than PHI nodes. Dan