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 STATISTIC(NumCacheNonlocal, "Number of cached non-local responses");
32 STATISTIC(NumUncacheNonlocal, "Number of uncached non-local responses");
34 char MemoryDependenceAnalysis::ID = 0;
36 // Register this pass...
37 static RegisterPass<MemoryDependenceAnalysis> X("memdep",
38 "Memory Dependence Analysis", false, true);
40 /// verifyRemoved - Verify that the specified instruction does not occur
41 /// in our internal data structures.
42 void MemoryDependenceAnalysis::verifyRemoved(Instruction *D) const {
43 for (LocalDepMapType::const_iterator I = LocalDeps.begin(),
44 E = LocalDeps.end(); I != E; ++I) {
45 assert(I->first != D && "Inst occurs in data structures");
46 assert(I->second.getPointer() != D &&
47 "Inst occurs in data structures");
50 for (NonLocalDepMapType::const_iterator I = NonLocalDeps.begin(),
51 E = NonLocalDeps.end(); I != E; ++I) {
52 assert(I->first != D && "Inst occurs in data structures");
53 for (DenseMap<BasicBlock*, DepResultTy>::iterator II = I->second.begin(),
54 EE = I->second.end(); II != EE; ++II)
55 assert(II->second.getPointer() != D && "Inst occurs in data structures");
58 for (ReverseDepMapType::const_iterator I = ReverseLocalDeps.begin(),
59 E = ReverseLocalDeps.end(); I != E; ++I)
60 for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(),
61 EE = I->second.end(); II != EE; ++II)
62 assert(*II != D && "Inst occurs in data structures");
64 for (ReverseDepMapType::const_iterator I = ReverseNonLocalDeps.begin(),
65 E = ReverseNonLocalDeps.end();
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");
72 /// getAnalysisUsage - Does not modify anything. It uses Alias Analysis.
74 void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
76 AU.addRequiredTransitive<AliasAnalysis>();
77 AU.addRequiredTransitive<TargetData>();
80 /// getCallSiteDependency - Private helper for finding the local dependencies
82 MemDepResult MemoryDependenceAnalysis::
83 getCallSiteDependency(CallSite C, BasicBlock::iterator ScanIt,
85 AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
86 TargetData &TD = getAnalysis<TargetData>();
88 // Walk backwards through the block, looking for dependencies
89 while (ScanIt != BB->begin()) {
90 Instruction *Inst = --ScanIt;
92 // If this inst is a memory op, get the pointer it accessed
94 uint64_t PointerSize = 0;
95 if (StoreInst *S = dyn_cast<StoreInst>(Inst)) {
96 Pointer = S->getPointerOperand();
97 PointerSize = TD.getTypeStoreSize(S->getOperand(0)->getType());
98 } else if (AllocationInst *AI = dyn_cast<AllocationInst>(Inst)) {
100 if (ConstantInt *C = dyn_cast<ConstantInt>(AI->getArraySize()))
101 // Use ABI size (size between elements), not store size (size of one
102 // element without padding).
103 PointerSize = C->getZExtValue() *
104 TD.getABITypeSize(AI->getAllocatedType());
107 } else if (VAArgInst *V = dyn_cast<VAArgInst>(Inst)) {
108 Pointer = V->getOperand(0);
109 PointerSize = TD.getTypeStoreSize(V->getType());
110 } else if (FreeInst *F = dyn_cast<FreeInst>(Inst)) {
111 Pointer = F->getPointerOperand();
113 // FreeInsts erase the entire structure
115 } else if (isa<CallInst>(Inst) || isa<InvokeInst>(Inst)) {
116 if (AA.getModRefBehavior(CallSite::get(Inst)) ==
117 AliasAnalysis::DoesNotAccessMemory)
119 return MemDepResult::get(Inst);
123 if (AA.getModRefInfo(C, Pointer, PointerSize) != AliasAnalysis::NoModRef)
124 return MemDepResult::get(Inst);
127 // No dependence found.
128 return MemDepResult::getNonLocal();
131 /// getNonLocalDependency - Perform a full dependency query for the
132 /// specified instruction, returning the set of blocks that the value is
133 /// potentially live across. The returned set of results will include a
134 /// "NonLocal" result for all blocks where the value is live across.
136 /// This method assumes the instruction returns a "nonlocal" dependency
137 /// within its own block.
139 void MemoryDependenceAnalysis::getNonLocalDependency(Instruction *QueryInst,
140 DenseMap<BasicBlock*, MemDepResult> &Result) {
141 assert(getDependency(QueryInst).isNonLocal() &&
142 "getNonLocalDependency should only be used on insts with non-local deps!");
143 DenseMap<BasicBlock*, DepResultTy> &Cache = NonLocalDeps[QueryInst];
145 /// DirtyBlocks - This is the set of blocks that need to be recomputed. This
146 /// can happen due to instructions being deleted etc.
147 SmallVector<BasicBlock*, 32> DirtyBlocks;
149 if (!Cache.empty()) {
150 // If we already have a partially computed set of results, scan them to
151 // determine what is dirty, seeding our initial DirtyBlocks worklist.
152 // FIXME: In the "don't need to be updated" case, this is expensive, why not
153 // have a per-"cache" flag saying it is undirty?
154 for (DenseMap<BasicBlock*, DepResultTy>::iterator I = Cache.begin(),
155 E = Cache.end(); I != E; ++I)
156 if (I->second.getInt() == Dirty)
157 DirtyBlocks.push_back(I->first);
161 // Seed DirtyBlocks with each of the preds of QueryInst's block.
162 BasicBlock *QueryBB = QueryInst->getParent();
163 // FIXME: use range insertion/append.
164 for (pred_iterator PI = pred_begin(QueryBB), E = pred_end(QueryBB);
166 DirtyBlocks.push_back(*PI);
167 NumUncacheNonlocal++;
170 // Iterate while we still have blocks to update.
171 while (!DirtyBlocks.empty()) {
172 BasicBlock *DirtyBB = DirtyBlocks.back();
173 DirtyBlocks.pop_back();
175 // Get the entry for this block. Note that this relies on DepResultTy
176 // default initializing to Dirty.
177 DepResultTy &DirtyBBEntry = Cache[DirtyBB];
179 // If DirtyBBEntry isn't dirty, it ended up on the worklist multiple times.
180 if (DirtyBBEntry.getInt() != Dirty) continue;
182 // Find out if this block has a local dependency for QueryInst.
183 // FIXME: If the dirty entry has an instruction pointer, scan from it!
184 // FIXME: Don't convert back and forth for MemDepResult <-> DepResultTy.
185 DirtyBBEntry = ConvFromResult(getDependencyFrom(QueryInst, DirtyBB->end(),
188 // If the block has a dependency (i.e. it isn't completely transparent to
189 // the value), remember it!
190 if (DirtyBBEntry.getInt() != NonLocal) {
191 // Keep the ReverseNonLocalDeps map up to date so we can efficiently
192 // update this when we remove instructions.
193 if (Instruction *Inst = DirtyBBEntry.getPointer())
194 ReverseNonLocalDeps[Inst].insert(QueryInst);
198 // If the block *is* completely transparent to the load, we need to check
199 // the predecessors of this block. Add them to our worklist.
200 for (pred_iterator I = pred_begin(DirtyBB), E = pred_end(DirtyBB);
202 DirtyBlocks.push_back(*I);
205 // Copy the result into the output set.
206 for (DenseMap<BasicBlock*, DepResultTy>::iterator I = Cache.begin(),
207 E = Cache.end(); I != E; ++I)
208 Result[I->first] = ConvToResult(I->second);
211 /// getDependency - Return the instruction on which a memory operation
212 /// depends. The local parameter indicates if the query should only
213 /// evaluate dependencies within the same basic block.
214 MemDepResult MemoryDependenceAnalysis::
215 getDependencyFrom(Instruction *QueryInst, BasicBlock::iterator ScanIt,
217 AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
218 TargetData &TD = getAnalysis<TargetData>();
220 // Get the pointer value for which dependence will be determined
222 uint64_t MemSize = 0;
223 bool MemVolatile = false;
225 if (StoreInst* S = dyn_cast<StoreInst>(QueryInst)) {
226 MemPtr = S->getPointerOperand();
227 MemSize = TD.getTypeStoreSize(S->getOperand(0)->getType());
228 MemVolatile = S->isVolatile();
229 } else if (LoadInst* L = dyn_cast<LoadInst>(QueryInst)) {
230 MemPtr = L->getPointerOperand();
231 MemSize = TD.getTypeStoreSize(L->getType());
232 MemVolatile = L->isVolatile();
233 } else if (VAArgInst* V = dyn_cast<VAArgInst>(QueryInst)) {
234 MemPtr = V->getOperand(0);
235 MemSize = TD.getTypeStoreSize(V->getType());
236 } else if (FreeInst* F = dyn_cast<FreeInst>(QueryInst)) {
237 MemPtr = F->getPointerOperand();
238 // FreeInsts erase the entire structure, not just a field.
240 } else if (isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst))
241 return getCallSiteDependency(CallSite::get(QueryInst), ScanIt, BB);
242 else // Non-memory instructions depend on nothing.
243 return MemDepResult::getNone();
245 // Walk backwards through the basic block, looking for dependencies
246 while (ScanIt != BB->begin()) {
247 Instruction *Inst = --ScanIt;
249 // If the access is volatile and this is a volatile load/store, return a
252 ((isa<LoadInst>(Inst) && cast<LoadInst>(Inst)->isVolatile()) ||
253 (isa<StoreInst>(Inst) && cast<StoreInst>(Inst)->isVolatile())))
254 return MemDepResult::get(Inst);
256 // MemDep is broken w.r.t. loads: it says that two loads of the same pointer
257 // depend on each other. :(
258 // FIXME: ELIMINATE THIS!
259 if (LoadInst *L = dyn_cast<LoadInst>(Inst)) {
260 Value *Pointer = L->getPointerOperand();
261 uint64_t PointerSize = TD.getTypeStoreSize(L->getType());
263 // If we found a pointer, check if it could be the same as our pointer
264 AliasAnalysis::AliasResult R =
265 AA.alias(Pointer, PointerSize, MemPtr, MemSize);
267 if (R == AliasAnalysis::NoAlias)
270 // May-alias loads don't depend on each other without a dependence.
271 if (isa<LoadInst>(QueryInst) && R == AliasAnalysis::MayAlias)
273 return MemDepResult::get(Inst);
276 // FIXME: This claims that an access depends on the allocation. This may
277 // make sense, but is dubious at best. It would be better to fix GVN to
278 // handle a 'None' Query.
279 if (AllocationInst *AI = dyn_cast<AllocationInst>(Inst)) {
281 uint64_t PointerSize;
282 if (ConstantInt *C = dyn_cast<ConstantInt>(AI->getArraySize()))
283 // Use ABI size (size between elements), not store size (size of one
284 // element without padding).
285 PointerSize = C->getZExtValue() *
286 TD.getABITypeSize(AI->getAllocatedType());
290 AliasAnalysis::AliasResult R =
291 AA.alias(Pointer, PointerSize, MemPtr, MemSize);
293 if (R == AliasAnalysis::NoAlias)
295 return MemDepResult::get(Inst);
299 // See if this instruction mod/ref's the pointer.
300 AliasAnalysis::ModRefResult MRR = AA.getModRefInfo(Inst, MemPtr, MemSize);
302 if (MRR == AliasAnalysis::NoModRef)
305 // Loads don't depend on read-only instructions.
306 if (isa<LoadInst>(QueryInst) && MRR == AliasAnalysis::Ref)
309 // Otherwise, there is a dependence.
310 return MemDepResult::get(Inst);
313 // If we found nothing, return the non-local flag.
314 return MemDepResult::getNonLocal();
317 /// getDependency - Return the instruction on which a memory operation
319 MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) {
320 Instruction *ScanPos = QueryInst;
322 // Check for a cached result
323 DepResultTy &LocalCache = LocalDeps[QueryInst];
325 // If the cached entry is non-dirty, just return it.
326 if (LocalCache.getInt() != Dirty)
327 return ConvToResult(LocalCache);
329 // Otherwise, if we have a dirty entry, we know we can start the scan at that
330 // instruction, which may save us some work.
331 if (Instruction *Inst = LocalCache.getPointer())
336 getDependencyFrom(QueryInst, ScanPos, QueryInst->getParent());
338 // Remember the result!
339 // FIXME: Don't convert back and forth! Make a shared helper function.
340 LocalCache = ConvFromResult(Res);
341 if (Instruction *I = Res.getInst())
342 ReverseLocalDeps[I].insert(QueryInst);
348 /// dropInstruction - Remove an instruction from the analysis, making
349 /// absolutely conservative assumptions when updating the cache. This is
350 /// useful, for example when an instruction is changed rather than removed.
351 void MemoryDependenceAnalysis::dropInstruction(Instruction* drop) {
352 LocalDepMapType::iterator depGraphEntry = LocalDeps.find(drop);
353 if (depGraphEntry != LocalDeps.end())
354 if (Instruction *Inst = depGraphEntry->second.getPointer())
355 ReverseLocalDeps[Inst].erase(drop);
357 // Drop dependency information for things that depended on this instr
358 SmallPtrSet<Instruction*, 4>& set = ReverseLocalDeps[drop];
359 for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
363 LocalDeps.erase(drop);
364 ReverseLocalDeps.erase(drop);
366 for (DenseMap<BasicBlock*, DepResultTy>::iterator DI =
367 NonLocalDeps[drop].begin(), DE = NonLocalDeps[drop].end();
369 if (Instruction *Inst = DI->second.getPointer())
370 ReverseNonLocalDeps[Inst].erase(drop);
372 if (ReverseNonLocalDeps.count(drop)) {
373 SmallPtrSet<Instruction*, 4>& set =
374 ReverseNonLocalDeps[drop];
375 for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
377 for (DenseMap<BasicBlock*, DepResultTy>::iterator DI =
378 NonLocalDeps[*I].begin(), DE = NonLocalDeps[*I].end();
380 if (DI->second == DepResultTy(drop, Normal))
381 // FIXME: Why not remember the old insertion point??
382 DI->second = DepResultTy(0, Dirty);
385 ReverseNonLocalDeps.erase(drop);
386 NonLocalDeps.erase(drop);
389 /// removeInstruction - Remove an instruction from the dependence analysis,
390 /// updating the dependence of instructions that previously depended on it.
391 /// This method attempts to keep the cache coherent using the reverse map.
392 void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) {
393 // Walk through the Non-local dependencies, removing this one as the value
394 // for any cached queries.
395 for (DenseMap<BasicBlock*, DepResultTy>::iterator DI =
396 NonLocalDeps[RemInst].begin(), DE = NonLocalDeps[RemInst].end();
398 if (Instruction *Inst = DI->second.getPointer())
399 ReverseNonLocalDeps[Inst].erase(RemInst);
401 // Shortly after this, we will look for things that depend on RemInst. In
402 // order to update these, we'll need a new dependency to base them on. We
403 // could completely delete any entries that depend on this, but it is better
404 // to make a more accurate approximation where possible. Compute that better
405 // approximation if we can.
406 DepResultTy NewDependency;
408 // If we have a cached local dependence query for this instruction, remove it.
410 LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst);
411 if (LocalDepEntry != LocalDeps.end()) {
412 DepResultTy LocalDep = LocalDepEntry->second;
414 // Remove this local dependency info.
415 LocalDeps.erase(LocalDepEntry);
417 // Remove us from DepInst's reverse set now that the local dep info is gone.
418 if (Instruction *Inst = LocalDep.getPointer())
419 ReverseLocalDeps[Inst].erase(RemInst);
421 // If we have unconfirmed info, don't trust it.
422 if (LocalDep.getInt() != Dirty) {
423 // If we have a confirmed non-local flag, use it.
424 if (LocalDep.getInt() == NonLocal || LocalDep.getInt() == None) {
425 // The only time this dependency is confirmed is if it is non-local.
426 NewDependency = LocalDep;
428 // If we have dep info for RemInst, set them to it.
429 Instruction *NDI = next(BasicBlock::iterator(LocalDep.getPointer()));
430 if (NDI != RemInst) // Don't use RemInst for the new dependency!
431 NewDependency = DepResultTy(NDI, Dirty);
436 // If we don't already have a local dependency answer for this instruction,
437 // use the immediate successor of RemInst. We use the successor because
438 // getDependence starts by checking the immediate predecessor of what is in
440 if (NewDependency == DepResultTy(0, Dirty))
441 NewDependency = DepResultTy(next(BasicBlock::iterator(RemInst)), Dirty);
443 // Loop over all of the things that depend on the instruction we're removing.
445 ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(RemInst);
446 if (ReverseDepIt != ReverseLocalDeps.end()) {
447 SmallPtrSet<Instruction*, 4> &ReverseDeps = ReverseDepIt->second;
448 for (SmallPtrSet<Instruction*, 4>::iterator I = ReverseDeps.begin(),
449 E = ReverseDeps.end(); I != E; ++I) {
450 Instruction *InstDependingOnRemInst = *I;
452 // If we thought the instruction depended on itself (possible for
453 // unconfirmed dependencies) ignore the update.
454 if (InstDependingOnRemInst == RemInst) continue;
456 // Insert the new dependencies.
457 LocalDeps[InstDependingOnRemInst] = NewDependency;
459 // If our NewDependency is an instruction, make sure to remember that new
460 // things depend on it.
461 if (Instruction *Inst = NewDependency.getPointer())
462 ReverseLocalDeps[Inst].insert(InstDependingOnRemInst);
464 ReverseLocalDeps.erase(RemInst);
467 ReverseDepIt = ReverseNonLocalDeps.find(RemInst);
468 if (ReverseDepIt != ReverseNonLocalDeps.end()) {
469 SmallPtrSet<Instruction*, 4>& set = ReverseDepIt->second;
470 for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
472 for (DenseMap<BasicBlock*, DepResultTy>::iterator
473 DI = NonLocalDeps[*I].begin(), DE = NonLocalDeps[*I].end();
475 if (DI->second == DepResultTy(RemInst, Normal))
476 // FIXME: Why not remember the old insertion point??
477 DI->second = DepResultTy(0, Dirty);
478 ReverseNonLocalDeps.erase(ReverseDepIt);
481 NonLocalDeps.erase(RemInst);
483 getAnalysis<AliasAnalysis>().deleteValue(RemInst);
485 DEBUG(verifyRemoved(RemInst));