include/llvm/Analysis/DataStructure.h

   1 //===- DataStructure.h - Build data structure graphs ------------*- C++ -*-===//
   2 //
   3 // Implement the LLVM data structure analysis library.
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #ifndef LLVM_ANALYSIS_DATA_STRUCTURE_H
   8 #define LLVM_ANALYSIS_DATA_STRUCTURE_H
   9
  10 #include "llvm/Analysis/DSSupport.h"
  11 #include "llvm/Pass.h"
  12
  13 class Type;
  14 class DSGraph;
  15 class DSNode;
  16 class LocalDataStructures;     // A collection of local graphs for a program
  17 class BUDataStructures;        // A collection of bu graphs for a program
  18 class TDDataStructures;        // A collection of td graphs for a program
  19
  20 // FIXME: move this stuff to a private header
  21 namespace DataStructureAnalysis {
  22   // isPointerType - Return true if this first class type is big enough to hold
  23   // a pointer.
  24   //
  25   bool isPointerType(const Type *Ty);
  26 }
  27
  28
  29 // LocalDataStructures - The analysis that computes the local data structure
  30 // graphs for all of the functions in the program.
  31 //
  32 // FIXME: This should be a Function pass that can be USED by a Pass, and would
  33 // be automatically preserved.  Until we can do that, this is a Pass.
  34 //
  35 class LocalDataStructures : public Pass {
  36   // DSInfo, one graph for each function
  37   std::map<const Function*, DSGraph*> DSInfo;
  38 public:
  39   ~LocalDataStructures() { releaseMemory(); }
  40
  41   virtual bool run(Module &M);
  42
  43   // getDSGraph - Return the data structure graph for the specified function.
  44   DSGraph &getDSGraph(const Function &F) const {
  45     std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
  46     assert(I != DSInfo.end() && "Function not in module!");
  47     return *I->second;
  48   }
  49
  50   // print - Print out the analysis results...
  51   void print(std::ostream &O, const Module *M) const;
  52
  53   // If the pass pipeline is done with this pass, we can release our memory...
  54   virtual void releaseMemory();
  55
  56   // getAnalysisUsage - This obviously provides a data structure graph.
  57   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  58     AU.setPreservesAll();
  59   }
  60 };
  61
  62 // BUDataStructures - The analysis that computes the interprocedurally closed
  63 // data structure graphs for all of the functions in the program.  This pass
  64 // only performs a "Bottom Up" propagation (hence the name).
  65 //
  66 class BUDataStructures : public Pass {
  67   // DSInfo, one graph for each function
  68   std::map<const Function*, DSGraph*> DSInfo;
  69   std::map<const Function*, std::vector<DSCallSite> > CallSites;
  70 public:
  71   ~BUDataStructures() { releaseMemory(); }
  72
  73   virtual bool run(Module &M);
  74
  75   // getDSGraph - Return the data structure graph for the specified function.
  76   DSGraph &getDSGraph(const Function &F) const {
  77     std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
  78     assert(I != DSInfo.end() && "Function not in module!");
  79     return *I->second;
  80   }
  81
  82   /// getCallSites - Return all of the call sites for the specified function
  83   ///
  84   const std::vector<DSCallSite> *getCallSites(const Function &F) const {
  85     std::map<const Function*, std::vector<DSCallSite> >::const_iterator I
  86       = CallSites.find(&F);
  87     return I != CallSites.end() ? &I->second : 0;
  88   }
  89
  90   // print - Print out the analysis results...
  91   void print(std::ostream &O, const Module *M) const;
  92
  93   // If the pass pipeline is done with this pass, we can release our memory...
  94   virtual void releaseMemory();
  95
  96   // getAnalysisUsage - This obviously provides a data structure graph.
  97   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  98     AU.setPreservesAll();
  99     AU.addRequired<LocalDataStructures>();
 100   }
 101 private:
 102   DSGraph &calculateGraph(Function &F);
 103 };
 104
 105 // TDDataStructures - Analysis that computes new data structure graphs
 106 // for each function using the closed graphs for the callers computed
 107 // by the bottom-up pass.
 108 //
 109 class TDDataStructures : public Pass {
 110   // DSInfo, one graph for each function
 111   std::map<const Function*, DSGraph*> DSInfo;
 112
 113   // Each graph in DSInfo is based on a graph in the BUDS object.  The BUMaps
 114   // member keeps the mappings from the BU graphs to the TD graphs as they are
 115   // calculated by calculateGraph.  This information is used to properly
 116   // implement resolving of call sites, where the call sites in the BUGraph are
 117   // in terms of the caller function's graph in the BUGraph.
 118   //
 119   typedef std::map<const DSNode*, DSNodeHandle> BUNodeMapTy;
 120   std::map<const Function*, BUNodeMapTy> BUMaps;
 121
 122   // CallSitesForFunction - This is a temporary map that is only kept around
 123   // when building the top-down closures for a program.  It traverses all of the
 124   // call sites in the BU graph and holds all of the call sites that each
 125   // function is the "resolving caller" for.
 126   //
 127   std::map<const Function*,
 128            std::vector<const DSCallSite*> > CallSitesForFunction;
 129
 130 public:
 131   ~TDDataStructures() { releaseMemory(); }
 132
 133   virtual bool run(Module &M);
 134
 135   // getDSGraph - Return the data structure graph for the specified function.
 136   DSGraph &getDSGraph(const Function &F) const {
 137     std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
 138     assert(I != DSInfo.end() && "Function not in module!");
 139     return *I->second;
 140   }
 141
 142   // print - Print out the analysis results...
 143   void print(std::ostream &O, const Module *M) const;
 144
 145   // If the pass pipeline is done with this pass, we can release our memory...
 146   virtual void releaseMemory();
 147
 148   // getAnalysisUsage - This obviously provides a data structure graph.
 149   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 150     AU.setPreservesAll();
 151     AU.addRequired<BUDataStructures>();
 152   }
 153 private:
 154   DSGraph &calculateGraph(Function &F);
 155
 156   void ResolveCallSite(DSGraph &Graph, const DSCallSite &CallSite);
 157 };
 158
 159 #if 0
 160 // GlobalDSGraph - A common graph for all the globals and their outgoing links
 161 // to externally visible nodes.  This includes GlobalValues, New nodes,
 162 // Cast nodes, and Calls.  This graph can only be used by one of the
 163 // individual function graphs, and it goes away when they all go away.
 164 //
 165 class GlobalDSGraph : public DSGraph {
 166   hash_set<const DSGraph*> Referrers;
 167   void addReference(const DSGraph* referrer);
 168   void removeReference(const DSGraph* referrer);
 169   friend class DSGraph;                           // give access to Referrers
 170
 171   GlobalDSGraph(const GlobalDSGraph &GlobalDSG);  // Do not implement
 172
 173   // Helper function for cloneGlobals and cloneCalls
 174   DSNode* cloneNodeInto(DSNode *OldNode,
 175                         std::map<const DSNode*, DSNode*> &NodeCache,
 176                         bool GlobalsAreFinal = false);
 177
 178 public:
 179   GlobalDSGraph();                                // Create an empty DSGraph
 180   virtual ~GlobalDSGraph();
 181
 182   void    cloneGlobals(DSGraph& Graph, bool CloneCalls = false);
 183   void    cloneCalls  (DSGraph& Graph);
 184 };
 185 #endif
 186
 187 #endif