[SCEV] Suppress hoisting insertion point of binops when unsafe

[wristow]

Summary

InsertBinop tries to move insertion-points out of loops for expressions that are loop-invariant. This patch adds a new parameter, IsSafeToHost (default true), to guard that hoisting. This allows callers to suppress that hoisting for unsafe situations, such as divisions that may have a zero denominator.

This fixes PR38697.

[wristow]

Since the callers of SCEVExpander::InsertBinop "know" whether the binop being inserted is safe to hoist, this proposed solution of having the caller pass a parameter to indicate whether it's safe seems clean. But a simpler approach is to special-case the opcode Instruction::UDiv in InsertBinop.

An even simpler approach is to simply never hoist the insertion-point in InsertBinop. In fact, in the cases I've examined, SCEVExpander::expand always did the desired hoisting when it was safe, anyway. So removing the loop that I'm guarding here with the new parameter IsSafeToHoist is equivalent for those test-cases (the check-all tests all passed on x86_64-linux if I simply removed the loop entirely). I'd be happy to go with this approach of removing the hoisting loop, but I don't know for certain whether the hoisting is always redundant with other optimizations.

To try to understand (and in particular, to try to find a test-case that depended on that hoisting being done), I looked through the history of that hosting loop. I see it was added more than 8 years ago (r97642):

Make SCEVExpander and LSR more aggressive about hoisting expressions out
of loops.

But that revision didn't include any test-cases. So I'm at a loss to demonstrate whether there are any cases where the code-gen is improved by the hoisting.

In investigating this history, I noticed a couple of other interesting points.

First, the patch here, along with the recently committed patch of:
https://reviews.llvm.org/rL347934

is equivalent to a patch that was committed about a year ago:
https://reviews.llvm.org/rL289412

(As an aside, that year-old commit uses the simpler approach of special-casing the opcode Instruction::UDiv in InsertBinop to guard the loop, rather than having the caller pass an extra parameter to indicate when it's unsafe to hoist.)

Second, the reason this patch and the recently committed r347934 are needed (even though this was fixed a year ago by r289412), is because that year-old fix was reverted at r289453:

Reverts r289412. It caused an OOB PHI operand access in instcombine when
ASan is enabled. Reduction in progress.

@rnk: I wanted to give you a heads up that that problem may re-apear once this patch is reviewed and committed.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

851

Limiting to constants looks super-conservative. How about getting SCEV for RHS and then asking SE isKnownPredicate(ICMP_NE, RHS, 0)?

[wristow]

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

851

Sounds good.

That said, I've put this work on the back-burner for the moment, because the effectiveness of this patch depends on the change of rL347934 being in place, and that commit was reverted today (at rL348426), due to SEGVs happening in PHINode Simplification in Instcombine. That may be the same underlying problem that motivated the revert I previously mentioned that was done about a year ago:

Reverts r289412. It caused an OOB PHI operand access in instcombine when
ASan is enabled. Reduction in progress.

In any case, until the fix that was done as rL347934 is re-instated in some form, I'll hold off on making the fix discussed here.

[wristow]

Limiting to constants looks super-conservative. How about getting SCEV for RHS and then asking SE isKnownPredicate(ICMP_NE, RHS, 0)?

Sounds good. ... In any case, until the fix that was done as rL347934 is re-instated in some form, I'll hold off on making the fix discussed here.

That fix has been reinstated at r356392 (D57428) so I'm now addressing this issue.

Taking the suggestion of isKnownPredicate(ICMP_NE, RHS, 0) from @mkazantsev, I see that for this situation, SE.isKnownNonZero(S->getRHS()) can be used. The resulting patch is then simpler than my original patch proposed here, and it adds the more aggressive analysis Max suggested. I've added additional tests in this update, which includes testing for that more aggressive behavior of the hoisting of a non-constant divisor that can be proven to be non-zero.

[wristow]

ping

[wristow]

ping

[wristow]

ping x 3

[sanjoy]

Only minor nitpicky comments, will LGTM once these are fixed.

Normally I'd ask you to wait for Max, but looks like he is no longer at Azul and thus is not getting phabricator emails.

include/llvm/Analysis/ScalarEvolutionExpander.h

321 ↗

(On Diff #192943)

I'd slightly prefer to not default this to anything, is that feasible?

test/Transforms/LoopVectorize/pr38697.ll

202 ↗

(On Diff #192943)

We should give these instructions names so that updating the tests remains easy (use opt -instnamer).

228 ↗

(On Diff #192943)

Can you please make these CHECK lines a bit more specific? Maybe using update_test_checks.py?

[wristow]

Thanks for the review @sanjoy!

I've removed the default setting of the IsSafeToHoist argument, and I've used opt -instnamer to give the instructions names.

I also ran update_test_checks.py, but I felt compelled to edit the result down significantly (because there were so many instructions that were not related to the optimization, and I was worried it would make the resulting test too sensitive to unrelated changes in llvm). After editing it down to what I felt were the relevant instructions, I then also wanted to add some checks to verify that a division did not appear in places where it shouldn't be hoisted to. With that, I decided it was so different from the results of update_test_checks.py that I decided to remove the comment Assertions have been autogenerated by utils/update_test_checks.py. Bottom line: There are more explicit checks than I had originally, but not anywhere near the full set that would appear from that script. If you'd prefer that I leave the more substantial set of checks in place, let me know, and it will be easy for me to "un-do" much of the editing-down I did.

[wristow]

test/Transforms/LoopVectorize/pr38697.ll

228 ↗

(On Diff #192943)

I've addressed this to some extent, but edited it down significantly. Let me know if you'd prefer the larger set of tests.

[sanjoy]

lgtm

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

833

Can you please add /*IsSafeToHoist*/ on these arguments?

[wristow]

In D55232#1494448, @sanjoy wrote:

lgtm

Thanks for the review!

llvm/include/llvm/Analysis/ScalarEvolutionExpander.h

private:
     LLVMContext &getContext() const { return SE.getContext(); }
 
     /// Recursive helper function for isHighCostExpansion.
     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.
-    Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS);
+    /// 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);
 
     /// 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/lib/Analysis/ScalarEvolutionExpander.cpp

Value *SCEVExpander::InsertNoopCastOfTo(Value *V, Type *Ty) {
 
   // Cast the instruction immediately after the instruction.
   Instruction *I = cast<Instruction>(V);
   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.
+/// 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) {
+                                 Value *LHS, Value *RHS, 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();
for (; ScanLimit; --IP, --ScanLimit) {
       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);
   rememberInstruction(BO);
 
   return BO;
 }
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);
+      Sum = InsertBinop(Instruction::Sub, Sum, W, 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);
+      Sum = InsertBinop(Instruction::Add, Sum, W, true);
       ++I;
     }
   }
 
   return Sum;
 }
 
 Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) {
const auto ExpandOpBinPowN = [this, &I, &OpsAndLoops, &Ty]() {
 
     // 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);
+      P = InsertBinop(Instruction::Mul, P, P, true);
       if (Exponent & BinExp)
-        Result = Result ? InsertBinop(Instruction::Mul, Result, P) : P;
+        Result = Result ? InsertBinop(Instruction::Mul, Result, P, 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);
+      Prod = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), Prod,
+                         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()));
+                           ConstantInt::get(Ty, RHS->logBase2()), true);
       } else {
-        Prod = InsertBinop(Instruction::Mul, Prod, W);
+        Prod = InsertBinop(Instruction::Mul, Prod, W, 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()));
+                         ConstantInt::get(Ty, RHS.logBase2()), true);
   }
 
   Value *RHS = expandCodeFor(S->getRHS(), Ty);
-  return InsertBinop(Instruction::UDiv, LHS, RHS);
+  return InsertBinop(Instruction::UDiv, LHS, RHS,
+                     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) {
   while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Base)) {

llvm/test/Transforms/LoopVectorize/pr38697.ll

+; RUN: opt -loop-vectorize -force-vector-width=2 -S < %s 2>&1 | FileCheck %s
+; RUN: opt -indvars -S < %s 2>&1 | FileCheck %s -check-prefix=INDVARCHECK
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Produced from test-case:
+;
+; void testCountIncrLoop(unsigned char *ptr, int lim, int count, int val)
+; {
+;   int inx = 0;
+;   for (int outer_i = 0; outer_i < lim; ++outer_i) {
+;     if (count > 0) { // At runtime, 'count' is 0, so the following code is dead.
+;       int result = val;
+;       int tmp = count;
+;
+;       while (tmp < 8) {
+;         result += val >> tmp;
+;         tmp += count;
+;       }
+;
+;       ptr[inx++] = (unsigned char) result;
+;     }
+;   }
+; }
+;
+; No explicit division appears in the input, but a division is generated during
+; vectorization, and that division is a division-by-0 when the input 'count'
+; is 0, so it cannot be hoisted above the guard of 'count > 0'.
+
+; Verify that a 'udiv' does not appear in the 'loop1.preheader' block, and that
+; a 'udiv' has been inserted at the top of the 'while.body.preheader' block.
+define void @testCountIncrLoop(i8* %ptr, i32 %lim, i32 %count, i32 %val) {
+; CHECK-LABEL: @testCountIncrLoop(
+; CHECK-NEXT:  entry:
+; CHECK:       loop1.preheader:
+; CHECK-NOT:     udiv
+; CHECK:       loop1.body:
+; CHECK:       while.cond.preheader:
+; CHECK:       while.body.preheader:
+; CHECK-NEXT:    [[TMP1:%.*]] = udiv i32 [[TMP0:%.*]], [[COUNT:%.*]]
+; CHECK:       vector.ph:
+; CHECK:       exit:
+; CHECK:         ret void
+;
+entry:
+  %cmp1 = icmp sgt i32 %lim, 0
+  br i1 %cmp1, label %loop1.preheader, label %exit
+
+loop1.preheader:                                  ; preds = %entry
+  %cmp2 = icmp sgt i32 %count, 0
+  %cmp4 = icmp slt i32 %count, 8
+  br label %loop1.body
+
+loop1.body:                                       ; preds = %loop1.inc, %loop1.preheader
+  %outer_i = phi i32 [ 0, %loop1.preheader ], [ %outer_i.1, %loop1.inc ]
+  %inx.1 = phi i32 [ 0, %loop1.preheader ], [ %inx.2, %loop1.inc ]
+  br i1 %cmp2, label %while.cond.preheader, label %loop1.inc
+
+while.cond.preheader:                             ; preds = %loop1.body
+  br i1 %cmp4, label %while.body, label %while.end
+
+while.body:                                       ; preds = %while.body, %while.cond.preheader
+  %tmp = phi i32 [ %add3, %while.body ], [ %count, %while.cond.preheader ]
+  %result.1 = phi i32 [ %add, %while.body ], [ %val, %while.cond.preheader ]
+  %shr = ashr i32 %val, %tmp
+  %add = add nsw i32 %shr, %result.1
+  %add3 = add nsw i32 %tmp, %count
+  %cmp3 = icmp slt i32 %add3, 8
+  br i1 %cmp3, label %while.body, label %while.end
+
+while.end:                                        ; preds = %while.body, %while.cond.preheader
+  %result.0.lcssa = phi i32 [ %val, %while.cond.preheader ], [ %add, %while.body ]
+  %conv = trunc i32 %result.0.lcssa to i8
+  %inc = add nsw i32 %inx.1, 1
+  %idxprom = sext i32 %inx.1 to i64
+  %arrayidx = getelementptr inbounds i8, i8* %ptr, i64 %idxprom
+  store i8 %conv, i8* %arrayidx, align 1
+  br label %loop1.inc
+
+loop1.inc:                                        ; preds = %while.end, %loop1.body
+  %inx.2 = phi i32 [ %inc, %while.end ], [ %inx.1, %loop1.body ]
+  %outer_i.1 = add nuw nsw i32 %outer_i, 1
+  %exitcond = icmp eq i32 %outer_i.1, %lim
+  br i1 %exitcond, label %exit, label %loop1.body
+
+exit:                                             ; preds = %loop1.inc, %entry
+  ret void
+}
+
+; These next tests are all based on the following source code, with slight
+; variations on the calculation of 'incr' (all of which are loop-invariant
+; divisions, but only some of which can be safely hoisted):
+;
+; uint32_t foo(uint32_t *ptr, uint32_t start1, uint32_t start2) {
+;   uint32_t counter1, counter2;
+;   uint32_t val = start1;
+;   for (counter1 = 1; counter1 < 100; ++counter1) {
+;     uint32_t index = 0;
+;     val += ptr[index];
+;     for (counter2 = start2; counter2 < 10; ++counter2) {
+;       // Division is loop invariant, and denominator is guaranteed non-zero:
+;       // Safe to hoist it out of the inner loop.
+;       uint32_t incr = 16 / counter1;
+;       index += incr;
+;       val += ptr[index];
+;     }
+;   }
+;   return val;
+; }
+
+; This version is as written above, where 'incr' is '16/counter1', and it is
+; guaranted that 'counter1' is always non-zero.  So it is safe to hoist the
+; division from the inner loop to the preheader.
+;
+; Verify that the 'udiv' is hoisted to the preheader, and is not in the loop body.
+define i32 @NonZeroDivHoist(i32* nocapture readonly %ptr, i32 %start1, i32 %start2) {
+; INDVARCHECK-LABEL: @NonZeroDivHoist(
+; INDVARCHECK-NEXT:  entry:
+; INDVARCHECK:       for.body3.lr.ph:
+; INDVARCHECK-NEXT:    [[TMP0:%.*]] = udiv i64 16, [[INDVARS_IV:%.*]]
+; INDVARCHECK-NEXT:    br label [[FOR_BODY3:%.*]]
+; INDVARCHECK:       for.body3:
+; INDVARCHECK-NOT:     udiv
+; INDVARCHECK:       for.end10:
+;
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.end, %entry
+  %val.0 = phi i32 [ %start1, %entry ], [ %val.1.lcssa, %for.end ]
+  %counter1.0 = phi i32 [ 1, %entry ], [ %inc9, %for.end ]
+  %cmp = icmp ult i32 %counter1.0, 100
+  br i1 %cmp, label %for.body, label %for.end10
+
+for.body:                                         ; preds = %for.cond
+  %tmp = load i32, i32* %ptr, align 4
+  %add = add i32 %tmp, %val.0
+  %cmp224 = icmp ult i32 %start2, 10
+  br i1 %cmp224, label %for.body3.lr.ph, label %for.end
+
+for.body3.lr.ph:                                  ; preds = %for.body
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.body3, %for.body3.lr.ph
+  %index.027 = phi i32 [ 0, %for.body3.lr.ph ], [ %add4, %for.body3 ]
+  %val.126 = phi i32 [ %add, %for.body3.lr.ph ], [ %add7, %for.body3 ]
+  %counter2.025 = phi i32 [ %start2, %for.body3.lr.ph ], [ %inc, %for.body3 ]
+  %div = udiv i32 16, %counter1.0
+  %add4 = add i32 %div, %index.027
+  %idxprom5 = zext i32 %add4 to i64
+  %arrayidx6 = getelementptr inbounds i32, i32* %ptr, i64 %idxprom5
+  %tmp1 = load i32, i32* %arrayidx6, align 4
+  %add7 = add i32 %tmp1, %val.126
+  %inc = add i32 %counter2.025, 1
+  %cmp2 = icmp ult i32 %inc, 10
+  br i1 %cmp2, label %for.body3, label %for.cond1.for.end_crit_edge
+
+for.cond1.for.end_crit_edge:                      ; preds = %for.body3
+  %split = phi i32 [ %add7, %for.body3 ]
+  br label %for.end
+
+for.end:                                          ; preds = %for.cond1.for.end_crit_edge, %for.body
+  %val.1.lcssa = phi i32 [ %split, %for.cond1.for.end_crit_edge ], [ %add, %for.body ]
+  %inc9 = add i32 %counter1.0, 1
+  br label %for.cond
+
+for.end10:                                        ; preds = %for.cond
+  %val.0.lcssa = phi i32 [ %val.0, %for.cond ]
+  ret i32 %val.0.lcssa
+}
+
+; This version is identical to the above 'NonZeroDivHoist' case, except the
+; outer ('counter1') loop starts at the unknown value of 'start1' rather than 1,
+; and so it is illegal to hoist the division because if 'start1' is 0, hoisting
+; it would incorrectly cause a divide-by-zero trap.
+;
+; Verify that the 'udiv' is not hoisted to the preheader, and it remains in the
+; loop body.
+define i32 @ZeroDivNoHoist(i32* nocapture readonly %ptr, i32 %start1, i32 %start2) {
+; INDVARCHECK-LABEL: @ZeroDivNoHoist(
+; INDVARCHECK-NEXT:  entry:
+; INDVARCHECK-NOT:     udiv
+; INDVARCHECK:       for.body3:
+; INDVARCHECK:         [[TMP1:%.*]] = udiv i64 16, [[INDVARS_IV:%.*]]
+; INDVARCHECK:       for.cond1.for.end_crit_edge:
+;
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.end, %entry
+  %val.0 = phi i32 [ %start1, %entry ], [ %val.1.lcssa, %for.end ]
+  %counter1.0 = phi i32 [ %start1, %entry ], [ %inc9, %for.end ]
+  %cmp = icmp ult i32 %counter1.0, 100
+  br i1 %cmp, label %for.body, label %for.end10
+
+for.body:                                         ; preds = %for.cond
+  %tmp = load i32, i32* %ptr, align 4
+  %add = add i32 %tmp, %val.0
+  %cmp224 = icmp ult i32 %start2, 10
+  br i1 %cmp224, label %for.body3.lr.ph, label %for.end
+
+for.body3.lr.ph:                                  ; preds = %for.body
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.body3, %for.body3.lr.ph
+  %index.027 = phi i32 [ 0, %for.body3.lr.ph ], [ %add4, %for.body3 ]
+  %val.126 = phi i32 [ %add, %for.body3.lr.ph ], [ %add7, %for.body3 ]
+  %counter2.025 = phi i32 [ %start2, %for.body3.lr.ph ], [ %inc, %for.body3 ]
+  %div = udiv i32 16, %counter1.0
+  %add4 = add i32 %div, %index.027
+  %idxprom5 = zext i32 %add4 to i64
+  %arrayidx6 = getelementptr inbounds i32, i32* %ptr, i64 %idxprom5
+  %tmp1 = load i32, i32* %arrayidx6, align 4
+  %add7 = add i32 %tmp1, %val.126
+  %inc = add i32 %counter2.025, 1
+  %cmp2 = icmp ult i32 %inc, 10
+  br i1 %cmp2, label %for.body3, label %for.cond1.for.end_crit_edge
+
+for.cond1.for.end_crit_edge:                      ; preds = %for.body3
+  %split = phi i32 [ %add7, %for.body3 ]
+  br label %for.end
+
+for.end:                                          ; preds = %for.cond1.for.end_crit_edge, %for.body
+  %val.1.lcssa = phi i32 [ %split, %for.cond1.for.end_crit_edge ], [ %add, %for.body ]
+  %inc9 = add i32 %counter1.0, 1
+  br label %for.cond
+
+for.end10:                                        ; preds = %for.cond
+  %val.0.lcssa = phi i32 [ %val.0, %for.cond ]
+  ret i32 %val.0.lcssa
+}
+
+; This version is has a clearly safe division by a non-zero constant (16).  The
+; division is transformed to a logical-shift-right of 4, and it is safely
+; hoisted.
+;
+; Verify that the division-operation is hoisted, and that it appears as a
+; right-shift ('lshr') rather than an explicit division.
+define i32 @DivBy16Hoist(i32* nocapture readonly %ptr, i32 %start1, i32 %start2) {
+; INDVARCHECK-LABEL: @DivBy16Hoist(
+; INDVARCHECK-NEXT:  entry:
+; INDVARCHECK:       for.cond:
+; INDVARCHECK:         [[TMP1:%.*]] = lshr i64 [[INDVARS_IV:%.*]], 4
+; INDVARCHECK:       for.body:
+; INDVARCHECK-NOT:     lshr
+; INDVARCHECK-NOT:     udiv
+; INDVARCHECK:       for.end10:
+;
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.end, %entry
+  %val.0 = phi i32 [ %start1, %entry ], [ %val.1.lcssa, %for.end ]
+  %counter1.0 = phi i32 [ %start1, %entry ], [ %inc9, %for.end ]
+  %cmp = icmp ult i32 %counter1.0, 100
+  br i1 %cmp, label %for.body, label %for.end10
+
+for.body:                                         ; preds = %for.cond
+  %tmp = load i32, i32* %ptr, align 4
+  %add = add i32 %tmp, %val.0
+  %cmp224 = icmp ult i32 %start2, 10
+  br i1 %cmp224, label %for.body3.lr.ph, label %for.end
+
+for.body3.lr.ph:                                  ; preds = %for.body
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.body3, %for.body3.lr.ph
+  %index.027 = phi i32 [ 0, %for.body3.lr.ph ], [ %add4, %for.body3 ]
+  %val.126 = phi i32 [ %add, %for.body3.lr.ph ], [ %add7, %for.body3 ]
+  %counter2.025 = phi i32 [ %start2, %for.body3.lr.ph ], [ %inc, %for.body3 ]
+  %div = udiv i32 %counter1.0, 16
+  %add4 = add i32 %div, %index.027
+  %idxprom5 = zext i32 %add4 to i64
+  %arrayidx6 = getelementptr inbounds i32, i32* %ptr, i64 %idxprom5
+  %tmp1 = load i32, i32* %arrayidx6, align 4
+  %add7 = add i32 %tmp1, %val.126
+  %inc = add i32 %counter2.025, 1
+  %cmp2 = icmp ult i32 %inc, 10
+  br i1 %cmp2, label %for.body3, label %for.cond1.for.end_crit_edge
+
+for.cond1.for.end_crit_edge:                      ; preds = %for.body3
+  %split = phi i32 [ %add7, %for.body3 ]
+  br label %for.end
+
+for.end:                                          ; preds = %for.cond1.for.end_crit_edge, %for.body
+  %val.1.lcssa = phi i32 [ %split, %for.cond1.for.end_crit_edge ], [ %add, %for.body ]
+  %inc9 = add i32 %counter1.0, 1
+  br label %for.cond
+
+for.end10:                                        ; preds = %for.cond
+  %val.0.lcssa = phi i32 [ %val.0, %for.cond ]
+  ret i32 %val.0.lcssa
+}
+
+; This version is has a clearly safe division by a non-zero constant (17).  The
+; division is safely hoisted, as it was in the 'DivBy16Hoist' verison, but here
+; it remains a division, rather than being transformed to a right-shift.
+;
+; Verify that the division-operation is hoisted.
+define i32 @DivBy17Hoist(i32* nocapture readonly %ptr, i32 %start1, i32 %start2) {
+; INDVARCHECK-LABEL: @DivBy17Hoist(
+; INDVARCHECK-NEXT:  entry:
+; INDVARCHECK:       for.cond:
+; INDVARCHECK:         [[TMP1:%.*]] = udiv i64 [[INDVARS_IV:%.*]], 17
+; INDVARCHECK:       for.body:
+; INDVARCHECK-NOT:     udiv
+; INDVARCHECK:       for.end10:
+;
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.end, %entry
+  %val.0 = phi i32 [ %start1, %entry ], [ %val.1.lcssa, %for.end ]
+  %counter1.0 = phi i32 [ %start1, %entry ], [ %inc9, %for.end ]
+  %cmp = icmp ult i32 %counter1.0, 100
+  br i1 %cmp, label %for.body, label %for.end10
+
+for.body:                                         ; preds = %for.cond
+  %tmp = load i32, i32* %ptr, align 4
+  %add = add i32 %tmp, %val.0
+  %cmp224 = icmp ult i32 %start2, 10
+  br i1 %cmp224, label %for.body3.lr.ph, label %for.end
+
+for.body3.lr.ph:                                  ; preds = %for.body
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.body3, %for.body3.lr.ph
+  %index.027 = phi i32 [ 0, %for.body3.lr.ph ], [ %add4, %for.body3 ]
+  %val.126 = phi i32 [ %add, %for.body3.lr.ph ], [ %add7, %for.body3 ]
+  %counter2.025 = phi i32 [ %start2, %for.body3.lr.ph ], [ %inc, %for.body3 ]
+  %div = udiv i32 %counter1.0, 17
+  %add4 = add i32 %div, %index.027
+  %idxprom5 = zext i32 %add4 to i64
+  %arrayidx6 = getelementptr inbounds i32, i32* %ptr, i64 %idxprom5
+  %tmp1 = load i32, i32* %arrayidx6, align 4
+  %add7 = add i32 %tmp1, %val.126
+  %inc = add i32 %counter2.025, 1
+  %cmp2 = icmp ult i32 %inc, 10
+  br i1 %cmp2, label %for.body3, label %for.cond1.for.end_crit_edge
+
+for.cond1.for.end_crit_edge:                      ; preds = %for.body3
+  %split = phi i32 [ %add7, %for.body3 ]
+  br label %for.end
+
+for.end:                                          ; preds = %for.cond1.for.end_crit_edge, %for.body
+  %val.1.lcssa = phi i32 [ %split, %for.cond1.for.end_crit_edge ], [ %add, %for.body ]
+  %inc9 = add i32 %counter1.0, 1
+  br label %for.cond
+
+for.end10:                                        ; preds = %for.cond
+  %val.0.lcssa = phi i32 [ %val.0, %for.cond ]
+  ret i32 %val.0.lcssa
+}