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.
57 DSGraph &getDSGraph(const Function &F) const {
58 hash_map<Function*, DSGraph*>::const_iterator I =
59 DSInfo.find(const_cast<Function*>(&F));
60 assert(I != DSInfo.end() && "Function not in module!");
64 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
66 // print - Print out the analysis results...
67 void print(std::ostream &O, const Module *M) const;
69 // If the pass pipeline is done with this pass, we can release our memory...
70 virtual void releaseMemory();
72 // getAnalysisUsage - This obviously provides a data structure graph.
73 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
75 AU.addRequired<TargetData>();
80 // BUDataStructures - The analysis that computes the interprocedurally closed
81 // data structure graphs for all of the functions in the program. This pass
82 // only performs a "Bottom Up" propagation (hence the name).
84 class BUDataStructures : public Pass {
86 // DSInfo, one graph for each function
87 hash_map<Function*, DSGraph*> DSInfo;
88 DSGraph *GlobalsGraph;
89 hash_multimap<Instruction*, Function*> ActualCallees;
91 ~BUDataStructures() { releaseMemory(); }
93 virtual bool run(Module &M);
95 bool hasGraph(const Function &F) const {
96 return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
99 // getDSGraph - Return the data structure graph for the specified function.
100 DSGraph &getDSGraph(const Function &F) const {
101 hash_map<Function*, DSGraph*>::const_iterator I =
102 DSInfo.find(const_cast<Function*>(&F));
103 assert(I != DSInfo.end() && "Function not in module!");
107 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
109 // print - Print out the analysis results...
110 void print(std::ostream &O, const Module *M) const;
112 // If the pass pipeline is done with this pass, we can release our memory...
113 virtual void releaseMemory();
115 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
116 AU.setPreservesAll();
117 AU.addRequired<LocalDataStructures>();
120 typedef hash_multimap<Instruction*, Function*> ActualCalleesTy;
121 const ActualCalleesTy &getActualCallees() const {
122 return ActualCallees;
126 void calculateGraph(DSGraph &G);
128 void calculateReachableGraphs(Function *F);
131 DSGraph &getOrCreateGraph(Function *F);
133 unsigned calculateGraphs(Function *F, std::vector<Function*> &Stack,
135 hash_map<Function*, unsigned> &ValMap);
139 // TDDataStructures - Analysis that computes new data structure graphs
140 // for each function using the closed graphs for the callers computed
141 // by the bottom-up pass.
143 class TDDataStructures : public Pass {
144 // DSInfo, one graph for each function
145 hash_map<Function*, DSGraph*> DSInfo;
146 hash_set<Function*> ArgsRemainIncomplete;
147 DSGraph *GlobalsGraph;
149 ~TDDataStructures() { releaseMyMemory(); }
151 virtual bool run(Module &M);
153 bool hasGraph(const Function &F) const {
154 return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
157 // getDSGraph - Return the data structure graph for the specified function.
158 DSGraph &getDSGraph(const Function &F) const {
159 hash_map<Function*, DSGraph*>::const_iterator I =
160 DSInfo.find(const_cast<Function*>(&F));
161 assert(I != DSInfo.end() && "Function not in module!");
165 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
167 // print - Print out the analysis results...
168 void print(std::ostream &O, const Module *M) const;
170 // If the pass pipeline is done with this pass, we can release our memory...
171 virtual void releaseMyMemory();
173 // getAnalysisUsage - This obviously provides a data structure graph.
174 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
175 AU.setPreservesAll();
176 AU.addRequired<BUDataStructures>();
180 void markReachableFunctionsExternallyAccessible(DSNode *N,
181 hash_set<DSNode*> &Visited);
183 void inlineGraphIntoCallees(DSGraph &G);
184 DSGraph &getOrCreateDSGraph(Function &F);
185 void ComputePostOrder(Function &F, hash_set<DSGraph*> &Visited,
186 std::vector<DSGraph*> &PostOrder,
187 const BUDataStructures::ActualCalleesTy &ActualCallees);
191 // CompleteBUDataStructures - This is the exact same as the bottom-up graphs,
192 // but we use take a completed call graph and inline all indirect callees into
193 // their callers graphs, making the result more useful for things like pool
196 struct CompleteBUDataStructures : public BUDataStructures {
197 virtual bool run(Module &M);
199 bool hasGraph(const Function &F) const {
200 return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
203 // getDSGraph - Return the data structure graph for the specified function.
204 DSGraph &getDSGraph(const Function &F) const {
205 hash_map<Function*, DSGraph*>::const_iterator I =
206 DSInfo.find(const_cast<Function*>(&F));
207 assert(I != DSInfo.end() && "Function not in module!");
211 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
212 AU.setPreservesAll();
213 AU.addRequired<BUDataStructures>();
215 // FIXME: TEMPORARY (remove once finalization of indirect call sites in the
216 // globals graph has been implemented in the BU pass)
217 AU.addRequired<TDDataStructures>();
223 } // End llvm namespace