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

Might be more concise as:

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

7004–7006

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

7015–7016

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

insert a comma: "computes ~A, assign"

6954

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

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

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

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

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

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

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 assign `A' to NotOf and return true, else
+/// return false.
+static bool MatchNotExpr(const SCEV *Expr, const SCEV *&NotOf) {
+  const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Expr);
+  if (!Add || Add->getNumOperands() != 2) return false;
+
+  const SCEVConstant *AddLHS = dyn_cast<SCEVConstant>(Add->getOperand(0));
+  if (!(AddLHS && AddLHS->getValue()->getValue().isAllOnesValue()))
+    return false;
+
+  const SCEVMulExpr *AddRHS = dyn_cast<SCEVMulExpr>(Add->getOperand(1));
+  if (!AddRHS || AddRHS->getNumOperands() != 2) return false;
+
+  const SCEVConstant *MulLHS = dyn_cast<SCEVConstant>(AddRHS->getOperand(0));
+  if (!(MulLHS && MulLHS->getValue()->getValue().isAllOnesValue()))
+    return false;
+
+  NotOf = AddRHS->getOperand(1);
+  return true;
+}
+
+
+/// Is Expr an SMin or UMin of Candidate and some other values?
+template<typename MaxExprType>
+static bool IsMaxConsistingOf(ScalarEvolution &SE,
+                              const SCEV *MaybeMaxExpr,
+                              const SCEV *Candidate) {
+  const MaxExprType *MaxExpr = dyn_cast<MaxExprType>(MaybeMaxExpr);
+  if (!MaxExpr) return false;
+
+  for (unsigned i = 0, e = MaxExpr->getNumOperands(); i != e; i++) {
+    const SCEV *Difference = SE.getMinusSCEV(Candidate, MaxExpr->getOperand(i));
+    if (Difference->isZero())
+      return true;
+  }
+
+  return false;
+}
+
+
+/// Is Expr an SMin or UMin of Candidate and some other values?
+static bool IsMinConsistingOf(ScalarEvolution &SE,
+                              bool CheckSMin,
+                              const SCEV *MaybeMinExpr,
+                              const SCEV *Candidate) {
+  const SCEV *MaybeMaxExpr = nullptr;
+  if (!MatchNotExpr(MaybeMinExpr, MaybeMaxExpr))
+    return false;
+
+  if (CheckSMin)
+    return IsMaxConsistingOf<SCEVSMaxExpr>(
+        SE, MaybeMaxExpr, SE.getNotSCEV(Candidate));
+  else
+    return IsMaxConsistingOf<SCEVUMaxExpr>(
+        SE, MaybeMaxExpr, SE.getNotSCEV(Candidate));
+}
+
+
+/// Is LHS `Pred` RHS true on the virtue of LHS or RHS being a SMin
+/// expression?
+static bool IsKnownPredicateViaMinMax(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(SE, true /* CheckSMin */, LHS, RHS) ||
+          // A <= max(A, ...)
+          IsMaxConsistingOf<SCEVSMaxExpr>(SE, RHS, LHS);
+
+    case ICmpInst::ICMP_UGE:
+      std::swap(LHS, RHS);
+      // fall through
+    case ICmpInst::ICMP_ULE:
+      return
+          // min(A, ...) <= A
+          IsMinConsistingOf(SE, false /* CheckSMin */, LHS, RHS) ||
+          // A <= max(A, ...)
+          IsMaxConsistingOf<SCEVUMaxExpr>(SE, RHS, LHS);
+  }
+}
+
 /// 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) ||
+        IsKnownPredicateViaMinMax(*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 

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
+}