LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

IPModRef.h

Go to the documentation of this file.
00001 //===- IPModRef.h - Compute IP Mod/Ref information --------------*- C++ -*-===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // class IPModRef:
00011 // 
00012 // class IPModRef is an interprocedural analysis pass that computes
00013 // flow-insensitive IP Mod and Ref information for every function
00014 // (the GMOD and GREF problems) and for every call site (MOD and REF).
00015 // 
00016 // In practice, this needs to do NO real interprocedural work because
00017 // all that is needed is done by the data structure analysis.
00018 // This uses the top-down DS graph for a function and the bottom-up DS graph
00019 // for each callee (including the Mod/Ref flags in the bottom-up graph)
00020 // to compute the set of nodes that are Mod and Ref for the function and
00021 // for each of its call sites.
00022 //
00023 // 
00024 // class FunctionModRefInfo:
00025 // 
00026 // The results of IPModRef are encapsulated in the class FunctionModRefInfo.
00027 // The results are stored as bit vectors: bit i represents node i
00028 // in the TD DSGraph for the current function.  (This node numbering is
00029 // implemented by class FunctionModRefInfo.)  Each FunctionModRefInfo
00030 // includes:
00031 // -- 2 bit vectors for the function (GMOD and GREF), and
00032 // -- 2 bit vectors for each call site (MOD and REF).
00033 //
00034 // 
00035 // IPModRef vs. Alias Analysis for Clients:
00036 // 
00037 // The IPModRef pass does not provide simpler query interfaces for specific
00038 // LLVM values, instructions, or pointers because those results should be
00039 // obtained through alias analysis (e.g., class DSAliasAnalysis).
00040 // class IPModRef is primarily meant for other analysis passes that need to
00041 // use Mod/Ref information efficiently for more complicated purposes;
00042 // the bit-vector representations make propagation very efficient.
00043 //
00044 //===----------------------------------------------------------------------===//
00045 
00046 #ifndef LLVM_ANALYSIS_IPMODREF_H
00047 #define LLVM_ANALYSIS_IPMODREF_H
00048 
00049 #include "llvm/Pass.h"
00050 #include "llvm/ADT/BitSetVector.h"
00051 #include "llvm/ADT/hash_map"
00052 
00053 namespace llvm {
00054 
00055 class Module;
00056 class Function;
00057 class CallSite;
00058 class Instruction;
00059 class CallInst;
00060 class InvokeInst;
00061 class DSNode;
00062 class DSGraph;
00063 class DSNodeHandle;
00064 class ModRefInfo;               // Result of IP Mod/Ref for one entity
00065 class FunctionModRefInfo;       // ModRefInfo for a func and all calls in it
00066 class IPModRef;                 // Pass that computes IP Mod/Ref info
00067 
00068 //----------------------------------------------------------------------------
00069 /// ModRefInfo Class - Representation of Mod/Ref information for a single
00070 /// function or callsite. This is represented as a pair of bit vectors, one each
00071 /// for Mod and Ref. Each bit vector is indexed by the node id of the DS graph
00072 /// node index.
00073 ///
00074 class ModRefInfo {
00075   BitSetVector   modNodeSet;            // set of modified nodes
00076   BitSetVector   refNodeSet;            // set of referenced nodes
00077   
00078 public:
00079   // Methods to construct ModRefInfo objects.
00080   ModRefInfo(unsigned int numNodes)
00081     : modNodeSet(numNodes),
00082       refNodeSet(numNodes) { }
00083 
00084   unsigned getSize() const {
00085     assert(modNodeSet.size() == refNodeSet.size() &&
00086            "Mod & Ref different size?");
00087     return modNodeSet.size();
00088   }
00089 
00090   void setNodeIsMod (unsigned nodeId)   { modNodeSet[nodeId] = true; }
00091   void setNodeIsRef (unsigned nodeId)   { refNodeSet[nodeId] = true; }
00092 
00093   // Methods to query the mod/ref info
00094   bool nodeIsMod (unsigned nodeId) const  { return modNodeSet.test(nodeId); }
00095   bool nodeIsRef (unsigned nodeId) const  { return refNodeSet.test(nodeId); }
00096   bool nodeIsKill(unsigned nodeId) const  { return false; }
00097 
00098   const BitSetVector&  getModSet() const  { return modNodeSet; }
00099         BitSetVector&  getModSet()        { return modNodeSet; }
00100 
00101   const BitSetVector&  getRefSet() const  { return refNodeSet; }
00102         BitSetVector&  getRefSet()        { return refNodeSet; }
00103 
00104   // Debugging support methods
00105   void print(std::ostream &O, const std::string& prefix=std::string("")) const;
00106   void dump() const;
00107 };
00108 
00109 
00110 //----------------------------------------------------------------------------
00111 /// FunctionModRefInfo Class - Representation of the results of IP Mod/Ref
00112 /// analysis for a function and for each of the call sites within the function.
00113 /// Each of these are represented as bit vectors of size = the number of nodes
00114 /// in the top-dwon DS graph of the function.  Nodes are identified by their
00115 /// nodeId, in the range [0 .. funcTDGraph.size()-1].
00116 ///
00117 class FunctionModRefInfo {
00118   const Function&       F;                  // The function
00119   IPModRef&             IPModRefObj;        // The IPModRef Object owning this
00120   DSGraph*              funcTDGraph;        // Top-down DS graph for function
00121   ModRefInfo            funcModRefInfo;     // ModRefInfo for the function body
00122   std::map<const Instruction*, ModRefInfo*>
00123                         callSiteModRefInfo; // ModRefInfo for each callsite
00124   std::map<const DSNode*, unsigned> NodeIds;
00125 
00126   friend class IPModRef;
00127 
00128   void computeModRef(const Function &func);
00129   void computeModRef(CallSite call);
00130   DSGraph*
00131   ResolveCallSiteModRefInfo(CallSite CS,
00132                             hash_map<const DSNode*, DSNodeHandle> &NodeMap);
00133 
00134 public:
00135   FunctionModRefInfo(const Function& func, IPModRef &IPModRefObj,
00136                      DSGraph* tdgClone);
00137   ~FunctionModRefInfo();
00138 
00139   // Identify the function and its relevant DS graph
00140   // 
00141   const Function& getFunction() const  { return F; }
00142   const DSGraph&  getFuncGraph() const { return *funcTDGraph; }
00143 
00144   // Retrieve Mod/Ref results for a single call site and for the function body
00145   // 
00146   const ModRefInfo* getModRefInfo(const Function& func) const {
00147     return &funcModRefInfo;
00148   }
00149   const ModRefInfo* getModRefInfo(const CallInst& callInst) const {
00150     std::map<const Instruction*, ModRefInfo*>::const_iterator I = 
00151       callSiteModRefInfo.find((Instruction*)&callInst);
00152     return (I == callSiteModRefInfo.end()) ? NULL : I->second;
00153   }
00154   const ModRefInfo* getModRefInfo(const InvokeInst& II) const {
00155     std::map<const Instruction*, ModRefInfo*>::const_iterator I = 
00156       callSiteModRefInfo.find((Instruction*)&II);
00157     return (I == callSiteModRefInfo.end()) ? NULL : I->second;
00158   }
00159 
00160   // Get the nodeIds used to index all Mod/Ref information for current function
00161   //
00162   unsigned getNodeId(const DSNode* node) const {
00163     std::map<const DSNode*, unsigned>::const_iterator iter = NodeIds.find(node);
00164     assert(iter != NodeIds.end() && iter->second < funcModRefInfo.getSize());
00165     return iter->second;
00166   }
00167 
00168   unsigned getNodeId(const Value* value) const;
00169 
00170   // Debugging support methods
00171   void print(std::ostream &O) const;
00172   void dump() const;
00173 };
00174 
00175 
00176 //----------------------------------------------------------------------------
00177 /// IPModRef Class - An interprocedural pass that computes IP Mod/Ref info for
00178 /// functions and for individual call sites.
00179 /// 
00180 /// Given the DSGraph of a function, this class can be queried for
00181 /// a ModRefInfo object describing all the nodes in the DSGraph that are
00182 /// (a) modified, and (b) referenced during an execution of the function
00183 /// from an arbitrary callsite, or during an execution of a single call-site
00184 /// within the function.
00185 ///
00186 class IPModRef : public ModulePass {
00187   std::map<const Function*, FunctionModRefInfo*> funcToModRefInfoMap;
00188   Module* M;
00189 
00190   FunctionModRefInfo& getFuncInfo(const Function& func,
00191                                   bool computeIfMissing = false);
00192 public:
00193   IPModRef() : M(NULL)  {}
00194   ~IPModRef()           {}
00195 
00196   /// run - Driver function to run IP Mod/Ref on a Module.
00197   /// This initializes the module reference, and then computes IPModRef
00198   /// results immediately if demand-driven analysis was *not* specified.
00199   /// 
00200   virtual bool runOnModule(Module &M);
00201 
00202   /// getFunctionModRefInfo - Retrieve the Mod/Ref information for a single
00203   /// function
00204   /// 
00205   const FunctionModRefInfo& getFunctionModRefInfo(const Function& func) {
00206     return getFuncInfo(func);
00207   }
00208 
00209   /// getBUDSGraph - This method returns the BU data structure graph for F
00210   /// through the use of the BUDataStructures object.
00211   ///
00212   const DSGraph &getBUDSGraph(const Function &F);
00213 
00214   // Debugging support methods
00215   // 
00216   void print(std::ostream &O) const;
00217   void dump() const;
00218 
00219   /// releaseMemory - Release memory held by this pass when the pass pipeline is
00220   /// done
00221   /// 
00222   virtual void releaseMemory();
00223 
00224   /// getAnalysisUsage - This pass requires top-down data structure graphs.
00225   /// It modifies nothing.
00226   /// 
00227   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
00228 };
00229 
00230 } // End llvm namespace
00231 
00232 #endif