LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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