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