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/Analysis/DSGraph.h"
  11 #include "llvm/Pass.h"
  12 #if 0
  13 #include "llvm/GlobalValue.h"
  14 #include "Support/HashExtras.h"
  15 #include "Support/hash_set"
  16 #include <set>
  17 #endif
  18
  19 class Type;
  20 class GlobalValue;
  21 #if 0
  22 class GlobalDSGraph;           // A common graph for globals in a program
  23 #endif
  24 class LocalDataStructures;     // A collection of local graphs for a program
  25 class BUDataStructures;        // A collection of bu graphs for a program
  26 class TDDataStructures;        // A collection of td graphs for a program
  27
  28
  29 // FIXME: move this stuff to a private header
  30 namespace DataStructureAnalysis {
  31   // isPointerType - Return true if this first class type is big enough to hold
  32   // a pointer.
  33   //
  34   bool isPointerType(const Type *Ty);
  35 }
  36
  37
  38 // LocalDataStructures - The analysis that computes the local data structure
  39 // graphs for all of the functions in the program.
  40 //
  41 // FIXME: This should be a Function pass that can be USED by a Pass, and would
  42 // be automatically preserved.  Until we can do that, this is a Pass.
  43 //
  44 class LocalDataStructures : public Pass {
  45   // DSInfo, one graph for each function
  46   std::map<const Function*, DSGraph*> DSInfo;
  47 public:
  48   ~LocalDataStructures() { releaseMemory(); }
  49
  50   virtual bool run(Module &M);
  51
  52   // getDSGraph - Return the data structure graph for the specified function.
  53   DSGraph &getDSGraph(const Function &F) const {
  54     std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
  55     assert(I != DSInfo.end() && "Function not in module!");
  56     return *I->second;
  57   }
  58
  59   // print - Print out the analysis results...
  60   void print(std::ostream &O, const Module *M) const;
  61
  62   // If the pass pipeline is done with this pass, we can release our memory...
  63   virtual void releaseMemory();
  64
  65   // getAnalysisUsage - This obviously provides a data structure graph.
  66   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  67     AU.setPreservesAll();
  68   }
  69 };
  70
  71 #if 0
  72 // BUDataStructures - The analysis that computes the interprocedurally closed
  73 // data structure graphs for all of the functions in the program.  This pass
  74 // only performs a "Bottom Up" propogation (hence the name).
  75 //
  76 class BUDataStructures : public Pass {
  77   // DSInfo, one graph for each function
  78   std::map<const Function*, DSGraph*> DSInfo;
  79 public:
  80   ~BUDataStructures() { releaseMemory(); }
  81
  82   virtual bool run(Module &M);
  83
  84   // getDSGraph - Return the data structure graph for the specified function.
  85   DSGraph &getDSGraph(const Function &F) const {
  86     std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
  87     assert(I != DSInfo.end() && "Function not in module!");
  88     return *I->second;
  89   }
  90
  91   // print - Print out the analysis results...
  92   void print(std::ostream &O, const Module *M) const;
  93
  94   // If the pass pipeline is done with this pass, we can release our memory...
  95   virtual void releaseMemory();
  96
  97   // getAnalysisUsage - This obviously provides a data structure graph.
  98   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  99     AU.setPreservesAll();
 100     AU.addRequired<LocalDataStructures>();
 101   }
 102 private:
 103   DSGraph &calculateGraph(Function &F);
 104 };
 105
 106
 107 // TDDataStructures - Analysis that computes new data structure graphs
 108 // for each function using the closed graphs for the callers computed
 109 // by the bottom-up pass.
 110 //
 111 class TDDataStructures : public Pass {
 112   // DSInfo, one graph for each function
 113   std::map<const Function*, DSGraph*> DSInfo;
 114 public:
 115   ~TDDataStructures() { releaseMemory(); }
 116
 117   virtual bool run(Module &M);
 118
 119   // getDSGraph - Return the data structure graph for the specified function.
 120   DSGraph &getDSGraph(const Function &F) const {
 121     std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
 122     assert(I != DSInfo.end() && "Function not in module!");
 123     return *I->second;
 124   }
 125
 126   // print - Print out the analysis results...
 127   void print(std::ostream &O, const Module *M) const;
 128
 129   // If the pass pipeline is done with this pass, we can release our memory...
 130   virtual void releaseMemory();
 131
 132   // getAnalysisUsage - This obviously provides a data structure graph.
 133   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 134     AU.setPreservesAll();
 135     AU.addRequired<BUDataStructures>();
 136   }
 137 private:
 138   DSGraph &calculateGraph(Function &F);
 139   void pushGraphIntoCallee(DSGraph &callerGraph, DSGraph &calleeGraph,
 140                            std::map<Value*, DSNodeHandle> &OldValMap,
 141                            std::map<const DSNode*, DSNode*> &OldNodeMap);
 142 };
 143 #endif
 144
 145 #if 0
 146 // GlobalDSGraph - A common graph for all the globals and their outgoing links
 147 // to externally visible nodes.  This includes GlobalValues, New nodes,
 148 // Cast nodes, and Calls.  This graph can only be used by one of the
 149 // individual function graphs, and it goes away when they all go away.
 150 //
 151 class GlobalDSGraph : public DSGraph {
 152   hash_set<const DSGraph*> Referrers;
 153   void addReference(const DSGraph* referrer);
 154   void removeReference(const DSGraph* referrer);
 155   friend class DSGraph;                           // give access to Referrers
 156
 157   GlobalDSGraph(const GlobalDSGraph &GlobalDSG);  // Do not implement
 158
 159   // Helper function for cloneGlobals and cloneCalls
 160   DSNode* cloneNodeInto(DSNode *OldNode,
 161                         std::map<const DSNode*, DSNode*> &NodeCache,
 162                         bool GlobalsAreFinal = false);
 163
 164 public:
 165   GlobalDSGraph();                                // Create an empty DSGraph
 166   virtual ~GlobalDSGraph();
 167
 168   void    cloneGlobals(DSGraph& Graph, bool CloneCalls = false);
 169   void    cloneCalls  (DSGraph& Graph);
 170 };
 171 #endif
 172
 173 #endif