1 //===- DataStructure.h - Build data structure graphs -------------*- 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"
18 class FunctionRepBuilder;
20 class FunctionDSGraph;
24 // FIXME: move this somewhere private
25 unsigned countPointerFields(const Type *Ty);
27 // PointerVal - Represent a pointer to a datastructure. The pointer points to
28 // a node, and can index into it. This is used for getelementptr instructions,
29 // which do not affect which node a pointer points to, but does change the field
34 unsigned Index; // Index into Node->FieldLinks[]
36 PointerVal(DSNode *N, unsigned Idx = 0) : Node(N), Index(Idx) {}
38 DSNode *getNode() const { return Node; }
39 unsigned getIndex() const { return Index; }
41 inline bool operator==(DSNode *N) const { return Node == N; }
42 inline bool operator!=(DSNode *N) const { return Node != N; }
44 // operator< - Allow insertion into a map...
45 bool operator<(const PointerVal &PV) const {
46 return Node < PV.Node || (Node == PV.Node && Index < PV.Index);
49 inline bool operator==(const PointerVal &PV) const {
50 return Node == PV.Node && Index == PV.Index;
52 inline bool operator!=(const PointerVal &PV) const { return !operator==(PV); }
54 void print(std::ostream &O) const;
58 // PointerValSet - This class represents a list of pointer values. The add
59 // method is used to add values to the set, and ensures that duplicates cannot
63 std::vector<PointerVal> Vals;
68 PointerValSet(const PointerValSet &PVS) : Vals(PVS.Vals) { addRefs(); }
69 ~PointerValSet() { dropRefs(); }
70 const PointerValSet &operator=(const PointerValSet &PVS);
72 // operator< - Allow insertion into a map...
73 bool operator<(const PointerValSet &PVS) const;
74 bool operator==(const PointerValSet &PVS) const;
76 const PointerVal &operator[](unsigned i) const { return Vals[i]; }
78 unsigned size() const { return Vals.size(); }
79 bool empty() const { return Vals.empty(); }
80 void clear() { dropRefs(); Vals.clear(); }
82 // add - Add the specified pointer, or contents of the specified PVS to this
83 // pointer set. If a 'Pointer' value is provided, notify the underlying data
84 // structure node that the pointer is pointing to it, so that it can be
85 // invalidated if neccesary later. True is returned if the value is new to
88 bool add(const PointerVal &PV, Value *Pointer = 0);
89 bool add(const PointerValSet &PVS, Value *Pointer = 0) {
91 for (unsigned i = 0, e = PVS.size(); i != e; ++i)
92 Changed |= add(PVS[i], Pointer);
96 // removePointerTo - Remove a single pointer val that points to the specified
98 void removePointerTo(DSNode *Node);
100 void print(std::ostream &O) const;
104 //===----------------------------------------------------------------------===//
105 // DSNode - Base class for all data structure nodes...
107 // This class keeps track of its type, the pointer fields in the data structure,
108 // and a list of LLVM values that are pointing to this node.
111 friend class FunctionDSGraph;
113 std::vector<PointerValSet> FieldLinks;
114 std::vector<Value*> Pointers; // Values pointing to me...
115 std::vector<PointerValSet*> Referrers;
117 DSNode(const DSNode &); // DO NOT IMPLEMENT
118 void operator=(const DSNode &); // DO NOT IMPLEMENT
121 NewNode, CallNode, ShadowNode, GlobalNode
124 DSNode(enum NodeTy NT, const Type *T);
127 assert(Referrers.empty() && "Referrers to dead node exist!");
130 typedef DSNodeIterator iterator;
131 inline iterator begin(); // Defined in DataStructureGraph.h
132 inline iterator end();
134 unsigned getNumLinks() const { return FieldLinks.size(); }
135 PointerValSet &getLink(unsigned i) {
136 assert(i < getNumLinks() && "Field links access out of range...");
137 return FieldLinks[i];
139 const PointerValSet &getLink(unsigned i) const {
140 assert(i < getNumLinks() && "Field links access out of range...");
141 return FieldLinks[i];
144 // addReferrer - Keep the referrer set up to date...
145 void addReferrer(PointerValSet *PVS) { Referrers.push_back(PVS); }
146 void removeReferrer(PointerValSet *PVS);
147 const std::vector<PointerValSet*> &getReferrers() const { return Referrers; }
149 // removeAllIncomingEdges - Erase all edges in the graph that point to
151 void removeAllIncomingEdges();
153 void addPointer(Value *V) { Pointers.push_back(V); }
154 const std::vector<Value*> &getPointers() const { return Pointers; }
156 const Type *getType() const { return Ty; }
158 // getNumOutgoingLinks - Return the number of outgoing links, which is usually
159 // the number of normal links, but for call nodes it also includes their
162 virtual unsigned getNumOutgoingLinks() const { return getNumLinks(); }
163 virtual PointerValSet &getOutgoingLink(unsigned Link) {
164 return getLink(Link);
166 virtual const PointerValSet &getOutgoingLink(unsigned Link) const {
167 return getLink(Link);
170 void print(std::ostream &O) const;
173 virtual std::string getCaption() const = 0;
174 virtual const std::vector<PointerValSet> *getAuxLinks() const {
175 return 0; // Default to nothing...
178 // isEquivalentTo - Return true if the nodes should be merged...
179 virtual bool isEquivalentTo(DSNode *Node) const = 0;
181 DSNode *clone() const {
182 DSNode *New = cloneImpl();
183 // Add all of the pointers to the new node...
184 for (unsigned pn = 0, pe = Pointers.size(); pn != pe; ++pn)
185 New->addPointer(Pointers[pn]);
190 virtual void dropAllReferences() {
194 static bool classof(const DSNode *N) { return true; }
196 virtual DSNode *cloneImpl() const = 0;
197 virtual void mapNode(std::map<const DSNode*, DSNode*> &NodeMap,
202 // AllocDSNode - Represent all allocation (malloc or alloca) in the program.
204 class AllocDSNode : public DSNode {
205 AllocationInst *Allocation;
207 AllocDSNode(AllocationInst *V);
209 virtual std::string getCaption() const;
211 bool isAllocaNode() const;
212 bool isMallocNode() const { return !isAllocaNode(); }
214 AllocationInst *getAllocation() const { return Allocation; }
216 // isEquivalentTo - Return true if the nodes should be merged...
217 virtual bool isEquivalentTo(DSNode *Node) const;
219 // Support type inquiry through isa, cast, and dyn_cast...
220 static bool classof(const AllocDSNode *) { return true; }
221 static bool classof(const DSNode *N) { return N->NodeType == NewNode; }
223 virtual AllocDSNode *cloneImpl() const { return new AllocDSNode(Allocation); }
227 // GlobalDSNode - Represent the memory location that a global variable occupies
229 class GlobalDSNode : public DSNode {
232 GlobalDSNode(GlobalValue *V);
234 GlobalValue *getGlobal() const { return Val; }
236 virtual std::string getCaption() const;
238 // isEquivalentTo - Return true if the nodes should be merged...
239 virtual bool isEquivalentTo(DSNode *Node) const;
241 // Support type inquiry through isa, cast, and dyn_cast...
242 static bool classof(const GlobalDSNode *) { return true; }
243 static bool classof(const DSNode *N) { return N->NodeType == GlobalNode; }
245 virtual GlobalDSNode *cloneImpl() const { return new GlobalDSNode(Val); }
249 // CallDSNode - Represent a call instruction in the program...
251 class CallDSNode : public DSNode {
252 friend class FunctionDSGraph;
254 std::vector<PointerValSet> ArgLinks;
256 CallDSNode(CallInst *CI);
261 CallInst *getCall() const { return CI; }
263 const std::vector<PointerValSet> *getAuxLinks() const { return &ArgLinks; }
264 virtual std::string getCaption() const;
266 bool addArgValue(unsigned ArgNo, const PointerValSet &PVS) {
267 return ArgLinks[ArgNo].add(PVS);
270 unsigned getNumArgs() const { return ArgLinks.size(); }
271 const PointerValSet &getArgValues(unsigned ArgNo) const {
272 assert(ArgNo < ArgLinks.size() && "Arg # out of range!");
273 return ArgLinks[ArgNo];
275 PointerValSet &getArgValues(unsigned ArgNo) {
276 assert(ArgNo < ArgLinks.size() && "Arg # out of range!");
277 return ArgLinks[ArgNo];
279 const std::vector<PointerValSet> &getArgs() const { return ArgLinks; }
281 virtual void dropAllReferences() {
282 DSNode::dropAllReferences();
286 // getNumOutgoingLinks - Return the number of outgoing links, which is usually
287 // the number of normal links, but for call nodes it also includes their
290 virtual unsigned getNumOutgoingLinks() const {
291 return getNumLinks() + getNumArgs();
293 virtual PointerValSet &getOutgoingLink(unsigned Link) {
294 if (Link < getNumLinks()) return getLink(Link);
295 return getArgValues(Link-getNumLinks());
297 virtual const PointerValSet &getOutgoingLink(unsigned Link) const {
298 if (Link < getNumLinks()) return getLink(Link);
299 return getArgValues(Link-getNumLinks());
302 // isEquivalentTo - Return true if the nodes should be merged...
303 virtual bool isEquivalentTo(DSNode *Node) const;
305 // Support type inquiry through isa, cast, and dyn_cast...
306 static bool classof(const CallDSNode *) { return true; }
307 static bool classof(const DSNode *N) { return N->NodeType == CallNode; }
309 virtual CallDSNode *cloneImpl() const { return new CallDSNode(CI); }
310 virtual void mapNode(std::map<const DSNode*, DSNode*> &NodeMap,
315 // ShadowDSNode - Represent a chunk of memory that we need to be able to
316 // address. These are generated due to (for example) pointer type method
317 // arguments... if the pointer is dereferenced, we need to have a node to point
318 // to. When functions are integrated into each other, shadow nodes are
321 class ShadowDSNode : public DSNode {
322 friend class FunctionDSGraph;
324 ShadowDSNode *ShadowParent; // Nonnull if this is a synthesized node...
325 std::vector<std::pair<const Type *, ShadowDSNode *> > SynthNodes;
327 ShadowDSNode(const Type *Ty, Module *M);
328 virtual std::string getCaption() const;
330 // synthesizeNode - Create a new shadow node that is to be linked into this
333 ShadowDSNode *synthesizeNode(const Type *Ty, FunctionRepBuilder *Rep);
335 // isEquivalentTo - Return true if the nodes should be merged...
336 virtual bool isEquivalentTo(DSNode *Node) const;
338 // Support type inquiry through isa, cast, and dyn_cast...
339 static bool classof(const ShadowDSNode *) { return true; }
340 static bool classof(const DSNode *N) { return N->NodeType == ShadowNode; }
343 ShadowDSNode(const Type *Ty, Module *M, ShadowDSNode *ShadParent);
345 virtual void mapNode(std::map<const DSNode*, DSNode*> &NodeMap,
347 virtual ShadowDSNode *cloneImpl() const {
349 return new ShadowDSNode(getType(), Mod, ShadowParent);
351 return new ShadowDSNode(getType(), Mod);
356 // FunctionDSGraph - The graph that represents a method.
358 class FunctionDSGraph {
360 std::vector<AllocDSNode*> AllocNodes;
361 std::vector<ShadowDSNode*> ShadowNodes;
362 std::vector<GlobalDSNode*> GlobalNodes;
363 std::vector<CallDSNode*> CallNodes;
364 PointerValSet RetNode; // Node that gets returned...
365 std::map<Value*, PointerValSet> ValueMap;
367 // cloneFunctionIntoSelf - Clone the specified method graph into the current
368 // method graph, returning the Return's set of the graph. If ValueMap is set
369 // to true, the ValueMap of the function is cloned into this function as well
370 // as the data structure graph itself. Regardless, the arguments value sets
371 // of DSG are copied into Args.
373 PointerValSet cloneFunctionIntoSelf(const FunctionDSGraph &G, bool ValueMap,
374 std::vector<PointerValSet> &Args);
376 bool RemoveUnreachableNodes();
377 bool UnlinkUndistinguishableNodes();
378 void MarkEscapeableNodesReachable(std::vector<bool> &RSN,
379 std::vector<bool> &RAN);
382 // Define the interface only accessable to DataStructure
383 friend class DataStructure;
384 FunctionDSGraph(Function *F);
385 FunctionDSGraph(const FunctionDSGraph &DSG);
388 void computeClosure(const DataStructure &DS);
391 Function *getFunction() const { return Func; }
393 // getEscapingAllocations - Add all allocations that escape the current
394 // function to the specified vector.
396 void getEscapingAllocations(std::vector<AllocDSNode*> &Allocs);
398 // getNonEscapingAllocations - Add all allocations that do not escape the
399 // current function to the specified vector.
401 void getNonEscapingAllocations(std::vector<AllocDSNode*> &Allocs);
403 // getValueMap - Get a map that describes what the nodes the scalars in this
404 // function point to...
406 std::map<Value*, PointerValSet> &getValueMap() { return ValueMap; }
407 const std::map<Value*, PointerValSet> &getValueMap() const { return ValueMap;}
409 const PointerValSet &getRetNodes() const { return RetNode; }
411 unsigned getGraphSize() const {
412 return AllocNodes.size() + ShadowNodes.size() +
413 GlobalNodes.size() + CallNodes.size();
416 void printFunction(std::ostream &O, const char *Label) const;
420 // FIXME: This should be a FunctionPass. When the pass framework sees a 'Pass'
421 // that uses the output of a FunctionPass, it should automatically build a map
422 // of output from the method pass that the pass can use.
424 class DataStructure : public Pass {
425 // DSInfo, one intraprocedural and one closed graph for each method...
426 typedef std::map<Function*, std::pair<FunctionDSGraph*,
427 FunctionDSGraph*> > InfoMap;
428 mutable InfoMap DSInfo;
430 static AnalysisID ID; // DataStructure Analysis ID
432 DataStructure(AnalysisID id) { assert(id == ID); }
433 ~DataStructure() { releaseMemory(); }
435 // run - Do nothing, because methods are analyzed lazily
436 virtual bool run(Module *TheModule) { return false; }
438 // getDSGraph - Return the data structure graph for the specified method.
439 // Since method graphs are lazily computed, we may have to create one on the
442 FunctionDSGraph &getDSGraph(Function *F) const {
443 std::pair<FunctionDSGraph*, FunctionDSGraph*> &N = DSInfo[F];
444 if (N.first) return *N.first;
445 return *(N.first = new FunctionDSGraph(F));
448 // getClosedDSGraph - Return the data structure graph for the specified
449 // method. Since method graphs are lazily computed, we may have to create one
450 // on the fly here. This is different than the normal DSGraph for the method
451 // because any function calls that are resolvable will have the data structure
452 // graphs of the called function incorporated into this function as well.
454 FunctionDSGraph &getClosedDSGraph(Function *F) const {
455 std::pair<FunctionDSGraph*, FunctionDSGraph*> &N = DSInfo[F];
456 if (N.second) return *N.second;
457 N.second = new FunctionDSGraph(getDSGraph(F));
458 N.second->computeClosure(*this);
462 // invalidateFunction - Inform this analysis that you changed the specified
463 // function, so the graphs that depend on it are out of date.
465 void invalidateFunction(Function *F) const {
466 // FIXME: THis should invalidate all functions who have inlined the
469 std::pair<FunctionDSGraph*, FunctionDSGraph*> &N = DSInfo[F];
472 N.first = N.second = 0;
475 // print - Print out the analysis results...
476 void print(std::ostream &O, Module *M) const;
478 // If the pass pipeline is done with this pass, we can release our memory...
479 virtual void releaseMemory();
481 // getAnalysisUsageInfo - This obviously provides a call graph
482 virtual void getAnalysisUsageInfo(AnalysisSet &Required,
483 AnalysisSet &Destroyed,
484 AnalysisSet &Provided) {
485 Provided.push_back(ID);