From 7ee46ed992690294cfe984366370cb4787fcf0f3 Mon Sep 17 00:00:00 2001 From: Tim Northover Date: Fri, 6 Jul 2018 08:04:47 +0000 Subject: CallGraphSCCPass: iterate over all functions. Previously we only iterated over functions reachable from the set of external functions in the module. But since some of the passes under this (notably the always-inliner and coroutine lowerer) are required for correctness, they need to run over everything. This just adds an extra layer of iteration over the CallGraph to keep track of which functions we've already visited and get the next batch of SCCs. Should fix PR38029. llvm-svn: 336419 --- llvm/lib/Analysis/CallGraphSCCPass.cpp | 110 +++++++++++++++++++++------------ 1 file changed, 71 insertions(+), 39 deletions(-) (limited to 'llvm/lib/Analysis/CallGraphSCCPass.cpp') diff --git a/llvm/lib/Analysis/CallGraphSCCPass.cpp b/llvm/lib/Analysis/CallGraphSCCPass.cpp index ef61c65463f..6ed9b6129d7 100644 --- a/llvm/lib/Analysis/CallGraphSCCPass.cpp +++ b/llvm/lib/Analysis/CallGraphSCCPass.cpp @@ -17,6 +17,7 @@ #include "llvm/Analysis/CallGraphSCCPass.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" #include "llvm/ADT/SCCIterator.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/CallGraph.h" @@ -63,6 +64,10 @@ public: /// whether any of the passes modifies the module, and if so, return true. bool runOnModule(Module &M) override; + /// Execute all of the passes scheduled for execution on a given SCC. Return + /// true if any passes modify the module. + bool runOnSCC(CallGraphSCC &SCC, CallGraph &CG); + using ModulePass::doInitialization; using ModulePass::doFinalization; @@ -448,51 +453,78 @@ bool CGPassManager::RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG, bool CGPassManager::runOnModule(Module &M) { CallGraph &CG = getAnalysis().getCallGraph(); bool Changed = doInitialization(CG); - - // Walk the callgraph in bottom-up SCC order. - scc_iterator CGI = scc_begin(&CG); - - CallGraphSCC CurSCC(CG, &CGI); - while (!CGI.isAtEnd()) { - // Copy the current SCC and increment past it so that the pass can hack - // on the SCC if it wants to without invalidating our iterator. - const std::vector &NodeVec = *CGI; - CurSCC.initialize(NodeVec); - ++CGI; - - // At the top level, we run all the passes in this pass manager on the - // functions in this SCC. However, we support iterative compilation in the - // case where a function pass devirtualizes a call to a function. For - // example, it is very common for a function pass (often GVN or instcombine) - // to eliminate the addressing that feeds into a call. With that improved - // information, we would like the call to be an inline candidate, infer - // mod-ref information etc. - // - // Because of this, we allow iteration up to a specified iteration count. - // This only happens in the case of a devirtualized call, so we only burn - // compile time in the case that we're making progress. We also have a hard - // iteration count limit in case there is crazy code. - unsigned Iteration = 0; - bool DevirtualizedCall = false; - do { - LLVM_DEBUG(if (Iteration) dbgs() - << " SCCPASSMGR: Re-visiting SCC, iteration #" << Iteration - << '\n'); - DevirtualizedCall = false; - Changed |= RunAllPassesOnSCC(CurSCC, CG, DevirtualizedCall); - } while (Iteration++ < MaxIterations && DevirtualizedCall); - - if (DevirtualizedCall) - LLVM_DEBUG(dbgs() << " CGSCCPASSMGR: Stopped iteration after " - << Iteration - << " times, due to -max-cg-scc-iterations\n"); - MaxSCCIterations.updateMax(Iteration); + DenseSet Visited; + + CallGraph::iterator INext; + for (auto I = CG.begin(), E = CG.end(); I != E;) { + // Walk the callgraph in bottom-up SCC order. + auto CGI = scc_begin(I->second.get()); + + CallGraphSCC CurSCC(CG, &CGI); + while (!CGI.isAtEnd()) { + const std::vector &NodeVec = *CGI; + + // Record that we've seen this set of functions so we don't run the pass + // twice. + for (auto *Elt : NodeVec) + Visited.insert(Elt->getFunction()); + + // Copy the current SCC and increment past it so that the pass can hack + // on the SCC if it wants to without invalidating our iterator. + CurSCC.initialize(NodeVec); + ++CGI; + + // If we've got all functions reachable from our chosen initial node, + // calculate the next node we need to search from now before parts of the + // graph are invalidated. + if (CGI.isAtEnd()) { + do + ++I; + while (I != E && Visited.count(I->first)); + } + + Changed |= runOnSCC(CurSCC, CG); + } } + Changed |= doFinalization(CG); return Changed; } +bool CGPassManager::runOnSCC(CallGraphSCC &CurSCC, CallGraph &CG) { + bool Changed = false; + + // At the top level, we run all the passes in this pass manager on the + // functions in this SCC. However, we support iterative compilation in the + // case where a function pass devirtualizes a call to a function. For + // example, it is very common for a function pass (often GVN or instcombine) + // to eliminate the addressing that feeds into a call. With that improved + // information, we would like the call to be an inline candidate, infer + // mod-ref information etc. + // + // Because of this, we allow iteration up to a specified iteration count. + // This only happens in the case of a devirtualized call, so we only burn + // compile time in the case that we're making progress. We also have a hard + // iteration count limit in case there is crazy code. + unsigned Iteration = 0; + bool DevirtualizedCall = false; + do { + LLVM_DEBUG(if (Iteration) dbgs() + << " SCCPASSMGR: Re-visiting SCC, iteration #" << Iteration + << '\n'); + DevirtualizedCall = false; + Changed |= RunAllPassesOnSCC(CurSCC, CG, DevirtualizedCall); + } while (Iteration++ < MaxIterations && DevirtualizedCall); + + if (DevirtualizedCall) + LLVM_DEBUG(dbgs() << " CGSCCPASSMGR: Stopped iteration after " << Iteration + << " times, due to -max-cg-scc-iterations\n"); + + MaxSCCIterations.updateMax(Iteration); + return Changed; +} + /// Initialize CG bool CGPassManager::doInitialization(CallGraph &CG) { bool Changed = false; -- cgit v1.2.3