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_map" 00020 #include "llvm/ADT/hash_set" 00021 #include "llvm/ADT/EquivalenceClasses.h" 00022 00023 namespace llvm { 00024 00025 class Type; 00026 class Instruction; 00027 class GlobalValue; 00028 class CallSite; 00029 class DSGraph; 00030 class DSCallSite; 00031 class DSNode; 00032 class DSNodeHandle; 00033 00034 FunctionPass *createDataStructureStatsPass(); 00035 FunctionPass *createDataStructureGraphCheckerPass(); 00036 00037 00038 // FIXME: move this stuff to a private header 00039 namespace DataStructureAnalysis { 00040 /// isPointerType - Return true if this first class type is big enough to hold 00041 /// a pointer. 00042 /// 00043 bool isPointerType(const Type *Ty); 00044 } 00045 00046 00047 // LocalDataStructures - The analysis that computes the local data structure 00048 // graphs for all of the functions in the program. 00049 // 00050 // FIXME: This should be a Function pass that can be USED by a Pass, and would 00051 // be automatically preserved. Until we can do that, this is a Pass. 00052 // 00053 class LocalDataStructures : public ModulePass { 00054 // DSInfo, one graph for each function 00055 hash_map<Function*, DSGraph*> DSInfo; 00056 DSGraph *GlobalsGraph; 00057 00058 /// GlobalECs - The equivalence classes for each global value that is merged 00059 /// with other global values in the DSGraphs. 00060 EquivalenceClasses<GlobalValue*> GlobalECs; 00061 public: 00062 ~LocalDataStructures() { releaseMemory(); } 00063 00064 virtual bool runOnModule(Module &M); 00065 00066 bool hasGraph(const Function &F) const { 00067 return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end(); 00068 } 00069 00070 /// getDSGraph - Return the data structure graph for the specified function. 00071 /// 00072 DSGraph &getDSGraph(const Function &F) const { 00073 hash_map<Function*, DSGraph*>::const_iterator I = 00074 DSInfo.find(const_cast<Function*>(&F)); 00075 assert(I != DSInfo.end() && "Function not in module!"); 00076 return *I->second; 00077 } 00078 00079 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; } 00080 00081 EquivalenceClasses<GlobalValue*> &getGlobalECs() { return GlobalECs; } 00082 00083 /// print - Print out the analysis results... 00084 /// 00085 void print(std::ostream &O, const Module *M) const; 00086 00087 /// releaseMemory - if the pass pipeline is done with this pass, we can 00088 /// release our memory... 00089 /// 00090 virtual void releaseMemory(); 00091 00092 /// getAnalysisUsage - This obviously provides a data structure graph. 00093 /// 00094 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00095 AU.setPreservesAll(); 00096 AU.addRequired<TargetData>(); 00097 } 00098 }; 00099 00100 00101 /// BUDataStructures - The analysis that computes the interprocedurally closed 00102 /// data structure graphs for all of the functions in the program. This pass 00103 /// only performs a "Bottom Up" propagation (hence the name). 00104 /// 00105 class BUDataStructures : public ModulePass { 00106 protected: 00107 // DSInfo, one graph for each function 00108 hash_map<Function*, DSGraph*> DSInfo; 00109 DSGraph *GlobalsGraph; 00110 std::set<std::pair<Instruction*, Function*> > ActualCallees; 00111 00112 // This map is only maintained during construction of BU Graphs 00113 std::map<std::vector<Function*>, 00114 std::pair<DSGraph*, std::vector<DSNodeHandle> > > *IndCallGraphMap; 00115 00116 /// GlobalECs - The equivalence classes for each global value that is merged 00117 /// with other global values in the DSGraphs. 00118 EquivalenceClasses<GlobalValue*> GlobalECs; 00119 public: 00120 ~BUDataStructures() { releaseMyMemory(); } 00121 00122 virtual bool runOnModule(Module &M); 00123 00124 bool hasGraph(const Function &F) const { 00125 return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end(); 00126 } 00127 00128 /// getDSGraph - Return the data structure graph for the specified function. 00129 /// 00130 DSGraph &getDSGraph(const Function &F) const { 00131 hash_map<Function*, DSGraph*>::const_iterator I = 00132 DSInfo.find(const_cast<Function*>(&F)); 00133 if (I != DSInfo.end()) 00134 return *I->second; 00135 return const_cast<BUDataStructures*>(this)-> 00136 CreateGraphForExternalFunction(F); 00137 } 00138 00139 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; } 00140 00141 EquivalenceClasses<GlobalValue*> &getGlobalECs() { return GlobalECs; } 00142 00143 DSGraph &CreateGraphForExternalFunction(const Function &F); 00144 00145 /// deleteValue/copyValue - Interfaces to update the DSGraphs in the program. 00146 /// These correspond to the interfaces defined in the AliasAnalysis class. 00147 void deleteValue(Value *V); 00148 void copyValue(Value *From, Value *To); 00149 00150 /// print - Print out the analysis results... 00151 /// 00152 void print(std::ostream &O, const Module *M) const; 00153 00154 // FIXME: Once the pass manager is straightened out, rename this to 00155 // releaseMemory. 00156 void releaseMyMemory(); 00157 00158 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00159 AU.setPreservesAll(); 00160 AU.addRequired<LocalDataStructures>(); 00161 } 00162 00163 typedef std::set<std::pair<Instruction*, Function*> > ActualCalleesTy; 00164 const ActualCalleesTy &getActualCallees() const { 00165 return ActualCallees; 00166 } 00167 00168 typedef ActualCalleesTy::const_iterator callee_iterator; 00169 callee_iterator callee_begin(Instruction *I) const { 00170 return ActualCallees.lower_bound(std::pair<Instruction*,Function*>(I, 0)); 00171 } 00172 00173 callee_iterator callee_end(Instruction *I) const { 00174 I = (Instruction*)((char*)I + 1); 00175 return ActualCallees.lower_bound(std::pair<Instruction*,Function*>(I, 0)); 00176 } 00177 00178 private: 00179 void calculateGraph(DSGraph &G); 00180 00181 DSGraph &getOrCreateGraph(Function *F); 00182 00183 unsigned calculateGraphs(Function *F, std::vector<Function*> &Stack, 00184 unsigned &NextID, 00185 hash_map<Function*, unsigned> &ValMap); 00186 }; 00187 00188 00189 /// TDDataStructures - Analysis that computes new data structure graphs 00190 /// for each function using the closed graphs for the callers computed 00191 /// by the bottom-up pass. 00192 /// 00193 class TDDataStructures : public ModulePass { 00194 // DSInfo, one graph for each function 00195 hash_map<Function*, DSGraph*> DSInfo; 00196 hash_set<Function*> ArgsRemainIncomplete; 00197 DSGraph *GlobalsGraph; 00198 BUDataStructures *BUInfo; 00199 00200 /// GlobalECs - The equivalence classes for each global value that is merged 00201 /// with other global values in the DSGraphs. 00202 EquivalenceClasses<GlobalValue*> GlobalECs; 00203 00204 /// CallerCallEdges - For a particular graph, we keep a list of these records 00205 /// which indicates which graphs call this function and from where. 00206 struct CallerCallEdge { 00207 DSGraph *CallerGraph; // The graph of the caller function. 00208 const DSCallSite *CS; // The actual call site. 00209 Function *CalledFunction; // The actual function being called. 00210 00211 CallerCallEdge(DSGraph *G, const DSCallSite *cs, Function *CF) 00212 : CallerGraph(G), CS(cs), CalledFunction(CF) {} 00213 00214 bool operator<(const CallerCallEdge &RHS) const { 00215 return CallerGraph < RHS.CallerGraph || 00216 (CallerGraph == RHS.CallerGraph && CS < RHS.CS); 00217 } 00218 }; 00219 00220 std::map<DSGraph*, std::vector<CallerCallEdge> > CallerEdges; 00221 00222 00223 // IndCallMap - We memoize the results of indirect call inlining operations 00224 // that have multiple targets here to avoid N*M inlining. The key to the map 00225 // is a sorted set of callee functions, the value is the DSGraph that holds 00226 // all of the caller graphs merged together, and the DSCallSite to merge with 00227 // the arguments for each function. 00228 std::map<std::vector<Function*>, DSGraph*> IndCallMap; 00229 00230 public: 00231 ~TDDataStructures() { releaseMyMemory(); } 00232 00233 virtual bool runOnModule(Module &M); 00234 00235 bool hasGraph(const Function &F) const { 00236 return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end(); 00237 } 00238 00239 /// getDSGraph - Return the data structure graph for the specified function. 00240 /// 00241 DSGraph &getDSGraph(const Function &F) const { 00242 hash_map<Function*, DSGraph*>::const_iterator I = 00243 DSInfo.find(const_cast<Function*>(&F)); 00244 if (I != DSInfo.end()) return *I->second; 00245 return const_cast<TDDataStructures*>(this)-> 00246 getOrCreateDSGraph(const_cast<Function&>(F)); 00247 } 00248 00249 DSGraph &getGlobalsGraph() const { return *GlobalsGraph; } 00250 EquivalenceClasses<GlobalValue*> &getGlobalECs() { return GlobalECs; } 00251 00252 00253 /// deleteValue/copyValue - Interfaces to update the DSGraphs in the program. 00254 /// These correspond to the interfaces defined in the AliasAnalysis class. 00255 void deleteValue(Value *V); 00256 void copyValue(Value *From, Value *To); 00257 00258 /// print - Print out the analysis results... 00259 /// 00260 void print(std::ostream &O, const Module *M) const; 00261 00262 /// If the pass pipeline is done with this pass, we can release our memory... 00263 /// 00264 virtual void releaseMyMemory(); 00265 00266 /// getAnalysisUsage - This obviously provides a data structure graph. 00267 /// 00268 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00269 AU.setPreservesAll(); 00270 AU.addRequired<BUDataStructures>(); 00271 } 00272 00273 private: 00274 void markReachableFunctionsExternallyAccessible(DSNode *N, 00275 hash_set<DSNode*> &Visited); 00276 00277 void InlineCallersIntoGraph(DSGraph &G); 00278 DSGraph &getOrCreateDSGraph(Function &F); 00279 void ComputePostOrder(Function &F, hash_set<DSGraph*> &Visited, 00280 std::vector<DSGraph*> &PostOrder); 00281 }; 00282 00283 00284 /// CompleteBUDataStructures - This is the exact same as the bottom-up graphs, 00285 /// but we use take a completed call graph and inline all indirect callees into 00286 /// their callers graphs, making the result more useful for things like pool 00287 /// allocation. 00288 /// 00289 struct CompleteBUDataStructures : public BUDataStructures { 00290 virtual bool runOnModule(Module &M); 00291 00292 bool hasGraph(const Function &F) const { 00293 return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end(); 00294 } 00295 00296 /// getDSGraph - Return the data structure graph for the specified function. 00297 /// 00298 DSGraph &getDSGraph(const Function &F) const { 00299 hash_map<Function*, DSGraph*>::const_iterator I = 00300 DSInfo.find(const_cast<Function*>(&F)); 00301 assert(I != DSInfo.end() && "Function not in module!"); 00302 return *I->second; 00303 } 00304 00305 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00306 AU.setPreservesAll(); 00307 AU.addRequired<BUDataStructures>(); 00308 00309 // FIXME: TEMPORARY (remove once finalization of indirect call sites in the 00310 // globals graph has been implemented in the BU pass) 00311 AU.addRequired<TDDataStructures>(); 00312 } 00313 00314 /// print - Print out the analysis results... 00315 /// 00316 void print(std::ostream &O, const Module *M) const; 00317 00318 private: 00319 unsigned calculateSCCGraphs(DSGraph &FG, std::vector<DSGraph*> &Stack, 00320 unsigned &NextID, 00321 hash_map<DSGraph*, unsigned> &ValMap); 00322 DSGraph &getOrCreateGraph(Function &F); 00323 void processGraph(DSGraph &G); 00324 }; 00325 00326 00327 /// EquivClassGraphs - This is the same as the complete bottom-up graphs, but 00328 /// with functions partitioned into equivalence classes and a single merged 00329 /// DS graph for all functions in an equivalence class. After this merging, 00330 /// graphs are inlined bottom-up on the SCCs of the final (CBU) call graph. 00331 /// 00332 struct EquivClassGraphs : public ModulePass { 00333 CompleteBUDataStructures *CBU; 00334 00335 DSGraph *GlobalsGraph; 00336 00337 // DSInfo - one graph for each function. 00338 hash_map<const Function*, DSGraph*> DSInfo; 00339 00340 /// ActualCallees - The actual functions callable from indirect call sites. 00341 /// 00342 std::set<std::pair<Instruction*, Function*> > ActualCallees; 00343 00344 // Equivalence class where functions that can potentially be called via the 00345 // same function pointer are in the same class. 00346 EquivalenceClasses<Function*> FuncECs; 00347 00348 /// OneCalledFunction - For each indirect call, we keep track of one 00349 /// target of the call. This is used to find equivalence class called by 00350 /// a call site. 00351 std::map<DSNode*, Function *> OneCalledFunction; 00352 00353 /// GlobalECs - The equivalence classes for each global value that is merged 00354 /// with other global values in the DSGraphs. 00355 EquivalenceClasses<GlobalValue*> GlobalECs; 00356 00357 public: 00358 /// EquivClassGraphs - Computes the equivalence classes and then the 00359 /// folded DS graphs for each class. 00360 /// 00361 virtual bool runOnModule(Module &M); 00362 00363 /// print - Print out the analysis results... 00364 /// 00365 void print(std::ostream &O, const Module *M) const; 00366 00367 EquivalenceClasses<GlobalValue*> &getGlobalECs() { return GlobalECs; } 00368 00369 /// getDSGraph - Return the data structure graph for the specified function. 00370 /// This returns the folded graph. The folded graph is the same as the CBU 00371 /// graph iff the function is in a singleton equivalence class AND all its 00372 /// callees also have the same folded graph as the CBU graph. 00373 /// 00374 DSGraph &getDSGraph(const Function &F) const { 00375 hash_map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F); 00376 assert(I != DSInfo.end() && "No graph computed for that function!"); 00377 return *I->second; 00378 } 00379 00380 bool hasGraph(const Function &F) const { 00381 return DSInfo.find(&F) != DSInfo.end(); 00382 } 00383 00384 /// ContainsDSGraphFor - Return true if we have a graph for the specified 00385 /// function. 00386 bool ContainsDSGraphFor(const Function &F) const { 00387 return DSInfo.find(&F) != DSInfo.end(); 00388 } 00389 00390 /// getSomeCalleeForCallSite - Return any one callee function at 00391 /// a call site. 00392 /// 00393 Function *getSomeCalleeForCallSite(const CallSite &CS) const; 00394 00395 DSGraph &getGlobalsGraph() const { 00396 return *GlobalsGraph; 00397 } 00398 00399 typedef std::set<std::pair<Instruction*, Function*> > ActualCalleesTy; 00400 const ActualCalleesTy &getActualCallees() const { 00401 return ActualCallees; 00402 } 00403 00404 typedef ActualCalleesTy::const_iterator callee_iterator; 00405 callee_iterator callee_begin(Instruction *I) const { 00406 return ActualCallees.lower_bound(std::pair<Instruction*,Function*>(I, 0)); 00407 } 00408 00409 callee_iterator callee_end(Instruction *I) const { 00410 I = (Instruction*)((char*)I + 1); 00411 return ActualCallees.lower_bound(std::pair<Instruction*,Function*>(I, 0)); 00412 } 00413 00414 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00415 AU.setPreservesAll(); 00416 AU.addRequired<CompleteBUDataStructures>(); 00417 } 00418 00419 private: 00420 void buildIndirectFunctionSets(Module &M); 00421 00422 unsigned processSCC(DSGraph &FG, std::vector<DSGraph*> &Stack, 00423 unsigned &NextID, 00424 std::map<DSGraph*, unsigned> &ValMap); 00425 void processGraph(DSGraph &FG); 00426 00427 DSGraph &getOrCreateGraph(Function &F); 00428 }; 00429 00430 } // End llvm namespace 00431 00432 #endif