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 //----------------------------------------------------------------------------
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
75 BitSetVector modNodeSet; // set of modified nodes
76 BitSetVector refNodeSet; // set of referenced nodes
79 // Methods to construct ModRefInfo objects.
80 ModRefInfo(unsigned int numNodes)
81 : modNodeSet(numNodes),
82 refNodeSet(numNodes) { }
84 unsigned getSize() const {
85 assert(modNodeSet.size() == refNodeSet.size() &&
86 "Mod & Ref different size?");
87 return modNodeSet.size();
90 void setNodeIsMod (unsigned nodeId) { modNodeSet[nodeId] = true; }
91 void setNodeIsRef (unsigned nodeId) { refNodeSet[nodeId] = true; }
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; }
98 const BitSetVector& getModSet() const { return modNodeSet; }
99 BitSetVector& getModSet() { return modNodeSet; }
101 const BitSetVector& getRefSet() const { return refNodeSet; }
102 BitSetVector& getRefSet() { return refNodeSet; }
104 // Debugging support methods
105 void print(std::ostream &O, const std::string& prefix=std::string("")) const;
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].
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;
126 friend class IPModRef;
128 void computeModRef(const Function &func);
129 void computeModRef(CallSite call);
131 ResolveCallSiteModRefInfo(CallSite CS,
132 hash_map<const DSNode*, DSNodeHandle> &NodeMap);
135 FunctionModRefInfo(const Function& func, IPModRef &IPModRefObj,
137 ~FunctionModRefInfo();
139 // Identify the function and its relevant DS graph
141 const Function& getFunction() const { return F; }
142 const DSGraph& getFuncGraph() const { return *funcTDGraph; }
144 // Retrieve Mod/Ref results for a single call site and for the function body
146 const ModRefInfo* getModRefInfo(const Function& func) const {
147 return &funcModRefInfo;
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;
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;
160 // Get the nodeIds used to index all Mod/Ref information for current function
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());
168 unsigned getNodeId(const Value* value) const;
170 // Debugging support methods
171 void print(std::ostream &O) const;
176 //----------------------------------------------------------------------------
177 /// IPModRef Class - An interprocedural pass that computes IP Mod/Ref info for
178 /// functions and for individual call sites.
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.
186 class IPModRef : public Pass {
187 std::map<const Function*, FunctionModRefInfo*> funcToModRefInfoMap;
190 FunctionModRefInfo& getFuncInfo(const Function& func,
191 bool computeIfMissing = false);
193 IPModRef() : M(NULL) {}
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.
200 virtual bool run(Module &M);
202 /// getFunctionModRefInfo - Retrieve the Mod/Ref information for a single
205 const FunctionModRefInfo& getFunctionModRefInfo(const Function& func) {
206 return getFuncInfo(func);
209 /// getBUDSGraph - This method returns the BU data structure graph for F
210 /// through the use of the BUDataStructures object.
212 const DSGraph &getBUDSGraph(const Function &F);
214 // Debugging support methods
216 void print(std::ostream &O) const;
219 /// releaseMemory - Release memory held by this pass when the pass pipeline is
222 virtual void releaseMemory();
224 /// getAnalysisUsage - This pass requires top-down data structure graphs.
225 /// It modifies nothing.
227 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
230 } // End llvm namespace