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 @@ -172,6 +170,8 @@ /// Notify the visitor that this instruction has been deleted. void invalidate(Instruction *I); + void clearWorkLists(); + 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 @@ -255,6 +255,9 @@ /// \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)) @@ -286,15 +289,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 +312,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; } @@ -358,14 +334,6 @@ 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 @@ -468,7 +436,7 @@ 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); @@ -763,21 +731,14 @@ 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"); } } @@ -793,24 +754,29 @@ // 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 (auto &I : make_early_inc_range(BB)) - Changed |= tryToReplaceWithConstant(&I); - } + 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(&I)) + if (II->getIntrinsicID() == Intrinsic::ssa_copy) + Solver.replaceUsesOfWith(II, II->getOperand(0), + /*NotifyUsers=*/false, + /*ForceDeletion=*/true); } }; @@ -832,7 +798,6 @@ // Replace some unresolved constant arguments. propagateConstantArgs(FuncDecls); - WorkList.clear(); Changed = 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); InstReplacedStat++; MadeChanges = true; } @@ -194,10 +189,13 @@ 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, @@ -245,8 +243,7 @@ // 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) @@ -374,7 +371,74 @@ } } -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()), + /*NotifyUsers=*/true, + /*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; @@ -401,10 +465,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); @@ -421,11 +486,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) { @@ -455,7 +521,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. @@ -590,13 +656,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) @@ -606,22 +669,13 @@ 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(&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(&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 @@ -723,9 +777,11 @@ << "' is constant!\n"); while (!GV->use_empty()) { StoreInst *SI = cast(GV->user_back()); + Solver.invalidate(SI); SI->eraseFromParent(); MadeChanges = true; } + Solver.removeLatticeValueFor(GV); M.getGlobalList().erase(GV); ++IPNumGlobalConst; } 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 @@ -380,6 +380,13 @@ 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. @@ -1331,7 +1338,12 @@ 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 &Constraint = PI->getConstraint(); if (!Constraint) { @@ -1455,6 +1467,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 @@ -1471,6 +1487,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 @@ -1595,10 +1615,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) { @@ -1730,6 +1746,8 @@ 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); }