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