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 <assert.h>
  11
  12 #include "llvm/Pass.h"
  13 #include "Support/HashExtras.h"
  14 #include "Support/hash_set"
  15
  16 class Type;
  17 class DSGraph;
  18 class DSNode;
  19 class DSCallSite;
  20
  21 // FIXME: move this stuff to a private header
  22 namespace DataStructureAnalysis {
  23   // isPointerType - Return true if this first class type is big enough to hold
  24   // a pointer.
  25   //
  26   bool isPointerType(const Type *Ty);
  27 }
  28
  29
  30 // LocalDataStructures - The analysis that computes the local data structure
  31 // graphs for all of the functions in the program.
  32 //
  33 // FIXME: This should be a Function pass that can be USED by a Pass, and would
  34 // be automatically preserved.  Until we can do that, this is a Pass.
  35 //
  36 class LocalDataStructures : public Pass {
  37   // DSInfo, one graph for each function
  38   hash_map<const Function*, DSGraph*> DSInfo;
  39   DSGraph *GlobalsGraph;
  40 public:
  41   ~LocalDataStructures() { releaseMemory(); }
  42
  43   virtual bool run(Module &M);
  44
  45   bool hasGraph(const Function &F) const {
  46     return DSInfo.find(&F) != DSInfo.end();
  47   }
  48
  49   // getDSGraph - Return the data structure graph for the specified function.
  50   DSGraph &getDSGraph(const Function &F) const {
  51     hash_map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&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<const Function*, DSGraph*> DSInfo;
  78   DSGraph *GlobalsGraph;
  79 public:
  80   ~BUDataStructures() { releaseMemory(); }
  81
  82   virtual bool run(Module &M);
  83
  84   bool hasGraph(const Function &F) const {
  85     return DSInfo.find(&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<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
  91     assert(I != DSInfo.end() && "Function not in module!");
  92     return *I->second;
  93   }
  94
  95   DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
  96
  97   // print - Print out the analysis results...
  98   void print(std::ostream &O, const Module *M) const;
  99
 100   // If the pass pipeline is done with this pass, we can release our memory...
 101   virtual void releaseMemory();
 102
 103   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 104     AU.setPreservesAll();
 105     AU.addRequired<LocalDataStructures>();
 106   }
 107 private:
 108   DSGraph &calculateGraph(Function &F);
 109
 110   // inlineNonSCCGraphs - This method is almost like the other two calculate
 111   // graph methods.  This one is used to inline function graphs (from functions
 112   // outside of the SCC) into functions in the SCC.  It is not supposed to touch
 113   // functions IN the SCC at all.
 114   //
 115   DSGraph &inlineNonSCCGraphs(Function &F,
 116                               hash_set<Function*> &SCCFunctions);
 117
 118   DSGraph &calculateSCCGraph(Function &F,
 119                              hash_set<Function*> &InlinedSCCFunctions);
 120   void calculateReachableGraphs(Function *F);
 121
 122
 123   DSGraph &getOrCreateGraph(Function *F);
 124
 125   unsigned calculateGraphs(Function *F, std::vector<Function*> &Stack,
 126                            unsigned &NextID,
 127                            hash_map<Function*, unsigned> &ValMap);
 128 };
 129
 130
 131 // TDDataStructures - Analysis that computes new data structure graphs
 132 // for each function using the closed graphs for the callers computed
 133 // by the bottom-up pass.
 134 //
 135 class TDDataStructures : public Pass {
 136   // DSInfo, one graph for each function
 137   hash_map<const Function*, DSGraph*> DSInfo;
 138   hash_set<const Function*> GraphDone;
 139   DSGraph *GlobalsGraph;
 140 public:
 141   ~TDDataStructures() { releaseMyMemory(); }
 142
 143   virtual bool run(Module &M);
 144
 145   bool hasGraph(const Function &F) const {
 146     return DSInfo.find(&F) != DSInfo.end();
 147   }
 148
 149   // getDSGraph - Return the data structure graph for the specified function.
 150   DSGraph &getDSGraph(const Function &F) const {
 151     hash_map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
 152     assert(I != DSInfo.end() && "Function not in module!");
 153     return *I->second;
 154   }
 155
 156   DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
 157
 158   // print - Print out the analysis results...
 159   void print(std::ostream &O, const Module *M) const;
 160
 161   // If the pass pipeline is done with this pass, we can release our memory...
 162   virtual void releaseMyMemory();
 163
 164   // getAnalysisUsage - This obviously provides a data structure graph.
 165   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 166     AU.setPreservesAll();
 167     AU.addRequired<BUDataStructures>();
 168   }
 169
 170 private:
 171   void calculateGraph(Function &F);
 172   DSGraph &getOrCreateDSGraph(Function &F);
 173
 174   void ResolveCallSite(DSGraph &Graph, const DSCallSite &CallSite);
 175 };
 176
 177 #endif