Separate the call graph implementation from its interface. This implements

the rough idea sketched out in http://nondot.org/sabre/LLVMNotes/CallGraphClass.txt,
allowing new spiffy implementations of the callgraph interface to be built.

Many thanks to Saem Ghani for contributing this!


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@24944 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 28 insertions, 68 deletions

diff --git a/include/llvm/Analysis/CallGraph.h b/include/llvm/Analysis/CallGraph.h
index fee5147761..4edb602356 100644
--- a/include/llvm/Analysis/CallGraph.h
+++ b/include/llvm/Analysis/CallGraph.h
@@ -64,25 +64,13 @@ class CallGraphNode;
 //===----------------------------------------------------------------------===//
 // CallGraph class definition
 //
-class CallGraph : public ModulePass {
+class CallGraph {
+protected:
   Module *Mod;              // The module this call graph represents
 
   typedef std::map<const Function *, CallGraphNode *> FunctionMapTy;
   FunctionMapTy FunctionMap;    // Map from a function to its node
 
-  // Root is root of the call graph, or the external node if a 'main' function
-  // couldn't be found.
-  //
-  CallGraphNode *Root;
-
-  // ExternalCallingNode - This node has edges to all external functions and
-  // those internal functions that have their address taken.
-  CallGraphNode *ExternalCallingNode;
-
-  // CallsExternalNode - This node has edges to it from all functions making
-  // indirect calls or calling an external function.
-  CallGraphNode *CallsExternalNode;
-
 public:
   //===---------------------------------------------------------------------
   // Accessors...
@@ -90,15 +78,6 @@ public:
   typedef FunctionMapTy::iterator iterator;
   typedef FunctionMapTy::const_iterator const_iterator;
 
-  CallGraphNode *getExternalCallingNode() const { return ExternalCallingNode; }
-  CallGraphNode *getCallsExternalNode()   const { return CallsExternalNode; }
-
-  // getRoot - Return the root of the call graph, which is either main, or if
-  // main cannot be found, the external node.
-  //
-        CallGraphNode *getRoot()       { return Root; }
-  const CallGraphNode *getRoot() const { return Root; }
-
   /// getModule - Return the module the call graph corresponds to.
   ///
   Module &getModule() const { return *Mod; }
@@ -108,7 +87,6 @@ public:
   inline const_iterator begin() const { return FunctionMap.begin(); }
   inline const_iterator end()   const { return FunctionMap.end();   }
 
-
   // Subscripting operators, return the call graph node for the provided
   // function
   inline const CallGraphNode *operator[](const Function *F) const {
@@ -122,6 +100,16 @@ public:
     return I->second;
   }
 
+  //Returns the CallGraphNode which is used to represent undetermined calls 
+  // into the callgraph.  Override this if you want behavioural inheritance.
+  virtual CallGraphNode* getExternalCallingNode() const { return 0; }
+  
+  //Return the root/main method in the module, or some other root node, such
+  // as the externalcallingnode.  Overload these if you behavioural 
+  // inheritance.
+  virtual CallGraphNode* getRoot() { return 0; }
+  virtual const CallGraphNode* getRoot() const { return 0; }
+  
   //===---------------------------------------------------------------------
   // Functions to keep a call graph up to date with a function that has been
   // modified.
@@ -147,54 +135,27 @@ public:
   //===---------------------------------------------------------------------
   // Pass infrastructure interface glue code...
   //
-  CallGraph() : Root(0), CallsExternalNode(0) {}
-  ~CallGraph() { destroy(); }
-
-  // runOnModule - Compute the call graph for the specified module.
-  virtual bool runOnModule(Module &M);
-
-  // getAnalysisUsage - This obviously provides a call graph
-  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
-    AU.setPreservesAll();
-  }
-
-  // releaseMemory - Data structures can be large, so free memory aggressively.
-  virtual void releaseMemory() {
-    destroy();
-  }
+protected:
+  CallGraph() {}
+  
+public:
+  virtual ~CallGraph() { destroy(); }
 
-  /// Print the types found in the module.  If the optional Module parameter is
-  /// passed in, then the types are printed symbolically if possible, using the
-  /// symbol table from the module.
+  /// initialize - Call this method before calling other methods, 
+  /// re/initializes the state of the CallGraph.
   ///
-  void print(std::ostream &o, const Module *M) const;
+  void initialize(Module &M);
 
-  /// dump - Print out this call graph.
-  ///
-  void dump() const;
+  virtual void print(std::ostream &o, const Module *M) const;
 
   // stub - dummy function, just ignore it
   static void stub();
-private:
-  //===---------------------------------------------------------------------
-  // Implementation of CallGraph construction
-  //
-
-  // getNodeFor - Return the node for the specified function or create one if it
-  // does not already exist.
-  //
-  CallGraphNode *getNodeFor(Function *F);
-
-  // addToCallGraph - Add a function to the call graph, and link the node to all
-  // of the functions that it calls.
-  //
-  void addToCallGraph(Function *F);
+protected:
 
   // destroy - Release memory for the call graph
-  void destroy();
+  virtual void destroy();
 };
 
-
 //===----------------------------------------------------------------------===//
 // CallGraphNode class definition
 //
@@ -256,15 +217,12 @@ public:
   /// removeCallEdgeTo, so it should not be used unless necessary.
   void removeAnyCallEdgeTo(CallGraphNode *Callee);
 
-private:                    // Stuff to construct the node, used by CallGraph
   friend class CallGraph;
 
   // CallGraphNode ctor - Create a node for the specified function...
   inline CallGraphNode(Function *f) : F(f) {}
 };
 
-
-
 //===----------------------------------------------------------------------===//
 // GraphTraits specializations for call graphs so that they can be treated as
 // graphs by the generic graph algorithms...
@@ -311,6 +269,7 @@ template<> struct GraphTraits<CallGraph*> : public GraphTraits<CallGraphNode*> {
     return *P.second;
   }
 };
+
 template<> struct GraphTraits<const CallGraph*> :
   public GraphTraits<const CallGraphNode*> {
   static NodeType *getEntryNode(const CallGraph *CGN) {
@@ -322,10 +281,13 @@ template<> struct GraphTraits<const CallGraph*> :
   static nodes_iterator nodes_end  (const CallGraph *CG) { return CG->end(); }
 };
 
-// Make sure that any clients of this file link in PostDominators.cpp
+// Make sure that any clients of this file link in CallGraph.cpp
 static IncludeFile
 CALLGRAPH_INCLUDE_FILE((void*)&CallGraph::stub);
 
+extern void BasicCallGraphStub();
+static IncludeFile HDR_INCLUDE_CALLGRAPH_CPP((void*)&BasicCallGraphStub);
+
 } // End llvm namespace
 
 #endif
diff --git a/include/llvm/Analysis/LinkAllAnalyses.h b/include/llvm/Analysis/LinkAllAnalyses.h
index 6188c27001..afb120ed87 100644
--- a/include/llvm/Analysis/LinkAllAnalyses.h
+++ b/include/llvm/Analysis/LinkAllAnalyses.h
@@ -16,7 +16,6 @@
 #define LLVM_ANALYSIS_LINKALLANALYSES_H
 
 #include "llvm/Analysis/AliasSetTracker.h"
-#include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/FindUsedTypes.h"
 #include "llvm/Analysis/IntervalPartition.h"
 #include "llvm/Analysis/PostDominators.h"
@@ -49,7 +48,6 @@ namespace {
       (void)new llvm::IntervalPartition();
       (void)new llvm::ImmediateDominators();
       (void)new llvm::PostDominatorSet();
-      (void)new llvm::CallGraph();
       (void)new llvm::FindUsedTypes();
       (void)new llvm::ScalarEvolution();
       ((llvm::Function*)0)->viewCFGOnly();