[SCEV] Use context to strengthen flags of BinOps

[mkazantsev]

Summary

Sometimes SCEV cannot infer nuw/nsw from something as simple as

  len in [0, MAX_INT]
...
  iv = phi(0, iv.next)
  guard(iv <s len)
  guard(iv <u len)
  iv.next = iv + 1

just because flag strenthening only relies on definition and does not use local facts.
This patch adds support for the simplest case: inference of flags of add(x, constant)
if we can contextually prove that x <= max_int - constant.

In case if it has negative CT impact, there is an option to disable this logic. I woudln't
expect that though.

[nikic]

For reference, this is the compile-time impact on CTMark: http://llvm-compile-time-tracker.com/compare.php?from=42b3a5fb463fd616d981888abaf0f48ab0065a8d&to=990947a67d32b00d74fcccc2c12abe5a32945abc&stat=instructions

[mkazantsev]

If it's too bad we can have the option switched off by default. I was going to spend some time improving our context-based analyzes (looks like we do redundant traversal), but haven't done it yet.

[DaniilSuchkov]

The change seems reasonable.

One potentially concerning thing is if we start using context for inferring no-wrap flags, we theoretically can complete the "there's a check => doesn't overflow, doesn't overflow => doesn't need the check" circle. But even if we do, it seems, the problem would be on the side of the transformation, removing checks based on flags.

Please wait few more days and then feel free to land if no one objects.

[mkazantsev]

There is a subtlety between no-wrap flags in instructions and SCEVs. The short answer is - no, correct usage of SCEV should never lead to what you are describing. We had such bugs in the past because SCEV was misused.

[apilipenko]

llvm/lib/Analysis/ScalarEvolution.cpp

2330

Maybe add a comment explaining the pattern you are looking for here?

Something like: "We can prove that add(x, constant) doesn't wrap if isKnownPredicateAt can guarantee that x <= max_int - constant at the given context."

[mkazantsev]

It did show some CT drops, but I think the change is useful enough to have it. If not, let's consider switching the option off, but I would advice against that.

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
   /// No SCEV with operand V1, and v2 can exist in this program.
   bool instructionCouldExistWitthOperands(const SCEV *A, const SCEV *B);
 
   /// Return true if the SCEV is a scAddRecExpr or it contains
   /// scAddRecExpr. The result will be cached in HasRecMap.
   bool containsAddRecurrence(const SCEV *S);
 
   /// Is operation \p BinOp between \p LHS and \p RHS provably does not have
-  /// a signed/unsigned overflow (\p Signed)?
+  /// a signed/unsigned overflow (\p Signed)? If \p CtxI is specified, the
+  /// no-overflow fact should be true in the context of this instruction.
   bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed,
-                       const SCEV *LHS, const SCEV *RHS);
+                       const SCEV *LHS, const SCEV *RHS,
+                       const Instruction *CtxI = nullptr);
 
   /// Parse NSW/NUW flags from add/sub/mul IR binary operation \p Op into
   /// SCEV no-wrap flags, and deduce flag[s] that aren't known yet.
   /// Does not mutate the original instruction. Returns None if it could not
   /// deduce more precise flags than the instruction already has, otherwise
   /// returns proven flags.
   Optional<SCEV::NoWrapFlags>
   getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO);

llvm/lib/Analysis/ScalarEvolution.cpp

cl::desc("Maximum amount of nodes to process while searching SCEVUnknown "
              "Phi strongly connected components"),
     cl::init(8));
 
 static cl::opt<bool>
     EnableFiniteLoopControl("scalar-evolution-finite-loop", cl::Hidden,
                             cl::desc("Handle <= and >= in finite loops"),
                             cl::init(true));
 
+static cl::opt<bool> UseContextForNoWrapFlagInference(
+    "scalar-evolution-use-context-for-no-wrap-flag-strenghening", cl::Hidden,
+    cl::desc("Infer nuw/nsw flags using context where suitable"),
+    cl::init(true));
+
 //===----------------------------------------------------------------------===//
 //                           SCEV class definitions
 //===----------------------------------------------------------------------===//
 
 //===----------------------------------------------------------------------===//
 // Implementation of the SCEV class.
 //
 
if (Mul && isa<SCEVConstant>(Mul->getOperand(0))) {
       }
     }
   }
 
   return Interesting;
 }
 
 bool ScalarEvolution::willNotOverflow(Instruction::BinaryOps BinOp, bool Signed,
-                                      const SCEV *LHS, const SCEV *RHS) {
+                                      const SCEV *LHS, const SCEV *RHS,
+                                      const Instruction *CtxI) {
   const SCEV *(ScalarEvolution::*Operation)(const SCEV *, const SCEV *,
                                             SCEV::NoWrapFlags, unsigned);
   switch (BinOp) {
   default:
     llvm_unreachable("Unsupported binary op");
   case Instruction::Add:
     Operation = &ScalarEvolution::getAddExpr;
     break;
bool ScalarEvolution::willNotOverflow(Instruction::BinaryOps BinOp, bool Signed,
   auto *WideTy =
       IntegerType::get(NarrowTy->getContext(), NarrowTy->getBitWidth() * 2);
 
   const SCEV *A = (this->*Extension)(
       (this->*Operation)(LHS, RHS, SCEV::FlagAnyWrap, 0), WideTy, 0);
   const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
   const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
   const SCEV *B = (this->*Operation)(LHSB, RHSB, SCEV::FlagAnyWrap, 0);
-  return A == B;
+  if (A == B)
+    return true;
+  // Can we use context to prove the fact we need?
+  if (!CtxI)
+    return false;
+  // TODO: Support other operations.
+  if (BinOp != Instruction::Add)
+    return false;
+  auto *RHSC = dyn_cast<SCEVConstant>(RHS);
+  // TODO: Lift this limitation.
+  if (!RHSC)
+    return false;
+  APInt C = RHSC->getAPInt();
+  // TODO: Also lift this limitation.
+  if (Signed && C.isNegative())
+    return false;
+  unsigned NumBits = C.getBitWidth();
+  APInt Max =
+      Signed ? APInt::getSignedMaxValue(NumBits) : APInt::getMaxValue(NumBits);
+  APInt Limit = Max - C;
+  ICmpInst::Predicate Pred = Signed ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
+  return isKnownPredicateAt(Pred, LHS, getConstant(Limit), CtxI);
 }
 
 Optional<SCEV::NoWrapFlags>
 ScalarEvolution::getStrengthenedNoWrapFlagsFromBinOp(
     const OverflowingBinaryOperator *OBO) {
   // It cannot be done any better.
   if (OBO->hasNoUnsignedWrap() && OBO->hasNoSignedWrap())
     return None;
ScalarEvolution::getStrengthenedNoWrapFlagsFromBinOp(
   if (OBO->getOpcode() != Instruction::Add &&
       OBO->getOpcode() != Instruction::Sub &&
       OBO->getOpcode() != Instruction::Mul)
     return None;
 
   const SCEV *LHS = getSCEV(OBO->getOperand(0));
   const SCEV *RHS = getSCEV(OBO->getOperand(1));
 
+  const Instruction *CtxI =
+      UseContextForNoWrapFlagInference ? dyn_cast<Instruction>(OBO) : nullptr;
   if (!OBO->hasNoUnsignedWrap() &&
       willNotOverflow((Instruction::BinaryOps)OBO->getOpcode(),
-                      /* Signed */ false, LHS, RHS)) {
+                      /* Signed */ false, LHS, RHS, CtxI)) {
     Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
     Deduced = true;
   }
 
   if (!OBO->hasNoSignedWrap() &&
       willNotOverflow((Instruction::BinaryOps)OBO->getOpcode(),
-                      /* Signed */ true, LHS, RHS)) {
+                      /* Signed */ true, LHS, RHS, CtxI)) {
     Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW);
     Deduced = true;
   }
 
   if (Deduced)
     return Flags;
   return None;
 }

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

 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY:%.*]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[SUM_0:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i64 [[INDVARS_IV]], [[TMP0]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_END:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i64 [[INDVARS_IV]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[ARRAYIDX]], align 4
 ; CHECK-NEXT:    [[ADD]] = add nsw i32 [[SUM_0]], [[TMP1]]
-; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
 ; CHECK-NEXT:    br label [[FOR_COND]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    [[SUM_0_LCSSA:%.*]] = phi i32 [ [[SUM_0]], [[FOR_COND]] ]
 ; CHECK-NEXT:    ret i32 [[SUM_0_LCSSA]]
 ;
 entry:
   br label %for.cond
 

 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[TMP0]], [[FOR_COND_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY:%.*]] ]
 ; CHECK-NEXT:    [[SUM_0:%.*]] = phi i32 [ [[ADD:%.*]], [[FOR_BODY]] ], [ 0, [[FOR_COND_PREHEADER]] ]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i64 [[INDVARS_IV]], [[TMP1]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_END:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i64 [[INDVARS_IV]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* [[ARRAYIDX]], align 4
 ; CHECK-NEXT:    [[ADD]] = add nsw i32 [[SUM_0]], [[TMP2]]
-; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i64 0, [[INDVARS_IV_NEXT]]
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[FOR_COND]], label [[FOR_END]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    [[SUM_0_LCSSA:%.*]] = phi i32 [ [[SUM_0]], [[FOR_BODY]] ], [ [[SUM_0]], [[FOR_COND]] ]
 ; CHECK-NEXT:    ret i32 [[SUM_0_LCSSA]]
 ; CHECK:       leave:
 ; CHECK-NEXT:    ret i32 0
 ;

llvm/test/Transforms/IndVarSimplify/X86/iv-widen.ll

 define void @loop_0_dead(i32* %a) {
 ; CHECK-LABEL: @loop_0_dead(
 ; CHECK-NEXT:  Prologue:
 ; CHECK-NEXT:    br i1 undef, label [[B18_PREHEADER:%.*]], label [[B6:%.*]]
 ; CHECK:       B18.preheader:
 ; CHECK-NEXT:    br label [[B18:%.*]]
 ; CHECK:       B18:
 ; CHECK-NEXT:    [[DOT02:%.*]] = phi i32 [ [[TMP33:%.*]], [[B24:%.*]] ], [ 0, [[B18_PREHEADER]] ]
-; CHECK-NEXT:    [[TMP33]] = add nuw i32 [[DOT02]], 1
+; CHECK-NEXT:    [[TMP33]] = add nuw nsw i32 [[DOT02]], 1
 ; CHECK-NEXT:    [[O:%.*]] = getelementptr i32, i32* [[A:%.*]], i32 [[DOT02]]
 ; CHECK-NEXT:    [[V:%.*]] = load i32, i32* [[O]], align 4
 ; CHECK-NEXT:    [[T:%.*]] = icmp eq i32 [[V]], 0
 ; CHECK-NEXT:    br i1 [[T]], label [[EXIT24:%.*]], label [[B24]]
 ; CHECK:       B24:
 ; CHECK-NEXT:    [[T2:%.*]] = icmp eq i32 [[TMP33]], 20
 ; CHECK-NEXT:    br i1 [[T2]], label [[B6_LOOPEXIT:%.*]], label [[B18]]
 ; CHECK:       B6.loopexit:

 define void @loop_2(i32 %size, i32 %nsteps, i32 %hsize, i32* %lined, i8 %tmp1) {
 ; CHECK-LABEL: @loop_2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP215:%.*]] = icmp sgt i32 [[SIZE:%.*]], 1
 ; CHECK-NEXT:    [[BC0:%.*]] = bitcast i32* [[LINED:%.*]] to i8*
 ; CHECK-NEXT:    [[TMP0:%.*]] = sext i32 [[SIZE]] to i64
 ; CHECK-NEXT:    [[TMP1:%.*]] = sext i32 [[HSIZE:%.*]] to i64
 ; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[NSTEPS:%.*]], i32 1)
-; CHECK-NEXT:    [[WIDE_TRIP_COUNT11:%.*]] = zext i32 [[SMAX]] to i64
+; CHECK-NEXT:    [[WIDE_TRIP_COUNT14:%.*]] = zext i32 [[SMAX]] to i64
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
-; CHECK-NEXT:    [[INDVARS_IV7:%.*]] = phi i64 [ [[INDVARS_IV_NEXT8:%.*]], [[FOR_INC:%.*]] ], [ 0, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[TMP2:%.*]] = mul nsw i64 [[INDVARS_IV7]], [[TMP0]]
+; CHECK-NEXT:    [[INDVARS_IV9:%.*]] = phi i64 [ [[INDVARS_IV_NEXT10:%.*]], [[FOR_INC:%.*]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[TMP2:%.*]] = mul nsw i64 [[INDVARS_IV9]], [[TMP0]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = add nsw i64 [[TMP2]], [[TMP1]]
 ; CHECK-NEXT:    br i1 [[CMP215]], label [[FOR_BODY2_PREHEADER:%.*]], label [[FOR_INC]]
 ; CHECK:       for.body2.preheader:
 ; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[SIZE]] to i64
 ; CHECK-NEXT:    br label [[FOR_BODY2:%.*]]
 ; CHECK:       for.body2:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 1, [[FOR_BODY2_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY2]] ]
 ; CHECK-NEXT:    [[TMP4:%.*]] = add nsw i64 [[TMP3]], [[INDVARS_IV]]
 ; CHECK-NEXT:    [[ADD_PTR:%.*]] = getelementptr inbounds i8, i8* [[BC0]], i64 [[TMP4]]
 ; CHECK-NEXT:    store i8 [[TMP1:%.*]], i8* [[ADD_PTR]], align 1
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY2]], label [[FOR_BODY3_PREHEADER:%.*]]
 ; CHECK:       for.body3.preheader:
 ; CHECK-NEXT:    [[TMP5:%.*]] = trunc i64 [[TMP3]] to i32
 ; CHECK-NEXT:    [[TMP6:%.*]] = zext i32 [[TMP5]] to i64
-; CHECK-NEXT:    [[WIDE_TRIP_COUNT5:%.*]] = zext i32 [[SIZE]] to i64
+; CHECK-NEXT:    [[WIDE_TRIP_COUNT7:%.*]] = zext i32 [[SIZE]] to i64
 ; CHECK-NEXT:    br label [[FOR_BODY3:%.*]]
 ; CHECK:       for.body3:
-; CHECK-NEXT:    [[INDVARS_IV2:%.*]] = phi i64 [ 1, [[FOR_BODY3_PREHEADER]] ], [ [[INDVARS_IV_NEXT3:%.*]], [[FOR_BODY3]] ]
-; CHECK-NEXT:    [[TMP7:%.*]] = add nuw nsw i64 [[TMP6]], [[INDVARS_IV2]]
+; CHECK-NEXT:    [[INDVARS_IV3:%.*]] = phi i64 [ 1, [[FOR_BODY3_PREHEADER]] ], [ [[INDVARS_IV_NEXT4:%.*]], [[FOR_BODY3]] ]
+; CHECK-NEXT:    [[TMP7:%.*]] = add nuw nsw i64 [[TMP6]], [[INDVARS_IV3]]
 ; CHECK-NEXT:    [[ADD_PTR2:%.*]] = getelementptr inbounds i8, i8* [[BC0]], i64 [[TMP7]]
 ; CHECK-NEXT:    store i8 [[TMP1]], i8* [[ADD_PTR2]], align 1
-; CHECK-NEXT:    [[INDVARS_IV_NEXT3]] = add nuw nsw i64 [[INDVARS_IV2]], 1
-; CHECK-NEXT:    [[EXITCOND6:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT3]], [[WIDE_TRIP_COUNT5]]
-; CHECK-NEXT:    br i1 [[EXITCOND6]], label [[FOR_BODY3]], label [[FOR_INC_LOOPEXIT:%.*]]
+; CHECK-NEXT:    [[INDVARS_IV_NEXT4]] = add nuw nsw i64 [[INDVARS_IV3]], 1
+; CHECK-NEXT:    [[EXITCOND8:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT4]], [[WIDE_TRIP_COUNT7]]
+; CHECK-NEXT:    br i1 [[EXITCOND8]], label [[FOR_BODY3]], label [[FOR_INC_LOOPEXIT:%.*]]
 ; CHECK:       for.inc.loopexit:
 ; CHECK-NEXT:    br label [[FOR_INC]]
 ; CHECK:       for.inc:
-; CHECK-NEXT:    [[INDVARS_IV_NEXT8]] = add nuw nsw i64 [[INDVARS_IV7]], 1
-; CHECK-NEXT:    [[EXITCOND12:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT8]], [[WIDE_TRIP_COUNT11]]
-; CHECK-NEXT:    br i1 [[EXITCOND12]], label [[FOR_BODY]], label [[FOR_END_LOOPEXIT:%.*]]
+; CHECK-NEXT:    [[INDVARS_IV_NEXT10]] = add nuw nsw i64 [[INDVARS_IV9]], 1
+; CHECK-NEXT:    [[EXITCOND15:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT10]], [[WIDE_TRIP_COUNT14]]
+; CHECK-NEXT:    br i1 [[EXITCOND15]], label [[FOR_BODY]], label [[FOR_END_LOOPEXIT:%.*]]
 ; CHECK:       for.end.loopexit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %cmp215 = icmp sgt i32 %size, 1
   %bc0 = bitcast i32* %lined to i8*
   br label %for.body
 

llvm/test/Transforms/IndVarSimplify/X86/pr35406.ll

 ; CHECK-NEXT:    br label [[LOOP1:%.*]]
 ; CHECK:       loop1:
 ; CHECK-NEXT:    [[LOCAL_0_:%.*]] = phi i32 [ 8, [[ENTRY:%.*]] ], [ [[I9:%.*]], [[LOOP2_EXIT:%.*]] ]
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[LOCAL_0_]], 15
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[EXIT:%.*]], label [[GENERAL_CASE24:%.*]]
 ; CHECK:       general_case24:
 ; CHECK-NEXT:    br i1 false, label [[LOOP2_PREHEADER:%.*]], label [[LOOP2_EXIT]]
 ; CHECK:       loop2.preheader:
-; CHECK-NEXT:    [[TMP0:%.*]] = udiv i32 14, [[LOCAL_0_]]
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i32 60392, [[TMP0]]
-; CHECK-NEXT:    [[TMP2:%.*]] = mul i32 [[TMP1]], -1
-; CHECK-NEXT:    [[TMP3:%.*]] = mul i32 [[TMP2]], [[TMP0]]
-; CHECK-NEXT:    [[TMP4:%.*]] = sext i32 [[TMP3]] to i64
-; CHECK-NEXT:    [[TMP5:%.*]] = add nsw i64 [[TMP4]], 60392
 ; CHECK-NEXT:    br label [[LOOP2:%.*]]
 ; CHECK:       loop2:
-; CHECK-NEXT:    [[INDVARS_IV_NEXT:%.*]] = add nsw i64 [[TMP5]], -1
 ; CHECK-NEXT:    [[I4:%.*]] = load atomic i64, i64* [[P1:%.*]] unordered, align 8
-; CHECK-NEXT:    [[I6:%.*]] = sub i64 [[I4]], [[INDVARS_IV_NEXT]]
+; CHECK-NEXT:    [[I6:%.*]] = sub i64 [[I4]], -1
 ; CHECK-NEXT:    store atomic i64 [[I6]], i64* [[P1]] unordered, align 8
 ; CHECK-NEXT:    br i1 true, label [[LOOP2_EXIT_LOOPEXIT:%.*]], label [[LOOP2]]
 ; CHECK:       loop2.exit.loopexit:
 ; CHECK-NEXT:    br label [[LOOP2_EXIT]]
 ; CHECK:       loop2.exit:
 ; CHECK-NEXT:    [[I9]] = add nuw nsw i32 [[LOCAL_0_]], 1
 ; CHECK-NEXT:    br i1 false, label [[EXIT]], label [[LOOP1]]
 ; CHECK:       exit:

llvm/test/Transforms/IndVarSimplify/bbi-63564.ll

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_COND:%.*]]
 ; CHECK:       for.cond:
 ; CHECK-NEXT:    br i1 false, label [[FOR_BODY:%.*]], label [[FOR_END4:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    br label [[FOR_BODY2:%.*]]
 ; CHECK:       for.body2:
 ; CHECK-NEXT:    [[INC2:%.*]] = phi i16 [ undef, [[FOR_BODY]] ], [ [[INC:%.*]], [[FOR_BODY2]] ]
-; CHECK-NEXT:    [[INC]] = add nsw i16 [[INC2]], 1
+; CHECK-NEXT:    [[INC]] = add nuw nsw i16 [[INC2]], 1
 ; CHECK-NEXT:    store i16 [[INC]], i16* undef, align 1
 ; CHECK-NEXT:    br i1 true, label [[FOR_BODY2]], label [[CRIT_EDGE:%.*]]
 ; CHECK:       crit_edge:
 ; CHECK-NEXT:    [[INC_LCSSA:%.*]] = phi i16 [ [[INC]], [[FOR_BODY2]] ]
 ; CHECK-NEXT:    store i16 [[INC_LCSSA]], i16* @a, align 1
 ; CHECK-NEXT:    unreachable
 ; CHECK:       for.end4:
 ; CHECK-NEXT:    ret void

llvm/test/Transforms/IndVarSimplify/cycled_phis.ll

 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[PREHEADER]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[SIGNED_CMP:%.*]] = icmp slt i32 [[IV]], [[LEN]]
 ; CHECK-NEXT:    br i1 [[SIGNED_CMP]], label [[SIGNED_PASSED:%.*]], label [[FAILED_SIGNED:%.*]]
 ; CHECK:       signed.passed:
 ; CHECK-NEXT:    [[UNSIGNED_CMP:%.*]] = icmp ult i32 [[IV]], [[LEN]]
 ; CHECK-NEXT:    br i1 [[UNSIGNED_CMP]], label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]]
 ; CHECK:       backedge:
-; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[DONE:%.*]]
 ; CHECK:       failed.signed:
 ; CHECK-NEXT:    call void @fail(i32 1)
 ; CHECK-NEXT:    unreachable
 ; CHECK:       failed.unsigned:
 ; CHECK-NEXT:    call void @fail(i32 2)
 ; CHECK-NEXT:    unreachable

 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[SIBLING_IV_NEXT_LCSSA]], [[PREHEADER]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[SIGNED_CMP:%.*]] = icmp slt i32 [[IV]], [[LEN]]
 ; CHECK-NEXT:    br i1 [[SIGNED_CMP]], label [[SIGNED_PASSED:%.*]], label [[FAILED_SIGNED:%.*]]
 ; CHECK:       signed.passed:
 ; CHECK-NEXT:    [[UNSIGNED_CMP:%.*]] = icmp ult i32 [[IV]], [[LEN]]
 ; CHECK-NEXT:    br i1 [[UNSIGNED_CMP]], label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]]
 ; CHECK:       backedge:
-; CHECK-NEXT:    [[IV_NEXT]] = add nuw i32 [[IV]], 1
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[DONE:%.*]]
 ; CHECK:       failed.signed:
 ; CHECK-NEXT:    call void @fail(i32 1)
 ; CHECK-NEXT:    unreachable
 ; CHECK:       failed.unsigned:
 ; CHECK-NEXT:    call void @fail(i32 2)
 ; CHECK-NEXT:    unreachable

 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[SIBLING_IV_NEXT_TRUNC]], [[PREHEADER]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[SIGNED_CMP:%.*]] = icmp ult i32 [[IV]], [[LEN]]
 ; CHECK-NEXT:    br i1 [[SIGNED_CMP]], label [[SIGNED_PASSED:%.*]], label [[FAILED_SIGNED:%.*]]
 ; CHECK:       signed.passed:
 ; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]]
 ; CHECK:       backedge:
-; CHECK-NEXT:    [[IV_NEXT]] = add nuw i32 [[IV]], 1
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[DONE:%.*]]
 ; CHECK:       failed.signed:
 ; CHECK-NEXT:    call void @fail(i32 1)
 ; CHECK-NEXT:    unreachable
 ; CHECK:       failed.unsigned:
 ; CHECK-NEXT:    call void @fail(i32 2)
 ; CHECK-NEXT:    unreachable

 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_START]], [[PREHEADER]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[SIGNED_CMP:%.*]] = icmp slt i32 [[IV]], [[LEN]]
 ; CHECK-NEXT:    br i1 [[SIGNED_CMP]], label [[SIGNED_PASSED:%.*]], label [[FAILED_SIGNED:%.*]]
 ; CHECK:       signed.passed:
 ; CHECK-NEXT:    [[UNSIGNED_CMP:%.*]] = icmp ult i32 [[IV]], [[LEN]]
 ; CHECK-NEXT:    br i1 [[UNSIGNED_CMP]], label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]]
 ; CHECK:       backedge:
-; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[OUTER_LOOP_BACKEDGE]]
 ; CHECK:       outer.loop.backedge:
 ; CHECK-NEXT:    [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    [[OUTER_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[OUTER_COND]], label [[OUTER_LOOP]], label [[DONE:%.*]]
 ; CHECK:       failed.signed:

 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_START]], [[PREHEADER]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[SIGNED_CMP:%.*]] = icmp slt i32 [[IV]], [[LEN]]
 ; CHECK-NEXT:    br i1 [[SIGNED_CMP]], label [[SIGNED_PASSED:%.*]], label [[FAILED_SIGNED:%.*]]
 ; CHECK:       signed.passed:
 ; CHECK-NEXT:    [[UNSIGNED_CMP:%.*]] = icmp ult i32 [[IV]], [[LEN]]
 ; CHECK-NEXT:    br i1 [[UNSIGNED_CMP]], label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]]
 ; CHECK:       backedge:
-; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[OUTER_LOOP_SELECTION:%.*]]
 ; CHECK:       outer.loop.selection:
 ; CHECK-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    [[SWITCH_COND:%.*]] = call i32 @switch.cond()
 ; CHECK-NEXT:    switch i32 [[SWITCH_COND]], label [[TAKE_SAME:%.*]] [
 ; CHECK-NEXT:    i32 1, label [[TAKE_INCREMENT:%.*]]

llvm/test/Transforms/IndVarSimplify/eliminate-comparison.ll

 ; CHECK-NEXT:    [[VAR_0]] = add nsw i32 [[VAR_0_IN]], -1
 ; CHECK-NEXT:    br i1 true, label [[STAY:%.*]], label [[BB2_LOOPEXIT:%.*]]
 ; CHECK:       stay:
 ; CHECK-NEXT:    [[TMP25:%.*]] = getelementptr inbounds i16, i16* [[TMP20:%.*]], i32 [[VAR_1]]
 ; CHECK-NEXT:    [[TMP26:%.*]] = load i16, i16* [[TMP25]], align 2
 ; CHECK-NEXT:    [[TMP29:%.*]] = icmp eq i16 [[TMP26]], 0
 ; CHECK-NEXT:    br i1 [[TMP29]], label [[BB1]], label [[BB2_LOOPEXIT]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    [[TMP30]] = add nuw i32 [[VAR_1]], 1
+; CHECK-NEXT:    [[TMP30]] = add nuw nsw i32 [[VAR_1]], 1
 ; CHECK-NEXT:    [[TMP31:%.*]] = icmp eq i32 [[VAR_0]], 0
 ; CHECK-NEXT:    br i1 [[TMP31]], label [[BB3:%.*]], label [[BB0]]
 ; CHECK:       bb2.loopexit:
 ; CHECK-NEXT:    br label [[BB2]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    ret i1 false
 ; CHECK:       bb3:
 ; CHECK-NEXT:    ret i1 true

 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[C1:%.*]] = icmp slt i32 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[C1]], label [[CHECKED_1:%.*]], label [[FAIL:%.*]]
 ; CHECK:       checked.1:
 ; CHECK-NEXT:    br i1 true, label [[CHECKED_2:%.*]], label [[FAIL]]
 ; CHECK:       checked.2:
 ; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL]]
 ; CHECK:       backedge:
-; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 758394
+; CHECK-NEXT:    [[IV_NEXT]] = add nsw i32 [[IV]], 758394
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond_func()
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       fail:
 ; CHECK-NEXT:    unreachable
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA1:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA1]]
 ;

 ; CHECK-NEXT:    [[C2:%.*]] = icmp slt i32 [[IV]], 1
 ; CHECK-NEXT:    [[C3:%.*]] = icmp slt i32 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[C1]], label [[CHECKED_1:%.*]], label [[FAIL:%.*]]
 ; CHECK:       checked.1:
 ; CHECK-NEXT:    br i1 [[C2]], label [[CHECKED_2:%.*]], label [[FAIL]]
 ; CHECK:       checked.2:
 ; CHECK-NEXT:    br i1 [[C3]], label [[BACKEDGE]], label [[FAIL]]
 ; CHECK:       backedge:
-; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 758394
+; CHECK-NEXT:    [[IV_NEXT]] = add nsw i32 [[IV]], 758394
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond_func()
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       fail:
 ; CHECK-NEXT:    unreachable
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA1:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA1]]
 ;

llvm/test/Transforms/IndVarSimplify/finite-exit-comparisons.ll

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[IN_RANGE:%.*]] = icmp ult i16 [[N:%.*]], 256
 ; CHECK-NEXT:    br i1 [[IN_RANGE]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_END:%.*]]
 ; CHECK:       for.body.preheader:
 ; CHECK-NEXT:    [[TMP0:%.*]] = trunc i16 [[N]] to i8
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ [[IV_NEXT:%.*]], [[FOR_BODY]] ], [ 0, [[FOR_BODY_PREHEADER]] ]
-; CHECK-NEXT:    [[IV_NEXT]] = add i8 [[IV]], 1
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw i8 [[IV]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[IV_NEXT]], [[TMP0]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_END_LOOPEXIT:%.*]]
 ; CHECK:       for.end.loopexit:
 ; CHECK-NEXT:    br label [[FOR_END]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    ret void
 ;
 entry:

llvm/test/Transforms/IndVarSimplify/loop-predication.ll

 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED:%.*]] ], [ 400, [[LOOP_PREHEADER:%.*]] ]
 ; CHECK-NEXT:    [[WITHIN_BOUNDS:%.*]] = icmp ult i32 [[I]], [[LENGTH:%.*]]
 ; CHECK-NEXT:    br i1 [[WITHIN_BOUNDS]], label [[GUARDED]], label [[DEOPT:%.*]], !prof [[PROF0]]
 ; CHECK:       deopt:
 ; CHECK-NEXT:    call void @prevent_merging()
 ; CHECK-NEXT:    ret i32 -1
 ; CHECK:       guarded:
 ; CHECK-NEXT:    store volatile i32 0, i32* [[A:%.*]], align 4
-; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
+; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
 ; CHECK-NEXT:    br label [[LOOP]]
 ;
 loop.preheader:
   br label %loop
 
 loop:                                             ; preds = %guarded, %loop.preheader
   %i = phi i32 [ %i.next, %guarded ], [ 400, %loop.preheader ]
   %within.bounds = icmp ult i32 %i, %length

llvm/test/Transforms/IndVarSimplify/trivial-guard.ll

 ; CHECK-NEXT:    br label [[LOOP_2:%.*]]
 ; CHECK:       loop.1.preheader:
 ; CHECK-NEXT:    br label [[LOOP_1:%.*]]
 ; CHECK:       loop.1:
 ; CHECK-NEXT:    [[IV_1:%.*]] = phi i32 [ [[IV_NEXT_1:%.*]], [[GUARDED_1:%.*]] ], [ 0, [[LOOP_1_PREHEADER]] ]
 ; CHECK-NEXT:    [[CHECK_1:%.*]] = icmp slt i32 [[IV_1]], [[X:%.*]]
 ; CHECK-NEXT:    br i1 [[CHECK_1]], label [[GUARDED_1]], label [[FAIL_LOOPEXIT:%.*]]
 ; CHECK:       guarded.1:
-; CHECK-NEXT:    [[IV_NEXT_1]] = add nuw i32 [[IV_1]], 1
+; CHECK-NEXT:    [[IV_NEXT_1]] = add nuw nsw i32 [[IV_1]], 1
 ; CHECK-NEXT:    [[LOOP_COND_1:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[LOOP_COND_1]], label [[LOOP_1]], label [[EXIT_LOOPEXIT:%.*]]
 ; CHECK:       loop.2:
 ; CHECK-NEXT:    br i1 true, label [[GUARDED_2:%.*]], label [[FAIL_LOOPEXIT1:%.*]]
 ; CHECK:       guarded.2:
 ; CHECK-NEXT:    [[LOOP_COND_2:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[LOOP_COND_2]], label [[LOOP_2]], label [[EXIT_LOOPEXIT2:%.*]]
 ; CHECK:       exit.loopexit:

 ; CHECK:       guarded.1:
 ; CHECK-NEXT:    [[LOOP_COND_1:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[LOOP_COND_1]], label [[LOOP_1]], label [[EXIT_LOOPEXIT:%.*]]
 ; CHECK:       loop.2:
 ; CHECK-NEXT:    [[IV_2:%.*]] = phi i32 [ [[IV_NEXT_2:%.*]], [[GUARDED_2:%.*]] ], [ 0, [[LOOP_2_PREHEADER]] ]
 ; CHECK-NEXT:    [[CHECK_2:%.*]] = icmp slt i32 [[IV_2]], [[X:%.*]]
 ; CHECK-NEXT:    br i1 [[CHECK_2]], label [[GUARDED_2]], label [[FAIL_LOOPEXIT1:%.*]]
 ; CHECK:       guarded.2:
-; CHECK-NEXT:    [[IV_NEXT_2]] = add nuw i32 [[IV_2]], 1
+; CHECK-NEXT:    [[IV_NEXT_2]] = add nuw nsw i32 [[IV_2]], 1
 ; CHECK-NEXT:    [[LOOP_COND_2:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[LOOP_COND_2]], label [[LOOP_2]], label [[EXIT_LOOPEXIT2:%.*]]
 ; CHECK:       exit.loopexit:
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit.loopexit2:
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void

llvm/test/Transforms/LoopUnroll/runtime-loop-multiple-exits.ll

 ; EPILOG-NEXT:    %cmp1.6 = icmp ult i32 %inc.6, %N
 ; EPILOG-NEXT:    br i1 %cmp1.6, label %latch.6, label %latchExit.epilog-lcssa.loopexit
 ; EPILOG:       latch.6:
 ; EPILOG-NEXT:    %niter.next.6 = add nuw nsw i32 %niter.next.5, 1
 ; EPILOG-NEXT:    %inc.7 = add nuw i32 %inc.6, 1
 ; EPILOG-NEXT:    %cmp1.7 = icmp ult i32 %inc.7, %N
 ; EPILOG-NEXT:    br i1 %cmp1.7, label %latch.7, label %latchExit.epilog-lcssa.loopexit
 ; EPILOG:       latch.7:
-; EPILOG-NEXT:    %niter.next.7 = add i32 %niter.next.6, 1
+; EPILOG-NEXT:    %niter.next.7 = add nuw i32 %niter.next.6, 1
 ; EPILOG-NEXT:    %niter.ncmp.7 = icmp ne i32 %niter.next.7, %unroll_iter
 ; EPILOG-NEXT:    br i1 %niter.ncmp.7, label %header, label %latchExit.unr-lcssa.loopexit
 ; EPILOG:       latchExit.unr-lcssa.loopexit:
 ; EPILOG-NEXT:    %i2.ph.ph.ph = phi i32 [ -1, %latch.7 ]
 ; EPILOG-NEXT:    %i4.unr.ph = phi i32 [ %inc.7, %latch.7 ]
 ; EPILOG-NEXT:    br label %latchExit.unr-lcssa
 ; EPILOG:       latchExit.unr-lcssa:
 ; EPILOG-NEXT:    %i2.ph.ph = phi i32 [ undef, %preheader ], [ %i2.ph.ph.ph, %latchExit.unr-lcssa.loopexit ]

 ; EPILOG-BLOCK-NEXT:    %cmp1 = icmp ult i32 %inc, %N
 ; EPILOG-BLOCK-NEXT:    br i1 %cmp1, label %latch, label %latchExit.epilog-lcssa.loopexit
 ; EPILOG-BLOCK:       latch:
 ; EPILOG-BLOCK-NEXT:    %niter.next = add nuw nsw i32 %niter, 1
 ; EPILOG-BLOCK-NEXT:    %inc.1 = add nuw i32 %inc, 1
 ; EPILOG-BLOCK-NEXT:    %cmp1.1 = icmp ult i32 %inc.1, %N
 ; EPILOG-BLOCK-NEXT:    br i1 %cmp1.1, label %latch.1, label %latchExit.epilog-lcssa.loopexit
 ; EPILOG-BLOCK:       latch.1:
-; EPILOG-BLOCK-NEXT:    %niter.next.1 = add i32 %niter.next, 1
+; EPILOG-BLOCK-NEXT:    %niter.next.1 = add nuw i32 %niter.next, 1
 ; EPILOG-BLOCK-NEXT:    %niter.ncmp.1 = icmp ne i32 %niter.next.1, %unroll_iter
 ; EPILOG-BLOCK-NEXT:    br i1 %niter.ncmp.1, label %header, label %latchExit.unr-lcssa.loopexit, !llvm.loop !8
 ; EPILOG-BLOCK:       latchExit.unr-lcssa.loopexit:
 ; EPILOG-BLOCK-NEXT:    %i2.ph.ph.ph = phi i32 [ -1, %latch.1 ]
 ; EPILOG-BLOCK-NEXT:    %i4.unr.ph = phi i32 [ %inc.1, %latch.1 ]
 ; EPILOG-BLOCK-NEXT:    br label %latchExit.unr-lcssa
 ; EPILOG-BLOCK:       latchExit.unr-lcssa:
 ; EPILOG-BLOCK-NEXT:    %i2.ph.ph = phi i32 [ undef, %preheader ], [ %i2.ph.ph.ph, %latchExit.unr-lcssa.loopexit ]