include/llvm/Analysis/DataStructure/DataStructure.h

   1 //===- DataStructure.h - Build data structure graphs ------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Implement the LLVM data structure analysis library.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_ANALYSIS_DATA_STRUCTURE_H
  15 #define LLVM_ANALYSIS_DATA_STRUCTURE_H
  16
  17 #include "llvm/Pass.h"
  18 #include "llvm/Target/TargetData.h"
  19 #include "Support/hash_set"
  20
  21 namespace llvm {
  22
  23 class Type;
  24 class Instruction;
  25 class DSGraph;
  26 class DSNode;
  27
  28 // FIXME: move this stuff to a private header
  29 namespace DataStructureAnalysis {
  30   /// isPointerType - Return true if this first class type is big enough to hold
  31   /// a pointer.
  32   ///
  33   bool isPointerType(const Type *Ty);
  34 }
  35
  36
  37 // LocalDataStructures - The analysis that computes the local data structure
  38 // graphs for all of the functions in the program.
  39 //
  40 // FIXME: This should be a Function pass that can be USED by a Pass, and would
  41 // be automatically preserved.  Until we can do that, this is a Pass.
  42 //
  43 class LocalDataStructures : public Pass {
  44   // DSInfo, one graph for each function
  45   hash_map<Function*, DSGraph*> DSInfo;
  46   DSGraph *GlobalsGraph;
  47 public:
  48   ~LocalDataStructures() { releaseMemory(); }
  49
  50   virtual bool run(Module &M);
  51
  52   bool hasGraph(const Function &F) const {
  53     return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
  54   }
  55
  56   /// getDSGraph - Return the data structure graph for the specified function.
  57   ///
  58   DSGraph &getDSGraph(const Function &F) const {
  59     hash_map<Function*, DSGraph*>::const_iterator I =
  60       DSInfo.find(const_cast<Function*>(&F));
  61     assert(I != DSInfo.end() && "Function not in module!");
  62     return *I->second;
  63   }
  64
  65   DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
  66
  67   /// print - Print out the analysis results...
  68   ///
  69   void print(std::ostream &O, const Module *M) const;
  70
  71   /// releaseMemory - if the pass pipeline is done with this pass, we can
  72   /// release our memory...
  73   ///
  74   virtual void releaseMemory();
  75
  76   /// getAnalysisUsage - This obviously provides a data structure graph.
  77   ///
  78   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  79     AU.setPreservesAll();
  80     AU.addRequired<TargetData>();
  81   }
  82 };
  83
  84
  85 /// BUDataStructures - The analysis that computes the interprocedurally closed
  86 /// data structure graphs for all of the functions in the program.  This pass
  87 /// only performs a "Bottom Up" propagation (hence the name).
  88 ///
  89 class BUDataStructures : public Pass {
  90 protected:
  91   // DSInfo, one graph for each function
  92   hash_map<Function*, DSGraph*> DSInfo;
  93   DSGraph *GlobalsGraph;
  94   hash_multimap<Instruction*, Function*> ActualCallees;
  95 public:
  96   ~BUDataStructures() { releaseMemory(); }
  97
  98   virtual bool run(Module &M);
  99
 100   bool hasGraph(const Function &F) const {
 101     return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
 102   }
 103
 104   /// getDSGraph - Return the data structure graph for the specified function.
 105   ///
 106   DSGraph &getDSGraph(const Function &F) const {
 107     hash_map<Function*, DSGraph*>::const_iterator I =
 108       DSInfo.find(const_cast<Function*>(&F));
 109     assert(I != DSInfo.end() && "Function not in module!");
 110     return *I->second;
 111   }
 112
 113   DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
 114
 115   /// print - Print out the analysis results...
 116   ///
 117   void print(std::ostream &O, const Module *M) const;
 118
 119   /// releaseMemory - if the pass pipeline is done with this pass, we can
 120   /// release our memory...
 121   ///
 122   virtual void releaseMemory();
 123
 124   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 125     AU.setPreservesAll();
 126     AU.addRequired<LocalDataStructures>();
 127   }
 128
 129   typedef hash_multimap<Instruction*, Function*> ActualCalleesTy;
 130   const ActualCalleesTy &getActualCallees() const {
 131     return ActualCallees;
 132   }
 133
 134 private:
 135   void calculateGraph(DSGraph &G);
 136
 137   void calculateReachableGraphs(Function *F);
 138
 139
 140   DSGraph &getOrCreateGraph(Function *F);
 141
 142   unsigned calculateGraphs(Function *F, std::vector<Function*> &Stack,
 143                            unsigned &NextID,
 144                            hash_map<Function*, unsigned> &ValMap);
 145 };
 146
 147
 148 /// TDDataStructures - Analysis that computes new data structure graphs
 149 /// for each function using the closed graphs for the callers computed
 150 /// by the bottom-up pass.
 151 ///
 152 class TDDataStructures : public Pass {
 153   // DSInfo, one graph for each function
 154   hash_map<Function*, DSGraph*> DSInfo;
 155   hash_set<Function*> ArgsRemainIncomplete;
 156   DSGraph *GlobalsGraph;
 157 public:
 158   ~TDDataStructures() { releaseMyMemory(); }
 159
 160   virtual bool run(Module &M);
 161
 162   bool hasGraph(const Function &F) const {
 163     return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
 164   }
 165
 166   /// getDSGraph - Return the data structure graph for the specified function.
 167   ///
 168   DSGraph &getDSGraph(const Function &F) const {
 169     hash_map<Function*, DSGraph*>::const_iterator I =
 170       DSInfo.find(const_cast<Function*>(&F));
 171     assert(I != DSInfo.end() && "Function not in module!");
 172     return *I->second;
 173   }
 174
 175   DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
 176
 177   /// print - Print out the analysis results...
 178   ///
 179   void print(std::ostream &O, const Module *M) const;
 180
 181   /// If the pass pipeline is done with this pass, we can release our memory...
 182   ///
 183   virtual void releaseMyMemory();
 184
 185   /// getAnalysisUsage - This obviously provides a data structure graph.
 186   ///
 187   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 188     AU.setPreservesAll();
 189     AU.addRequired<BUDataStructures>();
 190   }
 191
 192 private:
 193   void markReachableFunctionsExternallyAccessible(DSNode *N,
 194                                                   hash_set<DSNode*> &Visited);
 195
 196   void inlineGraphIntoCallees(DSGraph &G);
 197   DSGraph &getOrCreateDSGraph(Function &F);
 198   void ComputePostOrder(Function &F, hash_set<DSGraph*> &Visited,
 199                         std::vector<DSGraph*> &PostOrder,
 200                         const BUDataStructures::ActualCalleesTy &ActualCallees);
 201 };
 202
 203
 204 /// CompleteBUDataStructures - This is the exact same as the bottom-up graphs,
 205 /// but we use take a completed call graph and inline all indirect callees into
 206 /// their callers graphs, making the result more useful for things like pool
 207 /// allocation.
 208 ///
 209 struct CompleteBUDataStructures : public BUDataStructures {
 210   virtual bool run(Module &M);
 211
 212   bool hasGraph(const Function &F) const {
 213     return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
 214   }
 215
 216   /// getDSGraph - Return the data structure graph for the specified function.
 217   ///
 218   DSGraph &getDSGraph(const Function &F) const {
 219     hash_map<Function*, DSGraph*>::const_iterator I =
 220       DSInfo.find(const_cast<Function*>(&F));
 221     assert(I != DSInfo.end() && "Function not in module!");
 222     return *I->second;
 223   }
 224
 225   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 226     AU.setPreservesAll();
 227     AU.addRequired<BUDataStructures>();
 228
 229     // FIXME: TEMPORARY (remove once finalization of indirect call sites in the
 230     // globals graph has been implemented in the BU pass)
 231     AU.addRequired<TDDataStructures>();
 232   }
 233
 234   /// print - Print out the analysis results...
 235   ///
 236   void print(std::ostream &O, const Module *M) const;
 237
 238 private:
 239   unsigned calculateSCCGraphs(DSGraph &FG, std::vector<DSGraph*> &Stack,
 240                               unsigned &NextID,
 241                               hash_map<DSGraph*, unsigned> &ValMap);
 242   DSGraph &getOrCreateGraph(Function &F);
 243   void processGraph(DSGraph &G);
 244 };
 245
 246 } // End llvm namespace
 247
 248 #endif