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 // FIXME: move this stuff to a private header
19 namespace DataStructureAnalysis {
20 // isPointerType - Return true if this first class type is big enough to hold
23 bool isPointerType(const Type *Ty);
27 // LocalDataStructures - The analysis that computes the local data structure
28 // graphs for all of the functions in the program.
30 // FIXME: This should be a Function pass that can be USED by a Pass, and would
31 // be automatically preserved. Until we can do that, this is a Pass.
33 class LocalDataStructures : public Pass {
34 // DSInfo, one graph for each function
35 std::map<const Function*, DSGraph*> DSInfo;
36 DSGraph *GlobalsGraph;
38 ~LocalDataStructures() { releaseMemory(); }
40 virtual bool run(Module &M);
42 bool hasGraph(const Function &F) const {
43 return DSInfo.find(&F) != DSInfo.end();
46 // getDSGraph - Return the data structure graph for the specified function.
47 DSGraph &getDSGraph(const Function &F) const {
48 std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
49 assert(I != DSInfo.end() && "Function not in module!");
53 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
55 // print - Print out the analysis results...
56 void print(std::ostream &O, const Module *M) const;
58 // If the pass pipeline is done with this pass, we can release our memory...
59 virtual void releaseMemory();
61 // getAnalysisUsage - This obviously provides a data structure graph.
62 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
68 // BUDataStructures - The analysis that computes the interprocedurally closed
69 // data structure graphs for all of the functions in the program. This pass
70 // only performs a "Bottom Up" propagation (hence the name).
72 class BUDataStructures : public Pass {
73 // DSInfo, one graph for each function
74 std::map<const Function*, DSGraph*> DSInfo;
75 DSGraph *GlobalsGraph;
77 ~BUDataStructures() { releaseMemory(); }
79 virtual bool run(Module &M);
81 bool hasGraph(const Function &F) const {
82 return DSInfo.find(&F) != DSInfo.end();
85 // getDSGraph - Return the data structure graph for the specified function.
86 DSGraph &getDSGraph(const Function &F) const {
87 std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
88 assert(I != DSInfo.end() && "Function not in module!");
92 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
94 // print - Print out the analysis results...
95 void print(std::ostream &O, const Module *M) const;
97 // If the pass pipeline is done with this pass, we can release our memory...
98 virtual void releaseMemory();
100 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
101 AU.setPreservesAll();
102 AU.addRequired<LocalDataStructures>();
105 DSGraph &calculateGraph(Function &F);
107 // inlineNonSCCGraphs - This method is almost like the other two calculate
108 // graph methods. This one is used to inline function graphs (from functions
109 // outside of the SCC) into functions in the SCC. It is not supposed to touch
110 // functions IN the SCC at all.
112 DSGraph &BUDataStructures::inlineNonSCCGraphs(Function &F,
113 std::set<Function*> &SCCFunctions);
115 DSGraph &calculateSCCGraph(Function &F,
116 std::set<Function*> &InlinedSCCFunctions);
117 void calculateReachableGraphs(Function *F);
120 DSGraph &getOrCreateGraph(Function *F);
122 unsigned calculateGraphs(Function *F, std::vector<Function*> &Stack,
124 std::map<Function*, unsigned> &ValMap);
128 // TDDataStructures - Analysis that computes new data structure graphs
129 // for each function using the closed graphs for the callers computed
130 // by the bottom-up pass.
132 class TDDataStructures : public Pass {
133 // DSInfo, one graph for each function
134 std::map<const Function*, DSGraph*> DSInfo;
135 std::set<const Function*> GraphDone;
136 DSGraph *GlobalsGraph;
138 ~TDDataStructures() { releaseMemory(); }
140 virtual bool run(Module &M);
142 bool hasGraph(const Function &F) const {
143 return DSInfo.find(&F) != DSInfo.end();
146 // getDSGraph - Return the data structure graph for the specified function.
147 DSGraph &getDSGraph(const Function &F) const {
148 std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
149 assert(I != DSInfo.end() && "Function not in module!");
153 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
155 // print - Print out the analysis results...
156 void print(std::ostream &O, const Module *M) const;
158 // If the pass pipeline is done with this pass, we can release our memory...
159 virtual void releaseMemory();
161 // getAnalysisUsage - This obviously provides a data structure graph.
162 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
163 AU.setPreservesAll();
164 AU.addRequired<BUDataStructures>();
167 void calculateGraph(Function &F);
168 DSGraph &getOrCreateDSGraph(Function &F);
170 void ResolveCallSite(DSGraph &Graph, const DSCallSite &CallSite);