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 #include "Support/HashExtras.h"
  12 #include "Support/hash_set"
  13
  14 class Type;
  15 class DSGraph;
  16 class DSNode;
  17 class DSCallSite;
  18
  19 // FIXME: move this stuff to a private header
  20 namespace DataStructureAnalysis {
  21   // isPointerType - Return true if this first class type is big enough to hold
  22   // a pointer.
  23   //
  24   bool isPointerType(const Type *Ty);
  25 }
  26
  27
  28 // LocalDataStructures - The analysis that computes the local data structure
  29 // graphs for all of the functions in the program.
  30 //
  31 // FIXME: This should be a Function pass that can be USED by a Pass, and would
  32 // be automatically preserved.  Until we can do that, this is a Pass.
  33 //
  34 class LocalDataStructures : public Pass {
  35   // DSInfo, one graph for each function
  36   hash_map<const Function*, DSGraph*> DSInfo;
  37   DSGraph *GlobalsGraph;
  38 public:
  39   ~LocalDataStructures() { releaseMemory(); }
  40
  41   virtual bool run(Module &M);
  42
  43   bool hasGraph(const Function &F) const {
  44     return DSInfo.find(&F) != DSInfo.end();
  45   }
  46
  47   // getDSGraph - Return the data structure graph for the specified function.
  48   DSGraph &getDSGraph(const Function &F) const {
  49     hash_map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
  50     assert(I != DSInfo.end() && "Function not in module!");
  51     return *I->second;
  52   }
  53
  54   DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
  55
  56   // print - Print out the analysis results...
  57   void print(std::ostream &O, const Module *M) const;
  58
  59   // If the pass pipeline is done with this pass, we can release our memory...
  60   virtual void releaseMemory();
  61
  62   // getAnalysisUsage - This obviously provides a data structure graph.
  63   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  64     AU.setPreservesAll();
  65   }
  66 };
  67
  68
  69 // BUDataStructures - The analysis that computes the interprocedurally closed
  70 // data structure graphs for all of the functions in the program.  This pass
  71 // only performs a "Bottom Up" propagation (hence the name).
  72 //
  73 class BUDataStructures : public Pass {
  74   // DSInfo, one graph for each function
  75   hash_map<const Function*, DSGraph*> DSInfo;
  76   DSGraph *GlobalsGraph;
  77 public:
  78   ~BUDataStructures() { releaseMemory(); }
  79
  80   virtual bool run(Module &M);
  81
  82   bool hasGraph(const Function &F) const {
  83     return DSInfo.find(&F) != DSInfo.end();
  84   }
  85
  86   // getDSGraph - Return the data structure graph for the specified function.
  87   DSGraph &getDSGraph(const Function &F) const {
  88     hash_map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
  89     assert(I != DSInfo.end() && "Function not in module!");
  90     return *I->second;
  91   }
  92
  93   DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
  94
  95   // print - Print out the analysis results...
  96   void print(std::ostream &O, const Module *M) const;
  97
  98   // If the pass pipeline is done with this pass, we can release our memory...
  99   virtual void releaseMemory();
 100
 101   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 102     AU.setPreservesAll();
 103     AU.addRequired<LocalDataStructures>();
 104   }
 105 private:
 106   DSGraph &calculateGraph(Function &F);
 107
 108   // inlineNonSCCGraphs - This method is almost like the other two calculate
 109   // graph methods.  This one is used to inline function graphs (from functions
 110   // outside of the SCC) into functions in the SCC.  It is not supposed to touch
 111   // functions IN the SCC at all.
 112   //
 113   DSGraph &inlineNonSCCGraphs(Function &F,
 114                               hash_set<Function*> &SCCFunctions);
 115
 116   DSGraph &calculateSCCGraph(Function &F,
 117                              hash_set<Function*> &InlinedSCCFunctions);
 118   void calculateReachableGraphs(Function *F);
 119
 120
 121   DSGraph &getOrCreateGraph(Function *F);
 122
 123   unsigned calculateGraphs(Function *F, std::vector<Function*> &Stack,
 124                            unsigned &NextID,
 125                            hash_map<Function*, unsigned> &ValMap);
 126 };
 127
 128
 129 // TDDataStructures - Analysis that computes new data structure graphs
 130 // for each function using the closed graphs for the callers computed
 131 // by the bottom-up pass.
 132 //
 133 class TDDataStructures : public Pass {
 134   // DSInfo, one graph for each function
 135   hash_map<const Function*, DSGraph*> DSInfo;
 136   hash_set<const Function*> GraphDone;
 137   DSGraph *GlobalsGraph;
 138 public:
 139   ~TDDataStructures() { releaseMemory(); }
 140
 141   virtual bool run(Module &M);
 142
 143   bool hasGraph(const Function &F) const {
 144     return DSInfo.find(&F) != DSInfo.end();
 145   }
 146
 147   // getDSGraph - Return the data structure graph for the specified function.
 148   DSGraph &getDSGraph(const Function &F) const {
 149     hash_map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
 150     assert(I != DSInfo.end() && "Function not in module!");
 151     return *I->second;
 152   }
 153
 154   DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
 155
 156   // print - Print out the analysis results...
 157   void print(std::ostream &O, const Module *M) const;
 158
 159   // If the pass pipeline is done with this pass, we can release our memory...
 160   virtual void releaseMemory();
 161
 162   // getAnalysisUsage - This obviously provides a data structure graph.
 163   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 164     AU.setPreservesAll();
 165     AU.addRequired<BUDataStructures>();
 166   }
 167 private:
 168   void calculateGraph(Function &F);
 169   DSGraph &getOrCreateDSGraph(Function &F);
 170
 171   void ResolveCallSite(DSGraph &Graph, const DSCallSite &CallSite);
 172 };
 173
 174 #endif