[SCEV] Commute sign extends through nsw additions

[sanjoy]

Summary

Depends on D13613.

[sanjoy]

ping!

[nlewycky]

lib/Analysis/ScalarEvolution.cpp

1634

// sext(A +nsw B +nsw ... ) --> sext(A) +nsw sext(B) +nsw ...

1635–1637

Any reason not to do this with zext and nuw?

[sanjoy]

• address review: add comment

lib/Analysis/ScalarEvolution.cpp

1635–1637

No specific reason; we've only run into the sext case so far. If you think that it'll be good for symmetry, I can add a separate change for nuw by next week.

[nlewycky]

LGTM, but please do the obvious thing with zext too. I don't feel like the zext tests will need my review, but you can ask me to look at them if you feel otherwise. Thanks for the patch!

lib/Analysis/ScalarEvolution.cpp

1635–1637

Please do. You'll find the functions exceptionally symmetric already. :)

lib/Analysis/ScalarEvolution.cpp

if (SA->getNumOperands() == 2) {
           const APInt &C2 = SC2->getValue()->getValue();
           if (C1.isStrictlyPositive() && C2.isStrictlyPositive() &&
               C2.ugt(C1) && C2.isPowerOf2())
             return getAddExpr(getSignExtendExpr(SC1, Ty),
                               getSignExtendExpr(SMul, Ty));
         }
       }
     }
+
+    // sext((A + B + ...)<nsw>) --> (sext(A) + sext(B) + ...)<nsw>
+    if (SA->getNoWrapFlags(SCEV::FlagNSW)) {
+      // If the addition does not sign overflow then we can, by definition,
+      // commute the sign extension with the addition operation.
+      SmallVector<const SCEV *, 4> Ops;
+      for (const auto *Op : SA->operands())
+        Ops.push_back(getSignExtendExpr(Op, Ty));
+      return getAddExpr(Ops, SCEV::FlagNSW);
+    }
   }
   // If the input value is a chrec scev, and we can prove that the value
   // did not overflow the old, smaller, value, we can sign extend all of the
   // operands (often constants).  This allows analysis of something like
   // this:  for (signed char X = 0; X < 100; ++X) { int Y = X; }
   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op))
     if (AR->isAffine()) {
       const SCEV *Start = AR->getStart();

test/Analysis/ScalarEvolution/no-wrap-add-exprs.ll

; CHECK-NEXT:  -->  (2 + %len_norange) U: full-set S: full-set
   %q3 = sub i8 %len_norange, 2
 ; CHECK:  %q2 = sub i8 %len_norange, 1
 ; CHECK-NEXT:  -->  (-1 + %len_norange) U: full-set S: full-set
 ; CHECK:  %q3 = sub i8 %len_norange, 2
 ; CHECK-NEXT:  -->  (-2 + %len_norange) U: full-set S: full-set
 
   ret void
 }
+
+define void @f1(i8* %len_addr) {
+; CHECK-LABEL: Classifying expressions for: @f1
+ entry:
+  %len = load i8, i8* %len_addr, !range !0
+  %len_norange = load i8, i8* %len_addr
+; CHECK:  %len = load i8, i8* %len_addr, !range !0
+; CHECK-NEXT:  -->  %len U: [0,127) S: [0,127)
+; CHECK:  %len_norange = load i8, i8* %len_addr
+; CHECK-NEXT:  -->  %len_norange U: full-set S: full-set
+
+  %t0 = add i8 %len, -1
+  %t1 = add i8 %len, -2
+; CHECK:  %t0 = add i8 %len, -1
+; CHECK-NEXT:  -->  (-1 + %len)<nsw> U: [-1,126) S: [-1,126)
+; CHECK:  %t1 = add i8 %len, -2
+; CHECK-NEXT:  -->  (-2 + %len)<nsw> U: [-2,125) S: [-2,125)
+
+  %t0.sext = sext i8 %t0 to i16
+  %t1.sext = sext i8 %t1 to i16
+; CHECK:  %t0.sext = sext i8 %t0 to i16
+; CHECK-NEXT:  -->  (-1 + (zext i8 %len to i16))<nsw> U: [-1,126) S: [-1,126)
+; CHECK:  %t1.sext = sext i8 %t1 to i16
+; CHECK-NEXT:  -->  (-2 + (zext i8 %len to i16))<nsw> U: [-2,125) S: [-2,125)
+
+  %q0 = add i8 %len_norange, 1
+  %q1 = add i8 %len_norange, 2
+; CHECK:  %q0 = add i8 %len_norange, 1
+; CHECK-NEXT:  -->  (1 + %len_norange) U: full-set S: full-set
+; CHECK:  %q1 = add i8 %len_norange, 2
+; CHECK-NEXT:  -->  (2 + %len_norange) U: full-set S: full-set
+
+  %q0.sext = sext i8 %q0 to i16
+  %q1.sext = sext i8 %q1 to i16
+; CHECK:  %q0.sext = sext i8 %q0 to i16
+; CHECK-NEXT:  -->  (sext i8 (1 + %len_norange) to i16) U: [-128,128) S: [-128,128)
+; CHECK:  %q1.sext = sext i8 %q1 to i16
+; CHECK-NEXT:  -->  (sext i8 (2 + %len_norange) to i16) U: [-128,128) S: [-128,128)
+
+  ret void
+}