include/llvm/Analysis/CallGraph.h

   1 //===- llvm/Analysis/CallGraph.h - Build a Module's call graph ---*- C++ -*--=//
   2 //
   3 // This interface is used to build and manipulate a call graph, which is a very
   4 // useful tool for interprocedural optimization.
   5 //
   6 // This call graph represents a dynamic method invocation as a null method node.
   7 // A call graph may only have up to one null method node that represents all of
   8 // the dynamic method invocations.
   9 //
  10 // Additionally, the 'root' node of a call graph represents the "entry point"
  11 // node of the graph, which has an edge to every external method in the graph.
  12 // This node has a null method pointer.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_ANALYSIS_CALLGRAPH_H
  17 #define LLVM_ANALYSIS_CALLGRAPH_H
  18
  19 #include "Support/GraphTraits.h"
  20 #include <map>
  21 #include <vector>
  22 class Method;
  23 class Module;
  24
  25 namespace cfg {
  26
  27 class CallGraph;
  28 class CallGraphNode {
  29   Method *Meth;
  30   vector<CallGraphNode*> CalledMethods;
  31
  32   CallGraphNode(const CallGraphNode &);           // Do not implement
  33 public:
  34   typedef vector<CallGraphNode*>::iterator iterator;
  35   typedef vector<CallGraphNode*>::const_iterator const_iterator;
  36
  37   // getMethod - Return the method that this call graph node represents...
  38   Method *getMethod() const { return Meth; }
  39
  40   inline iterator begin() { return CalledMethods.begin(); }
  41   inline iterator end()   { return CalledMethods.end();   }
  42   inline const_iterator begin() const { return CalledMethods.begin(); }
  43   inline const_iterator end()   const { return CalledMethods.end();   }
  44   inline unsigned size() const { return CalledMethods.size(); }
  45
  46   inline CallGraphNode *operator[](unsigned i) const { return CalledMethods[i];}
  47
  48   void removeAllCalledMethods() {
  49     CalledMethods.clear();
  50   }
  51
  52 private:                    // Stuff to construct the node, used by CallGraph
  53   friend class CallGraph;
  54
  55   // CallGraphNode ctor - Create a node for the specified method...
  56   inline CallGraphNode(Method *M) : Meth(M) {}
  57
  58   // addCalledMethod add a method to the list of methods called by this one
  59   void addCalledMethod(CallGraphNode *M) {
  60     CalledMethods.push_back(M);
  61   }
  62 };
  63
  64
  65 class CallGraph {
  66   Module *Mod;              // The module this call graph represents
  67
  68   typedef map<const Method *, CallGraphNode *> MethodMapTy;
  69   MethodMapTy MethodMap;    // Map from a method to its node
  70
  71   CallGraphNode *Root;
  72 public:
  73   CallGraph(Module *TheModule);
  74   ~CallGraph();
  75
  76   typedef MethodMapTy::iterator iterator;
  77   typedef MethodMapTy::const_iterator const_iterator;
  78
  79   inline       CallGraphNode *getRoot()       { return Root; }
  80   inline const CallGraphNode *getRoot() const { return Root; }
  81   inline       iterator begin()       { return MethodMap.begin(); }
  82   inline       iterator end()         { return MethodMap.end();   }
  83   inline const_iterator begin() const { return MethodMap.begin(); }
  84   inline const_iterator end()   const { return MethodMap.end();   }
  85
  86   inline const CallGraphNode *operator[](const Method *M) const {
  87     const_iterator I = MethodMap.find(M);
  88     assert(I != MethodMap.end() && "Method not in callgraph!");
  89     return I->second;
  90   }
  91   inline CallGraphNode *operator[](const Method *M) {
  92     const_iterator I = MethodMap.find(M);
  93     assert(I != MethodMap.end() && "Method not in callgraph!");
  94     return I->second;
  95   }
  96
  97   // Methods to keep a call graph up to date with a method that has been
  98   // modified
  99   //
 100   void addMethodToModule(Method *Meth);  // TODO IMPLEMENT
 101
 102
 103   // removeMethodFromModule - Unlink the method from this module, returning it.
 104   // Because this removes the method from the module, the call graph node is
 105   // destroyed.  This is only valid if the method does not call any other
 106   // methods (ie, there are no edges in it's CGN).  The easiest way to do this
 107   // is to dropAllReferences before calling this.
 108   //
 109   Method *removeMethodFromModule(CallGraphNode *CGN);
 110   Method *removeMethodFromModule(Method *Meth) {
 111     return removeMethodFromModule((*this)[Meth]);
 112   }
 113
 114 private:   // Implementation of CallGraph construction
 115
 116   // getNodeFor - Return the node for the specified method or create one if it
 117   // does not already exist.
 118   //
 119   CallGraphNode *getNodeFor(Method *M);
 120
 121   // addToCallGraph - Add a method to the call graph, and link the node to all
 122   // of the methods that it calls.
 123   //
 124   void addToCallGraph(Method *M);
 125 };
 126
 127 }  // end namespace cfg
 128
 129
 130
 131
 132 // Provide graph traits for tranversing call graphs using standard graph
 133 // traversals.
 134 template <> struct GraphTraits<cfg::CallGraphNode*> {
 135   typedef cfg::CallGraphNode NodeType;
 136   typedef NodeType::iterator ChildIteratorType;
 137
 138   static NodeType *getEntryNode(cfg::CallGraphNode *CGN) { return CGN; }
 139   static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();}
 140   static inline ChildIteratorType child_end  (NodeType *N) { return N->end(); }
 141 };
 142
 143 template <> struct GraphTraits<const cfg::CallGraphNode*> {
 144   typedef const cfg::CallGraphNode NodeType;
 145   typedef NodeType::const_iterator ChildIteratorType;
 146
 147   static NodeType *getEntryNode(const cfg::CallGraphNode *CGN) { return CGN; }
 148   static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();}
 149   static inline ChildIteratorType child_end  (NodeType *N) { return N->end(); }
 150 };
 151
 152
 153 template<> struct GraphTraits<cfg::CallGraph*> :
 154   public GraphTraits<cfg::CallGraphNode*> {
 155   static NodeType *getEntryNode(cfg::CallGraph *CGN) {
 156     return CGN->getRoot();
 157   }
 158 };
 159 template<> struct GraphTraits<const cfg::CallGraph*> :
 160   public GraphTraits<const cfg::CallGraphNode*> {
 161   static NodeType *getEntryNode(const cfg::CallGraph *CGN) {
 162     return CGN->getRoot();
 163   }
 164 };
 165
 166
 167 // Checks if a method contains any call instructions.
 168 // Note that this uses the call graph only if one is provided.
 169 // It does not build the call graph.
 170 //
 171 bool isLeafMethod(const Method* method, const cfg::CallGraph *callGraph = 0);
 172
 173 #endif