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

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;