On Tue, Jan 27, 2015 at 8:32 PM, Sanjoy Das <sanjoy at playingwithpointers.com> wrote:> > > > Correct me if I am wrong but we are talking about transforming: > > %maybe_poison = add nuw i32 %a, %b > > %x = zext i32 %maybe_poison to i64 > > %y = lshr i64 %x 32 > > > > To: > > %za = zext i32 %a to i64 > > %zb = zext i32 %b to i64 > > %x = add nuw i64 %za, %zb > > %y = lshr i64 %x 32 > > > > ? > > > > If so, this seems fine in the model given by the RFC. > > > > In the before case: > > %maybe_poison doesn't infect the upper bits of %x with its poison which > > allows %y to have the well defined result 0. > > > > In the after case: > > %za and %zb will have their top 32-bits filled with zeros making it > > impossible for nuw to be violated for %x, %y would have the well defined > > result 0. > > > > If both %a and %b are 2^32-1, won't %y be 0 in the first case and 1 in > the second?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. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150127/e67366c6/attachment.html>
> 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". Now if we do the usual transform of "zext (add nuw X Y)" => "add nuw (zext X) (zext Y)" then we get %m.wide = zext i32 %m to i64 %n.wide = zext i32 %n to i64 %z = add nuw i64 %m.wide, %n.wide %s = lshr i64 %y, 32 %addr = gep %some_global, %s store i32 42, i32* %addr The new program does *not* have the same behavior as the old program for "%m = %n = 2^32-1". We have changed the behavior of a well-defined program by doing the "zext (add nuw X Y)" => "add nuw (zext X) (zext Y)" transform. -- Sanjoy
> Now if we do the usual transform of "zext (add nuw X Y)" => "add nuw > (zext X) (zext Y)" then we get > > %m.wide = zext i32 %m to i64 > %n.wide = zext i32 %n to i64 > %z = add nuw i64 %m.wide, %n.wide > %s = lshr i64 %y, 32 > %addr = gep %some_global, %s > store i32 42, i32* %addrI made a typo here: the lshr should be "%s = lshr i64 %z, 32". Its value will be 1 for %m = %n = 2^32-1, and the transformed program will store 42 to &(%some_global)[1]. -- Sanjoy
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>
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". > > Now if we do the usual transform of "zext (add nuw X Y)" => "add nuw > (zext X) (zext Y)" then we get > > %m.wide = zext i32 %m to i64 > %n.wide = zext i32 %n to i64 > %z = add nuw i64 %m.wide, %n.wide > %s = lshr i64 %y, 32 > %addr = gep %some_global, %s > store i32 42, i32* %addr > > The new program does *not* have the same behavior as the old program > for "%m = %n = 2^32-1". We have changed the behavior of a > well-defined program by doing the "zext (add nuw X Y)" => "add nuw > (zext X) (zext Y)" transform. >After some pondering and combing through LLVM's implementation, I think we must conclude that zexting a value with any poison bits creates poison in every new bit. Considering the following program: %zext = zext i32 %x to i64 %icmp = icmp i64 %zext, i64 1 we'd like to transform this to: %icmp = icmp i32 %x, i32 1 Is it reasonable to say that '%icmp' in the before case is not poison but '%icmp' in the after case is poison? LLVM assumes it can remove casts with impunity, I think this is a useful property to maintain.> > -- Sanjoy >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150201/e77adea9/attachment.html>