Index: include/llvm/Transforms/Scalar/SCCP.h =================================================================== --- include/llvm/Transforms/Scalar/SCCP.h +++ include/llvm/Transforms/Scalar/SCCP.h @@ -39,9 +39,14 @@ PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; -bool runIPSCCP( - Module &M, const DataLayout &DL, const TargetLibraryInfo *TLI, - function_ref(Function &)> getPredicateInfo); +/// Helper struct for bundling up the analysis per function for IPSCCP. +struct AnalysisForFn { + std::unique_ptr PredInfo; + DominatorTree *DT; +}; + +bool runIPSCCP(Module &M, const DataLayout &DL, const TargetLibraryInfo *TLI, + function_ref getAnalysis); } // end namespace llvm #endif // LLVM_TRANSFORMS_SCALAR_SCCP_H Index: lib/Transforms/IPO/SCCP.cpp =================================================================== --- lib/Transforms/IPO/SCCP.cpp +++ lib/Transforms/IPO/SCCP.cpp @@ -10,16 +10,20 @@ const DataLayout &DL = M.getDataLayout(); auto &TLI = AM.getResult(M); auto &FAM = AM.getResult(M).getManager(); - auto getPredicateInfo = - [&FAM](Function &F) -> std::unique_ptr { - return make_unique(F, - FAM.getResult(F), - FAM.getResult(F)); + auto getAnalysis = [&FAM](Function &F) -> AnalysisForFn { + DominatorTree &DT = FAM.getResult(F); + return { + make_unique(F, DT, FAM.getResult(F)), + &DT}; }; - if (!runIPSCCP(M, DL, &TLI, getPredicateInfo)) + if (!runIPSCCP(M, DL, &TLI, getAnalysis)) return PreservedAnalyses::all(); - return PreservedAnalyses::none(); + + PreservedAnalyses PA; + PA.preserve(); + PA.preserve(); + return PA; } namespace { @@ -44,14 +48,18 @@ const TargetLibraryInfo *TLI = &getAnalysis().getTLI(); - auto getPredicateInfo = - [this](Function &F) -> std::unique_ptr { - return make_unique( - F, this->getAnalysis(F).getDomTree(), - this->getAnalysis().getAssumptionCache(F)); + auto getAnalysis = [this](Function &F) -> AnalysisForFn { + DominatorTree &DT = + this->getAnalysis(F).getDomTree(); + return { + make_unique( + F, DT, + this->getAnalysis().getAssumptionCache( + F)), + nullptr}; }; - return runIPSCCP(M, DL, TLI, getPredicateInfo); + return runIPSCCP(M, DL, TLI, getAnalysis); } void getAnalysisUsage(AnalysisUsage &AU) const override { Index: lib/Transforms/Scalar/SCCP.cpp =================================================================== --- lib/Transforms/Scalar/SCCP.cpp +++ lib/Transforms/Scalar/SCCP.cpp @@ -247,19 +247,25 @@ using Edge = std::pair; DenseSet KnownFeasibleEdges; - DenseMap> PredInfos; + DenseMap AnalysisInfo; DenseMap> AdditionalUsers; public: - void addPredInfo(Function &F, std::unique_ptr PI) { - PredInfos[&F] = std::move(PI); + void addAnalysis(Function &F, AnalysisForFn A) { + AnalysisInfo.insert({&F, std::move(A)}); } const PredicateBase *getPredicateInfoFor(Instruction *I) { - auto PI = PredInfos.find(I->getFunction()); - if (PI == PredInfos.end()) + auto A = AnalysisInfo.find(I->getParent()->getParent()); + if (A == AnalysisInfo.end()) return nullptr; - return PI->second->getPredicateInfoFor(I); + return A->second.PredInfo->getPredicateInfoFor(I); + } + + DominatorTree *getDomTree(Function &F) { + auto A = AnalysisInfo.find(&F); + assert(A != AnalysisInfo.end() && "Need analysis for function."); + return A->second.DT; } SCCPSolver(const DataLayout &DL, const TargetLibraryInfo *tli) @@ -1927,10 +1933,9 @@ } } - -bool llvm::runIPSCCP( - Module &M, const DataLayout &DL, const TargetLibraryInfo *TLI, - function_ref(Function &)> getPredicateInfo) { +bool llvm::runIPSCCP(Module &M, const DataLayout &DL, + const TargetLibraryInfo *TLI, + function_ref getAnalysis) { SCCPSolver Solver(DL, TLI); // Loop over all functions, marking arguments to those with their addresses @@ -1939,7 +1944,8 @@ if (F.isDeclaration()) continue; - Solver.addPredInfo(F, getPredicateInfo(F)); + Solver.addAnalysis(F, getAnalysis(F)); + // Determine if we can track the function's return values. If so, add the // function to the solver's set of return-tracked functions. if (canTrackReturnsInterprocedurally(&F)) @@ -1988,12 +1994,13 @@ // Iterate over all of the instructions in the module, replacing them with // constants if we have found them to be of constant values. - SmallVector BlocksToErase; for (Function &F : M) { if (F.isDeclaration()) continue; + SmallVector BlocksToErase; + if (Solver.isBlockExecutable(&F.front())) for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E; ++AI) { @@ -2029,16 +2036,28 @@ } } - // 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(), /*UseLLVMTrap=*/false); - if (!Solver.isBlockExecutable(&F.front())) - NumInstRemoved += changeToUnreachable(F.front().getFirstNonPHI(), - /*UseLLVMTrap=*/false); + if (Solver.getDomTree(F)) { + DomTreeUpdater DTU(*Solver.getDomTree(F), + DomTreeUpdater::UpdateStrategy::Lazy); + // 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(), /*UseLLVMTrap=*/false, + /*PreserveLCSSA=*/false, &DTU); + if (!Solver.isBlockExecutable(&F.front())) + NumInstRemoved += changeToUnreachable(F.front().getFirstNonPHI(), + /*UseLLVMTrap=*/false); + } else { + for (BasicBlock *BB : BlocksToErase) + NumInstRemoved += + changeToUnreachable(BB->getFirstNonPHI(), /*UseLLVMTrap=*/false); + if (!Solver.isBlockExecutable(&F.front())) + NumInstRemoved += changeToUnreachable(F.front().getFirstNonPHI(), + /*UseLLVMTrap=*/false); + } // Now that all instructions in the function are constant folded, erase dead // blocks, because we can now use ConstantFoldTerminator to get rid of @@ -2069,7 +2088,6 @@ // Finally, delete the basic block. F.getBasicBlockList().erase(DeadBB); } - BlocksToErase.clear(); for (BasicBlock &BB : F) { for (BasicBlock::iterator BI = BB.begin(), E = BB.end(); BI != E;) { Index: test/Transforms/SCCP/ipsccp-preserve-domtree.ll =================================================================== --- /dev/null +++ test/Transforms/SCCP/ipsccp-preserve-domtree.ll @@ -0,0 +1,53 @@ +; Basic test to check that DominatorTreeAnalysis is preserved by IPSCCP and +; the following analysis can re-use it. The test contains two trivial functions +; IPSCCP can simplify, so we can test the case where IPSCCP makes changes. + +; RUN: opt -disable-verify -debug-pass-manager \ +; RUN: -passes='ipsccp,globalopt' -S %s 2>&1 \ +; RUN: | FileCheck -check-prefixes='IR,NEW-PM' %s + +; RUN: opt -passes='ipsccp' -verify-dom-info -S %s | FileCheck -check-prefixes='IR' %s + +; NEW-PM: Starting llvm::Module pass manager run. +; NEW-PM-NEXT: Running pass: IPSCCPPass +; NEW-PM-DAG: Running analysis: TargetLibraryAnalysis +; NEW-PM-DAG: Running analysis: InnerAnalysisManagerProxy +; NEW-PM-DAG: Running analysis: AssumptionAnalysis on f +; NEW-PM-DAG: Running analysis: PassInstrumentationAnalysis on f +; NEW-PM-DAG: Running analysis: DominatorTreeAnalysis on foo +; NEW-PM-DAG: Running analysis: AssumptionAnalysis on foo +; NEW-PM-NEXT: Invalidating all non-preserved analyses for: +; NEW-PM-NEXT: Invalidating all non-preserved analyses for: f +; NEW-PM-NEXT: Invalidating all non-preserved analyses for: foo +; NEW-PM-NEXT: Running pass: GlobalOptPass on +; NEW-PM-NEXT: Running analysis: BlockFrequencyAnalysis on foo +; NEW-PM-NEXT: Running analysis: LoopAnalysis on foo +; NEW-PM-NEXT: Running analysis: BranchProbabilityAnalysis on foo +; NEW-PM-NEXT: Running analysis: TargetLibraryAnalysis on foo +; NEW-PM-NEXT: Running analysis: TargetIRAnalysis on f +; NEW-PM-NEXT: Invalidating all non-preserved analyses for: + +; IR-LABEL: @f +; IR-NEXT: undef + +; IR-LABEL: @foo +; IR-NOT: icmp +; IR: br label %bbtrue +; IR-LABEL: bbtrue: +; IR-NEXT: ret i32 0 +define internal i32 @f() readnone { + ret i32 10 +} + +define i32 @foo(i32 %n) local_unnamed_addr { + %i = call i32 @f() + %cmp = icmp eq i32 %i, 10 + br i1 %cmp, label %bbtrue, label %bbfalse + +bbtrue: + ret i32 0 + +bbfalse: + %res = add i32 %n, %i + ret i32 %res +}