CallGraph passes: iterate over all functions rather than just externally visible ones

[t.p.northover]

Summary

From https://llvm.org/PR38029, we were failing to always_inline a function that's called from a static function not otherwise referenced. Since libc++ uses always_inline for functions it doesn't want to build into the shared object, this caused the valid C++ code

#include <string> 
static std::string f() { return std::string(); } 
int main() { (void) f; }

to fail with a linker error (there's no basic_string::basic_string in libc++.so). In the big scheme there are two ways this could be fixed. Either we somehow guarantee that unused internal functions are dropped, or we ensure that the always-inliner handles all functions.

This patch fixes the inliner (indirectly) since IMO there could be legitimate reasons to retain unused functions (e.g. debuggability) and some of the passes involved violate correctness contracts if not run on everything -- the AlwaysInliner and coroutine lowering pass for example.

What it actually does is put logic into CallGraphSCCPass to make sure that all nodes of the CallGraph are visited, not just the ones accessible from the externals node.

As an alternative I considered adapting scc_iterator to do this by default when the GraphTraits allow for it, but discarded that both because it involved nasty template magic and because it was inconsistent with the other graph iterators in ADT (which all only pursue nodes accessible from GraphTraits::getEntryNode).

[dexonsmith]

Awesome. I wonder, would it be worth measuring compile-time impact for optimized builds?

llvm/include/llvm/ADT/SCCIterator.h

101–102

It's weird to have begin() take a NodeRef and end() take a GraphT, but I wonder: do we need these at all?

llvm/lib/Analysis/CallGraphSCCPass.cpp

455–456

Might as well add a space to CallGraph * (or have clang-format do it) since you're touching this line. Also, I wonder if auto is just as clear as scc_iterator<...> here, since we're calling a begin function?

456

I would have expected DenseSet or SmallDenseSet. Is there a reason you're preferring std::set here?

458

I think if (!Visited.count(I->first)) might be more clear.

459

Can you make this auto *Elt so it's clear that it's a raw pointer?

[t.p.northover]

Thanks for looking at the patch.

I wonder, would it be worth measuring compile-time impact for optimized builds?

Very worthwhile because it revealed a problem with the iteration scheme. CallGraph nodes can become stale when the passes are run so I changed it to find the next node we're going to start from before running them.

As for actual compile time, across the test-suite it actually seemed to improve things by a tiny amount (0.1%). I don't actually trust that result, but it probably means any degradation is negligible.

llvm/include/llvm/ADT/SCCIterator.h

101–102

Yep, they are pretty weird. I'll make the constructors public and get rid of them.

llvm/lib/Analysis/CallGraphSCCPass.cpp

456

Yes, I somehow forgot about DenseSet. I deliberately avoided a Small variant because I can't imagine there are many translation units with a usefully small number of functions. So I'll update it do DenseSet.

[t.p.northover]

Address review comments and rework iteration to always find next location before modifying the current one.

[dexonsmith]

LGTM.

llvm/lib/Analysis/CallGraphSCCPass.cpp

478–479

You might add " before it's invalidated" or something to make it more clear why this is here.

[t.p.northover]

Thanks Duncan. Committed as r336419.

llvm/include/llvm/ADT/SCCIterator.h

class scc_iterator : public iterator_facade_base<
   void DFSVisitOne(NodeRef N);
 
   /// The stack-based DFS traversal; defined below.
   void DFSVisitChildren();
 
   /// Compute the next SCC using the DFS traversal.
   void GetNextSCC();
 
+public:
   scc_iterator(NodeRef entryN) : visitNum(0) {
     DFSVisitOne(entryN);
     GetNextSCC();
   }
 
   /// 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 {
     assert(!CurrentSCC.empty() || VisitStack.empty());
     return CurrentSCC.empty();
   }
 
   bool operator==(const scc_iterator &x) const {
     return VisitStack == x.VisitStack && CurrentSCC == x.CurrentSCC;
bool scc_iterator<GraphT, GT>::hasLoop() const {
     NodeRef N = CurrentSCC.front();
     for (ChildItTy CI = GT::child_begin(N), CE = GT::child_end(N); CI != CE;
          ++CI)
       if (*CI == N)
         return true;
     return false;
   }
 
-/// Construct the begin iterator for a deduced graph type T.
+/// Construct the begin iterator for a deduced graph type T, starting from its
+/// entry node.
 template <class T> scc_iterator<T> scc_begin(const T &G) {
-  return scc_iterator<T>::begin(G);
+  return scc_iterator<T>(GraphTraits<T>::getEntryNode(G));
+}
+
+/// Construct the begin iterator for a graph type T, starting from the specified
+/// node.
+template <class T, class U = GraphTraits<T>>
+scc_iterator<T, U> scc_begin(typename U::NodeRef N) {
+  return scc_iterator<T>(N);
 }
 
   /// Construct the end iterator for a deduced graph type T.
 template <class T> scc_iterator<T> scc_end(const T &G) {
-  return scc_iterator<T>::end(G);
+  return scc_iterator<T>();
 }
 
+
 } // end namespace llvm
 
 #endif // LLVM_ADT_SCCITERATOR_H

llvm/lib/Analysis/CallGraphSCCPass.cpp

 // there may be cycles in the call graph, passes of this type operate on the
 // call-graph in SCC order: that is, they process function bottom-up, except for
 // recursive functions, which they process all at once.
 //
 //===----------------------------------------------------------------------===//
 
 #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"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/LegacyPassManagers.h"
public:
   static char ID;
 
   explicit CGPassManager() : ModulePass(ID), PMDataManager() {}
 
   /// Execute all of the passes scheduled for execution.  Keep track of
   /// 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;
 
   bool doInitialization(CallGraph &CG);
   bool doFinalization(CallGraph &CG);
 
   /// Pass Manager itself does not invalidate any analysis info.
   void getAnalysisUsage(AnalysisUsage &Info) const override {
if (!CallGraphUpToDate)
     DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
   return Changed;
 }
 
 /// Execute all of the passes scheduled for execution.  Keep track of
 /// whether any of the passes modifies the module, and if so, return true.
 bool CGPassManager::runOnModule(Module &M) {
   CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
   bool Changed = doInitialization(CG);
-  
+  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.
-  scc_iterator<CallGraph*> CGI = scc_begin(&CG);
+    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.
-    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");
+      // If we've got all functions reachable from our chosen initial node,
+      // calculate the next node we need to search from now too.
+      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;
+
+    LLVM_DEBUG(dbgs() << "  CGSCCPASSMGR: Stopped iteration after " << Iteration
 
-    MaxSCCIterations.updateMax(Iteration);
-  }
-  Changed |= doFinalization(CG);
   return Changed;
 }
 
 /// Initialize CG
 bool CGPassManager::doInitialization(CallGraph &CG) {
   bool Changed = false;
   for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) {  
     if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {

llvm/test/Transforms/Inline/always-inline.ll

; CHECK: define void @inner14
   ret void
 }
 
 define void @outer14() {
 ; CHECK: call void @inner14
   call void @inner14()
   ret void
 }
+
+define internal i32 @outer15() {
+; CHECK-LABEL: @outer15
+; CHECK: ret i32 1
+  %res = call i32 @inner1()
+  ret i32 %res
+}