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 "Support/HashExtras.h"
  12 #include "Support/hash_set"
  13
  14 class Type;
  15 class CallInst;
  16 class DSGraph;
  17 class DSNode;
  18 class DSCallSite;
  19
  20 // FIXME: move this stuff to a private header
  21 namespace DataStructureAnalysis {
  22   // isPointerType - Return true if this first class type is big enough to hold
  23   // a pointer.
  24   //
  25   bool isPointerType(const Type *Ty);
  26 }
  27
  28
  29 // LocalDataStructures - The analysis that computes the local data structure
  30 // graphs for all of the functions in the program.
  31 //
  32 // FIXME: This should be a Function pass that can be USED by a Pass, and would
  33 // be automatically preserved.  Until we can do that, this is a Pass.
  34 //
  35 class LocalDataStructures : public Pass {
  36   // DSInfo, one graph for each function
  37   hash_map<Function*, DSGraph*> DSInfo;
  38   DSGraph *GlobalsGraph;
  39 public:
  40   ~LocalDataStructures() { releaseMemory(); }
  41
  42   virtual bool run(Module &M);
  43
  44   bool hasGraph(const Function &F) const {
  45     return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
  46   }
  47
  48   // getDSGraph - Return the data structure graph for the specified function.
  49   DSGraph &getDSGraph(const Function &F) const {
  50     hash_map<Function*, DSGraph*>::const_iterator I =
  51       DSInfo.find(const_cast<Function*>(&F));
  52     assert(I != DSInfo.end() && "Function not in module!");
  53     return *I->second;
  54   }
  55
  56   DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
  57
  58   // print - Print out the analysis results...
  59   void print(std::ostream &O, const Module *M) const;
  60
  61   // If the pass pipeline is done with this pass, we can release our memory...
  62   virtual void releaseMemory();
  63
  64   // getAnalysisUsage - This obviously provides a data structure graph.
  65   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  66     AU.setPreservesAll();
  67   }
  68 };
  69
  70
  71 // BUDataStructures - The analysis that computes the interprocedurally closed
  72 // data structure graphs for all of the functions in the program.  This pass
  73 // only performs a "Bottom Up" propagation (hence the name).
  74 //
  75 class BUDataStructures : public Pass {
  76   // DSInfo, one graph for each function
  77   hash_map<Function*, DSGraph*> DSInfo;
  78   DSGraph *GlobalsGraph;
  79   hash_multimap<CallInst*, Function*> ActualCallees;
  80 public:
  81   ~BUDataStructures() { releaseMemory(); }
  82
  83   virtual bool run(Module &M);
  84
  85   bool hasGraph(const Function &F) const {
  86     return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
  87   }
  88
  89   // getDSGraph - Return the data structure graph for the specified function.
  90   DSGraph &getDSGraph(const Function &F) const {
  91     hash_map<Function*, DSGraph*>::const_iterator I =
  92       DSInfo.find(const_cast<Function*>(&F));
  93     assert(I != DSInfo.end() && "Function not in module!");
  94     return *I->second;
  95   }
  96
  97   DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
  98
  99   // print - Print out the analysis results...
 100   void print(std::ostream &O, const Module *M) const;
 101
 102   // If the pass pipeline is done with this pass, we can release our memory...
 103   virtual void releaseMemory();
 104
 105   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 106     AU.setPreservesAll();
 107     AU.addRequired<LocalDataStructures>();
 108   }
 109
 110   typedef hash_multimap<CallInst*, Function*> ActualCalleesTy;
 111   const ActualCalleesTy &getActualCallees() const {
 112     return ActualCallees;
 113   }
 114
 115 private:
 116   void calculateGraph(DSGraph &G);
 117
 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<Function*, DSGraph*> DSInfo;
 136   hash_set<Function*> ArgsRemainIncomplete;
 137   DSGraph *GlobalsGraph;
 138 public:
 139   ~TDDataStructures() { releaseMyMemory(); }
 140
 141   virtual bool run(Module &M);
 142
 143   bool hasGraph(const Function &F) const {
 144     return DSInfo.find(const_cast<Function*>(&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<Function*, DSGraph*>::const_iterator I =
 150       DSInfo.find(const_cast<Function*>(&F));
 151     assert(I != DSInfo.end() && "Function not in module!");
 152     return *I->second;
 153   }
 154
 155   DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
 156
 157   // print - Print out the analysis results...
 158   void print(std::ostream &O, const Module *M) const;
 159
 160   // If the pass pipeline is done with this pass, we can release our memory...
 161   virtual void releaseMyMemory();
 162
 163   // getAnalysisUsage - This obviously provides a data structure graph.
 164   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 165     AU.setPreservesAll();
 166     AU.addRequired<BUDataStructures>();
 167   }
 168
 169 private:
 170   void calculateGraphFrom(Function &F);
 171   void inlineGraphIntoCallees(DSGraph &G);
 172   DSGraph &getOrCreateDSGraph(Function &F);
 173   void ComputePostOrder(Function &F, hash_set<DSGraph*> &Visited,
 174                         std::vector<DSGraph*> &PostOrder,
 175                         const BUDataStructures::ActualCalleesTy &ActualCallees);
 176 };
 177
 178 #endif