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