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/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;
78 hash_multimap<CallInst*, Function*> ActualCallees;
80 ~BUDataStructures() { releaseMemory(); }
82 virtual bool run(Module &M);
84 bool hasGraph(const Function &F) const {
85 return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
88 // getDSGraph - Return the data structure graph for the specified function.
89 DSGraph &getDSGraph(const Function &F) const {
90 hash_map<Function*, DSGraph*>::const_iterator I =
91 DSInfo.find(const_cast<Function*>(&F));
92 assert(I != DSInfo.end() && "Function not in module!");
96 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
98 // print - Print out the analysis results...
99 void print(std::ostream &O, const Module *M) const;
101 // If the pass pipeline is done with this pass, we can release our memory...
102 virtual void releaseMemory();
104 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
105 AU.setPreservesAll();
106 AU.addRequired<LocalDataStructures>();
109 typedef hash_multimap<CallInst*, Function*> ActualCalleesTy;
110 const ActualCalleesTy &getActualCallees() const {
111 return ActualCallees;
115 void calculateGraph(DSGraph &G);
117 void calculateReachableGraphs(Function *F);
120 DSGraph &getOrCreateGraph(Function *F);
122 unsigned calculateGraphs(Function *F, std::vector<Function*> &Stack,
124 hash_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 hash_map<Function*, DSGraph*> DSInfo;
135 hash_set<Function*> ArgsRemainIncomplete;
136 DSGraph *GlobalsGraph;
138 ~TDDataStructures() { releaseMyMemory(); }
140 virtual bool run(Module &M);
142 bool hasGraph(const Function &F) const {
143 return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
146 // getDSGraph - Return the data structure graph for the specified function.
147 DSGraph &getDSGraph(const Function &F) const {
148 hash_map<Function*, DSGraph*>::const_iterator I =
149 DSInfo.find(const_cast<Function*>(&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 inlineGraphIntoCallees(DSGraph &G);
170 DSGraph &getOrCreateDSGraph(Function &F);
171 void ComputePostOrder(Function &F, hash_set<DSGraph*> &Visited,
172 std::vector<DSGraph*> &PostOrder,
173 const BUDataStructures::ActualCalleesTy &ActualCallees);