diff --git a/llvm/include/llvm/Transforms/IPO/FunctionSpecialization.h b/llvm/include/llvm/Transforms/IPO/FunctionSpecialization.h --- a/llvm/include/llvm/Transforms/IPO/FunctionSpecialization.h +++ b/llvm/include/llvm/Transforms/IPO/FunctionSpecialization.h @@ -92,7 +92,6 @@ SmallPtrSet SpecializedFuncs; SmallPtrSet FullySpecialized; - SmallVector ReplacedWithConstant; DenseMap FunctionMetrics; public: @@ -104,7 +103,6 @@ ~FunctionSpecializer() { // Eliminate dead code. - removeDeadInstructions(); removeDeadFunctions(); } @@ -122,9 +120,6 @@ /// \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(); 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 @@ -75,8 +75,6 @@ /// 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 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 @@ -286,15 +286,6 @@ 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 " @@ -318,25 +309,7 @@ LLVM_DEBUG(dbgs() << "FnSpecialization: Replacing " << *V << "\nFnSpecialization: with " << *Const << "\n"); - // Record uses of V to avoid visiting irrelevant uses of const later. - SmallVector UseInsts; - for (auto *U : V->users()) - if (auto *I = dyn_cast(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(V)) { - if (I->isSafeToRemove()) { - ReplacedWithConstant.push_back(I); - 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 @@ -154,7 +154,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; } @@ -167,9 +167,6 @@ if (Inst.getType()->isVoidTy()) continue; if (tryToReplaceWithConstant(Solver, &Inst)) { - if (canRemoveInstruction(&Inst)) - Inst.eraseFromParent(); - MadeChanges = true; ++InstRemovedStat; } else if (isa(&Inst)) { @@ -183,9 +180,7 @@ 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, /*ForceDeletion=*/true); InstReplacedStat++; MadeChanges = true; } @@ -353,7 +348,73 @@ } } -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(BB->begin())) + return; + + unsigned NumPreds = cast(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 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()), + /*ForceDeletion=*/true); + ++NumInstrsRemoved; + } + + SmallVector 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 FeasibleSuccessors; @@ -380,10 +441,11 @@ SmallPtrSet SeenSuccs; SmallVector 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); @@ -400,11 +462,12 @@ 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) { @@ -434,7 +497,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. @@ -569,13 +632,10 @@ // 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) @@ -589,13 +649,11 @@ // 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(&Inst)) { - if (II->getIntrinsicID() == Intrinsic::ssa_copy) { - Value *Op = II->getOperand(0); - Inst.replaceAllUsesWith(Op); - Inst.eraseFromParent(); - } + if (auto *II = dyn_cast(&Inst)) { + if (II->getIntrinsicID() == Intrinsic::ssa_copy) { + Value *Op = II->getOperand(0); + Inst.replaceAllUsesWith(Op); + Inst.eraseFromParent(); } } } @@ -702,6 +760,7 @@ << "' is constant!\n"); while (!GV->use_empty()) { StoreInst *SI = cast(GV->user_back()); + Solver.invalidate(SI); SI->eraseFromParent(); MadeChanges = true; } 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 @@ -1327,7 +1327,10 @@ 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; + } const Optional &Constraint = PI->getConstraint(); if (!Constraint) { @@ -1338,6 +1341,8 @@ CmpInst::Predicate Pred = Constraint->Predicate; Value *OtherOp = Constraint->OtherOp; + addAdditionalUser(PI->Condition, &CB); + // Wait until OtherOp is resolved. if (getValueState(OtherOp).isUnknown()) { addAdditionalUser(OtherOp, &CB); @@ -1451,6 +1456,10 @@ 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 @@ -1467,6 +1476,10 @@ 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 @@ -1591,10 +1604,6 @@ 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) {