Preserving NSW/NUW bits

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.

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.

Thanks for the details, David. More comments below.

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

This is in fact the case. IndVarSimplicifaction is sign-extending the
induction variable. I also have a change that will widen the compare to
remove the trunc, but this is still a WIP. With all of this in place I'm
hoping InstCombine will do what I want and remove the extra 'add i64
%indvars.iv.next, -1.'

Chad