[SCEV] Infer nuw from nw for addrecs

[reames]

Summary

Noticed this while working on another patch. Was originally going to just land it, but it seemed a little too obvious and I'm tired. Is there something I'm missing here?

[lebedev.ri]

This does appear correct to me.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

2398

Why the IsKnownNonNegative check for the NUW case? Shouldn't this be on NSW?

[lebedev.ri]

llvm/lib/Analysis/ScalarEvolution.cpp

2393–2394

Comment implies that the step must be non-negative in both cases,
but enforces that only in the first case.

[lebedev.ri]

For the record, this

In D108601#2962217, @lebedev.ri wrote:

This does appear correct to me.

isn't approval. There's 'accept revision' for that.
I'm not sure just how much more softly do i need to word that message to convey that.

[reames]

llvm/lib/Analysis/ScalarEvolution.cpp

2398

We definitely need it for NSW - I'd apparently dropped it for the NSW case when rebasing this. Oops.

For the unsigned case, I'll be honest and say I'm not sure. I get really confused about the interpretation of the signed integer overflow rules on add. The case I was thinking of was starting at 0, and adding -1. Does that violate nuw or not? If it does, we need the positive check. If it doesn't, we probably don't. Now that I write this, I'm pretty sure the answer is we don't, but I regularly get confused by that case, so I'll let someone else confirm. :)

Keeping in mind that SCEV and IR mix flag interpretations oddly, I'm strongly tempted to keep the non-negative test for (my) sanity sake even if we don't strictly speaking need it.

[reames]

In D108601#2962661, @lebedev.ri wrote:

For the record, this

In D108601#2962217, @lebedev.ri wrote:

This does appear correct to me.

isn't approval. There's 'accept revision' for that.
I'm not sure just how much more softly do i need to word that message to convey that.

Sorry I misread your intent. It certainly read like approval to me, but well, my screw up. Reverted, and review resumed. Will wait for an explicit LGTM.

[reames]

Add missing non-negative check to NSW case.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

2398

If you think about it as not adding 0 and -1, but rather 0 and 0xffffffff, then it becomes more obvious that it's nuw. I'd prefer not having an unnecessary isKnownNonNegative check here -- doing sign checks for unsigned arithmetic is usually an indication that some logic isn't right...

(And if we don't need to check the sign, we can drop the Ops.size() == 2 limitation for the nuw case as well.)

[reames]

Implement review comment and narrow scope to nuw only.

I'll come back to the nsw case separately, but a) nuw is what's actually blocking me, and b) with the focus on generality in the review comments, we should do the same for nsw which requires a bit more code motion than I want to roll into this patch.

[lebedev.ri]

Now this i don't think is right.

llvm/test/Transforms/IndVarSimplify/widen-loop-comp.ll

514 ↗

(On Diff #368404)

Alive doesn't like this
https://alive2.llvm.org/ce/z/T5MNLf

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

2398

Okay, looks like I was wrong here! The bit I was missing is that nw is actually a signed property:

/// AddRec expressions may have a no-self-wraparound <NW> property if, in
/// the integer domain, abs(step) * max-iteration(loop) <=
/// unsigned-max(bitwidth).  This means that the recurrence will never reach
/// its start value if the step is non-zero.  Computing the same value on
/// each iteration is not considered wrapping, and recurrences with step = 0
/// are trivially <NW>.  <NW> is independent of the sign of step and the
/// value the add recurrence starts with.

Note the abs(step) in the definition. So we do need to ensure that the step is non-negative, to make sure that abs(step) is just step.

[reames]

llvm/lib/Analysis/ScalarEvolution.cpp

2398

Yeah, I'd just worked my way to the same conclusion. For my own future reference, here's the chain of logic.

no-self-wrap is a property which describes the space traversed. It is not a wrapping property per se.

(0,+, 255) in 8 bit math represents a value which decreases by one on each iteration (by wrapping through unsigned). Putting NUW on this generates poison on the 2nd iteration. NW on the other hand, is not violated because the number of values traversed (assuming BTC is small) is less than 255.

We need the non-negative restriction to line up the restriction in terms of values traversed with the NUW definition.

[reames]

Add back the positive restriction. The affine restriction could possibly be relaxed in the future.

[lebedev.ri]

LG

llvm/lib/Analysis/ScalarEvolution.cpp

2393

llvm/lib/Analysis/ScalarEvolution.cpp

if (SignOrUnsignWrap != SignOrUnsignMask &&
     if (!(SignOrUnsignWrap & SCEV::FlagNUW)) {
       auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
           Opcode, C, OBO::NoUnsignedWrap);
       if (NUWRegion.contains(SE->getUnsignedRange(Ops[1])))
         Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
     }
   }
 
+  // <0,+,nonnegative><nw> is also nuw
+  // TODO: Add corresponding nsw case
+  if (Type == scAddRecExpr && ScalarEvolution::hasFlags(Flags, SCEV::FlagNW) &&
+      !ScalarEvolution::hasFlags(Flags, SCEV::FlagNUW) && Ops.size() == 2 &&
+      Ops[0]->isZero() && IsKnownNonNegative(Ops[1]))
+    Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
+
   return Flags;
 }
 
 bool ScalarEvolution::isAvailableAtLoopEntry(const SCEV *S, const Loop *L) {
   return isLoopInvariant(S, L) && properlyDominates(S, L->getHeader());
 }
 
 /// Get a canonical add expression, or something simpler if possible.

llvm/test/Analysis/ScalarEvolution/ptrtoint.ll

 ; X64-NEXT:    --> (ptrtoint i8* %arg to i64) U: full-set S: full-set
 ; X64-NEXT:    %i7 = phi i8* [ %arg, %bb3 ], [ %i14, %bb6 ]
 ; X64-NEXT:    --> {%arg,+,1}<nuw><%bb6> U: full-set S: full-set Exits: (-1 + (-1 * (ptrtoint i8* %arg to i64)) + (ptrtoint i8* %arg1 to i64) + %arg) LoopDispositions: { %bb6: Computable }
 ; X64-NEXT:    %i8 = load i8, i8* %i7, align 1
 ; X64-NEXT:    --> %i8 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %bb6: Variant }
 ; X64-NEXT:    %i9 = ptrtoint i8* %i7 to i64
 ; X64-NEXT:    --> {(ptrtoint i8* %arg to i64),+,1}<nuw><%bb6> U: full-set S: full-set Exits: (-1 + (ptrtoint i8* %arg1 to i64)) LoopDispositions: { %bb6: Computable }
 ; X64-NEXT:    %i10 = sub i64 %i9, %i4
-; X64-NEXT:    --> {0,+,1}<nw><%bb6> U: full-set S: full-set Exits: (-1 + (-1 * (ptrtoint i8* %arg to i64)) + (ptrtoint i8* %arg1 to i64)) LoopDispositions: { %bb6: Computable }
+; X64-NEXT:    --> {0,+,1}<nuw><%bb6> U: full-set S: full-set Exits: (-1 + (-1 * (ptrtoint i8* %arg to i64)) + (ptrtoint i8* %arg1 to i64)) LoopDispositions: { %bb6: Computable }
 ; X64-NEXT:    %i11 = getelementptr inbounds i8, i8* %arg2, i64 %i10
 ; X64-NEXT:    --> {%arg2,+,1}<nw><%bb6> U: full-set S: full-set Exits: (-1 + (-1 * (ptrtoint i8* %arg to i64)) + (ptrtoint i8* %arg1 to i64) + %arg2) LoopDispositions: { %bb6: Computable }
 ; X64-NEXT:    %i12 = load i8, i8* %i11, align 1
 ; X64-NEXT:    --> %i12 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %bb6: Variant }
 ; X64-NEXT:    %i13 = add i8 %i12, %i8
 ; X64-NEXT:    --> (%i12 + %i8) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %bb6: Variant }
 ; X64-NEXT:    %i14 = getelementptr inbounds i8, i8* %i7, i64 1
 ; X64-NEXT:    --> {(1 + %arg)<nuw>,+,1}<nuw><%bb6> U: [1,0) S: [1,0) Exits: ((-1 * (ptrtoint i8* %arg to i64)) + (ptrtoint i8* %arg1 to i64) + %arg) LoopDispositions: { %bb6: Computable }

 ; X32-NEXT:    --> (zext i32 (ptrtoint i8* %arg to i32) to i64) U: [0,4294967296) S: [0,4294967296)
 ; X32-NEXT:    %i7 = phi i8* [ %arg, %bb3 ], [ %i14, %bb6 ]
 ; X32-NEXT:    --> {%arg,+,1}<nuw><%bb6> U: full-set S: full-set Exits: (-1 + (-1 * (ptrtoint i8* %arg to i32)) + (ptrtoint i8* %arg1 to i32) + %arg) LoopDispositions: { %bb6: Computable }
 ; X32-NEXT:    %i8 = load i8, i8* %i7, align 1
 ; X32-NEXT:    --> %i8 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %bb6: Variant }
 ; X32-NEXT:    %i9 = ptrtoint i8* %i7 to i64
 ; X32-NEXT:    --> {(zext i32 (ptrtoint i8* %arg to i32) to i64),+,1}<nuw><%bb6> U: [0,8589934591) S: [0,8589934591) Exits: ((zext i32 (-1 + (-1 * (ptrtoint i8* %arg to i32)) + (ptrtoint i8* %arg1 to i32)) to i64) + (zext i32 (ptrtoint i8* %arg to i32) to i64)) LoopDispositions: { %bb6: Computable }
 ; X32-NEXT:    %i10 = sub i64 %i9, %i4
-; X32-NEXT:    --> {0,+,1}<nw><%bb6> U: [0,4294967296) S: [0,4294967296) Exits: (zext i32 (-1 + (-1 * (ptrtoint i8* %arg to i32)) + (ptrtoint i8* %arg1 to i32)) to i64) LoopDispositions: { %bb6: Computable }
+; X32-NEXT:    --> {0,+,1}<nuw><%bb6> U: [0,4294967296) S: [0,4294967296) Exits: (zext i32 (-1 + (-1 * (ptrtoint i8* %arg to i32)) + (ptrtoint i8* %arg1 to i32)) to i64) LoopDispositions: { %bb6: Computable }
 ; X32-NEXT:    %i11 = getelementptr inbounds i8, i8* %arg2, i64 %i10
 ; X32-NEXT:    --> {%arg2,+,1}<%bb6> U: full-set S: full-set Exits: (-1 + (-1 * (ptrtoint i8* %arg to i32)) + (ptrtoint i8* %arg1 to i32) + %arg2) LoopDispositions: { %bb6: Computable }
 ; X32-NEXT:    %i12 = load i8, i8* %i11, align 1
 ; X32-NEXT:    --> %i12 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %bb6: Variant }
 ; X32-NEXT:    %i13 = add i8 %i12, %i8
 ; X32-NEXT:    --> (%i12 + %i8) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %bb6: Variant }
 ; X32-NEXT:    %i14 = getelementptr inbounds i8, i8* %i7, i64 1
 ; X32-NEXT:    --> {(1 + %arg)<nuw>,+,1}<nuw><%bb6> U: [1,0) S: [1,0) Exits: ((-1 * (ptrtoint i8* %arg to i32)) + (ptrtoint i8* %arg1 to i32) + %arg) LoopDispositions: { %bb6: Computable }

 ; X64-NEXT:    --> (ptrtoint i32* %arg to i64) U: full-set S: full-set
 ; X64-NEXT:    %i7 = phi i32* [ %arg, %bb3 ], [ %i15, %bb6 ]
 ; X64-NEXT:    --> {%arg,+,4}<nuw><%bb6> U: full-set S: full-set Exits: ((4 * ((-4 + (-1 * (ptrtoint i32* %arg to i64)) + (ptrtoint i32* %arg1 to i64)) /u 4))<nuw> + %arg) LoopDispositions: { %bb6: Computable }
 ; X64-NEXT:    %i8 = load i32, i32* %i7, align 4
 ; X64-NEXT:    --> %i8 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %bb6: Variant }
 ; X64-NEXT:    %i9 = ptrtoint i32* %i7 to i64
 ; X64-NEXT:    --> {(ptrtoint i32* %arg to i64),+,4}<nuw><%bb6> U: full-set S: full-set Exits: ((4 * ((-4 + (-1 * (ptrtoint i32* %arg to i64)) + (ptrtoint i32* %arg1 to i64)) /u 4))<nuw> + (ptrtoint i32* %arg to i64)) LoopDispositions: { %bb6: Computable }
 ; X64-NEXT:    %i10 = sub i64 %i9, %i4
-; X64-NEXT:    --> {0,+,4}<nw><%bb6> U: [0,-3) S: [-9223372036854775808,9223372036854775805) Exits: (4 * ((-4 + (-1 * (ptrtoint i32* %arg to i64)) + (ptrtoint i32* %arg1 to i64)) /u 4))<nuw> LoopDispositions: { %bb6: Computable }
+; X64-NEXT:    --> {0,+,4}<nuw><%bb6> U: [0,-3) S: [-9223372036854775808,9223372036854775805) Exits: (4 * ((-4 + (-1 * (ptrtoint i32* %arg to i64)) + (ptrtoint i32* %arg1 to i64)) /u 4))<nuw> LoopDispositions: { %bb6: Computable }
 ; X64-NEXT:    %i11 = ashr exact i64 %i10, 2
 ; X64-NEXT:    --> %i11 U: [-2305843009213693952,2305843009213693952) S: [-2305843009213693952,2305843009213693952) Exits: <<Unknown>> LoopDispositions: { %bb6: Variant }
 ; X64-NEXT:    %i12 = getelementptr inbounds i32, i32* %arg2, i64 %i11
 ; X64-NEXT:    --> ((4 * %i11)<nsw> + %arg2) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %bb6: Variant }
 ; X64-NEXT:    %i13 = load i32, i32* %i12, align 4
 ; X64-NEXT:    --> %i13 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %bb6: Variant }
 ; X64-NEXT:    %i14 = add nsw i32 %i13, %i8
 ; X64-NEXT:    --> (%i13 + %i8) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %bb6: Variant }

 ; X32-NEXT:    --> (zext i32 (ptrtoint i32* %arg to i32) to i64) U: [0,4294967296) S: [0,4294967296)
 ; X32-NEXT:    %i7 = phi i32* [ %arg, %bb3 ], [ %i15, %bb6 ]
 ; X32-NEXT:    --> {%arg,+,4}<nuw><%bb6> U: full-set S: full-set Exits: ((4 * ((-4 + (-1 * (ptrtoint i32* %arg to i32)) + (ptrtoint i32* %arg1 to i32)) /u 4))<nuw> + %arg) LoopDispositions: { %bb6: Computable }
 ; X32-NEXT:    %i8 = load i32, i32* %i7, align 4
 ; X32-NEXT:    --> %i8 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %bb6: Variant }
 ; X32-NEXT:    %i9 = ptrtoint i32* %i7 to i64
 ; X32-NEXT:    --> {(zext i32 (ptrtoint i32* %arg to i32) to i64),+,4}<nuw><%bb6> U: [0,8589934588) S: [0,8589934588) Exits: ((zext i32 (ptrtoint i32* %arg to i32) to i64) + (4 * ((zext i32 (-4 + (-1 * (ptrtoint i32* %arg to i32)) + (ptrtoint i32* %arg1 to i32)) to i64) /u 4))<nuw><nsw>) LoopDispositions: { %bb6: Computable }
 ; X32-NEXT:    %i10 = sub i64 %i9, %i4
-; X32-NEXT:    --> {0,+,4}<nw><%bb6> U: [0,4294967293) S: [0,4294967293) Exits: (4 * ((zext i32 (-4 + (-1 * (ptrtoint i32* %arg to i32)) + (ptrtoint i32* %arg1 to i32)) to i64) /u 4))<nuw><nsw> LoopDispositions: { %bb6: Computable }
+; X32-NEXT:    --> {0,+,4}<nuw><%bb6> U: [0,4294967293) S: [0,4294967293) Exits: (4 * ((zext i32 (-4 + (-1 * (ptrtoint i32* %arg to i32)) + (ptrtoint i32* %arg1 to i32)) to i64) /u 4))<nuw><nsw> LoopDispositions: { %bb6: Computable }
 ; X32-NEXT:    %i11 = ashr exact i64 %i10, 2
 ; X32-NEXT:    --> %i11 U: [-2147483648,2147483648) S: [-2147483648,2147483648) Exits: <<Unknown>> LoopDispositions: { %bb6: Variant }
 ; X32-NEXT:    %i12 = getelementptr inbounds i32, i32* %arg2, i64 %i11
 ; X32-NEXT:    --> ((4 * (trunc i64 %i11 to i32))<nsw> + %arg2) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %bb6: Variant }
 ; X32-NEXT:    %i13 = load i32, i32* %i12, align 4
 ; X32-NEXT:    --> %i13 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %bb6: Variant }
 ; X32-NEXT:    %i14 = add nsw i32 %i13, %i8
 ; X32-NEXT:    --> (%i13 + %i8) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %bb6: Variant }