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/STLExtras.h"
25 #include "Support/hash_map"
26 #include "Support/hash_set"
30 ///--------------------------------------------------------------------------
31 /// struct ModRefTable:
33 /// A data structure that tracks ModRefInfo for instructions:
34 /// -- modRefMap is a map of Instruction* -> ModRefInfo for the instr.
35 /// -- definers is a vector of instructions that define any node
36 /// -- users is a vector of instructions that reference any node
37 /// -- numUsersBeforeDef is a vector indicating that the number of users
38 /// seen before definers[i] is numUsersBeforeDef[i].
40 /// numUsersBeforeDef[] effectively tells us the exact interleaving of
41 /// definers and users within the ModRefTable.
42 /// This is only maintained when constructing the table for one SCC, and
43 /// not copied over from one table to another since it is no longer useful.
44 ///--------------------------------------------------------------------------
48 typedef hash_map<Instruction*, ModRefInfo> ModRefMap;
49 typedef ModRefMap::const_iterator const_map_iterator;
50 typedef ModRefMap:: iterator map_iterator;
51 typedef std::vector<Instruction*>::const_iterator const_ref_iterator;
52 typedef std::vector<Instruction*>:: iterator ref_iterator;
55 std::vector<Instruction*> definers;
56 std::vector<Instruction*> users;
57 std::vector<unsigned> numUsersBeforeDef;
59 // Iterators to enumerate all the defining instructions
60 const_ref_iterator defsBegin() const { return definers.begin(); }
61 ref_iterator defsBegin() { return definers.begin(); }
62 const_ref_iterator defsEnd() const { return definers.end(); }
63 ref_iterator defsEnd() { return definers.end(); }
65 // Iterators to enumerate all the user instructions
66 const_ref_iterator usersBegin() const { return users.begin(); }
67 ref_iterator usersBegin() { return users.begin(); }
68 const_ref_iterator usersEnd() const { return users.end(); }
69 ref_iterator usersEnd() { return users.end(); }
71 // Iterator identifying the last user that was seen *before* a
72 // specified def. In particular, all users in the half-closed range
73 // [ usersBegin(), usersBeforeDef_End(defPtr) )
74 // were seen *before* the specified def. All users in the half-closed range
75 // [ usersBeforeDef_End(defPtr), usersEnd() )
76 // were seen *after* the specified def.
78 ref_iterator usersBeforeDef_End(const_ref_iterator defPtr) {
79 unsigned defIndex = (unsigned) (defPtr - defsBegin());
80 assert(defIndex < numUsersBeforeDef.size());
81 assert(usersBegin() + numUsersBeforeDef[defIndex] <= usersEnd());
82 return usersBegin() + numUsersBeforeDef[defIndex];
84 const_ref_iterator usersBeforeDef_End(const_ref_iterator defPtr) const {
85 return const_cast<ModRefTable*>(this)->usersBeforeDef_End(defPtr);
91 void AddDef(Instruction* D) {
92 definers.push_back(D);
93 numUsersBeforeDef.push_back(users.size());
95 void AddUse(Instruction* U) {
98 void Insert(const ModRefTable& fromTable) {
99 modRefMap.insert(fromTable.modRefMap.begin(), fromTable.modRefMap.end());
100 definers.insert(definers.end(),
101 fromTable.definers.begin(), fromTable.definers.end());
102 users.insert(users.end(),
103 fromTable.users.begin(), fromTable.users.end());
104 numUsersBeforeDef.clear(); /* fromTable.numUsersBeforeDef is ignored */
109 ///--------------------------------------------------------------------------
110 /// class ModRefInfoBuilder:
112 /// A simple InstVisitor<> class that retrieves the Mod/Ref info for
113 /// Load/Store/Call instructions and inserts this information in
114 /// a ModRefTable. It also records all instructions that Mod any node
115 /// and all that use any node.
116 ///--------------------------------------------------------------------------
118 class ModRefInfoBuilder : public InstVisitor<ModRefInfoBuilder> {
119 const DSGraph& funcGraph;
120 const FunctionModRefInfo& funcModRef;
121 ModRefTable& modRefTable;
123 ModRefInfoBuilder(); // DO NOT IMPLEMENT
124 ModRefInfoBuilder(const ModRefInfoBuilder&); // DO NOT IMPLEMENT
125 void operator=(const ModRefInfoBuilder&); // DO NOT IMPLEMENT
128 /*ctor*/ ModRefInfoBuilder(const DSGraph& _funcGraph,
129 const FunctionModRefInfo& _funcModRef,
130 ModRefTable& _modRefTable)
131 : funcGraph(_funcGraph), funcModRef(_funcModRef), modRefTable(_modRefTable)
135 // At a call instruction, retrieve the ModRefInfo using IPModRef results.
136 // Add the call to the defs list if it modifies any nodes and to the uses
137 // list if it refs any nodes.
139 void visitCallInst (CallInst& callInst) {
140 ModRefInfo safeModRef(funcGraph.getGraphSize());
141 const ModRefInfo* callModRef = funcModRef.getModRefInfo(callInst);
142 if (callModRef == NULL)
143 { // call to external/unknown function: mark all nodes as Mod and Ref
144 safeModRef.getModSet().set();
145 safeModRef.getRefSet().set();
146 callModRef = &safeModRef;
149 modRefTable.modRefMap.insert(std::make_pair(&callInst,
150 ModRefInfo(*callModRef)));
151 if (callModRef->getModSet().any())
152 modRefTable.AddDef(&callInst);
153 if (callModRef->getRefSet().any())
154 modRefTable.AddUse(&callInst);
157 // At a store instruction, add to the mod set the single node pointed to
158 // by the pointer argument of the store. Interestingly, if there is no
159 // such node, that would be a null pointer reference!
160 void visitStoreInst (StoreInst& storeInst) {
161 const DSNodeHandle& ptrNode =
162 funcGraph.getNodeForValue(storeInst.getPointerOperand());
163 if (const DSNode* target = ptrNode.getNode())
165 unsigned nodeId = funcModRef.getNodeId(target);
167 modRefTable.modRefMap.insert(
168 std::make_pair(&storeInst,
169 ModRefInfo(funcGraph.getGraphSize()))).first->second;
170 minfo.setNodeIsMod(nodeId);
171 modRefTable.AddDef(&storeInst);
174 std::cerr << "Warning: Uninitialized pointer reference!\n";
177 // At a load instruction, add to the ref set the single node pointed to
178 // by the pointer argument of the load. Interestingly, if there is no
179 // such node, that would be a null pointer reference!
180 void visitLoadInst (LoadInst& loadInst) {
181 const DSNodeHandle& ptrNode =
182 funcGraph.getNodeForValue(loadInst.getPointerOperand());
183 if (const DSNode* target = ptrNode.getNode())
185 unsigned nodeId = funcModRef.getNodeId(target);
187 modRefTable.modRefMap.insert(
188 std::make_pair(&loadInst,
189 ModRefInfo(funcGraph.getGraphSize()))).first->second;
190 minfo.setNodeIsRef(nodeId);
191 modRefTable.AddUse(&loadInst);
194 std::cerr << "Warning: Uninitialized pointer reference!\n";
199 //----------------------------------------------------------------------------
200 // class MemoryDepAnalysis: A dep. graph for load/store/call instructions
201 //----------------------------------------------------------------------------
203 /// Basic dependence gathering algorithm, using TarjanSCCIterator on CFG:
205 /// for every SCC S in the CFG in PostOrder on the SCC DAG
207 /// for every basic block BB in S in *postorder*
208 /// for every instruction I in BB in reverse
209 /// Add (I, ModRef[I]) to ModRefCurrent
210 /// if (Mod[I] != NULL)
211 /// Add I to DefSetCurrent: { I \in S : Mod[I] != NULL }
212 /// if (Ref[I] != NULL)
213 /// Add I to UseSetCurrent: { I : Ref[I] != NULL }
215 /// for every def D in DefSetCurrent
217 /// // NOTE: D comes after itself iff S contains a loop
218 /// if (HasLoop(S) && D & D)
219 /// Add output-dep: D -> D2
221 /// for every def D2 *after* D in DefSetCurrent
222 /// // NOTE: D2 comes before D in execution order
224 /// Add output-dep: D2 -> D
226 /// Add output-dep: D -> D2
228 /// for every use U in UseSetCurrent that was seen *before* D
229 /// // NOTE: U comes after D in execution order
231 /// if (U != D || HasLoop(S))
232 /// Add true-dep: D -> U
234 /// Add anti-dep: U -> D
236 /// for every use U in UseSetCurrent that was seen *after* D
237 /// // NOTE: U comes before D in execution order
239 /// if (U != D || HasLoop(S))
240 /// Add anti-dep: U -> D
242 /// Add true-dep: D -> U
244 /// for every def Dnext in DefSetAfter
245 /// // NOTE: Dnext comes after D in execution order
247 /// Add output-dep: D -> Dnext
249 /// for every use Unext in UseSetAfter
250 /// // NOTE: Unext comes after D in execution order
252 /// Add true-dep: D -> Unext
254 /// for every use U in UseSetCurrent
255 /// for every def Dnext in DefSetAfter
256 /// // NOTE: Dnext comes after U in execution order
258 /// Add anti-dep: U -> Dnext
260 /// Add ModRefCurrent to ModRefAfter: { (I, ModRef[I] ) }
261 /// Add DefSetCurrent to DefSetAfter: { I : Mod[I] != NULL }
262 /// Add UseSetCurrent to UseSetAfter: { I : Ref[I] != NULL }
267 void MemoryDepAnalysis::ProcessSCC(SCC<Function*>& S,
268 ModRefTable& ModRefAfter)
270 ModRefTable ModRefCurrent;
271 ModRefTable::ModRefMap& mapCurrent = ModRefCurrent.modRefMap;
272 ModRefTable::ModRefMap& mapAfter = ModRefAfter.modRefMap;
274 bool hasLoop = S.HasLoop();
276 // Builder class fills out a ModRefTable one instruction at a time.
277 // To use it, we just invoke it's visit function for each basic block:
279 // for each basic block BB in the SCC in *postorder*
280 // for each instruction I in BB in *reverse*
281 // ModRefInfoBuilder::visit(I)
282 // : Add (I, ModRef[I]) to ModRefCurrent.modRefMap
283 // : Add I to ModRefCurrent.definers if it defines any node
284 // : Add I to ModRefCurrent.users if it uses any node
286 ModRefInfoBuilder builder(*funcGraph, *funcModRef, ModRefCurrent);
287 for (SCC<Function*>::iterator BI=S.begin(), BE=S.end(); BI != BE; ++BI)
288 // Note: BBs in the SCC<> created by TarjanSCCIterator are in postorder.
289 for (BasicBlock::reverse_iterator II=(*BI)->rbegin(), IE=(*BI)->rend();
293 /// for every def D in DefSetCurrent
295 for (ModRefTable::ref_iterator II=ModRefCurrent.defsBegin(),
296 IE=ModRefCurrent.defsEnd(); II != IE; ++II)
298 /// // NOTE: D comes after itself iff S contains a loop
300 /// Add output-dep: D -> D2
302 funcDepGraph->AddSimpleDependence(**II, **II, OutputDependence);
304 /// for every def D2 *after* D in DefSetCurrent
305 /// // NOTE: D2 comes before D in execution order
307 /// Add output-dep: D2 -> D
309 /// Add output-dep: D -> D2
310 for (ModRefTable::ref_iterator JI=II+1; JI != IE; ++JI)
311 if (!Disjoint(mapCurrent.find(*II)->second.getModSet(),
312 mapCurrent.find(*JI)->second.getModSet()))
314 funcDepGraph->AddSimpleDependence(**JI, **II, OutputDependence);
316 funcDepGraph->AddSimpleDependence(**II, **JI, OutputDependence);
319 /// for every use U in UseSetCurrent that was seen *before* D
320 /// // NOTE: U comes after D in execution order
322 /// if (U != D || HasLoop(S))
323 /// Add true-dep: U -> D
325 /// Add anti-dep: D -> U
326 ModRefTable::ref_iterator JI=ModRefCurrent.usersBegin();
327 ModRefTable::ref_iterator JE = ModRefCurrent.usersBeforeDef_End(II);
328 for ( ; JI != JE; ++JI)
329 if (!Disjoint(mapCurrent.find(*II)->second.getModSet(),
330 mapCurrent.find(*JI)->second.getRefSet()))
332 if (*II != *JI || hasLoop)
333 funcDepGraph->AddSimpleDependence(**II, **JI, TrueDependence);
335 funcDepGraph->AddSimpleDependence(**JI, **II, AntiDependence);
338 /// for every use U in UseSetCurrent that was seen *after* D
339 /// // NOTE: U comes before D in execution order
341 /// if (U != D || HasLoop(S))
342 /// Add anti-dep: U -> D
344 /// Add true-dep: D -> U
345 for (/*continue JI*/ JE = ModRefCurrent.usersEnd(); JI != JE; ++JI)
346 if (!Disjoint(mapCurrent.find(*II)->second.getModSet(),
347 mapCurrent.find(*JI)->second.getRefSet()))
349 if (*II != *JI || hasLoop)
350 funcDepGraph->AddSimpleDependence(**JI, **II, AntiDependence);
352 funcDepGraph->AddSimpleDependence(**II, **JI, TrueDependence);
355 /// for every def Dnext in DefSetPrev
356 /// // NOTE: Dnext comes after D in execution order
358 /// Add output-dep: D -> Dnext
359 for (ModRefTable::ref_iterator JI=ModRefAfter.defsBegin(),
360 JE=ModRefAfter.defsEnd(); JI != JE; ++JI)
361 if (!Disjoint(mapCurrent.find(*II)->second.getModSet(),
362 mapAfter.find(*JI)->second.getModSet()))
363 funcDepGraph->AddSimpleDependence(**II, **JI, OutputDependence);
365 /// for every use Unext in UseSetAfter
366 /// // NOTE: Unext comes after D in execution order
368 /// Add true-dep: D -> Unext
369 for (ModRefTable::ref_iterator JI=ModRefAfter.usersBegin(),
370 JE=ModRefAfter.usersEnd(); JI != JE; ++JI)
371 if (!Disjoint(mapCurrent.find(*II)->second.getModSet(),
372 mapAfter.find(*JI)->second.getRefSet()))
373 funcDepGraph->AddSimpleDependence(**II, **JI, TrueDependence);
377 /// for every use U in UseSetCurrent
378 /// for every def Dnext in DefSetAfter
379 /// // NOTE: Dnext comes after U in execution order
381 /// Add anti-dep: U -> Dnext
382 for (ModRefTable::ref_iterator II=ModRefCurrent.usersBegin(),
383 IE=ModRefCurrent.usersEnd(); II != IE; ++II)
384 for (ModRefTable::ref_iterator JI=ModRefAfter.defsBegin(),
385 JE=ModRefAfter.defsEnd(); JI != JE; ++JI)
386 if (!Disjoint(mapCurrent.find(*II)->second.getRefSet(),
387 mapAfter.find(*JI)->second.getModSet()))
388 funcDepGraph->AddSimpleDependence(**II, **JI, AntiDependence);
390 /// Add ModRefCurrent to ModRefAfter: { (I, ModRef[I] ) }
391 /// Add DefSetCurrent to DefSetAfter: { I : Mod[I] != NULL }
392 /// Add UseSetCurrent to UseSetAfter: { I : Ref[I] != NULL }
393 ModRefAfter.Insert(ModRefCurrent);
397 /// Debugging support methods
399 void MemoryDepAnalysis::print(std::ostream &O) const
402 for (hash_map<Function*, DependenceGraph*>::const_iterator
403 I = funcMap.begin(), E = funcMap.end(); I != E; ++I)
405 Function* func = I->first;
406 DependenceGraph* depGraph = I->second;
408 O << "\n================================================================\n";
409 O << "DEPENDENCE GRAPH FOR MEMORY OPERATIONS IN FUNCTION " << func->getName();
410 O << "\n================================================================\n\n";
411 depGraph->print(*func, O);
418 /// Run the pass on a function
420 bool MemoryDepAnalysis::runOnFunction(Function& func)
422 assert(! func.isExternal());
424 // Get the FunctionModRefInfo holding IPModRef results for this function.
425 // Use the TD graph recorded within the FunctionModRefInfo object, which
426 // may not be the same as the original TD graph computed by DS analysis.
428 funcModRef = &getAnalysis<IPModRef>().getFunctionModRefInfo(func);
429 funcGraph = &funcModRef->getFuncGraph();
431 // TEMPORARY: ptr to depGraph (later just becomes "this").
432 assert(funcMap.find(&func) == funcMap.end() && "Analyzing function twice?");
433 funcDepGraph = funcMap[&func] = new DependenceGraph();
435 ModRefTable ModRefAfter;
437 SCC<Function*>* nextSCC;
438 for (TarjanSCC_iterator<Function*> tarjSCCiter = tarj_begin(&func);
439 (nextSCC = *tarjSCCiter) != NULL; ++tarjSCCiter)
440 ProcessSCC(*nextSCC, ModRefAfter);
446 //-------------------------------------------------------------------------
447 // TEMPORARY FUNCTIONS TO MAKE THIS A MODULE PASS ---
448 // These functions will go away once this class becomes a FunctionPass.
451 // Driver function to compute dependence graphs for every function.
452 // This is temporary and will go away once this is a FunctionPass.
454 bool MemoryDepAnalysis::run(Module& M)
456 for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI)
457 if (! FI->isExternal())
458 runOnFunction(*FI); // automatically inserts each depGraph into funcMap
462 // Release all the dependence graphs in the map.
463 void MemoryDepAnalysis::releaseMemory()
465 for (hash_map<Function*, DependenceGraph*>::const_iterator
466 I = funcMap.begin(), E = funcMap.end(); I != E; ++I)
470 // Clear pointers because the pass constructor will not be invoked again.
476 MemoryDepAnalysis::~MemoryDepAnalysis()
481 //----END TEMPORARY FUNCTIONS----------------------------------------------
484 void MemoryDepAnalysis::dump() const
486 this->print(std::cerr);
489 static RegisterAnalysis<MemoryDepAnalysis>
490 Z("memdep", "Memory Dependence Analysis");