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   /// print - Print out the analysis results...
 117   ///
 118   void print(std::ostream &O, const Module *M) const;
 119
 120   /// releaseMemory - if the pass pipeline is done with this pass, we can
 121   /// release our memory...
 122   ///
 123   virtual void releaseMemory();
 124
 125   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 126     AU.setPreservesAll();
 127     AU.addRequired<LocalDataStructures>();
 128   }
 129
 130   typedef hash_multimap<Instruction*, Function*> ActualCalleesTy;
 131   const ActualCalleesTy &getActualCallees() const {
 132     return ActualCallees;
 133   }
 134
 135 private:
 136   void calculateGraph(DSGraph &G);
 137
 138   void calculateReachableGraphs(Function *F);
 139
 140
 141   DSGraph &getOrCreateGraph(Function *F);
 142
 143   unsigned calculateGraphs(Function *F, std::vector<Function*> &Stack,
 144                            unsigned &NextID,
 145                            hash_map<Function*, unsigned> &ValMap);
 146 };
 147
 148
 149 /// TDDataStructures - Analysis that computes new data structure graphs
 150 /// for each function using the closed graphs for the callers computed
 151 /// by the bottom-up pass.
 152 ///
 153 class TDDataStructures : public ModulePass {
 154   // DSInfo, one graph for each function
 155   hash_map<Function*, DSGraph*> DSInfo;
 156   hash_set<Function*> ArgsRemainIncomplete;
 157   DSGraph *GlobalsGraph;
 158 public:
 159   ~TDDataStructures() { releaseMyMemory(); }
 160
 161   virtual bool runOnModule(Module &M);
 162
 163   bool hasGraph(const Function &F) const {
 164     return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
 165   }
 166
 167   /// getDSGraph - Return the data structure graph for the specified function.
 168   ///
 169   DSGraph &getDSGraph(const Function &F) const {
 170     hash_map<Function*, DSGraph*>::const_iterator I =
 171       DSInfo.find(const_cast<Function*>(&F));
 172     assert(I != DSInfo.end() && "Function not in module!");
 173     return *I->second;
 174   }
 175
 176   DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
 177
 178   /// print - Print out the analysis results...
 179   ///
 180   void print(std::ostream &O, const Module *M) const;
 181
 182   /// If the pass pipeline is done with this pass, we can release our memory...
 183   ///
 184   virtual void releaseMyMemory();
 185
 186   /// getAnalysisUsage - This obviously provides a data structure graph.
 187   ///
 188   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 189     AU.setPreservesAll();
 190     AU.addRequired<BUDataStructures>();
 191   }
 192
 193 private:
 194   void markReachableFunctionsExternallyAccessible(DSNode *N,
 195                                                   hash_set<DSNode*> &Visited);
 196
 197   void inlineGraphIntoCallees(DSGraph &G);
 198   DSGraph &getOrCreateDSGraph(Function &F);
 199   void ComputePostOrder(Function &F, hash_set<DSGraph*> &Visited,
 200                         std::vector<DSGraph*> &PostOrder,
 201                         const BUDataStructures::ActualCalleesTy &ActualCallees);
 202 };
 203
 204
 205 /// CompleteBUDataStructures - This is the exact same as the bottom-up graphs,
 206 /// but we use take a completed call graph and inline all indirect callees into
 207 /// their callers graphs, making the result more useful for things like pool
 208 /// allocation.
 209 ///
 210 struct CompleteBUDataStructures : public BUDataStructures {
 211   virtual bool runOnModule(Module &M);
 212
 213   bool hasGraph(const Function &F) const {
 214     return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
 215   }
 216
 217   /// getDSGraph - Return the data structure graph for the specified function.
 218   ///
 219   DSGraph &getDSGraph(const Function &F) const {
 220     hash_map<Function*, DSGraph*>::const_iterator I =
 221       DSInfo.find(const_cast<Function*>(&F));
 222     assert(I != DSInfo.end() && "Function not in module!");
 223     return *I->second;
 224   }
 225
 226   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 227     AU.setPreservesAll();
 228     AU.addRequired<BUDataStructures>();
 229
 230     // FIXME: TEMPORARY (remove once finalization of indirect call sites in the
 231     // globals graph has been implemented in the BU pass)
 232     AU.addRequired<TDDataStructures>();
 233   }
 234
 235   /// print - Print out the analysis results...
 236   ///
 237   void print(std::ostream &O, const Module *M) const;
 238
 239 private:
 240   unsigned calculateSCCGraphs(DSGraph &FG, std::vector<DSGraph*> &Stack,
 241                               unsigned &NextID,
 242                               hash_map<DSGraph*, unsigned> &ValMap);
 243   DSGraph &getOrCreateGraph(Function &F);
 244   void processGraph(DSGraph &G);
 245 };
 246
 247 } // End llvm namespace
 248
 249 #endif