[SCEV] Use wrap flags in InsertBinop

[samparker]

Summary

If the given SCEVExpr has no (un)signed flags attached to it, transfer these other to the resulting instruction.

@echristo Would you mind taking a particular look at the changes in single-access-no-preloop? As I'm quite confused how both nuw nsw get attached to the add instruction.

[samparker]

Ping.

[jdoerfert]

lib/Analysis/ScalarEvolutionExpander.cpp

753 ↗

(On Diff #199563)

Why is this happening only at the end? A SCEVAdd <nsw>(a+b+c) should have two <nsw> additions, right? Should we have the following code as a helper routine that is called after a new Sum was created?

I just realized, maybe my interpretation of SCEVAdd <nsw>(a+b+c) is wrong. Does it mean there is no intermediate overflow? In that case, the above might be what we want. If that is not the case, what does it mean?

754 ↗

(On Diff #199563)

This makes implicit assumptions about the hierarchy. Could you (also) check isa<Instruction>?

[nikic]

It's not entirely obvious to me that this will be correct if an existing add instruction gets reused.

I think it might make more sense to pass nowrap flags to InsertBinop and integrate more tightly there, in particular see the TODO on canGeneratePoison. That is pick an existing instruction with right nowrap flags or insert a new one, but don't reuse an instruction while assigning different flags.

[samparker]

Thanks both, I've moved the logic into InsertBinop.

[nikic]

lib/Analysis/ScalarEvolutionExpander.cpp

193 ↗

(On Diff #202685)

I'd move the comment down to the corresponding branch.

865 ↗

(On Diff #202685)

Should be FlagAnyWrap?

[samparker]

lib/Analysis/ScalarEvolutionExpander.cpp

865 ↗

(On Diff #202685)

Neither lshr or udiv wrap, they only support 'exact'.

[samparker]

Updated comments.

[nikic]

lib/Analysis/ScalarEvolutionExpander.cpp

865 ↗

(On Diff #202685)

Right, that's why you want to pass no flags here, which is what AnyWrap (=0) does. FlagNW is a different kind of nowrap flag that doesn't apply to udiv and has no IR representation anyway.

[samparker]

lib/Analysis/ScalarEvolutionExpander.cpp

865 ↗

(On Diff #202685)

Ah, okay, thanks!

[samparker]

Using FlagAnyWrap for lshr and udiv.

[nikic]

test/Transforms/LoopIdiom/basic.ll

49 ↗

(On Diff #203104)

This nuw flag seems dubious. Or maybe the whole transform is dubious. It's not immediately clear to me why it would be illegal to have a loop that clears a whole address space using say i16s and size half the address space. In that case this memset formation will go from clearing the address space to setting zero bytes. With the additional nuw flag it will be UB instead. But I don't think it's UB to pass a large size to this function in the first place. Am I wrong about that?

[nikic]

LGTM. The question regarding the memset transform still stands, but it's really an unrelated issue.

[samparker]

test/Transforms/LoopIdiom/basic.ll

49 ↗

(On Diff #203104)

I agree, it looks wrong to me. I can't see how it's safe to double 'Size'.

[samparker]

test/Transforms/LoopIdiom/basic.ll

49 ↗

(On Diff #203104)

@echristo Looks like your test, so are you able to shed some light on this please?

[reames]

Flags on SCEVs are valid for the current set of users that exist in the loop. If you add *new* users then those flags may no longer be valid. We recently ran into this in LFTR, and this patch seems likely to have the same risk. I have not audited the patch or its output to be sure, just throwing out a possibility.

[samparker]

Thanks Philip. This has been reverted, so something is wrong. I'm finding it difficult to wrap, pun intended, my head around how adding users affects the semantics of a given expression. Are they any reviews/threads that you could point me to?

[nikic]

In D61934#1534106, @samparker wrote:

Thanks Philip. This has been reverted, so something is wrong. I'm finding it difficult to wrap, pun intended, my head around how adding users affects the semantics of a given expression. Are they any reviews/threads that you could point me to?

It would be nice to find out what went wrong here. The issue Philip refers to is discussed in D60935, but I don't think it applies in this context. I would expect that the nowrap flags in SCEV are just wrong ... somewhere.

[reames]

A suggestion on how to make progress here. Introduce the wrap flags to the API, but have *all* callers pass AnyWrap. That must be NFC.

Then land each API usage one by one. (Without separate review is fine, but let them sit for a day or two between commits.) Whichever one breaks is the problematic one, and you'll then know where to spend your debugging cycles.

llvm/trunk/lib/Analysis/ScalarEvolutionExpander.cpp

747

This particular pair of lines looks really suspicious. The flags which are correct on an add are very different from those valid on a subtract.

Consider:
add nsw i32 %a, -1
sub nsw nuw i32 %a, 1
OR
add nsw nuw i8 %a, 127 ;; %a must be zero
sub i32 %a, 128

[samparker]

Thanks @reames - this is the approach I will take and I'll pay particular attention to the add/sub case. I'll link the commits back to this review as I go.

[samparker]

First part: https://reviews.llvm.org/rL363147

llvm/trunk/include/llvm/Analysis/ScalarEvolutionExpander.h

private:
     bool isHighCostExpansionHelper(const SCEV *S, Loop *L,
                                    const Instruction *At,
                                    SmallPtrSetImpl<const SCEV *> &Processed);
 
     /// Insert the specified binary operator, doing a small amount of work to
     /// avoid inserting an obviously redundant operation, and hoisting to an
     /// outer loop when the opportunity is there and it is safe.
     Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS,
-                       bool IsSafeToHoist);
+                       SCEV::NoWrapFlags Flags, bool IsSafeToHoist);
 
     /// Arrange for there to be a cast of V to Ty at IP, reusing an existing
     /// cast if a suitable one exists, moving an existing cast if a suitable one
     /// exists but isn't in the right place, or creating a new one.
     Value *ReuseOrCreateCast(Value *V, Type *Ty,
                              Instruction::CastOps Op,
                              BasicBlock::iterator IP);
 

llvm/trunk/lib/Analysis/ScalarEvolutionExpander.cpp

Value *SCEVExpander::InsertNoopCastOfTo(Value *V, Type *Ty) {
   BasicBlock::iterator IP = findInsertPointAfter(I, Builder.GetInsertBlock());
   return ReuseOrCreateCast(I, Ty, Op, IP);
 }
 
 /// InsertBinop - Insert the specified binary operator, doing a small amount
 /// of work to avoid inserting an obviously redundant operation, and hoisting
 /// to an outer loop when the opportunity is there and it is safe.
 Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode,
-                                 Value *LHS, Value *RHS, bool IsSafeToHoist) {
+                                 Value *LHS, Value *RHS,
+                                 SCEV::NoWrapFlags Flags, bool IsSafeToHoist) {
   // Fold a binop with constant operands.
   if (Constant *CLHS = dyn_cast<Constant>(LHS))
     if (Constant *CRHS = dyn_cast<Constant>(RHS))
       return ConstantExpr::get(Opcode, CLHS, CRHS);
 
   // Do a quick scan to see if we have this binop nearby.  If so, reuse it.
   unsigned ScanLimit = 6;
   BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin();
   // Scanning starts from the last instruction before the insertion point.
   BasicBlock::iterator IP = Builder.GetInsertPoint();
   if (IP != BlockBegin) {
     --IP;
     for (; ScanLimit; --IP, --ScanLimit) {
       // Don't count dbg.value against the ScanLimit, to avoid perturbing the
       // generated code.
       if (isa<DbgInfoIntrinsic>(IP))
         ScanLimit++;
 
-      // Conservatively, do not use any instruction which has any of wrap/exact
-      // flags installed.
-      // TODO: Instead of simply disable poison instructions we can be clever
-      //       here and match SCEV to this instruction.
-      auto canGeneratePoison = [](Instruction *I) {
-        if (isa<OverflowingBinaryOperator>(I) &&
-            (I->hasNoSignedWrap() || I->hasNoUnsignedWrap()))
+      auto canGenerateIncompatiblePoison = [&Flags](Instruction *I) {
+        // Ensure that no-wrap flags match.
+        if (isa<OverflowingBinaryOperator>(I)) {
+          if (I->hasNoSignedWrap() != (Flags & SCEV::FlagNSW))
+            return true;
+          if (I->hasNoUnsignedWrap() != (Flags & SCEV::FlagNUW))
             return true;
+        }
+        // Conservatively, do not use any instruction which has any of exact
+        // flags installed.
         if (isa<PossiblyExactOperator>(I) && I->isExact())
           return true;
         return false;
       };
       if (IP->getOpcode() == (unsigned)Opcode && IP->getOperand(0) == LHS &&
-          IP->getOperand(1) == RHS && !canGeneratePoison(&*IP))
+          IP->getOperand(1) == RHS && !canGenerateIncompatiblePoison(&*IP))
         return &*IP;
       if (IP == BlockBegin) break;
     }
   }
 
   // Save the original insertion point so we can restore it when we're done.
   DebugLoc Loc = Builder.GetInsertPoint()->getDebugLoc();
   SCEVInsertPointGuard Guard(Builder, this);
 
   if (IsSafeToHoist) {
     // Move the insertion point out of as many loops as we can.
     while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
       if (!L->isLoopInvariant(LHS) || !L->isLoopInvariant(RHS)) break;
       BasicBlock *Preheader = L->getLoopPreheader();
       if (!Preheader) break;
 
       // Ok, move up a level.
       Builder.SetInsertPoint(Preheader->getTerminator());
     }
   }
 
   // If we haven't found this binop, insert it.
   Instruction *BO = cast<Instruction>(Builder.CreateBinOp(Opcode, LHS, RHS));
   BO->setDebugLoc(Loc);
+  if (Flags & SCEV::FlagNUW)
+    BO->setHasNoUnsignedWrap();
+  if (Flags & SCEV::FlagNSW)
+    BO->setHasNoSignedWrap();
   rememberInstruction(BO);
 
   return BO;
 }
 
 /// FactorOutConstant - Test if S is divisible by Factor, using signed
 /// division. If so, update S with Factor divided out and return true.
 /// S need not be evenly divisible if a reasonable remainder can be
if (!Sum) {
                                                SE.getSCEV(Sum));
       for (++I; I != E && I->first == CurLoop; ++I)
         NewOps.push_back(I->second);
       Sum = expandAddToGEP(NewOps.begin(), NewOps.end(), PTy, Ty, expand(Op));
     } else if (Op->isNonConstantNegative()) {
       // Instead of doing a negate and add, just do a subtract.
       Value *W = expandCodeFor(SE.getNegativeSCEV(Op), Ty);
       Sum = InsertNoopCastOfTo(Sum, Ty);
-      Sum = InsertBinop(Instruction::Sub, Sum, W, /*IsSafeToHoist*/ true);
+      Sum = InsertBinop(Instruction::Sub, Sum, W, S->getNoWrapFlags(),
+                        /*IsSafeToHoist*/ true);
       ++I;
     } else {
       // A simple add.
       Value *W = expandCodeFor(Op, Ty);
       Sum = InsertNoopCastOfTo(Sum, Ty);
       // Canonicalize a constant to the RHS.
       if (isa<Constant>(Sum)) std::swap(Sum, W);
-      Sum = InsertBinop(Instruction::Add, Sum, W, /*IsSafeToHoist*/ true);
+      Sum = InsertBinop(Instruction::Add, Sum, W, S->getNoWrapFlags(),
+                        /*IsSafeToHoist*/ true);
       ++I;
     }
   }
 
   return Sum;
 }
 
 Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) {
Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) {
   // Emit instructions to mul all the operands. Hoist as much as possible
   // out of loops.
   Value *Prod = nullptr;
   auto I = OpsAndLoops.begin();
 
   // Expand the calculation of X pow N in the following manner:
   // Let N = P1 + P2 + ... + PK, where all P are powers of 2. Then:
   // X pow N = (X pow P1) * (X pow P2) * ... * (X pow PK).
-  const auto ExpandOpBinPowN = [this, &I, &OpsAndLoops, &Ty]() {
+  const auto ExpandOpBinPowN = [this, &I, &OpsAndLoops, &Ty, &S]() {
     auto E = I;
     // Calculate how many times the same operand from the same loop is included
     // into this power.
     uint64_t Exponent = 0;
     const uint64_t MaxExponent = UINT64_MAX >> 1;
     // No one sane will ever try to calculate such huge exponents, but if we
     // need this, we stop on UINT64_MAX / 2 because we need to exit the loop
     // below when the power of 2 exceeds our Exponent, and we want it to be
     // 1u << 31 at most to not deal with unsigned overflow.
     while (E != OpsAndLoops.end() && *I == *E && Exponent != MaxExponent) {
       ++Exponent;
       ++E;
     }
     assert(Exponent > 0 && "Trying to calculate a zeroth exponent of operand?");
 
     // Calculate powers with exponents 1, 2, 4, 8 etc. and include those of them
     // that are needed into the result.
     Value *P = expandCodeFor(I->second, Ty);
     Value *Result = nullptr;
     if (Exponent & 1)
       Result = P;
     for (uint64_t BinExp = 2; BinExp <= Exponent; BinExp <<= 1) {
-      P = InsertBinop(Instruction::Mul, P, P, /*IsSafeToHoist*/ true);
+      P = InsertBinop(Instruction::Mul, P, P, S->getNoWrapFlags(),
+                      /*IsSafeToHoist*/ true);
       if (Exponent & BinExp)
         Result = Result ? InsertBinop(Instruction::Mul, Result, P,
+                                      S->getNoWrapFlags(),
                                       /*IsSafeToHoist*/ true)
                         : P;
     }
 
     I = E;
     assert(Result && "Nothing was expanded?");
     return Result;
   };
 
   while (I != OpsAndLoops.end()) {
     if (!Prod) {
       // This is the first operand. Just expand it.
       Prod = ExpandOpBinPowN();
     } else if (I->second->isAllOnesValue()) {
       // Instead of doing a multiply by negative one, just do a negate.
       Prod = InsertNoopCastOfTo(Prod, Ty);
       Prod = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), Prod,
+                         S->getNoWrapFlags(),
                          /*IsSafeToHoist*/ true);
       ++I;
     } else {
       // A simple mul.
       Value *W = ExpandOpBinPowN();
       Prod = InsertNoopCastOfTo(Prod, Ty);
       // Canonicalize a constant to the RHS.
       if (isa<Constant>(Prod)) std::swap(Prod, W);
       const APInt *RHS;
       if (match(W, m_Power2(RHS))) {
         // Canonicalize Prod*(1<<C) to Prod<<C.
         assert(!Ty->isVectorTy() && "vector types are not SCEVable");
         Prod = InsertBinop(Instruction::Shl, Prod,
                            ConstantInt::get(Ty, RHS->logBase2()),
-                           /*IsSafeToHoist*/ true);
+                           S->getNoWrapFlags(), /*IsSafeToHoist*/ true);
       } else {
-        Prod = InsertBinop(Instruction::Mul, Prod, W, /*IsSafeToHoist*/ true);
+        Prod = InsertBinop(Instruction::Mul, Prod, W, S->getNoWrapFlags(),
+                           /*IsSafeToHoist*/ true);
       }
     }
   }
 
   return Prod;
 }
 
 Value *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) {
   Type *Ty = SE.getEffectiveSCEVType(S->getType());
 
   Value *LHS = expandCodeFor(S->getLHS(), Ty);
   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) {
     const APInt &RHS = SC->getAPInt();
     if (RHS.isPowerOf2())
       return InsertBinop(Instruction::LShr, LHS,
                          ConstantInt::get(Ty, RHS.logBase2()),
-                         /*IsSafeToHoist*/ true);
+                         SCEV::FlagAnyWrap, /*IsSafeToHoist*/ true);
   }
 
   Value *RHS = expandCodeFor(S->getRHS(), Ty);
-  return InsertBinop(Instruction::UDiv, LHS, RHS,
+  return InsertBinop(Instruction::UDiv, LHS, RHS, SCEV::FlagAnyWrap,
                      /*IsSafeToHoist*/ SE.isKnownNonZero(S->getRHS()));
 }
 
 /// Move parts of Base into Rest to leave Base with the minimal
 /// expression that provides a pointer operand suitable for a
 /// GEP expansion.
 static void ExposePointerBase(const SCEV *&Base, const SCEV *&Rest,
                               ScalarEvolution &SE) {

llvm/trunk/test/CodeGen/Hexagon/loop-idiom/memmove-rt-check.ll

 ; RUN: opt -hexagon-loop-idiom -S < %s | FileCheck %s
 
 ; Make sure that we generate correct runtime checks.
 
 ; CHECK: b7.old:
-; CHECK:   [[LEN:%[0-9]+]] = shl i32 %len, 3
+; CHECK:   [[LEN:%[0-9]+]] = shl nuw i32 %len, 3
 ; CHECK:   [[SRC:%[0-9]+]] = ptrtoint i8* %src to i32
 ; CHECK:   [[DST:%[0-9]+]] = ptrtoint i8* %dst to i32
 ; CHECK:   [[ULT:%[0-9]+]] = icmp ult i32 [[DST]], [[SRC]]
 ; CHECK:   [[SUB:%[0-9]+]] = sub i32 [[DST]], [[SRC]]
 ; CHECK:   [[SLT:%[0-9]+]] = icmp sle i32 [[LEN]], [[SUB]]
 ; CHECK:   [[CND:%[0-9]+]] = or i1 [[ULT]], [[SLT]]
 ; CHECK:   br i1 [[CND]], label %b8.rtli, label %b8.rtli.ph
 

llvm/trunk/test/Transforms/IRCE/bad_expander.ll

 define void @test_03(i64* %p1, i64* %p2, i1 %maybe_exit) {
 
 ; Show that IRCE would hit test_02 if the division was safe (denom not zero).
 
 ; CHECK-LABEL: test_03
 ; CHECK:       entry:
 ; CHECK-NEXT:    %num = load i64, i64* %p1, align 4
 ; CHECK-NEXT:    [[DIV:%[^ ]+]] = udiv i64 %num, 13
-; CHECK-NEXT:    [[DIV_MINUS_1:%[^ ]+]] = add i64 [[DIV]], -1
+; CHECK-NEXT:    [[DIV_MINUS_1:%[^ ]+]] = add nsw i64 [[DIV]], -1
 ; CHECK-NEXT:    [[COMP1:%[^ ]+]] = icmp sgt i64 [[DIV_MINUS_1]], 0
 ; CHECK-NEXT:    %exit.mainloop.at = select i1 [[COMP1]], i64 [[DIV_MINUS_1]], i64 0
 ; CHECK-NEXT:    [[COMP2:%[^ ]+]] = icmp slt i64 0, %exit.mainloop.at
 ; CHECK-NEXT:    br i1 [[COMP2]], label %loop.preheader, label %main.pseudo.exit
 ; CHECK-NOT:     preloop
 ; CHECK:       loop:
 ; CHECK-NEXT:    %iv = phi i64 [ %iv.next, %guarded ], [ 0, %loop.preheader ]
 ; CHECK-NEXT:    %iv.next = add nuw nsw i64 %iv, 1

llvm/trunk/test/Transforms/IRCE/conjunctive-checks.ll

 ; RUN: opt -S -verify-loop-info -irce < %s | FileCheck %s
 ; RUN: opt -S -verify-loop-info -passes='require<branch-prob>,loop(irce)' < %s | FileCheck %s
 
 define void @f_0(i32 *%arr, i32 *%a_len_ptr, i32 %n, i1* %cond_buf) {
 ; CHECK-LABEL: @f_0(
 
 ; CHECK: loop.preheader:
-; CHECK: [[len_sub:[^ ]+]] = add i32 %len, -4
+; CHECK: [[len_sub:[^ ]+]] = add nsw i32 %len, -4
 ; CHECK: [[exit_main_loop_at_hiclamp_cmp:[^ ]+]] = icmp slt i32 %n, [[len_sub]]
 ; CHECK: [[exit_main_loop_at_hiclamp:[^ ]+]] = select i1 [[exit_main_loop_at_hiclamp_cmp]], i32 %n, i32 [[len_sub]]
 ; CHECK: [[exit_main_loop_at_loclamp_cmp:[^ ]+]] = icmp sgt i32 [[exit_main_loop_at_hiclamp]], 0
 ; CHECK: [[exit_main_loop_at_loclamp:[^ ]+]] = select i1 [[exit_main_loop_at_loclamp_cmp]], i32 [[exit_main_loop_at_hiclamp]], i32 0
 ; CHECK: [[enter_main_loop:[^ ]+]] = icmp slt i32 0, [[exit_main_loop_at_loclamp]]
 ; CHECK: br i1 [[enter_main_loop]], label %[[loop_preheader2:[^ ,]+]], label %main.pseudo.exit
 
 ; CHECK: [[loop_preheader2]]:

llvm/trunk/test/Transforms/IRCE/decrementing-loop.ll

  exit:
   ret void
 
 ; CHECK: loop.preheader:
 ; CHECK:   [[len_hiclamp_cmp:[^ ]+]] = icmp slt i32 %len, %n
 ; CHECK:   [[len_hiclamp:[^ ]+]] = select i1 [[len_hiclamp_cmp]], i32 %len, i32 %n
 ; CHECK:   [[not_exit_preloop_at_cmp:[^ ]+]] = icmp sgt i32 [[len_hiclamp]], 0
 ; CHECK:   [[not_exit_preloop_at:[^ ]+]] = select i1 [[not_exit_preloop_at_cmp]], i32 [[len_hiclamp]], i32 0
-; CHECK:   %exit.preloop.at = add i32 [[not_exit_preloop_at]], -1
+; CHECK:   %exit.preloop.at = add nsw i32 [[not_exit_preloop_at]], -1
 }
 
 ; Make sure that we can eliminate the range check when the loop looks like:
 ; for (i = len.a - 1; i >= 0; --i)
 ;   b[i] = a[i];
 define void @test_01(i32* %a, i32* %b, i32* %a_len_ptr, i32* %b_len_ptr) {
 
 ; CHECK-LABEL: test_01

llvm/trunk/test/Transforms/IRCE/ranges_of_different_types.ll

 ; %exit.mainloop.at = 101
 
 define void @test_01(i32* %arr, i32* %a_len_ptr) #0 {
 
 ; CHECK-LABEL: test_01(
 ; CHECK-NOT:     preloop
 ; CHECK:         entry:
 ; CHECK-NEXT:      %len = load i32, i32* %a_len_ptr, !range !0
-; CHECK-NEXT:      [[SUB1:%[^ ]+]] = add i32 %len, -13
+; CHECK-NEXT:      [[SUB1:%[^ ]+]] = add nsw i32 %len, -13
 ; CHECK-NEXT:      [[CMP1:%[^ ]+]] = icmp slt i32 [[SUB1]], 101
 ; CHECK-NEXT:      [[SMAX:%[^ ]+]] = select i1 [[CMP1]], i32 [[SUB1]], i32 101
 ; CHECK-NEXT:      [[CMP2:%[^ ]+]] = icmp sgt i32 [[SMAX]], 0
 ; CHECK-NEXT:      %exit.mainloop.at = select i1 [[CMP2]], i32 [[SMAX]], i32 0
 ; CHECK-NEXT:      [[GOTO_LOOP:%[^ ]+]] = icmp slt i32 0, %exit.mainloop.at
 ; CHECK-NEXT:      br i1 [[GOTO_LOOP]], label %loop.preheader, label %main.pseudo.exit
 ; CHECK:         loop
 ; CHECK:           br i1 true, label %in.bounds

 ; %len = SINT_MAX
 ; %exit.mainloop.at = 101
 
 define void @test_02(i32* %arr, i32* %a_len_ptr) #0 {
 
 ; CHECK-LABEL: test_02(
 ; CHECK:         entry:
 ; CHECK-NEXT:      %len = load i32, i32* %a_len_ptr, !range !0
-; CHECK-NEXT:      [[LEN_MINUS_SMAX:%[^ ]+]] = add i32 %len, -2147483647
+; CHECK-NEXT:      [[LEN_MINUS_SMAX:%[^ ]+]] = add nuw nsw i32 %len, -2147483647
 ; CHECK-NEXT:      [[CMP1:%[^ ]+]] = icmp sgt i32 [[LEN_MINUS_SMAX]], -13
 ; CHECK-NEXT:      [[SMAX1:%[^ ]+]] = select i1 [[CMP1]], i32 [[LEN_MINUS_SMAX]], i32 -13
-; CHECK-NEXT:      [[SUB1:%[^ ]+]] = sub i32 %len, [[SMAX1]]
+; CHECK-NEXT:      [[SUB1:%[^ ]+]] = sub nuw nsw i32 %len, [[SMAX1]]
 ; CHECK-NEXT:      [[CMP2:%[^ ]+]] = icmp slt i32 [[SUB1]], 101
 ; CHECK-NEXT:      [[SMAX2:%[^ ]+]] = select i1 [[CMP2]], i32 [[SUB1]], i32 101
 ; CHECK-NEXT:      [[CMP3:%[^ ]+]] = icmp sgt i32 [[SMAX2]], 0
 ; CHECK-NEXT:      %exit.mainloop.at = select i1 [[CMP3]], i32 [[SMAX2]], i32 0
 ; CHECK-NEXT:      br i1 true, label %loop.preloop.preheader
 ; CHECK:         loop.preloop:
 ; CHECK-NEXT:      %idx.preloop = phi i32 [ %idx.next.preloop, %in.bounds.preloop ], [ 0, %loop.preloop.preheader ]
 ; CHECK-NEXT:      %idx.next.preloop = add i32 %idx.preloop, 1

 ; %len = SINT_MAX
 ; %exit.mainloop.at = 101
 
 define void @test_04(i32* %arr, i32* %a_len_ptr) #0 {
 
 ; CHECK-LABEL: test_04(
 ; CHECK:         entry:
 ; CHECK-NEXT:      %len = load i32, i32* %a_len_ptr, !range !0
-; CHECK-NEXT:      [[SUB1:%[^ ]+]] = add i32 %len, 13
+; CHECK-NEXT:      [[SUB1:%[^ ]+]] = add nuw i32 %len, 13
 ; CHECK-NEXT:      [[CMP1:%[^ ]+]] = icmp ult i32 [[SUB1]], 101
 ; CHECK-NEXT:      %exit.mainloop.at = select i1 [[CMP1]], i32 [[SUB1]], i32 101
 ; CHECK-NEXT:      br i1 true, label %loop.preloop.preheader
 ; CHECK:         in.bounds.preloop:
 ; CHECK-NEXT:      %addr.preloop = getelementptr i32, i32* %arr, i32 %idx.preloop
 ; CHECK-NEXT:      store i32 0, i32* %addr.preloop
 ; CHECK-NEXT:      %next.preloop = icmp ult i32 %idx.next.preloop, 101
 ; CHECK-NEXT:      [[PRELOOP_COND:%[^ ]+]] = icmp ult i32 %idx.next.preloop, 13

 
 ; Signed latch, signed RC, positive offset. Same as test_01.
 define void @test_05(i32* %arr, i32* %a_len_ptr) #0 {
 
 ; CHECK-LABEL: test_05(
 ; CHECK-NOT:     preloop
 ; CHECK:         entry:
 ; CHECK-NEXT:      %len = load i32, i32* %a_len_ptr, !range !0
-; CHECK-NEXT:      [[SUB1:%[^ ]+]] = add i32 %len, -13
+; CHECK-NEXT:      [[SUB1:%[^ ]+]] = add nsw i32 %len, -13
 ; CHECK-NEXT:      [[CMP1:%[^ ]+]] = icmp slt i32 [[SUB1]], 101
 ; CHECK-NEXT:      [[SMAX:%[^ ]+]] = select i1 [[CMP1]], i32 [[SUB1]], i32 101
 ; CHECK-NEXT:      [[CMP2:%[^ ]+]] = icmp sgt i32 [[SMAX]], 0
 ; CHECK-NEXT:      %exit.mainloop.at = select i1 [[CMP2]], i32 [[SMAX]], i32 0
 ; CHECK-NEXT:      [[GOTO_LOOP:%[^ ]+]] = icmp slt i32 0, %exit.mainloop.at
 ; CHECK-NEXT:      br i1 [[GOTO_LOOP]], label %loop.preheader, label %main.pseudo.exit
 ; CHECK:         loop
 ; CHECK:           br i1 true, label %in.bounds

 }
 
 ; Signed latch, signed RC, negative offset. Same as test_02.
 define void @test_06(i32* %arr, i32* %a_len_ptr) #0 {
 
 ; CHECK-LABEL: test_06(
 ; CHECK:         entry:
 ; CHECK-NEXT:      %len = load i32, i32* %a_len_ptr, !range !0
-; CHECK-NEXT:      [[LEN_MINUS_SMAX:%[^ ]+]] = add i32 %len, -2147483647
+; CHECK-NEXT:      [[LEN_MINUS_SMAX:%[^ ]+]] = add nuw nsw i32 %len, -2147483647
 ; CHECK-NEXT:      [[CMP1:%[^ ]+]] = icmp sgt i32 [[LEN_MINUS_SMAX]], -13
 ; CHECK-NEXT:      [[SMAX1:%[^ ]+]] = select i1 [[CMP1]], i32 [[LEN_MINUS_SMAX]], i32 -13
-; CHECK-NEXT:      [[SUB1:%[^ ]+]] = sub i32 %len, [[SMAX1]]
+; CHECK-NEXT:      [[SUB1:%[^ ]+]] = sub nuw nsw i32 %len, [[SMAX1]]
 ; CHECK-NEXT:      [[CMP2:%[^ ]+]] = icmp slt i32 [[SUB1]], 101
 ; CHECK-NEXT:      [[SMAX2:%[^ ]+]] = select i1 [[CMP2]], i32 [[SUB1]], i32 101
 ; CHECK-NEXT:      [[CMP3:%[^ ]+]] = icmp sgt i32 [[SMAX2]], 0
 ; CHECK-NEXT:      %exit.mainloop.at = select i1 [[CMP3]], i32 [[SMAX2]], i32 0
 ; CHECK-NEXT:      br i1 true, label %loop.preloop.preheader
 ; CHECK:         in.bounds.preloop:
 ; CHECK-NEXT:      %addr.preloop = getelementptr i32, i32* %arr, i32 %idx.preloop
 ; CHECK-NEXT:      store i32 0, i32* %addr.preloop

 }
 
 ; Unsigned latch, Unsigned RC, negative offset. Same as test_04.
 define void @test_08(i32* %arr, i32* %a_len_ptr) #0 {
 
 ; CHECK-LABEL: test_08(
 ; CHECK:         entry:
 ; CHECK-NEXT:      %len = load i32, i32* %a_len_ptr, !range !0
-; CHECK-NEXT:      [[SUB1:%[^ ]+]] = add i32 %len, 13
+; CHECK-NEXT:      [[SUB1:%[^ ]+]] = add nuw i32 %len, 13
 ; CHECK-NEXT:      [[CMP1:%[^ ]+]] = icmp ult i32 [[SUB1]], 101
 ; CHECK-NEXT:      %exit.mainloop.at = select i1 [[CMP1]], i32 [[SUB1]], i32 101
 ; CHECK-NEXT:      br i1 true, label %loop.preloop.preheader
 ; CHECK:         in.bounds.preloop:
 ; CHECK-NEXT:      %addr.preloop = getelementptr i32, i32* %arr, i32 %idx.preloop
 ; CHECK-NEXT:      store i32 0, i32* %addr.preloop
 ; CHECK-NEXT:      %next.preloop = icmp ult i32 %idx.next.preloop, 101
 ; CHECK-NEXT:      [[PRELOOP_COND:%[^ ]+]] = icmp ult i32 %idx.next.preloop, 13

llvm/trunk/test/Transforms/IRCE/rc-negative-bound.ll

 ; CHECK-LABEL: @test_03(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 0
 ; CHECK-NEXT:    br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
 ; CHECK:       loop.preheader:
 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[BOUND:%.*]], -2147483647
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i32 [[TMP0]], 0
 ; CHECK-NEXT:    [[SMIN:%.*]] = select i1 [[TMP1]], i32 [[TMP0]], i32 0
-; CHECK-NEXT:    [[TMP2:%.*]] = sub i32 [[BOUND]], [[SMIN]]
+; CHECK-NEXT:    [[TMP2:%.*]] = sub nsw i32 [[BOUND]], [[SMIN]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp slt i32 [[BOUND]], 0
 ; CHECK-NEXT:    [[SMAX:%.*]] = select i1 [[TMP3]], i32 [[BOUND]], i32 0
 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp sgt i32 [[SMAX]], -1
 ; CHECK-NEXT:    [[SMIN1:%.*]] = select i1 [[TMP4]], i32 [[SMAX]], i32 -1
 ; CHECK-NEXT:    [[TMP5:%.*]] = add i32 [[SMIN1]], 1
 ; CHECK-NEXT:    [[TMP6:%.*]] = mul i32 [[TMP2]], [[TMP5]]
 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp slt i32 [[N]], [[TMP6]]
 ; CHECK-NEXT:    [[SMAX2:%.*]] = select i1 [[TMP7]], i32 [[N]], i32 [[TMP6]]

 ; CHECK-LABEL: @test_07(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 0
 ; CHECK-NEXT:    br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
 ; CHECK:       loop.preheader:
 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[BOUND:%.*]], -2147483647
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i32 [[TMP0]], 0
 ; CHECK-NEXT:    [[SMIN:%.*]] = select i1 [[TMP1]], i32 [[TMP0]], i32 0
-; CHECK-NEXT:    [[TMP2:%.*]] = sub i32 [[BOUND]], [[SMIN]]
+; CHECK-NEXT:    [[TMP2:%.*]] = sub nsw i32 [[BOUND]], [[SMIN]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp slt i32 [[BOUND]], 0
 ; CHECK-NEXT:    [[SMAX:%.*]] = select i1 [[TMP3]], i32 [[BOUND]], i32 0
 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp sgt i32 [[SMAX]], -1
 ; CHECK-NEXT:    [[SMIN1:%.*]] = select i1 [[TMP4]], i32 [[SMAX]], i32 -1
 ; CHECK-NEXT:    [[TMP5:%.*]] = add i32 [[SMIN1]], 1
 ; CHECK-NEXT:    [[TMP6:%.*]] = mul i32 [[TMP2]], [[TMP5]]
 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp slt i32 [[N]], [[TMP6]]
 ; CHECK-NEXT:    [[SMAX2:%.*]] = select i1 [[TMP7]], i32 [[N]], i32 [[TMP6]]

llvm/trunk/test/Transforms/IRCE/single-access-no-preloop.ll

 
  exit:
   ret void
 }
 
 ; CHECK-LABEL: @single_access_no_preloop_with_offset(
 
 ; CHECK: loop.preheader:
-; CHECK: [[safe_range_end:[^ ]+]] = add i32 %len, -4
+; CHECK: [[safe_range_end:[^ ]+]] = add nsw i32 %len, -4
 ; CHECK: [[exit_main_loop_at_hiclamp_cmp:[^ ]+]] = icmp slt i32 %n, [[safe_range_end]]
 ; CHECK: [[exit_main_loop_at_hiclamp:[^ ]+]] = select i1 [[exit_main_loop_at_hiclamp_cmp]], i32 %n, i32 [[safe_range_end]]
 ; CHECK: [[exit_main_loop_at_loclamp_cmp:[^ ]+]] = icmp sgt i32 [[exit_main_loop_at_hiclamp]], 0
 ; CHECK: [[exit_main_loop_at_loclamp:[^ ]+]] = select i1 [[exit_main_loop_at_loclamp_cmp]], i32 [[exit_main_loop_at_hiclamp]], i32 0
 ; CHECK: [[enter_main_loop:[^ ]+]] = icmp slt i32 0, [[exit_main_loop_at_loclamp]]
 ; CHECK: br i1 [[enter_main_loop]], label %[[loop_preheader:[^ ,]+]], label %main.pseudo.exit
 
 ; CHECK: loop:

llvm/trunk/test/Transforms/IRCE/single-access-with-preloop.ll

exit:
   ret void
 }
 
 ; CHECK-LABEL: @single_access_with_preloop(
 ; CHECK: loop.preheader:
 ; CHECK: [[check_min_sint_offset:[^ ]+]] = icmp sgt i32 %offset, -2147483647
 ; CHECK: [[safe_offset_preloop:[^ ]+]] = select i1 [[check_min_sint_offset]], i32 %offset, i32 -2147483647
 ; If Offset was a SINT_MIN, we could have an overflow here. That is why we calculated its safe version.
-; CHECK: [[safe_start:[^ ]+]] = sub i32 0, [[safe_offset_preloop]]
+; CHECK: [[safe_start:[^ ]+]] = sub nsw i32 0, [[safe_offset_preloop]]
 ; CHECK: [[exit_preloop_at_cond_loclamp:[^ ]+]] = icmp slt i32 %n, [[safe_start]]
 ; CHECK: [[exit_preloop_at_loclamp:[^ ]+]] = select i1 [[exit_preloop_at_cond_loclamp]], i32 %n, i32 [[safe_start]]
 ; CHECK: [[exit_preloop_at_cond:[^ ]+]] = icmp sgt i32 [[exit_preloop_at_loclamp]], 0
 ; CHECK: [[exit_preloop_at:[^ ]+]] = select i1 [[exit_preloop_at_cond]], i32 [[exit_preloop_at_loclamp]], i32 0
 
 
-; CHECK: [[len_minus_sint_max:[^ ]+]] = add i32 %len, -2147483647
+; CHECK: [[len_minus_sint_max:[^ ]+]] = add nuw nsw i32 %len, -2147483647
 ; CHECK: [[check_len_min_sint_offset:[^ ]+]] = icmp sgt i32 %offset, [[len_minus_sint_max]]
 ; CHECK: [[safe_offset_mainloop:[^ ]+]] = select i1 [[check_len_min_sint_offset]], i32 %offset, i32 [[len_minus_sint_max]]
 ; If Offset was a SINT_MIN, we could have an overflow here. That is why we calculated its safe version.
-; CHECK: [[safe_upper_end:[^ ]+]] = sub i32 %len, [[safe_offset_mainloop]]
+; CHECK: [[safe_upper_end:[^ ]+]] = sub nsw i32 %len, [[safe_offset_mainloop]]
 ; CHECK: [[exit_mainloop_at_cond_loclamp:[^ ]+]] = icmp slt i32 %n, [[safe_upper_end]]
 ; CHECK: [[exit_mainloop_at_loclamp:[^ ]+]] = select i1 [[exit_mainloop_at_cond_loclamp]], i32 %n, i32 [[safe_upper_end]]
 ; CHECK: [[check_offset_mainloop_2:[^ ]+]] = icmp sgt i32 %offset, 0
 ; CHECK: [[safe_offset_mainloop_2:[^ ]+]] = select i1 [[check_offset_mainloop_2]], i32 %offset, i32 0
-; CHECK: [[safe_lower_end:[^ ]+]] = sub i32 2147483647, [[safe_offset_mainloop_2]]
+; CHECK: [[safe_lower_end:[^ ]+]] = sub nsw i32 2147483647, [[safe_offset_mainloop_2]]
 ; CHECK: [[exit_mainloop_at_cond_hiclamp:[^ ]+]] = icmp slt i32 [[exit_mainloop_at_loclamp]], [[safe_lower_end]]
 ; CHECK: [[exit_mainloop_at_hiclamp:[^ ]+]] = select i1 [[exit_mainloop_at_cond_hiclamp]], i32 [[exit_mainloop_at_loclamp]], i32 [[safe_lower_end]]
 ; CHECK: [[exit_mainloop_at_cmp:[^ ]+]] = icmp sgt i32 [[exit_mainloop_at_hiclamp]], 0
 ; CHECK: [[exit_mainloop_at:[^ ]+]] = select i1 [[exit_mainloop_at_cmp]], i32 [[exit_mainloop_at_hiclamp]], i32 0
 
 ; CHECK: mainloop:
 ; CHECK: br label %loop
 

llvm/trunk/test/Transforms/IRCE/stride_more_than_1.ll

 }
 
 ; IV = 100; IV >s -1; IV -= 7; 0 <= Len <= 50. IRCE is allowed.
 define void @test_05(i32* %arr, i32* %a_len_ptr) {
 
 ; CHECK:      @test_05(
 ; CHECK:      entry:
 ; CHECK-NEXT:   %len = load i32, i32* %a_len_ptr
-; CHECK-NEXT:   %exit.preloop.at = add i32 %len, -1
+; CHECK-NEXT:   %exit.preloop.at = add nsw i32 %len, -1
 ; CHECK-NEXT:   [[COND1:%[^ ]+]] = icmp sgt i32 100, %exit.preloop.at
 ; CHECK-NEXT:   br i1 [[COND1]], label %loop.preloop.preheader, label %preloop.pseudo.exit
 ; CHECK:      loop.preloop.preheader:
 ; CHECK-NEXT:   br label %loop.preloop
 ; CHECK:      mainloop:
 ; CHECK-NEXT:   br label %loop
 ; CHECK:      loop:
 ; CHECK-NEXT:   %idx = phi i32 [ %idx.preloop.copy, %mainloop ], [ %idx.next, %in.bounds ]

 }
 
 ; IV = MAX_INT - 7; IV >u 6; IV -= 7; 10 <= Len <= 50. IRCE is allowed.
 define void @test_06(i32* %arr, i32* %a_len_ptr) {
 
 ; CHECK:      @test_06(
 ; CHECK:      entry:
 ; CHECK-NEXT:   %len = load i32, i32* %a_len_ptr
-; CHECK-NEXT:   %exit.preloop.at = add i32 %len, -1
+; CHECK-NEXT:   %exit.preloop.at = add nsw i32 %len, -1
 ; CHECK-NEXT:   [[COND1:%[^ ]+]] = icmp ugt i32 2147483640, %exit.preloop.at
 ; CHECK-NEXT:   br i1 [[COND1]], label %loop.preloop.preheader, label %preloop.pseudo.exit
 ; CHECK:      loop.preloop.preheader:
 ; CHECK-NEXT:   br label %loop.preloop
 ; CHECK:      mainloop:
 ; CHECK-NEXT:   br label %loop
 ; CHECK:      loop:
 ; CHECK-NEXT:   %idx = phi i32 [ %idx.preloop.copy, %mainloop ], [ %idx.next, %in.bounds ]

 }
 
 ; IV = MAX_INT; IV >u 6; IV -= 7; 10 <= Len <= 50. IRCE is allowed.
 define void @test_08(i32* %arr, i32* %a_len_ptr) {
 
 ; CHECK:      @test_08(
 ; CHECK:      entry:
 ; CHECK-NEXT:   %len = load i32, i32* %a_len_ptr
-; CHECK-NEXT:   %exit.preloop.at = add i32 %len, -1
+; CHECK-NEXT:   %exit.preloop.at = add nsw i32 %len, -1
 ; CHECK-NEXT:   [[COND1:%[^ ]+]] = icmp ugt i32 2147483647, %exit.preloop.at
 ; CHECK-NEXT:   br i1 [[COND1]], label %loop.preloop.preheader, label %preloop.pseudo.exit
 ; CHECK:      loop.preloop.preheader:
 ; CHECK-NEXT:   br label %loop.preloop
 ; CHECK:      mainloop:
 ; CHECK-NEXT:   br label %loop
 ; CHECK:      loop:
 ; CHECK-NEXT:   %idx = phi i32 [ %idx.preloop.copy, %mainloop ], [ %idx.next, %in.bounds ]

llvm/trunk/test/Transforms/IRCE/unsigned_comparisons_ugt.ll

 ; UGT condition for decreasing loop.
 define void @test_02(i32* %arr, i32* %a_len_ptr) #0 {
 
 ; CHECK: test_02(
 ; CHECK:        entry:
 ; CHECK-NEXT:     %len = load i32, i32* %a_len_ptr, !range !0
 ; CHECK-NEXT:     [[COND1:%[^ ]+]] = icmp ugt i32 %len, 1
 ; CHECK-NEXT:     [[UMIN:%[^ ]+]] = select i1 [[COND1]], i32 %len, i32 1
-; CHECK-NEXT:     %exit.preloop.at = add i32 [[UMIN]], -1
+; CHECK-NEXT:     %exit.preloop.at = add nsw i32 [[UMIN]], -1
 ; CHECK-NEXT:     [[COND2:%[^ ]+]] = icmp ugt i32 100, %exit.preloop.at
 ; CHECK-NEXT:     br i1 [[COND2]], label %loop.preloop.preheader, label %preloop.pseudo.exit
 ; CHECK:        mainloop:
 ; CHECK-NEXT:     br label %loop
 ; CHECK:        loop:
 ; CHECK-NEXT:     %idx = phi i32 [ %idx.preloop.copy, %mainloop ], [ %idx.next, %in.bounds ]
 ; CHECK-NEXT:     %idx.next = add i32 %idx, -1
 ; CHECK-NEXT:     %abc = icmp ult i32 %idx, %len

 ; Check SINT_MAX + 1, test is similar to test_02.
 define void @test_04(i32* %arr, i32* %a_len_ptr) #0 {
 
 ; CHECK: test_04(
 ; CHECK:        entry:
 ; CHECK-NEXT:     %len = load i32, i32* %a_len_ptr, !range !0
 ; CHECK-NEXT:     [[COND1:%[^ ]+]] = icmp ugt i32 %len, 1
 ; CHECK-NEXT:     [[UMIN:%[^ ]+]] = select i1 [[COND1]], i32 %len, i32 1
-; CHECK-NEXT:     %exit.preloop.at = add i32 [[UMIN]], -1
+; CHECK-NEXT:     %exit.preloop.at = add nsw i32 [[UMIN]], -1
 ; CHECK-NEXT:     [[COND2:%[^ ]+]] = icmp ugt i32 -2147483648, %exit.preloop.at
 ; CHECK-NEXT:     br i1 [[COND2]], label %loop.preloop.preheader, label %preloop.pseudo.exit
 ; CHECK:        mainloop:
 ; CHECK-NEXT:     br label %loop
 ; CHECK:        loop:
 ; CHECK-NEXT:     %idx = phi i32 [ %idx.preloop.copy, %mainloop ], [ %idx.next, %in.bounds ]
 ; CHECK-NEXT:     %idx.next = add i32 %idx, -1
 ; CHECK-NEXT:     %abc = icmp ult i32 %idx, %len

llvm/trunk/test/Transforms/IRCE/unsigned_comparisons_ult.ll

 ; ULT condition for decreasing loops.
 define void @test_02(i32* %arr, i32* %a_len_ptr) #0 {
 
 ; CHECK: test_02(
 ; CHECK:        entry:
 ; CHECK-NEXT:     %len = load i32, i32* %a_len_ptr, !range !0
 ; CHECK-NEXT:     [[COND1:%[^ ]+]] = icmp ugt i32 %len, 1
 ; CHECK-NEXT:     [[UMIN:%[^ ]+]] = select i1 [[COND1]], i32 %len, i32 1
-; CHECK-NEXT:     %exit.preloop.at = add i32 [[UMIN]], -1
+; CHECK-NEXT:     %exit.preloop.at = add nsw i32 [[UMIN]], -1
 ; CHECK-NEXT:     [[COND2:%[^ ]+]] = icmp ugt i32 100, %exit.preloop.at
 ; CHECK-NEXT:     br i1 [[COND2]], label %loop.preloop.preheader, label %preloop.pseudo.exit
 ; CHECK:        mainloop:
 ; CHECK-NEXT:     br label %loop
 ; CHECK:        loop:
 ; CHECK-NEXT:     %idx = phi i32 [ %idx.preloop.copy, %mainloop ], [ %idx.next, %in.bounds ]
 ; CHECK-NEXT:     %idx.next = add i32 %idx, -1
 ; CHECK-NEXT:     %abc = icmp ult i32 %idx, %len

 
 ; Check SINT_MAX + 1, test is similar to test_02.
 define void @test_05(i32* %arr, i32* %a_len_ptr) #0 {
 ; CHECK: test_05(
 ; CHECK:        entry:
 ; CHECK-NEXT:     %len = load i32, i32* %a_len_ptr, !range !0
 ; CHECK-NEXT:     [[COND1:%[^ ]+]] = icmp ugt i32 %len, 1
 ; CHECK-NEXT:     [[UMIN:%[^ ]+]] = select i1 [[COND1]], i32 %len, i32 1
-; CHECK-NEXT:     %exit.preloop.at = add i32 [[UMIN]], -1
+; CHECK-NEXT:     %exit.preloop.at = add nsw i32 [[UMIN]], -1
 ; CHECK-NEXT:     [[COND2:%[^ ]+]] = icmp ugt i32 -2147483648, %exit.preloop.at
 ; CHECK-NEXT:     br i1 [[COND2]], label %loop.preloop.preheader, label %preloop.pseudo.exit
 ; CHECK:        mainloop:
 ; CHECK-NEXT:     br label %loop
 ; CHECK:        loop:
 ; CHECK-NEXT:     %idx = phi i32 [ %idx.preloop.copy, %mainloop ], [ %idx.next, %in.bounds ]
 ; CHECK-NEXT:     %idx.next = add i32 %idx, -1
 ; CHECK-NEXT:     %abc = icmp ult i32 %idx, %len

llvm/trunk/test/Transforms/IndVarSimplify/lftr.ll

 define void @test_udiv_as_shift(i8* %a, i8 %n) nounwind uwtable ssp {
 ; CHECK-LABEL: @test_udiv_as_shift(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[E:%.*]] = icmp sgt i8 [[N:%.*]], 3
 ; CHECK-NEXT:    br i1 [[E]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
 ; CHECK:       loop.preheader:
 ; CHECK-NEXT:    [[TMP0:%.*]] = add i8 [[N]], 3
 ; CHECK-NEXT:    [[TMP1:%.*]] = lshr i8 [[TMP0]], 2
-; CHECK-NEXT:    [[TMP2:%.*]] = add i8 [[TMP1]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = add nuw nsw i8 [[TMP1]], 1
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[I1:%.*]] = phi i8 [ [[I1_INC:%.*]], [[LOOP]] ], [ 0, [[LOOP_PREHEADER]] ]
 ; CHECK-NEXT:    [[I1_INC]] = add nuw nsw i8 [[I1]], 1
 ; CHECK-NEXT:    store volatile i8 0, i8* [[A:%.*]]
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i8 [[I1_INC]], [[TMP2]]
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
 ; CHECK:       exit.loopexit:

llvm/trunk/test/Transforms/IndVarSimplify/loop_evaluate_1.ll

loopexit:               ; preds = %loopentry
         ret i32 %tmp.2
 }
 
 
 ; PR12377
 ; CHECK-LABEL: @test2
 ; CHECK: [[VAR1:%.+]] = add i32 %arg, -11
 ; CHECK: [[VAR2:%.+]] = lshr i32 [[VAR1]], 1
-; CHECK: [[VAR3:%.+]] = add i32 [[VAR2]], 1
+; CHECK: [[VAR3:%.+]] = add nuw i32 [[VAR2]], 1
 ; CHECK: [[VAR4:%.+]] = phi i32 [ 0, %bb ], [ [[VAR3]], %bb1.preheader ]
 ; CHECK: ret i32 [[VAR4]]
 define i32 @test2(i32 %arg) {
 bb:
   %tmp = icmp ugt i32 %arg, 10
   br i1 %tmp, label %bb1, label %bb7
 
 bb1:                                              ; preds = %bb1, %bb

llvm/trunk/test/Transforms/LoopIdiom/X86/unordered-atomic-memcpy.ll

 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 ;; memcpy.atomic formation (atomic load & store) -- element size 2
 define void @test6(i64 %Size) nounwind ssp {
 ; CHECK-LABEL: @test6(
-; CHECK: [[Sz:%[0-9]+]] = shl i64 %Size, 1
+; CHECK: [[Sz:%[0-9]+]] = shl nuw i64 %Size, 1
 ; CHECK: call void @llvm.memcpy.element.unordered.atomic.p0i8.p0i8.i64(i8* align 2 %Dest{{[0-9]*}}, i8* align 2 %Base{{[0-9]*}}, i64 [[Sz]], i32 2)
 ; CHECK-NOT: store
 ; CHECK: ret void
 bb.nph:
   %Base = alloca i16, i32 10000
   %Dest = alloca i16, i32 10000
   br label %for.body
 

 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 ;; memcpy.atomic formation (atomic load & store) -- element size 4
 define void @test7(i64 %Size) nounwind ssp {
 ; CHECK-LABEL: @test7(
-; CHECK: [[Sz:%[0-9]+]] = shl i64 %Size, 2
+; CHECK: [[Sz:%[0-9]+]] = shl nuw i64 %Size, 2
 ; CHECK: call void @llvm.memcpy.element.unordered.atomic.p0i8.p0i8.i64(i8* align 4 %Dest{{[0-9]*}}, i8* align 4 %Base{{[0-9]*}}, i64 [[Sz]], i32 4)
 ; CHECK-NOT: store
 ; CHECK: ret void
 bb.nph:
   %Base = alloca i32, i32 10000
   %Dest = alloca i32, i32 10000
   br label %for.body
 

 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 ;; memcpy.atomic formation (atomic load & store) -- element size 8
 define void @test8(i64 %Size) nounwind ssp {
 ; CHECK-LABEL: @test8(
-; CHECK: [[Sz:%[0-9]+]] = shl i64 %Size, 3
+; CHECK: [[Sz:%[0-9]+]] = shl nuw i64 %Size, 3
 ; CHECK: call void @llvm.memcpy.element.unordered.atomic.p0i8.p0i8.i64(i8* align 8 %Dest{{[0-9]*}}, i8* align 8 %Base{{[0-9]*}}, i64 [[Sz]], i32 8)
 ; CHECK-NOT: store
 ; CHECK: ret void
 bb.nph:
   %Base = alloca i64, i32 10000
   %Dest = alloca i64, i32 10000
   br label %for.body
 

 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 ;; memcpy.atomic formation rejection (atomic load & store) -- element size 16
 define void @test9(i64 %Size) nounwind ssp {
 ; CHECK-LABEL: @test9(
-; CHECK: [[Sz:%[0-9]+]] = shl i64 %Size, 4
+; CHECK: [[Sz:%[0-9]+]] = shl nuw i64 %Size, 4
 ; CHECK: call void @llvm.memcpy.element.unordered.atomic.p0i8.p0i8.i64(i8* align 16 %Dest{{[0-9]*}}, i8* align 16 %Base{{[0-9]*}}, i64 [[Sz]], i32 16)
 ; CHECK-NOT: store
 ; CHECK: ret void
 bb.nph:
   %Base = alloca i128, i32 10000
   %Dest = alloca i128, i32 10000
   br label %for.body
 

llvm/trunk/test/Transforms/LoopIdiom/basic.ll

for.body:                                         ; preds = %bb.nph, %for.body
   %indvar.next = add i64 %indvar, 1
   %exitcond = icmp eq i64 %indvar.next, %Size
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 ; CHECK-LABEL: @test1_i16(
 ; CHECK: %[[BaseBC:.*]] = bitcast i16* %Base to i8*
-; CHECK: %[[Sz:[0-9]+]] = shl i64 %Size, 1
+; CHECK: %[[Sz:[0-9]+]] = shl nuw i64 %Size, 1
 ; CHECK: call void @llvm.memset.p0i8.i64(i8* align 2 %[[BaseBC]], i8 0, i64 %[[Sz]], i1 false)
 ; CHECK-NOT: store
 }
 
 ; This is a loop that was rotated but where the blocks weren't merged.  This
 ; shouldn't perturb us.
 define void @test1a(i8* %Base, i64 %Size) nounwind ssp {
 bb.nph:                                           ; preds = %entry
for.body:                                         ; preds = %entry, %for.body
   %inc = add nsw i64 %i.011, 1
   %exitcond = icmp eq i64 %inc, %Size
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 ; CHECK-LABEL: @test2(
 ; CHECK: br i1 %cmp10,
-; CHECK: %0 = shl i64 %Size, 2
+; CHECK: %0 = shl nuw i64 %Size, 2
 ; CHECK: call void @llvm.memset.p0i8.i64(i8* align 4 %Base1, i8 1, i64 %0, i1 false)
 ; CHECK-NOT: store
 }
 
 ; This is a case where there is an extra may-aliased store in the loop, we can't
 ; promote the memset.
 define void @test3(i32* %Base, i64 %Size, i8 *%MayAlias) nounwind ssp {
 entry:
for.body:                                         ; preds = %bb.nph, %for.body
   %exitcond = icmp eq i64 %indvar.next, %Size
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 ; CHECK-LABEL: @test6_dest_align(
 ; CHECK: %[[Dst:.*]] = bitcast i32* %Dest to i8*
 ; CHECK: %[[Src:.*]] = bitcast i32* %Base to i8*
-; CHECK: %[[Sz:[0-9]+]] = shl i64 %Size, 2
+; CHECK: %[[Sz:[0-9]+]] = shl nuw i64 %Size, 2
 ; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 4 %[[Dst]], i8* align 1 %[[Src]], i64 %[[Sz]], i1 false)
 ; CHECK-NOT: store
 ; CHECK: ret void
 }
 
 ;; memcpy formation, check alignment
 define void @test6_src_align(i32* noalias align 4 %Base, i32* noalias align 1 %Dest, i64 %Size) nounwind ssp {
 bb.nph:
for.body:                                         ; preds = %bb.nph, %for.body
   %exitcond = icmp eq i64 %indvar.next, %Size
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 ; CHECK-LABEL: @test6_src_align(
 ; CHECK: %[[Dst]] = bitcast i32* %Dest to i8*
 ; CHECK: %[[Src]] = bitcast i32* %Base to i8*
-; CHECK: %[[Sz:[0-9]+]] = shl i64 %Size, 2
+; CHECK: %[[Sz:[0-9]+]] = shl nuw i64 %Size, 2
 ; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 1 %[[Dst]], i8* align 4 %[[Src]], i64 %[[Sz]], i1 false)
 ; CHECK-NOT: store
 ; CHECK: ret void
 }
 
 
 ; This is a loop that was rotated but where the blocks weren't merged.  This
 ; shouldn't perturb us.

 ; CHECK:       entry:
 ; CHECK:         %[[C1:.*]] = icmp sgt i32 %size, 0
 ; CHECK-NEXT:    br i1 %[[C1]], label %loop.ph, label %exit
 
 loop.ph:
   br label %loop.body
 ; CHECK:       loop.ph:
 ; CHECK-NEXT:    %[[ZEXT_SIZE:.*]] = zext i32 %size to i64
-; CHECK-NEXT:    %[[SCALED_SIZE:.*]] = shl i64 %[[ZEXT_SIZE]], 3
+; CHECK-NEXT:    %[[SCALED_SIZE:.*]] = shl nuw nsw i64 %[[ZEXT_SIZE]], 3
 ; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 8 %{{.*}}, i8 0, i64 %[[SCALED_SIZE]], i1 false)
 
 loop.body:
   %storemerge4 = phi i32 [ 0, %loop.ph ], [ %inc, %loop.body ]
   %idxprom = sext i32 %storemerge4 to i64
   %arrayidx = getelementptr inbounds i64, i64* %ptr, i64 %idxprom
   store i64 0, i64* %arrayidx, align 8
   %inc = add nsw i32 %storemerge4, 1

 ; CHECK:       entry:
 ; CHECK:         %[[C1:.*]] = icmp sgt i32 %size, 0
 ; CHECK-NEXT:    br i1 %[[C1]], label %loop.ph, label %exit
 
 loop.ph:
   br label %loop.body
 ; CHECK:       loop.ph:
 ; CHECK-NEXT:    %[[ZEXT_SIZE:.*]] = zext i32 %size to i64
-; CHECK-NEXT:    %[[SCALED_SIZE:.*]] = shl i64 %[[ZEXT_SIZE]], 3
+; CHECK-NEXT:    %[[SCALED_SIZE:.*]] = shl nuw nsw i64 %[[ZEXT_SIZE]], 3
 ; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 8 %{{.*}}, i8* align 8 %{{.*}}, i64 %[[SCALED_SIZE]], i1 false)
 
 loop.body:
   %storemerge4 = phi i32 [ 0, %loop.ph ], [ %inc, %loop.body ]
   %idxprom1 = sext i32 %storemerge4 to i64
   %arrayidx1 = getelementptr inbounds i64, i64* %src, i64 %idxprom1
   %v = load i64, i64* %arrayidx1, align 8
   %idxprom2 = sext i32 %storemerge4 to i64

llvm/trunk/test/Transforms/LoopIdiom/memcpy-debugify-remarks.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -basicaa -debugify -loop-idiom -pass-remarks=loop-idiom -pass-remarks-analysis=loop-idiom -verify -verify-each -verify-dom-info -verify-loop-info  < %s -S 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Check that everything still works when debuginfo is present, and that it is reasonably propagated.
 
 ; CHECK: remark: <stdin>:6:1: Formed a call to llvm.memcpy.p0i8.p0i8.i64() function
 
 define void @test6_dest_align(i32* noalias align 1 %Base, i32* noalias align 4 %Dest, i64 %Size) nounwind ssp {
 ; CHECK-LABEL: @test6_dest_align(
 ; CHECK-NEXT:  bb.nph:
 ; CHECK-NEXT:    [[DEST1:%.*]] = bitcast i32* [[DEST:%.*]] to i8*
 ; CHECK-NEXT:    [[BASE2:%.*]] = bitcast i32* [[BASE:%.*]] to i8*
-; CHECK-NEXT:    [[TMP0:%.*]] = shl i64 [[SIZE:%.*]], 2, !dbg !18
+; CHECK-NEXT:    [[TMP0:%.*]] = shl nuw i64 [[SIZE:%.*]], 2, !dbg !18
 ; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 4 [[DEST1]], i8* align 1 [[BASE2]], i64 [[TMP0]], i1 false), !dbg !19
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]], !dbg !18
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ 0, [[BB_NPH:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[FOR_BODY]] ], !dbg !20
 ; CHECK-NEXT:    call void @llvm.dbg.value(metadata i64 [[INDVAR]], metadata !9, metadata !DIExpression()), !dbg !20
 ; CHECK-NEXT:    [[I_0_014:%.*]] = getelementptr i32, i32* [[BASE]], i64 [[INDVAR]], !dbg !21
 ; CHECK-NEXT:    call void @llvm.dbg.value(metadata i32* [[I_0_014]], metadata !11, metadata !DIExpression()), !dbg !21
 ; CHECK-NEXT:    [[DESTI:%.*]] = getelementptr i32, i32* [[DEST]], i64 [[INDVAR]], !dbg !22

llvm/trunk/test/Transforms/LoopReroll/basic.ll

 for.end:
   ret void
 }
 
 define void @pointer_bitcast_baseinst(i16* %arg, i8* %arg1, i64 %arg2) {
 ; CHECK-LABEL: @pointer_bitcast_baseinst(
 ; CHECK:       bb3:
 ; CHECK-NEXT:    %indvar = phi i64 [ %indvar.next, %bb3 ], [ 0, %bb ]
-; CHECK-NEXT:    %4 = shl i64 %indvar, 3
+; CHECK-NEXT:    %4 = shl nuw i64 %indvar, 3
 ; CHECK-NEXT:    %5 = add i64 %4, 1
 ; CHECK-NEXT:    %tmp5 = shl nuw i64 %5, 1
 ; CHECK-NEXT:    %tmp6 = getelementptr i8, i8* %arg1, i64 %tmp5
 ; CHECK-NEXT:    %tmp7 = bitcast i8* %tmp6 to <8 x i16>*
 ; CHECK-NEXT:    %tmp8 = load <8 x i16>, <8 x i16>* %tmp7, align 2
 ; CHECK-NEXT:    %tmp13 = getelementptr i16, i16* %arg, i64 %5
 ; CHECK-NEXT:    %tmp14 = bitcast i16* %tmp13 to <8 x i16>*
 ; CHECK-NEXT:    store <8 x i16> %tmp8, <8 x i16>* %tmp14, align 2

llvm/trunk/test/Transforms/LoopReroll/complex_reroll.ll

 while.body.preheader:                             ; preds = %entry
   br label %while.body
 
 while.body:                                       ; preds = %while.body.preheader, %while.body
 ;CHECK-LABEL: while.body:
 ;CHECK-NEXT:  %indvar = phi i64 [ %indvar.next, %while.body ], [ 0, %while.body.preheader ]
 ;CHECK-NEXT:  %S.012 = phi i32 [ %add, %while.body ], [ undef, %while.body.preheader ]
 ;CHECK-NEXT:  %4 = trunc i64 %indvar to i32
-;CHECK-NEXT:  %5 = mul i64 %indvar, -1
+;CHECK-NEXT:  %5 = mul nsw i64 %indvar, -1
 ;CHECK-NEXT:  %scevgep = getelementptr i32, i32* %buf, i64 %5
 ;CHECK-NEXT:  %6 = load i32, i32* %scevgep, align 4
 ;CHECK-NEXT:  %add = add nsw i32 %6, %S.012
 ;CHECK-NEXT:  %indvar.next = add i64 %indvar, 1
 ;CHECK-NEXT:  %exitcond = icmp eq i32 %4, %3
 ;CHECK-NEXT:  br i1 %exitcond, label %while.end.loopexit, label %while.body
 
   %i.013 = phi i32 [ %sub, %while.body ], [ %len, %while.body.preheader ]

llvm/trunk/test/Transforms/LoopReroll/nonconst_lb.ll

 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 ; CHECK-LABEL: @foo
 ; CHECK: for.body.preheader:                               ; preds = %entry
 ; CHECK:   %0 = add i32 %n, -1
 ; CHECK:   %1 = sub i32 %0, %m
 ; CHECK:   %2 = lshr i32 %1, 2
-; CHECK:   %3 = shl i32 %2, 2
+; CHECK:   %3 = shl nuw i32 %2, 2
 ; CHECK:   %4 = add i32 %3, 3
 ; CHECK:   br label %for.body
 
 ; CHECK: for.body:                                         ; preds = %for.body, %for.body.preheader
 ; CHECK:   %indvar = phi i32 [ 0, %for.body.preheader ], [ %indvar.next, %for.body ]
 ; CHECK:   %5 = add i32 %m, %indvar
 ; CHECK:   %arrayidx = getelementptr inbounds i32, i32* %B, i32 %5
 ; CHECK:   %6 = load i32, i32* %arrayidx, align 4
for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 ; CHECK-LABEL: @daxpy_ur
 ; CHECK: for.body.preheader:
 ; CHECK:   %0 = add i32 %n, -1
 ; CHECK:   %1 = sub i32 %0, %rem
 ; CHECK:   %2 = lshr i32 %1, 2
-; CHECK:   %3 = shl i32 %2, 2
+; CHECK:   %3 = shl nuw i32 %2, 2
 ; CHECK:   %4 = add i32 %3, 3
 ; CHECK:   br label %for.body
 
 ; CHECK: for.body:
 ; CHECK:   %indvar = phi i32 [ 0, %for.body.preheader ], [ %indvar.next, %for.body ]
 ; CHECK:   %5 = add i32 %rem, %indvar
 ; CHECK:   %arrayidx = getelementptr inbounds float, float* %dy, i32 %5
 ; CHECK:   %6 = load float, float* %arrayidx, align 4
 ; CHECK:   %arrayidx1 = getelementptr inbounds float, float* %dx, i32 %5
 ; CHECK:   %7 = load float, float* %arrayidx1, align 4
 ; CHECK:   %mul = fmul float %7, %da
 ; CHECK:   %add = fadd float %6, %mul
 ; CHECK:   store float %add, float* %arrayidx, align 4
 ; CHECK:   %indvar.next = add i32 %indvar, 1
 ; CHECK:   %exitcond = icmp eq i32 %indvar, %4
 ; CHECK:   br i1 %exitcond, label %for.end.loopexit, label %for.body

llvm/trunk/test/Transforms/LoopReroll/ptrindvar.ll

 
 while.body.preheader:
   br label %while.body
 
 while.body:
 ;CHECK-LABEL: while.body:
 ;CHECK-NEXT:    %indvar = phi i64 [ %indvar.next, %while.body ], [ 0, %while.body.preheader ]
 ;CHECK-NEXT:    %S.011 = phi i32 [ %add, %while.body ], [ undef, %while.body.preheader ]
-;CHECK-NEXT:    %4 = mul i64 %indvar, -1
+;CHECK-NEXT:    %4 = mul nsw i64 %indvar, -1
 ;CHECK-NEXT:    %scevgep = getelementptr i32, i32* %buf, i64 %4
 ;CHECK-NEXT:    %5 = load i32, i32* %scevgep, align 4
 ;CHECK-NEXT:    %add = add nsw i32 %5, %S.011
 ;CHECK-NEXT:    %indvar.next = add i64 %indvar, 1
 ;CHECK-NEXT:    %exitcond = icmp eq i64 %indvar, %3
 ;CHECK-NEXT:    br i1 %exitcond, label %while.end.loopexit, label %while.body
 
   %S.011 = phi i32 [ %add2, %while.body ], [ undef, %while.body.preheader ]

llvm/trunk/test/Transforms/LoopStrengthReduce/2011-10-06-ReusePhi.ll

 ; RUN: opt -loop-reduce -S < %s | FileCheck %s
 ;
 ; Test LSR's intelligence regarding phi reuse.
 ; Verify that scaled GEPs are not reused. rdar://5064068
 
 target triple = "x86_64-apple-darwin"
 
 ; Provide legal integer types.
 target datalayout = "n8:16:32:64"
 
 
 ; CHECK-LABEL: @test(
 ; multiplies are hoisted out of the loop
 ; CHECK: while.body.lr.ph:
-; CHECK: shl i64
-; CHECK: shl i64
+; CHECK: shl nsw i64
+; CHECK: shl nsw i64
 ; GEPs are ugly
 ; CHECK: while.body:
 ; CHECK: phi
 ; CHECK: phi
 ; CHECK: phi
 ; CHECK: phi
 ; CHECK-NOT: phi
 ; CHECK: bitcast float* {{.*}} to i1*

llvm/trunk/test/Transforms/LoopStrengthReduce/X86/lsr-expand-quadratic.ll

 ; CHECK:  %lsr.iv1 = phi i32 [ %lsr.iv.next2, %test2.loop ], [ -16777216, %entry ]
 ; CHECK:  %lsr.iv = phi i32 [ %lsr.iv.next, %test2.loop ], [ 1, %entry ]
 ; CHECK:  %lsr.iv.next = add nsw i32 %lsr.iv, -1
 ; CHECK:  %lsr.iv.next2 = add nsw i32 %lsr.iv1, 16777216
 ;
 ; CHECK-LABEL: for.end:
 ; CHECK:  %tobool.us = icmp eq i32 %lsr.iv.next, 0
 ; CHECK:  %sub.us = select i1 %tobool.us, i32 0, i32 0
-; CHECK:  %0 = sub i32 0, %sub.us
+; CHECK:  %0 = sub nuw nsw i32 0, %sub.us
 ; CHECK:  %1 = sub i32 %0, %lsr.iv.next
 ; CHECK:  %sext.us = mul i32 %lsr.iv.next2, %1
 ; CHECK:  %f = ashr i32 %sext.us, 24
 ; CHECK: ret i32 %f
 define i32 @test2() {
 entry:
   br label %test2.loop
 

llvm/trunk/test/Transforms/LoopStrengthReduce/X86/nested-loop.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -loop-reduce -S < %s | FileCheck %s
 
 ; Check when we use an outerloop induction variable inside of an innerloop
 ; induction value expr, LSR can still choose to use single induction variable
 ; for the innerloop and share it in multiple induction value exprs.
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @foo(i32 %size, i32 %nsteps, i32 %hsize, i32* %lined, i8* %maxarray) {
 ; CHECK-LABEL: @foo(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP215:%.*]] = icmp sgt i32 [[SIZE:%.*]], 1
 ; CHECK-NEXT:    [[T0:%.*]] = zext i32 [[SIZE]] to i64
 ; CHECK-NEXT:    [[T1:%.*]] = sext i32 [[NSTEPS:%.*]] to i64
-; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[T0]], -1
+; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i64 [[T0]], -1
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[LSR_IV1:%.*]] = phi i64 [ [[LSR_IV_NEXT2:%.*]], [[FOR_INC:%.*]] ], [ 1, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[INDVARS_IV2:%.*]] = phi i64 [ [[INDVARS_IV_NEXT3:%.*]], [[FOR_INC]] ], [ 0, [[ENTRY]] ]
 ; CHECK-NEXT:    br i1 [[CMP215]], label [[FOR_BODY2_PREHEADER:%.*]], label [[FOR_INC]]
 ; CHECK:       for.body2.preheader:
 ; CHECK-NEXT:    br label [[FOR_BODY2:%.*]]
 ; CHECK:       for.body2:

llvm/trunk/test/Transforms/LoopStrengthReduce/post-inc-icmpzero.ll

 ; RUN: opt -loop-reduce -S < %s | FileCheck %s
 ; PR9939
 
 ; LSR should properly handle the post-inc offset when folding the
 ; non-IV operand of an icmp into the IV.
 
 ; CHECK:   [[r1:%[a-z0-9\.]+]] = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
 ; CHECK:   [[r2:%[a-z0-9\.]+]] = lshr exact i64 [[r1]], 1
 ; CHECK:   [[r3:%[a-z0-9\.]+]] = bitcast i64 [[r2]] to i64
 ; CHECK: for.body.lr.ph:
-; CHECK:   [[r4:%[a-z0-9]+]] = shl i64 [[r3]], 1
+; CHECK:   [[r4:%[a-z0-9]+]] = shl nuw i64 [[r3]], 1
 ; CHECK:   br label %for.body
 ; CHECK: for.body:
 ; CHECK:   %lsr.iv2 = phi i64 [ %lsr.iv.next, %for.body ], [ [[r4]], %for.body.lr.ph ]
 ; CHECK:   %lsr.iv.next = add i64 %lsr.iv2, -2
 ; CHECK:   %lsr.iv.next3 = inttoptr i64 %lsr.iv.next to i16*
 ; CHECK:   %cmp27 = icmp eq i16* %lsr.iv.next3, null
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"

llvm/trunk/test/Transforms/LoopVectorize/AArch64/pr36032.ll

 ; CHECK-NEXT:    [[CONV:%.*]] = and i32 [[F_0]], 65535
 ; CHECK-NEXT:    br i1 [[CMP12]], label [[FOR_BODY_LR_PH:%.*]], label [[FOR_COND_CLEANUP]]
 ; CHECK:       for.body.lr.ph:
 ; CHECK-NEXT:    [[TMP0:%.*]] = zext i32 [[G_0]] to i64
 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i64 4, [[TMP0]]
 ; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[TMP1]], 4
 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_SCEVCHECK:%.*]]
 ; CHECK:       vector.scevcheck:
-; CHECK-NEXT:    [[TMP2:%.*]] = sub i64 3, [[TMP0]]
+; CHECK-NEXT:    [[TMP2:%.*]] = sub nsw i64 3, [[TMP0]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[G_0]], [[CONV]]
 ; CHECK-NEXT:    [[TMP4:%.*]] = trunc i64 [[TMP2]] to i32
 ; CHECK-NEXT:    [[MUL:%.*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 1, i32 [[TMP4]])
 ; CHECK-NEXT:    [[MUL_RESULT:%.*]] = extractvalue { i32, i1 } [[MUL]], 0
 ; CHECK-NEXT:    [[MUL_OVERFLOW:%.*]] = extractvalue { i32, i1 } [[MUL]], 1
 ; CHECK-NEXT:    [[TMP5:%.*]] = add i32 [[TMP3]], [[MUL_RESULT]]
 ; CHECK-NEXT:    [[TMP6:%.*]] = sub i32 [[TMP3]], [[MUL_RESULT]]
 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp ugt i32 [[TMP6]], [[TMP3]]

llvm/trunk/test/Transforms/LoopVectorize/X86/illegal-parallel-loop-uniform-write.ll

 define void @foo(i32* nocapture %a, i32* nocapture %b, i32 %k, i32 %m) #0 {
 ; CHECK-LABEL: @foo(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP27:%.*]] = icmp sgt i32 [[M:%.*]], 0
 ; CHECK-NEXT:    br i1 [[CMP27]], label [[FOR_BODY3_LR_PH_US_PREHEADER:%.*]], label [[FOR_END15:%.*]]
 ; CHECK:       for.body3.lr.ph.us.preheader:
 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[M]], -1
 ; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[TMP0]] to i64
-; CHECK-NEXT:    [[TMP2:%.*]] = add i64 [[TMP1]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = add nuw nsw i64 [[TMP1]], 1
 ; CHECK-NEXT:    [[TMP3:%.*]] = zext i32 [[K:%.*]] to i64
 ; CHECK-NEXT:    br label [[FOR_BODY3_LR_PH_US:%.*]]
 ; CHECK:       for.end.us:
 ; CHECK-NEXT:    [[ARRAYIDX9_US:%.*]] = getelementptr inbounds i32, i32* [[B:%.*]], i64 [[INDVARS_IV33:%.*]]
 ; CHECK-NEXT:    [[TMP4:%.*]] = load i32, i32* [[ARRAYIDX9_US]], align 4, !llvm.mem.parallel_loop_access !0
 ; CHECK-NEXT:    [[ADD10_US:%.*]] = add nsw i32 [[TMP4]], 3
 ; CHECK-NEXT:    store i32 [[ADD10_US]], i32* [[ARRAYIDX9_US]], align 4, !llvm.mem.parallel_loop_access !0
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT34:%.*]] = add i64 [[INDVARS_IV33]], 1