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 <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, unsigned Indent);
 106   bool ResolveFunctionCalls(DSGraph &G, unsigned &FirstResolvableCall,
 107                             std::map<Function*, DSCallSite> &InProcess,
 108                             unsigned Indent);
 109 };
 110
 111
 112 // TDDataStructures - Analysis that computes new data structure graphs
 113 // for each function using the closed graphs for the callers computed
 114 // by the bottom-up pass.
 115 //
 116 class TDDataStructures : public Pass {
 117   // DSInfo, one graph for each function
 118   std::map<const Function*, DSGraph*> DSInfo;
 119   std::set<const Function*> GraphDone;
 120   DSGraph *GlobalsGraph;
 121 public:
 122   ~TDDataStructures() { releaseMemory(); }
 123
 124   virtual bool run(Module &M);
 125
 126   bool hasGraph(const Function &F) const {
 127     return DSInfo.find(&F) != DSInfo.end();
 128   }
 129
 130   // getDSGraph - Return the data structure graph for the specified function.
 131   DSGraph &getDSGraph(const Function &F) const {
 132     std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
 133     assert(I != DSInfo.end() && "Function not in module!");
 134     return *I->second;
 135   }
 136
 137   DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
 138
 139   // print - Print out the analysis results...
 140   void print(std::ostream &O, const Module *M) const;
 141
 142   // If the pass pipeline is done with this pass, we can release our memory...
 143   virtual void releaseMemory();
 144
 145   // getAnalysisUsage - This obviously provides a data structure graph.
 146   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 147     AU.setPreservesAll();
 148     AU.addRequired<BUDataStructures>();
 149   }
 150 private:
 151   void calculateGraph(Function &F);
 152   DSGraph &getOrCreateDSGraph(Function &F);
 153
 154   void ResolveCallSite(DSGraph &Graph, const DSCallSite &CallSite);
 155 };
 156
 157 #endif