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<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(const_cast<Function*>(&F)) != DSInfo.end();
47 // getDSGraph - Return the data structure graph for the specified function.
48 DSGraph &getDSGraph(const Function &F) const {
49 hash_map<Function*, DSGraph*>::const_iterator I =
50 DSInfo.find(const_cast<Function*>(&F));
51 assert(I != DSInfo.end() && "Function not in module!");
55 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
57 // print - Print out the analysis results...
58 void print(std::ostream &O, const Module *M) const;
60 // If the pass pipeline is done with this pass, we can release our memory...
61 virtual void releaseMemory();
63 // getAnalysisUsage - This obviously provides a data structure graph.
64 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
70 // BUDataStructures - The analysis that computes the interprocedurally closed
71 // data structure graphs for all of the functions in the program. This pass
72 // only performs a "Bottom Up" propagation (hence the name).
74 class BUDataStructures : public Pass {
75 // DSInfo, one graph for each function
76 hash_map<Function*, DSGraph*> DSInfo;
77 DSGraph *GlobalsGraph;
79 ~BUDataStructures() { releaseMemory(); }
81 virtual bool run(Module &M);
83 bool hasGraph(const Function &F) const {
84 return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
87 // getDSGraph - Return the data structure graph for the specified function.
88 DSGraph &getDSGraph(const Function &F) const {
89 hash_map<Function*, DSGraph*>::const_iterator I =
90 DSInfo.find(const_cast<Function*>(&F));
91 assert(I != DSInfo.end() && "Function not in module!");
95 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
97 // print - Print out the analysis results...
98 void print(std::ostream &O, const Module *M) const;
100 // If the pass pipeline is done with this pass, we can release our memory...
101 virtual void releaseMemory();
103 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
104 AU.setPreservesAll();
105 AU.addRequired<LocalDataStructures>();
108 void calculateGraph(DSGraph &G);
110 // inlineNonSCCGraphs - This method is almost like the other two calculate
111 // graph methods. This one is used to inline function graphs (from functions
112 // outside of the SCC) into functions in the SCC. It is not supposed to touch
113 // functions IN the SCC at all.
115 DSGraph &inlineNonSCCGraphs(Function &F,
116 hash_set<Function*> &SCCFunctions);
118 DSGraph &calculateSCCGraph(Function &F,
119 hash_set<Function*> &InlinedSCCFunctions);
120 void calculateReachableGraphs(Function *F);
123 DSGraph &getOrCreateGraph(Function *F);
125 unsigned calculateGraphs(Function *F, std::vector<Function*> &Stack,
127 hash_map<Function*, unsigned> &ValMap);
131 // TDDataStructures - Analysis that computes new data structure graphs
132 // for each function using the closed graphs for the callers computed
133 // by the bottom-up pass.
135 class TDDataStructures : public Pass {
136 // DSInfo, one graph for each function
137 hash_map<Function*, DSGraph*> DSInfo;
138 hash_set<const Function*> GraphDone;
139 DSGraph *GlobalsGraph;
141 ~TDDataStructures() { releaseMyMemory(); }
143 virtual bool run(Module &M);
145 bool hasGraph(const Function &F) const {
146 return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
149 // getDSGraph - Return the data structure graph for the specified function.
150 DSGraph &getDSGraph(const Function &F) const {
151 hash_map<Function*, DSGraph*>::const_iterator I =
152 DSInfo.find(const_cast<Function*>(&F));
153 assert(I != DSInfo.end() && "Function not in module!");
157 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
159 // print - Print out the analysis results...
160 void print(std::ostream &O, const Module *M) const;
162 // If the pass pipeline is done with this pass, we can release our memory...
163 virtual void releaseMyMemory();
165 // getAnalysisUsage - This obviously provides a data structure graph.
166 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
167 AU.setPreservesAll();
168 AU.addRequired<BUDataStructures>();
172 void calculateGraph(Function &F);
173 DSGraph &getOrCreateDSGraph(Function &F);