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