On Tue, Jan 27, 2015 at 8:58 PM, Sanjoy Das <sanjoy at playingwithpointers.com> wrote:> > Ah, yes. You are right, we cannot always assume that %y would be zero in > > the second case. > > This wouldn't be the first time we've lost information that we could use > to > > optimize a program by transforming it. > > > > Do you think this result would be problematic? It seems consistent with > the > > RFC and LLVM's current behavior. > > > > The problem is not that we're losing information, the problem is that > we're changing the behavior of a well-defined program. > > I'll try to put the whole argument in one place: > > We start with > > %x = add nuw i32 %m, %n > %y = zext i32 %x to i64 > %s = lshr i64 %y, 32 > %addr = gep %some_global, %s > store i32 42, i32* %addr > > In the above program, for all values of %x, %s is 0. This means the > program is well-defined when %x is poison (since you don't need to > look at %x to determine the value of %addr, in the same sense as you > don't need to look at X to determine the value of "and X, 0"); and it > stores 42 to &(%some_global)[0]. Specifically, the above program is > well defined for "%m = %n = 2^32-1".I don't follow this last sentence. if the definition of NUW is that zext-ing the result is equivalent to zext-ing the inputs and doing the operation at a higher bitwidth (my understanding), then %m and %n cannot hold those values, that would violate the NUW flag. Either my understanding of th edefinition holds, or the transformation you are proposing isn't valid IMO. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150127/bd36ea4b/attachment.html>
> if the definition of NUW is that zext-ing the result is equivalent to > zext-ing the inputs and doing the operation at a higher bitwidth (my > understanding), then %m and %n cannot hold those values, that would violate > the NUW flag.The problem to solve is adequately defining "cannot hold". In the strictest sense, you could say if %m = %n = 2^31 - 1 then the program has UB; in effect defining "cannot hold" in the same way a location you're loading from "cannot be" non-deferenceable. But, as David points out, that would mean you cannot hoist arithmetic with the nuw/nsw tags intact: if (foo) %t = add nuw X Y since it could be that (X != 2^32-1 && Y != 2^32-1) only if foo =true. Arithmetic with no-wrap flags effectively are side-effecting operations in this scheme. The RFC tries to formalize a weaker notion of "cannot hold" that justifies treating arithmetic like arithmetic. I'm trying to show that the notion of poison value in this RFC is too weak; and allows for certain programs to be well-defined (like the example I just showed) which change meaning in the face of transforms we'd like to be able to do. -- Sanjoy
On Tue, Jan 27, 2015 at 9:38 PM, Sanjoy Das <sanjoy at playingwithpointers.com> wrote:> > if the definition of NUW is that zext-ing the result is equivalent to > > zext-ing the inputs and doing the operation at a higher bitwidth (my > > understanding), then %m and %n cannot hold those values, that would > violate > > the NUW flag. > > The problem to solve is adequately defining "cannot hold". In the > strictest sense, you could say if %m = %n = 2^31 - 1 then the program > has UB; in effect defining "cannot hold" in the same way a location > you're loading from "cannot be" non-deferenceable. But, as David points > out, that would mean you cannot hoist arithmetic with the nuw/nsw tags > intact: > > if (foo) > %t = add nuw X Y > > since it could be that (X != 2^32-1 && Y != 2^32-1) only if foo => true. Arithmetic with no-wrap flags effectively are side-effecting > operations in this scheme. > > The RFC tries to formalize a weaker notion of "cannot hold" that > justifies treating arithmetic like arithmetic.Yes, quite familiar.> I'm trying to show > that the notion of poison value in this RFC is too weak; and allows > for certain programs to be well-defined (like the example I just > showed) which change meaning in the face of transforms we'd like to be > able to do.I see, this is a case where the RFC as it stands strips poison too soon. Going to ponder this, I feel like this should be something we can incorporate into the model. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150127/dcc58ff9/attachment.html>
On 01/27/2015 09:38 PM, Sanjoy Das wrote:>> if the definition of NUW is that zext-ing the result is equivalent to >> zext-ing the inputs and doing the operation at a higher bitwidth (my >> understanding), then %m and %n cannot hold those values, that would violate >> the NUW flag. > The problem to solve is adequately defining "cannot hold". In the > strictest sense, you could say if %m = %n = 2^31 - 1 then the program > has UB; in effect defining "cannot hold" in the same way a location > you're loading from "cannot be" non-deferenceable. But, as David points > out, that would mean you cannot hoist arithmetic with the nuw/nsw tags > intact: > > if (foo) > %t = add nuw X Y > > since it could be that (X != 2^32-1 && Y != 2^32-1) only if foo => true. Arithmetic with no-wrap flags effectively are side-effecting > operations in this scheme. > > The RFC tries to formalize a weaker notion of "cannot hold" that > justifies treating arithmetic like arithmetic. I'm trying to show > that the notion of poison value in this RFC is too weak; and allows > for certain programs to be well-defined (like the example I just > showed) which change meaning in the face of transforms we'd like to be > able to do.I don't think your example is actually problematic. The original program before your transformation *executed* undefined behavior in the form of '%x = add nuw i32 %m, %n' with "%m = %n = 2^32-1 (a.k.a INT_MAX)". If I understand the c++ spec correctly, that implies that the meaning of this program is lost, even if the value of that instruction doesn't contribute to the output of the program. We can produce any output for this program (or none, or wipe your hard drive) and it would be "correct". To show a problem, you'd need to show a *well defined* program which becomes undefined through a series of transformations. In your example, you might try the input program: br i1 %cnd, label %skip, label %exec exec: %x1 = add nuw i32 %m, %n br label %skip skip: %x = phi (x1, 0) %y = zext i32 %x to i64 %s = lshr i64 %y, 32 %addr = gep %some_global, %s store i32 42, i32* %addr But when the add is speculated, this becomes: %x1 = add nuw i32 %m, %n %x = select i1 %cnd x1, 0 %y = zext i32 %x to i64 %s = lshr i64 %y, 32 %addr = gep %some_global, %s store i32 42, i32* %addr This is well defined as per the spec David sent out. %x is not poison. %x1 is, but that's fine. Philip -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150128/85639b0f/attachment.html>