From b7219f9e807c2a8e91cd64be8314341fea6e92ad Mon Sep 17 00:00:00 2001 From: Evgeniy Stepanov Date: Fri, 13 Jul 2018 16:32:31 +0000 Subject: [PATCH] Revert "CallGraphSCCPass: iterate over all functions." This reverts commit r336419: use-after-free on CallGraph::FunctionMap elements due to the use of a stale iterator in CGPassManager::runOnModule. The iterator may be invalidated if a pass removes a function, ex.: llvm::LegacyInlinerBase::inlineCalls inlineCallsImpl llvm::CallGraph::removeFunctionFromModule git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@337018 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/SCCIterator.h | 24 +++--- lib/Analysis/CallGraphSCCPass.cpp | 110 +++++++++--------------- test/Transforms/Inline/always-inline.ll | 7 -- 3 files changed, 49 insertions(+), 92 deletions(-) diff --git a/include/llvm/ADT/SCCIterator.h b/include/llvm/ADT/SCCIterator.h index 2dc2b343df9..ab1dc4613be 100644 --- a/include/llvm/ADT/SCCIterator.h +++ b/include/llvm/ADT/SCCIterator.h @@ -90,7 +90,6 @@ class scc_iterator : public iterator_facade_base< /// Compute the next SCC using the DFS traversal. void GetNextSCC(); -public: scc_iterator(NodeRef entryN) : visitNum(0) { DFSVisitOne(entryN); GetNextSCC(); @@ -99,6 +98,12 @@ public: /// End is when the DFS stack is empty. scc_iterator() = default; +public: + static scc_iterator begin(const GraphT &G) { + return scc_iterator(GT::getEntryNode(G)); + } + static scc_iterator end(const GraphT &) { return scc_iterator(); } + /// Direct loop termination test which is more efficient than /// comparison with \c end(). bool isAtEnd() const { @@ -217,25 +222,16 @@ bool scc_iterator::hasLoop() const { return false; } -/// Construct the begin iterator for a deduced graph type T, starting from its -/// entry node. +/// Construct the begin iterator for a deduced graph type T. template scc_iterator scc_begin(const T &G) { - return scc_iterator(GraphTraits::getEntryNode(G)); + return scc_iterator::begin(G); } -/// Construct the begin iterator for a graph type T, starting from the specified -/// node. -template > -scc_iterator scc_begin(typename U::NodeRef N) { - return scc_iterator(N); -} - - /// Construct the end iterator for a deduced graph type T. +/// Construct the end iterator for a deduced graph type T. template scc_iterator scc_end(const T &G) { - return scc_iterator(); + return scc_iterator::end(G); } - } // end namespace llvm #endif // LLVM_ADT_SCCITERATOR_H diff --git a/lib/Analysis/CallGraphSCCPass.cpp b/lib/Analysis/CallGraphSCCPass.cpp index 6ed9b6129d7..ef61c65463f 100644 --- a/lib/Analysis/CallGraphSCCPass.cpp +++ b/lib/Analysis/CallGraphSCCPass.cpp @@ -17,7 +17,6 @@ #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" @@ -64,10 +63,6 @@ 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; @@ -453,78 +448,51 @@ 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"); - 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); - } + MaxSCCIterations.updateMax(Iteration); } - 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; diff --git a/test/Transforms/Inline/always-inline.ll b/test/Transforms/Inline/always-inline.ll index fe61992eac0..791eb94779b 100644 --- a/test/Transforms/Inline/always-inline.ll +++ b/test/Transforms/Inline/always-inline.ll @@ -316,10 +316,3 @@ define void @outer14() { call void @inner14() ret void } - -define internal i32 @outer15() { -; CHECK-LABEL: @outer15 -; CHECK: ret i32 1 - %res = call i32 @inner1() - ret i32 %res -} -- 2.50.1