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