David/All, Just a quick question about NSW/NUW bits, if you've got a second. I noticed you've been doing a little work on this as of late. I have a bit of code that looks like the following: %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 %2 = add i64 %indvars.iv.next, -1 %tmp = trunc i64 %2 to i32 %cmp = icmp slt i32 %tmp, %0 br i1 %cmp, label %for.body, label %for.end.loopexit I'm trying to fold the 2nd add instruction into the compare by changing the condition from from 'slt' to 'sle': %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 %tmp = trunc i64 %indvars.iv.next to i32 %cmp = icmp sle i32 %tmp, %0 br i1 %cmp, label %for.body, label %for.end.loopexit However, AFAICT the NSW bits must be set. In what cases can we propagate the NSW bit from the first add to the second, if any? If a case exists, can this be handled by the WillNotOverflowSignedAdd function? Chad
So, the trunc makes this transform a bit questionable because you have to reason about bits in the middle of your value. Consider the following input values: %indvars.iv = 0x........7fffffff %0 = 0x8......1 Consider the following values in the 'before' case: %2 = 0x........7fffffff %indvars.iv.next = 0x........80000000 %tmp = 0x7fffffff %cmp = false This results in the following values in the 'after' case: %indvars.iv.next = 0x........80000000 %tmp = 0x80000000 %cmp = true Regardless of whether or not you propagate nsw/nuw, the transform is currently unsound. The transform is sound if %indvars.iv has a sufficiently large number of signbits. e.x. %indvars.iv = sext i31 %invdars.actual to i64 If this precondition holds, any existing nsw or nuw flags should still hold. On Tue, Sep 2, 2014 at 3:22 PM, Chad Rosier <mcrosier at codeaurora.org> wrote:> David/All, > Just a quick question about NSW/NUW bits, if you've got a second. I > noticed you've been doing a little work on this as of late. > > I have a bit of code that looks like the following: > > %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 > %2 = add i64 %indvars.iv.next, -1 > %tmp = trunc i64 %2 to i32 > %cmp = icmp slt i32 %tmp, %0 > br i1 %cmp, label %for.body, label %for.end.loopexit > > I'm trying to fold the 2nd add instruction into the compare by changing > the condition from from 'slt' to 'sle': > > %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 > %tmp = trunc i64 %indvars.iv.next to i32 > %cmp = icmp sle i32 %tmp, %0 > br i1 %cmp, label %for.body, label %for.end.loopexit > > However, AFAICT the NSW bits must be set. In what cases can we propagate > the NSW bit from the first add to the second, if any? If a case exists, > can this be handled by the WillNotOverflowSignedAdd function? > > Chad > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140902/594b29b9/attachment.html>
On Tue, Sep 2, 2014 at 4:16 PM, David Majnemer <david.majnemer at gmail.com> wrote:> So, the trunc makes this transform a bit questionable because you have to > reason about bits in the middle of your value. > > Consider the following input values: > %indvars.iv = 0x........7fffffff > %0 = 0x8......1 > > Consider the following values in the 'before' case: > %2 = 0x........7fffffff > %indvars.iv.next = 0x........80000000 > %tmp = 0x7fffffff > %cmp = false > > This results in the following values in the 'after' case: > %indvars.iv.next = 0x........80000000 > %tmp = 0x80000000 > %cmp = true > > Regardless of whether or not you propagate nsw/nuw, the transform is > currently unsound. > > The transform is sound if %indvars.iv has a sufficiently large number of > signbits. > e.x. > %indvars.iv = sext i31 %invdars.actual to i64 > > If this precondition holds, any existing nsw or nuw flags should still > hold. >Some other interesting things spring to mind. If either (%indvars.iv & (1 << 31)) == 1 or if (%indvars.iv & (1 << 31)) =(%indvars.iv & (1 << 30)), then the transform is safe; I'm not immediately sure about nuw or nsw.> > > > On Tue, Sep 2, 2014 at 3:22 PM, Chad Rosier <mcrosier at codeaurora.org> > wrote: > >> David/All, >> Just a quick question about NSW/NUW bits, if you've got a second. I >> noticed you've been doing a little work on this as of late. >> >> I have a bit of code that looks like the following: >> >> %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 >> %2 = add i64 %indvars.iv.next, -1 >> %tmp = trunc i64 %2 to i32 >> %cmp = icmp slt i32 %tmp, %0 >> br i1 %cmp, label %for.body, label %for.end.loopexit >> >> I'm trying to fold the 2nd add instruction into the compare by changing >> the condition from from 'slt' to 'sle': >> >> %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 >> %tmp = trunc i64 %indvars.iv.next to i32 >> %cmp = icmp sle i32 %tmp, %0 >> br i1 %cmp, label %for.body, label %for.end.loopexit >> >> However, AFAICT the NSW bits must be set. In what cases can we propagate >> the NSW bit from the first add to the second, if any? If a case exists, >> can this be handled by the WillNotOverflowSignedAdd function? >> >> Chad >> >> >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140902/7ec69e2d/attachment.html>