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