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