diff options
| -rw-r--r-- | llvm/include/llvm/Transforms/Scalar/SCCP.h | 11 | ||||
| -rw-r--r-- | llvm/lib/Transforms/IPO/SCCP.cpp | 35 | ||||
| -rw-r--r-- | llvm/lib/Transforms/Scalar/SCCP.cpp | 65 | ||||
| -rw-r--r-- | llvm/test/Transforms/SCCP/ipsccp-preserve-domtree.ll | 63 |
4 files changed, 131 insertions, 43 deletions
diff --git a/llvm/include/llvm/Transforms/Scalar/SCCP.h b/llvm/include/llvm/Transforms/Scalar/SCCP.h index e434d41d034..dfc3421df96 100644 --- a/llvm/include/llvm/Transforms/Scalar/SCCP.h +++ b/llvm/include/llvm/Transforms/Scalar/SCCP.h @@ -39,9 +39,14 @@ public: PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; -bool runIPSCCP( - Module &M, const DataLayout &DL, const TargetLibraryInfo *TLI, - function_ref<std::unique_ptr<PredicateInfo>(Function &)> getPredicateInfo); +/// Helper struct for bundling up the analysis results per function for IPSCCP. +struct AnalysisResultsForFn { + std::unique_ptr<PredicateInfo> PredInfo; + DominatorTree *DT; +}; + +bool runIPSCCP(Module &M, const DataLayout &DL, const TargetLibraryInfo *TLI, + function_ref<AnalysisResultsForFn(Function &)> getAnalysis); } // end namespace llvm #endif // LLVM_TRANSFORMS_SCALAR_SCCP_H diff --git a/llvm/lib/Transforms/IPO/SCCP.cpp b/llvm/lib/Transforms/IPO/SCCP.cpp index e2bb6f185c3..7cb7cdc0ebb 100644 --- a/llvm/lib/Transforms/IPO/SCCP.cpp +++ b/llvm/lib/Transforms/IPO/SCCP.cpp @@ -10,16 +10,20 @@ PreservedAnalyses IPSCCPPass::run(Module &M, ModuleAnalysisManager &AM) { const DataLayout &DL = M.getDataLayout(); auto &TLI = AM.getResult<TargetLibraryAnalysis>(M); auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager(); - auto getPredicateInfo = - [&FAM](Function &F) -> std::unique_ptr<PredicateInfo> { - return make_unique<PredicateInfo>(F, - FAM.getResult<DominatorTreeAnalysis>(F), - FAM.getResult<AssumptionAnalysis>(F)); + auto getAnalysis = [&FAM](Function &F) -> AnalysisResultsForFn { + DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(F); + return { + make_unique<PredicateInfo>(F, DT, FAM.getResult<AssumptionAnalysis>(F)), + &DT}; }; - if (!runIPSCCP(M, DL, &TLI, getPredicateInfo)) + if (!runIPSCCP(M, DL, &TLI, getAnalysis)) return PreservedAnalyses::all(); - return PreservedAnalyses::none(); + + PreservedAnalyses PA; + PA.preserve<DominatorTreeAnalysis>(); + PA.preserve<FunctionAnalysisManagerModuleProxy>(); + return PA; } namespace { @@ -44,14 +48,19 @@ public: const TargetLibraryInfo *TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); - auto getPredicateInfo = - [this](Function &F) -> std::unique_ptr<PredicateInfo> { - return make_unique<PredicateInfo>( - F, this->getAnalysis<DominatorTreeWrapperPass>(F).getDomTree(), - this->getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F)); + auto getAnalysis = [this](Function &F) -> AnalysisResultsForFn { + DominatorTree &DT = + this->getAnalysis<DominatorTreeWrapperPass>(F).getDomTree(); + return { + make_unique<PredicateInfo>( + F, DT, + this->getAnalysis<AssumptionCacheTracker>().getAssumptionCache( + F)), + nullptr}; // We cannot preserve the DT with the legacy pass manager, + // so so set it to nullptr. }; - return runIPSCCP(M, DL, TLI, getPredicateInfo); + return runIPSCCP(M, DL, TLI, getAnalysis); } void getAnalysisUsage(AnalysisUsage &AU) const override { diff --git a/llvm/lib/Transforms/Scalar/SCCP.cpp b/llvm/lib/Transforms/Scalar/SCCP.cpp index 1f98128f923..1d75e58e31f 100644 --- a/llvm/lib/Transforms/Scalar/SCCP.cpp +++ b/llvm/lib/Transforms/Scalar/SCCP.cpp @@ -247,19 +247,25 @@ class SCCPSolver : public InstVisitor<SCCPSolver> { using Edge = std::pair<BasicBlock *, BasicBlock *>; DenseSet<Edge> KnownFeasibleEdges; - DenseMap<Function *, std::unique_ptr<PredicateInfo>> PredInfos; + DenseMap<Function *, AnalysisResultsForFn> AnalysisResults; DenseMap<Value *, SmallPtrSet<User *, 2>> AdditionalUsers; public: - void addPredInfo(Function &F, std::unique_ptr<PredicateInfo> PI) { - PredInfos[&F] = std::move(PI); + void addAnalysis(Function &F, AnalysisResultsForFn A) { + AnalysisResults.insert({&F, std::move(A)}); } const PredicateBase *getPredicateInfoFor(Instruction *I) { - auto PI = PredInfos.find(I->getFunction()); - if (PI == PredInfos.end()) + auto A = AnalysisResults.find(I->getParent()->getParent()); + if (A == AnalysisResults.end()) return nullptr; - return PI->second->getPredicateInfoFor(I); + return A->second.PredInfo->getPredicateInfoFor(I); + } + + DominatorTree *getDomTree(Function &F) { + auto A = AnalysisResults.find(&F); + assert(A != AnalysisResults.end() && "Need analysis results for function."); + return A->second.DT; } SCCPSolver(const DataLayout &DL, const TargetLibraryInfo *tli) @@ -1927,10 +1933,9 @@ static void forceIndeterminateEdge(Instruction* I, SCCPSolver &Solver) { } } - bool llvm::runIPSCCP( Module &M, const DataLayout &DL, const TargetLibraryInfo *TLI, - function_ref<std::unique_ptr<PredicateInfo>(Function &)> getPredicateInfo) { + function_ref<AnalysisResultsForFn(Function &)> getAnalysis) { SCCPSolver Solver(DL, TLI); // Loop over all functions, marking arguments to those with their addresses @@ -1939,7 +1944,8 @@ bool llvm::runIPSCCP( 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 @@ bool llvm::runIPSCCP( // Iterate over all of the instructions in the module, replacing them with // constants if we have found them to be of constant values. - SmallVector<BasicBlock*, 512> BlocksToErase; for (Function &F : M) { if (F.isDeclaration()) continue; + SmallVector<BasicBlock *, 512> BlocksToErase; + if (Solver.isBlockExecutable(&F.front())) for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E; ++AI) { @@ -2029,23 +2036,27 @@ bool llvm::runIPSCCP( } } - // 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) + 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); + changeToUnreachable(BB->getFirstNonPHI(), /*UseLLVMTrap=*/false, + /*PreserveLCSSA=*/false, &DTU); + } if (!Solver.isBlockExecutable(&F.front())) NumInstRemoved += changeToUnreachable(F.front().getFirstNonPHI(), - /*UseLLVMTrap=*/false); + /*UseLLVMTrap=*/false, + /*PreserveLCSSA=*/false, &DTU); - // Now that all instructions in the function are constant folded, erase dead - // blocks, because we can now use ConstantFoldTerminator to get rid of - // in-edges. - for (unsigned i = 0, e = BlocksToErase.size(); i != e; ++i) { + // Now that all instructions in the function are constant folded, + // use ConstantFoldTerminator to get rid of in-edges, record DT updates and + // delete dead BBs. + for (BasicBlock *DeadBB : BlocksToErase) { // If there are any PHI nodes in this successor, drop entries for BB now. - BasicBlock *DeadBB = BlocksToErase[i]; for (Value::user_iterator UI = DeadBB->user_begin(), UE = DeadBB->user_end(); UI != UE;) { @@ -2060,16 +2071,16 @@ bool llvm::runIPSCCP( // If we have forced an edge for an indeterminate value, then force the // terminator to fold to that edge. forceIndeterminateEdge(I, Solver); - bool Folded = ConstantFoldTerminator(I->getParent()); + bool Folded = ConstantFoldTerminator(I->getParent(), + /*DeleteDeadConditions=*/false, + /*TLI=*/nullptr, &DTU); assert(Folded && "Expect TermInst on constantint or blockaddress to be folded"); (void) Folded; } - - // Finally, delete the basic block. - F.getBasicBlockList().erase(DeadBB); + // Mark dead BB for deletion. + DTU.deleteBB(DeadBB); } - BlocksToErase.clear(); for (BasicBlock &BB : F) { for (BasicBlock::iterator BI = BB.begin(), E = BB.end(); BI != E;) { diff --git a/llvm/test/Transforms/SCCP/ipsccp-preserve-domtree.ll b/llvm/test/Transforms/SCCP/ipsccp-preserve-domtree.ll new file mode 100644 index 00000000000..1b3cdd6051e --- /dev/null +++ b/llvm/test/Transforms/SCCP/ipsccp-preserve-domtree.ll @@ -0,0 +1,63 @@ +; 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,function(verify<domtree>)' -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 f1 +; NEW-PM-DAG: Running analysis: DominatorTreeAnalysis on f1 +; NEW-PM-DAG: Running analysis: PassInstrumentationAnalysis on f1 +; NEW-PM-DAG: Running analysis: DominatorTreeAnalysis on f2 +; NEW-PM-DAG: Running analysis: AssumptionAnalysis on f2 +; NEW-PM-DAG: Running analysis: PassInstrumentationAnalysis on f2 +; NEW-PM-NEXT: Invalidating all non-preserved analyses for: +; NEW-PM-NEXT: Invalidating all non-preserved analyses for: f1 +; NEW-PM-NEXT: Invalidating all non-preserved analyses for: f2 +; NEW-PM-NEXT: Running pass: GlobalOptPass on +; NEW-PM-DAG: Running analysis: BlockFrequencyAnalysis on f2 +; NEW-PM-DAG: Running analysis: LoopAnalysis on f2 +; NEW-PM-DAG: Running analysis: BranchProbabilityAnalysis on f2 +; NEW-PM-DAG: Running analysis: TargetLibraryAnalysis on f2 +; NEW-PM-NEXT: Running analysis: TargetIRAnalysis on f1 +; NEW-PM-NEXT: Invalidating all non-preserved analyses for: + +; IR-LABEL: @f1 +; IR-LABEL: entry: +; IR-NEXT: br label %bb2 +; IR-LABEL: bb2: +; IR-NEXT: undef + +; IR-LABEL: @f2 +; IR-NOT: icmp +; IR: br label %bbtrue +; IR-LABEL: bbtrue: +; IR-NEXT: ret i32 0 +define internal i32 @f1() readnone { +entry: + br i1 false, label %bb1, label %bb2 +bb1: + ret i32 10 +bb2: + ret i32 10 +} + +define i32 @f2(i32 %n) { + %i = call i32 @f1() + %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 +} |
