1 //===- IPModRef.h - Compute IP Mod/Ref information --------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
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).
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.
24 // class FunctionModRefInfo:
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
31 // -- 2 bit vectors for the function (GMOD and GREF), and
32 // -- 2 bit vectors for each call site (MOD and REF).
35 // IPModRef vs. Alias Analysis for Clients:
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.
44 //===----------------------------------------------------------------------===//
46 #ifndef LLVM_ANALYSIS_IPMODREF_H
47 #define LLVM_ANALYSIS_IPMODREF_H
49 #include "llvm/Pass.h"
50 #include "Support/BitSetVector.h"
51 #include "Support/hash_map"
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
68 //---------------------------------------------------------------------------
72 // Representation of Mod/Ref information for a single function or callsite.
73 // This is represented as a pair of bit vectors, one each for Mod and Ref.
74 // Each bit vector is indexed by the node id of the DS graph node index.
75 //---------------------------------------------------------------------------
78 BitSetVector modNodeSet; // set of modified nodes
79 BitSetVector refNodeSet; // set of referenced nodes
83 // Methods to construct ModRefInfo objects.
85 ModRefInfo(unsigned int numNodes)
86 : modNodeSet(numNodes),
87 refNodeSet(numNodes) { }
89 unsigned getSize() const {
90 assert(modNodeSet.size() == refNodeSet.size() &&
91 "Mod & Ref different size?");
92 return modNodeSet.size();
95 void setNodeIsMod (unsigned nodeId) { modNodeSet[nodeId] = true; }
96 void setNodeIsRef (unsigned nodeId) { refNodeSet[nodeId] = true; }
99 // Methods to query the mod/ref info
101 bool nodeIsMod (unsigned nodeId) const { return modNodeSet.test(nodeId); }
102 bool nodeIsRef (unsigned nodeId) const { return refNodeSet.test(nodeId); }
103 bool nodeIsKill(unsigned nodeId) const { return false; }
105 const BitSetVector& getModSet() const { return modNodeSet; }
106 BitSetVector& getModSet() { return modNodeSet; }
108 const BitSetVector& getRefSet() const { return refNodeSet; }
109 BitSetVector& getRefSet() { return refNodeSet; }
111 // Debugging support methods
112 void print(std::ostream &O, const std::string& prefix=std::string("")) const;
117 //----------------------------------------------------------------------------
118 // class FunctionModRefInfo
120 // Representation of the results of IP Mod/Ref analysis for a function
121 // and for each of the call sites within the function.
122 // Each of these are represented as bit vectors of size = the number of
123 // nodes in the top-dwon DS graph of the function. Nodes are identified by
124 // their nodeId, in the range [0 .. funcTDGraph.size()-1].
125 //----------------------------------------------------------------------------
127 class FunctionModRefInfo {
128 const Function& F; // The function
129 IPModRef& IPModRefObj; // The IPModRef Object owning this
130 DSGraph* funcTDGraph; // Top-down DS graph for function
131 ModRefInfo funcModRefInfo; // ModRefInfo for the function body
132 std::map<const Instruction*, ModRefInfo*>
133 callSiteModRefInfo; // ModRefInfo for each callsite
134 std::map<const DSNode*, unsigned> NodeIds;
136 friend class IPModRef;
138 void computeModRef (const Function &func);
139 void computeModRef (CallSite call);
140 DSGraph *ResolveCallSiteModRefInfo(CallSite CS,
141 hash_map<const DSNode*, DSNodeHandle> &NodeMap);
144 /* ctor */ FunctionModRefInfo (const Function& func,
145 IPModRef& IPModRefObj,
147 /* dtor */ ~FunctionModRefInfo ();
149 // Identify the function and its relevant DS graph
151 const Function& getFunction() const { return F; }
152 const DSGraph& getFuncGraph() const { return *funcTDGraph; }
154 // Retrieve Mod/Ref results for a single call site and for the function body
156 const ModRefInfo* getModRefInfo (const Function& func) const {
157 return &funcModRefInfo;
159 const ModRefInfo* getModRefInfo (const CallInst& callInst) const {
160 std::map<const Instruction*, ModRefInfo*>::const_iterator I =
161 callSiteModRefInfo.find((Instruction*)&callInst);
162 return (I == callSiteModRefInfo.end()) ? NULL : I->second;
164 const ModRefInfo* getModRefInfo (const InvokeInst& II) const {
165 std::map<const Instruction*, ModRefInfo*>::const_iterator I =
166 callSiteModRefInfo.find((Instruction*)&II);
167 return (I == callSiteModRefInfo.end()) ? NULL : I->second;
170 // Get the nodeIds used to index all Mod/Ref information for current function
172 unsigned getNodeId (const DSNode* node) const {
173 std::map<const DSNode*, unsigned>::const_iterator iter = NodeIds.find(node);
174 assert(iter != NodeIds.end() && iter->second < funcModRefInfo.getSize());
178 unsigned getNodeId (const Value* value) const;
180 // Debugging support methods
181 void print(std::ostream &O) const;
186 //----------------------------------------------------------------------------
190 // An interprocedural pass that computes IP Mod/Ref info for functions and
191 // for individual call sites.
193 // Given the DSGraph of a function, this class can be queried for
194 // a ModRefInfo object describing all the nodes in the DSGraph that are
195 // (a) modified, and (b) referenced during an execution of the function
196 // from an arbitrary callsite, or during an execution of a single call-site
197 // within the function.
198 //----------------------------------------------------------------------------
200 class IPModRef : public Pass {
201 std::map<const Function*, FunctionModRefInfo*> funcToModRefInfoMap;
204 FunctionModRefInfo& getFuncInfo(const Function& func,
205 bool computeIfMissing = false);
207 IPModRef() : M(NULL) { }
210 // Driver function to run IP Mod/Ref on a Module.
211 // This initializes the module reference, and then computes IPModRef
212 // results immediately if demand-driven analysis was *not* specified.
214 virtual bool run(Module &M);
216 // Retrieve the Mod/Ref information for a single function
218 const FunctionModRefInfo& getFunctionModRefInfo(const Function& func) {
219 return getFuncInfo(func);
222 /// getBUDSGraph - This method returns the BU data structure graph for F
223 /// through the use of the BUDataStructures object.
225 const DSGraph &getBUDSGraph(const Function &F);
227 // Debugging support methods
229 void print(std::ostream &O) const;
232 // Release memory held by this pass when the pass pipeline is done
234 virtual void releaseMemory();
236 // getAnalysisUsage - This pass requires top-down data structure graphs.
237 // It modifies nothing.
239 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
242 //===----------------------------------------------------------------------===//
244 } // End llvm namespace