aboutsummaryrefslogtreecommitdiffstats
path: root/include/llvm/Analysis/CallGraph.h
blob: 8365a4f397c290d70ea86f329cae09ab3f297de2 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
//===- llvm/Analysis/CallGraph.h - Build a Module's call graph ---*- C++ -*--=//
//
// This interface is used to build and manipulate a call graph, which is a very 
// useful tool for interprocedural optimization.
//
// This call graph represents a dynamic method invocation as a null method node.
// A call graph may only have up to one null method node that represents all of
// the dynamic method invocations.
//
// Additionally, the 'root' node of a call graph represents the "entry point"
// node of the graph, which has an edge to every external method in the graph.
// This node has a null method pointer.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_CALLGRAPH_H
#define LLVM_ANALYSIS_CALLGRAPH_H

#include "Support/GraphTraits.h"
#include <map>
#include <vector>
class Method;
class Module;

namespace cfg {

class CallGraph;
class CallGraphNode {
  Method *Meth;
  vector<CallGraphNode*> CalledMethods;

  CallGraphNode(const CallGraphNode &);           // Do not implement
public:
  typedef vector<CallGraphNode*>::iterator iterator;
  typedef vector<CallGraphNode*>::const_iterator const_iterator;

  // getMethod - Return the method that this call graph node represents...
  Method *getMethod() const { return Meth; }

  inline iterator begin() { return CalledMethods.begin(); }
  inline iterator end()   { return CalledMethods.end();   }
  inline const_iterator begin() const { return CalledMethods.begin(); }
  inline const_iterator end()   const { return CalledMethods.end();   }
  inline unsigned size() const { return CalledMethods.size(); }

  inline CallGraphNode *operator[](unsigned i) const { return CalledMethods[i];}

  void removeAllCalledMethods() {
    CalledMethods.clear();
  }

private:                    // Stuff to construct the node, used by CallGraph
  friend class CallGraph;

  // CallGraphNode ctor - Create a node for the specified method...
  inline CallGraphNode(Method *M) : Meth(M) {}
  
  // addCalledMethod add a method to the list of methods called by this one
  void addCalledMethod(CallGraphNode *M) {
    CalledMethods.push_back(M);
  }
};


class CallGraph {
  Module *Mod;              // The module this call graph represents

  typedef map<const Method *, CallGraphNode *> MethodMapTy;
  MethodMapTy MethodMap;    // Map from a method to its node

  CallGraphNode *Root;
public:
  CallGraph(Module *TheModule);
  ~CallGraph();

  typedef MethodMapTy::iterator iterator;
  typedef MethodMapTy::const_iterator const_iterator;

  inline       CallGraphNode *getRoot()       { return Root; }
  inline const CallGraphNode *getRoot() const { return Root; }
  inline       iterator begin()       { return MethodMap.begin(); }
  inline       iterator end()         { return MethodMap.end();   }
  inline const_iterator begin() const { return MethodMap.begin(); }
  inline const_iterator end()   const { return MethodMap.end();   }

  inline const CallGraphNode *operator[](const Method *M) const {
    const_iterator I = MethodMap.find(M);
    assert(I != MethodMap.end() && "Method not in callgraph!");
    return I->second;
  }
  inline CallGraphNode *operator[](const Method *M) {
    const_iterator I = MethodMap.find(M);
    assert(I != MethodMap.end() && "Method not in callgraph!");
    return I->second;
  }

  // Methods to keep a call graph up to date with a method that has been
  // modified
  //
  void addMethodToModule(Method *Meth);  // TODO IMPLEMENT


  // removeMethodFromModule - Unlink the method from this module, returning it.
  // Because this removes the method from the module, the call graph node is
  // destroyed.  This is only valid if the method does not call any other
  // methods (ie, there are no edges in it's CGN).  The easiest way to do this
  // is to dropAllReferences before calling this.
  //
  Method *removeMethodFromModule(CallGraphNode *CGN);
  Method *removeMethodFromModule(Method *Meth) {
    return removeMethodFromModule((*this)[Meth]);
  }

private:   // Implementation of CallGraph construction

  // getNodeFor - Return the node for the specified method or create one if it
  // does not already exist.
  //
  CallGraphNode *getNodeFor(Method *M);

  // addToCallGraph - Add a method to the call graph, and link the node to all
  // of the methods that it calls.
  //
  void addToCallGraph(Method *M);
};

}  // end namespace cfg




// Provide graph traits for tranversing call graphs using standard graph
// traversals.
template <> struct GraphTraits<cfg::CallGraphNode*> {
  typedef cfg::CallGraphNode NodeType;
  typedef NodeType::iterator ChildIteratorType;

  static NodeType *getEntryNode(cfg::CallGraphNode *CGN) { return CGN; }
  static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();}
  static inline ChildIteratorType child_end  (NodeType *N) { return N->end(); }
};

template <> struct GraphTraits<const cfg::CallGraphNode*> {
  typedef const cfg::CallGraphNode NodeType;
  typedef NodeType::const_iterator ChildIteratorType;

  static NodeType *getEntryNode(const cfg::CallGraphNode *CGN) { return CGN; }
  static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();}
  static inline ChildIteratorType child_end  (NodeType *N) { return N->end(); }
};


template<> struct GraphTraits<cfg::CallGraph*> :
  public GraphTraits<cfg::CallGraphNode*> {
  static NodeType *getEntryNode(cfg::CallGraph *CGN) {
    return CGN->getRoot();
  }
};
template<> struct GraphTraits<const cfg::CallGraph*> :
  public GraphTraits<const cfg::CallGraphNode*> {
  static NodeType *getEntryNode(const cfg::CallGraph *CGN) {
    return CGN->getRoot();
  }
};


// Checks if a method contains any call instructions.
// Note that this uses the call graph only if one is provided.
// It does not build the call graph.
// 
bool isLeafMethod(const Method* method, const cfg::CallGraph *callGraph = 0);

#endif