1 //===- MemoryDepAnalysis.cpp - Compute dep graph for memory ops --*-C++-*--===//
3 // This file implements a pass (MemoryDepAnalysis) that computes memory-based
4 // data dependences between instructions for each function in a module.
5 // Memory-based dependences occur due to load and store operations, but
6 // also the side-effects of call instructions.
8 // The result of this pass is a DependenceGraph for each function
9 // representing the memory-based data dependences between instructions.
10 //===----------------------------------------------------------------------===//
12 #include "llvm/Analysis/MemoryDepAnalysis.h"
13 #include "llvm/Analysis/IPModRef.h"
14 #include "llvm/Analysis/DataStructure.h"
15 #include "llvm/Analysis/DSGraph.h"
16 #include "llvm/Module.h"
17 #include "llvm/Function.h"
18 #include "llvm/iMemory.h"
19 #include "llvm/iOther.h"
20 #include "llvm/Support/InstVisitor.h"
21 #include "llvm/Support/CFG.h"
22 #include "Support/TarjanSCCIterator.h"
23 #include "Support/Statistic.h"
24 #include "Support/NonCopyable.h"
25 #include "Support/STLExtras.h"
26 #include "Support/hash_map"
27 #include "Support/hash_set"
31 ///--------------------------------------------------------------------------
32 /// struct ModRefTable:
34 /// A data structure that tracks ModRefInfo for instructions:
35 /// -- modRefMap is a map of Instruction* -> ModRefInfo for the instr.
36 /// -- definers is a vector of instructions that define any node
37 /// -- users is a vector of instructions that reference any node
38 /// -- numUsersBeforeDef is a vector indicating that the number of users
39 /// seen before definers[i] is numUsersBeforeDef[i].
41 /// numUsersBeforeDef[] effectively tells us the exact interleaving of
42 /// definers and users within the ModRefTable.
43 /// This is only maintained when constructing the table for one SCC, and
44 /// not copied over from one table to another since it is no longer useful.
45 ///--------------------------------------------------------------------------
49 typedef hash_map<Instruction*, ModRefInfo> ModRefMap;
50 typedef ModRefMap::const_iterator const_map_iterator;
51 typedef ModRefMap:: iterator map_iterator;
52 typedef std::vector<Instruction*>::const_iterator const_ref_iterator;
53 typedef std::vector<Instruction*>:: iterator ref_iterator;
56 std::vector<Instruction*> definers;
57 std::vector<Instruction*> users;
58 std::vector<unsigned> numUsersBeforeDef;
60 // Iterators to enumerate all the defining instructions
61 const_ref_iterator defsBegin() const { return definers.begin(); }
62 ref_iterator defsBegin() { return definers.begin(); }
63 const_ref_iterator defsEnd() const { return definers.end(); }
64 ref_iterator defsEnd() { return definers.end(); }
66 // Iterators to enumerate all the user instructions
67 const_ref_iterator usersBegin() const { return users.begin(); }
68 ref_iterator usersBegin() { return users.begin(); }
69 const_ref_iterator usersEnd() const { return users.end(); }
70 ref_iterator usersEnd() { return users.end(); }
72 // Iterator identifying the last user that was seen *before* a
73 // specified def. In particular, all users in the half-closed range
74 // [ usersBegin(), usersBeforeDef_End(defPtr) )
75 // were seen *before* the specified def. All users in the half-closed range
76 // [ usersBeforeDef_End(defPtr), usersEnd() )
77 // were seen *after* the specified def.
79 ref_iterator usersBeforeDef_End(const_ref_iterator defPtr) {
80 unsigned defIndex = (unsigned) (defPtr - defsBegin());
81 assert(defIndex < numUsersBeforeDef.size());
82 assert(usersBegin() + numUsersBeforeDef[defIndex] <= usersEnd());
83 return usersBegin() + numUsersBeforeDef[defIndex];
85 const_ref_iterator usersBeforeDef_End(const_ref_iterator defPtr) const {
86 return const_cast<ModRefTable*>(this)->usersBeforeDef_End(defPtr);
92 void AddDef(Instruction* D) {
93 definers.push_back(D);
94 numUsersBeforeDef.push_back(users.size());
96 void AddUse(Instruction* U) {
99 void Insert(const ModRefTable& fromTable) {
100 modRefMap.insert(fromTable.modRefMap.begin(), fromTable.modRefMap.end());
101 definers.insert(definers.end(),
102 fromTable.definers.begin(), fromTable.definers.end());
103 users.insert(users.end(),
104 fromTable.users.begin(), fromTable.users.end());
105 numUsersBeforeDef.clear(); /* fromTable.numUsersBeforeDef is ignored */
110 ///--------------------------------------------------------------------------
111 /// class ModRefInfoBuilder:
113 /// A simple InstVisitor<> class that retrieves the Mod/Ref info for
114 /// Load/Store/Call instructions and inserts this information in
115 /// a ModRefTable. It also records all instructions that Mod any node
116 /// and all that use any node.
117 ///--------------------------------------------------------------------------
119 class ModRefInfoBuilder: public InstVisitor<ModRefInfoBuilder>,
122 const DSGraph& funcGraph;
123 const FunctionModRefInfo& funcModRef;
124 ModRefTable& modRefTable;
126 ModRefInfoBuilder(); // do not implement
129 /*ctor*/ ModRefInfoBuilder(const DSGraph& _funcGraph,
130 const FunctionModRefInfo& _funcModRef,
131 ModRefTable& _modRefTable)
132 : funcGraph(_funcGraph), funcModRef(_funcModRef), modRefTable(_modRefTable)
136 // At a call instruction, retrieve the ModRefInfo using IPModRef results.
137 // Add the call to the defs list if it modifies any nodes and to the uses
138 // list if it refs any nodes.
140 void visitCallInst (CallInst& callInst) {
141 ModRefInfo safeModRef(funcGraph.getGraphSize());
142 const ModRefInfo* callModRef = funcModRef.getModRefInfo(callInst);
143 if (callModRef == NULL)
144 { // call to external/unknown function: mark all nodes as Mod and Ref
145 safeModRef.getModSet().set();
146 safeModRef.getRefSet().set();
147 callModRef = &safeModRef;
150 modRefTable.modRefMap.insert(std::make_pair(&callInst,
151 ModRefInfo(*callModRef)));
152 if (callModRef->getModSet().any())
153 modRefTable.AddDef(&callInst);
154 if (callModRef->getRefSet().any())
155 modRefTable.AddUse(&callInst);
158 // At a store instruction, add to the mod set the single node pointed to
159 // by the pointer argument of the store. Interestingly, if there is no
160 // such node, that would be a null pointer reference!
161 void visitStoreInst (StoreInst& storeInst) {
162 const DSNodeHandle& ptrNode =
163 funcGraph.getNodeForValue(storeInst.getPointerOperand());
164 if (const DSNode* target = ptrNode.getNode())
166 unsigned nodeId = funcModRef.getNodeId(target);
168 modRefTable.modRefMap.insert(
169 std::make_pair(&storeInst,
170 ModRefInfo(funcGraph.getGraphSize()))).first->second;
171 minfo.setNodeIsMod(nodeId);
172 modRefTable.AddDef(&storeInst);
175 std::cerr << "Warning: Uninitialized pointer reference!\n";
178 // At a load instruction, add to the ref set the single node pointed to
179 // by the pointer argument of the load. Interestingly, if there is no
180 // such node, that would be a null pointer reference!
181 void visitLoadInst (LoadInst& loadInst) {
182 const DSNodeHandle& ptrNode =
183 funcGraph.getNodeForValue(loadInst.getPointerOperand());
184 if (const DSNode* target = ptrNode.getNode())
186 unsigned nodeId = funcModRef.getNodeId(target);
188 modRefTable.modRefMap.insert(
189 std::make_pair(&loadInst,
190 ModRefInfo(funcGraph.getGraphSize()))).first->second;
191 minfo.setNodeIsRef(nodeId);
192 modRefTable.AddUse(&loadInst);
195 std::cerr << "Warning: Uninitialized pointer reference!\n";
200 //----------------------------------------------------------------------------
201 // class MemoryDepAnalysis: A dep. graph for load/store/call instructions
202 //----------------------------------------------------------------------------
204 /// Basic dependence gathering algorithm, using TarjanSCCIterator on CFG:
206 /// for every SCC S in the CFG in PostOrder on the SCC DAG
208 /// for every basic block BB in S in *postorder*
209 /// for every instruction I in BB in reverse
210 /// Add (I, ModRef[I]) to ModRefCurrent
211 /// if (Mod[I] != NULL)
212 /// Add I to DefSetCurrent: { I \in S : Mod[I] != NULL }
213 /// if (Ref[I] != NULL)
214 /// Add I to UseSetCurrent: { I : Ref[I] != NULL }
216 /// for every def D in DefSetCurrent
218 /// // NOTE: D comes after itself iff S contains a loop
219 /// if (HasLoop(S) && D & D)
220 /// Add output-dep: D -> D2
222 /// for every def D2 *after* D in DefSetCurrent
223 /// // NOTE: D2 comes before D in execution order
225 /// Add output-dep: D2 -> D
227 /// Add output-dep: D -> D2
229 /// for every use U in UseSetCurrent that was seen *before* D
230 /// // NOTE: U comes after D in execution order
232 /// if (U != D || HasLoop(S))
233 /// Add true-dep: D -> U
235 /// Add anti-dep: U -> D
237 /// for every use U in UseSetCurrent that was seen *after* D
238 /// // NOTE: U comes before D in execution order
240 /// if (U != D || HasLoop(S))
241 /// Add anti-dep: U -> D
243 /// Add true-dep: D -> U
245 /// for every def Dnext in DefSetAfter
246 /// // NOTE: Dnext comes after D in execution order
248 /// Add output-dep: D -> Dnext
250 /// for every use Unext in UseSetAfter
251 /// // NOTE: Unext comes after D in execution order
253 /// Add true-dep: D -> Unext
255 /// for every use U in UseSetCurrent
256 /// for every def Dnext in DefSetAfter
257 /// // NOTE: Dnext comes after U in execution order
259 /// Add anti-dep: U -> Dnext
261 /// Add ModRefCurrent to ModRefAfter: { (I, ModRef[I] ) }
262 /// Add DefSetCurrent to DefSetAfter: { I : Mod[I] != NULL }
263 /// Add UseSetCurrent to UseSetAfter: { I : Ref[I] != NULL }
268 void MemoryDepAnalysis::ProcessSCC(SCC<Function*>& S,
269 ModRefTable& ModRefAfter)
271 ModRefTable ModRefCurrent;
272 ModRefTable::ModRefMap& mapCurrent = ModRefCurrent.modRefMap;
273 ModRefTable::ModRefMap& mapAfter = ModRefAfter.modRefMap;
275 bool hasLoop = S.HasLoop();
277 // Builder class fills out a ModRefTable one instruction at a time.
278 // To use it, we just invoke it's visit function for each basic block:
280 // for each basic block BB in the SCC in *postorder*
281 // for each instruction I in BB in *reverse*
282 // ModRefInfoBuilder::visit(I)
283 // : Add (I, ModRef[I]) to ModRefCurrent.modRefMap
284 // : Add I to ModRefCurrent.definers if it defines any node
285 // : Add I to ModRefCurrent.users if it uses any node
287 ModRefInfoBuilder builder(*funcGraph, *funcModRef, ModRefCurrent);
288 for (SCC<Function*>::iterator BI=S.begin(), BE=S.end(); BI != BE; ++BI)
289 // Note: BBs in the SCC<> created by TarjanSCCIterator are in postorder.
290 for (BasicBlock::reverse_iterator II=(*BI)->rbegin(), IE=(*BI)->rend();
294 /// for every def D in DefSetCurrent
296 for (ModRefTable::ref_iterator II=ModRefCurrent.defsBegin(),
297 IE=ModRefCurrent.defsEnd(); II != IE; ++II)
299 /// // NOTE: D comes after itself iff S contains a loop
301 /// Add output-dep: D -> D2
303 funcDepGraph->AddSimpleDependence(**II, **II, OutputDependence);
305 /// for every def D2 *after* D in DefSetCurrent
306 /// // NOTE: D2 comes before D in execution order
308 /// Add output-dep: D2 -> D
310 /// Add output-dep: D -> D2
311 for (ModRefTable::ref_iterator JI=II+1; JI != IE; ++JI)
312 if (!Disjoint(mapCurrent.find(*II)->second.getModSet(),
313 mapCurrent.find(*JI)->second.getModSet()))
315 funcDepGraph->AddSimpleDependence(**JI, **II, OutputDependence);
317 funcDepGraph->AddSimpleDependence(**II, **JI, OutputDependence);
320 /// for every use U in UseSetCurrent that was seen *before* D
321 /// // NOTE: U comes after D in execution order
323 /// if (U != D || HasLoop(S))
324 /// Add true-dep: U -> D
326 /// Add anti-dep: D -> U
327 ModRefTable::ref_iterator JI=ModRefCurrent.usersBegin();
328 ModRefTable::ref_iterator JE = ModRefCurrent.usersBeforeDef_End(II);
329 for ( ; JI != JE; ++JI)
330 if (!Disjoint(mapCurrent.find(*II)->second.getModSet(),
331 mapCurrent.find(*JI)->second.getRefSet()))
333 if (*II != *JI || hasLoop)
334 funcDepGraph->AddSimpleDependence(**II, **JI, TrueDependence);
336 funcDepGraph->AddSimpleDependence(**JI, **II, AntiDependence);
339 /// for every use U in UseSetCurrent that was seen *after* D
340 /// // NOTE: U comes before D in execution order
342 /// if (U != D || HasLoop(S))
343 /// Add anti-dep: U -> D
345 /// Add true-dep: D -> U
346 for (/*continue JI*/ JE = ModRefCurrent.usersEnd(); JI != JE; ++JI)
347 if (!Disjoint(mapCurrent.find(*II)->second.getModSet(),
348 mapCurrent.find(*JI)->second.getRefSet()))
350 if (*II != *JI || hasLoop)
351 funcDepGraph->AddSimpleDependence(**JI, **II, AntiDependence);
353 funcDepGraph->AddSimpleDependence(**II, **JI, TrueDependence);
356 /// for every def Dnext in DefSetPrev
357 /// // NOTE: Dnext comes after D in execution order
359 /// Add output-dep: D -> Dnext
360 for (ModRefTable::ref_iterator JI=ModRefAfter.defsBegin(),
361 JE=ModRefAfter.defsEnd(); JI != JE; ++JI)
362 if (!Disjoint(mapCurrent.find(*II)->second.getModSet(),
363 mapAfter.find(*JI)->second.getModSet()))
364 funcDepGraph->AddSimpleDependence(**II, **JI, OutputDependence);
366 /// for every use Unext in UseSetAfter
367 /// // NOTE: Unext comes after D in execution order
369 /// Add true-dep: D -> Unext
370 for (ModRefTable::ref_iterator JI=ModRefAfter.usersBegin(),
371 JE=ModRefAfter.usersEnd(); JI != JE; ++JI)
372 if (!Disjoint(mapCurrent.find(*II)->second.getModSet(),
373 mapAfter.find(*JI)->second.getRefSet()))
374 funcDepGraph->AddSimpleDependence(**II, **JI, TrueDependence);
378 /// for every use U in UseSetCurrent
379 /// for every def Dnext in DefSetAfter
380 /// // NOTE: Dnext comes after U in execution order
382 /// Add anti-dep: U -> Dnext
383 for (ModRefTable::ref_iterator II=ModRefCurrent.usersBegin(),
384 IE=ModRefCurrent.usersEnd(); II != IE; ++II)
385 for (ModRefTable::ref_iterator JI=ModRefAfter.defsBegin(),
386 JE=ModRefAfter.defsEnd(); JI != JE; ++JI)
387 if (!Disjoint(mapCurrent.find(*II)->second.getRefSet(),
388 mapAfter.find(*JI)->second.getModSet()))
389 funcDepGraph->AddSimpleDependence(**II, **JI, AntiDependence);
391 /// Add ModRefCurrent to ModRefAfter: { (I, ModRef[I] ) }
392 /// Add DefSetCurrent to DefSetAfter: { I : Mod[I] != NULL }
393 /// Add UseSetCurrent to UseSetAfter: { I : Ref[I] != NULL }
394 ModRefAfter.Insert(ModRefCurrent);
398 /// Debugging support methods
400 void MemoryDepAnalysis::print(std::ostream &O) const
403 for (hash_map<Function*, DependenceGraph*>::const_iterator
404 I = funcMap.begin(), E = funcMap.end(); I != E; ++I)
406 Function* func = I->first;
407 DependenceGraph* depGraph = I->second;
409 O << "\n================================================================\n";
410 O << "DEPENDENCE GRAPH FOR MEMORY OPERATIONS IN FUNCTION " << func->getName();
411 O << "\n================================================================\n\n";
412 depGraph->print(*func, O);
419 /// Run the pass on a function
421 bool MemoryDepAnalysis::runOnFunction(Function& func)
423 assert(! func.isExternal());
425 // Get the FunctionModRefInfo holding IPModRef results for this function.
426 // Use the TD graph recorded within the FunctionModRefInfo object, which
427 // may not be the same as the original TD graph computed by DS analysis.
429 funcModRef = &getAnalysis<IPModRef>().getFunctionModRefInfo(func);
430 funcGraph = &funcModRef->getFuncGraph();
432 // TEMPORARY: ptr to depGraph (later just becomes "this").
433 assert(funcMap.find(&func) == funcMap.end() && "Analyzing function twice?");
434 funcDepGraph = funcMap[&func] = new DependenceGraph();
436 ModRefTable ModRefAfter;
438 SCC<Function*>* nextSCC;
439 for (TarjanSCC_iterator<Function*> tarjSCCiter = tarj_begin(&func);
440 (nextSCC = *tarjSCCiter) != NULL; ++tarjSCCiter)
441 ProcessSCC(*nextSCC, ModRefAfter);
447 //-------------------------------------------------------------------------
448 // TEMPORARY FUNCTIONS TO MAKE THIS A MODULE PASS ---
449 // These functions will go away once this class becomes a FunctionPass.
452 // Driver function to compute dependence graphs for every function.
453 // This is temporary and will go away once this is a FunctionPass.
455 bool MemoryDepAnalysis::run(Module& M)
457 for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI)
458 if (! FI->isExternal())
459 runOnFunction(*FI); // automatically inserts each depGraph into funcMap
463 // Release all the dependence graphs in the map.
464 void MemoryDepAnalysis::releaseMemory()
466 for (hash_map<Function*, DependenceGraph*>::const_iterator
467 I = funcMap.begin(), E = funcMap.end(); I != E; ++I)
471 // Clear pointers because the pass constructor will not be invoked again.
477 MemoryDepAnalysis::~MemoryDepAnalysis()
482 //----END TEMPORARY FUNCTIONS----------------------------------------------
485 void MemoryDepAnalysis::dump() const
487 this->print(std::cerr);
490 static RegisterAnalysis<MemoryDepAnalysis>
491 Z("memdep", "Memory Dependence Analysis");