[SCEV][NFC] Introduce utility functions that measure number of iterations before overflow

[mkazantsev]

Summary

Current implementation of getBackedgeTakenCount returns the number of iterations if the loop
exits by its latch condition and not by some side exit (like exception throw or guard). On the other
hand, nsw/nuw flags in AddRecExpr guarantee no-overflow in real loop execution. In patricular,
it can be set based on fact that we have proved that the loop always exits by guard after some iterations.

This inconsistence lures to make an assumption that if an AddRec has no-wrap flag then it will not overflow
if we make getBackedgeTakenCount iterations, and it is incorrect. It creates dangerous pitfalls, see details
of https://reviews.llvm.org/D37569 as an example. In particular, we cannot use the fact that some monotonic
predicate is true on first and last iteration to prove that it is also true on every intermediate iteration just because
the monotonicity could be proved from guard and last iteration is calculated with getBackedgeTakenCount.

To resolve this contradiction and keeping feasibility to use monotonicity to prove facts, we need to be able to prove
that an AddRecExpr does not overflow even if the looop getBackedgeTakenCount iterations (EVEN if it is impossible
and we always exit by guard before it happens). You can think of it as "let us disable all side exit, actually make this
number of iterations and see if it is overflown".

This patch introduces a function that can be used to make this check.

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

6446

I'm not sure this is sound -- the backedge taken count you compute here can itself be dependent on the nuw/nsw flags, i.e. something like (this exact example may not work):

i = 300;
do {
  guard(i u< 900);
} while (++i u< 200);

In theory the add rec for i can be proved nuw based on the guard and that can be used to upper bound the ++i u< 200 trip count to ~0u - 300 since other i would have to unsigned overflow.

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

6446

I gave it some thought on the weekends, and the possibility of such situation also bugs me. Let me think of the alternative solution that doesn't use monotonicity to prove the fact that we have here.

[mkazantsev]

Not sure is it a bug or not, but I've found a better way to solve the problem. Abandoning in favor of patch https://reviews.llvm.org/D43759

include/llvm/Analysis/ScalarEvolution.h

const SCEV *getPredicatedBackedgeTakenCount(const Loop *L,
                                               SCEVUnionPredicate &Predicates);
 
   /// When successful, this returns a SCEVConstant that is greater than or equal
   /// to (i.e. a "conservative over-approximation") of the value returend by
   /// getBackedgeTakenCount.  If such a value cannot be computed, it returns the
   /// SCEVCouldNotCompute object.
   const SCEV *getMaxBackedgeTakenCount(const Loop *L);
 
+  /// Returns precise number of iterations which it takes for \p AR to reach the
+  /// bound of signed/unsigned range (which one is defined by \p Signed), or
+  /// SCEVCouldNotCompute if it fails to compute this number.
+  const SCEV *getNumberOfIterationsToLimit(const SCEVAddRecExpr *AR,
+                                           bool Signed);
+
+  /// Returns true if the \p AR does not have signed/unsigned wrap
+  /// (which one is defined by \p Signed) even if the loop exits by latch
+  /// condition and no abnormal exit is taken. In other words, that it does not
+  /// overflow if the loop makes the number of iterations returned by
+  /// getBackedgeTakenCount().
+  bool isProvedNoOverflowOnNormalExit(const SCEVAddRecExpr *AR, bool Signed);
+
   /// Return true if the backedge taken count is either the value returned by
   /// getMaxBackedgeTakenCount or zero.
   bool isBackedgeTakenCountMaxOrZero(const Loop *L);
 
   /// Return true if the specified loop has an analyzable loop-invariant
   /// backedge-taken count.
   bool hasLoopInvariantBackedgeTakenCount(const Loop *L);
 

lib/Analysis/ScalarEvolution.cpp

 }
 
 /// Similar to getBackedgeTakenCount, except return the least SCEV value that is
 /// known never to be less than the actual backedge taken count.
 const SCEV *ScalarEvolution::getMaxBackedgeTakenCount(const Loop *L) {
   return getBackedgeTakenInfo(L).getMax(this);
 }
 
+const SCEV *
+ScalarEvolution::getNumberOfIterationsToLimit(const SCEVAddRecExpr *AR,
+                                              bool Signed) {
+  unsigned BitWidth = getTypeSizeInBits(AR->getType());
+
+  // We assume that MinLimit <= Start <= MaxLimit (signed/unsigned comparison is
+  // defined by Signed flag), so (Maxlimit - Start) and (Start - MinLimit) can
+  // be interpreted as unsigned non-negative values.
+  const SCEV *Start = AR->getStart();
+  const SCEV *Step = AR->getStepRecurrence(*this);
+  if (!isAvailableAtLoopEntry(Step, AR->getLoop()))
+    return getCouldNotCompute();
+
+  // [LeftBorder, RightBorder] represent a range where the AR iterates without
+  // overflow.
+  const SCEV *LeftBorder = nullptr;
+  const SCEV *RightBorder = nullptr;
+  if (isKnownNegative(Step)) {
+    Step = getNegativeSCEV(Step);
+    LeftBorder = Signed ? getConstant(APInt::getSignedMinValue(BitWidth))
+                        : getConstant(APInt::getMinValue(BitWidth));
+    RightBorder = Start;
+  } else if (isKnownPositive(Step)) {
+    LeftBorder = Start;
+    RightBorder = Signed ? getConstant(APInt::getSignedMaxValue(BitWidth))
+                         : getConstant(APInt::getMaxValue(BitWidth));
+  } else
+    return getCouldNotCompute();
+
+  return getUDivExpr(getMinusSCEV(RightBorder, LeftBorder), Step);
+}
+
+bool ScalarEvolution::isProvedNoOverflowOnNormalExit(const SCEVAddRecExpr *AR,
+                                                     bool Signed) {
+  const Loop *L = AR->getLoop();
+  // The nsw/nuw flag for monotonicity could have been proved via some guard
+  // within the loop. Make sure that we do not actually overflow.
+  const SCEV *NumIters = getBackedgeTakenCount(L);
+  if (isa<SCEVCouldNotCompute>(NumIters))
+    return false;
+
+  const SCEV *ItersToLimit = getNumberOfIterationsToLimit(AR, Signed);
+  if (isa<SCEVCouldNotCompute>(ItersToLimit))
+    return false;
+
+  // Use the fact that we are in the loop to strip negative parts of ranges.
+  Type *WiderType = getWiderType(NumIters->getType(), ItersToLimit->getType());
+  auto StripOffNegativePart = [&](const SCEV *S) {
+    S = getNoopOrZeroExtend(S, WiderType);
+    const SCEV *Zero = getZero(WiderType);
+    if (isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SGE, S, Zero))
+      return getSMaxExpr(S, Zero);
+    return S;
+  };
+
+  return isLoopEntryGuardedByCond(L, ICmpInst::ICMP_ULE,
+                                  StripOffNegativePart(NumIters),
+                                  StripOffNegativePart(ItersToLimit));
+}
+
 bool ScalarEvolution::isBackedgeTakenCountMaxOrZero(const Loop *L) {
   return getBackedgeTakenInfo(L).isMaxOrZero(this);
 }
 
 /// Push PHI nodes in the header of the given loop onto the given Worklist.
 static void
 PushLoopPHIs(const Loop *L, SmallVectorImpl<Instruction *> &Worklist) {
   BasicBlock *Header = L->getHeader();

unittests/Analysis/ScalarEvolutionTest.cpp

TEST_F(ScalarEvolutionsTest, SCEVCacheNSW) {
   EXPECT_TRUE(isa<SCEVAddExpr>(SC1));
   // Expand for S1, it should use S1 not S2 in spite S2
   // first in the cache.
   SCEVExpander Exp(SE, M.getDataLayout(), "expander");
   auto *I = cast<Instruction>(Exp.expandCodeFor(SC1, nullptr, R));
   EXPECT_FALSE(I->hasNoSignedWrap());
 }
 
+// Make sure that SCEV correctly identifies which Phis cannot overflow on normal
+// exit. Loop with positive step.
+TEST_F(ScalarEvolutionsTest, SCEVNoOverflowOnNormalExitInc) {
+  /*
+   * Create the following code:
+   * func(i64 addrspace(10)* %arg)
+   * top:
+   *  br label %L.ph
+   * L.ph:
+   *  br label %L
+   * L:
+   *  %phi = phi i64 [ i64 0, %L.ph ], [ %add, %L2 ]
+   *  %iv1 = phi i64 [ i64 SINT_MIN ], [ i64 %iv1.inc ]        ; Does not wrap
+   *  %iv2 = phi i64 [ i64 SINT_MAX - 1000 ], [ i64 %iv2.inc ] ; Does not wrap
+   *  %iv3 = phi i64 [ i64 SINT_MAX - 999 ], [ i64 %iv3.inc ]  ; Wraps
+   *  %iv1.inc = add i64 %iv1, 1
+   *  %iv2.inc = add i64 %iv2, 1
+   *  %iv3.inc = add i64 %iv3, 1
+   *  %add = add i64 %phi2, 1
+   *  %cond = icmp slt i64 %phi, 1000.
+   *  br i1 %cond, label %post, label %L2
+   * post:
+   *  ret void
+   *
+   */
+
+  // Create a module with non-integral pointers in it's datalayout
+  Module NIM("nonintegral", Context);
+  std::string DataLayout = M.getDataLayoutStr();
+  if (!DataLayout.empty())
+    DataLayout += "-";
+  DataLayout += "ni:10";
+  NIM.setDataLayout(DataLayout);
+
+  Type *T_int64 = Type::getInt64Ty(Context);
+  Type *T_pint64 = T_int64->getPointerTo(10);
+
+  FunctionType *FTy =
+      FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false);
+  Function *F = cast<Function>(NIM.getOrInsertFunction("foo", FTy));
+
+  BasicBlock *Top = BasicBlock::Create(Context, "top", F);
+  BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F);
+  BasicBlock *L = BasicBlock::Create(Context, "L", F);
+  BasicBlock *Post = BasicBlock::Create(Context, "post", F);
+
+  IRBuilder<> Builder(Top);
+  Builder.CreateBr(LPh);
+
+  Builder.SetInsertPoint(LPh);
+  Builder.CreateBr(L);
+
+  Builder.SetInsertPoint(L);
+  PHINode *Phi = Builder.CreatePHI(T_int64, 2);
+  PHINode *IV1 = Builder.CreatePHI(T_int64, 2);
+  PHINode *IV2 = Builder.CreatePHI(T_int64, 2);
+  PHINode *IV3 = Builder.CreatePHI(T_int64, 2);
+
+  uint64_t Min = std::numeric_limits<int64_t>::min();
+  uint64_t Max = std::numeric_limits<int64_t>::max();
+
+  auto *Add = cast<Instruction>(
+      Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add"));
+  auto *IV1Inc = cast<Instruction>(
+      Builder.CreateAdd(IV1, ConstantInt::get(T_int64, 1), "inc"));
+  auto *IV2Inc = cast<Instruction>(
+      Builder.CreateAdd(IV2, ConstantInt::get(T_int64, 1), "inc"));
+  auto *IV3Inc = cast<Instruction>(
+      Builder.CreateAdd(IV3, ConstantInt::get(T_int64, 1), "inc"));
+  auto *Cond = cast<Instruction>(Builder.CreateICmp(
+      ICmpInst::ICMP_SLT, Phi, ConstantInt::get(T_int64, 1000), "cond"));
+  Builder.CreateCondBr(Cond, L, Post);
+
+  Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh);
+  Phi->addIncoming(Add, L);
+
+  IV1->addIncoming(ConstantInt::get(T_int64, Min), LPh);
+  IV2->addIncoming(ConstantInt::get(T_int64, Max - 1000), LPh);
+  IV3->addIncoming(ConstantInt::get(T_int64, Max - 999), LPh);
+
+  IV1->addIncoming(IV1Inc, L);
+  IV2->addIncoming(IV2Inc, L);
+  IV3->addIncoming(IV3Inc, L);
+
+  Builder.SetInsertPoint(Post);
+  Builder.CreateRetVoid();
+
+  ScalarEvolution SE = buildSE(*F);
+  auto *Loop = LI->getLoopFor(L);
+  const SCEV *EC = SE.getBackedgeTakenCount(Loop);
+  EXPECT_TRUE(isa<SCEVConstant>(EC));
+  EXPECT_EQ(1000u, cast<SCEVConstant>(EC)->getAPInt().getLimitedValue());
+  auto *AR1 = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(IV1));
+  auto *AR2 = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(IV2));
+  auto *AR3 = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(IV3));
+  EXPECT_NE(nullptr, AR1);
+  EXPECT_NE(nullptr, AR2);
+  EXPECT_NE(nullptr, AR3);
+  EXPECT_TRUE(SE.isProvedNoOverflowOnNormalExit(AR1, /* Signed */ true));
+  EXPECT_TRUE(SE.isProvedNoOverflowOnNormalExit(AR2, /* Signed */ true));
+  EXPECT_FALSE(SE.isProvedNoOverflowOnNormalExit(AR3, /* Signed */ true));
+  EXPECT_TRUE(SE.isProvedNoOverflowOnNormalExit(AR1, /* Signed */ false));
+  EXPECT_TRUE(SE.isProvedNoOverflowOnNormalExit(AR2, /* Signed */ false));
+  EXPECT_TRUE(SE.isProvedNoOverflowOnNormalExit(AR3, /* Signed */ false));
+}
+
+// Make sure that SCEV correctly identifies which Phis cannot overflow on normal
+// exit. Loop with negative step.
+TEST_F(ScalarEvolutionsTest, SCEVNoOverflowOnNormalExitDec) {
+  /*
+   * Create the following code:
+   * func(i64 addrspace(10)* %arg)
+   * top:
+   *  br label %L.ph
+   * L.ph:
+   *  br label %L
+   * L:
+   *  %phi = phi i64 [ i64 0, %L.ph ], [ %add, %L2 ]
+   *  %iv1 = phi i64 [ i64 SINT_MAX ], [ i64 %iv1.inc ]        ; Does not wrap
+   *  %iv2 = phi i64 [ i64 SINT_MIN + 1000 ], [ i64 %iv2.inc ] ; Does not wrap
+   *  %iv3 = phi i64 [ i64 SINT_MIN + 999 ], [ i64 %iv3.inc ]  ; Wraps
+   *  %iv1.inc = add i64 %iv1, -1
+   *  %iv2.inc = add i64 %iv2, -1
+   *  %iv3.inc = add i64 %iv3, -1
+   *  %add = add i64 %phi2, 1
+   *  %cond = icmp slt i64 %phi, 1000.
+   *  br i1 %cond, label %post, label %L2
+   * post:
+   *  ret void
+   *
+   */
+
+  // Create a module with non-integral pointers in it's datalayout
+  Module NIM("nonintegral", Context);
+  std::string DataLayout = M.getDataLayoutStr();
+  if (!DataLayout.empty())
+    DataLayout += "-";
+  DataLayout += "ni:10";
+  NIM.setDataLayout(DataLayout);
+
+  Type *T_int64 = Type::getInt64Ty(Context);
+  Type *T_pint64 = T_int64->getPointerTo(10);
+
+  FunctionType *FTy =
+      FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false);
+  Function *F = cast<Function>(NIM.getOrInsertFunction("foo", FTy));
+
+  BasicBlock *Top = BasicBlock::Create(Context, "top", F);
+  BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F);
+  BasicBlock *L = BasicBlock::Create(Context, "L", F);
+  BasicBlock *Post = BasicBlock::Create(Context, "post", F);
+
+  IRBuilder<> Builder(Top);
+  Builder.CreateBr(LPh);
+
+  Builder.SetInsertPoint(LPh);
+  Builder.CreateBr(L);
+
+  Builder.SetInsertPoint(L);
+  PHINode *Phi = Builder.CreatePHI(T_int64, 2);
+  PHINode *IV1 = Builder.CreatePHI(T_int64, 2);
+  PHINode *IV2 = Builder.CreatePHI(T_int64, 2);
+  PHINode *IV3 = Builder.CreatePHI(T_int64, 2);
+
+  uint64_t Min = std::numeric_limits<int64_t>::min();
+  uint64_t Max = std::numeric_limits<int64_t>::max();
+
+  auto *Add = cast<Instruction>(
+      Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add"));
+  auto *IV1Inc = cast<Instruction>(
+      Builder.CreateAdd(IV1, ConstantInt::get(T_int64, -1), "dec"));
+  auto *IV2Inc = cast<Instruction>(
+      Builder.CreateAdd(IV2, ConstantInt::get(T_int64, -1), "dec"));
+  auto *IV3Inc = cast<Instruction>(
+      Builder.CreateAdd(IV3, ConstantInt::get(T_int64, -1), "dec"));
+  auto *Cond = cast<Instruction>(Builder.CreateICmp(
+      ICmpInst::ICMP_SLT, Phi, ConstantInt::get(T_int64, 1000), "cond"));
+  Builder.CreateCondBr(Cond, L, Post);
+
+  Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh);
+  Phi->addIncoming(Add, L);
+
+  IV1->addIncoming(ConstantInt::get(T_int64, Max), LPh);
+  IV2->addIncoming(ConstantInt::get(T_int64, Min + 1000), LPh);
+  IV3->addIncoming(ConstantInt::get(T_int64, Min + 999), LPh);
+
+  IV1->addIncoming(IV1Inc, L);
+  IV2->addIncoming(IV2Inc, L);
+  IV3->addIncoming(IV3Inc, L);
+
+  Builder.SetInsertPoint(Post);
+  Builder.CreateRetVoid();
+
+  ScalarEvolution SE = buildSE(*F);
+  auto *Loop = LI->getLoopFor(L);
+  const SCEV *EC = SE.getBackedgeTakenCount(Loop);
+  EXPECT_TRUE(isa<SCEVConstant>(EC));
+  EXPECT_EQ(1000u, cast<SCEVConstant>(EC)->getAPInt().getLimitedValue());
+  auto *AR1 = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(IV1));
+  auto *AR2 = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(IV2));
+  auto *AR3 = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(IV3));
+  EXPECT_NE(nullptr, AR1);
+  EXPECT_NE(nullptr, AR2);
+  EXPECT_NE(nullptr, AR3);
+  EXPECT_TRUE(SE.isProvedNoOverflowOnNormalExit(AR1, /* Signed */ true));
+  EXPECT_TRUE(SE.isProvedNoOverflowOnNormalExit(AR2, /* Signed */ true));
+  EXPECT_FALSE(SE.isProvedNoOverflowOnNormalExit(AR3, /* Signed */ true));
+  EXPECT_TRUE(SE.isProvedNoOverflowOnNormalExit(AR1, /* Signed */ false));
+  EXPECT_TRUE(SE.isProvedNoOverflowOnNormalExit(AR2, /* Signed */ false));
+  EXPECT_TRUE(SE.isProvedNoOverflowOnNormalExit(AR3, /* Signed */ false));
+}
+
 }  // end anonymous namespace
 }  // end namespace llvm