1 files changed, 71 insertions, 39 deletions

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<CallGraphWrapperPass>().getCallGraph();
   bool Changed = doInitialization(CG);
-  
-  // Walk the callgraph in bottom-up SCC order.
-  scc_iterator<CallGraph*> 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<CallGraphNode *> &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<const Function *> 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<CallGraph *>(I->second.get());
+
+    CallGraphSCC CurSCC(CG, &CGI);
+    while (!CGI.isAtEnd()) {
+      const std::vector<CallGraphNode *> &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;