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,13 @@
   /// completely specialized and is no longer needed).
   void markFunctionUnreachable(Function *F);
 
+  /// Replace all uses and visit their users (optionally remove from parent).
+  void replaceUsesOfWith(Value *Old, Value *New, bool NotifyUsers=true,
+                                                 bool ForceDeletion=false);
+
+  /// Notify the visitor that this instruction has been deleted.
+  void invalidate(Instruction *I);
+
   void visit(Instruction *I);
   void visitCall(CallInst &I);
 };
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
@@ -21,6 +21,7 @@
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include <cassert>
 #include <utility>
 #include <vector>
@@ -68,6 +69,7 @@
   const DataLayout &DL;
   std::function<const TargetLibraryInfo &(Function &)> GetTLI;
   SmallPtrSet<BasicBlock *, 8> BBExecutable; // The BBs that are executable.
+  DenseSet<Value *> InvalidatedInsts; // Instructions which have been deleted.
   DenseMap<Value *, ValueLatticeElement>
       ValueState; // The state each value is in.
 
@@ -227,14 +229,6 @@
   // successors are reachable from a given terminator instruction.
   void getFeasibleSuccessors(Instruction &TI, SmallVectorImpl<bool> &Succs);
 
-  // OperandChangedState - This method is invoked on all of the users of an
-  // instruction that was just changed state somehow.  Based on this
-  // information, we need to update the specified user of this instruction.
-  void operandChangedState(Instruction *I) {
-    if (BBExecutable.count(I->getParent())) // Inst is executable?
-      visit(*I);
-  }
-
   // Add U as additional user of V.
   void addAdditionalUser(Value *V, User *U) {
     AdditionalUsers[V].insert(U);
@@ -372,6 +366,28 @@
           Users.push_back(I);
   }
 
+  void invalidate(Instruction *I) {
+    auto Iter = AdditionalUsers.find(I);
+    if (Iter != AdditionalUsers.end())
+      for (User *U : Iter->second)
+        if (auto *I = dyn_cast<Instruction>(U))
+          removePredicateInfoFor(I);
+    removeFromAdditionalUsers(I);
+    removeFromAdditionalUserOf(I);
+    AdditionalUsers.erase(I);
+    AdditionalUserOf.erase(I);
+    removeLatticeValueFor(I);
+    InvalidatedInsts.insert(I);
+  }
+
+  // OperandChangedState - This method is invoked on all of the users of an
+  // instruction that was just changed state somehow.  Based on this
+  // information, we need to update the specified user of this instruction.
+  void operandChangedState(Instruction *I) {
+    if (BBExecutable.count(I->getParent())) // Inst is executable?
+      visit(*I);
+  }
+
   DomTreeUpdater getDTU(Function &F) {
     auto A = AnalysisResults.find(&F);
     assert(A != AnalysisResults.end() && "Need analysis results for function.");
@@ -441,7 +457,13 @@
     return StructValues;
   }
 
-  void removeLatticeValueFor(Value *V) { ValueState.erase(V); }
+  void removeLatticeValueFor(Value *V) {
+    if (auto *STy = dyn_cast<StructType>(V->getType()))
+      for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
+        StructValueState.erase(std::make_pair(V, i));
+    else
+      ValueState.erase(V);
+  }
 
   const ValueLatticeElement &getLatticeValueFor(Value *V) const {
     assert(!V->getType()->isStructTy() &&
@@ -1667,6 +1689,47 @@
   Visitor->markFunctionUnreachable(F);
 }
 
+static bool canRemoveInstruction(Instruction *I) {
+  if (wouldInstructionBeTriviallyDead(I))
+    return true;
+
+  // Some instructions can be handled but are rejected above. Catch
+  // those cases by falling through to here.
+  // TODO: Mark globals as being constant earlier, so
+  // TODO: wouldInstructionBeTriviallyDead() knows that atomic loads
+  // TODO: are safe to remove.
+  return isa<LoadInst>(I);
+}
+
+void SCCPSolver::replaceUsesOfWith(Value *Old, Value *New, bool NotifyUsers,
+                                                           bool ForceDeletion) {
+  // Record uses of Old to avoid visiting irrelevant uses of New later.
+  SmallVector<Instruction *> ToNotify;
+
+  if (NotifyUsers) {
+    Visitor->findAdditionalUsersFor(Old, ToNotify);
+    for (User *U : Old->users())
+      if (auto *I = dyn_cast<Instruction>(U))
+        if (I != Old)
+          ToNotify.push_back(I);
+  }
+
+  Old->replaceAllUsesWith(New);
+
+  // Remove the instruction from Block and Solver.
+  if (auto *I = dyn_cast<Instruction>(Old)) {
+    if (canRemoveInstruction(I) || ForceDeletion) {
+      Visitor->invalidate(I);
+      I->eraseFromParent();
+    }
+  }
+
+  for (Instruction *I : ToNotify)
+    Visitor->operandChangedState(I);
+}
+
+void SCCPSolver::invalidate(Instruction *I) { Visitor->invalidate(I); }
+
 void SCCPSolver::visit(Instruction *I) { Visitor->visit(I); }
 
 void SCCPSolver::visitCall(CallInst &I) { Visitor->visitCall(I); }