1 //===- DataStructure.h - Build a Module's call graph -------------*- C++ -*--=//
3 // Implement the LLVM data structure analysis library.
5 //===----------------------------------------------------------------------===//
7 #ifndef LLVM_ANALYSIS_DATA_STRUCTURE_H
8 #define LLVM_ANALYSIS_DATA_STRUCTURE_H
10 #include "llvm/Pass.h"
16 class FunctionArgument;
18 class FunctionRepBuilder;
20 class FunctionDSGraph;
23 // FIXME: move this somewhere private
24 unsigned countPointerFields(const Type *Ty);
26 // PointerVal - Represent a pointer to a datastructure. The pointer points to
27 // a node, and can index into it. This is used for getelementptr instructions,
28 // which do not affect which node a pointer points to, but does change the field
33 unsigned Index; // Index into Node->FieldLinks[]
35 PointerVal(DSNode *N, unsigned Idx = 0) : Node(N), Index(Idx) {}
37 DSNode *getNode() const { return Node; }
38 unsigned getIndex() const { return Index; }
40 inline bool operator==(DSNode *N) const { return Node == N; }
41 inline bool operator!=(DSNode *N) const { return Node != N; }
43 inline bool operator==(const PointerVal &PV) const {
44 return Node == PV.Node && Index == PV.Index;
46 inline bool operator!=(const PointerVal &PV) const { return !operator==(PV); }
48 void print(std::ostream &O) const;
52 // PointerValSet - This class represents a list of pointer values. The add
53 // method is used to add values to the set, and ensures that duplicates cannot
57 std::vector<PointerVal> Vals;
62 PointerValSet(const PointerValSet &PVS) : Vals(PVS.Vals) { addRefs(); }
63 ~PointerValSet() { dropRefs(); }
64 const PointerValSet &operator=(const PointerValSet &PVS);
66 const PointerVal &operator[](unsigned i) const { return Vals[i]; }
68 unsigned size() const { return Vals.size(); }
69 bool empty() const { return Vals.empty(); }
70 void clear() { dropRefs(); Vals.clear(); }
72 // add - Add the specified pointer, or contents of the specified PVS to this
73 // pointer set. If a 'Pointer' value is provided, notify the underlying data
74 // structure node that the pointer is pointing to it, so that it can be
75 // invalidated if neccesary later. True is returned if the value is new to
78 bool add(const PointerVal &PV, Value *Pointer = 0);
79 bool add(const PointerValSet &PVS, Value *Pointer = 0) {
81 for (unsigned i = 0, e = PVS.size(); i != e; ++i)
82 Changed |= add(PVS[i], Pointer);
86 // removePointerTo - Remove a single pointer val that points to the specified
88 void removePointerTo(DSNode *Node);
90 void print(std::ostream &O) const;
94 //===----------------------------------------------------------------------===//
95 // DSNode - Base class for all data structure nodes...
97 // This class keeps track of its type, the pointer fields in the data structure,
98 // and a list of LLVM values that are pointing to this node.
101 friend class FunctionDSGraph;
103 std::vector<PointerValSet> FieldLinks;
104 std::vector<Value*> Pointers; // Values pointing to me...
105 std::vector<PointerValSet*> Referrers;
107 DSNode(const DSNode &); // DO NOT IMPLEMENT
108 void operator=(const DSNode &); // DO NOT IMPLEMENT
111 NewNode, CallNode, ShadowNode, ArgNode, GlobalNode
114 DSNode(enum NodeTy NT, const Type *T);
117 assert(Referrers.empty() && "Referrers to dead node exist!");
120 unsigned getNumLinks() const { return FieldLinks.size(); }
121 PointerValSet &getLink(unsigned i) {
122 assert(i < getNumLinks() && "Field links access out of range...");
123 return FieldLinks[i];
126 // addReferrer - Keep the referrer set up to date...
127 void addReferrer(PointerValSet *PVS) { Referrers.push_back(PVS); }
128 void removeReferrer(PointerValSet *PVS);
129 const std::vector<PointerValSet*> &getReferrers() const { return Referrers; }
131 void addPointer(Value *V) { Pointers.push_back(V); }
132 const std::vector<Value*> &getPointers() const { return Pointers; }
134 const Type *getType() const { return Ty; }
136 void print(std::ostream &O) const;
138 virtual std::string getCaption() const = 0;
139 virtual const std::vector<PointerValSet> *getAuxLinks() const {
140 return 0; // Default to nothing...
143 DSNode *clone() const {
144 DSNode *New = cloneImpl();
145 // Add all of the pointers to the new node...
146 for (unsigned pn = 0, pe = Pointers.size(); pn != pe; ++pn)
147 New->addPointer(Pointers[pn]);
152 virtual void dropAllReferences() {
157 virtual DSNode *cloneImpl() const = 0;
158 virtual void mapNode(std::map<const DSNode*, DSNode*> &NodeMap,
163 // NewDSNode - Represent all allocation (malloc or alloca) in the program.
165 class NewDSNode : public DSNode {
166 AllocationInst *Allocation;
168 NewDSNode(AllocationInst *V);
170 virtual std::string getCaption() const;
172 // Support type inquiry through isa, cast, and dyn_cast...
173 static bool classof(const NewDSNode *) { return true; }
174 static bool classof(const DSNode *N) { return N->NodeType == NewNode; }
176 virtual NewDSNode *cloneImpl() const { return new NewDSNode(Allocation); }
180 // GlobalDSNode - Represent the memory location that a global variable occupies
182 class GlobalDSNode : public DSNode {
185 GlobalDSNode(GlobalValue *V);
187 virtual std::string getCaption() const;
189 // Support type inquiry through isa, cast, and dyn_cast...
190 static bool classof(const GlobalDSNode *) { return true; }
191 static bool classof(const DSNode *N) { return N->NodeType == GlobalNode; }
193 virtual GlobalDSNode *cloneImpl() const { return new GlobalDSNode(Val); }
197 // CallDSNode - Represent a call instruction in the program...
199 class CallDSNode : public DSNode {
201 std::vector<PointerValSet> ArgLinks;
203 CallDSNode(CallInst *CI);
205 CallInst *getCall() const { return CI; }
207 const std::vector<PointerValSet> *getAuxLinks() const { return &ArgLinks; }
208 virtual std::string getCaption() const;
210 bool addArgValue(unsigned ArgNo, const PointerValSet &PVS) {
211 return ArgLinks[ArgNo].add(PVS);
214 unsigned getNumArgs() const { return ArgLinks.size(); }
215 const PointerValSet &getArgValues(unsigned ArgNo) const {
216 assert(ArgNo < ArgLinks.size() && "Arg # out of range!");
217 return ArgLinks[ArgNo];
220 virtual void dropAllReferences() {
221 DSNode::dropAllReferences();
226 // Support type inquiry through isa, cast, and dyn_cast...
227 static bool classof(const CallDSNode *) { return true; }
228 static bool classof(const DSNode *N) { return N->NodeType == CallNode; }
230 virtual CallDSNode *cloneImpl() const { return new CallDSNode(CI); }
231 virtual void mapNode(std::map<const DSNode*, DSNode*> &NodeMap,
236 // ArgDSNode - Represent an incoming argument to the current function...
238 class ArgDSNode : public DSNode {
239 FunctionArgument *FuncArg;
241 ArgDSNode(FunctionArgument *MA);
242 virtual std::string getCaption() const;
244 // Support type inquiry through isa, cast, and dyn_cast...
245 static bool classof(const ArgDSNode *) { return true; }
246 static bool classof(const DSNode *N) { return N->NodeType == ArgNode; }
248 virtual ArgDSNode *cloneImpl() const { return new ArgDSNode(FuncArg); }
252 // ShadowDSNode - Represent a chunk of memory that we need to be able to
253 // address. These are generated due to (for example) pointer type method
254 // arguments... if the pointer is dereferenced, we need to have a node to point
255 // to. When functions are integrated into each other, shadow nodes are
258 class ShadowDSNode : public DSNode {
259 friend class FunctionDSGraph;
262 ShadowDSNode *ShadowParent; // Nonnull if this is a synthesized node...
263 std::vector<std::pair<const Type *, ShadowDSNode *> > SynthNodes;
265 ShadowDSNode(DSNode *Parent, Module *M);
266 virtual std::string getCaption() const;
268 // synthesizeNode - Create a new shadow node that is to be linked into this
271 ShadowDSNode *synthesizeNode(const Type *Ty, FunctionRepBuilder *Rep);
273 // Support type inquiry through isa, cast, and dyn_cast...
274 static bool classof(const ShadowDSNode *) { return true; }
275 static bool classof(const DSNode *N) { return N->NodeType == ShadowNode; }
278 ShadowDSNode(const Type *Ty, Module *M, ShadowDSNode *ShadParent);
280 virtual void mapNode(std::map<const DSNode*, DSNode*> &NodeMap,
282 virtual ShadowDSNode *cloneImpl() const {
284 return new ShadowDSNode(getType(), Mod, ShadowParent);
286 return new ShadowDSNode(Parent, Mod);
291 // FunctionDSGraph - The graph that represents a method.
293 class FunctionDSGraph {
295 std::vector<DSNode*> Nodes;
296 std::vector<ShadowDSNode*> ShadowNodes;
297 PointerValSet RetNode; // Node that gets returned...
298 std::map<Value*, PointerValSet> ValueMap;
300 // cloneFunctionIntoSelf - Clone the specified method graph into the current
301 // method graph, returning the Return's set of the graph. If ValueMap is set
302 // to true, the ValueMap of the function is cloned into this function as well
303 // as the data structure graph itself.
305 PointerValSet cloneFunctionIntoSelf(const FunctionDSGraph &G, bool ValueMap);
306 void RemoveUnreachableShadowNodes();
307 void UnlinkUndistinguishableShadowNodes();
309 FunctionDSGraph(Function *F);
310 FunctionDSGraph(const FunctionDSGraph &DSG);
313 void computeClosure(const DataStructure &DS);
315 Function *getFunction() const { return Func; }
317 void printFunction(std::ostream &O, const char *Label) const;
321 // FIXME: This should be a FunctionPass. When the pass framework sees a 'Pass'
322 // that uses the output of a FunctionPass, it should automatically build a map
323 // of output from the method pass that the pass can use.
325 class DataStructure : public Pass {
326 // DSInfo, one intraprocedural and one closed graph for each method...
327 typedef std::map<Function*, std::pair<FunctionDSGraph*,
328 FunctionDSGraph*> > InfoMap;
329 mutable InfoMap DSInfo;
331 static AnalysisID ID; // DataStructure Analysis ID
333 DataStructure(AnalysisID id) { assert(id == ID); }
334 ~DataStructure() { releaseMemory(); }
336 // run - Do nothing, because methods are analyzed lazily
337 virtual bool run(Module *TheModule) { return false; }
339 // getDSGraph - Return the data structure graph for the specified method.
340 // Since method graphs are lazily computed, we may have to create one on the
343 FunctionDSGraph &getDSGraph(Function *F) const {
344 std::pair<FunctionDSGraph*, FunctionDSGraph*> &N = DSInfo[F];
345 if (N.first) return *N.first;
346 return *(N.first = new FunctionDSGraph(F));
349 // getClosedDSGraph - Return the data structure graph for the specified
350 // method. Since method graphs are lazily computed, we may have to create one
351 // on the fly here. This is different than the normal DSGraph for the method
352 // because any function calls that are resolvable will have the data structure
353 // graphs of the called function incorporated into this function as well.
355 FunctionDSGraph &getClosedDSGraph(Function *F) const {
356 std::pair<FunctionDSGraph*, FunctionDSGraph*> &N = DSInfo[F];
357 if (N.second) return *N.second;
358 N.second = new FunctionDSGraph(getDSGraph(F));
359 N.second->computeClosure(*this);
363 // print - Print out the analysis results...
364 void print(std::ostream &O, Module *M) const;
366 // If the pass pipeline is done with this pass, we can release our memory...
367 virtual void releaseMemory();
369 // getAnalysisUsageInfo - This obviously provides a call graph
370 virtual void getAnalysisUsageInfo(AnalysisSet &Required,
371 AnalysisSet &Destroyed,
372 AnalysisSet &Provided) {
373 Provided.push_back(ID);