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;
25 // FIXME: move this somewhere private
26 unsigned countPointerFields(const Type *Ty);
28 // PointerVal - Represent a pointer to a datastructure. The pointer points to
29 // a node, and can index into it. This is used for getelementptr instructions,
30 // which do not affect which node a pointer points to, but does change the field
35 unsigned Index; // Index into Node->FieldLinks[]
37 PointerVal(DSNode *N, unsigned Idx = 0) : Node(N), Index(Idx) {}
39 DSNode *getNode() const { return Node; }
40 unsigned getIndex() const { return Index; }
42 inline bool operator==(DSNode *N) const { return Node == N; }
43 inline bool operator!=(DSNode *N) const { return Node != N; }
45 // operator< - Allow insertion into a map...
46 bool operator<(const PointerVal &PV) const {
47 return Node < PV.Node || (Node == PV.Node && Index < PV.Index);
50 inline bool operator==(const PointerVal &PV) const {
51 return Node == PV.Node && Index == PV.Index;
53 inline bool operator!=(const PointerVal &PV) const { return !operator==(PV); }
55 void print(std::ostream &O) const;
59 // PointerValSet - This class represents a list of pointer values. The add
60 // method is used to add values to the set, and ensures that duplicates cannot
64 std::vector<PointerVal> Vals;
69 PointerValSet(const PointerValSet &PVS) : Vals(PVS.Vals) { addRefs(); }
70 ~PointerValSet() { dropRefs(); }
71 const PointerValSet &operator=(const PointerValSet &PVS);
73 // operator< - Allow insertion into a map...
74 bool operator<(const PointerValSet &PVS) const;
75 bool operator==(const PointerValSet &PVS) const;
77 const PointerVal &operator[](unsigned i) const { return Vals[i]; }
79 unsigned size() const { return Vals.size(); }
80 bool empty() const { return Vals.empty(); }
81 void clear() { dropRefs(); Vals.clear(); }
83 // add - Add the specified pointer, or contents of the specified PVS to this
84 // pointer set. If a 'Pointer' value is provided, notify the underlying data
85 // structure node that the pointer is pointing to it, so that it can be
86 // invalidated if neccesary later. True is returned if the value is new to
89 bool add(const PointerVal &PV, Value *Pointer = 0);
90 bool add(const PointerValSet &PVS, Value *Pointer = 0) {
92 for (unsigned i = 0, e = PVS.size(); i != e; ++i)
93 Changed |= add(PVS[i], Pointer);
97 // removePointerTo - Remove a single pointer val that points to the specified
99 void removePointerTo(DSNode *Node);
101 void print(std::ostream &O) const;
105 //===----------------------------------------------------------------------===//
106 // DSNode - Base class for all data structure nodes...
108 // This class keeps track of its type, the pointer fields in the data structure,
109 // and a list of LLVM values that are pointing to this node.
112 friend class FunctionDSGraph;
114 std::vector<PointerValSet> FieldLinks;
115 std::vector<Value*> Pointers; // Values pointing to me...
116 std::vector<PointerValSet*> Referrers;
118 std::vector<std::pair<const Type *, ShadowDSNode *> > SynthNodes;
120 DSNode(const DSNode &); // DO NOT IMPLEMENT
121 void operator=(const DSNode &); // DO NOT IMPLEMENT
124 NewNode, CallNode, ShadowNode, GlobalNode
127 DSNode(enum NodeTy NT, const Type *T);
130 assert(Referrers.empty() && "Referrers to dead node exist!");
133 typedef DSNodeIterator iterator;
134 inline iterator begin(); // Defined in DataStructureGraph.h
135 inline iterator end();
137 unsigned getNumLinks() const { return FieldLinks.size(); }
138 PointerValSet &getLink(unsigned i) {
139 assert(i < getNumLinks() && "Field links access out of range...");
140 return FieldLinks[i];
142 const PointerValSet &getLink(unsigned i) const {
143 assert(i < getNumLinks() && "Field links access out of range...");
144 return FieldLinks[i];
147 // addReferrer - Keep the referrer set up to date...
148 void addReferrer(PointerValSet *PVS) { Referrers.push_back(PVS); }
149 void removeReferrer(PointerValSet *PVS);
150 const std::vector<PointerValSet*> &getReferrers() const { return Referrers; }
152 // removeAllIncomingEdges - Erase all edges in the graph that point to
154 void removeAllIncomingEdges();
156 void addPointer(Value *V) { Pointers.push_back(V); }
157 const std::vector<Value*> &getPointers() const { return Pointers; }
159 const Type *getType() const { return Ty; }
161 // getNumOutgoingLinks - Return the number of outgoing links, which is usually
162 // the number of normal links, but for call nodes it also includes their
165 virtual unsigned getNumOutgoingLinks() const { return getNumLinks(); }
166 virtual PointerValSet &getOutgoingLink(unsigned Link) {
167 return getLink(Link);
169 virtual const PointerValSet &getOutgoingLink(unsigned Link) const {
170 return getLink(Link);
173 void print(std::ostream &O) const;
176 virtual std::string getCaption() const = 0;
177 virtual const std::vector<PointerValSet> *getAuxLinks() const {
178 return 0; // Default to nothing...
181 // isEquivalentTo - Return true if the nodes should be merged...
182 virtual bool isEquivalentTo(DSNode *Node) const = 0;
183 virtual void mergeInto(DSNode *Node) const {}
185 DSNode *clone() const {
186 DSNode *New = cloneImpl();
187 // Add all of the pointers to the new node...
188 for (unsigned pn = 0, pe = Pointers.size(); pn != pe; ++pn)
189 New->addPointer(Pointers[pn]);
193 // synthesizeNode - Create a new shadow node that is to be linked into this
196 ShadowDSNode *synthesizeNode(const Type *Ty, FunctionRepBuilder *Rep);
198 virtual void dropAllReferences() {
202 static bool classof(const DSNode *N) { return true; }
204 virtual DSNode *cloneImpl() const = 0;
205 virtual void mapNode(std::map<const DSNode*, DSNode*> &NodeMap,
210 // AllocDSNode - Represent all allocation (malloc or alloca) in the program.
212 class AllocDSNode : public DSNode {
213 AllocationInst *Allocation;
214 bool isVarSize; // Allocating variable sized objects
216 AllocDSNode(AllocationInst *V, bool isVarSize = false);
218 virtual std::string getCaption() const;
220 bool isAllocaNode() const;
221 bool isMallocNode() const { return !isAllocaNode(); }
223 AllocationInst *getAllocation() const { return Allocation; }
224 bool isVariableSize() const { return isVarSize; }
226 // isEquivalentTo - Return true if the nodes should be merged...
227 virtual bool isEquivalentTo(DSNode *Node) const;
228 virtual void mergeInto(DSNode *Node) const;
230 // Support type inquiry through isa, cast, and dyn_cast...
231 static bool classof(const AllocDSNode *) { return true; }
232 static bool classof(const DSNode *N) { return N->NodeType == NewNode; }
234 virtual AllocDSNode *cloneImpl() const { return new AllocDSNode(Allocation,
239 // GlobalDSNode - Represent the memory location that a global variable occupies
241 class GlobalDSNode : public DSNode {
244 GlobalDSNode(GlobalValue *V);
246 GlobalValue *getGlobal() const { return Val; }
248 virtual std::string getCaption() const;
250 // isEquivalentTo - Return true if the nodes should be merged...
251 virtual bool isEquivalentTo(DSNode *Node) const;
253 // Support type inquiry through isa, cast, and dyn_cast...
254 static bool classof(const GlobalDSNode *) { return true; }
255 static bool classof(const DSNode *N) { return N->NodeType == GlobalNode; }
257 virtual GlobalDSNode *cloneImpl() const { return new GlobalDSNode(Val); }
261 // CallDSNode - Represent a call instruction in the program...
263 class CallDSNode : public DSNode {
264 friend class FunctionDSGraph;
266 std::vector<PointerValSet> ArgLinks;
268 CallDSNode(CallInst *CI);
273 CallInst *getCall() const { return CI; }
275 const std::vector<PointerValSet> *getAuxLinks() const { return &ArgLinks; }
276 virtual std::string getCaption() const;
278 bool addArgValue(unsigned ArgNo, const PointerValSet &PVS) {
279 return ArgLinks[ArgNo].add(PVS);
282 unsigned getNumArgs() const { return ArgLinks.size(); }
283 const PointerValSet &getArgValues(unsigned ArgNo) const {
284 assert(ArgNo < ArgLinks.size() && "Arg # out of range!");
285 return ArgLinks[ArgNo];
287 PointerValSet &getArgValues(unsigned ArgNo) {
288 assert(ArgNo < ArgLinks.size() && "Arg # out of range!");
289 return ArgLinks[ArgNo];
291 const std::vector<PointerValSet> &getArgs() const { return ArgLinks; }
293 virtual void dropAllReferences() {
294 DSNode::dropAllReferences();
298 // getNumOutgoingLinks - Return the number of outgoing links, which is usually
299 // the number of normal links, but for call nodes it also includes their
302 virtual unsigned getNumOutgoingLinks() const {
303 return getNumLinks() + getNumArgs();
305 virtual PointerValSet &getOutgoingLink(unsigned Link) {
306 if (Link < getNumLinks()) return getLink(Link);
307 return getArgValues(Link-getNumLinks());
309 virtual const PointerValSet &getOutgoingLink(unsigned Link) const {
310 if (Link < getNumLinks()) return getLink(Link);
311 return getArgValues(Link-getNumLinks());
314 // isEquivalentTo - Return true if the nodes should be merged...
315 virtual bool isEquivalentTo(DSNode *Node) const;
317 // Support type inquiry through isa, cast, and dyn_cast...
318 static bool classof(const CallDSNode *) { return true; }
319 static bool classof(const DSNode *N) { return N->NodeType == CallNode; }
321 virtual CallDSNode *cloneImpl() const { return new CallDSNode(CI); }
322 virtual void mapNode(std::map<const DSNode*, DSNode*> &NodeMap,
327 // ShadowDSNode - Represent a chunk of memory that we need to be able to
328 // address. These are generated due to (for example) pointer type method
329 // arguments... if the pointer is dereferenced, we need to have a node to point
330 // to. When functions are integrated into each other, shadow nodes are
333 class ShadowDSNode : public DSNode {
334 friend class FunctionDSGraph;
335 friend class FunctionRepBuilder;
337 DSNode *ShadowParent; // Nonnull if this is a synthesized node...
339 ShadowDSNode(const Type *Ty, Module *M);
340 virtual std::string getCaption() const;
342 // isEquivalentTo - Return true if the nodes should be merged...
343 virtual bool isEquivalentTo(DSNode *Node) const;
345 DSNode *getShadowParent() const { return ShadowParent; }
347 // Support type inquiry through isa, cast, and dyn_cast...
348 static bool classof(const ShadowDSNode *) { return true; }
349 static bool classof(const DSNode *N) { return N->NodeType == ShadowNode; }
352 ShadowDSNode(const Type *Ty, Module *M, DSNode *ShadParent);
354 virtual ShadowDSNode *cloneImpl() const {
356 return new ShadowDSNode(getType(), Mod, ShadowParent);
358 return new ShadowDSNode(getType(), Mod);
363 // FunctionDSGraph - The graph that represents a method.
365 class FunctionDSGraph {
367 std::vector<AllocDSNode*> AllocNodes;
368 std::vector<ShadowDSNode*> ShadowNodes;
369 std::vector<GlobalDSNode*> GlobalNodes;
370 std::vector<CallDSNode*> CallNodes;
371 PointerValSet RetNode; // Node that gets returned...
372 std::map<Value*, PointerValSet> ValueMap;
374 // cloneFunctionIntoSelf - Clone the specified method graph into the current
375 // method graph, returning the Return's set of the graph. If ValueMap is set
376 // to true, the ValueMap of the function is cloned into this function as well
377 // as the data structure graph itself. Regardless, the arguments value sets
378 // of DSG are copied into Args.
380 PointerValSet cloneFunctionIntoSelf(const FunctionDSGraph &G, bool ValueMap,
381 std::vector<PointerValSet> &Args);
383 bool RemoveUnreachableNodes();
384 bool UnlinkUndistinguishableNodes();
385 void MarkEscapeableNodesReachable(std::vector<bool> &RSN,
386 std::vector<bool> &RAN);
389 // Define the interface only accessable to DataStructure
390 friend class DataStructure;
391 FunctionDSGraph(Function *F);
392 FunctionDSGraph(const FunctionDSGraph &DSG);
395 void computeClosure(const DataStructure &DS);
398 Function *getFunction() const { return Func; }
400 // getEscapingAllocations - Add all allocations that escape the current
401 // function to the specified vector.
403 void getEscapingAllocations(std::vector<AllocDSNode*> &Allocs);
405 // getNonEscapingAllocations - Add all allocations that do not escape the
406 // current function to the specified vector.
408 void getNonEscapingAllocations(std::vector<AllocDSNode*> &Allocs);
410 // getValueMap - Get a map that describes what the nodes the scalars in this
411 // function point to...
413 std::map<Value*, PointerValSet> &getValueMap() { return ValueMap; }
414 const std::map<Value*, PointerValSet> &getValueMap() const { return ValueMap;}
416 const PointerValSet &getRetNodes() const { return RetNode; }
418 unsigned getGraphSize() const {
419 return AllocNodes.size() + ShadowNodes.size() +
420 GlobalNodes.size() + CallNodes.size();
423 void printFunction(std::ostream &O, const char *Label) const;
427 // FIXME: This should be a FunctionPass. When the pass framework sees a 'Pass'
428 // that uses the output of a FunctionPass, it should automatically build a map
429 // of output from the method pass that the pass can use.
431 class DataStructure : public Pass {
432 // DSInfo, one intraprocedural and one closed graph for each method...
433 typedef std::map<Function*, std::pair<FunctionDSGraph*,
434 FunctionDSGraph*> > InfoMap;
435 mutable InfoMap DSInfo;
437 static AnalysisID ID; // DataStructure Analysis ID
439 DataStructure(AnalysisID id) { assert(id == ID); }
440 ~DataStructure() { releaseMemory(); }
442 virtual const char *getPassName() const { return "Data Structure Analysis"; }
444 // run - Do nothing, because methods are analyzed lazily
445 virtual bool run(Module *TheModule) { return false; }
447 // getDSGraph - Return the data structure graph for the specified method.
448 // Since method graphs are lazily computed, we may have to create one on the
451 FunctionDSGraph &getDSGraph(Function *F) const {
452 std::pair<FunctionDSGraph*, FunctionDSGraph*> &N = DSInfo[F];
453 if (N.first) return *N.first;
454 return *(N.first = new FunctionDSGraph(F));
457 // getClosedDSGraph - Return the data structure graph for the specified
458 // method. Since method graphs are lazily computed, we may have to create one
459 // on the fly here. This is different than the normal DSGraph for the method
460 // because any function calls that are resolvable will have the data structure
461 // graphs of the called function incorporated into this function as well.
463 FunctionDSGraph &getClosedDSGraph(Function *F) const {
464 std::pair<FunctionDSGraph*, FunctionDSGraph*> &N = DSInfo[F];
465 if (N.second) return *N.second;
466 N.second = new FunctionDSGraph(getDSGraph(F));
467 N.second->computeClosure(*this);
471 // invalidateFunction - Inform this analysis that you changed the specified
472 // function, so the graphs that depend on it are out of date.
474 void invalidateFunction(Function *F) const {
475 // FIXME: THis should invalidate all functions who have inlined the
478 std::pair<FunctionDSGraph*, FunctionDSGraph*> &N = DSInfo[F];
481 N.first = N.second = 0;
484 // print - Print out the analysis results...
485 void print(std::ostream &O, Module *M) const;
487 // If the pass pipeline is done with this pass, we can release our memory...
488 virtual void releaseMemory();
490 // getAnalysisUsage - This obviously provides a call graph
491 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
492 AU.setPreservesAll();