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/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