[SCCP] Notify the Solver when an instruction is removed.

[labrinea]

Summary

Discussion: https://discourse.llvm.org/t/rfc-should-we-enable-function-specialization/61518

[labrinea]

This is a proof of concept for RFC: Should we enable Function Specialization?, not ready for review.

[labrinea]

llvm/lib/Transforms/Utils/SCCPSolver.cpp

1713

This is something weren't checking before. There can be self-referencing PHI nodes which get replaced and then we are visiting them, which results in a crash.

1718–1724

Also this should happen first and then visit the users, otherwise the solver keeps invalid lattice state in the meantime.

[labrinea]

rebased

[labrinea]

• rebased
• remove lattice value of deleted globals (fixes https://reviews.llvm.org/D128827)

[labrinea]

Changes from last revision:

• replace ssa_copy intrinsics on each iteration of Function Specialization
• Clear the Solver's worklist before each iteration of Function Specialization

[labrinea]

ping

[labrinea]

Abandoning in favor of D126455.

llvm/include/llvm/Transforms/IPO/FunctionSpecialization.h

class FunctionSpecializer {
   std::function<const TargetLibraryInfo &(Function &)> GetTLI;
 
   // The number of functions specialised, used for collecting statistics and
   // also in the cost model.
   unsigned NbFunctionsSpecialized = 0;
 
   SmallPtrSet<Function *, 4> SpecializedFuncs;
   SmallPtrSet<Function *, 4> FullySpecialized;
-  SmallVector<Instruction *> ReplacedWithConstant;
   DenseMap<Function *, CodeMetrics> FunctionMetrics;
 
 public:
   FunctionSpecializer(SCCPSolver &Solver, Module &M,
       std::function<AssumptionCache &(Function &)> GetAC,
       std::function<TargetTransformInfo &(Function &)> GetTTI,
       std::function<const TargetLibraryInfo &(Function &)> GetTLI)
     : Solver(Solver), M(M), GetAC(GetAC), GetTTI(GetTTI), GetTLI(GetTLI) {}
 
   ~FunctionSpecializer() {
     // Eliminate dead code.
-    removeDeadInstructions();
     removeDeadFunctions();
   }
 
   bool specialize(FuncList &FuncDecls);
 
 private:
   /// Iterate over the argument tracked functions see if there
   /// are any new constant values for the call instruction via
   /// stack variables.
   void propagateConstantArgs(FuncList &WorkList);
 
   /// Attempt to specialize functions in the module to enable constant
   /// propagation across function boundaries.
   ///
   /// \returns true if at least one function is specialized.
   bool specializeFunctions(FuncList &Candidates, FuncList &WorkList);
 
-  /// Clean up unused instructions.
-  void removeDeadInstructions();
-
   /// Clean up fully specialized functions.
   void removeDeadFunctions();
 
   /// Replace value and visit any affected users.
   bool tryToReplaceWithConstant(Value *V);
 
   // Compute the code metrics for function \p F.
   CodeMetrics &analyzeFunction(Function *F);

llvm/include/llvm/Transforms/Utils/SCCPSolver.h

public:
 
   void addAnalysis(Function &F, AnalysisResultsForFn A);
 
   /// markBlockExecutable - This method can be used by clients to mark all of
   /// the blocks that are known to be intrinsically live in the processed unit.
   /// This returns true if the block was not considered live before.
   bool markBlockExecutable(BasicBlock *BB);
 
-  const PredicateBase *getPredicateInfoFor(Instruction *I);
-
   DomTreeUpdater getDTU(Function &F);
 
   /// trackValueOfGlobalVariable - Clients can use this method to
   /// inform the SCCPSolver that it should track loads and stores to the
   /// specified global variable if it can.  This is only legal to call if
   /// performing Interprocedural SCCP.
   void trackValueOfGlobalVariable(GlobalVariable *GV);
 
public:
 
   /// 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 clearWorkLists();
+
   void visit(Instruction *I);
   void visitCall(CallInst &I);
 };
 
 } // namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

 
 
 /// Attempt to specialize functions in the module to enable constant
 /// propagation across function boundaries.
 ///
 /// \returns true if at least one function is specialized.
 bool FunctionSpecializer::specializeFunctions(FuncList &Candidates,
                                               FuncList &WorkList) {
+  WorkList.clear();
+  Solver.clearWorkLists();
+
   bool Changed = false;
   for (auto *F : Candidates) {
     if (!isCandidateFunction(F))
       continue;
 
     auto Cost = getSpecializationCost(F);
     if (!Cost.isValid()) {
       LLVM_DEBUG(
for (auto &Entry : Specializations)
       specializeFunction(F, Entry.second, WorkList);
   }
 
   updateSpecializedFuncs(Candidates, WorkList);
   NumFuncSpecialized += NbFunctionsSpecialized;
   return Changed;
 }
 
-void FunctionSpecializer::removeDeadInstructions() {
-  for (auto *I : ReplacedWithConstant) {
-    LLVM_DEBUG(dbgs() << "FnSpecialization: Removing dead instruction " << *I
-                      << "\n");
-    I->eraseFromParent();
-  }
-  ReplacedWithConstant.clear();
-}
-
 void FunctionSpecializer::removeDeadFunctions() {
   for (auto *F : FullySpecialized) {
     LLVM_DEBUG(dbgs() << "FnSpecialization: Removing dead function "
                       << F->getName() << "\n");
     F->eraseFromParent();
   }
   FullySpecialized.clear();
 }
 
 bool FunctionSpecializer::tryToReplaceWithConstant(Value *V) {
   if (!V->getType()->isSingleValueType() || isa<CallBase>(V) ||
       V->user_empty())
     return false;
 
   const ValueLatticeElement &IV = Solver.getLatticeValueFor(V);
   if (isOverdefined(IV))
     return false;
   auto *Const =
       isConstant(IV) ? Solver.getConstant(IV) : UndefValue::get(V->getType());
 
   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()) {
-      ReplacedWithConstant.push_back(I);
-      Solver.removeLatticeValueFor(I);
-    }
-  }
+  Solver.replaceUsesOfWith(V, Const);
   return true;
 }
 
 // Compute the code metrics for function \p F.
 CodeMetrics &FunctionSpecializer::analyzeFunction(Function *F) {
   auto I = FunctionMetrics.insert({F, CodeMetrics()});
   CodeMetrics &Metrics = I.first->second;
   if (I.second) {
     // The code metrics were not cached.
     SmallPtrSet<const Value *, 32> EphValues;
     CodeMetrics::collectEphemeralValues(F, &(GetAC)(*F), EphValues);
     for (BasicBlock &BB : *F)
       Metrics.analyzeBasicBlock(&BB, (GetTTI)(*F), EphValues);
 
     LLVM_DEBUG(dbgs() << "FnSpecialization: Code size of function "
                       << F->getName() << " is " << Metrics.NumInsts
                       << " instructions\n");
   }
   return Metrics;
 }
 
-/// Clone the function \p F and remove the ssa_copy intrinsics added by
-/// the SCCPSolver in the cloned version.
-static Function *cloneCandidateFunction(Function *F, ValueToValueMapTy &Mappings) {
-  Function *Clone = CloneFunction(F, Mappings);
-  removeSSACopy(*Clone);
-  return Clone;
-}
-
 /// This function decides whether it's worthwhile to specialize function
 /// \p F based on the known constant values its arguments can take on. It
 /// only discovers potential specialization opportunities without actually
 /// applying them.
 ///
 /// \returns true if any specializations have been found.
 bool FunctionSpecializer::calculateGains(Function *F, InstructionCost Cost,
                               SmallVectorImpl<CallSpecBinding> &WorkList) {
bool FunctionSpecializer::isCandidateFunction(Function *F) {
   LLVM_DEBUG(dbgs() << "FnSpecialization: Try function: " << F->getName()
                     << "\n");
   return true;
 }
 
 void FunctionSpecializer::specializeFunction(Function *F, SpecializationInfo &S,
                                              FuncList &WorkList) {
   ValueToValueMapTy Mappings;
-  Function *Clone = cloneCandidateFunction(F, Mappings);
+  Function *Clone = CloneFunction(F, Mappings);
 
   // Rewrite calls to the function so that they call the clone instead.
   rewriteCallSites(Clone, S.Args, Mappings);
 
   // Initialize the lattice state of the arguments of the function clone,
   // marking the argument on which we specialized the function constant
   // with the given value.
   Solver.markArgInFuncSpecialization(Clone, S.Args);
for (auto *CS : CallSitesToRewrite) {
     }
   }
 }
 
 void FunctionSpecializer::updateSpecializedFuncs(FuncList &Candidates,
                                                  FuncList &WorkList) {
   for (auto *F : WorkList) {
     SpecializedFuncs.insert(F);
+    Candidates.push_back(F);
 
     // Initialize the state of the newly created functions, marking them
     // argument-tracked and executable.
     if (F->hasExactDefinition() && !F->hasFnAttribute(Attribute::Naked))
       Solver.addTrackedFunction(F);
-
     Solver.addArgumentTrackedFunction(F);
-    Candidates.push_back(F);
     Solver.markBlockExecutable(&F->front());
-
-    // Replace the function arguments for the specialized functions.
-    for (Argument &Arg : F->args())
-      if (!Arg.use_empty() && tryToReplaceWithConstant(&Arg))
-        LLVM_DEBUG(dbgs() << "FnSpecialization: Replaced constant argument: "
-                          << Arg.getNameOrAsOperand() << "\n");
   }
 }
 
 bool FunctionSpecializer::specialize(FuncList &FuncDecls) {
   bool Changed = false;
 
   // Solve for constants.
   auto RunSCCPSolver = [&](auto &WorkList) {
     bool ResolvedUndefs = true;
 
     while (ResolvedUndefs) {
       // Not running the solver unnecessary is checked in regression test
       // nothing-to-do.ll, so if this debug message is changed, this regression
       // test needs updating too.
       LLVM_DEBUG(dbgs() << "FnSpecialization: Running solver\n");
-
       Solver.solve();
+
       LLVM_DEBUG(dbgs() << "FnSpecialization: Resolving undefs\n");
       ResolvedUndefs = false;
       for (Function *F : WorkList)
-        if (Solver.resolvedUndefsIn(*F))
-          ResolvedUndefs = true;
+        ResolvedUndefs |= Solver.resolvedUndefsIn(*F);
     }
 
     for (auto *F : WorkList) {
-      for (BasicBlock &BB : *F) {
-        if (!Solver.isBlockExecutable(&BB))
-          continue;
-        // FIXME: The solver may make changes to the function here, so set
-        // Changed, even if later function specialization does not trigger.
+      for (Argument &Arg : F->args())
+        if (!Arg.use_empty())
+          Changed |= tryToReplaceWithConstant(&Arg);
+      for (BasicBlock &BB : *F)
+        if (Solver.isBlockExecutable(&BB))
           for (auto &I : make_early_inc_range(BB))
             Changed |= tryToReplaceWithConstant(&I);
-      }
+      for (BasicBlock &BB : *F)
+        for (Instruction &I : llvm::make_early_inc_range(BB))
+          if (auto *II = dyn_cast<IntrinsicInst>(&I))
+            if (II->getIntrinsicID() == Intrinsic::ssa_copy)
+              Solver.replaceUsesOfWith(II, II->getOperand(0),
+                                       /*NotifyUsers=*/false,
+                                       /*ForceDeletion=*/true);
     }
   };
 
 #ifndef NDEBUG
   LLVM_DEBUG(dbgs() << "FnSpecialization: Worklist fn decls:\n");
   for (auto *F : FuncDecls)
     LLVM_DEBUG(dbgs() << "FnSpecialization: *) " << F->getName() << "\n");
 #endif
 
   SmallVector<Function *, 8> WorkList;
   unsigned I = 0;
   while (FuncSpecializationMaxIters != I++ &&
          specializeFunctions(FuncDecls, WorkList)) {
     LLVM_DEBUG(dbgs() << "FnSpecialization: Finished iteration " << I << "\n");
 
     // Run the solver for the specialized functions.
     RunSCCPSolver(WorkList);
 
     // Replace some unresolved constant arguments.
     propagateConstantArgs(FuncDecls);
 
-    WorkList.clear();
     Changed = true;
   }
 
   LLVM_DEBUG(dbgs() << "FnSpecialization: Number of specializations = "
                     << NumFuncSpecialized << "\n");
 
   // Remove any ssa_copy intrinsics that may have been introduced.
   removeSSACopy(M);
   return Changed;
 }

llvm/lib/Transforms/Scalar/SCCP.cpp

if (CB && ((CB->isMustTailCall() &&
     LLVM_DEBUG(dbgs() << "  Can\'t treat the result of call " << *CB
                       << " as a constant\n");
     return false;
   }
 
   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;
 }
 
 static bool simplifyInstsInBlock(SCCPSolver &Solver, BasicBlock &BB,
                                  SmallPtrSetImpl<Value *> &InsertedValues,
                                  Statistic &InstRemovedStat,
                                  Statistic &InstReplacedStat) {
   bool MadeChanges = false;
   for (Instruction &Inst : make_early_inc_range(BB)) {
     if (Inst.getType()->isVoidTy())
       continue;
     if (tryToReplaceWithConstant(Solver, &Inst)) {
-      if (canRemoveInstruction(&Inst))
-        Inst.eraseFromParent();
-
       MadeChanges = true;
       ++InstRemovedStat;
     } else if (isa<SExtInst>(&Inst)) {
       Value *ExtOp = Inst.getOperand(0);
       if (isa<Constant>(ExtOp) || InsertedValues.count(ExtOp))
         continue;
       const ValueLatticeElement &IV = Solver.getLatticeValueFor(ExtOp);
       if (!IV.isConstantRange(/*UndefAllowed=*/false))
         continue;
       if (IV.getConstantRange().isAllNonNegative()) {
         auto *ZExt = new ZExtInst(ExtOp, Inst.getType(), "", &Inst);
         ZExt->takeName(&Inst);
         InsertedValues.insert(ZExt);
-        Inst.replaceAllUsesWith(ZExt);
-        Solver.removeLatticeValueFor(&Inst);
-        Inst.eraseFromParent();
+        Solver.replaceUsesOfWith(&Inst, ZExt);
         InstReplacedStat++;
         MadeChanges = true;
       }
     }
   }
   return MadeChanges;
 }
 
-static bool removeNonFeasibleEdges(const SCCPSolver &Solver, BasicBlock *BB,
+static bool removeNonFeasibleEdges(SCCPSolver &Solver, BasicBlock *BB,
                                    DomTreeUpdater &DTU,
                                    BasicBlock *&NewUnreachableBB);
 
+static unsigned changeBBToUnreachable(BasicBlock *BB, DomTreeUpdater &DTU,
+                                      SCCPSolver &Solver);
+
 // runSCCP() - Run the Sparse Conditional Constant Propagation algorithm,
 // and return true if the function was modified.
 static bool runSCCP(Function &F, const DataLayout &DL,
                     const TargetLibraryInfo *TLI, DomTreeUpdater &DTU) {
   LLVM_DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n");
   SCCPSolver Solver(
       DL, [TLI](Function &F) -> const TargetLibraryInfo & { return *TLI; },
       F.getContext());
for (BasicBlock &BB : F) {
     }
 
     MadeChanges |= simplifyInstsInBlock(Solver, BB, InsertedValues,
                                         NumInstRemoved, NumInstReplaced);
   }
 
   // Remove unreachable blocks and non-feasible edges.
   for (BasicBlock *DeadBB : BlocksToErase)
-    NumInstRemoved += changeToUnreachable(DeadBB->getFirstNonPHI(),
-                                          /*PreserveLCSSA=*/false, &DTU);
+    NumInstRemoved += changeBBToUnreachable(DeadBB, DTU, Solver);
 
   BasicBlock *NewUnreachableBB = nullptr;
   for (BasicBlock &BB : F)
     MadeChanges |= removeNonFeasibleEdges(Solver, &BB, DTU, NewUnreachableBB);
 
   for (BasicBlock *DeadBB : BlocksToErase)
     if (!DeadBB->hasAddressTaken())
       DTU.deleteBB(DeadBB);
for (BasicBlock &BB : F) {
     }
 
     if (auto *RI = dyn_cast<ReturnInst>(BB.getTerminator()))
       if (!isa<UndefValue>(RI->getOperand(0)))
         ReturnsToZap.push_back(RI);
   }
 }
 
-static bool removeNonFeasibleEdges(const SCCPSolver &Solver, BasicBlock *BB,
+// When unlinking two basic blocks, some of the successor's PHI
+// nodes might get eliminated. The Solver must be notified of
+// their removal.
+//
+// (adapted from BasicBlock::removePredecessor)
+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);
+  }
+}
+
+// Insert an unreachable instruction before the first non-PHI node,
+// making it and the rest of the code in the block dead. Replace the
+// dead instructions with Undef and notify the Solver of their removal.
+//
+// (adapted from llvm::changeToUnreachable)
+static unsigned changeBBToUnreachable(BasicBlock *BB, DomTreeUpdater &DTU,
+                                      SCCPSolver &Solver) {
+  SmallSet<BasicBlock *, 8> UniqueSuccessors;
+
+  // Loop over all of the successors, removing BB's entry from any PHI nodes.
+  for (BasicBlock *Successor : successors(BB)) {
+    removePredecessor(Successor, BB, Solver);
+    UniqueSuccessors.insert(Successor);
+  }
+  // All instructions after this are dead.
+  Instruction *FirstNonPHI = BB->getFirstNonPHI();
+  auto *UI = new UnreachableInst(BB->getContext(), FirstNonPHI);
+  UI->setDebugLoc(FirstNonPHI->getDebugLoc());
+
+  unsigned NumInstrsRemoved = 0;
+  auto Range = llvm::make_range(FirstNonPHI->getIterator(), BB->end());
+  for (Instruction &Inst : llvm::make_early_inc_range(Range)) {
+    Solver.replaceUsesOfWith(&Inst, UndefValue::get(Inst.getType()),
+                             /*NotifyUsers=*/true,
+                             /*ForceDeletion=*/true);
+    ++NumInstrsRemoved;
+  }
+
+  SmallVector<DominatorTree::UpdateType, 8> Updates;
+  Updates.reserve(UniqueSuccessors.size());
+  for (BasicBlock *UniqueSuccessor : UniqueSuccessors)
+    Updates.push_back({DominatorTree::Delete, BB, UniqueSuccessor});
+  DTU.applyUpdates(Updates);
+
+  return NumInstrsRemoved;
+}
+
+static bool removeNonFeasibleEdges(SCCPSolver &Solver, BasicBlock *BB,
                                    DomTreeUpdater &DTU,
                                    BasicBlock *&NewUnreachableBB) {
   SmallPtrSet<BasicBlock *, 8> FeasibleSuccessors;
   bool HasNonFeasibleEdges = false;
   for (BasicBlock *Succ : successors(BB)) {
     if (Solver.isEdgeFeasible(BB, Succ))
       FeasibleSuccessors.insert(Succ);
     else
assert((isa<BranchInst>(TI) || isa<SwitchInst>(TI) ||
           isa<IndirectBrInst>(TI)) &&
          "Terminator must be a br, switch or indirectbr");
 
   if (FeasibleSuccessors.size() == 0) {
     // Branch on undef/poison, replace with unreachable.
     SmallPtrSet<BasicBlock *, 8> SeenSuccs;
     SmallVector<DominatorTree::UpdateType, 8> Updates;
     for (BasicBlock *Succ : successors(BB)) {
-      Succ->removePredecessor(BB);
+      removePredecessor(Succ, BB, Solver);
       if (SeenSuccs.insert(Succ).second)
         Updates.push_back({DominatorTree::Delete, BB, Succ});
     }
+    Solver.invalidate(TI);
     TI->eraseFromParent();
     new UnreachableInst(BB->getContext(), BB);
     DTU.applyUpdatesPermissive(Updates);
   } else if (FeasibleSuccessors.size() == 1) {
     // Replace with an unconditional branch to the only feasible successor.
     BasicBlock *OnlyFeasibleSuccessor = *FeasibleSuccessors.begin();
     SmallVector<DominatorTree::UpdateType, 8> Updates;
     bool HaveSeenOnlyFeasibleSuccessor = false;
     for (BasicBlock *Succ : successors(BB)) {
       if (Succ == OnlyFeasibleSuccessor && !HaveSeenOnlyFeasibleSuccessor) {
         // Don't remove the edge to the only feasible successor the first time
         // we see it. We still do need to remove any multi-edges to it though.
         HaveSeenOnlyFeasibleSuccessor = true;
         continue;
       }
 
-      Succ->removePredecessor(BB);
+      removePredecessor(Succ, BB, Solver);
       Updates.push_back({DominatorTree::Delete, BB, Succ});
     }
 
     BranchInst::Create(OnlyFeasibleSuccessor, BB);
+    Solver.invalidate(TI);
     TI->eraseFromParent();
     DTU.applyUpdatesPermissive(Updates);
   } else if (FeasibleSuccessors.size() > 1) {
     SwitchInstProfUpdateWrapper SI(*cast<SwitchInst>(TI));
     SmallVector<DominatorTree::UpdateType, 8> Updates;
 
     // If the default destination is unfeasible it will never be taken. Replace
     // it with a new block with a single Unreachable instruction.
if (FeasibleSuccessors.size() == 0) {
 
     for (auto CI = SI->case_begin(); CI != SI->case_end();) {
       if (FeasibleSuccessors.contains(CI->getCaseSuccessor())) {
         ++CI;
         continue;
       }
 
       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.
     }
 
     DTU.applyUpdatesPermissive(Updates);
   } else {
     llvm_unreachable("Must have at least one feasible successor");
for (BasicBlock &BB : F) {
                                           IPNumInstRemoved, IPNumInstReplaced);
     }
 
     DomTreeUpdater DTU = Solver.getDTU(F);
     // Change dead blocks to unreachable. We do it after replacing constants
     // in all executable blocks, because changeToUnreachable may remove PHI
     // nodes in executable blocks we found values for. The function's entry
     // block is not part of BlocksToErase, so we have to handle it separately.
-    for (BasicBlock *BB : BlocksToErase) {
-      NumInstRemoved += changeToUnreachable(BB->getFirstNonPHI(),
-                                            /*PreserveLCSSA=*/false, &DTU);
-    }
+    for (BasicBlock *BB : BlocksToErase)
+      NumInstRemoved += changeBBToUnreachable(BB, DTU, Solver);
     if (!Solver.isBlockExecutable(&F.front()))
-      NumInstRemoved += changeToUnreachable(F.front().getFirstNonPHI(),
-                                            /*PreserveLCSSA=*/false, &DTU);
+      NumInstRemoved += changeBBToUnreachable(&F.front(), DTU, Solver);
 
     BasicBlock *NewUnreachableBB = nullptr;
     for (BasicBlock &BB : F)
       MadeChanges |= removeNonFeasibleEdges(Solver, &BB, DTU, NewUnreachableBB);
 
     for (BasicBlock *DeadBB : BlocksToErase)
       if (!DeadBB->hasAddressTaken())
         DTU.deleteBB(DeadBB);
 
-    if (!SpecializeFunctions) {
-      // The Function Specializer will delete those after completion.
-      for (BasicBlock &BB : F) {
-        for (Instruction &Inst : llvm::make_early_inc_range(BB)) {
-          if (Solver.getPredicateInfoFor(&Inst)) {
-            if (auto *II = dyn_cast<IntrinsicInst>(&Inst)) {
-              if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
-                Value *Op = II->getOperand(0);
-                Inst.replaceAllUsesWith(Op);
-                Inst.eraseFromParent();
-              }
-            }
-          }
-        }
-      }
-    }
+    for (BasicBlock &BB : F)
+      for (Instruction &Inst : llvm::make_early_inc_range(BB))
+        if (auto *II = dyn_cast<IntrinsicInst>(&Inst))
+          if (II->getIntrinsicID() == Intrinsic::ssa_copy)
+            Solver.replaceUsesOfWith(II, II->getOperand(0),
+                                     /*NotifyUsers=*/false,
+                                     /*ForceDeletion=*/true);
   }
 
   // If we inferred constant or undef return values for a function, we replaced
   // all call uses with the inferred value.  This means we don't need to bother
   // actually returning anything from the function.  Replace all return
   // instructions with return undef.
   //
   // Do this in two stages: first identify the functions we should process, then
bool llvm::runIPSCCP(
   for (auto &I : make_early_inc_range(Solver.getTrackedGlobals())) {
     GlobalVariable *GV = I.first;
     if (isOverdefined(I.second))
       continue;
     LLVM_DEBUG(dbgs() << "Found that GV '" << GV->getName()
                       << "' is constant!\n");
     while (!GV->use_empty()) {
       StoreInst *SI = cast<StoreInst>(GV->user_back());
+      Solver.invalidate(SI);
       SI->eraseFromParent();
       MadeChanges = true;
     }
+    Solver.removeLatticeValueFor(GV);
     M.getGlobalList().erase(GV);
     ++IPNumGlobalConst;
   }
 
   if (SpecializeFunctions) {
     SmallVector<Function *> Candidates;
     for (Function *F : Solver.getArgumentTrackedFunctions())
       if (!F->hasFnAttribute(Attribute::NoDuplicate))
         Candidates.push_back(F);
 
     MadeChanges |= Specializer.specialize(Candidates);
   }
 
   return MadeChanges;
 }

llvm/lib/Transforms/Utils/SCCPSolver.cpp

void invalidate(Instruction *I) {
     removeFromAdditionalUsers(I);
     removeFromAdditionalUserOf(I);
     AdditionalUsers.erase(I);
     AdditionalUserOf.erase(I);
     removeLatticeValueFor(I);
     InvalidatedInsts.insert(I);
   }
 
+  void clearWorkLists() {
+    BBWorkList.clear();
+    InstWorkList.clear();
+    OverdefinedInstWorkList.clear();
+    InvalidatedInsts.clear();
+  }
+
   // 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);
   }
 
void SCCPInstVisitor::handleCallResult(CallBase &CB) {
   if (auto *II = dyn_cast<IntrinsicInst>(&CB)) {
     if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
       if (ValueState[&CB].isOverdefined())
         return;
 
       Value *CopyOf = CB.getOperand(0);
       ValueLatticeElement CopyOfVal = getValueState(CopyOf);
       const auto *PI = getPredicateInfoFor(&CB);
-      assert(PI && "Missing predicate info for ssa.copy");
+      if (!PI) {
+        mergeInValue(ValueState[&CB], &CB, CopyOfVal);
+        return;
+      }
+
+      addAdditionalUser(PI->Condition, &CB);
 
       const Optional<PredicateConstraint> &Constraint = PI->getConstraint();
       if (!Constraint) {
         mergeInValue(ValueState[&CB], &CB, CopyOfVal);
         return;
       }
 
       CmpInst::Predicate Pred = Constraint->Predicate;
void SCCPInstVisitor::solve() {
   // Process the work lists until they are empty!
   while (!BBWorkList.empty() || !InstWorkList.empty() ||
          !OverdefinedInstWorkList.empty()) {
     // Process the overdefined instruction's work list first, which drives other
     // things to overdefined more quickly.
     while (!OverdefinedInstWorkList.empty()) {
       Value *I = OverdefinedInstWorkList.pop_back_val();
 
+      // Skip invalid instruction.
+      if (InvalidatedInsts.count(I))
+        continue;
+
       LLVM_DEBUG(dbgs() << "\nPopped off OI-WL: " << *I << '\n');
 
       // "I" got into the work list because it either made the transition from
       // bottom to constant, or to overdefined.
       //
       // Anything on this worklist that is overdefined need not be visited
       // since all of its users will have already been marked as overdefined
       // Update all of the users of this instruction's value.
       //
       markUsersAsChanged(I);
     }
 
     // Process the instruction work list.
     while (!InstWorkList.empty()) {
       Value *I = InstWorkList.pop_back_val();
 
+      // Skip invalid instruction.
+      if (InvalidatedInsts.count(I))
+        continue;
+
       LLVM_DEBUG(dbgs() << "\nPopped off I-WL: " << *I << '\n');
 
       // "I" got into the work list because it made the transition from undef to
       // constant.
       //
       // Anything on this worklist that is overdefined need not be visited
       // since all of its users will have already been marked as overdefined.
       // Update all of the users of this instruction's value.

 void SCCPSolver::addAnalysis(Function &F, AnalysisResultsForFn A) {
   return Visitor->addAnalysis(F, std::move(A));
 }
 
 bool SCCPSolver::markBlockExecutable(BasicBlock *BB) {
   return Visitor->markBlockExecutable(BB);
 }
 
-const PredicateBase *SCCPSolver::getPredicateInfoFor(Instruction *I) {
-  return Visitor->getPredicateInfoFor(I);
-}
-
 DomTreeUpdater SCCPSolver::getDTU(Function &F) { return Visitor->getDTU(F); }
 
 void SCCPSolver::trackValueOfGlobalVariable(GlobalVariable *GV) {
   Visitor->trackValueOfGlobalVariable(GV);
 }
 
 void SCCPSolver::addTrackedFunction(Function *F) {
   Visitor->addTrackedFunction(F);
void SCCPSolver::markFunctionUnreachable(Function *F) {
   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::clearWorkLists() { Visitor->clearWorkLists(); }
+
 void SCCPSolver::visit(Instruction *I) { Visitor->visit(I); }
 
 void SCCPSolver::visitCall(CallInst &I) { Visitor->visitCall(I); }