1 //===- MemoryDependenceAnalysis.cpp - Mem Deps Implementation --*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements an analysis that determines, for a given memory
11 // operation, what preceding memory operations it depends on. It builds on
12 // alias analysis information, and tries to provide a lazy, caching interface to
13 // a common kind of alias information query.
15 //===----------------------------------------------------------------------===//
17 #define DEBUG_TYPE "memdep"
18 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
19 #include "llvm/Constants.h"
20 #include "llvm/Instructions.h"
21 #include "llvm/Function.h"
22 #include "llvm/Analysis/AliasAnalysis.h"
23 #include "llvm/ADT/Statistic.h"
24 #include "llvm/ADT/STLExtras.h"
25 #include "llvm/Support/CFG.h"
26 #include "llvm/Support/CommandLine.h"
27 #include "llvm/Support/Debug.h"
28 #include "llvm/Target/TargetData.h"
31 // Control the calculation of non-local dependencies by only examining the
32 // predecessors if the basic block has less than X amount (50 by default).
34 PredLimit("nonlocaldep-threshold", cl::Hidden, cl::init(50),
35 cl::desc("Control the calculation of non-local"
36 "dependencies (default = 50)"));
38 STATISTIC(NumCacheNonlocal, "Number of cached non-local responses");
39 STATISTIC(NumUncacheNonlocal, "Number of uncached non-local responses");
41 char MemoryDependenceAnalysis::ID = 0;
43 // Register this pass...
44 static RegisterPass<MemoryDependenceAnalysis> X("memdep",
45 "Memory Dependence Analysis", false, true);
47 /// verifyRemoved - Verify that the specified instruction does not occur
48 /// in our internal data structures.
49 void MemoryDependenceAnalysis::verifyRemoved(Instruction *D) const {
50 for (LocalDepMapType::const_iterator I = LocalDeps.begin(),
51 E = LocalDeps.end(); I != E; ++I) {
52 assert(I->first != D && "Inst occurs in data structures");
53 assert(I->second.getPointer() != D &&
54 "Inst occurs in data structures");
57 for (nonLocalDepMapType::const_iterator I = depGraphNonLocal.begin(),
58 E = depGraphNonLocal.end(); I != E; ++I) {
59 assert(I->first != D && "Inst occurs in data structures");
60 for (DenseMap<BasicBlock*, DepResultTy>::iterator II = I->second.begin(),
61 EE = I->second.end(); II != EE; ++II)
62 assert(II->second.getPointer() != D && "Inst occurs in data structures");
65 for (reverseDepMapType::const_iterator I = reverseDep.begin(),
66 E = reverseDep.end(); I != E; ++I)
67 for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(),
68 EE = I->second.end(); II != EE; ++II)
69 assert(*II != D && "Inst occurs in data structures");
71 for (reverseDepMapType::const_iterator I = reverseDepNonLocal.begin(),
72 E = reverseDepNonLocal.end();
74 for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(),
75 EE = I->second.end(); II != EE; ++II)
76 assert(*II != D && "Inst occurs in data structures");
79 /// getAnalysisUsage - Does not modify anything. It uses Alias Analysis.
81 void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
83 AU.addRequiredTransitive<AliasAnalysis>();
84 AU.addRequiredTransitive<TargetData>();
87 /// getCallSiteDependency - Private helper for finding the local dependencies
89 MemDepResult MemoryDependenceAnalysis::
90 getCallSiteDependency(CallSite C, BasicBlock::iterator ScanIt,
92 AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
93 TargetData &TD = getAnalysis<TargetData>();
95 // Walk backwards through the block, looking for dependencies
96 while (ScanIt != BB->begin()) {
97 Instruction *Inst = --ScanIt;
99 // If this inst is a memory op, get the pointer it accessed
101 uint64_t PointerSize = 0;
102 if (StoreInst *S = dyn_cast<StoreInst>(Inst)) {
103 Pointer = S->getPointerOperand();
104 PointerSize = TD.getTypeStoreSize(S->getOperand(0)->getType());
105 } else if (AllocationInst *AI = dyn_cast<AllocationInst>(Inst)) {
107 if (ConstantInt *C = dyn_cast<ConstantInt>(AI->getArraySize()))
108 PointerSize = C->getZExtValue() *
109 TD.getTypeStoreSize(AI->getAllocatedType());
112 } else if (VAArgInst *V = dyn_cast<VAArgInst>(Inst)) {
113 Pointer = V->getOperand(0);
114 PointerSize = TD.getTypeStoreSize(V->getType());
115 } else if (FreeInst *F = dyn_cast<FreeInst>(Inst)) {
116 Pointer = F->getPointerOperand();
118 // FreeInsts erase the entire structure
120 } else if (isa<CallInst>(Inst) || isa<InvokeInst>(Inst)) {
121 if (AA.getModRefBehavior(CallSite::get(Inst)) ==
122 AliasAnalysis::DoesNotAccessMemory)
124 return MemDepResult::get(Inst);
128 if (AA.getModRefInfo(C, Pointer, PointerSize) != AliasAnalysis::NoModRef)
129 return MemDepResult::get(Inst);
132 // No dependence found.
133 return MemDepResult::getNonLocal();
136 /// nonLocalHelper - Private helper used to calculate non-local dependencies
137 /// by doing DFS on the predecessors of a block to find its dependencies.
138 void MemoryDependenceAnalysis::nonLocalHelper(Instruction* query,
140 DenseMap<BasicBlock*, DepResultTy> &resp) {
141 // Set of blocks that we've already visited in our DFS
142 SmallPtrSet<BasicBlock*, 4> visited;
143 // If we're updating a dirtied cache entry, we don't need to reprocess
144 // already computed entries.
145 for (DenseMap<BasicBlock*, DepResultTy>::iterator I = resp.begin(),
146 E = resp.end(); I != E; ++I)
147 if (I->second.getInt() != Dirty)
148 visited.insert(I->first);
150 // Current stack of the DFS
151 SmallVector<BasicBlock*, 4> stack;
152 for (pred_iterator PI = pred_begin(block), PE = pred_end(block);
154 stack.push_back(*PI);
157 while (!stack.empty()) {
158 BasicBlock* BB = stack.back();
160 // If we've already visited this block, no need to revist
161 if (visited.count(BB)) {
166 // If we find a new block with a local dependency for query,
167 // then we insert the new dependency and backtrack.
171 MemDepResult localDep = getDependencyFrom(query, BB->end(), BB);
172 if (!localDep.isNonLocal()) {
173 resp.insert(std::make_pair(BB, ConvFromResult(localDep)));
177 // If we re-encounter the starting block, we still need to search it
178 // because there might be a dependency in the starting block AFTER
179 // the position of the query. This is necessary to get loops right.
180 } else if (BB == block) {
183 MemDepResult localDep = getDependencyFrom(query, BB->end(), BB);
184 if (localDep.getInst() != query)
185 resp.insert(std::make_pair(BB, ConvFromResult(localDep)));
191 // If we didn't find anything, recurse on the precessors of this block
192 // Only do this for blocks with a small number of predecessors.
193 bool predOnStack = false;
194 bool inserted = false;
195 if (std::distance(pred_begin(BB), pred_end(BB)) <= PredLimit) {
196 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
198 if (!visited.count(*PI)) {
199 stack.push_back(*PI);
205 // If we inserted a new predecessor, then we'll come back to this block
208 // If we didn't insert because we have no predecessors, then this
209 // query has no dependency at all.
210 else if (!inserted && !predOnStack) {
211 resp.insert(std::make_pair(BB, DepResultTy(0, None)));
212 // If we didn't insert because our predecessors are already on the stack,
213 // then we might still have a dependency, but it will be discovered during
215 } else if (!inserted && predOnStack){
216 resp.insert(std::make_pair(BB, DepResultTy(0, NonLocal)));
223 /// getNonLocalDependency - Fills the passed-in map with the non-local
224 /// dependencies of the queries. The map will contain NonLocal for
225 /// blocks between the query and its dependencies.
226 void MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query,
227 DenseMap<BasicBlock*, MemDepResult> &resp) {
228 if (depGraphNonLocal.count(query)) {
229 DenseMap<BasicBlock*, DepResultTy> &cached = depGraphNonLocal[query];
232 SmallVector<BasicBlock*, 4> dirtied;
233 for (DenseMap<BasicBlock*, DepResultTy>::iterator I = cached.begin(),
234 E = cached.end(); I != E; ++I)
235 if (I->second.getInt() == Dirty)
236 dirtied.push_back(I->first);
238 for (SmallVector<BasicBlock*, 4>::iterator I = dirtied.begin(),
239 E = dirtied.end(); I != E; ++I) {
240 MemDepResult localDep = getDependencyFrom(query, (*I)->end(), *I);
241 if (!localDep.isNonLocal())
242 cached[*I] = ConvFromResult(localDep);
245 nonLocalHelper(query, *I, cached);
249 // Update the reverse non-local dependency cache.
250 for (DenseMap<BasicBlock*, DepResultTy>::iterator I = cached.begin(),
251 E = cached.end(); I != E; ++I) {
252 if (Instruction *Inst = I->second.getPointer())
253 reverseDepNonLocal[Inst].insert(query);
254 resp[I->first] = ConvToResult(I->second);
260 NumUncacheNonlocal++;
262 // If not, go ahead and search for non-local deps.
263 DenseMap<BasicBlock*, DepResultTy> &cached = depGraphNonLocal[query];
264 nonLocalHelper(query, query->getParent(), cached);
266 // Update the non-local dependency cache
267 for (DenseMap<BasicBlock*, DepResultTy>::iterator I = cached.begin(),
268 E = cached.end(); I != E; ++I) {
269 // FIXME: Merge with the code above!
270 if (Instruction *Inst = I->second.getPointer())
271 reverseDepNonLocal[Inst].insert(query);
272 resp[I->first] = ConvToResult(I->second);
276 /// getDependency - Return the instruction on which a memory operation
277 /// depends. The local parameter indicates if the query should only
278 /// evaluate dependencies within the same basic block.
279 MemDepResult MemoryDependenceAnalysis::
280 getDependencyFrom(Instruction *QueryInst, BasicBlock::iterator ScanIt,
282 AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
283 TargetData &TD = getAnalysis<TargetData>();
285 // Get the pointer value for which dependence will be determined
287 uint64_t MemSize = 0;
288 bool MemVolatile = false;
290 if (StoreInst* S = dyn_cast<StoreInst>(QueryInst)) {
291 MemPtr = S->getPointerOperand();
292 MemSize = TD.getTypeStoreSize(S->getOperand(0)->getType());
293 MemVolatile = S->isVolatile();
294 } else if (LoadInst* L = dyn_cast<LoadInst>(QueryInst)) {
295 MemPtr = L->getPointerOperand();
296 MemSize = TD.getTypeStoreSize(L->getType());
297 MemVolatile = L->isVolatile();
298 } else if (VAArgInst* V = dyn_cast<VAArgInst>(QueryInst)) {
299 MemPtr = V->getOperand(0);
300 MemSize = TD.getTypeStoreSize(V->getType());
301 } else if (FreeInst* F = dyn_cast<FreeInst>(QueryInst)) {
302 MemPtr = F->getPointerOperand();
303 // FreeInsts erase the entire structure, not just a field.
305 } else if (isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst))
306 return getCallSiteDependency(CallSite::get(QueryInst), ScanIt, BB);
307 else // Non-memory instructions depend on nothing.
308 return MemDepResult::getNone();
310 // Walk backwards through the basic block, looking for dependencies
311 while (ScanIt != BB->begin()) {
312 Instruction *Inst = --ScanIt;
314 // If the access is volatile and this is a volatile load/store, return a
317 ((isa<LoadInst>(Inst) && cast<LoadInst>(Inst)->isVolatile()) ||
318 (isa<StoreInst>(Inst) && cast<StoreInst>(Inst)->isVolatile())))
319 return MemDepResult::get(Inst);
321 // MemDep is broken w.r.t. loads: it says that two loads of the same pointer
322 // depend on each other. :(
323 // FIXME: ELIMINATE THIS!
324 if (LoadInst *L = dyn_cast<LoadInst>(Inst)) {
325 Value *Pointer = L->getPointerOperand();
326 uint64_t PointerSize = TD.getTypeStoreSize(L->getType());
328 // If we found a pointer, check if it could be the same as our pointer
329 AliasAnalysis::AliasResult R =
330 AA.alias(Pointer, PointerSize, MemPtr, MemSize);
332 if (R == AliasAnalysis::NoAlias)
335 // May-alias loads don't depend on each other without a dependence.
336 if (isa<LoadInst>(QueryInst) && R == AliasAnalysis::MayAlias)
338 return MemDepResult::get(Inst);
341 // FIXME: This claims that an access depends on the allocation. This may
342 // make sense, but is dubious at best. It would be better to fix GVN to
343 // handle a 'None' Query.
344 if (AllocationInst *AI = dyn_cast<AllocationInst>(Inst)) {
346 uint64_t PointerSize;
347 if (ConstantInt *C = dyn_cast<ConstantInt>(AI->getArraySize()))
348 PointerSize = C->getZExtValue() *
349 TD.getTypeStoreSize(AI->getAllocatedType());
353 AliasAnalysis::AliasResult R =
354 AA.alias(Pointer, PointerSize, MemPtr, MemSize);
356 if (R == AliasAnalysis::NoAlias)
358 return MemDepResult::get(Inst);
362 // See if this instruction mod/ref's the pointer.
363 AliasAnalysis::ModRefResult MRR = AA.getModRefInfo(Inst, MemPtr, MemSize);
365 if (MRR == AliasAnalysis::NoModRef)
368 // Loads don't depend on read-only instructions.
369 if (isa<LoadInst>(QueryInst) && MRR == AliasAnalysis::Ref)
372 // Otherwise, there is a dependence.
373 return MemDepResult::get(Inst);
376 // If we found nothing, return the non-local flag.
377 return MemDepResult::getNonLocal();
380 /// getDependency - Return the instruction on which a memory operation
382 MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) {
383 Instruction *ScanPos = QueryInst;
385 // Check for a cached result
386 DepResultTy &LocalCache = LocalDeps[QueryInst];
388 // If the cached entry is non-dirty, just return it.
389 if (LocalCache.getInt() != Dirty)
390 return ConvToResult(LocalCache);
392 // Otherwise, if we have a dirty entry, we know we can start the scan at that
393 // instruction, which may save us some work.
394 if (Instruction *Inst = LocalCache.getPointer())
399 getDependencyFrom(QueryInst, ScanPos, QueryInst->getParent());
401 // Remember the result!
402 // FIXME: Don't convert back and forth! Make a shared helper function.
403 LocalCache = ConvFromResult(Res);
404 if (Instruction *I = Res.getInst())
405 reverseDep[I].insert(QueryInst);
411 /// dropInstruction - Remove an instruction from the analysis, making
412 /// absolutely conservative assumptions when updating the cache. This is
413 /// useful, for example when an instruction is changed rather than removed.
414 void MemoryDependenceAnalysis::dropInstruction(Instruction* drop) {
415 LocalDepMapType::iterator depGraphEntry = LocalDeps.find(drop);
416 if (depGraphEntry != LocalDeps.end())
417 if (Instruction *Inst = depGraphEntry->second.getPointer())
418 reverseDep[Inst].erase(drop);
420 // Drop dependency information for things that depended on this instr
421 SmallPtrSet<Instruction*, 4>& set = reverseDep[drop];
422 for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
426 LocalDeps.erase(drop);
427 reverseDep.erase(drop);
429 for (DenseMap<BasicBlock*, DepResultTy>::iterator DI =
430 depGraphNonLocal[drop].begin(), DE = depGraphNonLocal[drop].end();
432 if (Instruction *Inst = DI->second.getPointer())
433 reverseDepNonLocal[Inst].erase(drop);
435 if (reverseDepNonLocal.count(drop)) {
436 SmallPtrSet<Instruction*, 4>& set =
437 reverseDepNonLocal[drop];
438 for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
440 for (DenseMap<BasicBlock*, DepResultTy>::iterator DI =
441 depGraphNonLocal[*I].begin(), DE = depGraphNonLocal[*I].end();
443 if (DI->second == DepResultTy(drop, Normal))
444 // FIXME: Why not remember the old insertion point??
445 DI->second = DepResultTy(0, Dirty);
448 reverseDepNonLocal.erase(drop);
449 depGraphNonLocal.erase(drop);
452 /// removeInstruction - Remove an instruction from the dependence analysis,
453 /// updating the dependence of instructions that previously depended on it.
454 /// This method attempts to keep the cache coherent using the reverse map.
455 void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) {
456 // Walk through the Non-local dependencies, removing this one as the value
457 // for any cached queries.
458 for (DenseMap<BasicBlock*, DepResultTy>::iterator DI =
459 depGraphNonLocal[RemInst].begin(), DE = depGraphNonLocal[RemInst].end();
461 if (Instruction *Inst = DI->second.getPointer())
462 reverseDepNonLocal[Inst].erase(RemInst);
464 // Shortly after this, we will look for things that depend on RemInst. In
465 // order to update these, we'll need a new dependency to base them on. We
466 // could completely delete any entries that depend on this, but it is better
467 // to make a more accurate approximation where possible. Compute that better
468 // approximation if we can.
469 DepResultTy NewDependency;
471 // If we have a cached local dependence query for this instruction, remove it.
473 LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst);
474 if (LocalDepEntry != LocalDeps.end()) {
475 DepResultTy LocalDep = LocalDepEntry->second;
477 // Remove this local dependency info.
478 LocalDeps.erase(LocalDepEntry);
480 // Remove us from DepInst's reverse set now that the local dep info is gone.
481 if (Instruction *Inst = LocalDep.getPointer())
482 reverseDep[Inst].erase(RemInst);
484 // If we have unconfirmed info, don't trust it.
485 if (LocalDep.getInt() != Dirty) {
486 // If we have a confirmed non-local flag, use it.
487 if (LocalDep.getInt() == NonLocal || LocalDep.getInt() == None) {
488 // The only time this dependency is confirmed is if it is non-local.
489 NewDependency = LocalDep;
491 // If we have dep info for RemInst, set them to it.
492 Instruction *NDI = next(BasicBlock::iterator(LocalDep.getPointer()));
493 if (NDI != RemInst) // Don't use RemInst for the new dependency!
494 NewDependency = DepResultTy(NDI, Dirty);
499 // If we don't already have a local dependency answer for this instruction,
500 // use the immediate successor of RemInst. We use the successor because
501 // getDependence starts by checking the immediate predecessor of what is in
503 if (NewDependency == DepResultTy(0, Dirty))
504 NewDependency = DepResultTy(next(BasicBlock::iterator(RemInst)), Dirty);
506 // Loop over all of the things that depend on the instruction we're removing.
508 reverseDepMapType::iterator ReverseDepIt = reverseDep.find(RemInst);
509 if (ReverseDepIt != reverseDep.end()) {
510 SmallPtrSet<Instruction*, 4> &ReverseDeps = ReverseDepIt->second;
511 for (SmallPtrSet<Instruction*, 4>::iterator I = ReverseDeps.begin(),
512 E = ReverseDeps.end(); I != E; ++I) {
513 Instruction *InstDependingOnRemInst = *I;
515 // If we thought the instruction depended on itself (possible for
516 // unconfirmed dependencies) ignore the update.
517 if (InstDependingOnRemInst == RemInst) continue;
519 // Insert the new dependencies.
520 LocalDeps[InstDependingOnRemInst] = NewDependency;
522 // If our NewDependency is an instruction, make sure to remember that new
523 // things depend on it.
524 if (Instruction *Inst = NewDependency.getPointer())
525 reverseDep[Inst].insert(InstDependingOnRemInst);
527 reverseDep.erase(RemInst);
530 ReverseDepIt = reverseDepNonLocal.find(RemInst);
531 if (ReverseDepIt != reverseDepNonLocal.end()) {
532 SmallPtrSet<Instruction*, 4>& set = ReverseDepIt->second;
533 for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
535 for (DenseMap<BasicBlock*, DepResultTy>::iterator DI =
536 depGraphNonLocal[*I].begin(), DE = depGraphNonLocal[*I].end();
538 if (DI->second == DepResultTy(RemInst, Normal))
539 // FIXME: Why not remember the old insertion point??
540 DI->second = DepResultTy(0, Dirty);
541 reverseDepNonLocal.erase(ReverseDepIt);
544 depGraphNonLocal.erase(RemInst);
546 getAnalysis<AliasAnalysis>().deleteValue(RemInst);
548 DEBUG(verifyRemoved(RemInst));