[SCCP] Use range info to prove AddInst has NUW flag.

[fhahn]

Summary

This patch updates SCCP to use the value ranges of AddInst operands to
try to prove the AddInst does not overflow in the unsigned sense and
adds the NUW flag. The reasoning is done with
makeGuaranteedNoWrapRegion (thanks @nikic for point it out!).

Follow-ups will include adding NSW and extension to more
OverflowingBinaryOperators.

[nikic]

llvm/lib/Transforms/Utils/SCCPSolver.cpp

180

Why is this needed?

190

There is an SCCPInstVisitor::getConstantRange() helper -- probably that should be moved to SCCPSolver and reused here?

196

Should be RangeB. Doesn't make a difference for add, but would be wrong when extending to sub.

[fhahn]

Address comments, thanks!

[fhahn]

llvm/lib/Transforms/Utils/SCCPSolver.cpp

180

It's not needed in the latest version, originally this was to exclude vector constants. Removed, thanks!

190

probably that should be moved to SCCPSolver and reused here?

I just made it a standalone static function

196

Flipped Ranges, thanks!

[nikic]

LGTM apart from the one note.

llvm/lib/Transforms/Utils/SCCPSolver.cpp

191

This should be guarded under if (!Inst.hasNoUnsignedWrap()). Otherwise we will report an unnecessary change.

[fhahn]

llvm/lib/Transforms/Utils/SCCPSolver.cpp

191

Thanks, changed to if (!Inst.hasNoUnsignedWrap() &&NUWRange.contains(RangeA)). Could also have a separate check guarding makeGuaranteedNoWrapRegion, which would increase nesting though and hopefully existing compilers should be smart enough to delay the computation :)

[nikic]

llvm/lib/Transforms/Utils/SCCPSolver.cpp

191

Existing compilers almost certainly can't delay that computation (it's not LLVM_READONLY, and I'm not sure clang would sink the call even then).

[dyung]

@fhahn this change was causing many of our internal tests to hit an assertion failure which I bisected back to your change. I've filed issue #60280 with a repro. Can you take a look?

I've reverted the change so that it doesn't go into the release branch if you don't have a chance to fix it first.

[mstorsjo]

In D142387#4079082, @dyung wrote:

@fhahn this change was causing many of our internal tests to hit an assertion failure which I bisected back to your change. I've filed issue #60280 with a repro. Can you take a look?

I've reverted the change so that it doesn't go into the release branch if you don't have a chance to fix it first.

Thanks for the revert! I also ran into this, and bisected the issue back to this commit.

[fhahn]

Thanks for the reports and revert! Should be fixed in the recommitted version.

llvm/lib/Transforms/Utils/SCCPSolver.cpp

191

Fair point, I was assuming it at least to get inlined, but then realized that it is not even defined in the header....

Updated in the recommitted version.

llvm/lib/Transforms/Utils/SCCPSolver.cpp

 static const unsigned MaxNumRangeExtensions = 10;
 
 /// Returns MergeOptions with MaxWidenSteps set to MaxNumRangeExtensions.
 static ValueLatticeElement::MergeOptions getMaxWidenStepsOpts() {
   return ValueLatticeElement::MergeOptions().setMaxWidenSteps(
       MaxNumRangeExtensions);
 }
 
+static ConstantRange getConstantRange(const ValueLatticeElement &LV, Type *Ty,
+                                      bool UndefAllowed = true) {
+  assert(Ty->isIntOrIntVectorTy() && "Should be int or int vector");
+  if (LV.isConstantRange(UndefAllowed))
+    return LV.getConstantRange();
+  return ConstantRange::getFull(Ty->getScalarSizeInBits());
+}
+
 namespace llvm {
 
 bool SCCPSolver::isConstant(const ValueLatticeElement &LV) {
   return LV.isConstant() ||
          (LV.isConstantRange() && LV.getConstantRange().isSingleElement());
 }
 
 bool SCCPSolver::isOverdefined(const ValueLatticeElement &LV) {
bool SCCPSolver::tryToReplaceWithConstant(Value *V) {
 
   LLVM_DEBUG(dbgs() << "  Constant: " << *Const << " = " << *V << '\n');
 
   // Replaces all of the uses of a variable with uses of the constant.
   V->replaceAllUsesWith(Const);
   return true;
 }
 
-/// Try to replace signed instructions with their unsigned equivalent.
-static bool replaceSignedInst(SCCPSolver &Solver,
+/// Try to replace refine \p Inst with information of its value ranges from \p
+/// Solver. For example, SExts are replaced by ZExt, if the value range of the
+/// result is non-negative.
+static bool refineInstruction(SCCPSolver &Solver,
                               SmallPtrSetImpl<Value *> &InsertedValues,
                               Instruction &Inst) {
   // Determine if a signed value is known to be >= 0.
   auto isNonNegative = [&Solver](Value *V) {
     // If this value was constant-folded, it may not have a solver entry.
     // Handle integers. Otherwise, return false.
     if (auto *C = dyn_cast<Constant>(V)) {
       auto *CInt = dyn_cast<ConstantInt>(C);
case Instruction::SRem: {
     if (InsertedValues.count(Op0) || InsertedValues.count(Op1) ||
         !isNonNegative(Op0) || !isNonNegative(Op1))
       return false;
     auto NewOpcode = Inst.getOpcode() == Instruction::SDiv ? Instruction::UDiv
                                                            : Instruction::URem;
     NewInst = BinaryOperator::Create(NewOpcode, Op0, Op1, "", &Inst);
     break;
   }
+  case Instruction::Add: {
+    auto GetRange = [&Solver, &InsertedValues](Value *Op) {
+      unsigned Bitwidth = Op->getType()->getScalarSizeInBits();
+      if (InsertedValues.contains(Op) || isa<UndefValue>(Op))
+        return ConstantRange::getFull(Bitwidth);
+      if (auto *Const = dyn_cast<ConstantInt>(Op))
+        return ConstantRange(Const->getValue());
+
+      return getConstantRange(Solver.getLatticeValueFor(Op), Op->getType(),
+                              /*UndefAllowed=*/false);
+    };
+
+    auto RangeA = GetRange(Inst.getOperand(0));
+    auto RangeB = GetRange(Inst.getOperand(1));
+    auto NUWRange = ConstantRange::makeGuaranteedNoWrapRegion(
+        Instruction::Add, RangeB, OverflowingBinaryOperator::NoUnsignedWrap);
+    if (!Inst.hasNoUnsignedWrap() && NUWRange.contains(RangeA)) {
+      Inst.setHasNoUnsignedWrap();
+      return true;
+    }
+
+    return false;
+  }
   default:
     return false;
   }
 
   // Wire up the new instruction and update state.
   assert(NewInst && "Expected replacement instruction");
   NewInst->takeName(&Inst);
   InsertedValues.insert(NewInst);
for (Instruction &Inst : make_early_inc_range(BB)) {
     if (Inst.getType()->isVoidTy())
       continue;
     if (tryToReplaceWithConstant(&Inst)) {
       if (canRemoveInstruction(&Inst))
         Inst.eraseFromParent();
 
       MadeChanges = true;
       ++InstRemovedStat;
-    } else if (replaceSignedInst(*this, InsertedValues, Inst)) {
+    } else if (refineInstruction(*this, InsertedValues, Inst)) {
       MadeChanges = true;
       ++InstReplacedStat;
     }
   }
   return MadeChanges;
 }
 
 bool SCCPSolver::removeNonFeasibleEdges(BasicBlock *BB, DomTreeUpdater &DTU,
if (auto *STy = dyn_cast<StructType>(V->getType()))
         markOverdefined(getStructValueState(V, i), V);
     else
       markOverdefined(ValueState[V], V);
   }
 
   bool isStructLatticeConstant(Function *F, StructType *STy);
 
   Constant *getConstant(const ValueLatticeElement &LV) const;
-  ConstantRange getConstantRange(const ValueLatticeElement &LV, Type *Ty) const;
 
   SmallPtrSetImpl<Function *> &getArgumentTrackedFunctions() {
     return TrackingIncomingArguments;
   }
 
   void markArgInFuncSpecialization(Function *F,
                                    const SmallVectorImpl<ArgInfo> &Args);
 
Constant *SCCPInstVisitor::getConstant(const ValueLatticeElement &LV) const {
   if (LV.isConstantRange()) {
     const auto &CR = LV.getConstantRange();
     if (CR.getSingleElement())
       return ConstantInt::get(Ctx, *CR.getSingleElement());
   }
   return nullptr;
 }
 
-ConstantRange
-SCCPInstVisitor::getConstantRange(const ValueLatticeElement &LV,
-                                  Type *Ty) const {
-  assert(Ty->isIntOrIntVectorTy() && "Should be int or int vector");
-  if (LV.isConstantRange())
-    return LV.getConstantRange();
-  return ConstantRange::getFull(Ty->getScalarSizeInBits());
-}
-
 void SCCPInstVisitor::markArgInFuncSpecialization(
     Function *F, const SmallVectorImpl<ArgInfo> &Args) {
   assert(!Args.empty() && "Specialization without arguments");
   assert(F->arg_size() == Args[0].Formal->getParent()->arg_size() &&
          "Functions should have the same number of arguments");
 
   auto Iter = Args.begin();
   Argument *NewArg = F->arg_begin();

llvm/test/Transforms/SCCP/add-nuw-nsw-flags.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=ipsccp -S %s | FileCheck %s
 
 define i8 @range_from_lshr(i8 %a) {
 ; CHECK-LABEL: @range_from_lshr(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A_SHR:%.*]] = lshr i8 [[A:%.*]], 1
-; CHECK-NEXT:    [[ADD_1:%.*]] = add i8 [[A_SHR]], 1
-; CHECK-NEXT:    [[ADD_2:%.*]] = add i8 [[A_SHR]], -128
+; CHECK-NEXT:    [[ADD_1:%.*]] = add nuw i8 [[A_SHR]], 1
+; CHECK-NEXT:    [[ADD_2:%.*]] = add nuw i8 [[A_SHR]], -128
 ; CHECK-NEXT:    [[ADD_3:%.*]] = add i8 [[A_SHR]], -127
 ; CHECK-NEXT:    [[ADD_4:%.*]] = add i8 [[A_SHR]], -1
 ; CHECK-NEXT:    [[RES_1:%.*]] = xor i8 [[ADD_1]], [[ADD_2]]
 ; CHECK-NEXT:    [[RES_2:%.*]] = xor i8 [[RES_1]], [[ADD_3]]
 ; CHECK-NEXT:    [[RES_3:%.*]] = xor i8 [[RES_2]], [[ADD_4]]
 ; CHECK-NEXT:    ret i8 [[RES_3]]
 ;
 entry:
   %a.shr = lshr i8 %a, 1
   %add.1 = add i8 %a.shr, 1
   %add.2 = add i8 %a.shr, 128
   %add.3 = add i8 %a.shr, 129
   %add.4 = add i8 %a.shr, -1
   %res.1 = xor i8 %add.1, %add.2
   %res.2 = xor i8 %res.1, %add.3
   %res.3 = xor i8 %res.2, %add.4
   ret i8 %res.3
 }
 
 define i8 @a_and_15_add_1(i8 %a) {
 ; CHECK-LABEL: @a_and_15_add_1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A_AND:%.*]] = and i8 [[A:%.*]], 15
-; CHECK-NEXT:    [[ADD_1:%.*]] = add i8 [[A_AND]], 1
+; CHECK-NEXT:    [[ADD_1:%.*]] = add nuw i8 [[A_AND]], 1
 ; CHECK-NEXT:    ret i8 [[ADD_1]]
 ;
 entry:
   %a.and = and i8 %a, 15
   %add.1 = add i8 %a.and, 1
   ret i8 %add.1
 }
 

 define i8 @sge_0_and_sle_90(i8 %a) {
 ; CHECK-LABEL: @sge_0_and_sle_90(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[SGT:%.*]] = icmp sge i8 [[A:%.*]], 0
 ; CHECK-NEXT:    [[SLT:%.*]] = icmp sle i8 [[A]], 90
 ; CHECK-NEXT:    [[AND:%.*]] = and i1 [[SGT]], [[SLT]]
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
-; CHECK-NEXT:    [[ADD_1:%.*]] = add i8 [[A]], 1
+; CHECK-NEXT:    [[ADD_1:%.*]] = add nuw i8 [[A]], 1
 ; CHECK-NEXT:    [[ADD_2:%.*]] = add i8 [[A]], -1
-; CHECK-NEXT:    [[ADD_3:%.*]] = add i8 [[A]], -91
+; CHECK-NEXT:    [[ADD_3:%.*]] = add nuw i8 [[A]], -91
 ; CHECK-NEXT:    [[ADD_4:%.*]] = add i8 [[A]], -90
 ; CHECK-NEXT:    [[RES_1:%.*]] = xor i8 [[ADD_1]], [[ADD_2]]
 ; CHECK-NEXT:    [[RES_2:%.*]] = xor i8 [[RES_1]], [[ADD_3]]
 ; CHECK-NEXT:    [[RES_3:%.*]] = xor i8 [[RES_2]], [[ADD_4]]
 ; CHECK-NEXT:    ret i8 [[RES_3]]
 ; CHECK:       else:
 ; CHECK-NEXT:    [[ADD_5:%.*]] = add i8 [[A]], 1
 ; CHECK-NEXT:    [[ADD_6:%.*]] = add i8 [[A]], -1

llvm/test/Transforms/SCCP/binaryops-constexprs.ll

entry:
   %and.3 = and i32 ptrtoint (ptr inttoptr (i32 20 to ptr) to i32), ptrtoint (ptr inttoptr (i32 100 to ptr) to i32)
   call void @use.i32(i32 %and.3)
   ret void
 }
 
 define void @add_constexpr(i32 %a) {
 ; CHECK-LABEL: @add_constexpr(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[ADD_1:%.*]] = add i32 0, [[A:%.*]]
+; CHECK-NEXT:    [[ADD_1:%.*]] = add nuw i32 0, [[A:%.*]]
 ; CHECK-NEXT:    call void @use.i32(i32 [[ADD_1]])
 ; CHECK-NEXT:    [[ADD_2:%.*]] = add i32 20, [[A]]
 ; CHECK-NEXT:    call void @use.i32(i32 [[ADD_2]])
 ; CHECK-NEXT:    [[COND_1:%.*]] = icmp ne i32 [[ADD_2]], 100
 ; CHECK-NEXT:    call void @use.i1(i1 [[COND_1]])
 ; CHECK-NEXT:    [[COND_2:%.*]] = icmp eq i32 [[ADD_2]], 100
 ; CHECK-NEXT:    call void @use.i1(i1 [[COND_2]])
 ; CHECK-NEXT:    [[COND_3:%.*]] = icmp eq i32 [[ADD_2]], 10

llvm/test/Transforms/SCCP/conditions-ranges-with-undef.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=ipsccp -S | FileCheck %s
 
 declare void @use(i1)
 
 ; We can simplify the conditions in the true block, because the condition
 ; allows us to replace all uses of %a in the block with a  constant.
 define void @val_undef_eq() {
 ; CHECK-LABEL: @val_undef_eq(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[A:%.*]] = add i32 undef, 0
+; CHECK-NEXT:    [[A:%.*]] = add nuw i32 undef, 0
 ; CHECK-NEXT:    [[BC_1:%.*]] = icmp eq i32 [[A]], 10
 ; CHECK-NEXT:    br i1 [[BC_1]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
 ; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    ret void
 ; CHECK:       false:
 ; CHECK-NEXT:    ret void

 
 declare void @use.i32(i32)
 
 ; It is not allowed to use the range information from the condition to remove
 ; %a.127 = and ... in the true block, as %a could be undef.
 define void @val_undef_range() {
 ; CHECK-LABEL: @val_undef_range(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[A:%.*]] = add i32 undef, 0
+; CHECK-NEXT:    [[A:%.*]] = add nuw i32 undef, 0
 ; CHECK-NEXT:    [[BC_1:%.*]] = icmp ult i32 [[A]], 127
 ; CHECK-NEXT:    br i1 [[BC_1]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
 ; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[A_127:%.*]] = and i32 [[A]], 127
 ; CHECK-NEXT:    call void @use.i32(i32 [[A_127]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       false:

llvm/test/Transforms/SCCP/conditions-ranges.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=ipsccp -S | FileCheck %s
 
 declare void @use(i1)
 
 define void @f1(i32 %a, i32 %b) {
 ; CHECK-LABEL: @f1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A_255:%.*]] = and i32 [[A:%.*]], 255
-; CHECK-NEXT:    [[A_2:%.*]] = add i32 [[A_255]], 20
+; CHECK-NEXT:    [[A_2:%.*]] = add nuw i32 [[A_255]], 20
 ; CHECK-NEXT:    [[BC:%.*]] = icmp ugt i32 [[B:%.*]], [[A_2]]
 ; CHECK-NEXT:    br i1 [[BC]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
 ; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    call void @use(i1 true)
true:
   ret void
 }
 
 ; Test with 2 related nested conditions (%b > [20, 276) && %b < 255).
 define void @f8_nested_conds(i32 %a, i32 %b) {
 ; CHECK-LABEL: @f8_nested_conds(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A_255:%.*]] = and i32 [[A:%.*]], 255
-; CHECK-NEXT:    [[A_2:%.*]] = add i32 [[A_255]], 20
+; CHECK-NEXT:    [[A_2:%.*]] = add nuw i32 [[A_255]], 20
 ; CHECK-NEXT:    [[BC_1:%.*]] = icmp ugt i32 [[B:%.*]], [[A_2]]
 ; CHECK-NEXT:    br i1 [[BC_1]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
 ; CHECK-NEXT:    [[BC_2:%.*]] = icmp ult i32 [[B]], 255
 ; CHECK-NEXT:    br i1 [[BC_2]], label [[TRUE_2:%.*]], label [[FALSE_2:%.*]]
 ; CHECK:       true.2:
 ; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    call void @use(i1 false)

 ; CHECK:       for.cond11:
 ; CHECK-NEXT:    [[J_0:%.*]] = phi i32 [ 0, [[FOR_BODY]] ], [ [[INC:%.*]], [[FOR_BODY14:%.*]] ]
 ; CHECK-NEXT:    [[CMP12:%.*]] = icmp slt i32 [[J_0]], 2
 ; CHECK-NEXT:    br i1 [[CMP12]], label [[FOR_BODY14]], label [[FOR_COND_CLEANUP13]]
 ; CHECK:       for.cond.cleanup13:
 ; CHECK-NEXT:    [[INC27]] = add nsw i32 [[I_0]], 1
 ; CHECK-NEXT:    br label [[FOR_COND]]
 ; CHECK:       for.body14:
-; CHECK-NEXT:    [[INC]] = add nsw i32 [[J_0]], 1
+; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[J_0]], 1
 ; CHECK-NEXT:    br label [[FOR_COND11]]
 ;
 entry:
   br label %for.cond
 
 for.cond:                                         ; preds = %for.cond.cleanup13, %if.then
   %i.0 = phi i32 [ 0, %entry ], [ %inc27, %for.cond.cleanup13 ]
   %cmp9 = icmp sle i32 %i.0, 3

llvm/test/Transforms/SCCP/ip-add-range-to-call.ll

 ;
   ret i32 %x
 }
 
 define i32 @caller1() {
 ; CHECK-LABEL: @caller1(
 ; CHECK-NEXT:    [[C1:%.*]] = call i32 @callee(i32 10), !range [[RNG0:![0-9]+]]
 ; CHECK-NEXT:    [[C2:%.*]] = call i32 @callee(i32 20), !range [[RNG0]]
-; CHECK-NEXT:    [[A:%.*]] = add i32 [[C1]], [[C2]]
+; CHECK-NEXT:    [[A:%.*]] = add nuw i32 [[C1]], [[C2]]
 ; CHECK-NEXT:    ret i32 [[A]]
 ;
   %c1 = call i32 @callee(i32 10)
   %c2 = call i32 @callee(i32 20)
   %a = add i32 %c1, %c2
   ret i32 %a
 }
 

llvm/test/Transforms/SCCP/ip-constant-ranges.ll

 define internal i32 @f2(i32 %x) {
 ; CHECK-LABEL: define {{[^@]+}}@f2
 ; CHECK-SAME: (i32 [[X:%.*]]) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[X]], 300
 ; CHECK-NEXT:    [[CMP4:%.*]] = icmp ugt i32 [[X]], 300
 ; CHECK-NEXT:    [[RES1:%.*]] = select i1 [[CMP]], i32 1, i32 2
 ; CHECK-NEXT:    [[RES4:%.*]] = select i1 [[CMP4]], i32 3, i32 4
-; CHECK-NEXT:    [[RES6:%.*]] = add i32 [[RES1]], 3
-; CHECK-NEXT:    [[RES7:%.*]] = add i32 5, [[RES4]]
-; CHECK-NEXT:    [[RES:%.*]] = add i32 [[RES6]], 5
+; CHECK-NEXT:    [[RES6:%.*]] = add nuw i32 [[RES1]], 3
+; CHECK-NEXT:    [[RES7:%.*]] = add nuw i32 5, [[RES4]]
+; CHECK-NEXT:    [[RES:%.*]] = add nuw i32 [[RES6]], 5
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
 entry:
   %cmp = icmp sgt i32 %x, 300
   %cmp2 = icmp ne i32 %x, 10
   %cmp3 = icmp sge i32 %x, 47
   %cmp4 = icmp ugt i32 %x, 300
   %cmp5 = icmp uge i32 %x, 47

 
 define i32 @caller1() {
 ; CHECK-LABEL: define {{[^@]+}}@caller1() {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CALL1:%.*]] = tail call i32 @f1(i32 1, i32 301)
 ; CHECK-NEXT:    [[CALL2:%.*]] = tail call i32 @f1(i32 47, i32 999)
 ; CHECK-NEXT:    [[CALL3:%.*]] = tail call i32 @f2(i32 47)
 ; CHECK-NEXT:    [[CALL4:%.*]] = tail call i32 @f2(i32 301)
-; CHECK-NEXT:    [[RES_1:%.*]] = add nsw i32 12, [[CALL3]]
-; CHECK-NEXT:    [[RES_2:%.*]] = add nsw i32 [[RES_1]], [[CALL4]]
+; CHECK-NEXT:    [[RES_1:%.*]] = add nuw nsw i32 12, [[CALL3]]
+; CHECK-NEXT:    [[RES_2:%.*]] = add nuw nsw i32 [[RES_1]], [[CALL4]]
 ; CHECK-NEXT:    ret i32 [[RES_2]]
 ;
 entry:
   %call1 = tail call i32 @f1(i32 1, i32 301)
   %call2 = tail call i32 @f1(i32 47, i32 999)
   %call3 = tail call i32 @f2(i32 47)
   %call4 = tail call i32 @f2(i32 301)
   %res.1 = add nsw i32 12, %call3

llvm/test/Transforms/SCCP/ip-ranges-binaryops.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=ipsccp -S | FileCheck %s
 
 ; x = [10, 21), y = [100, 201)
 ; x + y = [110, 221)
 define internal i1 @f.add(i32 %x, i32 %y) {
 ; CHECK-LABEL: @f.add(
-; CHECK-NEXT:    [[A_1:%.*]] = add i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[A_1:%.*]] = add nuw i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp sgt i32 [[A_1]], 219
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp slt i32 [[A_1]], 111
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp eq i32 [[A_1]], 150
 ; CHECK-NEXT:    [[C_6:%.*]] = icmp slt i32 [[A_1]], 150
-; CHECK-NEXT:    [[RES_1:%.*]] = add i1 false, [[C_2]]
-; CHECK-NEXT:    [[RES_2:%.*]] = add i1 [[RES_1]], false
+; CHECK-NEXT:    [[RES_1:%.*]] = add nuw i1 false, [[C_2]]
+; CHECK-NEXT:    [[RES_2:%.*]] = add nuw i1 [[RES_1]], false
 ; CHECK-NEXT:    [[RES_3:%.*]] = add i1 [[RES_2]], [[C_4]]
 ; CHECK-NEXT:    [[RES_4:%.*]] = add i1 [[RES_3]], [[C_5]]
 ; CHECK-NEXT:    [[RES_5:%.*]] = add i1 [[RES_4]], [[C_6]]
 ; CHECK-NEXT:    ret i1 [[RES_5]]
 ;
   %a.1 = add i32 %x, %y
   %c.1 = icmp sgt i32 %a.1, 220
   %c.2 = icmp sgt i32 %a.1, 219

 ; x - y = [-190, -79)
 define internal i1 @f.sub(i32 %x, i32 %y) {
 ; CHECK-LABEL: @f.sub(
 ; CHECK-NEXT:    [[A_1:%.*]] = sub i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp sgt i32 [[A_1]], -81
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp slt i32 [[A_1]], -189
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp eq i32 [[A_1]], -150
 ; CHECK-NEXT:    [[C_6:%.*]] = icmp slt i32 [[A_1]], -150
-; CHECK-NEXT:    [[RES_1:%.*]] = add i1 false, [[C_2]]
-; CHECK-NEXT:    [[RES_2:%.*]] = add i1 [[RES_1]], false
+; CHECK-NEXT:    [[RES_1:%.*]] = add nuw i1 false, [[C_2]]
+; CHECK-NEXT:    [[RES_2:%.*]] = add nuw i1 [[RES_1]], false
 ; CHECK-NEXT:    [[RES_3:%.*]] = add i1 [[RES_2]], [[C_4]]
 ; CHECK-NEXT:    [[RES_4:%.*]] = add i1 [[RES_3]], [[C_5]]
 ; CHECK-NEXT:    [[RES_5:%.*]] = add i1 [[RES_4]], [[C_6]]
 ; CHECK-NEXT:    ret i1 [[RES_5]]
 ;
   %a.1 = sub i32 %x, %y
   %c.1 = icmp sgt i32 %a.1, -80
   %c.2 = icmp sgt i32 %a.1, -81

 ; x * y = [1000, 4001)
 define internal i1 @f.mul(i32 %x, i32 %y) {
 ; CHECK-LABEL: @f.mul(
 ; CHECK-NEXT:    [[A_1:%.*]] = mul i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp sgt i32 [[A_1]], 3999
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp slt i32 [[A_1]], 1001
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp eq i32 [[A_1]], 1500
 ; CHECK-NEXT:    [[C_6:%.*]] = icmp slt i32 [[A_1]], 1500
-; CHECK-NEXT:    [[RES_1:%.*]] = add i1 false, [[C_2]]
-; CHECK-NEXT:    [[RES_2:%.*]] = add i1 [[RES_1]], false
+; CHECK-NEXT:    [[RES_1:%.*]] = add nuw i1 false, [[C_2]]
+; CHECK-NEXT:    [[RES_2:%.*]] = add nuw i1 [[RES_1]], false
 ; CHECK-NEXT:    [[RES_3:%.*]] = add i1 [[RES_2]], [[C_4]]
 ; CHECK-NEXT:    [[RES_4:%.*]] = add i1 [[RES_3]], [[C_5]]
 ; CHECK-NEXT:    [[RES_5:%.*]] = add i1 [[RES_4]], [[C_6]]
 ; CHECK-NEXT:    ret i1 [[RES_5]]
 ;
   %a.1 = mul i32 %x, %y
   %c.1 = icmp sgt i32 %a.1, 4000
   %c.2 = icmp sgt i32 %a.1, 3999

llvm/test/Transforms/SCCP/ip-ranges-casts.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=ipsccp -S | FileCheck %s
 
 ; x = [100, 301)
 define internal i1 @f.trunc(i32 %x) {
 ; CHECK-LABEL: @f.trunc(
 ; CHECK-NEXT:    [[T_1:%.*]] = trunc i32 [[X:%.*]] to i16
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp sgt i16 [[T_1]], 299
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp slt i16 [[T_1]], 101
-; CHECK-NEXT:    [[RES_1:%.*]] = add i1 false, [[C_2]]
-; CHECK-NEXT:    [[RES_2:%.*]] = add i1 [[RES_1]], false
+; CHECK-NEXT:    [[RES_1:%.*]] = add nuw i1 false, [[C_2]]
+; CHECK-NEXT:    [[RES_2:%.*]] = add nuw i1 [[RES_1]], false
 ; CHECK-NEXT:    [[RES_3:%.*]] = add i1 [[RES_2]], [[C_4]]
 ; CHECK-NEXT:    [[T_2:%.*]] = trunc i32 [[X]] to i8
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp sgt i8 [[T_2]], 44
 ; CHECK-NEXT:    [[C_6:%.*]] = icmp sgt i8 [[T_2]], 43
 ; CHECK-NEXT:    [[C_7:%.*]] = icmp slt i8 [[T_2]], 100
 ; CHECK-NEXT:    [[C_8:%.*]] = icmp slt i8 [[T_2]], 101
 ; CHECK-NEXT:    [[RES_4:%.*]] = add i1 [[RES_3]], [[C_5]]
 ; CHECK-NEXT:    [[RES_5:%.*]] = add i1 [[RES_4]], [[C_6]]

 
 
 ; x = [100, 301)
 define internal i1 @f.zext(i32 %x, i32 %y) {
 ; CHECK-LABEL: @f.zext(
 ; CHECK-NEXT:    [[T_1:%.*]] = zext i32 [[X:%.*]] to i64
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp sgt i64 [[T_1]], 299
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp slt i64 [[T_1]], 101
-; CHECK-NEXT:    [[RES_1:%.*]] = add i1 false, [[C_2]]
-; CHECK-NEXT:    [[RES_2:%.*]] = add i1 [[RES_1]], false
+; CHECK-NEXT:    [[RES_1:%.*]] = add nuw i1 false, [[C_2]]
+; CHECK-NEXT:    [[RES_2:%.*]] = add nuw i1 [[RES_1]], false
 ; CHECK-NEXT:    [[RES_3:%.*]] = add i1 [[RES_2]], [[C_4]]
 ; CHECK-NEXT:    [[T_2:%.*]] = zext i32 [[Y:%.*]] to i64
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp sgt i64 [[T_2]], 300
 ; CHECK-NEXT:    [[C_6:%.*]] = icmp sgt i64 [[T_2]], 299
 ; CHECK-NEXT:    [[C_8:%.*]] = icmp slt i64 [[T_2]], 1
 ; CHECK-NEXT:    [[RES_4:%.*]] = add i1 [[RES_3]], [[C_5]]
 ; CHECK-NEXT:    [[RES_5:%.*]] = add i1 [[RES_4]], [[C_6]]
-; CHECK-NEXT:    [[RES_6:%.*]] = add i1 [[RES_5]], false
+; CHECK-NEXT:    [[RES_6:%.*]] = add nuw i1 [[RES_5]], false
 ; CHECK-NEXT:    [[RES_7:%.*]] = add i1 [[RES_6]], [[C_8]]
 ; CHECK-NEXT:    ret i1 [[RES_7]]
 ;
 
   %t.1 = zext i32 %x to i64
   %c.1 = icmp sgt i64 %t.1, 300
   %c.2 = icmp sgt i64 %t.1, 299
   %c.3 = icmp slt i64 %t.1, 100

 }
 
 ; x = [100, 301)
 define internal i1 @f.sext(i32 %x, i32 %y) {
 ; CHECK-LABEL: @f.sext(
 ; CHECK-NEXT:    [[T_1:%.*]] = zext i32 [[X:%.*]] to i64
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp sgt i64 [[T_1]], 299
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp slt i64 [[T_1]], 101
-; CHECK-NEXT:    [[RES_1:%.*]] = add i1 false, [[C_2]]
-; CHECK-NEXT:    [[RES_2:%.*]] = add i1 [[RES_1]], false
+; CHECK-NEXT:    [[RES_1:%.*]] = add nuw i1 false, [[C_2]]
+; CHECK-NEXT:    [[RES_2:%.*]] = add nuw i1 [[RES_1]], false
 ; CHECK-NEXT:    [[RES_3:%.*]] = add i1 [[RES_2]], [[C_4]]
 ; CHECK-NEXT:    [[T_2:%.*]] = sext i32 [[Y:%.*]] to i64
 ; CHECK-NEXT:    [[C_6:%.*]] = icmp sgt i64 [[T_2]], 899
 ; CHECK-NEXT:    [[C_8:%.*]] = icmp slt i64 [[T_2]], -119
-; CHECK-NEXT:    [[RES_4:%.*]] = add i1 [[RES_3]], false
+; CHECK-NEXT:    [[RES_4:%.*]] = add nuw i1 [[RES_3]], false
 ; CHECK-NEXT:    [[RES_5:%.*]] = add i1 [[RES_4]], [[C_6]]
-; CHECK-NEXT:    [[RES_6:%.*]] = add i1 [[RES_5]], false
+; CHECK-NEXT:    [[RES_6:%.*]] = add nuw i1 [[RES_5]], false
 ; CHECK-NEXT:    [[RES_7:%.*]] = add i1 [[RES_6]], [[C_8]]
 ; CHECK-NEXT:    ret i1 [[RES_7]]
 ;
   %t.1 = sext i32 %x to i64
   %c.1 = icmp sgt i64 %t.1, 300
   %c.2 = icmp sgt i64 %t.1, 299
   %c.3 = icmp slt i64 %t.1, 100
   %c.4 = icmp slt i64 %t.1, 101

llvm/test/Transforms/SCCP/ip-ranges-phis.ll

 ; CHECK:       end:
 ; CHECK-NEXT:    [[P:%.*]] = phi i32 [ [[X]], [[ENTRY:%.*]] ], [ [[Y]], [[IF_TRUE_1]] ], [ [[Z]], [[IF_TRUE_2]] ]
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp sgt i32 [[P]], 5
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp eq i32 [[P]], 0
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp slt i32 [[P]], 0
 ; CHECK-NEXT:    [[V_1:%.*]] = select i1 [[C_1]], i32 10, i32 100
 ; CHECK-NEXT:    [[V_2:%.*]] = select i1 [[C_2]], i32 20, i32 200
 ; CHECK-NEXT:    [[V_3:%.*]] = select i1 [[C_3]], i32 30, i32 300
-; CHECK-NEXT:    [[R_1:%.*]] = add i32 [[V_1]], [[V_2]]
-; CHECK-NEXT:    [[R_2:%.*]] = add i32 [[R_1]], [[V_3]]
-; CHECK-NEXT:    [[R_3:%.*]] = add i32 [[R_2]], 400
-; CHECK-NEXT:    [[R_4:%.*]] = add i32 [[R_3]], 50
-; CHECK-NEXT:    [[R_5:%.*]] = add i32 [[R_4]], 60
-; CHECK-NEXT:    [[R_6:%.*]] = add i32 [[R_4]], 700
+; CHECK-NEXT:    [[R_1:%.*]] = add nuw i32 [[V_1]], [[V_2]]
+; CHECK-NEXT:    [[R_2:%.*]] = add nuw i32 [[R_1]], [[V_3]]
+; CHECK-NEXT:    [[R_3:%.*]] = add nuw i32 [[R_2]], 400
+; CHECK-NEXT:    [[R_4:%.*]] = add nuw i32 [[R_3]], 50
+; CHECK-NEXT:    [[R_5:%.*]] = add nuw i32 [[R_4]], 60
+; CHECK-NEXT:    [[R_6:%.*]] = add nuw i32 [[R_4]], 700
 ; CHECK-NEXT:    ret i32 [[R_6]]
 ;
 
 
 
 entry:
   br i1 %cmp.1, label %if.true.1, label %end
 

 ; CHECK-NEXT:    [[C_7:%.*]] = icmp slt i32 [[P]], -11
 ; CHECK-NEXT:    [[V_1:%.*]] = select i1 [[C_1]], i32 10, i32 100
 ; CHECK-NEXT:    [[V_2:%.*]] = select i1 [[C_2]], i32 20, i32 200
 ; CHECK-NEXT:    [[V_3:%.*]] = select i1 [[C_3]], i32 30, i32 300
 ; CHECK-NEXT:    [[V_4:%.*]] = select i1 [[C_4]], i32 40, i32 400
 ; CHECK-NEXT:    [[V_5:%.*]] = select i1 [[C_5]], i32 50, i32 500
 ; CHECK-NEXT:    [[V_6:%.*]] = select i1 [[C_6]], i32 60, i32 600
 ; CHECK-NEXT:    [[V_7:%.*]] = select i1 [[C_7]], i32 70, i32 700
-; CHECK-NEXT:    [[R_1:%.*]] = add i32 [[V_1]], [[V_2]]
-; CHECK-NEXT:    [[R_2:%.*]] = add i32 [[R_1]], [[V_3]]
-; CHECK-NEXT:    [[R_3:%.*]] = add i32 [[R_2]], [[V_4]]
-; CHECK-NEXT:    [[R_4:%.*]] = add i32 [[R_3]], [[V_5]]
-; CHECK-NEXT:    [[R_5:%.*]] = add i32 [[R_4]], [[V_6]]
-; CHECK-NEXT:    [[R_6:%.*]] = add i32 [[R_4]], [[V_7]]
+; CHECK-NEXT:    [[R_1:%.*]] = add nuw i32 [[V_1]], [[V_2]]
+; CHECK-NEXT:    [[R_2:%.*]] = add nuw i32 [[R_1]], [[V_3]]
+; CHECK-NEXT:    [[R_3:%.*]] = add nuw i32 [[R_2]], [[V_4]]
+; CHECK-NEXT:    [[R_4:%.*]] = add nuw i32 [[R_3]], [[V_5]]
+; CHECK-NEXT:    [[R_5:%.*]] = add nuw i32 [[R_4]], [[V_6]]
+; CHECK-NEXT:    [[R_6:%.*]] = add nuw i32 [[R_4]], [[V_7]]
 ; CHECK-NEXT:    ret i32 [[R_6]]
 ;
 
 
 entry:
   br i1 %cmp.1, label %if.true.1, label %end
 
 if.true.1:

llvm/test/Transforms/SCCP/ip-ranges-select.ll

 declare void @use(i32)
 
 define internal i1 @f1(i32 %x, i32 %y, i1 %cmp) {
 ; CHECK-LABEL: define {{[^@]+}}@f1
 ; CHECK-SAME: (i32 [[X:%.*]], i32 [[Y:%.*]], i1 [[CMP:%.*]]) {
 ; CHECK-NEXT:    [[SEL_1:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[Y]]
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp sgt i32 [[SEL_1]], 100
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp eq i32 [[SEL_1]], 50
-; CHECK-NEXT:    [[RES_1:%.*]] = add i1 false, [[C_2]]
+; CHECK-NEXT:    [[RES_1:%.*]] = add nuw i1 false, [[C_2]]
 ; CHECK-NEXT:    [[RES_2:%.*]] = add i1 [[RES_1]], [[C_3]]
-; CHECK-NEXT:    [[RES_3:%.*]] = add i1 [[RES_2]], false
+; CHECK-NEXT:    [[RES_3:%.*]] = add nuw i1 [[RES_2]], false
 ; CHECK-NEXT:    ret i1 [[RES_3]]
 ;
   %sel.1 = select i1 %cmp, i32 %x, i32 %y
   %c.1 = icmp sgt i32 %sel.1, 300
   %c.2 = icmp sgt i32 %sel.1, 100
   %c.3 = icmp eq i32 %sel.1, 50
   %c.4 = icmp slt i32 %sel.1, 9
   %res.1 = add i1 %c.1, %c.2

llvm/test/Transforms/SCCP/return-argument.ll

F:              ; preds = %0
   store i32 %X2, ptr %V
   ret ptr %V
 }
 
 ;; This function returns its first argument as a part of a multiple return
 ;; value
 define internal { i32, i32 } @foo(i32 %A, i32 %B) {
 ; CHECK-LABEL: @foo(
-; CHECK-NEXT:    [[X:%.*]] = add i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[X:%.*]] = add nuw i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[Y:%.*]] = insertvalue { i32, i32 } undef, i32 [[A]], 0
 ; CHECK-NEXT:    [[Z:%.*]] = insertvalue { i32, i32 } [[Y]], i32 [[X]], 1
 ; CHECK-NEXT:    ret { i32, i32 } [[Z]]
 ;
   %X = add i32 %A, %B
   %Y = insertvalue { i32, i32 } undef, i32 %A, 0
   %Z = insertvalue { i32, i32 } %Y, i32 %X, 1
   ret { i32, i32 } %Z
 }
 
 define void @caller(i1 %C) personality ptr @__gxx_personality_v0 {
 ; CHECK-LABEL: @caller(
 ; CHECK-NEXT:    [[Q:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    [[W:%.*]] = call ptr @incdec(i1 [[C:%.*]], ptr [[Q]])
 ; CHECK-NEXT:    [[S1:%.*]] = call { i32, i32 } @foo(i32 1, i32 2)
 ; CHECK-NEXT:    [[X1:%.*]] = extractvalue { i32, i32 } [[S1]], 0
 ; CHECK-NEXT:    [[S2:%.*]] = invoke { i32, i32 } @foo(i32 3, i32 4)
 ; CHECK-NEXT:    to label [[OK:%.*]] unwind label [[LPAD:%.*]]
 ; CHECK:       OK:
 ; CHECK-NEXT:    [[X2:%.*]] = extractvalue { i32, i32 } [[S2]], 0
-; CHECK-NEXT:    [[Z:%.*]] = add i32 [[X1]], [[X2]]
+; CHECK-NEXT:    [[Z:%.*]] = add nuw i32 [[X1]], [[X2]]
 ; CHECK-NEXT:    store i32 [[Z]], ptr [[W]], align 4
 ; CHECK-NEXT:    br label [[RET:%.*]]
 ; CHECK:       LPAD:
 ; CHECK-NEXT:    [[EXN:%.*]] = landingpad { ptr, i32 }
 ; CHECK-NEXT:    cleanup
 ; CHECK-NEXT:    br label [[RET]]
 ; CHECK:       RET:
 ; CHECK-NEXT:    ret void

llvm/test/Transforms/SCCP/return-constants.ll

 }
 
 define %0 @caller(i1 %Q) {
 ; CHECK-LABEL: @caller(
 ; CHECK-NEXT:    [[X:%.*]] = call [[TMP0:%.*]] @foo(i1 [[Q:%.*]])
 ; CHECK-NEXT:    [[B:%.*]] = extractvalue [[TMP0]] [[X]], 1
 ; CHECK-NEXT:    [[Y:%.*]] = call [[TMP0]] @bar(i1 [[Q]])
 ; CHECK-NEXT:    [[D:%.*]] = extractvalue [[TMP0]] [[Y]], 1
-; CHECK-NEXT:    [[N:%.*]] = add i32 [[B]], [[D]]
+; CHECK-NEXT:    [[N:%.*]] = add nuw i32 [[B]], [[D]]
 ; CHECK-NEXT:    ret [[TMP0]] [[X]]
 ;
   %X = call %0 @foo(i1 %Q)
   %A = extractvalue %0 %X, 0
   %B = extractvalue %0 %X, 1
   %Y = call %0 @bar(i1 %Q)
   %C = extractvalue %0 %Y, 0
   %D = extractvalue %0 %Y, 1
   %M = add i32 %A, %C
   %N = add i32 %B, %D
   ret %0 %X
 }

llvm/test/Transforms/SCCP/widening.ll

 ; SCCP-LABEL: @test_2_incoming_constants(
 ; SCCP-NEXT:  entry:
 ; SCCP-NEXT:    [[C_1:%.*]] = call i1 @cond()
 ; SCCP-NEXT:    br i1 [[C_1]], label [[BB1:%.*]], label [[EXIT:%.*]]
 ; SCCP:       bb1:
 ; SCCP-NEXT:    br label [[EXIT]]
 ; SCCP:       exit:
 ; SCCP-NEXT:    [[P:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 1, [[BB1]] ]
-; SCCP-NEXT:    [[A:%.*]] = add i32 [[P]], 1
+; SCCP-NEXT:    [[A:%.*]] = add nuw i32 [[P]], 1
 ; SCCP-NEXT:    call void @use(i1 true)
 ; SCCP-NEXT:    call void @use(i1 false)
 ; SCCP-NEXT:    ret void
 ;
 ; IPSCCP-LABEL: @test_2_incoming_constants(
 ; IPSCCP-NEXT:  entry:
 ; IPSCCP-NEXT:    [[C_1:%.*]] = call i1 @cond()
 ; IPSCCP-NEXT:    br i1 [[C_1]], label [[BB1:%.*]], label [[EXIT:%.*]]
 ; IPSCCP:       bb1:
 ; IPSCCP-NEXT:    br label [[EXIT]]
 ; IPSCCP:       exit:
 ; IPSCCP-NEXT:    [[P:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 1, [[BB1]] ]
-; IPSCCP-NEXT:    [[A:%.*]] = add i32 [[P]], 1
+; IPSCCP-NEXT:    [[A:%.*]] = add nuw i32 [[P]], 1
 ; IPSCCP-NEXT:    call void @use(i1 true)
 ; IPSCCP-NEXT:    call void @use(i1 false)
 ; IPSCCP-NEXT:    ret void
 ;
 entry:
   %c.1 = call i1 @cond()
   br i1 %c.1, label %bb1, label %exit
 

 ; SCCP-NEXT:    br i1 [[C_1]], label [[BB1:%.*]], label [[EXIT:%.*]]
 ; SCCP:       bb1:
 ; SCCP-NEXT:    [[C_2:%.*]] = call i1 @cond()
 ; SCCP-NEXT:    br i1 [[C_2]], label [[BB2:%.*]], label [[EXIT]]
 ; SCCP:       bb2:
 ; SCCP-NEXT:    br label [[EXIT]]
 ; SCCP:       exit:
 ; SCCP-NEXT:    [[P:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 1, [[BB1]] ], [ 2, [[BB2]] ]
-; SCCP-NEXT:    [[A:%.*]] = add i32 [[P]], 1
+; SCCP-NEXT:    [[A:%.*]] = add nuw i32 [[P]], 1
 ; SCCP-NEXT:    call void @use(i1 true)
 ; SCCP-NEXT:    call void @use(i1 false)
 ; SCCP-NEXT:    ret void
 ;
 ; IPSCCP-LABEL: @test_3_incoming_constants(
 ; IPSCCP-NEXT:  entry:
 ; IPSCCP-NEXT:    [[C_1:%.*]] = call i1 @cond()
 ; IPSCCP-NEXT:    br i1 [[C_1]], label [[BB1:%.*]], label [[EXIT:%.*]]
 ; IPSCCP:       bb1:
 ; IPSCCP-NEXT:    [[C_2:%.*]] = call i1 @cond()
 ; IPSCCP-NEXT:    br i1 [[C_2]], label [[BB2:%.*]], label [[EXIT]]
 ; IPSCCP:       bb2:
 ; IPSCCP-NEXT:    br label [[EXIT]]
 ; IPSCCP:       exit:
 ; IPSCCP-NEXT:    [[P:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 1, [[BB1]] ], [ 2, [[BB2]] ]
-; IPSCCP-NEXT:    [[A:%.*]] = add i32 [[P]], 1
+; IPSCCP-NEXT:    [[A:%.*]] = add nuw i32 [[P]], 1
 ; IPSCCP-NEXT:    call void @use(i1 true)
 ; IPSCCP-NEXT:    call void @use(i1 false)
 ; IPSCCP-NEXT:    ret void
 ;
 entry:
   %c.1 = call i1 @cond()
   br i1 %c.1, label %bb1, label %exit
 

 ; SCCP-NEXT:    br i1 [[C_3]], label [[BB3:%.*]], label [[EXIT]]
 ; SCCP:       bb3:
 ; SCCP-NEXT:    [[C_4:%.*]] = call i1 @cond()
 ; SCCP-NEXT:    br i1 [[C_4]], label [[BB4:%.*]], label [[EXIT]]
 ; SCCP:       bb4:
 ; SCCP-NEXT:    br label [[EXIT]]
 ; SCCP:       exit:
 ; SCCP-NEXT:    [[P:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 1, [[BB1]] ], [ 2, [[BB2]] ], [ 3, [[BB3]] ], [ 4, [[BB4]] ]
-; SCCP-NEXT:    [[A:%.*]] = add i32 [[P]], 1
+; SCCP-NEXT:    [[A:%.*]] = add nuw i32 [[P]], 1
 ; SCCP-NEXT:    call void @use(i1 true)
 ; SCCP-NEXT:    call void @use(i1 false)
 ; SCCP-NEXT:    ret void
 ;
 ; IPSCCP-LABEL: @test_5_incoming_constants(
 ; IPSCCP-NEXT:  entry:
 ; IPSCCP-NEXT:    [[C_1:%.*]] = call i1 @cond()
 ; IPSCCP-NEXT:    br i1 [[C_1]], label [[BB1:%.*]], label [[EXIT:%.*]]
 ; IPSCCP:       bb1:
 ; IPSCCP-NEXT:    [[C_2:%.*]] = call i1 @cond()
 ; IPSCCP-NEXT:    br i1 [[C_2]], label [[BB2:%.*]], label [[EXIT]]
 ; IPSCCP:       bb2:
 ; IPSCCP-NEXT:    [[C_3:%.*]] = call i1 @cond()
 ; IPSCCP-NEXT:    br i1 [[C_3]], label [[BB3:%.*]], label [[EXIT]]
 ; IPSCCP:       bb3:
 ; IPSCCP-NEXT:    [[C_4:%.*]] = call i1 @cond()
 ; IPSCCP-NEXT:    br i1 [[C_4]], label [[BB4:%.*]], label [[EXIT]]
 ; IPSCCP:       bb4:
 ; IPSCCP-NEXT:    br label [[EXIT]]
 ; IPSCCP:       exit:
 ; IPSCCP-NEXT:    [[P:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 1, [[BB1]] ], [ 2, [[BB2]] ], [ 3, [[BB3]] ], [ 4, [[BB4]] ]
-; IPSCCP-NEXT:    [[A:%.*]] = add i32 [[P]], 1
+; IPSCCP-NEXT:    [[A:%.*]] = add nuw i32 [[P]], 1
 ; IPSCCP-NEXT:    call void @use(i1 true)
 ; IPSCCP-NEXT:    call void @use(i1 false)
 ; IPSCCP-NEXT:    ret void
 ;
 entry:
   %c.1 = call i1 @cond()
   br i1 %c.1, label %bb1, label %exit
 

 ; SCCP-NEXT:    br i1 [[C_2]], label [[EXIT]], label [[BB2:%.*]]
 ; SCCP:       bb2:
 ; SCCP-NEXT:    [[C_3:%.*]] = call i1 @cond()
 ; SCCP-NEXT:    br i1 [[C_3]], label [[BB3:%.*]], label [[EXIT]]
 ; SCCP:       bb3:
 ; SCCP-NEXT:    br label [[EXIT]]
 ; SCCP:       exit:
 ; SCCP-NEXT:    [[P:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ 3, [[BB1]] ], [ 2, [[BB2]] ], [ 5, [[BB3]] ]
-; SCCP-NEXT:    [[A:%.*]] = add i32 [[P]], 1
+; SCCP-NEXT:    [[A:%.*]] = add nuw i32 [[P]], 1
 ; SCCP-NEXT:    call void @use(i1 true)
 ; SCCP-NEXT:    call void @use(i1 false)
 ; SCCP-NEXT:    br label [[EXIT_1:%.*]]
 ; SCCP:       exit.1:
 ; SCCP-NEXT:    ret void
 ;
 ; IPSCCP-LABEL: @rotated_loop_2(
 ; IPSCCP-NEXT:  entry:
 ; IPSCCP-NEXT:    [[C_1:%.*]] = call i1 @cond()
 ; IPSCCP-NEXT:    br i1 [[C_1]], label [[EXIT:%.*]], label [[BB1:%.*]]
 ; IPSCCP:       bb1:
 ; IPSCCP-NEXT:    [[C_2:%.*]] = call i1 @cond()
 ; IPSCCP-NEXT:    br i1 [[C_2]], label [[EXIT]], label [[BB2:%.*]]
 ; IPSCCP:       bb2:
 ; IPSCCP-NEXT:    [[C_3:%.*]] = call i1 @cond()
 ; IPSCCP-NEXT:    br i1 [[C_3]], label [[BB3:%.*]], label [[EXIT]]
 ; IPSCCP:       bb3:
 ; IPSCCP-NEXT:    br label [[EXIT]]
 ; IPSCCP:       exit:
 ; IPSCCP-NEXT:    [[P:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ 3, [[BB1]] ], [ 2, [[BB2]] ], [ 5, [[BB3]] ]
-; IPSCCP-NEXT:    [[A:%.*]] = add i32 [[P]], 1
+; IPSCCP-NEXT:    [[A:%.*]] = add nuw i32 [[P]], 1
 ; IPSCCP-NEXT:    call void @use(i1 true)
 ; IPSCCP-NEXT:    call void @use(i1 false)
 ; IPSCCP-NEXT:    br label [[EXIT_1:%.*]]
 ; IPSCCP:       exit.1:
 ; IPSCCP-NEXT:    ret void
 ;
 entry:
   %c.1 = call i1 @cond()

 ; IPSCCP-NEXT:  entry:
 ; IPSCCP-NEXT:    br label [[LOOP_HEADER:%.*]]
 ; IPSCCP:       loop.header:
 ; IPSCCP-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_BODY:%.*]] ]
 ; IPSCCP-NEXT:    [[C_1:%.*]] = icmp slt i32 [[IV]], 2
 ; IPSCCP-NEXT:    br i1 [[C_1]], label [[LOOP_BODY]], label [[EXIT:%.*]]
 ; IPSCCP:       loop.body:
 ; IPSCCP-NEXT:    call void @use(i1 true)
-; IPSCCP-NEXT:    [[IV_NEXT]] = add nsw i32 [[IV]], 1
+; IPSCCP-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; IPSCCP-NEXT:    br label [[LOOP_HEADER]]
 ; IPSCCP:       exit:
 ; IPSCCP-NEXT:    ret void
 ;
 entry:
   br label %loop.header
 
 loop.header: