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 // operator< - Allow insertion into a map...
44 bool operator<(const PointerVal &PV) const {
45 return Node < PV.Node || (Node == PV.Node && Index < PV.Index);
48 inline bool operator==(const PointerVal &PV) const {
49 return Node == PV.Node && Index == PV.Index;
51 inline bool operator!=(const PointerVal &PV) const { return !operator==(PV); }
53 void print(std::ostream &O) const;
57 // PointerValSet - This class represents a list of pointer values. The add
58 // method is used to add values to the set, and ensures that duplicates cannot
62 std::vector<PointerVal> Vals;
67 PointerValSet(const PointerValSet &PVS) : Vals(PVS.Vals) { addRefs(); }
68 ~PointerValSet() { dropRefs(); }
69 const PointerValSet &operator=(const PointerValSet &PVS);
71 // operator< - Allow insertion into a map...
72 bool operator<(const PointerValSet &PVS) const;
73 bool operator==(const PointerValSet &PVS) const;
75 const PointerVal &operator[](unsigned i) const { return Vals[i]; }
77 unsigned size() const { return Vals.size(); }
78 bool empty() const { return Vals.empty(); }
79 void clear() { dropRefs(); Vals.clear(); }
81 // add - Add the specified pointer, or contents of the specified PVS to this
82 // pointer set. If a 'Pointer' value is provided, notify the underlying data
83 // structure node that the pointer is pointing to it, so that it can be
84 // invalidated if neccesary later. True is returned if the value is new to
87 bool add(const PointerVal &PV, Value *Pointer = 0);
88 bool add(const PointerValSet &PVS, Value *Pointer = 0) {
90 for (unsigned i = 0, e = PVS.size(); i != e; ++i)
91 Changed |= add(PVS[i], Pointer);
95 // removePointerTo - Remove a single pointer val that points to the specified
97 void removePointerTo(DSNode *Node);
99 void print(std::ostream &O) const;
103 //===----------------------------------------------------------------------===//
104 // DSNode - Base class for all data structure nodes...
106 // This class keeps track of its type, the pointer fields in the data structure,
107 // and a list of LLVM values that are pointing to this node.
110 friend class FunctionDSGraph;
112 std::vector<PointerValSet> FieldLinks;
113 std::vector<Value*> Pointers; // Values pointing to me...
114 std::vector<PointerValSet*> Referrers;
116 DSNode(const DSNode &); // DO NOT IMPLEMENT
117 void operator=(const DSNode &); // DO NOT IMPLEMENT
120 NewNode, CallNode, ShadowNode, ArgNode, GlobalNode
123 DSNode(enum NodeTy NT, const Type *T);
126 assert(Referrers.empty() && "Referrers to dead node exist!");
129 unsigned getNumLinks() const { return FieldLinks.size(); }
130 PointerValSet &getLink(unsigned i) {
131 assert(i < getNumLinks() && "Field links access out of range...");
132 return FieldLinks[i];
135 // addReferrer - Keep the referrer set up to date...
136 void addReferrer(PointerValSet *PVS) { Referrers.push_back(PVS); }
137 void removeReferrer(PointerValSet *PVS);
138 const std::vector<PointerValSet*> &getReferrers() const { return Referrers; }
140 // removeAllIncomingEdges - Erase all edges in the graph that point to
142 void removeAllIncomingEdges();
144 void addPointer(Value *V) { Pointers.push_back(V); }
145 const std::vector<Value*> &getPointers() const { return Pointers; }
147 const Type *getType() const { return Ty; }
149 void print(std::ostream &O) const;
151 virtual std::string getCaption() const = 0;
152 virtual const std::vector<PointerValSet> *getAuxLinks() const {
153 return 0; // Default to nothing...
156 // isEquivalentTo - Return true if the nodes should be merged...
157 virtual bool isEquivalentTo(DSNode *Node) const = 0;
159 DSNode *clone() const {
160 DSNode *New = cloneImpl();
161 // Add all of the pointers to the new node...
162 for (unsigned pn = 0, pe = Pointers.size(); pn != pe; ++pn)
163 New->addPointer(Pointers[pn]);
168 virtual void dropAllReferences() {
172 static bool classof(const DSNode *N) { return true; }
174 virtual DSNode *cloneImpl() const = 0;
175 virtual void mapNode(std::map<const DSNode*, DSNode*> &NodeMap,
180 // AllocDSNode - Represent all allocation (malloc or alloca) in the program.
182 class AllocDSNode : public DSNode {
183 AllocationInst *Allocation;
185 AllocDSNode(AllocationInst *V);
187 virtual std::string getCaption() const;
189 bool isAllocaNode() const;
190 bool isMallocNode() const { return !isAllocaNode(); }
192 // isEquivalentTo - Return true if the nodes should be merged...
193 virtual bool isEquivalentTo(DSNode *Node) const;
195 // Support type inquiry through isa, cast, and dyn_cast...
196 static bool classof(const AllocDSNode *) { return true; }
197 static bool classof(const DSNode *N) { return N->NodeType == NewNode; }
199 virtual AllocDSNode *cloneImpl() const { return new AllocDSNode(Allocation); }
203 // GlobalDSNode - Represent the memory location that a global variable occupies
205 class GlobalDSNode : public DSNode {
208 GlobalDSNode(GlobalValue *V);
210 GlobalValue *getGlobal() const { return Val; }
212 virtual std::string getCaption() const;
214 // isEquivalentTo - Return true if the nodes should be merged...
215 virtual bool isEquivalentTo(DSNode *Node) const;
217 // Support type inquiry through isa, cast, and dyn_cast...
218 static bool classof(const GlobalDSNode *) { return true; }
219 static bool classof(const DSNode *N) { return N->NodeType == GlobalNode; }
221 virtual GlobalDSNode *cloneImpl() const { return new GlobalDSNode(Val); }
225 // CallDSNode - Represent a call instruction in the program...
227 class CallDSNode : public DSNode {
228 friend class FunctionDSGraph;
230 std::vector<PointerValSet> ArgLinks;
232 CallDSNode(CallInst *CI);
234 CallInst *getCall() const { return CI; }
236 const std::vector<PointerValSet> *getAuxLinks() const { return &ArgLinks; }
237 virtual std::string getCaption() const;
239 bool addArgValue(unsigned ArgNo, const PointerValSet &PVS) {
240 return ArgLinks[ArgNo].add(PVS);
243 unsigned getNumArgs() const { return ArgLinks.size(); }
244 const PointerValSet &getArgValues(unsigned ArgNo) const {
245 assert(ArgNo < ArgLinks.size() && "Arg # out of range!");
246 return ArgLinks[ArgNo];
248 const std::vector<PointerValSet> &getArgs() const { return ArgLinks; }
250 virtual void dropAllReferences() {
251 DSNode::dropAllReferences();
255 // isEquivalentTo - Return true if the nodes should be merged...
256 virtual bool isEquivalentTo(DSNode *Node) const;
258 // Support type inquiry through isa, cast, and dyn_cast...
259 static bool classof(const CallDSNode *) { return true; }
260 static bool classof(const DSNode *N) { return N->NodeType == CallNode; }
262 virtual CallDSNode *cloneImpl() const { return new CallDSNode(CI); }
263 virtual void mapNode(std::map<const DSNode*, DSNode*> &NodeMap,
268 // ArgDSNode - Represent an incoming argument to the current function...
270 class ArgDSNode : public DSNode {
271 FunctionArgument *FuncArg;
273 ArgDSNode(FunctionArgument *MA);
274 virtual std::string getCaption() const;
276 // isEquivalentTo - Return true if the nodes should be merged...
277 virtual bool isEquivalentTo(DSNode *Node) const;
279 // Support type inquiry through isa, cast, and dyn_cast...
280 static bool classof(const ArgDSNode *) { return true; }
281 static bool classof(const DSNode *N) { return N->NodeType == ArgNode; }
283 virtual ArgDSNode *cloneImpl() const { return new ArgDSNode(FuncArg); }
287 // ShadowDSNode - Represent a chunk of memory that we need to be able to
288 // address. These are generated due to (for example) pointer type method
289 // arguments... if the pointer is dereferenced, we need to have a node to point
290 // to. When functions are integrated into each other, shadow nodes are
293 // Shadow nodes may be marked as "critical" nodes when they are created. This
294 // mark indicates that the node is the result of a function call, the value
295 // pointed to by an incoming argument, or the value pointed to by a global
296 // variable [fixme todo]. Since it is not possible to know what these nodes
297 // point to, given just the current context, they are marked "Critical" to avoid
298 // having the shadow node merger eliminate them.
300 class ShadowDSNode : public DSNode {
301 friend class FunctionDSGraph;
304 ShadowDSNode *ShadowParent; // Nonnull if this is a synthesized node...
305 std::vector<std::pair<const Type *, ShadowDSNode *> > SynthNodes;
308 ShadowDSNode(DSNode *Parent, Module *M, bool Critical = false);
309 virtual std::string getCaption() const;
311 // synthesizeNode - Create a new shadow node that is to be linked into this
314 ShadowDSNode *synthesizeNode(const Type *Ty, FunctionRepBuilder *Rep);
316 bool isCriticalNode() const { return CriticalNode; }
317 void resetCriticalMark() { CriticalNode = false; }
319 // isEquivalentTo - Return true if the nodes should be merged...
320 virtual bool isEquivalentTo(DSNode *Node) const;
322 // Support type inquiry through isa, cast, and dyn_cast...
323 static bool classof(const ShadowDSNode *) { return true; }
324 static bool classof(const DSNode *N) { return N->NodeType == ShadowNode; }
327 ShadowDSNode(const Type *Ty, Module *M, ShadowDSNode *ShadParent);
329 virtual void mapNode(std::map<const DSNode*, DSNode*> &NodeMap,
331 virtual ShadowDSNode *cloneImpl() const {
333 return new ShadowDSNode(getType(), Mod, ShadowParent);
335 return new ShadowDSNode(Parent, Mod, CriticalNode);
340 // FunctionDSGraph - The graph that represents a method.
342 class FunctionDSGraph {
344 std::vector<ArgDSNode*> ArgNodes;
345 std::vector<AllocDSNode*> AllocNodes;
346 std::vector<ShadowDSNode*> ShadowNodes;
347 std::vector<GlobalDSNode*> GlobalNodes;
348 std::vector<CallDSNode*> CallNodes;
349 PointerValSet RetNode; // Node that gets returned...
350 std::map<Value*, PointerValSet> ValueMap;
352 // cloneFunctionIntoSelf - Clone the specified method graph into the current
353 // method graph, returning the Return's set of the graph. If ValueMap is set
354 // to true, the ValueMap of the function is cloned into this function as well
355 // as the data structure graph itself.
357 PointerValSet cloneFunctionIntoSelf(const FunctionDSGraph &G, bool ValueMap);
358 bool RemoveUnreachableNodes();
359 bool UnlinkUndistinguishableNodes();
360 void MarkEscapeableNodesReachable(std::vector<bool> &RSN,
361 std::vector<bool> &RAN);
364 // Define the interface only accessable to DataStructure
365 friend class DataStructure;
366 FunctionDSGraph(Function *F);
367 FunctionDSGraph(const FunctionDSGraph &DSG);
370 void computeClosure(const DataStructure &DS);
373 Function *getFunction() const { return Func; }
375 // getEscapingAllocations - Add all allocations that escape the current
376 // function to the specified vector.
378 void getEscapingAllocations(std::vector<AllocDSNode*> &Allocs);
380 // getNonEscapingAllocations - Add all allocations that do not escape the
381 // current function to the specified vector.
383 void getNonEscapingAllocations(std::vector<AllocDSNode*> &Allocs);
385 void printFunction(std::ostream &O, const char *Label) const;
389 // FIXME: This should be a FunctionPass. When the pass framework sees a 'Pass'
390 // that uses the output of a FunctionPass, it should automatically build a map
391 // of output from the method pass that the pass can use.
393 class DataStructure : public Pass {
394 // DSInfo, one intraprocedural and one closed graph for each method...
395 typedef std::map<Function*, std::pair<FunctionDSGraph*,
396 FunctionDSGraph*> > InfoMap;
397 mutable InfoMap DSInfo;
399 static AnalysisID ID; // DataStructure Analysis ID
401 DataStructure(AnalysisID id) { assert(id == ID); }
402 ~DataStructure() { releaseMemory(); }
404 // run - Do nothing, because methods are analyzed lazily
405 virtual bool run(Module *TheModule) { return false; }
407 // getDSGraph - Return the data structure graph for the specified method.
408 // Since method graphs are lazily computed, we may have to create one on the
411 FunctionDSGraph &getDSGraph(Function *F) const {
412 std::pair<FunctionDSGraph*, FunctionDSGraph*> &N = DSInfo[F];
413 if (N.first) return *N.first;
414 return *(N.first = new FunctionDSGraph(F));
417 // getClosedDSGraph - Return the data structure graph for the specified
418 // method. Since method graphs are lazily computed, we may have to create one
419 // on the fly here. This is different than the normal DSGraph for the method
420 // because any function calls that are resolvable will have the data structure
421 // graphs of the called function incorporated into this function as well.
423 FunctionDSGraph &getClosedDSGraph(Function *F) const {
424 std::pair<FunctionDSGraph*, FunctionDSGraph*> &N = DSInfo[F];
425 if (N.second) return *N.second;
426 N.second = new FunctionDSGraph(getDSGraph(F));
427 N.second->computeClosure(*this);
431 // print - Print out the analysis results...
432 void print(std::ostream &O, Module *M) const;
434 // If the pass pipeline is done with this pass, we can release our memory...
435 virtual void releaseMemory();
437 // getAnalysisUsageInfo - This obviously provides a call graph
438 virtual void getAnalysisUsageInfo(AnalysisSet &Required,
439 AnalysisSet &Destroyed,
440 AnalysisSet &Provided) {
441 Provided.push_back(ID);