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"
16 class LocalDataStructures; // A collection of local graphs for a program
17 class BUDataStructures; // A collection of bu graphs for a program
18 class TDDataStructures; // A collection of td graphs for a program
20 // FIXME: move this stuff to a private header
21 namespace DataStructureAnalysis {
22 // isPointerType - Return true if this first class type is big enough to hold
25 bool isPointerType(const Type *Ty);
29 // LocalDataStructures - The analysis that computes the local data structure
30 // graphs for all of the functions in the program.
32 // FIXME: This should be a Function pass that can be USED by a Pass, and would
33 // be automatically preserved. Until we can do that, this is a Pass.
35 class LocalDataStructures : public Pass {
36 // DSInfo, one graph for each function
37 std::map<const Function*, DSGraph*> DSInfo;
39 ~LocalDataStructures() { releaseMemory(); }
41 virtual bool run(Module &M);
43 // getDSGraph - Return the data structure graph for the specified function.
44 DSGraph &getDSGraph(const Function &F) const {
45 std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
46 assert(I != DSInfo.end() && "Function not in module!");
50 // print - Print out the analysis results...
51 void print(std::ostream &O, const Module *M) const;
53 // If the pass pipeline is done with this pass, we can release our memory...
54 virtual void releaseMemory();
56 // getAnalysisUsage - This obviously provides a data structure graph.
57 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
62 // BUDataStructures - The analysis that computes the interprocedurally closed
63 // data structure graphs for all of the functions in the program. This pass
64 // only performs a "Bottom Up" propogation (hence the name).
66 class BUDataStructures : public Pass {
68 // DSInfo, one graph for each function
69 std::map<const Function*, DSGraph*> DSInfo;
70 std::map<const Function*, std::vector<DSCallSite> > CallSites;
72 ~BUDataStructures() { releaseMemory(); }
74 virtual bool run(Module &M);
76 // getDSGraph - Return the data structure graph for the specified function.
77 DSGraph &getDSGraph(const Function &F) const {
78 std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
79 assert(I != DSInfo.end() && "Function not in module!");
83 const std::vector<DSCallSite> *getCallSites(const Function &F) const {
84 std::map<const Function*, std::vector<DSCallSite> >::const_iterator I
86 return I != CallSites.end() ? &I->second : 0;
89 // print - Print out the analysis results...
90 void print(std::ostream &O, const Module *M) const;
92 // If the pass pipeline is done with this pass, we can release our memory...
93 virtual void releaseMemory();
95 // getAnalysisUsage - This obviously provides a data structure graph.
96 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
98 AU.addRequired<LocalDataStructures>();
101 DSGraph &calculateGraph(Function &F);
104 // TDDataStructures - Analysis that computes new data structure graphs
105 // for each function using the closed graphs for the callers computed
106 // by the bottom-up pass.
108 class TDDataStructures : public Pass {
109 // DSInfo, one graph for each function
110 std::map<const Function*, DSGraph*> DSInfo;
112 ~TDDataStructures() { releaseMemory(); }
114 virtual bool run(Module &M);
116 // getDSGraph - Return the data structure graph for the specified function.
117 DSGraph &getDSGraph(const Function &F) const {
118 std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
119 assert(I != DSInfo.end() && "Function not in module!");
123 // print - Print out the analysis results...
124 void print(std::ostream &O, const Module *M) const;
126 // If the pass pipeline is done with this pass, we can release our memory...
127 virtual void releaseMemory();
129 // getAnalysisUsage - This obviously provides a data structure graph.
130 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
131 AU.setPreservesAll();
132 AU.addRequired<BUDataStructures>();
135 DSGraph &calculateGraph(Function &F);
137 void ResolveCallSite(DSGraph &Graph,
138 const DSCallSite &CallSite);
142 // GlobalDSGraph - A common graph for all the globals and their outgoing links
143 // to externally visible nodes. This includes GlobalValues, New nodes,
144 // Cast nodes, and Calls. This graph can only be used by one of the
145 // individual function graphs, and it goes away when they all go away.
147 class GlobalDSGraph : public DSGraph {
148 hash_set<const DSGraph*> Referrers;
149 void addReference(const DSGraph* referrer);
150 void removeReference(const DSGraph* referrer);
151 friend class DSGraph; // give access to Referrers
153 GlobalDSGraph(const GlobalDSGraph &GlobalDSG); // Do not implement
155 // Helper function for cloneGlobals and cloneCalls
156 DSNode* cloneNodeInto(DSNode *OldNode,
157 std::map<const DSNode*, DSNode*> &NodeCache,
158 bool GlobalsAreFinal = false);
161 GlobalDSGraph(); // Create an empty DSGraph
162 virtual ~GlobalDSGraph();
164 void cloneGlobals(DSGraph& Graph, bool CloneCalls = false);
165 void cloneCalls (DSGraph& Graph);