[PM] Split the CallGraph out from the ModulePass which creates the

CallGraph.

This makes the CallGraph a totally generic analysis object that is the
container for the graph data structure and the primary interface for
querying and manipulating it. The pass logic is separated into its own
class. For compatibility reasons, the pass provides wrapper methods for
most of the methods on CallGraph -- they all just forward.

This will allow the new pass manager infrastructure to provide its own
analysis pass that constructs the same CallGraph object and makes it
available. The idea is that in the new pass manager, the analysis pass's
'run' method returns a concrete analysis 'result'. Here, that result is
a 'CallGraph'. The 'run' method will typically do only minimal work,
deferring much of the work into the implementation of the result object
in order to be lazy about computing things, but when (like DomTree)
there is *some* up-front computation, the analysis does it prior to
handing the result back to the querying pass.

I know some of this is fairly ugly. I'm happy to change it around if
folks can suggest a cleaner interim state, but there is going to be some
amount of unavoidable ugliness during the transition period. The good
thing is that this is very limited and will naturally go away when the
old pass infrastructure goes away. It won't hang around to bother us
later.

Next up is the initial new-PM-style call graph analysis. =]

llvm-svn: 195722

12 files changed, 129 insertions, 93 deletions

diff --git a/llvm/lib/Analysis/IPA/CallGraph.cpp b/llvm/lib/Analysis/IPA/CallGraph.cpp
index d5a718bfbc8..de8164cc2db 100644
--- a/llvm/lib/Analysis/IPA/CallGraph.cpp
+++ b/llvm/lib/Analysis/IPA/CallGraph.cpp
@@ -16,9 +16,37 @@
 #include "llvm/Support/raw_ostream.h"
 using namespace llvm;
 
-CallGraph::CallGraph()
-    : ModulePass(ID), Root(0), ExternalCallingNode(0), CallsExternalNode(0) {
-  initializeCallGraphPass(*PassRegistry::getPassRegistry());
+//===----------------------------------------------------------------------===//
+// Implementations of the CallGraph class methods.
+//
+
+CallGraph::CallGraph(Module &M)
+    : M(M), Root(0), ExternalCallingNode(getOrInsertFunction(0)),
+      CallsExternalNode(new CallGraphNode(0)) {
+  // Add every function to the call graph.
+  for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
+    addToCallGraph(I);
+
+  // If we didn't find a main function, use the external call graph node
+  if (Root == 0)
+    Root = ExternalCallingNode;
+}
+
+CallGraph::~CallGraph() {
+  // CallsExternalNode is not in the function map, delete it explicitly.
+  CallsExternalNode->allReferencesDropped();
+  delete CallsExternalNode;
+
+// Reset all node's use counts to zero before deleting them to prevent an
+// assertion from firing.
+#ifndef NDEBUG
+  for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end();
+       I != E; ++I)
+    I->second->allReferencesDropped();
+#endif
+  for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end();
+       I != E; ++I)
+    delete I->second;
 }
 
 void CallGraph::addToCallGraph(Function *F) {
@@ -62,59 +90,7 @@ void CallGraph::addToCallGraph(Function *F) {
     }
 }
 
-void CallGraph::getAnalysisUsage(AnalysisUsage &AU) const {
-  AU.setPreservesAll();
-}
-
-bool CallGraph::runOnModule(Module &M) {
-  this->M = &M;
-
-  ExternalCallingNode = getOrInsertFunction(0);
-  assert(!CallsExternalNode);
-  CallsExternalNode = new CallGraphNode(0);
-  Root = 0;
-
-  // Add every function to the call graph.
-  for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
-    addToCallGraph(I);
-
-  // If we didn't find a main function, use the external call graph node
-  if (Root == 0)
-    Root = ExternalCallingNode;
-
-  return false;
-}
-
-INITIALIZE_PASS(CallGraph, "basiccg", "CallGraph Construction", false, true)
-
-char CallGraph::ID = 0;
-
-void CallGraph::releaseMemory() {
-  /// CallsExternalNode is not in the function map, delete it explicitly.
-  if (CallsExternalNode) {
-    CallsExternalNode->allReferencesDropped();
-    delete CallsExternalNode;
-    CallsExternalNode = 0;
-  }
-
-  if (FunctionMap.empty())
-    return;
-
-// Reset all node's use counts to zero before deleting them to prevent an
-// assertion from firing.
-#ifndef NDEBUG
-  for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end();
-       I != E; ++I)
-    I->second->allReferencesDropped();
-#endif
-  
-  for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end();
-      I != E; ++I)
-    delete I->second;
-  FunctionMap.clear();
-}
-
-void CallGraph::print(raw_ostream &OS, const Module*) const {
+void CallGraph::print(raw_ostream &OS) const {
   OS << "CallGraph Root is: ";
   if (Function *F = Root->getFunction())
     OS << F->getName() << "\n";
@@ -125,16 +101,11 @@ void CallGraph::print(raw_ostream &OS, const Module*) const {
   for (CallGraph::const_iterator I = begin(), E = end(); I != E; ++I)
     I->second->print(OS);
 }
+
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
-void CallGraph::dump() const {
-  print(dbgs(), 0);
-}
+void CallGraph::dump() const { print(dbgs()); }
 #endif
 
-//===----------------------------------------------------------------------===//
-// Implementations of public modification methods
-//
-
 // removeFunctionFromModule - Unlink the function from this module, returning
 // it.  Because this removes the function from the module, the call graph node
 // is destroyed.  This is only valid if the function does not call any other
@@ -148,7 +119,7 @@ Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) {
   delete CGN;                       // Delete the call graph node for this func
   FunctionMap.erase(F);             // Remove the call graph node from the map
 
-  M->getFunctionList().remove(F);
+  M.getFunctionList().remove(F);
   return F;
 }
 
@@ -172,12 +143,17 @@ void CallGraph::spliceFunction(const Function *From, const Function *To) {
 // not already exist.
 CallGraphNode *CallGraph::getOrInsertFunction(const Function *F) {
   CallGraphNode *&CGN = FunctionMap[F];
-  if (CGN) return CGN;
-  
-  assert((!F || F->getParent() == M) && "Function not in current module!");
+  if (CGN)
+    return CGN;
+
+  assert((!F || F->getParent() == &M) && "Function not in current module!");
   return CGN = new CallGraphNode(const_cast<Function*>(F));
 }
 
+//===----------------------------------------------------------------------===//
+// Implementations of the CallGraphNode class methods.
+//
+
 void CallGraphNode::print(raw_ostream &OS) const {
   if (Function *F = getFunction())
     OS << "Call graph node for function: '" << F->getName() << "'";
@@ -260,5 +236,46 @@ void CallGraphNode::replaceCallEdge(CallSite CS,
   }
 }
 
+//===----------------------------------------------------------------------===//
+// Implementations of the CallGraphWrapperPass class methods.
+//
+
+CallGraphWrapperPass::CallGraphWrapperPass() : ModulePass(ID) {
+  initializeCallGraphWrapperPassPass(*PassRegistry::getPassRegistry());
+}
+
+CallGraphWrapperPass::~CallGraphWrapperPass() {}
+
+void CallGraphWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+}
+
+bool CallGraphWrapperPass::runOnModule(Module &M) {
+  // All the real work is done in the constructor for the CallGraph.
+  G.reset(new CallGraph(M));
+  return false;
+}
+
+INITIALIZE_PASS(CallGraphWrapperPass, "basiccg", "CallGraph Construction",
+                false, true)
+
+char CallGraphWrapperPass::ID = 0;
+
+void CallGraphWrapperPass::releaseMemory() { G.reset(0); }
+
+void CallGraphWrapperPass::print(raw_ostream &OS, const Module *) const {
+  if (!G) {
+    OS << "No call graph has been built!\n";
+    return;
+  }
+
+  // Just delegate.
+  G->print(OS);
+}
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+void CallGraphWrapperPass::dump() const { print(dbgs(), 0); }
+#endif
+
 // Enuse that users of CallGraph.h also link with this file
 DEFINING_FILE_FOR(CallGraph)
diff --git a/llvm/lib/Analysis/IPA/CallGraphSCCPass.cpp b/llvm/lib/Analysis/IPA/CallGraphSCCPass.cpp
index 182beca3643..a3f77b7eb47 100644
--- a/llvm/lib/Analysis/IPA/CallGraphSCCPass.cpp
+++ b/llvm/lib/Analysis/IPA/CallGraphSCCPass.cpp
@@ -60,7 +60,7 @@ public:
   /// Pass Manager itself does not invalidate any analysis info.
   void getAnalysisUsage(AnalysisUsage &Info) const {
     // CGPassManager walks SCC and it needs CallGraph.
-    Info.addRequired<CallGraph>();
+    Info.addRequired<CallGraphWrapperPass>();
     Info.setPreservesAll();
   }
 
@@ -424,7 +424,7 @@ bool CGPassManager::RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
 /// run - 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<CallGraph>();
+  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
   bool Changed = doInitialization(CG);
   
   // Walk the callgraph in bottom-up SCC order.
@@ -570,8 +570,8 @@ void CallGraphSCCPass::assignPassManager(PMStack &PMS,
 /// the call graph.  If the derived class implements this method, it should
 /// always explicitly call the implementation here.
 void CallGraphSCCPass::getAnalysisUsage(AnalysisUsage &AU) const {
-  AU.addRequired<CallGraph>();
-  AU.addPreserved<CallGraph>();
+  AU.addRequired<CallGraphWrapperPass>();
+  AU.addPreserved<CallGraphWrapperPass>();
 }
 
 
diff --git a/llvm/lib/Analysis/IPA/CallPrinter.cpp b/llvm/lib/Analysis/IPA/CallPrinter.cpp
index 1c9856b2520..68dcd3c0642 100644
--- a/llvm/lib/Analysis/IPA/CallPrinter.cpp
+++ b/llvm/lib/Analysis/IPA/CallPrinter.cpp
@@ -35,24 +35,38 @@ template <> struct DOTGraphTraits<CallGraph *> : public DefaultDOTGraphTraits {
   }
 };
 
+struct AnalysisCallGraphWrapperPassTraits {
+  static CallGraph *getGraph(CallGraphWrapperPass *P) {
+    return &P->getCallGraph();
+  }
+};
+
 } // end llvm namespace
 
 namespace {
 
-struct CallGraphViewer : public DOTGraphTraitsModuleViewer<CallGraph, true> {
+struct CallGraphViewer
+    : public DOTGraphTraitsModuleViewer<CallGraphWrapperPass, true, CallGraph *,
+                                        AnalysisCallGraphWrapperPassTraits> {
   static char ID;
 
   CallGraphViewer()
-      : DOTGraphTraitsModuleViewer<CallGraph, true>("callgraph", ID) {
+      : DOTGraphTraitsModuleViewer<CallGraphWrapperPass, true, CallGraph *,
+                                   AnalysisCallGraphWrapperPassTraits>(
+            "callgraph", ID) {
     initializeCallGraphViewerPass(*PassRegistry::getPassRegistry());
   }
 };
 
-struct CallGraphPrinter : public DOTGraphTraitsModulePrinter<CallGraph, true> {
+struct CallGraphPrinter : public DOTGraphTraitsModulePrinter<
+                              CallGraphWrapperPass, true, CallGraph *,
+                              AnalysisCallGraphWrapperPassTraits> {
   static char ID;
 
   CallGraphPrinter()
-      : DOTGraphTraitsModulePrinter<CallGraph, true>("callgraph", ID) {
+      : DOTGraphTraitsModulePrinter<CallGraphWrapperPass, true, CallGraph *,
+                                    AnalysisCallGraphWrapperPassTraits>(
+            "callgraph", ID) {
     initializeCallGraphPrinterPass(*PassRegistry::getPassRegistry());
   }
 };
diff --git a/llvm/lib/Analysis/IPA/GlobalsModRef.cpp b/llvm/lib/Analysis/IPA/GlobalsModRef.cpp
index 7ec46442bf4..e0723026de7 100644
--- a/llvm/lib/Analysis/IPA/GlobalsModRef.cpp
+++ b/llvm/lib/Analysis/IPA/GlobalsModRef.cpp
@@ -95,15 +95,19 @@ namespace {
     }
 
     bool runOnModule(Module &M) {
-      InitializeAliasAnalysis(this);                 // set up super class
-      AnalyzeGlobals(M);                          // find non-addr taken globals
-      AnalyzeCallGraph(getAnalysis<CallGraph>(), M); // Propagate on CG
+      InitializeAliasAnalysis(this);
+
+      // Find non-addr taken globals.
+      AnalyzeGlobals(M);
+
+      // Propagate on CG.
+      AnalyzeCallGraph(getAnalysis<CallGraphWrapperPass>().getCallGraph(), M);
       return false;
     }
 
     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
       AliasAnalysis::getAnalysisUsage(AU);
-      AU.addRequired<CallGraph>();
+      AU.addRequired<CallGraphWrapperPass>();
       AU.setPreservesAll();                         // Does not transform code
     }
 
@@ -189,7 +193,7 @@ char GlobalsModRef::ID = 0;
 INITIALIZE_AG_PASS_BEGIN(GlobalsModRef, AliasAnalysis,
                 "globalsmodref-aa", "Simple mod/ref analysis for globals",    
                 false, true, false)
-INITIALIZE_PASS_DEPENDENCY(CallGraph)
+INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
 INITIALIZE_AG_PASS_END(GlobalsModRef, AliasAnalysis,
                 "globalsmodref-aa", "Simple mod/ref analysis for globals",    
                 false, true, false)
diff --git a/llvm/lib/Analysis/IPA/IPA.cpp b/llvm/lib/Analysis/IPA/IPA.cpp
index 47357cf9212..b07271abd42 100644
--- a/llvm/lib/Analysis/IPA/IPA.cpp
+++ b/llvm/lib/Analysis/IPA/IPA.cpp
@@ -19,7 +19,7 @@ using namespace llvm;
 
 /// initializeIPA - Initialize all passes linked into the IPA library.
 void llvm::initializeIPA(PassRegistry &Registry) {
-  initializeCallGraphPass(Registry);
+  initializeCallGraphWrapperPassPass(Registry);
   initializeCallGraphPrinterPass(Registry);
   initializeCallGraphViewerPass(Registry);
   initializeFindUsedTypesPass(Registry);
diff --git a/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp b/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp
index df08091ac5b..49a67211db6 100644
--- a/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp
+++ b/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp
@@ -88,7 +88,7 @@ char ArgPromotion::ID = 0;
 INITIALIZE_PASS_BEGIN(ArgPromotion, "argpromotion",
                 "Promote 'by reference' arguments to scalars", false, false)
 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
-INITIALIZE_PASS_DEPENDENCY(CallGraph)
+INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
 INITIALIZE_PASS_END(ArgPromotion, "argpromotion",
                 "Promote 'by reference' arguments to scalars", false, false)
 
@@ -621,8 +621,8 @@ CallGraphNode *ArgPromotion::DoPromotion(Function *F,
 
   // Get the callgraph information that we need to update to reflect our
   // changes.
-  CallGraph &CG = getAnalysis<CallGraph>();
-  
+  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
+
   // Get a new callgraph node for NF.
   CallGraphNode *NF_CGN = CG.getOrInsertFunction(NF);
 
diff --git a/llvm/lib/Transforms/IPO/FunctionAttrs.cpp b/llvm/lib/Transforms/IPO/FunctionAttrs.cpp
index 60e5f067639..6e41f262fa6 100644
--- a/llvm/lib/Transforms/IPO/FunctionAttrs.cpp
+++ b/llvm/lib/Transforms/IPO/FunctionAttrs.cpp
@@ -137,7 +137,7 @@ char FunctionAttrs::ID = 0;
 INITIALIZE_PASS_BEGIN(FunctionAttrs, "functionattrs",
                 "Deduce function attributes", false, false)
 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
-INITIALIZE_PASS_DEPENDENCY(CallGraph)
+INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
 INITIALIZE_PASS_END(FunctionAttrs, "functionattrs",
                 "Deduce function attributes", false, false)
diff --git a/llvm/lib/Transforms/IPO/InlineAlways.cpp b/llvm/lib/Transforms/IPO/InlineAlways.cpp
index 437597ec037..be1fe9a117e 100644
--- a/llvm/lib/Transforms/IPO/InlineAlways.cpp
+++ b/llvm/lib/Transforms/IPO/InlineAlways.cpp
@@ -63,7 +63,7 @@ public:
 char AlwaysInliner::ID = 0;
 INITIALIZE_PASS_BEGIN(AlwaysInliner, "always-inline",
                 "Inliner for always_inline functions", false, false)
-INITIALIZE_PASS_DEPENDENCY(CallGraph)
+INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(InlineCostAnalysis)
 INITIALIZE_PASS_END(AlwaysInliner, "always-inline",
                 "Inliner for always_inline functions", false, false)
diff --git a/llvm/lib/Transforms/IPO/InlineSimple.cpp b/llvm/lib/Transforms/IPO/InlineSimple.cpp
index 57379a334f2..29292288e1b 100644
--- a/llvm/lib/Transforms/IPO/InlineSimple.cpp
+++ b/llvm/lib/Transforms/IPO/InlineSimple.cpp
@@ -61,7 +61,7 @@ public:
 char SimpleInliner::ID = 0;
 INITIALIZE_PASS_BEGIN(SimpleInliner, "inline",
                 "Function Integration/Inlining", false, false)
-INITIALIZE_PASS_DEPENDENCY(CallGraph)
+INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(InlineCostAnalysis)
 INITIALIZE_PASS_END(SimpleInliner, "inline",
                 "Function Integration/Inlining", false, false)
diff --git a/llvm/lib/Transforms/IPO/Inliner.cpp b/llvm/lib/Transforms/IPO/Inliner.cpp
index d75d6ca92b3..dc710d14157 100644
--- a/llvm/lib/Transforms/IPO/Inliner.cpp
+++ b/llvm/lib/Transforms/IPO/Inliner.cpp
@@ -395,7 +395,7 @@ static bool InlineHistoryIncludes(Function *F, int InlineHistoryID,
 }
 
 bool Inliner::runOnSCC(CallGraphSCC &SCC) {
-  CallGraph &CG = getAnalysis<CallGraph>();
+  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
   const DataLayout *TD = getAnalysisIfAvailable<DataLayout>();
   const TargetLibraryInfo *TLI = getAnalysisIfAvailable<TargetLibraryInfo>();
 
diff --git a/llvm/lib/Transforms/IPO/Internalize.cpp b/llvm/lib/Transforms/IPO/Internalize.cpp
index 64e2cedfb13..962d3de3156 100644
--- a/llvm/lib/Transforms/IPO/Internalize.cpp
+++ b/llvm/lib/Transforms/IPO/Internalize.cpp
@@ -63,7 +63,7 @@ namespace {
 
     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
       AU.setPreservesCFG();
-      AU.addPreserved<CallGraph>();
+      AU.addPreserved<CallGraphWrapperPass>();
     }
   };
 } // end anonymous namespace
@@ -127,7 +127,8 @@ static bool shouldInternalize(const GlobalValue &GV,
 }
 
 bool InternalizePass::runOnModule(Module &M) {
-  CallGraph *CG = getAnalysisIfAvailable<CallGraph>();
+  CallGraphWrapperPass *CGPass = getAnalysisIfAvailable<CallGraphWrapperPass>();
+  CallGraph *CG = CGPass ? &CGPass->getCallGraph() : 0;
   CallGraphNode *ExternalNode = CG ? CG->getExternalCallingNode() : 0;
   bool Changed = false;
 
diff --git a/llvm/lib/Transforms/IPO/PruneEH.cpp b/llvm/lib/Transforms/IPO/PruneEH.cpp
index b1609131214..cba6ae052b8 100644
--- a/llvm/lib/Transforms/IPO/PruneEH.cpp
+++ b/llvm/lib/Transforms/IPO/PruneEH.cpp
@@ -51,7 +51,7 @@ namespace {
 char PruneEH::ID = 0;
 INITIALIZE_PASS_BEGIN(PruneEH, "prune-eh",
                 "Remove unused exception handling info", false, false)
-INITIALIZE_PASS_DEPENDENCY(CallGraph)
+INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
 INITIALIZE_PASS_END(PruneEH, "prune-eh",
                 "Remove unused exception handling info", false, false)
 
@@ -60,7 +60,7 @@ Pass *llvm::createPruneEHPass() { return new PruneEH(); }
 
 bool PruneEH::runOnSCC(CallGraphSCC &SCC) {
   SmallPtrSet<CallGraphNode *, 8> SCCNodes;
-  CallGraph &CG = getAnalysis<CallGraph>();
+  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
   bool MadeChange = false;
 
   // Fill SCCNodes with the elements of the SCC.  Used for quickly
@@ -234,7 +234,7 @@ bool PruneEH::SimplifyFunction(Function *F) {
 /// exist in the BB.
 void PruneEH::DeleteBasicBlock(BasicBlock *BB) {
   assert(pred_begin(BB) == pred_end(BB) && "BB is not dead!");
-  CallGraph &CG = getAnalysis<CallGraph>();
+  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
 
   CallGraphNode *CGN = CG[BB->getParent()];
   for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; ) {