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 "llvm/ADT/hash_map"
  20 #include "llvm/ADT/hash_set"
  21
  22 namespace llvm {
  23
  24 class Type;
  25 class Instruction;
  26 class DSGraph;
  27 class DSNode;
  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 ModulePass {
  45   // DSInfo, one graph for each function
  46   hash_map<Function*, DSGraph*> DSInfo;
  47   DSGraph *GlobalsGraph;
  48 public:
  49   ~LocalDataStructures() { releaseMemory(); }
  50
  51   virtual bool runOnModule(Module &M);
  52
  53   bool hasGraph(const Function &F) const {
  54     return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
  55   }
  56
  57   /// getDSGraph - Return the data structure graph for the specified function.
  58   ///
  59   DSGraph &getDSGraph(const Function &F) const {
  60     hash_map<Function*, DSGraph*>::const_iterator I =
  61       DSInfo.find(const_cast<Function*>(&F));
  62     assert(I != DSInfo.end() && "Function not in module!");
  63     return *I->second;
  64   }
  65
  66   DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
  67
  68   /// print - Print out the analysis results...
  69   ///
  70   void print(std::ostream &O, const Module *M) const;
  71
  72   /// releaseMemory - if the pass pipeline is done with this pass, we can
  73   /// release our memory...
  74   ///
  75   virtual void releaseMemory();
  76
  77   /// getAnalysisUsage - This obviously provides a data structure graph.
  78   ///
  79   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  80     AU.setPreservesAll();
  81     AU.addRequired<TargetData>();
  82   }
  83 };
  84
  85
  86 /// BUDataStructures - The analysis that computes the interprocedurally closed
  87 /// data structure graphs for all of the functions in the program.  This pass
  88 /// only performs a "Bottom Up" propagation (hence the name).
  89 ///
  90 class BUDataStructures : public ModulePass {
  91 protected:
  92   // DSInfo, one graph for each function
  93   hash_map<Function*, DSGraph*> DSInfo;
  94   DSGraph *GlobalsGraph;
  95   hash_multimap<Instruction*, Function*> ActualCallees;
  96 public:
  97   ~BUDataStructures() { releaseMemory(); }
  98
  99   virtual bool runOnModule(Module &M);
 100
 101   bool hasGraph(const Function &F) const {
 102     return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
 103   }
 104
 105   /// getDSGraph - Return the data structure graph for the specified function.
 106   ///
 107   DSGraph &getDSGraph(const Function &F) const {
 108     hash_map<Function*, DSGraph*>::const_iterator I =
 109       DSInfo.find(const_cast<Function*>(&F));
 110     assert(I != DSInfo.end() && "Function not in module!");
 111     return *I->second;
 112   }
 113
 114   DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
 115
 116   /// deleteValue/copyValue - Interfaces to update the DSGraphs in the program.
 117   /// These correspond to the interfaces defined in the AliasAnalysis class.
 118   void deleteValue(Value *V);
 119   void copyValue(Value *From, Value *To);
 120
 121   /// print - Print out the analysis results...
 122   ///
 123   void print(std::ostream &O, const Module *M) const;
 124
 125   /// releaseMemory - if the pass pipeline is done with this pass, we can
 126   /// release our memory...
 127   ///
 128   virtual void releaseMemory();
 129
 130   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 131     AU.setPreservesAll();
 132     AU.addRequired<LocalDataStructures>();
 133   }
 134
 135   typedef hash_multimap<Instruction*, Function*> ActualCalleesTy;
 136   const ActualCalleesTy &getActualCallees() const {
 137     return ActualCallees;
 138   }
 139
 140 private:
 141   void calculateGraph(DSGraph &G);
 142
 143   void calculateReachableGraphs(Function *F);
 144
 145
 146   DSGraph &getOrCreateGraph(Function *F);
 147
 148   unsigned calculateGraphs(Function *F, std::vector<Function*> &Stack,
 149                            unsigned &NextID,
 150                            hash_map<Function*, unsigned> &ValMap);
 151 };
 152
 153
 154 /// TDDataStructures - Analysis that computes new data structure graphs
 155 /// for each function using the closed graphs for the callers computed
 156 /// by the bottom-up pass.
 157 ///
 158 class TDDataStructures : public ModulePass {
 159   // DSInfo, one graph for each function
 160   hash_map<Function*, DSGraph*> DSInfo;
 161   hash_set<Function*> ArgsRemainIncomplete;
 162   DSGraph *GlobalsGraph;
 163 public:
 164   ~TDDataStructures() { releaseMyMemory(); }
 165
 166   virtual bool runOnModule(Module &M);
 167
 168   bool hasGraph(const Function &F) const {
 169     return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
 170   }
 171
 172   /// getDSGraph - Return the data structure graph for the specified function.
 173   ///
 174   DSGraph &getDSGraph(const Function &F) const {
 175     hash_map<Function*, DSGraph*>::const_iterator I =
 176       DSInfo.find(const_cast<Function*>(&F));
 177     assert(I != DSInfo.end() && "Function not in module!");
 178     return *I->second;
 179   }
 180
 181   DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
 182
 183   /// deleteValue/copyValue - Interfaces to update the DSGraphs in the program.
 184   /// These correspond to the interfaces defined in the AliasAnalysis class.
 185   void deleteValue(Value *V);
 186   void copyValue(Value *From, Value *To);
 187
 188   /// print - Print out the analysis results...
 189   ///
 190   void print(std::ostream &O, const Module *M) const;
 191
 192   /// If the pass pipeline is done with this pass, we can release our memory...
 193   ///
 194   virtual void releaseMyMemory();
 195
 196   /// getAnalysisUsage - This obviously provides a data structure graph.
 197   ///
 198   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 199     AU.setPreservesAll();
 200     AU.addRequired<BUDataStructures>();
 201   }
 202
 203 private:
 204   void markReachableFunctionsExternallyAccessible(DSNode *N,
 205                                                   hash_set<DSNode*> &Visited);
 206
 207   void inlineGraphIntoCallees(DSGraph &G);
 208   DSGraph &getOrCreateDSGraph(Function &F);
 209   void ComputePostOrder(Function &F, hash_set<DSGraph*> &Visited,
 210                         std::vector<DSGraph*> &PostOrder,
 211                         const BUDataStructures::ActualCalleesTy &ActualCallees);
 212 };
 213
 214
 215 /// CompleteBUDataStructures - This is the exact same as the bottom-up graphs,
 216 /// but we use take a completed call graph and inline all indirect callees into
 217 /// their callers graphs, making the result more useful for things like pool
 218 /// allocation.
 219 ///
 220 struct CompleteBUDataStructures : public BUDataStructures {
 221   virtual bool runOnModule(Module &M);
 222
 223   bool hasGraph(const Function &F) const {
 224     return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
 225   }
 226
 227   /// getDSGraph - Return the data structure graph for the specified function.
 228   ///
 229   DSGraph &getDSGraph(const Function &F) const {
 230     hash_map<Function*, DSGraph*>::const_iterator I =
 231       DSInfo.find(const_cast<Function*>(&F));
 232     assert(I != DSInfo.end() && "Function not in module!");
 233     return *I->second;
 234   }
 235
 236   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 237     AU.setPreservesAll();
 238     AU.addRequired<BUDataStructures>();
 239
 240     // FIXME: TEMPORARY (remove once finalization of indirect call sites in the
 241     // globals graph has been implemented in the BU pass)
 242     AU.addRequired<TDDataStructures>();
 243   }
 244
 245   /// print - Print out the analysis results...
 246   ///
 247   void print(std::ostream &O, const Module *M) const;
 248
 249 private:
 250   unsigned calculateSCCGraphs(DSGraph &FG, std::vector<DSGraph*> &Stack,
 251                               unsigned &NextID,
 252                               hash_map<DSGraph*, unsigned> &ValMap);
 253   DSGraph &getOrCreateGraph(Function &F);
 254   void processGraph(DSGraph &G);
 255 };
 256
 257 } // End llvm namespace
 258
 259 #endif