1 //===- IPModRef.h - Compute IP Mod/Ref information --------------*- C++ -*-===//
5 // class IPModRef is an interprocedural analysis pass that computes
6 // flow-insensitive IP Mod and Ref information for every function
7 // (the GMOD and GREF problems) and for every call site (MOD and REF).
9 // In practice, this needs to do NO real interprocedural work because
10 // all that is needed is done by the data structure analysis.
11 // This uses the top-down DS graph for a function and the bottom-up DS graph
12 // for each callee (including the Mod/Ref flags in the bottom-up graph)
13 // to compute the set of nodes that are Mod and Ref for the function and
14 // for each of its call sites.
17 // class FunctionModRefInfo:
19 // The results of IPModRef are encapsulated in the class FunctionModRefInfo.
20 // The results are stored as bit vectors: bit i represents node i
21 // in the TD DSGraph for the current function. (This node numbering is
22 // implemented by class FunctionModRefInfo.) Each FunctionModRefInfo
24 // -- 2 bit vectors for the function (GMOD and GREF), and
25 // -- 2 bit vectors for each call site (MOD and REF).
28 // IPModRef vs. Alias Analysis for Clients:
30 // The IPModRef pass does not provide simpler query interfaces for specific
31 // LLVM values, instructions, or pointers because those results should be
32 // obtained through alias analysis (e.g., class DSAliasAnalysis).
33 // class IPModRef is primarily meant for other analysis passes that need to
34 // use Mod/Ref information efficiently for more complicated purposes;
35 // the bit-vector representations make propagation very efficient.
36 //===----------------------------------------------------------------------===//
39 #ifndef LLVM_ANALYSIS_IPMODREF_H
40 #define LLVM_ANALYSIS_IPMODREF_H
43 #include "llvm/Analysis/DataStructure.h"
44 #include "llvm/Analysis/DSGraph.h"
45 #include "llvm/Pass.h"
46 #include "Support/BitSetVector.h"
47 #include "Support/NonCopyable.h"
53 class ModRefInfo; // Result of IP Mod/Ref for one entity
54 class FunctionModRefInfo; // ModRefInfo for a func and all calls in it
55 class IPModRef; // Pass that computes IP Mod/Ref info
58 //---------------------------------------------------------------------------
62 // Representation of Mod/Ref information for a single function or callsite.
63 // This is represented as a pair of bit vectors, one each for Mod and Ref.
64 // Each bit vector is indexed by the node id of the DS graph node index.
65 //---------------------------------------------------------------------------
68 BitSetVector modNodeSet; // set of modified nodes
69 BitSetVector refNodeSet; // set of referenced nodes
73 // Methods to construct ModRefInfo objects.
75 ModRefInfo(unsigned int numNodes)
76 : modNodeSet(numNodes),
77 refNodeSet(numNodes) { }
79 void setNodeIsMod (unsigned nodeId) { modNodeSet[nodeId] = true; }
80 void setNodeIsRef (unsigned nodeId) { refNodeSet[nodeId] = true; }
83 // Methods to query the mod/ref info
85 bool nodeIsMod (unsigned nodeId) const { return modNodeSet.test(nodeId); }
86 bool nodeIsRef (unsigned nodeId) const { return refNodeSet.test(nodeId); }
87 bool nodeIsKill(unsigned nodeId) const { return false; }
89 const BitSetVector& getModSet() const { return modNodeSet; }
90 BitSetVector& getModSet() { return modNodeSet; }
92 const BitSetVector& getRefSet() const { return refNodeSet; }
93 BitSetVector& getRefSet() { return refNodeSet; }
95 // Debugging support methods
96 void print(std::ostream &O) const;
101 //----------------------------------------------------------------------------
102 // class FunctionModRefInfo
104 // Representation of the results of IP Mod/Ref analysis for a function
105 // and for each of the call sites within the function.
106 // Each of these are represented as bit vectors of size = the number of
107 // nodes in the top-dwon DS graph of the function. Nodes are identified by
108 // their nodeId, in the range [0 .. funcTDGraph.size()-1].
109 //----------------------------------------------------------------------------
111 class FunctionModRefInfo {
112 const Function& F; // The function
113 const DSGraph& funcTDGraph; // Top-down DS graph for function
114 const DSGraph& funcLocalGraph; // Local DS graph for function
115 ModRefInfo funcModRefInfo; // ModRefInfo for the function body
116 std::map<const CallInst*, ModRefInfo*>
117 callSiteModRefInfo; // ModRefInfo for each callsite
118 std::map<const DSNode*, unsigned> NodeIds;
120 friend class IPModRef;
122 void computeModRef (const Function &func);
123 void computeModRef (const CallInst& callInst);
126 /* ctor */ FunctionModRefInfo (const Function& func,
129 /* dtor */ ~FunctionModRefInfo ();
131 // Identify the function and its relevant DS graph
133 const Function& getFunction() const { return F; }
134 const DSGraph& getFuncGraph() const { return funcTDGraph; }
136 // Retrieve Mod/Ref results for a single call site and for the function body
138 const ModRefInfo* getModRefInfo (const Function& func) const {
139 return &funcModRefInfo;
141 const ModRefInfo* getModRefInfo (const CallInst& callInst) const {
142 std::map<const CallInst*, ModRefInfo*>::const_iterator I =
143 callSiteModRefInfo.find(&callInst);
144 return (I == callSiteModRefInfo.end())? NULL : I->second;
147 // Get the nodeIds used to index all Mod/Ref information for current function
149 unsigned getNodeId (const DSNode* node) const {
150 std::map<const DSNode*, unsigned>::const_iterator iter = NodeIds.find(node);
151 assert(iter == NodeIds.end() || iter->second < funcTDGraph.getGraphSize());
152 return (iter == NodeIds.end())? funcTDGraph.getGraphSize() : iter->second;
154 unsigned getNodeId (const Value* value) const {
155 return getNodeId(funcTDGraph.getNodeForValue(const_cast<Value*>(value))
159 // Debugging support methods
160 void print(std::ostream &O) const;
165 //----------------------------------------------------------------------------
169 // An interprocedural pass that computes IP Mod/Ref info for functions and
170 // for individual call sites.
172 // Given the DSGraph of a function, this class can be queried for
173 // a ModRefInfo object describing all the nodes in the DSGraph that are
174 // (a) modified, and (b) referenced during an execution of the function
175 // from an arbitrary callsite, or during an execution of a single call-site
176 // within the function.
177 //----------------------------------------------------------------------------
179 class IPModRef : public Pass {
180 std::map<const Function*, FunctionModRefInfo*> funcToModRefInfoMap;
183 FunctionModRefInfo& getFuncInfo(const Function& func,
184 bool computeIfMissing = false)
186 FunctionModRefInfo*& funcInfo = funcToModRefInfoMap[&func];
187 assert (funcInfo != NULL || computeIfMissing);
188 if (funcInfo == NULL && computeIfMissing)
189 { // Create a new FunctionModRefInfo object
190 funcInfo = new FunctionModRefInfo(func, // inserts into map
191 getAnalysis<TDDataStructures>().getDSGraph(func),
192 getAnalysis<LocalDataStructures>().getDSGraph(func));
193 funcInfo->computeModRef(func); // computes the mod/ref info
199 IPModRef() : M(NULL) { }
202 // Driver function to run IP Mod/Ref on a Module.
203 // This initializes the module reference, and then computes IPModRef
204 // results immediately if demand-driven analysis was *not* specified.
206 virtual bool run(Module &M);
208 // Retrieve the Mod/Ref information for a single function
210 const FunctionModRefInfo& getFunctionModRefInfo(const Function& func) {
211 return getFuncInfo(func);
214 // Debugging support methods
216 void print(std::ostream &O) const;
219 // Release memory held by this pass when the pass pipeline is done
221 virtual void releaseMemory();
223 // getAnalysisUsage - This pass requires top-down data structure graphs.
224 // It modifies nothing.
226 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
227 AU.setPreservesAll();
228 AU.addRequired<LocalDataStructures>();
229 AU.addRequired<TDDataStructures>();
233 //===----------------------------------------------------------------------===//