LLVM API Documentation

DataStructure.h

Go to the documentation of this file.
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