MemoryDependenceAnalysis.cpp revision 86b29ef64a36c8779ef7855b3c4b95744eb2f08b
1//===- MemoryDependenceAnalysis.cpp - Mem Deps Implementation --*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 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. 14// 15//===----------------------------------------------------------------------===// 16 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" 29using namespace llvm; 30 31STATISTIC(NumCacheNonlocal, "Number of cached non-local responses"); 32STATISTIC(NumUncacheNonlocal, "Number of uncached non-local responses"); 33 34char MemoryDependenceAnalysis::ID = 0; 35 36// Register this pass... 37static RegisterPass<MemoryDependenceAnalysis> X("memdep", 38 "Memory Dependence Analysis", false, true); 39 40/// verifyRemoved - Verify that the specified instruction does not occur 41/// in our internal data structures. 42void 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"); 48 } 49 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"); 56 } 57 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"); 63 64 for (ReverseDepMapType::const_iterator I = ReverseNonLocalDeps.begin(), 65 E = ReverseNonLocalDeps.end(); 66 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"); 70} 71 72/// getAnalysisUsage - Does not modify anything. It uses Alias Analysis. 73/// 74void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 75 AU.setPreservesAll(); 76 AU.addRequiredTransitive<AliasAnalysis>(); 77 AU.addRequiredTransitive<TargetData>(); 78} 79 80/// getCallSiteDependency - Private helper for finding the local dependencies 81/// of a call site. 82MemDepResult MemoryDependenceAnalysis:: 83getCallSiteDependency(CallSite C, BasicBlock::iterator ScanIt, 84 BasicBlock *BB) { 85 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 86 TargetData &TD = getAnalysis<TargetData>(); 87 88 // Walk backwards through the block, looking for dependencies 89 while (ScanIt != BB->begin()) { 90 Instruction *Inst = --ScanIt; 91 92 // If this inst is a memory op, get the pointer it accessed 93 Value *Pointer = 0; 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)) { 99 Pointer = AI; 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()); 105 else 106 PointerSize = ~0UL; 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(); 112 113 // FreeInsts erase the entire structure 114 PointerSize = ~0UL; 115 } else if (isa<CallInst>(Inst) || isa<InvokeInst>(Inst)) { 116 if (AA.getModRefBehavior(CallSite::get(Inst)) == 117 AliasAnalysis::DoesNotAccessMemory) 118 continue; 119 return MemDepResult::get(Inst); 120 } else 121 continue; 122 123 if (AA.getModRefInfo(C, Pointer, PointerSize) != AliasAnalysis::NoModRef) 124 return MemDepResult::get(Inst); 125 } 126 127 // No dependence found. 128 return MemDepResult::getNonLocal(); 129} 130 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. 135/// 136/// This method assumes the instruction returns a "nonlocal" dependency 137/// within its own block. 138/// 139void 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]; 144 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; 148 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); 158 159 NumCacheNonlocal++; 160 } else { 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); 165 PI != E; ++PI) 166 DirtyBlocks.push_back(*PI); 167 NumUncacheNonlocal++; 168 } 169 170 // Iterate while we still have blocks to update. 171 while (!DirtyBlocks.empty()) { 172 BasicBlock *DirtyBB = DirtyBlocks.back(); 173 DirtyBlocks.pop_back(); 174 175 // Get the entry for this block. Note that this relies on DepResultTy 176 // default initializing to Dirty. 177 DepResultTy &DirtyBBEntry = Cache[DirtyBB]; 178 179 // If DirtyBBEntry isn't dirty, it ended up on the worklist multiple times. 180 if (DirtyBBEntry.getInt() != Dirty) continue; 181 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(), 186 DirtyBB)); 187 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); 195 continue; 196 } 197 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); 201 I != E; ++I) 202 DirtyBlocks.push_back(*I); 203 } 204 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); 209} 210 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. 214MemDepResult MemoryDependenceAnalysis:: 215getDependencyFrom(Instruction *QueryInst, BasicBlock::iterator ScanIt, 216 BasicBlock *BB) { 217 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 218 TargetData &TD = getAnalysis<TargetData>(); 219 220 // Get the pointer value for which dependence will be determined 221 Value *MemPtr = 0; 222 uint64_t MemSize = 0; 223 bool MemVolatile = false; 224 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. 239 MemSize = ~0UL; 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(); 244 245 // Walk backwards through the basic block, looking for dependencies 246 while (ScanIt != BB->begin()) { 247 Instruction *Inst = --ScanIt; 248 249 // If the access is volatile and this is a volatile load/store, return a 250 // dependence. 251 if (MemVolatile && 252 ((isa<LoadInst>(Inst) && cast<LoadInst>(Inst)->isVolatile()) || 253 (isa<StoreInst>(Inst) && cast<StoreInst>(Inst)->isVolatile()))) 254 return MemDepResult::get(Inst); 255 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()); 262 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); 266 267 if (R == AliasAnalysis::NoAlias) 268 continue; 269 270 // May-alias loads don't depend on each other without a dependence. 271 if (isa<LoadInst>(QueryInst) && R == AliasAnalysis::MayAlias) 272 continue; 273 return MemDepResult::get(Inst); 274 } 275 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)) { 280 Value *Pointer = AI; 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()); 287 else 288 PointerSize = ~0UL; 289 290 AliasAnalysis::AliasResult R = 291 AA.alias(Pointer, PointerSize, MemPtr, MemSize); 292 293 if (R == AliasAnalysis::NoAlias) 294 continue; 295 return MemDepResult::get(Inst); 296 } 297 298 299 // See if this instruction mod/ref's the pointer. 300 AliasAnalysis::ModRefResult MRR = AA.getModRefInfo(Inst, MemPtr, MemSize); 301 302 if (MRR == AliasAnalysis::NoModRef) 303 continue; 304 305 // Loads don't depend on read-only instructions. 306 if (isa<LoadInst>(QueryInst) && MRR == AliasAnalysis::Ref) 307 continue; 308 309 // Otherwise, there is a dependence. 310 return MemDepResult::get(Inst); 311 } 312 313 // If we found nothing, return the non-local flag. 314 return MemDepResult::getNonLocal(); 315} 316 317/// getDependency - Return the instruction on which a memory operation 318/// depends. 319MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) { 320 Instruction *ScanPos = QueryInst; 321 322 // Check for a cached result 323 DepResultTy &LocalCache = LocalDeps[QueryInst]; 324 325 // If the cached entry is non-dirty, just return it. 326 if (LocalCache.getInt() != Dirty) 327 return ConvToResult(LocalCache); 328 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()) 332 ScanPos = Inst; 333 334 // Do the scan. 335 MemDepResult Res = 336 getDependencyFrom(QueryInst, ScanPos, QueryInst->getParent()); 337 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); 343 344 return Res; 345} 346 347 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. 351void 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); 356 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(); 360 I != E; ++I) 361 LocalDeps.erase(*I); 362 363 LocalDeps.erase(drop); 364 ReverseLocalDeps.erase(drop); 365 366 for (DenseMap<BasicBlock*, DepResultTy>::iterator DI = 367 NonLocalDeps[drop].begin(), DE = NonLocalDeps[drop].end(); 368 DI != DE; ++DI) 369 if (Instruction *Inst = DI->second.getPointer()) 370 ReverseNonLocalDeps[Inst].erase(drop); 371 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(); 376 I != E; ++I) 377 for (DenseMap<BasicBlock*, DepResultTy>::iterator DI = 378 NonLocalDeps[*I].begin(), DE = NonLocalDeps[*I].end(); 379 DI != DE; ++DI) 380 if (DI->second == DepResultTy(drop, Normal)) 381 // FIXME: Why not remember the old insertion point?? 382 DI->second = DepResultTy(0, Dirty); 383 } 384 385 ReverseNonLocalDeps.erase(drop); 386 NonLocalDeps.erase(drop); 387} 388 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. 392void 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(); 397 DI != DE; ++DI) 398 if (Instruction *Inst = DI->second.getPointer()) 399 ReverseNonLocalDeps[Inst].erase(RemInst); 400 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; 407 408 // If we have a cached local dependence query for this instruction, remove it. 409 // 410 LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst); 411 if (LocalDepEntry != LocalDeps.end()) { 412 DepResultTy LocalDep = LocalDepEntry->second; 413 414 // Remove this local dependency info. 415 LocalDeps.erase(LocalDepEntry); 416 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); 420 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; 427 } else { 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); 432 } 433 } 434 } 435 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 439 // the cache. 440 if (NewDependency == DepResultTy(0, Dirty)) 441 NewDependency = DepResultTy(next(BasicBlock::iterator(RemInst)), Dirty); 442 443 // Loop over all of the things that depend on the instruction we're removing. 444 // 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; 451 452 // If we thought the instruction depended on itself (possible for 453 // unconfirmed dependencies) ignore the update. 454 if (InstDependingOnRemInst == RemInst) continue; 455 456 // Insert the new dependencies. 457 LocalDeps[InstDependingOnRemInst] = NewDependency; 458 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); 463 } 464 ReverseLocalDeps.erase(RemInst); 465 } 466 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(); 471 I != E; ++I) 472 for (DenseMap<BasicBlock*, DepResultTy>::iterator 473 DI = NonLocalDeps[*I].begin(), DE = NonLocalDeps[*I].end(); 474 DI != DE; ++DI) 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); 479 } 480 481 NonLocalDeps.erase(RemInst); 482 483 getAnalysis<AliasAnalysis>().deleteValue(RemInst); 484 485 DEBUG(verifyRemoved(RemInst)); 486} 487