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 "llvm/ADT/hash_map"
20 #include "llvm/ADT/hash_set"
21 #include "llvm/ADT/EquivalenceClasses.h"
34 FunctionPass *createDataStructureStatsPass();
35 FunctionPass *createDataStructureGraphCheckerPass();
38 // FIXME: move this stuff to a private header
39 namespace DataStructureAnalysis {
40 /// isPointerType - Return true if this first class type is big enough to hold
43 bool isPointerType(const Type *Ty);
47 // LocalDataStructures - The analysis that computes the local data structure
48 // graphs for all of the functions in the program.
50 // FIXME: This should be a Function pass that can be USED by a Pass, and would
51 // be automatically preserved. Until we can do that, this is a Pass.
53 class LocalDataStructures : public ModulePass {
54 // DSInfo, one graph for each function
55 hash_map<Function*, DSGraph*> DSInfo;
56 DSGraph *GlobalsGraph;
58 /// GlobalECs - The equivalence classes for each global value that is merged
59 /// with other global values in the DSGraphs.
60 EquivalenceClasses<GlobalValue*> GlobalECs;
62 ~LocalDataStructures() { releaseMemory(); }
64 virtual bool runOnModule(Module &M);
66 bool hasGraph(const Function &F) const {
67 return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
70 /// getDSGraph - Return the data structure graph for the specified function.
72 DSGraph &getDSGraph(const Function &F) const {
73 hash_map<Function*, DSGraph*>::const_iterator I =
74 DSInfo.find(const_cast<Function*>(&F));
75 assert(I != DSInfo.end() && "Function not in module!");
79 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
81 EquivalenceClasses<GlobalValue*> &getGlobalECs() { return GlobalECs; }
83 /// print - Print out the analysis results...
85 void print(std::ostream &O, const Module *M) const;
87 /// releaseMemory - if the pass pipeline is done with this pass, we can
88 /// release our memory...
90 virtual void releaseMemory();
92 /// getAnalysisUsage - This obviously provides a data structure graph.
94 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
96 AU.addRequired<TargetData>();
101 /// BUDataStructures - The analysis that computes the interprocedurally closed
102 /// data structure graphs for all of the functions in the program. This pass
103 /// only performs a "Bottom Up" propagation (hence the name).
105 class BUDataStructures : public ModulePass {
107 // DSInfo, one graph for each function
108 hash_map<Function*, DSGraph*> DSInfo;
109 DSGraph *GlobalsGraph;
110 std::set<std::pair<Instruction*, Function*> > ActualCallees;
112 // This map is only maintained during construction of BU Graphs
113 std::map<std::vector<Function*>,
114 std::pair<DSGraph*, std::vector<DSNodeHandle> > > *IndCallGraphMap;
116 /// GlobalECs - The equivalence classes for each global value that is merged
117 /// with other global values in the DSGraphs.
118 EquivalenceClasses<GlobalValue*> GlobalECs;
120 ~BUDataStructures() { releaseMyMemory(); }
122 virtual bool runOnModule(Module &M);
124 bool hasGraph(const Function &F) const {
125 return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
128 /// getDSGraph - Return the data structure graph for the specified function.
130 DSGraph &getDSGraph(const Function &F) const {
131 hash_map<Function*, DSGraph*>::const_iterator I =
132 DSInfo.find(const_cast<Function*>(&F));
133 if (I != DSInfo.end())
135 return const_cast<BUDataStructures*>(this)->
136 CreateGraphForExternalFunction(F);
139 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
141 EquivalenceClasses<GlobalValue*> &getGlobalECs() { return GlobalECs; }
143 DSGraph &CreateGraphForExternalFunction(const Function &F);
145 /// deleteValue/copyValue - Interfaces to update the DSGraphs in the program.
146 /// These correspond to the interfaces defined in the AliasAnalysis class.
147 void deleteValue(Value *V);
148 void copyValue(Value *From, Value *To);
150 /// print - Print out the analysis results...
152 void print(std::ostream &O, const Module *M) const;
154 // FIXME: Once the pass manager is straightened out, rename this to
156 void releaseMyMemory();
158 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
159 AU.setPreservesAll();
160 AU.addRequired<LocalDataStructures>();
163 typedef std::set<std::pair<Instruction*, Function*> > ActualCalleesTy;
164 const ActualCalleesTy &getActualCallees() const {
165 return ActualCallees;
168 typedef ActualCalleesTy::const_iterator callee_iterator;
169 callee_iterator callee_begin(Instruction *I) const {
170 return ActualCallees.lower_bound(std::pair<Instruction*,Function*>(I, 0));
173 callee_iterator callee_end(Instruction *I) const {
174 I = (Instruction*)((char*)I + 1);
175 return ActualCallees.lower_bound(std::pair<Instruction*,Function*>(I, 0));
179 void calculateGraph(DSGraph &G);
181 DSGraph &getOrCreateGraph(Function *F);
183 unsigned calculateGraphs(Function *F, std::vector<Function*> &Stack,
185 hash_map<Function*, unsigned> &ValMap);
189 /// TDDataStructures - Analysis that computes new data structure graphs
190 /// for each function using the closed graphs for the callers computed
191 /// by the bottom-up pass.
193 class TDDataStructures : public ModulePass {
194 // DSInfo, one graph for each function
195 hash_map<Function*, DSGraph*> DSInfo;
196 hash_set<Function*> ArgsRemainIncomplete;
197 DSGraph *GlobalsGraph;
198 BUDataStructures *BUInfo;
200 /// GlobalECs - The equivalence classes for each global value that is merged
201 /// with other global values in the DSGraphs.
202 EquivalenceClasses<GlobalValue*> GlobalECs;
204 /// CallerCallEdges - For a particular graph, we keep a list of these records
205 /// which indicates which graphs call this function and from where.
206 struct CallerCallEdge {
207 DSGraph *CallerGraph; // The graph of the caller function.
208 const DSCallSite *CS; // The actual call site.
209 Function *CalledFunction; // The actual function being called.
211 CallerCallEdge(DSGraph *G, const DSCallSite *cs, Function *CF)
212 : CallerGraph(G), CS(cs), CalledFunction(CF) {}
214 bool operator<(const CallerCallEdge &RHS) const {
215 return CallerGraph < RHS.CallerGraph ||
216 (CallerGraph == RHS.CallerGraph && CS < RHS.CS);
220 std::map<DSGraph*, std::vector<CallerCallEdge> > CallerEdges;
223 // IndCallMap - We memoize the results of indirect call inlining operations
224 // that have multiple targets here to avoid N*M inlining. The key to the map
225 // is a sorted set of callee functions, the value is the DSGraph that holds
226 // all of the caller graphs merged together, and the DSCallSite to merge with
227 // the arguments for each function.
228 std::map<std::vector<Function*>, DSGraph*> IndCallMap;
231 ~TDDataStructures() { releaseMyMemory(); }
233 virtual bool runOnModule(Module &M);
235 bool hasGraph(const Function &F) const {
236 return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
239 /// getDSGraph - Return the data structure graph for the specified function.
241 DSGraph &getDSGraph(const Function &F) const {
242 hash_map<Function*, DSGraph*>::const_iterator I =
243 DSInfo.find(const_cast<Function*>(&F));
244 if (I != DSInfo.end()) return *I->second;
245 return const_cast<TDDataStructures*>(this)->
246 getOrCreateDSGraph(const_cast<Function&>(F));
249 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
250 EquivalenceClasses<GlobalValue*> &getGlobalECs() { return GlobalECs; }
253 /// deleteValue/copyValue - Interfaces to update the DSGraphs in the program.
254 /// These correspond to the interfaces defined in the AliasAnalysis class.
255 void deleteValue(Value *V);
256 void copyValue(Value *From, Value *To);
258 /// print - Print out the analysis results...
260 void print(std::ostream &O, const Module *M) const;
262 /// If the pass pipeline is done with this pass, we can release our memory...
264 virtual void releaseMyMemory();
266 /// getAnalysisUsage - This obviously provides a data structure graph.
268 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
269 AU.setPreservesAll();
270 AU.addRequired<BUDataStructures>();
274 void markReachableFunctionsExternallyAccessible(DSNode *N,
275 hash_set<DSNode*> &Visited);
277 void InlineCallersIntoGraph(DSGraph &G);
278 DSGraph &getOrCreateDSGraph(Function &F);
279 void ComputePostOrder(Function &F, hash_set<DSGraph*> &Visited,
280 std::vector<DSGraph*> &PostOrder);
284 /// CompleteBUDataStructures - This is the exact same as the bottom-up graphs,
285 /// but we use take a completed call graph and inline all indirect callees into
286 /// their callers graphs, making the result more useful for things like pool
289 struct CompleteBUDataStructures : public BUDataStructures {
290 virtual bool runOnModule(Module &M);
292 bool hasGraph(const Function &F) const {
293 return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
296 /// getDSGraph - Return the data structure graph for the specified function.
298 DSGraph &getDSGraph(const Function &F) const {
299 hash_map<Function*, DSGraph*>::const_iterator I =
300 DSInfo.find(const_cast<Function*>(&F));
301 assert(I != DSInfo.end() && "Function not in module!");
305 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
306 AU.setPreservesAll();
307 AU.addRequired<BUDataStructures>();
309 // FIXME: TEMPORARY (remove once finalization of indirect call sites in the
310 // globals graph has been implemented in the BU pass)
311 AU.addRequired<TDDataStructures>();
314 /// print - Print out the analysis results...
316 void print(std::ostream &O, const Module *M) const;
319 unsigned calculateSCCGraphs(DSGraph &FG, std::vector<DSGraph*> &Stack,
321 hash_map<DSGraph*, unsigned> &ValMap);
322 DSGraph &getOrCreateGraph(Function &F);
323 void processGraph(DSGraph &G);
327 /// EquivClassGraphs - This is the same as the complete bottom-up graphs, but
328 /// with functions partitioned into equivalence classes and a single merged
329 /// DS graph for all functions in an equivalence class. After this merging,
330 /// graphs are inlined bottom-up on the SCCs of the final (CBU) call graph.
332 struct EquivClassGraphs : public ModulePass {
333 CompleteBUDataStructures *CBU;
335 DSGraph *GlobalsGraph;
337 // DSInfo - one graph for each function.
338 hash_map<const Function*, DSGraph*> DSInfo;
340 /// ActualCallees - The actual functions callable from indirect call sites.
342 std::set<std::pair<Instruction*, Function*> > ActualCallees;
344 // Equivalence class where functions that can potentially be called via the
345 // same function pointer are in the same class.
346 EquivalenceClasses<Function*> FuncECs;
348 /// OneCalledFunction - For each indirect call, we keep track of one
349 /// target of the call. This is used to find equivalence class called by
351 std::map<DSNode*, Function *> OneCalledFunction;
353 /// GlobalECs - The equivalence classes for each global value that is merged
354 /// with other global values in the DSGraphs.
355 EquivalenceClasses<GlobalValue*> GlobalECs;
358 /// EquivClassGraphs - Computes the equivalence classes and then the
359 /// folded DS graphs for each class.
361 virtual bool runOnModule(Module &M);
363 /// print - Print out the analysis results...
365 void print(std::ostream &O, const Module *M) const;
367 EquivalenceClasses<GlobalValue*> &getGlobalECs() { return GlobalECs; }
369 /// getDSGraph - Return the data structure graph for the specified function.
370 /// This returns the folded graph. The folded graph is the same as the CBU
371 /// graph iff the function is in a singleton equivalence class AND all its
372 /// callees also have the same folded graph as the CBU graph.
374 DSGraph &getDSGraph(const Function &F) const {
375 hash_map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
376 assert(I != DSInfo.end() && "No graph computed for that function!");
380 bool hasGraph(const Function &F) const {
381 return DSInfo.find(&F) != DSInfo.end();
384 /// ContainsDSGraphFor - Return true if we have a graph for the specified
386 bool ContainsDSGraphFor(const Function &F) const {
387 return DSInfo.find(&F) != DSInfo.end();
390 /// getSomeCalleeForCallSite - Return any one callee function at
393 Function *getSomeCalleeForCallSite(const CallSite &CS) const;
395 DSGraph &getGlobalsGraph() const {
396 return *GlobalsGraph;
399 typedef std::set<std::pair<Instruction*, Function*> > ActualCalleesTy;
400 const ActualCalleesTy &getActualCallees() const {
401 return ActualCallees;
404 typedef ActualCalleesTy::const_iterator callee_iterator;
405 callee_iterator callee_begin(Instruction *I) const {
406 return ActualCallees.lower_bound(std::pair<Instruction*,Function*>(I, 0));
409 callee_iterator callee_end(Instruction *I) const {
410 I = (Instruction*)((char*)I + 1);
411 return ActualCallees.lower_bound(std::pair<Instruction*,Function*>(I, 0));
414 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
415 AU.setPreservesAll();
416 AU.addRequired<CompleteBUDataStructures>();
420 void buildIndirectFunctionSets(Module &M);
422 unsigned processSCC(DSGraph &FG, std::vector<DSGraph*> &Stack,
424 std::map<DSGraph*, unsigned> &ValMap);
425 void processGraph(DSGraph &FG);
427 DSGraph &getOrCreateGraph(Function &F);
430 } // End llvm namespace