Index: lib/Transforms/Scalar/SCCP.cpp
===================================================================
--- lib/Transforms/Scalar/SCCP.cpp
+++ lib/Transforms/Scalar/SCCP.cpp
@@ -1888,6 +1888,43 @@
   }
 }
 
+/// Update the condition for terminators that are branching on indeterminate
+/// values, forcing them to use a specific edge.
+static void forceIndeterminateEdge(Instruction* I, SCCPSolver &Solver) {
+  BasicBlock *Dest = nullptr;
+  Constant *C = nullptr;;
+  if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
+    if (!isa<ConstantInt>(SI->getCondition())) {
+      // Indeterminate switch; use first case value.
+      Dest = SI->case_begin()->getCaseSuccessor();
+      C = SI->case_begin()->getCaseValue();
+    }
+  } else if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
+    if (!isa<ConstantInt>(BI->getCondition())) {
+      // Indeterminate branch; use false.
+      Dest = BI->getSuccessor(1);
+      C = ConstantInt::getFalse(BI->getContext());
+    }
+  } else if (IndirectBrInst *IBR = dyn_cast<IndirectBrInst>(I)) {
+    if (!isa<BlockAddress>(IBR->getAddress()->stripPointerCasts())) {
+      // Indeterminate indirectbr; use successor 0.
+      Dest = IBR->getSuccessor(0);
+      C = BlockAddress::get(IBR->getSuccessor(0));
+    }
+  } else {
+    llvm_unreachable("Unexpected terminator instruction");
+  }
+  if (C) {
+    assert(Solver.isEdgeFeasible(I->getParent(), Dest) &&
+           "Didn't find feasible edge?");
+    (void)Dest;
+
+    I->setOperand(0, C);
+  }
+  return;
+}
+
+
 bool llvm::runIPSCCP(
     Module &M, const DataLayout &DL, const TargetLibraryInfo *TLI,
     function_ref<std::unique_ptr<PredicateInfo>(Function &)> getPredicateInfo) {
@@ -2017,32 +2054,10 @@
         // Ignore blockaddress users; BasicBlock's dtor will handle them.
         if (!I) continue;
 
+        // If we have forced an edge for an indeterminate value, then force the
+        // terminator to fold to that edge.
+        forceIndeterminateEdge(I, Solver);
         bool Folded = ConstantFoldTerminator(I->getParent());
-        if (!Folded) {
-          // If the branch can't be folded, we must have forced an edge
-          // for an indeterminate value. Force the terminator to fold
-          // to that edge.
-          Constant *C;
-          BasicBlock *Dest;
-          if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
-            Dest = SI->case_begin()->getCaseSuccessor();
-            C = SI->case_begin()->getCaseValue();
-          } else if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
-            Dest = BI->getSuccessor(1);
-            C = ConstantInt::getFalse(BI->getContext());
-          } else if (IndirectBrInst *IBR = dyn_cast<IndirectBrInst>(I)) {
-            Dest = IBR->getSuccessor(0);
-            C = BlockAddress::get(IBR->getSuccessor(0));
-          } else {
-            llvm_unreachable("Unexpected terminator instruction");
-          }
-          assert(Solver.isEdgeFeasible(I->getParent(), Dest) &&
-                 "Didn't find feasible edge?");
-          (void)Dest;
-
-          I->setOperand(0, C);
-          Folded = ConstantFoldTerminator(I->getParent());
-        }
         assert(Folded &&
               "Expect TermInst on constantint or blockaddress to be folded");
         (void) Folded;
Index: test/Transforms/SCCP/switch-undef-constantfoldterminator.ll
===================================================================
--- /dev/null
+++ test/Transforms/SCCP/switch-undef-constantfoldterminator.ll
@@ -0,0 +1,47 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -ipsccp -S | FileCheck %s
+
+; This test case used to end up like this:
+;
+;    While deleting: label %lor.rhs
+;    Use still stuck around after Def is destroyed:  br i1 undef, label %lor.rhs, label %land.end
+;    opt: ../lib/IR/Value.cpp:92: llvm::Value::~Value(): Assertion `use_empty() && "Uses remain when a value is destroyed!"' failed.
+;
+; due to ConstantFoldTerminator rewriting the switch into
+;
+;    br i1 undef, label %lor.rhs, label %land.end
+;
+; while SCCP implementation relied on the terminator to always be folded into
+; an unconditional branch when ConstantFoldTerminator returned true.
+
+define void @f4() {
+; CHECK-LABEL: define void @f4(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CALL:%.*]] = call i16 @f3(i16 undef)
+; CHECK-NEXT:    ret void
+;
+entry:
+  %call = call i16 @f3(i16 undef)
+  ret void
+}
+
+define internal i16 @f3(i16 %p1) {
+; CHECK-LABEL: define internal i16 @f3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LAND_END:%.*]]
+; CHECK:       land.end:
+; CHECK-NEXT:    ret i16 undef
+;
+entry:
+  switch i16 %p1, label %land.end [
+  i16 0, label %land.end
+  i16 1, label %lor.rhs
+  ]
+
+lor.rhs:
+  br label %land.end
+
+land.end:
+  ret i16 0
+}
+