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