1 //===- DataStructure.h - Build data structure graphs ------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Implement the LLVM data structure analysis library.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ANALYSIS_DATA_STRUCTURE_H
15 #define LLVM_ANALYSIS_DATA_STRUCTURE_H
17 #include "llvm/Pass.h"
18 #include "llvm/Target/TargetData.h"
19 #include "Support/hash_set"
28 // FIXME: move this stuff to a private header
29 namespace DataStructureAnalysis {
30 /// isPointerType - Return true if this first class type is big enough to hold
33 bool isPointerType(const Type *Ty);
37 // LocalDataStructures - The analysis that computes the local data structure
38 // graphs for all of the functions in the program.
40 // FIXME: This should be a Function pass that can be USED by a Pass, and would
41 // be automatically preserved. Until we can do that, this is a Pass.
43 class LocalDataStructures : public Pass {
44 // DSInfo, one graph for each function
45 hash_map<Function*, DSGraph*> DSInfo;
46 DSGraph *GlobalsGraph;
48 ~LocalDataStructures() { releaseMemory(); }
50 virtual bool run(Module &M);
52 bool hasGraph(const Function &F) const {
53 return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
56 /// getDSGraph - Return the data structure graph for the specified function.
58 DSGraph &getDSGraph(const Function &F) const {
59 hash_map<Function*, DSGraph*>::const_iterator I =
60 DSInfo.find(const_cast<Function*>(&F));
61 assert(I != DSInfo.end() && "Function not in module!");
65 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
67 /// print - Print out the analysis results...
69 void print(std::ostream &O, const Module *M) const;
71 /// releaseMemory - if the pass pipeline is done with this pass, we can
72 /// release our memory...
74 virtual void releaseMemory();
76 /// getAnalysisUsage - This obviously provides a data structure graph.
78 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
80 AU.addRequired<TargetData>();
85 /// BUDataStructures - The analysis that computes the interprocedurally closed
86 /// data structure graphs for all of the functions in the program. This pass
87 /// only performs a "Bottom Up" propagation (hence the name).
89 class BUDataStructures : public Pass {
91 // DSInfo, one graph for each function
92 hash_map<Function*, DSGraph*> DSInfo;
93 DSGraph *GlobalsGraph;
94 hash_multimap<Instruction*, Function*> ActualCallees;
96 ~BUDataStructures() { releaseMemory(); }
98 virtual bool run(Module &M);
100 bool hasGraph(const Function &F) const {
101 return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
104 /// getDSGraph - Return the data structure graph for the specified function.
106 DSGraph &getDSGraph(const Function &F) const {
107 hash_map<Function*, DSGraph*>::const_iterator I =
108 DSInfo.find(const_cast<Function*>(&F));
109 assert(I != DSInfo.end() && "Function not in module!");
113 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
115 /// print - Print out the analysis results...
117 void print(std::ostream &O, const Module *M) const;
119 /// releaseMemory - if the pass pipeline is done with this pass, we can
120 /// release our memory...
122 virtual void releaseMemory();
124 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
125 AU.setPreservesAll();
126 AU.addRequired<LocalDataStructures>();
129 typedef hash_multimap<Instruction*, Function*> ActualCalleesTy;
130 const ActualCalleesTy &getActualCallees() const {
131 return ActualCallees;
135 void calculateGraph(DSGraph &G);
137 void calculateReachableGraphs(Function *F);
140 DSGraph &getOrCreateGraph(Function *F);
142 unsigned calculateGraphs(Function *F, std::vector<Function*> &Stack,
144 hash_map<Function*, unsigned> &ValMap);
148 /// TDDataStructures - Analysis that computes new data structure graphs
149 /// for each function using the closed graphs for the callers computed
150 /// by the bottom-up pass.
152 class TDDataStructures : public Pass {
153 // DSInfo, one graph for each function
154 hash_map<Function*, DSGraph*> DSInfo;
155 hash_set<Function*> ArgsRemainIncomplete;
156 DSGraph *GlobalsGraph;
158 ~TDDataStructures() { releaseMyMemory(); }
160 virtual bool run(Module &M);
162 bool hasGraph(const Function &F) const {
163 return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
166 /// getDSGraph - Return the data structure graph for the specified function.
168 DSGraph &getDSGraph(const Function &F) const {
169 hash_map<Function*, DSGraph*>::const_iterator I =
170 DSInfo.find(const_cast<Function*>(&F));
171 assert(I != DSInfo.end() && "Function not in module!");
175 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
177 /// print - Print out the analysis results...
179 void print(std::ostream &O, const Module *M) const;
181 /// If the pass pipeline is done with this pass, we can release our memory...
183 virtual void releaseMyMemory();
185 /// getAnalysisUsage - This obviously provides a data structure graph.
187 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
188 AU.setPreservesAll();
189 AU.addRequired<BUDataStructures>();
193 void markReachableFunctionsExternallyAccessible(DSNode *N,
194 hash_set<DSNode*> &Visited);
196 void inlineGraphIntoCallees(DSGraph &G);
197 DSGraph &getOrCreateDSGraph(Function &F);
198 void ComputePostOrder(Function &F, hash_set<DSGraph*> &Visited,
199 std::vector<DSGraph*> &PostOrder,
200 const BUDataStructures::ActualCalleesTy &ActualCallees);
204 /// CompleteBUDataStructures - This is the exact same as the bottom-up graphs,
205 /// but we use take a completed call graph and inline all indirect callees into
206 /// their callers graphs, making the result more useful for things like pool
209 struct CompleteBUDataStructures : public BUDataStructures {
210 virtual bool run(Module &M);
212 bool hasGraph(const Function &F) const {
213 return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
216 /// getDSGraph - Return the data structure graph for the specified function.
218 DSGraph &getDSGraph(const Function &F) const {
219 hash_map<Function*, DSGraph*>::const_iterator I =
220 DSInfo.find(const_cast<Function*>(&F));
221 assert(I != DSInfo.end() && "Function not in module!");
225 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
226 AU.setPreservesAll();
227 AU.addRequired<BUDataStructures>();
229 // FIXME: TEMPORARY (remove once finalization of indirect call sites in the
230 // globals graph has been implemented in the BU pass)
231 AU.addRequired<TDDataStructures>();
234 /// print - Print out the analysis results...
236 void print(std::ostream &O, const Module *M) const;
239 unsigned calculateSCCGraphs(DSGraph &FG, std::vector<DSGraph*> &Stack,
241 hash_map<DSGraph*, unsigned> &ValMap);
242 DSGraph &getOrCreateGraph(Function &F);
243 void processGraph(DSGraph &G);
246 } // End llvm namespace