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   // getDSGraph - Return the data structure graph for the specified function.
  43   DSGraph &getDSGraph(const Function &F) const {
  44     std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
  45     assert(I != DSInfo.end() && "Function not in module!");
  46     return *I->second;
  47   }
  48
  49   DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
  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
  64 // BUDataStructures - The analysis that computes the interprocedurally closed
  65 // data structure graphs for all of the functions in the program.  This pass
  66 // only performs a "Bottom Up" propagation (hence the name).
  67 //
  68 class BUDataStructures : public Pass {
  69   // DSInfo, one graph for each function
  70   std::map<const Function*, DSGraph*> DSInfo;
  71   DSGraph *GlobalsGraph;
  72 public:
  73   ~BUDataStructures() { releaseMemory(); }
  74
  75   virtual bool run(Module &M);
  76
  77   // getDSGraph - Return the data structure graph for the specified function.
  78   DSGraph &getDSGraph(const Function &F) const {
  79     std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
  80     assert(I != DSInfo.end() && "Function not in module!");
  81     return *I->second;
  82   }
  83
  84   DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
  85
  86   // print - Print out the analysis results...
  87   void print(std::ostream &O, const Module *M) const;
  88
  89   // If the pass pipeline is done with this pass, we can release our memory...
  90   virtual void releaseMemory();
  91
  92   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  93     AU.setPreservesAll();
  94     AU.addRequired<LocalDataStructures>();
  95   }
  96 private:
  97   DSGraph &calculateGraph(Function &F);
  98 };
  99
 100
 101 // TDDataStructures - Analysis that computes new data structure graphs
 102 // for each function using the closed graphs for the callers computed
 103 // by the bottom-up pass.
 104 //
 105 class TDDataStructures : public Pass {
 106   // DSInfo, one graph for each function
 107   std::map<const Function*, DSGraph*> DSInfo;
 108   std::set<const Function*> GraphDone;
 109   DSGraph *GlobalsGraph;
 110 public:
 111   ~TDDataStructures() { releaseMemory(); }
 112
 113   virtual bool run(Module &M);
 114
 115   // getDSGraph - Return the data structure graph for the specified function.
 116   DSGraph &getDSGraph(const Function &F) const {
 117     std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
 118     assert(I != DSInfo.end() && "Function not in module!");
 119     return *I->second;
 120   }
 121
 122   DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
 123
 124   // print - Print out the analysis results...
 125   void print(std::ostream &O, const Module *M) const;
 126
 127   // If the pass pipeline is done with this pass, we can release our memory...
 128   virtual void releaseMemory();
 129
 130   // getAnalysisUsage - This obviously provides a data structure graph.
 131   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 132     AU.setPreservesAll();
 133     AU.addRequired<BUDataStructures>();
 134   }
 135 private:
 136   void calculateGraph(Function &F);
 137   DSGraph &getOrCreateDSGraph(Function &F);
 138
 139   void ResolveCallSite(DSGraph &Graph, const DSCallSite &CallSite);
 140 };
 141
 142 #endif