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