diff --git a/llvm/include/llvm/Transforms/Utils/SCCPSolver.h b/llvm/include/llvm/Transforms/Utils/SCCPSolver.h
--- a/llvm/include/llvm/Transforms/Utils/SCCPSolver.h
+++ b/llvm/include/llvm/Transforms/Utils/SCCPSolver.h
@@ -165,6 +165,9 @@
   /// completely specialized and is no longer needed).
   void markFunctionUnreachable(Function *F);
 
+  /// Replace all uses and visit their users.
+  void replaceUsesOfWith(Value *Old, Value *New);
+
   void visit(Instruction *I);
   void visitCall(CallInst &I);
 };
diff --git a/llvm/lib/Transforms/IPO/FunctionSpecialization.cpp b/llvm/lib/Transforms/IPO/FunctionSpecialization.cpp
--- a/llvm/lib/Transforms/IPO/FunctionSpecialization.cpp
+++ b/llvm/lib/Transforms/IPO/FunctionSpecialization.cpp
@@ -308,25 +308,7 @@
   LLVM_DEBUG(dbgs() << "FnSpecialization: Replacing " << *V
                     << "\nFnSpecialization: with " << *Const << "\n");
 
-  // Record uses of V to avoid visiting irrelevant uses of const later.
-  SmallVector<Instruction *> UseInsts;
-  for (auto *U : V->users())
-    if (auto *I = dyn_cast<Instruction>(U))
-      if (Solver.isBlockExecutable(I->getParent()))
-        UseInsts.push_back(I);
-
-  V->replaceAllUsesWith(Const);
-
-  for (auto *I : UseInsts)
-    Solver.visit(I);
-
-  // Remove the instruction from Block and Solver.
-  if (auto *I = dyn_cast<Instruction>(V)) {
-    if (I->isSafeToRemove()) {
-      I->eraseFromParent();
-      Solver.removeLatticeValueFor(I);
-    }
-  }
+  Solver.replaceUsesOfWith(V, Const);
   return true;
 }
 
diff --git a/llvm/lib/Transforms/Scalar/SCCP.cpp b/llvm/lib/Transforms/Scalar/SCCP.cpp
--- a/llvm/lib/Transforms/Scalar/SCCP.cpp
+++ b/llvm/lib/Transforms/Scalar/SCCP.cpp
@@ -140,8 +140,7 @@
 
   LLVM_DEBUG(dbgs() << "  Constant: " << *Const << " = " << *V << '\n');
 
-  // Replaces all of the uses of a variable with uses of the constant.
-  V->replaceAllUsesWith(Const);
+  Solver.replaceUsesOfWith(V, Const);
   return true;
 }
 
@@ -154,9 +153,6 @@
     if (Inst.getType()->isVoidTy())
       continue;
     if (tryToReplaceWithConstant(Solver, &Inst)) {
-      if (Inst.isSafeToRemove())
-        Inst.eraseFromParent();
-
       MadeChanges = true;
       ++InstRemovedStat;
     } else if (isa<SExtInst>(&Inst)) {
@@ -340,7 +336,35 @@
   }
 }
 
-static bool removeNonFeasibleEdges(const SCCPSolver &Solver, BasicBlock *BB,
+// When unlinking two basic blocks, some of the successor's PHI
+// nodes might get eliminated. Their Lattice Value should be
+// removed from the Solver.
+static void removePredecessor(BasicBlock *BB, BasicBlock *Pred,
+                              SCCPSolver &Solver) {
+  // Use hasNUsesOrMore to bound the cost of this assertion for complex CFGs.
+  assert((BB->hasNUsesOrMore(16) || is_contained(predecessors(BB), Pred)) &&
+         "Pred is not a predecessor!");
+
+  // Return early if there are no PHI nodes to update.
+  if (BB->empty() || !isa<PHINode>(BB->begin()))
+    return;
+
+  unsigned NumPreds = cast<PHINode>(BB->front()).getNumIncomingValues();
+  for (PHINode &Phi : make_early_inc_range(BB->phis())) {
+    Phi.removeIncomingValue(Pred, /*KeepOneInputPHIs=*/false);
+
+    // If we have a single predecessor, removeIncomingValue may have erased the
+    // PHI node itself.
+    if (NumPreds == 1)
+      continue;
+
+    // Try to replace the PHI node with a constant value.
+    if (Value *PhiConstant = Phi.hasConstantValue())
+      Solver.replaceUsesOfWith(&Phi, PhiConstant);
+  }
+}
+
+static bool removeNonFeasibleEdges(SCCPSolver &Solver, BasicBlock *BB,
                                    DomTreeUpdater &DTU,
                                    BasicBlock *&NewUnreachableBB) {
   SmallPtrSet<BasicBlock *, 8> FeasibleSuccessors;
@@ -375,12 +399,13 @@
         continue;
       }
 
-      Succ->removePredecessor(BB);
+      removePredecessor(Succ, BB, Solver);
       Updates.push_back({DominatorTree::Delete, BB, Succ});
     }
 
     BranchInst::Create(OnlyFeasibleSuccessor, BB);
     TI->eraseFromParent();
+    Solver.removeLatticeValueFor(TI);
     DTU.applyUpdatesPermissive(Updates);
   } else if (FeasibleSuccessors.size() > 1) {
     SwitchInstProfUpdateWrapper SI(*cast<SwitchInst>(TI));
@@ -409,7 +434,7 @@
       }
 
       BasicBlock *Succ = CI->getCaseSuccessor();
-      Succ->removePredecessor(BB);
+      removePredecessor(Succ, BB, Solver);
       Updates.push_back({DominatorTree::Delete, BB, Succ});
       SI.removeCase(CI);
       // Don't increment CI, as we removed a case.
@@ -570,6 +595,7 @@
                 Value *Op = II->getOperand(0);
                 Inst.replaceAllUsesWith(Op);
                 Inst.eraseFromParent();
+                Solver.removeLatticeValueFor(&Inst);
               }
             }
           }
@@ -678,6 +704,7 @@
     while (!GV->use_empty()) {
       StoreInst *SI = cast<StoreInst>(GV->user_back());
       SI->eraseFromParent();
+      Solver.removeLatticeValueFor(SI);
       MadeChanges = true;
     }
     M.getGlobalList().erase(GV);
diff --git a/llvm/lib/Transforms/Utils/SCCPSolver.cpp b/llvm/lib/Transforms/Utils/SCCPSolver.cpp
--- a/llvm/lib/Transforms/Utils/SCCPSolver.cpp
+++ b/llvm/lib/Transforms/Utils/SCCPSolver.cpp
@@ -1730,6 +1730,28 @@
   Visitor->markFunctionUnreachable(F);
 }
 
+void SCCPSolver::replaceUsesOfWith(Value *Old, Value *New) {
+  // Record uses of Old to avoid visiting irrelevant uses of New later.
+  SmallVector<Instruction *> UseInsts;
+  for (User *U : Old->users())
+    if (auto *I = dyn_cast<Instruction>(U))
+      if (I != Old && isBlockExecutable(I->getParent()))
+        UseInsts.push_back(I);
+
+  Old->replaceAllUsesWith(New);
+
+  // Remove the instruction from Block and Solver.
+  if (auto *I = dyn_cast<Instruction>(Old)) {
+    if (I->isSafeToRemove()) {
+      I->eraseFromParent();
+      removeLatticeValueFor(I);
+    }
+  }
+
+  for (Instruction *I : UseInsts)
+    visit(I);
+}
+
 void SCCPSolver::visit(Instruction *I) { Visitor->visit(I); }
 
 void SCCPSolver::visitCall(CallInst &I) { Visitor->visitCall(I); }