LLVM API Documentation
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