Index: llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp
===================================================================
--- llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp
+++ llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp
@@ -576,15 +576,33 @@
       BasicBlock *KnownSucc = nullptr;
       if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
         if (BI->isConditional()) {
-          if (Constant *SimpleCond =
-                  SimplifiedValues.lookup(BI->getCondition())) {
+          auto evaluateCondition = [&](Value *Cond) -> Optional<bool> {
+            if (SimplifiedValues.count(Cond))
+              Cond = SimplifiedValues[Cond];
+
             // Just take the first successor if condition is undef
-            if (isa<UndefValue>(SimpleCond))
-              KnownSucc = BI->getSuccessor(0);
-            else if (ConstantInt *SimpleCondVal =
-                         dyn_cast<ConstantInt>(SimpleCond))
-              KnownSucc = BI->getSuccessor(SimpleCondVal->isZero() ? 1 : 0);
-          }
+            if (isa<UndefValue>(Cond))
+              return true;
+            if (auto *CI = dyn_cast<ConstantInt>(Cond))
+              return !CI->isZero();
+
+            auto *ICI = dyn_cast<ICmpInst>(Cond);
+            if (!ICI)
+              return None;
+            Value *LHS = ICI->getOperand(0);
+            if (SimplifiedValues.count(LHS))
+              LHS = SimplifiedValues[LHS];
+            Value *RHS = ICI->getOperand(1);
+            if (SimplifiedValues.count(RHS))
+              RHS = SimplifiedValues[RHS];
+            if (!SE.isSCEVable(RHS->getType()))
+              return None;
+            return SE.evaluatePredicateAt(ICI->getPredicate(),
+                                          SE.getSCEV(LHS),
+                                          SE.getSCEV(RHS), BI);
+          };
+          if (auto Opt = evaluateCondition(BI->getCondition()))
+            KnownSucc = BI->getSuccessor(*Opt ? 0 : 1);
         }
       } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
         if (Constant *SimpleCond =
Index: llvm/test/Transforms/LoopUnroll/unroll-cost-symbolic-execute.ll
===================================================================
--- /dev/null
+++ llvm/test/Transforms/LoopUnroll/unroll-cost-symbolic-execute.ll
@@ -0,0 +1,320 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -loop-unroll -unroll-threshold=120 < %s | FileCheck %s
+
+; We can symbolically evaluate %sub to %limit on first iteration, and
+; to zero on all future iterations.
+; TODO: We could unroll this, but currently don't.
+define i32 @test_symbolic(i32 %limit) {
+; CHECK-LABEL: @test_symbolic(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[LOOP_GUARD:%.*]] = icmp sge i32 [[LIMIT:%.*]], 0
+; CHECK-NEXT:    br i1 [[LOOP_GUARD]], label [[LOOP_PREHEADER:%.*]], label [[FAILURE:%.*]]
+; CHECK:       loop.preheader:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[BACKEDGE]] ], [ 0, [[LOOP_PREHEADER]] ]
+; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[LIMIT]], [[SUM]]
+; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sge i32 [[SUB]], 0
+; CHECK-NEXT:    br i1 [[IS_POSITIVE]], label [[BACKEDGE]], label [[IF_FALSE:%.*]]
+; CHECK:       if.false:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[BACKEDGE]]
+; CHECK:       backedge:
+; CHECK-NEXT:    [[SUM_NEXT]] = add i32 [[SUM]], [[SUB]]
+; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 8
+; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]]
+; CHECK:       done:
+; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
+; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
+; CHECK:       failure:
+; CHECK-NEXT:    unreachable
+;
+entry:
+  %loop_guard = icmp sge i32 %limit, 0
+  br i1 %loop_guard, label %loop, label %failure
+
+loop:                                             ; preds = %backedge, %entry
+  %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ]
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+  %sub = sub i32 %limit, %sum
+  %is.positive = icmp sge i32 %sub, 0
+  br i1 %is.positive, label %backedge, label %if.false
+
+if.false:                                         ; preds = %loop
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  br label %backedge
+
+backedge:                                         ; preds = %if.false, %loop
+  %sum.next = add i32 %sum, %sub
+  %iv.next = add i32 %iv, 1
+  %loop.cond = icmp ne i32 %iv, 8
+  br i1 %loop.cond, label %loop, label %done
+
+done:                                             ; preds = %backedge
+  %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
+  ret i32 %sum.next.lcssa
+
+failure:
+  unreachable
+}
+
+; A tweaked version of the above where the evaluation produces constants
+; on each iteration.
+; TODO: None of the if.false blocks are reachable, it would be nice if
+; the output of unrolling made this obvious and didn't rely on other
+; passes to cleanup code the cost model already knew was dead.
+define i32 @test_constant(i32 %limit) {
+; CHECK-LABEL: @test_constant(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[LOOP_GUARD:%.*]] = icmp sge i32 [[LIMIT:%.*]], 0
+; CHECK-NEXT:    br i1 [[LOOP_GUARD]], label [[LOOP_PREHEADER:%.*]], label [[FAILURE:%.*]]
+; CHECK:       loop.preheader:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sle i32 0, [[LIMIT]]
+; CHECK-NEXT:    br i1 [[IS_POSITIVE]], label [[BACKEDGE:%.*]], label [[IF_FALSE:%.*]]
+; CHECK:       if.false:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[BACKEDGE]]
+; CHECK:       backedge:
+; CHECK-NEXT:    [[IS_POSITIVE_1:%.*]] = icmp sle i32 0, [[LIMIT]]
+; CHECK-NEXT:    br i1 [[IS_POSITIVE_1]], label [[BACKEDGE_1:%.*]], label [[IF_FALSE_1:%.*]]
+; CHECK:       failure:
+; CHECK-NEXT:    unreachable
+; CHECK:       if.false.1:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[BACKEDGE_1]]
+; CHECK:       backedge.1:
+; CHECK-NEXT:    [[IS_POSITIVE_2:%.*]] = icmp sle i32 0, [[LIMIT]]
+; CHECK-NEXT:    br i1 [[IS_POSITIVE_2]], label [[BACKEDGE_2:%.*]], label [[IF_FALSE_2:%.*]]
+; CHECK:       if.false.2:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[BACKEDGE_2]]
+; CHECK:       backedge.2:
+; CHECK-NEXT:    [[IS_POSITIVE_3:%.*]] = icmp sle i32 0, [[LIMIT]]
+; CHECK-NEXT:    br i1 [[IS_POSITIVE_3]], label [[BACKEDGE_3:%.*]], label [[IF_FALSE_3:%.*]]
+; CHECK:       if.false.3:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[BACKEDGE_3]]
+; CHECK:       backedge.3:
+; CHECK-NEXT:    [[IS_POSITIVE_4:%.*]] = icmp sle i32 0, [[LIMIT]]
+; CHECK-NEXT:    br i1 [[IS_POSITIVE_4]], label [[BACKEDGE_4:%.*]], label [[IF_FALSE_4:%.*]]
+; CHECK:       if.false.4:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[BACKEDGE_4]]
+; CHECK:       backedge.4:
+; CHECK-NEXT:    [[IS_POSITIVE_5:%.*]] = icmp sle i32 0, [[LIMIT]]
+; CHECK-NEXT:    br i1 [[IS_POSITIVE_5]], label [[BACKEDGE_5:%.*]], label [[IF_FALSE_5:%.*]]
+; CHECK:       if.false.5:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[BACKEDGE_5]]
+; CHECK:       backedge.5:
+; CHECK-NEXT:    [[IS_POSITIVE_6:%.*]] = icmp sle i32 0, [[LIMIT]]
+; CHECK-NEXT:    br i1 [[IS_POSITIVE_6]], label [[BACKEDGE_6:%.*]], label [[IF_FALSE_6:%.*]]
+; CHECK:       if.false.6:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[BACKEDGE_6]]
+; CHECK:       backedge.6:
+; CHECK-NEXT:    [[IS_POSITIVE_7:%.*]] = icmp sle i32 0, [[LIMIT]]
+; CHECK-NEXT:    br i1 [[IS_POSITIVE_7]], label [[BACKEDGE_7:%.*]], label [[IF_FALSE_7:%.*]]
+; CHECK:       if.false.7:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[BACKEDGE_7]]
+; CHECK:       backedge.7:
+; CHECK-NEXT:    [[IS_POSITIVE_8:%.*]] = icmp sle i32 0, [[LIMIT]]
+; CHECK-NEXT:    br i1 [[IS_POSITIVE_8]], label [[BACKEDGE_8:%.*]], label [[IF_FALSE_8:%.*]]
+; CHECK:       if.false.8:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[BACKEDGE_8]]
+; CHECK:       backedge.8:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %loop_guard = icmp sge i32 %limit, 0
+  br i1 %loop_guard, label %loop, label %failure
+
+loop:                                             ; preds = %backedge, %entry
+  %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ]
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+  %sub = sub i32 0, %sum
+  %is.positive = icmp sle i32 %sub, %limit
+  br i1 %is.positive, label %backedge, label %if.false
+
+if.false:                                         ; preds = %loop
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  br label %backedge
+
+backedge:                                         ; preds = %if.false, %loop
+  %sum.next = add i32 %sum, %sub
+  %iv.next = add i32 %iv, 1
+  %loop.cond = icmp ne i32 %iv, 8
+  br i1 %loop.cond, label %loop, label %done
+
+done:                                             ; preds = %backedge
+  %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
+  ret i32 %sum.next.lcssa
+
+failure:
+  unreachable
+}
+
+
+declare void @foo()