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"
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 hash_map<Function*, DSGraph*> DSInfo;
38 DSGraph *GlobalsGraph;
40 ~LocalDataStructures() { releaseMemory(); }
42 virtual bool run(Module &M);
44 bool hasGraph(const Function &F) const {
45 return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
48 // getDSGraph - Return the data structure graph for the specified function.
49 DSGraph &getDSGraph(const Function &F) const {
50 hash_map<Function*, DSGraph*>::const_iterator I =
51 DSInfo.find(const_cast<Function*>(&F));
52 assert(I != DSInfo.end() && "Function not in module!");
56 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
58 // print - Print out the analysis results...
59 void print(std::ostream &O, const Module *M) const;
61 // If the pass pipeline is done with this pass, we can release our memory...
62 virtual void releaseMemory();
64 // getAnalysisUsage - This obviously provides a data structure graph.
65 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
71 // BUDataStructures - The analysis that computes the interprocedurally closed
72 // data structure graphs for all of the functions in the program. This pass
73 // only performs a "Bottom Up" propagation (hence the name).
75 class BUDataStructures : public Pass {
76 // DSInfo, one graph for each function
77 hash_map<Function*, DSGraph*> DSInfo;
78 DSGraph *GlobalsGraph;
79 hash_multimap<CallInst*, Function*> ActualCallees;
81 ~BUDataStructures() { releaseMemory(); }
83 virtual bool run(Module &M);
85 bool hasGraph(const Function &F) const {
86 return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
89 // getDSGraph - Return the data structure graph for the specified function.
90 DSGraph &getDSGraph(const Function &F) const {
91 hash_map<Function*, DSGraph*>::const_iterator I =
92 DSInfo.find(const_cast<Function*>(&F));
93 assert(I != DSInfo.end() && "Function not in module!");
97 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
99 // print - Print out the analysis results...
100 void print(std::ostream &O, const Module *M) const;
102 // If the pass pipeline is done with this pass, we can release our memory...
103 virtual void releaseMemory();
105 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
106 AU.setPreservesAll();
107 AU.addRequired<LocalDataStructures>();
110 typedef hash_multimap<CallInst*, Function*> ActualCalleesTy;
111 const ActualCalleesTy &getActualCallees() const {
112 return ActualCallees;
116 void calculateGraph(DSGraph &G);
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<Function*, DSGraph*> DSInfo;
136 hash_set<Function*> ArgsRemainIncomplete;
137 DSGraph *GlobalsGraph;
139 ~TDDataStructures() { releaseMyMemory(); }
141 virtual bool run(Module &M);
143 bool hasGraph(const Function &F) const {
144 return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
147 // getDSGraph - Return the data structure graph for the specified function.
148 DSGraph &getDSGraph(const Function &F) const {
149 hash_map<Function*, DSGraph*>::const_iterator I =
150 DSInfo.find(const_cast<Function*>(&F));
151 assert(I != DSInfo.end() && "Function not in module!");
155 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
157 // print - Print out the analysis results...
158 void print(std::ostream &O, const Module *M) const;
160 // If the pass pipeline is done with this pass, we can release our memory...
161 virtual void releaseMyMemory();
163 // getAnalysisUsage - This obviously provides a data structure graph.
164 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
165 AU.setPreservesAll();
166 AU.addRequired<BUDataStructures>();
170 void calculateGraphFrom(Function &F);
171 void inlineGraphIntoCallees(DSGraph &G);
172 DSGraph &getOrCreateDSGraph(Function &F);
173 void ComputePostOrder(Function &F, hash_set<DSGraph*> &Visited,
174 std::vector<DSGraph*> &PostOrder,
175 const BUDataStructures::ActualCalleesTy &ActualCallees);