On Dec 1, 2011, at 9:09 AM, Chris Lattner wrote:> > On Dec 1, 2011, at 8:46 AM, Dan Gohman wrote: > >> >> On Nov 30, 2011, at 10:49 PM, Chris Lattner wrote: >> >>> >>> On Nov 29, 2011, at 3:21 PM, Dan Gohman wrote: >>> >>>> >>>> A natural reaction to this problem is to think that LLVM IR is so nice >>>> and pretty that naturally there must be a nice and pretty solution. Here >>>> are some alternatives that have been considered: >>>> >>>> - Go back to using undef for overflow. There were no known real-world >>>> bugs with this. It's just inconsistent. >>> >>> +1 for the simple and obvious answer. >> >> To be clear, the main sign-extension elimination optimization is not valid under >> the simple and obvious answer. Are you proposing to do it anyway? > > Please define "valid". We discussed this a very very long time ago, and I don't recall the details.int a = INT_MAX, b = 1; long c = (long)(a + b); What is the value of c, on an LP64 target? By standard C rules, the add overflow invokes immediate undefined behavior of course. 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 0x0000000000000001 0x0000000000000002 ... 0x000000007fffffff or 0xffffffff80000000 0xffffffff80000001 0xffffffff80000002 ... 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. Therefore, if signed add overflow returns undef, promoting such 32-bit variables to 64-bit variables is not a behavior-preserving transformation. Dan
Dan Gohman <gohman at apple.com> writes:> In a world where signed add overflow returns undef, c could be any of > 0x0000000000000000 > 0x0000000000000001 > 0x0000000000000002 > ... > 0x000000007fffffff > or > 0xffffffff80000000 > 0xffffffff80000001 > 0xffffffff80000002 > ... > 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.Is undef considered to be "one true value" which is just unknown? I always considered it to be "any possible value." If the latter, there is no problem with undef "changing values" as a result of various operations, including sign extension.> Therefore, if signed add overflow returns undef, promoting such 32-bit variables to > 64-bit variables is not a behavior-preserving transformation.Sure it is, if undef is allowed to "float freely" and change its value on a whim. The behavior is, "this could be anything at any time." If I'm understanding you correctly. -Dave
On Thu, Dec 1, 2011 at 9:44 AM, David A. Greene <greened at obbligato.org> wrote:> Dan Gohman <gohman at apple.com> writes: > >> In a world where signed add overflow returns undef, c could be any of >> 0x0000000000000000 >> 0x0000000000000001 >> 0x0000000000000002 >> ... >> 0x000000007fffffff >> or >> 0xffffffff80000000 >> 0xffffffff80000001 >> 0xffffffff80000002 >> ... >> 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. > > Is undef considered to be "one true value" which is just unknown? I > always considered it to be "any possible value."The current LLVM IR definition of undef is essentially "each time undef is evaluated, it evaluates to an arbitrary value, but it must evaluate to some specific value". SimplifyDemandedBits is an example of a transformation which uses undef in a way that would be incorrect under a model where undef is like the current trap value; take a look at r133022 for a case where this matters. -Eli
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? 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. Confused, ~ Scott
On Mon, Dec 5, 2011 at 5:50 PM, me22 <me22.ca at gmail.com> 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"Yes.> and thus also undef?No: it's some value between INT32_MIN and INT32_MAX. Think of undef as a read from an arbitrary register: you can't predict what it will contain, but you know it contains some representable value. -Eli
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