Teach ScalarEvolution to exploit min and max expressions.

[sanjoy]

Summary

Teach ScalarEvolution to exploit min and max expressions when proving isKnownPredicate.

The motivation for this change is to optimize away checks in loops like this:

limit = min(t, len)
for (i = 0 to limit)
  if (i >= len || i < 0) throw_array_of_of_bounds();
  a[i] = ...

[majnemer]

lib/Analysis/ScalarEvolution.cpp

6982 ↗

(On Diff #17212)

Might be more concise as:

for (const SCEV *Operand : MaxExpr)
  const SCEV *Difference = SE.getMinusSCEV(Candidate, Operand);

7004–7006 ↗

(On Diff #17212)

This seems contrary to http://llvm.org/docs/CodingStandards.html#don-t-use-else-after-a-return

7015–7016 ↗

(On Diff #17212)

I thought case labels should be at the same indentation level as the switch.

[sanjoy]

Address David's review + minor nits I noticed. No functional change.

[atrick]

Overall really nice work. Thanks to David for reviewing. See my comments inline.

lib/Analysis/ScalarEvolution.cpp

6952 ↗

(On Diff #17219)

insert a comma: "computes ~A, assign"

6954 ↗

(On Diff #17219)

Not a big deal, but why not return NotOf and nullptr for a mismatch?

Did you implement the pattern matching to avoid the overhead of just comparing the result of getNotExpr if you can bail-out of the match early?

6983 ↗

(On Diff #17219)

Can you explain why the subtraction is necessary. What unique expressions have zero difference?

Are you assuming that MaybeExpr and Candidate have the same bitwidth? What happens if they don't?

7034 ↗

(On Diff #17219)

Out of curiosity, do you need the unreachable? There shouldn't be a warning for a covered switch, should be a warning otherwise.

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

6954 ↗

(On Diff #17219)

Not a big deal, but why not return NotOf and nullptr for a mismatch?

Will do, that seems obviously better.

Did you implement the pattern matching to avoid the overhead of just comparing the result of getNotExpr if you can bail-out of the match early?

Yes. I have to admit though that I don't have a good intuition on what kinds of operations in ScalarEvolution are fast enough that they're not worth optimizing like this.

6983 ↗

(On Diff #17219)

Can you explain why the subtraction is necessary. What unique expressions have zero difference?

I was initially thinking of things like %a OP %b vs. %b OP %a but depending on how scev canonicalizes these it may not actually be an issue. I'll change it to use pointer equality for now -- that seems to pass the test with this patch.

Are you assuming that MaybeExpr and Candidate have the same bitwidth? What happens if they don't?

I don't think that should be an issue once I change this to use pointer equality. That said, is isImpliedCondOperands(P, A, B, C, D) ever called with either A Pred B or C Pred D not well-typed?

7034 ↗

(On Diff #17219)

Without the llvm_unreachable I don't see a warning with clang, but wasn't sure if one of the buildbots might.

[sanjoy]

Address review comments by Andy

[atrick]

LGTM

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

bool ScalarEvolution::isImpliedCondOperands(ICmpInst::Predicate Pred,
   return isImpliedCondOperandsHelper(Pred, LHS, RHS,
                                      FoundLHS, FoundRHS) ||
          // ~x < ~y --> x > y
          isImpliedCondOperandsHelper(Pred, LHS, RHS,
                                      getNotSCEV(FoundRHS),
                                      getNotSCEV(FoundLHS));
 }
 
+
+/// If Expr computes ~A, return A else return nullptr
+static const SCEV *MatchNotExpr(const SCEV *Expr) {
+  const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Expr);
+  if (!Add || Add->getNumOperands() != 2) return nullptr;
+
+  const SCEVConstant *AddLHS = dyn_cast<SCEVConstant>(Add->getOperand(0));
+  if (!(AddLHS && AddLHS->getValue()->getValue().isAllOnesValue()))
+    return nullptr;
+
+  const SCEVMulExpr *AddRHS = dyn_cast<SCEVMulExpr>(Add->getOperand(1));
+  if (!AddRHS || AddRHS->getNumOperands() != 2) return nullptr;
+
+  const SCEVConstant *MulLHS = dyn_cast<SCEVConstant>(AddRHS->getOperand(0));
+  if (!(MulLHS && MulLHS->getValue()->getValue().isAllOnesValue()))
+    return nullptr;
+
+  return AddRHS->getOperand(1);
+}
+
+
+/// Is MaybeMaxExpr an SMax or UMax of Candidate and some other values?
+template<typename MaxExprType>
+static bool IsMaxConsistingOf(const SCEV *MaybeMaxExpr,
+                              const SCEV *Candidate) {
+  const MaxExprType *MaxExpr = dyn_cast<MaxExprType>(MaybeMaxExpr);
+  if (!MaxExpr) return false;
+
+  auto It = std::find(MaxExpr->op_begin(), MaxExpr->op_end(), Candidate);
+  return It != MaxExpr->op_end();
+}
+
+
+/// Is MaybeMinExpr an SMin or UMin of Candidate and some other values?
+template<typename MaxExprType>
+static bool IsMinConsistingOf(ScalarEvolution &SE,
+                              const SCEV *MaybeMinExpr,
+                              const SCEV *Candidate) {
+  const SCEV *MaybeMaxExpr = MatchNotExpr(MaybeMinExpr);
+  if (!MaybeMaxExpr)
+    return false;
+
+  return IsMaxConsistingOf<MaxExprType>(MaybeMaxExpr, SE.getNotSCEV(Candidate));
+}
+
+
+/// Is LHS `Pred` RHS true on the virtue of LHS or RHS being a Min or Max
+/// expression?
+static bool IsKnownPredicateViaMinOrMax(ScalarEvolution &SE,
+                                        ICmpInst::Predicate Pred,
+                                        const SCEV *LHS, const SCEV *RHS) {
+  switch (Pred) {
+  default:
+    return false;
+
+  case ICmpInst::ICMP_SGE:
+    std::swap(LHS, RHS);
+    // fall through
+  case ICmpInst::ICMP_SLE:
+    return
+      // min(A, ...) <= A
+      IsMinConsistingOf<SCEVSMaxExpr>(SE, LHS, RHS) ||
+      // A <= max(A, ...)
+      IsMaxConsistingOf<SCEVSMaxExpr>(RHS, LHS);
+
+  case ICmpInst::ICMP_UGE:
+    std::swap(LHS, RHS);
+    // fall through
+  case ICmpInst::ICMP_ULE:
+    return
+      // min(A, ...) <= A
+      IsMinConsistingOf<SCEVUMaxExpr>(SE, LHS, RHS) ||
+      // A <= max(A, ...)
+      IsMaxConsistingOf<SCEVUMaxExpr>(RHS, LHS);
+  }
+
+  llvm_unreachable("covered switch fell through?!");
+}
+
 /// isImpliedCondOperandsHelper - Test whether the condition described by
 /// Pred, LHS, and RHS is true whenever the condition described by Pred,
 /// FoundLHS, and FoundRHS is true.
 bool
 ScalarEvolution::isImpliedCondOperandsHelper(ICmpInst::Predicate Pred,
                                              const SCEV *LHS, const SCEV *RHS,
                                              const SCEV *FoundLHS,
                                              const SCEV *FoundRHS) {
+  auto IsKnownPredicateFull =
+      [this](ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS) {
+    return isKnownPredicateWithRanges(Pred, LHS, RHS) ||
+        IsKnownPredicateViaMinOrMax(*this, Pred, LHS, RHS);
+  };
+
   switch (Pred) {
   default: llvm_unreachable("Unexpected ICmpInst::Predicate value!");
   case ICmpInst::ICMP_EQ:
   case ICmpInst::ICMP_NE:
     if (HasSameValue(LHS, FoundLHS) && HasSameValue(RHS, FoundRHS))
       return true;
     break;
   case ICmpInst::ICMP_SLT:
   case ICmpInst::ICMP_SLE:
-    if (isKnownPredicateWithRanges(ICmpInst::ICMP_SLE, LHS, FoundLHS) &&
-        isKnownPredicateWithRanges(ICmpInst::ICMP_SGE, RHS, FoundRHS))
+    if (IsKnownPredicateFull(ICmpInst::ICMP_SLE, LHS, FoundLHS) &&
+        IsKnownPredicateFull(ICmpInst::ICMP_SGE, RHS, FoundRHS))
       return true;
     break;
   case ICmpInst::ICMP_SGT:
   case ICmpInst::ICMP_SGE:
-    if (isKnownPredicateWithRanges(ICmpInst::ICMP_SGE, LHS, FoundLHS) &&
-        isKnownPredicateWithRanges(ICmpInst::ICMP_SLE, RHS, FoundRHS))
+    if (IsKnownPredicateFull(ICmpInst::ICMP_SGE, LHS, FoundLHS) &&
+        IsKnownPredicateFull(ICmpInst::ICMP_SLE, RHS, FoundRHS))
       return true;
     break;
   case ICmpInst::ICMP_ULT:
   case ICmpInst::ICMP_ULE:
-    if (isKnownPredicateWithRanges(ICmpInst::ICMP_ULE, LHS, FoundLHS) &&
-        isKnownPredicateWithRanges(ICmpInst::ICMP_UGE, RHS, FoundRHS))
+    if (IsKnownPredicateFull(ICmpInst::ICMP_ULE, LHS, FoundLHS) &&
+        IsKnownPredicateFull(ICmpInst::ICMP_UGE, RHS, FoundRHS))
       return true;
     break;
   case ICmpInst::ICMP_UGT:
   case ICmpInst::ICMP_UGE:
-    if (isKnownPredicateWithRanges(ICmpInst::ICMP_UGE, LHS, FoundLHS) &&
-        isKnownPredicateWithRanges(ICmpInst::ICMP_ULE, RHS, FoundRHS))
+    if (IsKnownPredicateFull(ICmpInst::ICMP_UGE, LHS, FoundLHS) &&
+        IsKnownPredicateFull(ICmpInst::ICMP_ULE, RHS, FoundRHS))
       return true;
     break;
   }
 
   return false;
 }
 
 // Verify if an linear IV with positive stride can overflow when in a 

llvm/trunk/test/Transforms/IndVarSimplify/backedge-on-min-max.ll

+; RUN: opt < %s -indvars -S | FileCheck %s
+
+;; --- signed ---
+
+define void @min.signed.1(i32* %a, i32 %a_len, i32 %n) {
+; CHECK-LABEL: @min.signed.1
+ entry:
+  %smin.cmp = icmp slt i32 %a_len, %n
+  %smin = select i1 %smin.cmp, i32 %a_len, i32 %n
+  %entry.cond = icmp slt i32 0, %smin
+  br i1 %entry.cond, label %loop, label %exit
+
+ loop:
+  %idx = phi i32 [ 0, %entry ], [ %idx.inc, %latch ]
+  %idx.inc = add i32 %idx, 1
+  %in.bounds = icmp slt i32 %idx, %a_len
+  br i1 %in.bounds, label %ok, label %latch
+; CHECK: br i1 true, label %ok, label %latch
+
+ ok:
+  %addr = getelementptr i32* %a, i32 %idx
+  store i32 %idx, i32* %addr
+  br label %latch
+
+ latch:
+  %be.cond = icmp slt i32 %idx.inc, %smin
+  br i1 %be.cond, label %loop, label %exit
+
+ exit:
+  ret void
+}
+
+define void @min.signed.2(i32* %a, i32 %a_len, i32 %n) {
+; CHECK-LABEL: @min.signed.2
+ entry:
+  %smin.cmp = icmp slt i32 %a_len, %n
+  %smin = select i1 %smin.cmp, i32 %a_len, i32 %n
+  %entry.cond = icmp slt i32 0, %smin
+  br i1 %entry.cond, label %loop, label %exit
+
+ loop:
+  %idx = phi i32 [ 0, %entry ], [ %idx.inc, %latch ]
+  %idx.inc = add i32 %idx, 1
+  %in.bounds = icmp sgt i32 %a_len, %idx
+  br i1 %in.bounds, label %ok, label %latch
+; CHECK: br i1 true, label %ok, label %latch
+
+ ok:
+  %addr = getelementptr i32* %a, i32 %idx
+  store i32 %idx, i32* %addr
+  br label %latch
+
+ latch:
+  %be.cond = icmp slt i32 %idx.inc, %smin
+  br i1 %be.cond, label %loop, label %exit
+
+ exit:
+  ret void
+}
+
+define void @min.signed.3(i32* %a, i32 %n) {
+; CHECK-LABEL: @min.signed.3
+ entry:
+  %smin.cmp = icmp slt i32 42, %n
+  %smin = select i1 %smin.cmp, i32 42, i32 %n
+  %entry.cond = icmp slt i32 0, %smin
+  br i1 %entry.cond, label %loop, label %exit
+
+ loop:
+  %idx = phi i32 [ 0, %entry ], [ %idx.inc, %latch ]
+  %idx.inc = add i32 %idx, 1
+  %in.bounds = icmp slt i32 %idx, 42
+  br i1 %in.bounds, label %ok, label %latch
+; CHECK: br i1 true, label %ok, label %latch
+
+ ok:
+  %addr = getelementptr i32* %a, i32 %idx
+  store i32 %idx, i32* %addr
+  br label %latch
+
+ latch:
+  %be.cond = icmp slt i32 %idx.inc, %smin
+  br i1 %be.cond, label %loop, label %exit
+
+ exit:
+  ret void
+}
+
+define void @min.signed.4(i32* %a, i32 %n) {
+; CHECK-LABEL: @min.signed.4
+ entry:
+  %smin.cmp = icmp slt i32 42, %n
+  %smin = select i1 %smin.cmp, i32 42, i32 %n
+  %entry.cond = icmp slt i32 0, %smin
+  br i1 %entry.cond, label %loop, label %exit
+
+ loop:
+  %idx = phi i32 [ 0, %entry ], [ %idx.inc, %latch ]
+  %idx.inc = add i32 %idx, 1
+  %in.bounds = icmp sgt i32 42, %idx
+  br i1 %in.bounds, label %ok, label %latch
+; CHECK: br i1 true, label %ok, label %latch
+
+ ok:
+  %addr = getelementptr i32* %a, i32 %idx
+  store i32 %idx, i32* %addr
+  br label %latch
+
+ latch:
+  %be.cond = icmp slt i32 %idx.inc, %smin
+  br i1 %be.cond, label %loop, label %exit
+
+ exit:
+  ret void
+}
+
+define void @max.signed.1(i32* %a, i32 %a_len, i32 %n) {
+; CHECK-LABEL: @max.signed.1
+ entry:
+  %smax.cmp = icmp sgt i32 %a_len, %n
+  %smax = select i1 %smax.cmp, i32 %a_len, i32 %n
+  %entry.cond = icmp sgt i32 0, %smax
+  br i1 %entry.cond, label %loop, label %exit
+
+ loop:
+  %idx = phi i32 [ 0, %entry ], [ %idx.inc, %latch ]
+  %idx.inc = add i32 %idx, 1
+  %in.bounds = icmp sgt i32 %idx, %a_len
+  br i1 %in.bounds, label %ok, label %latch
+; CHECK: br i1 true, label %ok, label %latch
+
+ ok:
+  %addr = getelementptr i32* %a, i32 %idx
+  store i32 %idx, i32* %addr
+  br label %latch
+
+ latch:
+  %be.cond = icmp sgt i32 %idx.inc, %smax
+  br i1 %be.cond, label %loop, label %exit
+
+ exit:
+  ret void
+}
+
+define void @max.signed.2(i32* %a, i32 %a_len, i32 %n) {
+; CHECK-LABEL: @max.signed.2
+ entry:
+  %smax.cmp = icmp sgt i32 %a_len, %n
+  %smax = select i1 %smax.cmp, i32 %a_len, i32 %n
+  %entry.cond = icmp sgt i32 0, %smax
+  br i1 %entry.cond, label %loop, label %exit
+
+ loop:
+  %idx = phi i32 [ 0, %entry ], [ %idx.inc, %latch ]
+  %idx.inc = add i32 %idx, 1
+  %in.bounds = icmp slt i32 %a_len, %idx
+  br i1 %in.bounds, label %ok, label %latch
+; CHECK: br i1 true, label %ok, label %latch
+
+ ok:
+  %addr = getelementptr i32* %a, i32 %idx
+  store i32 %idx, i32* %addr
+  br label %latch
+
+ latch:
+  %be.cond = icmp sgt i32 %idx.inc, %smax
+  br i1 %be.cond, label %loop, label %exit
+
+ exit:
+  ret void
+}
+
+define void @max.signed.3(i32* %a, i32 %n, i32 %init) {
+; CHECK-LABEL: @max.signed.3
+ entry:
+  %smax.cmp = icmp sgt i32 42, %n
+  %smax = select i1 %smax.cmp, i32 42, i32 %n
+  %entry.cond = icmp sgt i32 %init, %smax
+  br i1 %entry.cond, label %loop, label %exit
+
+ loop:
+  %idx = phi i32 [ %init, %entry ], [ %idx.inc, %latch ]
+  %idx.inc = add i32 %idx, 1
+  %in.bounds = icmp sgt i32 %idx, 42
+  br i1 %in.bounds, label %ok, label %latch
+; CHECK: br i1 true, label %ok, label %latch
+
+ ok:
+  %addr = getelementptr i32* %a, i32 %idx
+  store i32 %idx, i32* %addr
+  br label %latch
+
+ latch:
+  %be.cond = icmp sgt i32 %idx.inc, %smax
+  br i1 %be.cond, label %loop, label %exit
+
+ exit:
+  ret void
+}
+
+define void @max.signed.4(i32* %a, i32 %n, i32 %init) {
+; CHECK-LABEL: @max.signed.4
+ entry:
+  %smax.cmp = icmp sgt i32 42, %n
+  %smax = select i1 %smax.cmp, i32 42, i32 %n
+  %entry.cond = icmp sgt i32 %init, %smax
+  br i1 %entry.cond, label %loop, label %exit
+
+ loop:
+  %idx = phi i32 [ %init, %entry ], [ %idx.inc, %latch ]
+  %idx.inc = add i32 %idx, 1
+  %in.bounds = icmp slt i32 42, %idx
+  br i1 %in.bounds, label %ok, label %latch
+; CHECK: br i1 true, label %ok, label %latch
+
+ ok:
+  %addr = getelementptr i32* %a, i32 %idx
+  store i32 %idx, i32* %addr
+  br label %latch
+
+ latch:
+  %be.cond = icmp sgt i32 %idx.inc, %smax
+  br i1 %be.cond, label %loop, label %exit
+
+ exit:
+  ret void
+}
+
+;; --- unsigned ---
+
+define void @min.unsigned.1(i32* %a, i32 %a_len, i32 %n) {
+; CHECK-LABEL: @min.unsigned.1
+ entry:
+  %umin.cmp = icmp ult i32 %a_len, %n
+  %umin = select i1 %umin.cmp, i32 %a_len, i32 %n
+  %entry.cond = icmp ult i32 5, %umin
+  br i1 %entry.cond, label %loop, label %exit
+
+ loop:
+  %idx = phi i32 [ 5, %entry ], [ %idx.inc, %latch ]
+  %idx.inc = add i32 %idx, 1
+  %in.bounds = icmp ult i32 %idx, %a_len
+  br i1 %in.bounds, label %ok, label %latch
+; CHECK: br i1 true, label %ok, label %latch
+
+ ok:
+  %addr = getelementptr i32* %a, i32 %idx
+  store i32 %idx, i32* %addr
+  br label %latch
+
+ latch:
+  %be.cond = icmp ult i32 %idx.inc, %umin
+  br i1 %be.cond, label %loop, label %exit
+
+ exit:
+  ret void
+}
+
+define void @min.unsigned.2(i32* %a, i32 %a_len, i32 %n) {
+; CHECK-LABEL: @min.unsigned.2
+ entry:
+  %umin.cmp = icmp ult i32 %a_len, %n
+  %umin = select i1 %umin.cmp, i32 %a_len, i32 %n
+  %entry.cond = icmp ult i32 5, %umin
+  br i1 %entry.cond, label %loop, label %exit
+
+ loop:
+  %idx = phi i32 [ 5, %entry ], [ %idx.inc, %latch ]
+  %idx.inc = add i32 %idx, 1
+  %in.bounds = icmp ugt i32 %a_len, %idx
+  br i1 %in.bounds, label %ok, label %latch
+; CHECK: br i1 true, label %ok, label %latch
+
+ ok:
+  %addr = getelementptr i32* %a, i32 %idx
+  store i32 %idx, i32* %addr
+  br label %latch
+
+ latch:
+  %be.cond = icmp ult i32 %idx.inc, %umin
+  br i1 %be.cond, label %loop, label %exit
+
+ exit:
+  ret void
+}
+
+define void @min.unsigned.3(i32* %a, i32 %n) {
+; CHECK-LABEL: @min.unsigned.3
+ entry:
+  %umin.cmp = icmp ult i32 42, %n
+  %umin = select i1 %umin.cmp, i32 42, i32 %n
+  %entry.cond = icmp ult i32 5, %umin
+  br i1 %entry.cond, label %loop, label %exit
+
+ loop:
+  %idx = phi i32 [ 5, %entry ], [ %idx.inc, %latch ]
+  %idx.inc = add i32 %idx, 1
+  %in.bounds = icmp ult i32 %idx, 42
+  br i1 %in.bounds, label %ok, label %latch
+; CHECK: br i1 true, label %ok, label %latch
+
+ ok:
+  %addr = getelementptr i32* %a, i32 %idx
+  store i32 %idx, i32* %addr
+  br label %latch
+
+ latch:
+  %be.cond = icmp ult i32 %idx.inc, %umin
+  br i1 %be.cond, label %loop, label %exit
+
+ exit:
+  ret void
+}
+
+define void @min.unsigned.4(i32* %a, i32 %n) {
+; CHECK-LABEL: @min.unsigned.4
+ entry:
+  %umin.cmp = icmp ult i32 42, %n
+  %umin = select i1 %umin.cmp, i32 42, i32 %n
+  %entry.cond = icmp ult i32 5, %umin
+  br i1 %entry.cond, label %loop, label %exit
+
+ loop:
+  %idx = phi i32 [ 5, %entry ], [ %idx.inc, %latch ]
+  %idx.inc = add i32 %idx, 1
+  %in.bounds = icmp ugt i32 42, %idx
+  br i1 %in.bounds, label %ok, label %latch
+; CHECK: br i1 true, label %ok, label %latch
+
+ ok:
+  %addr = getelementptr i32* %a, i32 %idx
+  store i32 %idx, i32* %addr
+  br label %latch
+
+ latch:
+  %be.cond = icmp ult i32 %idx.inc, %umin
+  br i1 %be.cond, label %loop, label %exit
+
+ exit:
+  ret void
+}
+
+define void @max.unsigned.1(i32* %a, i32 %a_len, i32 %n) {
+; CHECK-LABEL: @max.unsigned.1
+ entry:
+  %umax.cmp = icmp ugt i32 %a_len, %n
+  %umax = select i1 %umax.cmp, i32 %a_len, i32 %n
+  %entry.cond = icmp ugt i32 5, %umax
+  br i1 %entry.cond, label %loop, label %exit
+
+ loop:
+  %idx = phi i32 [ 5, %entry ], [ %idx.inc, %latch ]
+  %idx.inc = add i32 %idx, 1
+  %in.bounds = icmp ugt i32 %idx, %a_len
+  br i1 %in.bounds, label %ok, label %latch
+; CHECK: br i1 true, label %ok, label %latch
+
+ ok:
+  %addr = getelementptr i32* %a, i32 %idx
+  store i32 %idx, i32* %addr
+  br label %latch
+
+ latch:
+  %be.cond = icmp ugt i32 %idx.inc, %umax
+  br i1 %be.cond, label %loop, label %exit
+
+ exit:
+  ret void
+}
+
+define void @max.unsigned.2(i32* %a, i32 %a_len, i32 %n) {
+; CHECK-LABEL: @max.unsigned.2
+ entry:
+  %umax.cmp = icmp ugt i32 %a_len, %n
+  %umax = select i1 %umax.cmp, i32 %a_len, i32 %n
+  %entry.cond = icmp ugt i32 5, %umax
+  br i1 %entry.cond, label %loop, label %exit
+
+ loop:
+  %idx = phi i32 [ 5, %entry ], [ %idx.inc, %latch ]
+  %idx.inc = add i32 %idx, 1
+  %in.bounds = icmp ult i32 %a_len, %idx
+  br i1 %in.bounds, label %ok, label %latch
+; CHECK: br i1 true, label %ok, label %latch
+
+ ok:
+  %addr = getelementptr i32* %a, i32 %idx
+  store i32 %idx, i32* %addr
+  br label %latch
+
+ latch:
+  %be.cond = icmp ugt i32 %idx.inc, %umax
+  br i1 %be.cond, label %loop, label %exit
+
+ exit:
+  ret void
+}
+
+define void @max.unsigned.3(i32* %a, i32 %n, i32 %init) {
+; CHECK-LABEL: @max.unsigned.3
+ entry:
+  %umax.cmp = icmp ugt i32 42, %n
+  %umax = select i1 %umax.cmp, i32 42, i32 %n
+  %entry.cond = icmp ugt i32 %init, %umax
+  br i1 %entry.cond, label %loop, label %exit
+
+ loop:
+  %idx = phi i32 [ %init, %entry ], [ %idx.inc, %latch ]
+  %idx.inc = add i32 %idx, 1
+  %in.bounds = icmp ugt i32 %idx, 42
+  br i1 %in.bounds, label %ok, label %latch
+; CHECK: br i1 true, label %ok, label %latch
+
+ ok:
+  %addr = getelementptr i32* %a, i32 %idx
+  store i32 %idx, i32* %addr
+  br label %latch
+
+ latch:
+  %be.cond = icmp ugt i32 %idx.inc, %umax
+  br i1 %be.cond, label %loop, label %exit
+
+ exit:
+  ret void
+}
+
+define void @max.unsigned.4(i32* %a, i32 %n, i32 %init) {
+; CHECK-LABEL: @max.unsigned.4
+ entry:
+  %umax.cmp = icmp ugt i32 42, %n
+  %umax = select i1 %umax.cmp, i32 42, i32 %n
+  %entry.cond = icmp ugt i32 %init, %umax
+  br i1 %entry.cond, label %loop, label %exit
+
+ loop:
+  %idx = phi i32 [ %init, %entry ], [ %idx.inc, %latch ]
+  %idx.inc = add i32 %idx, 1
+  %in.bounds = icmp ult i32 42, %idx
+  br i1 %in.bounds, label %ok, label %latch
+; CHECK: br i1 true, label %ok, label %latch
+
+ ok:
+  %addr = getelementptr i32* %a, i32 %idx
+  store i32 %idx, i32* %addr
+  br label %latch
+
+ latch:
+  %be.cond = icmp ugt i32 %idx.inc, %umax
+  br i1 %be.cond, label %loop, label %exit
+
+ exit:
+  ret void
+}