LLVM API Documentation
00001 //===- DataStructure.h - Build data structure graphs ------------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // Implement the LLVM data structure analysis library. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #ifndef LLVM_ANALYSIS_DATA_STRUCTURE_H 00015 #define LLVM_ANALYSIS_DATA_STRUCTURE_H 00016 00017 #include "llvm/Pass.h" 00018 #include "llvm/Target/TargetData.h" 00019 #include "llvm/ADT/hash_set" 00020 00021 namespace llvm { 00022 00023 class Type; 00024 class Instruction; 00025 class DSGraph; 00026 class DSNode; 00027 00028 // FIXME: move this stuff to a private header 00029 namespace DataStructureAnalysis { 00030 /// isPointerType - Return true if this first class type is big enough to hold 00031 /// a pointer. 00032 /// 00033 bool isPointerType(const Type *Ty); 00034 } 00035 00036 00037 // LocalDataStructures - The analysis that computes the local data structure 00038 // graphs for all of the functions in the program. 00039 // 00040 // FIXME: This should be a Function pass that can be USED by a Pass, and would 00041 // be automatically preserved. Until we can do that, this is a Pass. 00042 // 00043 class LocalDataStructures : public ModulePass { 00044 // DSInfo, one graph for each function 00045 hash_map<Function*, DSGraph*> DSInfo; 00046 DSGraph *GlobalsGraph; 00047 public: 00048 ~LocalDataStructures() { releaseMemory(); } 00049 00050 virtual bool runOnModule(Module &M); 00051 00052 bool hasGraph(const Function &F) const { 00053 return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end(); 00054 } 00055 00056 /// getDSGraph - Return the data structure graph for the specified function. 00057 /// 00058 DSGraph &getDSGraph(const Function &F) const { 00059 hash_map<Function*, DSGraph*>::const_iterator I = 00060 DSInfo.find(const_cast<Function*>(&F)); 00061 assert(I != DSInfo.end() && "Function not in module!"); 00062 return *I->second; 00063 } 00064 00065 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; } 00066 00067 /// print - Print out the analysis results... 00068 /// 00069 void print(std::ostream &O, const Module *M) const; 00070 00071 /// releaseMemory - if the pass pipeline is done with this pass, we can 00072 /// release our memory... 00073 /// 00074 virtual void releaseMemory(); 00075 00076 /// getAnalysisUsage - This obviously provides a data structure graph. 00077 /// 00078 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00079 AU.setPreservesAll(); 00080 AU.addRequired<TargetData>(); 00081 } 00082 }; 00083 00084 00085 /// BUDataStructures - The analysis that computes the interprocedurally closed 00086 /// data structure graphs for all of the functions in the program. This pass 00087 /// only performs a "Bottom Up" propagation (hence the name). 00088 /// 00089 class BUDataStructures : public ModulePass { 00090 protected: 00091 // DSInfo, one graph for each function 00092 hash_map<Function*, DSGraph*> DSInfo; 00093 DSGraph *GlobalsGraph; 00094 hash_multimap<Instruction*, Function*> ActualCallees; 00095 public: 00096 ~BUDataStructures() { releaseMemory(); } 00097 00098 virtual bool runOnModule(Module &M); 00099 00100 bool hasGraph(const Function &F) const { 00101 return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end(); 00102 } 00103 00104 /// getDSGraph - Return the data structure graph for the specified function. 00105 /// 00106 DSGraph &getDSGraph(const Function &F) const { 00107 hash_map<Function*, DSGraph*>::const_iterator I = 00108 DSInfo.find(const_cast<Function*>(&F)); 00109 assert(I != DSInfo.end() && "Function not in module!"); 00110 return *I->second; 00111 } 00112 00113 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; } 00114 00115 /// print - Print out the analysis results... 00116 /// 00117 void print(std::ostream &O, const Module *M) const; 00118 00119 /// releaseMemory - if the pass pipeline is done with this pass, we can 00120 /// release our memory... 00121 /// 00122 virtual void releaseMemory(); 00123 00124 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00125 AU.setPreservesAll(); 00126 AU.addRequired<LocalDataStructures>(); 00127 } 00128 00129 typedef hash_multimap<Instruction*, Function*> ActualCalleesTy; 00130 const ActualCalleesTy &getActualCallees() const { 00131 return ActualCallees; 00132 } 00133 00134 private: 00135 void calculateGraph(DSGraph &G); 00136 00137 void calculateReachableGraphs(Function *F); 00138 00139 00140 DSGraph &getOrCreateGraph(Function *F); 00141 00142 unsigned calculateGraphs(Function *F, std::vector<Function*> &Stack, 00143 unsigned &NextID, 00144 hash_map<Function*, unsigned> &ValMap); 00145 }; 00146 00147 00148 /// TDDataStructures - Analysis that computes new data structure graphs 00149 /// for each function using the closed graphs for the callers computed 00150 /// by the bottom-up pass. 00151 /// 00152 class TDDataStructures : public ModulePass { 00153 // DSInfo, one graph for each function 00154 hash_map<Function*, DSGraph*> DSInfo; 00155 hash_set<Function*> ArgsRemainIncomplete; 00156 DSGraph *GlobalsGraph; 00157 public: 00158 ~TDDataStructures() { releaseMyMemory(); } 00159 00160 virtual bool runOnModule(Module &M); 00161 00162 bool hasGraph(const Function &F) const { 00163 return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end(); 00164 } 00165 00166 /// getDSGraph - Return the data structure graph for the specified function. 00167 /// 00168 DSGraph &getDSGraph(const Function &F) const { 00169 hash_map<Function*, DSGraph*>::const_iterator I = 00170 DSInfo.find(const_cast<Function*>(&F)); 00171 assert(I != DSInfo.end() && "Function not in module!"); 00172 return *I->second; 00173 } 00174 00175 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; } 00176 00177 /// print - Print out the analysis results... 00178 /// 00179 void print(std::ostream &O, const Module *M) const; 00180 00181 /// If the pass pipeline is done with this pass, we can release our memory... 00182 /// 00183 virtual void releaseMyMemory(); 00184 00185 /// getAnalysisUsage - This obviously provides a data structure graph. 00186 /// 00187 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00188 AU.setPreservesAll(); 00189 AU.addRequired<BUDataStructures>(); 00190 } 00191 00192 private: 00193 void markReachableFunctionsExternallyAccessible(DSNode *N, 00194 hash_set<DSNode*> &Visited); 00195 00196 void inlineGraphIntoCallees(DSGraph &G); 00197 DSGraph &getOrCreateDSGraph(Function &F); 00198 void ComputePostOrder(Function &F, hash_set<DSGraph*> &Visited, 00199 std::vector<DSGraph*> &PostOrder, 00200 const BUDataStructures::ActualCalleesTy &ActualCallees); 00201 }; 00202 00203 00204 /// CompleteBUDataStructures - This is the exact same as the bottom-up graphs, 00205 /// but we use take a completed call graph and inline all indirect callees into 00206 /// their callers graphs, making the result more useful for things like pool 00207 /// allocation. 00208 /// 00209 struct CompleteBUDataStructures : public BUDataStructures { 00210 virtual bool runOnModule(Module &M); 00211 00212 bool hasGraph(const Function &F) const { 00213 return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end(); 00214 } 00215 00216 /// getDSGraph - Return the data structure graph for the specified function. 00217 /// 00218 DSGraph &getDSGraph(const Function &F) const { 00219 hash_map<Function*, DSGraph*>::const_iterator I = 00220 DSInfo.find(const_cast<Function*>(&F)); 00221 assert(I != DSInfo.end() && "Function not in module!"); 00222 return *I->second; 00223 } 00224 00225 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00226 AU.setPreservesAll(); 00227 AU.addRequired<BUDataStructures>(); 00228 00229 // FIXME: TEMPORARY (remove once finalization of indirect call sites in the 00230 // globals graph has been implemented in the BU pass) 00231 AU.addRequired<TDDataStructures>(); 00232 } 00233 00234 /// print - Print out the analysis results... 00235 /// 00236 void print(std::ostream &O, const Module *M) const; 00237 00238 private: 00239 unsigned calculateSCCGraphs(DSGraph &FG, std::vector<DSGraph*> &Stack, 00240 unsigned &NextID, 00241 hash_map<DSGraph*, unsigned> &ValMap); 00242 DSGraph &getOrCreateGraph(Function &F); 00243 void processGraph(DSGraph &G); 00244 }; 00245 00246 } // End llvm namespace 00247 00248 #endif