lib/Analysis/DataStructure/IPModRef.h

   1 //===- IPModRef.h - Compute IP Mod/Ref information --------------*- 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 // class IPModRef:
  11 //
  12 // class IPModRef is an interprocedural analysis pass that computes
  13 // flow-insensitive IP Mod and Ref information for every function
  14 // (the GMOD and GREF problems) and for every call site (MOD and REF).
  15 //
  16 // In practice, this needs to do NO real interprocedural work because
  17 // all that is needed is done by the data structure analysis.
  18 // This uses the top-down DS graph for a function and the bottom-up DS graph
  19 // for each callee (including the Mod/Ref flags in the bottom-up graph)
  20 // to compute the set of nodes that are Mod and Ref for the function and
  21 // for each of its call sites.
  22 //
  23 //
  24 // class FunctionModRefInfo:
  25 //
  26 // The results of IPModRef are encapsulated in the class FunctionModRefInfo.
  27 // The results are stored as bit vectors: bit i represents node i
  28 // in the TD DSGraph for the current function.  (This node numbering is
  29 // implemented by class FunctionModRefInfo.)  Each FunctionModRefInfo
  30 // includes:
  31 // -- 2 bit vectors for the function (GMOD and GREF), and
  32 // -- 2 bit vectors for each call site (MOD and REF).
  33 //
  34 //
  35 // IPModRef vs. Alias Analysis for Clients:
  36 //
  37 // The IPModRef pass does not provide simpler query interfaces for specific
  38 // LLVM values, instructions, or pointers because those results should be
  39 // obtained through alias analysis (e.g., class DSAliasAnalysis).
  40 // class IPModRef is primarily meant for other analysis passes that need to
  41 // use Mod/Ref information efficiently for more complicated purposes;
  42 // the bit-vector representations make propagation very efficient.
  43 //
  44 //===----------------------------------------------------------------------===//
  45
  46 #ifndef LLVM_ANALYSIS_IPMODREF_H
  47 #define LLVM_ANALYSIS_IPMODREF_H
  48
  49 #include "llvm/Pass.h"
  50 #include "llvm/ADT/BitSetVector.h"
  51 #include "llvm/ADT/hash_map"
  52
  53 namespace llvm {
  54
  55 class Module;
  56 class Function;
  57 class CallSite;
  58 class Instruction;
  59 class CallInst;
  60 class InvokeInst;
  61 class DSNode;
  62 class DSGraph;
  63 class DSNodeHandle;
  64 class ModRefInfo;               // Result of IP Mod/Ref for one entity
  65 class FunctionModRefInfo;       // ModRefInfo for a func and all calls in it
  66 class IPModRef;                 // Pass that computes IP Mod/Ref info
  67
  68 //----------------------------------------------------------------------------
  69 /// ModRefInfo Class - Representation of Mod/Ref information for a single
  70 /// function or callsite. This is represented as a pair of bit vectors, one each
  71 /// for Mod and Ref. Each bit vector is indexed by the node id of the DS graph
  72 /// node index.
  73 ///
  74 class ModRefInfo {
  75   BitSetVector   modNodeSet;            // set of modified nodes
  76   BitSetVector   refNodeSet;            // set of referenced nodes
  77
  78 public:
  79   // Methods to construct ModRefInfo objects.
  80   ModRefInfo(unsigned int numNodes)
  81     : modNodeSet(numNodes),
  82       refNodeSet(numNodes) { }
  83
  84   unsigned getSize() const {
  85     assert(modNodeSet.size() == refNodeSet.size() &&
  86            "Mod & Ref different size?");
  87     return modNodeSet.size();
  88   }
  89
  90   void setNodeIsMod (unsigned nodeId)   { modNodeSet[nodeId] = true; }
  91   void setNodeIsRef (unsigned nodeId)   { refNodeSet[nodeId] = true; }
  92
  93   // Methods to query the mod/ref info
  94   bool nodeIsMod (unsigned nodeId) const  { return modNodeSet.test(nodeId); }
  95   bool nodeIsRef (unsigned nodeId) const  { return refNodeSet.test(nodeId); }
  96   bool nodeIsKill(unsigned nodeId) const  { return false; }
  97
  98   const BitSetVector&  getModSet() const  { return modNodeSet; }
  99         BitSetVector&  getModSet()        { return modNodeSet; }
 100
 101   const BitSetVector&  getRefSet() const  { return refNodeSet; }
 102         BitSetVector&  getRefSet()        { return refNodeSet; }
 103
 104   // Debugging support methods
 105   void print(std::ostream &O, const std::string& prefix=std::string("")) const;
 106   void dump() const;
 107 };
 108
 109
 110 //----------------------------------------------------------------------------
 111 /// FunctionModRefInfo Class - Representation of the results of IP Mod/Ref
 112 /// analysis for a function and for each of the call sites within the function.
 113 /// Each of these are represented as bit vectors of size = the number of nodes
 114 /// in the top-dwon DS graph of the function.  Nodes are identified by their
 115 /// nodeId, in the range [0 .. funcTDGraph.size()-1].
 116 ///
 117 class FunctionModRefInfo {
 118   const Function&       F;                  // The function
 119   IPModRef&             IPModRefObj;        // The IPModRef Object owning this
 120   DSGraph*              funcTDGraph;        // Top-down DS graph for function
 121   ModRefInfo            funcModRefInfo;     // ModRefInfo for the function body
 122   std::map<const Instruction*, ModRefInfo*>
 123                         callSiteModRefInfo; // ModRefInfo for each callsite
 124   std::map<const DSNode*, unsigned> NodeIds;
 125
 126   friend class IPModRef;
 127
 128   void computeModRef(const Function &func);
 129   void computeModRef(CallSite call);
 130   DSGraph*
 131   ResolveCallSiteModRefInfo(CallSite CS,
 132                             hash_map<const DSNode*, DSNodeHandle> &NodeMap);
 133
 134 public:
 135   FunctionModRefInfo(const Function& func, IPModRef &IPModRefObj,
 136                      DSGraph* tdgClone);
 137   ~FunctionModRefInfo();
 138
 139   // Identify the function and its relevant DS graph
 140   //
 141   const Function& getFunction() const  { return F; }
 142   const DSGraph&  getFuncGraph() const { return *funcTDGraph; }
 143
 144   // Retrieve Mod/Ref results for a single call site and for the function body
 145   //
 146   const ModRefInfo* getModRefInfo(const Function& func) const {
 147     return &funcModRefInfo;
 148   }
 149   const ModRefInfo* getModRefInfo(const CallInst& callInst) const {
 150     std::map<const Instruction*, ModRefInfo*>::const_iterator I =
 151       callSiteModRefInfo.find((Instruction*)&callInst);
 152     return (I == callSiteModRefInfo.end()) ? NULL : I->second;
 153   }
 154   const ModRefInfo* getModRefInfo(const InvokeInst& II) const {
 155     std::map<const Instruction*, ModRefInfo*>::const_iterator I =
 156       callSiteModRefInfo.find((Instruction*)&II);
 157     return (I == callSiteModRefInfo.end()) ? NULL : I->second;
 158   }
 159
 160   // Get the nodeIds used to index all Mod/Ref information for current function
 161   //
 162   unsigned getNodeId(const DSNode* node) const {
 163     std::map<const DSNode*, unsigned>::const_iterator iter = NodeIds.find(node);
 164     assert(iter != NodeIds.end() && iter->second < funcModRefInfo.getSize());
 165     return iter->second;
 166   }
 167
 168   unsigned getNodeId(const Value* value) const;
 169
 170   // Debugging support methods
 171   void print(std::ostream &O) const;
 172   void dump() const;
 173 };
 174
 175
 176 //----------------------------------------------------------------------------
 177 /// IPModRef Class - An interprocedural pass that computes IP Mod/Ref info for
 178 /// functions and for individual call sites.
 179 ///
 180 /// Given the DSGraph of a function, this class can be queried for
 181 /// a ModRefInfo object describing all the nodes in the DSGraph that are
 182 /// (a) modified, and (b) referenced during an execution of the function
 183 /// from an arbitrary callsite, or during an execution of a single call-site
 184 /// within the function.
 185 ///
 186 class IPModRef : public Pass {
 187   std::map<const Function*, FunctionModRefInfo*> funcToModRefInfoMap;
 188   Module* M;
 189
 190   FunctionModRefInfo& getFuncInfo(const Function& func,
 191                                   bool computeIfMissing = false);
 192 public:
 193   IPModRef() : M(NULL)  {}
 194   ~IPModRef()           {}
 195
 196   /// run - Driver function to run IP Mod/Ref on a Module.
 197   /// This initializes the module reference, and then computes IPModRef
 198   /// results immediately if demand-driven analysis was *not* specified.
 199   ///
 200   virtual bool run(Module &M);
 201
 202   /// getFunctionModRefInfo - Retrieve the Mod/Ref information for a single
 203   /// function
 204   ///
 205   const FunctionModRefInfo& getFunctionModRefInfo(const Function& func) {
 206     return getFuncInfo(func);
 207   }
 208
 209   /// getBUDSGraph - This method returns the BU data structure graph for F
 210   /// through the use of the BUDataStructures object.
 211   ///
 212   const DSGraph &getBUDSGraph(const Function &F);
 213
 214   // Debugging support methods
 215   //
 216   void print(std::ostream &O) const;
 217   void dump() const;
 218
 219   /// releaseMemory - Release memory held by this pass when the pass pipeline is
 220   /// done
 221   ///
 222   virtual void releaseMemory();
 223
 224   /// getAnalysisUsage - This pass requires top-down data structure graphs.
 225   /// It modifies nothing.
 226   ///
 227   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 228 };
 229
 230 } // End llvm namespace
 231
 232 #endif