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"
11 #include "Support/HashExtras.h"
12 #include "Support/hash_set"
19 // FIXME: move this stuff to a private header
20 namespace DataStructureAnalysis {
21 // isPointerType - Return true if this first class type is big enough to hold
24 bool isPointerType(const Type *Ty);
28 // LocalDataStructures - The analysis that computes the local data structure
29 // graphs for all of the functions in the program.
31 // FIXME: This should be a Function pass that can be USED by a Pass, and would
32 // be automatically preserved. Until we can do that, this is a Pass.
34 class LocalDataStructures : public Pass {
35 // DSInfo, one graph for each function
36 hash_map<const Function*, DSGraph*> DSInfo;
37 DSGraph *GlobalsGraph;
39 ~LocalDataStructures() { releaseMemory(); }
41 virtual bool run(Module &M);
43 bool hasGraph(const Function &F) const {
44 return DSInfo.find(&F) != DSInfo.end();
47 // getDSGraph - Return the data structure graph for the specified function.
48 DSGraph &getDSGraph(const Function &F) const {
49 hash_map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
50 assert(I != DSInfo.end() && "Function not in module!");
54 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
56 // print - Print out the analysis results...
57 void print(std::ostream &O, const Module *M) const;
59 // If the pass pipeline is done with this pass, we can release our memory...
60 virtual void releaseMemory();
62 // getAnalysisUsage - This obviously provides a data structure graph.
63 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
69 // BUDataStructures - The analysis that computes the interprocedurally closed
70 // data structure graphs for all of the functions in the program. This pass
71 // only performs a "Bottom Up" propagation (hence the name).
73 class BUDataStructures : public Pass {
74 // DSInfo, one graph for each function
75 hash_map<const Function*, DSGraph*> DSInfo;
76 DSGraph *GlobalsGraph;
78 ~BUDataStructures() { releaseMemory(); }
80 virtual bool run(Module &M);
82 bool hasGraph(const Function &F) const {
83 return DSInfo.find(&F) != DSInfo.end();
86 // getDSGraph - Return the data structure graph for the specified function.
87 DSGraph &getDSGraph(const Function &F) const {
88 hash_map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
89 assert(I != DSInfo.end() && "Function not in module!");
93 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
95 // print - Print out the analysis results...
96 void print(std::ostream &O, const Module *M) const;
98 // If the pass pipeline is done with this pass, we can release our memory...
99 virtual void releaseMemory();
101 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
102 AU.setPreservesAll();
103 AU.addRequired<LocalDataStructures>();
106 DSGraph &calculateGraph(Function &F);
108 // inlineNonSCCGraphs - This method is almost like the other two calculate
109 // graph methods. This one is used to inline function graphs (from functions
110 // outside of the SCC) into functions in the SCC. It is not supposed to touch
111 // functions IN the SCC at all.
113 DSGraph &inlineNonSCCGraphs(Function &F,
114 hash_set<Function*> &SCCFunctions);
116 DSGraph &calculateSCCGraph(Function &F,
117 hash_set<Function*> &InlinedSCCFunctions);
118 void calculateReachableGraphs(Function *F);
121 DSGraph &getOrCreateGraph(Function *F);
123 unsigned calculateGraphs(Function *F, std::vector<Function*> &Stack,
125 hash_map<Function*, unsigned> &ValMap);
129 // TDDataStructures - Analysis that computes new data structure graphs
130 // for each function using the closed graphs for the callers computed
131 // by the bottom-up pass.
133 class TDDataStructures : public Pass {
134 // DSInfo, one graph for each function
135 hash_map<const Function*, DSGraph*> DSInfo;
136 hash_set<const Function*> GraphDone;
137 DSGraph *GlobalsGraph;
139 ~TDDataStructures() { releaseMyMemory(); }
141 virtual bool run(Module &M);
143 bool hasGraph(const Function &F) const {
144 return DSInfo.find(&F) != DSInfo.end();
147 // getDSGraph - Return the data structure graph for the specified function.
148 DSGraph &getDSGraph(const Function &F) const {
149 hash_map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
150 assert(I != DSInfo.end() && "Function not in module!");
154 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
156 // print - Print out the analysis results...
157 void print(std::ostream &O, const Module *M) const;
159 // If the pass pipeline is done with this pass, we can release our memory...
160 virtual void releaseMyMemory();
162 // getAnalysisUsage - This obviously provides a data structure graph.
163 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
164 AU.setPreservesAll();
165 AU.addRequired<BUDataStructures>();
169 void calculateGraph(Function &F);
170 DSGraph &getOrCreateDSGraph(Function &F);
172 void ResolveCallSite(DSGraph &Graph, const DSCallSite &CallSite);