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 "llvm/Pass.h"
  21 class Method;
  22 class Module;
  23
  24 namespace cfg {
  25
  26 class CallGraph;
  27 class CallGraphNode {
  28   Method *Meth;
  29   std::vector<CallGraphNode*> CalledMethods;
  30
  31   CallGraphNode(const CallGraphNode &);           // Do not implement
  32 public:
  33   typedef std::vector<CallGraphNode*>::iterator iterator;
  34   typedef std::vector<CallGraphNode*>::const_iterator const_iterator;
  35
  36   // getMethod - Return the method that this call graph node represents...
  37   Method *getMethod() const { return Meth; }
  38
  39   inline iterator begin() { return CalledMethods.begin(); }
  40   inline iterator end()   { return CalledMethods.end();   }
  41   inline const_iterator begin() const { return CalledMethods.begin(); }
  42   inline const_iterator end()   const { return CalledMethods.end();   }
  43   inline unsigned size() const { return CalledMethods.size(); }
  44
  45   inline CallGraphNode *operator[](unsigned i) const { return CalledMethods[i];}
  46
  47   void removeAllCalledMethods() {
  48     CalledMethods.clear();
  49   }
  50
  51 private:                    // Stuff to construct the node, used by CallGraph
  52   friend class CallGraph;
  53
  54   // CallGraphNode ctor - Create a node for the specified method...
  55   inline CallGraphNode(Method *M) : Meth(M) {}
  56
  57   // addCalledMethod add a method to the list of methods called by this one
  58   void addCalledMethod(CallGraphNode *M) {
  59     CalledMethods.push_back(M);
  60   }
  61 };
  62
  63
  64 class CallGraph : public Pass {
  65   Module *Mod;              // The module this call graph represents
  66
  67   typedef std::map<const Method *, CallGraphNode *> MethodMapTy;
  68   MethodMapTy MethodMap;    // Map from a method to its node
  69
  70   CallGraphNode *Root;
  71 public:
  72   static AnalysisID ID;    // We are an analysis, we must have an ID
  73
  74   CallGraph(AnalysisID AID) : Root(0) { assert(AID == ID); }
  75   ~CallGraph() { destroy(); }
  76
  77   typedef MethodMapTy::iterator iterator;
  78   typedef MethodMapTy::const_iterator const_iterator;
  79
  80   inline       CallGraphNode *getRoot()       { return Root; }
  81   inline const CallGraphNode *getRoot() const { return Root; }
  82   inline       iterator begin()       { return MethodMap.begin(); }
  83   inline       iterator end()         { return MethodMap.end();   }
  84   inline const_iterator begin() const { return MethodMap.begin(); }
  85   inline const_iterator end()   const { return MethodMap.end();   }
  86
  87   inline const CallGraphNode *operator[](const Method *M) const {
  88     const_iterator I = MethodMap.find(M);
  89     assert(I != MethodMap.end() && "Method not in callgraph!");
  90     return I->second;
  91   }
  92   inline CallGraphNode *operator[](const Method *M) {
  93     const_iterator I = MethodMap.find(M);
  94     assert(I != MethodMap.end() && "Method not in callgraph!");
  95     return I->second;
  96   }
  97
  98   // Methods to keep a call graph up to date with a method that has been
  99   // modified
 100   //
 101   void addMethodToModule(Method *Meth);  // TODO IMPLEMENT
 102
 103
 104   // removeMethodFromModule - Unlink the method from this module, returning it.
 105   // Because this removes the method from the module, the call graph node is
 106   // destroyed.  This is only valid if the method does not call any other
 107   // methods (ie, there are no edges in it's CGN).  The easiest way to do this
 108   // is to dropAllReferences before calling this.
 109   //
 110   Method *removeMethodFromModule(CallGraphNode *CGN);
 111   Method *removeMethodFromModule(Method *Meth) {
 112     return removeMethodFromModule((*this)[Meth]);
 113   }
 114
 115   // run - Compute the call graph for the specified module.
 116   virtual bool run(Module *TheModule);
 117
 118   // getAnalysisUsageInfo - This obviously provides a call graph
 119   virtual void getAnalysisUsageInfo(AnalysisSet &Required,
 120                                     AnalysisSet &Destroyed,
 121                                     AnalysisSet &Provided) {
 122     Provided.push_back(ID);
 123   }
 124
 125 private:   // Implementation of CallGraph construction
 126   void destroy();
 127
 128   // getNodeFor - Return the node for the specified method or create one if it
 129   // does not already exist.
 130   //
 131   CallGraphNode *getNodeFor(Method *M);
 132
 133   // addToCallGraph - Add a method to the call graph, and link the node to all
 134   // of the methods that it calls.
 135   //
 136   void addToCallGraph(Method *M);
 137 };
 138
 139 }  // end namespace cfg
 140
 141
 142
 143
 144 // Provide graph traits for tranversing call graphs using standard graph
 145 // traversals.
 146 template <> struct GraphTraits<cfg::CallGraphNode*> {
 147   typedef cfg::CallGraphNode NodeType;
 148   typedef NodeType::iterator ChildIteratorType;
 149
 150   static NodeType *getEntryNode(cfg::CallGraphNode *CGN) { return CGN; }
 151   static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();}
 152   static inline ChildIteratorType child_end  (NodeType *N) { return N->end(); }
 153 };
 154
 155 template <> struct GraphTraits<const cfg::CallGraphNode*> {
 156   typedef const cfg::CallGraphNode NodeType;
 157   typedef NodeType::const_iterator ChildIteratorType;
 158
 159   static NodeType *getEntryNode(const cfg::CallGraphNode *CGN) { return CGN; }
 160   static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();}
 161   static inline ChildIteratorType child_end  (NodeType *N) { return N->end(); }
 162 };
 163
 164
 165 template<> struct GraphTraits<cfg::CallGraph*> :
 166   public GraphTraits<cfg::CallGraphNode*> {
 167   static NodeType *getEntryNode(cfg::CallGraph *CGN) {
 168     return CGN->getRoot();
 169   }
 170 };
 171 template<> struct GraphTraits<const cfg::CallGraph*> :
 172   public GraphTraits<const cfg::CallGraphNode*> {
 173   static NodeType *getEntryNode(const cfg::CallGraph *CGN) {
 174     return CGN->getRoot();
 175   }
 176 };
 177
 178
 179 // Checks if a method contains any call instructions.
 180 // Note that this uses the call graph only if one is provided.
 181 // It does not build the call graph.
 182 //
 183 bool isLeafMethod(const Method* method, const cfg::CallGraph *callGraph = 0);
 184
 185 #endif