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