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 CallSite;
  29 class DSGraph;
  30 class DSCallSite;
  31 class DSNode;
  32 class DSNodeHandle;
  33
  34 // FIXME: move this stuff to a private header
  35 namespace DataStructureAnalysis {
  36   /// isPointerType - Return true if this first class type is big enough to hold
  37   /// a pointer.
  38   ///
  39   bool isPointerType(const Type *Ty);
  40 }
  41
  42
  43 // LocalDataStructures - The analysis that computes the local data structure
  44 // graphs for all of the functions in the program.
  45 //
  46 // FIXME: This should be a Function pass that can be USED by a Pass, and would
  47 // be automatically preserved.  Until we can do that, this is a Pass.
  48 //
  49 class LocalDataStructures : public ModulePass {
  50   // DSInfo, one graph for each function
  51   hash_map<Function*, DSGraph*> DSInfo;
  52   DSGraph *GlobalsGraph;
  53
  54   /// GlobalECs - The equivalence classes for each global value that is merged
  55   /// with other global values in the DSGraphs.
  56   EquivalenceClasses<GlobalValue*> GlobalECs;
  57 public:
  58   ~LocalDataStructures() { releaseMemory(); }
  59
  60   virtual bool runOnModule(Module &M);
  61
  62   bool hasGraph(const Function &F) const {
  63     return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
  64   }
  65
  66   /// getDSGraph - Return the data structure graph for the specified function.
  67   ///
  68   DSGraph &getDSGraph(const Function &F) const {
  69     hash_map<Function*, DSGraph*>::const_iterator I =
  70       DSInfo.find(const_cast<Function*>(&F));
  71     assert(I != DSInfo.end() && "Function not in module!");
  72     return *I->second;
  73   }
  74
  75   DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
  76
  77   EquivalenceClasses<GlobalValue*> &getGlobalECs() { return GlobalECs; }
  78
  79   /// print - Print out the analysis results...
  80   ///
  81   void print(std::ostream &O, const Module *M) const;
  82
  83   /// releaseMemory - if the pass pipeline is done with this pass, we can
  84   /// release our memory...
  85   ///
  86   virtual void releaseMemory();
  87
  88   /// getAnalysisUsage - This obviously provides a data structure graph.
  89   ///
  90   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  91     AU.setPreservesAll();
  92     AU.addRequired<TargetData>();
  93   }
  94 };
  95
  96
  97 /// BUDataStructures - The analysis that computes the interprocedurally closed
  98 /// data structure graphs for all of the functions in the program.  This pass
  99 /// only performs a "Bottom Up" propagation (hence the name).
 100 ///
 101 class BUDataStructures : public ModulePass {
 102 protected:
 103   // DSInfo, one graph for each function
 104   hash_map<Function*, DSGraph*> DSInfo;
 105   DSGraph *GlobalsGraph;
 106   std::set<std::pair<Instruction*, Function*> > ActualCallees;
 107
 108   // This map is only maintained during construction of BU Graphs
 109   std::map<std::vector<Function*>,
 110            std::pair<DSGraph*, std::vector<DSNodeHandle> > > *IndCallGraphMap;
 111
 112   /// GlobalECs - The equivalence classes for each global value that is merged
 113   /// with other global values in the DSGraphs.
 114   EquivalenceClasses<GlobalValue*> GlobalECs;
 115 public:
 116   ~BUDataStructures() { releaseMyMemory(); }
 117
 118   virtual bool runOnModule(Module &M);
 119
 120   bool hasGraph(const Function &F) const {
 121     return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
 122   }
 123
 124   /// getDSGraph - Return the data structure graph for the specified function.
 125   ///
 126   DSGraph &getDSGraph(const Function &F) const {
 127     hash_map<Function*, DSGraph*>::const_iterator I =
 128       DSInfo.find(const_cast<Function*>(&F));
 129     assert(I != DSInfo.end() && "Function not in module!");
 130     return *I->second;
 131   }
 132
 133   DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
 134
 135   EquivalenceClasses<GlobalValue*> &getGlobalECs() { return GlobalECs; }
 136
 137
 138   /// deleteValue/copyValue - Interfaces to update the DSGraphs in the program.
 139   /// These correspond to the interfaces defined in the AliasAnalysis class.
 140   void deleteValue(Value *V);
 141   void copyValue(Value *From, Value *To);
 142
 143   /// print - Print out the analysis results...
 144   ///
 145   void print(std::ostream &O, const Module *M) const;
 146
 147   // FIXME: Once the pass manager is straightened out, rename this to
 148   // releaseMemory.
 149   void releaseMyMemory();
 150
 151   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 152     AU.setPreservesAll();
 153     AU.addRequired<LocalDataStructures>();
 154   }
 155
 156   typedef std::set<std::pair<Instruction*, Function*> > ActualCalleesTy;
 157   const ActualCalleesTy &getActualCallees() const {
 158     return ActualCallees;
 159   }
 160
 161   typedef ActualCalleesTy::const_iterator callee_iterator;
 162   callee_iterator callee_begin(Instruction *I) const {
 163     return ActualCallees.lower_bound(std::pair<Instruction*,Function*>(I, 0));
 164   }
 165
 166   callee_iterator callee_end(Instruction *I) const {
 167     I = (Instruction*)((char*)I + 1);
 168     return ActualCallees.lower_bound(std::pair<Instruction*,Function*>(I, 0));
 169   }
 170
 171 private:
 172   void calculateGraph(DSGraph &G);
 173
 174   DSGraph &getOrCreateGraph(Function *F);
 175
 176   unsigned calculateGraphs(Function *F, std::vector<Function*> &Stack,
 177                            unsigned &NextID,
 178                            hash_map<Function*, unsigned> &ValMap);
 179 };
 180
 181
 182 /// TDDataStructures - Analysis that computes new data structure graphs
 183 /// for each function using the closed graphs for the callers computed
 184 /// by the bottom-up pass.
 185 ///
 186 class TDDataStructures : public ModulePass {
 187   // DSInfo, one graph for each function
 188   hash_map<Function*, DSGraph*> DSInfo;
 189   hash_set<Function*> ArgsRemainIncomplete;
 190   DSGraph *GlobalsGraph;
 191   BUDataStructures *BUInfo;
 192
 193   /// GlobalECs - The equivalence classes for each global value that is merged
 194   /// with other global values in the DSGraphs.
 195   EquivalenceClasses<GlobalValue*> GlobalECs;
 196
 197   /// CallerCallEdges - For a particular graph, we keep a list of these records
 198   /// which indicates which graphs call this function and from where.
 199   struct CallerCallEdge {
 200     DSGraph *CallerGraph;        // The graph of the caller function.
 201     const DSCallSite *CS;        // The actual call site.
 202     Function *CalledFunction;    // The actual function being called.
 203
 204     CallerCallEdge(DSGraph *G, const DSCallSite *cs, Function *CF)
 205       : CallerGraph(G), CS(cs), CalledFunction(CF) {}
 206
 207     bool operator<(const CallerCallEdge &RHS) const {
 208       return CallerGraph < RHS.CallerGraph ||
 209             (CallerGraph == RHS.CallerGraph && CS < RHS.CS);
 210     }
 211   };
 212
 213   std::map<DSGraph*, std::vector<CallerCallEdge> > CallerEdges;
 214
 215
 216   // IndCallMap - We memoize the results of indirect call inlining operations
 217   // that have multiple targets here to avoid N*M inlining.  The key to the map
 218   // is a sorted set of callee functions, the value is the DSGraph that holds
 219   // all of the caller graphs merged together, and the DSCallSite to merge with
 220   // the arguments for each function.
 221   std::map<std::vector<Function*>, DSGraph*> IndCallMap;
 222
 223 public:
 224   ~TDDataStructures() { releaseMyMemory(); }
 225
 226   virtual bool runOnModule(Module &M);
 227
 228   bool hasGraph(const Function &F) const {
 229     return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
 230   }
 231
 232   /// getDSGraph - Return the data structure graph for the specified function.
 233   ///
 234   DSGraph &getDSGraph(const Function &F) const {
 235     hash_map<Function*, DSGraph*>::const_iterator I =
 236       DSInfo.find(const_cast<Function*>(&F));
 237     assert(I != DSInfo.end() && "Function not in module!");
 238     return *I->second;
 239   }
 240
 241   DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
 242   EquivalenceClasses<GlobalValue*> &getGlobalECs() { return GlobalECs; }
 243
 244
 245   /// deleteValue/copyValue - Interfaces to update the DSGraphs in the program.
 246   /// These correspond to the interfaces defined in the AliasAnalysis class.
 247   void deleteValue(Value *V);
 248   void copyValue(Value *From, Value *To);
 249
 250   /// print - Print out the analysis results...
 251   ///
 252   void print(std::ostream &O, const Module *M) const;
 253
 254   /// If the pass pipeline is done with this pass, we can release our memory...
 255   ///
 256   virtual void releaseMyMemory();
 257
 258   /// getAnalysisUsage - This obviously provides a data structure graph.
 259   ///
 260   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 261     AU.setPreservesAll();
 262     AU.addRequired<BUDataStructures>();
 263   }
 264
 265 private:
 266   void markReachableFunctionsExternallyAccessible(DSNode *N,
 267                                                   hash_set<DSNode*> &Visited);
 268
 269   void InlineCallersIntoGraph(DSGraph &G);
 270   DSGraph &getOrCreateDSGraph(Function &F);
 271   void ComputePostOrder(Function &F, hash_set<DSGraph*> &Visited,
 272                         std::vector<DSGraph*> &PostOrder);
 273 };
 274
 275
 276 /// CompleteBUDataStructures - This is the exact same as the bottom-up graphs,
 277 /// but we use take a completed call graph and inline all indirect callees into
 278 /// their callers graphs, making the result more useful for things like pool
 279 /// allocation.
 280 ///
 281 struct CompleteBUDataStructures : public BUDataStructures {
 282   virtual bool runOnModule(Module &M);
 283
 284   bool hasGraph(const Function &F) const {
 285     return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
 286   }
 287
 288   /// getDSGraph - Return the data structure graph for the specified function.
 289   ///
 290   DSGraph &getDSGraph(const Function &F) const {
 291     hash_map<Function*, DSGraph*>::const_iterator I =
 292       DSInfo.find(const_cast<Function*>(&F));
 293     assert(I != DSInfo.end() && "Function not in module!");
 294     return *I->second;
 295   }
 296
 297   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 298     AU.setPreservesAll();
 299     AU.addRequired<BUDataStructures>();
 300
 301     // FIXME: TEMPORARY (remove once finalization of indirect call sites in the
 302     // globals graph has been implemented in the BU pass)
 303     AU.addRequired<TDDataStructures>();
 304   }
 305
 306   /// print - Print out the analysis results...
 307   ///
 308   void print(std::ostream &O, const Module *M) const;
 309
 310 private:
 311   unsigned calculateSCCGraphs(DSGraph &FG, std::vector<DSGraph*> &Stack,
 312                               unsigned &NextID,
 313                               hash_map<DSGraph*, unsigned> &ValMap);
 314   DSGraph &getOrCreateGraph(Function &F);
 315   void processGraph(DSGraph &G);
 316 };
 317
 318
 319 /// EquivClassGraphs - This is the same as the complete bottom-up graphs, but
 320 /// with functions partitioned into equivalence classes and a single merged
 321 /// DS graph for all functions in an equivalence class.  After this merging,
 322 /// graphs are inlined bottom-up on the SCCs of the final (CBU) call graph.
 323 ///
 324 struct EquivClassGraphs : public ModulePass {
 325   CompleteBUDataStructures *CBU;
 326
 327   DSGraph *GlobalsGraph;
 328
 329   // DSInfo - one graph for each function.
 330   hash_map<const Function*, DSGraph*> DSInfo;
 331
 332   /// ActualCallees - The actual functions callable from indirect call sites.
 333   ///
 334   std::set<std::pair<Instruction*, Function*> > ActualCallees;
 335
 336   // Equivalence class where functions that can potentially be called via the
 337   // same function pointer are in the same class.
 338   EquivalenceClasses<Function*> FuncECs;
 339
 340   /// OneCalledFunction - For each indirect call, we keep track of one
 341   /// target of the call.  This is used to find equivalence class called by
 342   /// a call site.
 343   std::map<DSNode*, Function *> OneCalledFunction;
 344
 345   /// GlobalECs - The equivalence classes for each global value that is merged
 346   /// with other global values in the DSGraphs.
 347   EquivalenceClasses<GlobalValue*> GlobalECs;
 348
 349 public:
 350   /// EquivClassGraphs - Computes the equivalence classes and then the
 351   /// folded DS graphs for each class.
 352   ///
 353   virtual bool runOnModule(Module &M);
 354
 355   /// print - Print out the analysis results...
 356   ///
 357   void print(std::ostream &O, const Module *M) const;
 358
 359   EquivalenceClasses<GlobalValue*> &getGlobalECs() { return GlobalECs; }
 360
 361   /// getDSGraph - Return the data structure graph for the specified function.
 362   /// This returns the folded graph.  The folded graph is the same as the CBU
 363   /// graph iff the function is in a singleton equivalence class AND all its
 364   /// callees also have the same folded graph as the CBU graph.
 365   ///
 366   DSGraph &getDSGraph(const Function &F) const {
 367     hash_map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
 368     assert(I != DSInfo.end() && "No graph computed for that function!");
 369     return *I->second;
 370   }
 371
 372   bool hasGraph(const Function &F) const {
 373     return DSInfo.find(&F) != DSInfo.end();
 374   }
 375
 376   /// ContainsDSGraphFor - Return true if we have a graph for the specified
 377   /// function.
 378   bool ContainsDSGraphFor(const Function &F) const {
 379     return DSInfo.find(&F) != DSInfo.end();
 380   }
 381
 382   /// getSomeCalleeForCallSite - Return any one callee function at
 383   /// a call site.
 384   ///
 385   Function *getSomeCalleeForCallSite(const CallSite &CS) const;
 386
 387   DSGraph &getGlobalsGraph() const {
 388     return *GlobalsGraph;
 389   }
 390
 391   typedef std::set<std::pair<Instruction*, Function*> > ActualCalleesTy;
 392   const ActualCalleesTy &getActualCallees() const {
 393     return ActualCallees;
 394   }
 395
 396   typedef ActualCalleesTy::const_iterator callee_iterator;
 397   callee_iterator callee_begin(Instruction *I) const {
 398     return ActualCallees.lower_bound(std::pair<Instruction*,Function*>(I, 0));
 399   }
 400
 401   callee_iterator callee_end(Instruction *I) const {
 402     I = (Instruction*)((char*)I + 1);
 403     return ActualCallees.lower_bound(std::pair<Instruction*,Function*>(I, 0));
 404   }
 405
 406   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 407     AU.setPreservesAll();
 408     AU.addRequired<CompleteBUDataStructures>();
 409   }
 410
 411 private:
 412   void buildIndirectFunctionSets(Module &M);
 413
 414   unsigned processSCC(DSGraph &FG, std::vector<DSGraph*> &Stack,
 415                       unsigned &NextID,
 416                       std::map<DSGraph*, unsigned> &ValMap);
 417   void processGraph(DSGraph &FG);
 418
 419   DSGraph &getOrCreateGraph(Function &F);
 420 };
 421
 422 } // End llvm namespace
 423
 424 #endif