MemoryDependenceAnalysis.cpp revision 8c4652790e04515f34cf920b0783d6ec4161a313
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 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). 33static cl::opt<int> 34PredLimit("nonlocaldep-threshold", cl::Hidden, cl::init(50), 35 cl::desc("Control the calculation of non-local" 36 "dependencies (default = 50)")); 37 38STATISTIC(NumCacheNonlocal, "Number of cached non-local responses"); 39STATISTIC(NumUncacheNonlocal, "Number of uncached non-local responses"); 40 41char MemoryDependenceAnalysis::ID = 0; 42 43// Register this pass... 44static RegisterPass<MemoryDependenceAnalysis> X("memdep", 45 "Memory Dependence Analysis", false, true); 46 47/// verifyRemoved - Verify that the specified instruction does not occur 48/// in our internal data structures. 49void 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"); 55 } 56 57 for (NonLocalDepMapType::const_iterator I = NonLocalDeps.begin(), 58 E = NonLocalDeps.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"); 63 } 64 65 for (ReverseDepMapType::const_iterator I = ReverseLocalDeps.begin(), 66 E = ReverseLocalDeps.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"); 70 71 for (ReverseDepMapType::const_iterator I = ReverseNonLocalDeps.begin(), 72 E = ReverseNonLocalDeps.end(); 73 I != E; ++I) 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"); 77} 78 79/// getAnalysisUsage - Does not modify anything. It uses Alias Analysis. 80/// 81void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 82 AU.setPreservesAll(); 83 AU.addRequiredTransitive<AliasAnalysis>(); 84 AU.addRequiredTransitive<TargetData>(); 85} 86 87/// getCallSiteDependency - Private helper for finding the local dependencies 88/// of a call site. 89MemDepResult MemoryDependenceAnalysis:: 90getCallSiteDependency(CallSite C, BasicBlock::iterator ScanIt, 91 BasicBlock *BB) { 92 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 93 TargetData &TD = getAnalysis<TargetData>(); 94 95 // Walk backwards through the block, looking for dependencies 96 while (ScanIt != BB->begin()) { 97 Instruction *Inst = --ScanIt; 98 99 // If this inst is a memory op, get the pointer it accessed 100 Value *Pointer = 0; 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)) { 106 Pointer = AI; 107 if (ConstantInt *C = dyn_cast<ConstantInt>(AI->getArraySize())) 108 PointerSize = C->getZExtValue() * 109 TD.getTypeStoreSize(AI->getAllocatedType()); 110 else 111 PointerSize = ~0UL; 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(); 117 118 // FreeInsts erase the entire structure 119 PointerSize = ~0UL; 120 } else if (isa<CallInst>(Inst) || isa<InvokeInst>(Inst)) { 121 if (AA.getModRefBehavior(CallSite::get(Inst)) == 122 AliasAnalysis::DoesNotAccessMemory) 123 continue; 124 return MemDepResult::get(Inst); 125 } else 126 continue; 127 128 if (AA.getModRefInfo(C, Pointer, PointerSize) != AliasAnalysis::NoModRef) 129 return MemDepResult::get(Inst); 130 } 131 132 // No dependence found. 133 return MemDepResult::getNonLocal(); 134} 135 136/// nonLocalHelper - Private helper used to calculate non-local dependencies 137/// by doing DFS on the predecessors of a block to find its dependencies. 138void MemoryDependenceAnalysis::nonLocalHelper(Instruction* query, 139 BasicBlock* block, 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); 149 150 // Current stack of the DFS 151 SmallVector<BasicBlock*, 4> stack; 152 for (pred_iterator PI = pred_begin(block), PE = pred_end(block); 153 PI != PE; ++PI) 154 stack.push_back(*PI); 155 156 // Do a basic DFS 157 while (!stack.empty()) { 158 BasicBlock* BB = stack.back(); 159 160 // If we've already visited this block, no need to revist 161 if (visited.count(BB)) { 162 stack.pop_back(); 163 continue; 164 } 165 166 // If we find a new block with a local dependency for query, 167 // then we insert the new dependency and backtrack. 168 if (BB != block) { 169 visited.insert(BB); 170 171 MemDepResult localDep = getDependencyFrom(query, BB->end(), BB); 172 if (!localDep.isNonLocal()) { 173 resp.insert(std::make_pair(BB, ConvFromResult(localDep))); 174 stack.pop_back(); 175 continue; 176 } 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) { 181 visited.insert(BB); 182 183 MemDepResult localDep = getDependencyFrom(query, BB->end(), BB); 184 if (localDep.getInst() != query) 185 resp.insert(std::make_pair(BB, ConvFromResult(localDep))); 186 187 stack.pop_back(); 188 continue; 189 } 190 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); 197 PI != PE; ++PI) 198 if (!visited.count(*PI)) { 199 stack.push_back(*PI); 200 inserted = true; 201 } else 202 predOnStack = true; 203 } 204 205 // If we inserted a new predecessor, then we'll come back to this block 206 if (inserted) 207 continue; 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 214 // backtracking. 215 } else if (!inserted && predOnStack){ 216 resp.insert(std::make_pair(BB, DepResultTy(0, NonLocal))); 217 } 218 219 stack.pop_back(); 220 } 221} 222 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. 226void MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query, 227 DenseMap<BasicBlock*, MemDepResult> &resp) { 228 if (NonLocalDeps.count(query)) { 229 DenseMap<BasicBlock*, DepResultTy> &cached = NonLocalDeps[query]; 230 NumCacheNonlocal++; 231 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); 237 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); 243 else { 244 cached.erase(*I); 245 nonLocalHelper(query, *I, cached); 246 } 247 } 248 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 ReverseNonLocalDeps[Inst].insert(query); 254 resp[I->first] = ConvToResult(I->second); 255 } 256 257 return; 258 } 259 260 NumUncacheNonlocal++; 261 262 // If not, go ahead and search for non-local deps. 263 DenseMap<BasicBlock*, DepResultTy> &cached = NonLocalDeps[query]; 264 nonLocalHelper(query, query->getParent(), cached); 265 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 ReverseNonLocalDeps[Inst].insert(query); 272 resp[I->first] = ConvToResult(I->second); 273 } 274} 275 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. 279MemDepResult MemoryDependenceAnalysis:: 280getDependencyFrom(Instruction *QueryInst, BasicBlock::iterator ScanIt, 281 BasicBlock *BB) { 282 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 283 TargetData &TD = getAnalysis<TargetData>(); 284 285 // Get the pointer value for which dependence will be determined 286 Value *MemPtr = 0; 287 uint64_t MemSize = 0; 288 bool MemVolatile = false; 289 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. 304 MemSize = ~0UL; 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(); 309 310 // Walk backwards through the basic block, looking for dependencies 311 while (ScanIt != BB->begin()) { 312 Instruction *Inst = --ScanIt; 313 314 // If the access is volatile and this is a volatile load/store, return a 315 // dependence. 316 if (MemVolatile && 317 ((isa<LoadInst>(Inst) && cast<LoadInst>(Inst)->isVolatile()) || 318 (isa<StoreInst>(Inst) && cast<StoreInst>(Inst)->isVolatile()))) 319 return MemDepResult::get(Inst); 320 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()); 327 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); 331 332 if (R == AliasAnalysis::NoAlias) 333 continue; 334 335 // May-alias loads don't depend on each other without a dependence. 336 if (isa<LoadInst>(QueryInst) && R == AliasAnalysis::MayAlias) 337 continue; 338 return MemDepResult::get(Inst); 339 } 340 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)) { 345 Value *Pointer = AI; 346 uint64_t PointerSize; 347 if (ConstantInt *C = dyn_cast<ConstantInt>(AI->getArraySize())) 348 PointerSize = C->getZExtValue() * 349 TD.getTypeStoreSize(AI->getAllocatedType()); 350 else 351 PointerSize = ~0UL; 352 353 AliasAnalysis::AliasResult R = 354 AA.alias(Pointer, PointerSize, MemPtr, MemSize); 355 356 if (R == AliasAnalysis::NoAlias) 357 continue; 358 return MemDepResult::get(Inst); 359 } 360 361 362 // See if this instruction mod/ref's the pointer. 363 AliasAnalysis::ModRefResult MRR = AA.getModRefInfo(Inst, MemPtr, MemSize); 364 365 if (MRR == AliasAnalysis::NoModRef) 366 continue; 367 368 // Loads don't depend on read-only instructions. 369 if (isa<LoadInst>(QueryInst) && MRR == AliasAnalysis::Ref) 370 continue; 371 372 // Otherwise, there is a dependence. 373 return MemDepResult::get(Inst); 374 } 375 376 // If we found nothing, return the non-local flag. 377 return MemDepResult::getNonLocal(); 378} 379 380/// getDependency - Return the instruction on which a memory operation 381/// depends. 382MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) { 383 Instruction *ScanPos = QueryInst; 384 385 // Check for a cached result 386 DepResultTy &LocalCache = LocalDeps[QueryInst]; 387 388 // If the cached entry is non-dirty, just return it. 389 if (LocalCache.getInt() != Dirty) 390 return ConvToResult(LocalCache); 391 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()) 395 ScanPos = Inst; 396 397 // Do the scan. 398 MemDepResult Res = 399 getDependencyFrom(QueryInst, ScanPos, QueryInst->getParent()); 400 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 ReverseLocalDeps[I].insert(QueryInst); 406 407 return Res; 408} 409 410 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. 414void MemoryDependenceAnalysis::dropInstruction(Instruction* drop) { 415 LocalDepMapType::iterator depGraphEntry = LocalDeps.find(drop); 416 if (depGraphEntry != LocalDeps.end()) 417 if (Instruction *Inst = depGraphEntry->second.getPointer()) 418 ReverseLocalDeps[Inst].erase(drop); 419 420 // Drop dependency information for things that depended on this instr 421 SmallPtrSet<Instruction*, 4>& set = ReverseLocalDeps[drop]; 422 for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end(); 423 I != E; ++I) 424 LocalDeps.erase(*I); 425 426 LocalDeps.erase(drop); 427 ReverseLocalDeps.erase(drop); 428 429 for (DenseMap<BasicBlock*, DepResultTy>::iterator DI = 430 NonLocalDeps[drop].begin(), DE = NonLocalDeps[drop].end(); 431 DI != DE; ++DI) 432 if (Instruction *Inst = DI->second.getPointer()) 433 ReverseNonLocalDeps[Inst].erase(drop); 434 435 if (ReverseNonLocalDeps.count(drop)) { 436 SmallPtrSet<Instruction*, 4>& set = 437 ReverseNonLocalDeps[drop]; 438 for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end(); 439 I != E; ++I) 440 for (DenseMap<BasicBlock*, DepResultTy>::iterator DI = 441 NonLocalDeps[*I].begin(), DE = NonLocalDeps[*I].end(); 442 DI != DE; ++DI) 443 if (DI->second == DepResultTy(drop, Normal)) 444 // FIXME: Why not remember the old insertion point?? 445 DI->second = DepResultTy(0, Dirty); 446 } 447 448 ReverseNonLocalDeps.erase(drop); 449 NonLocalDeps.erase(drop); 450} 451 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. 455void 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 NonLocalDeps[RemInst].begin(), DE = NonLocalDeps[RemInst].end(); 460 DI != DE; ++DI) 461 if (Instruction *Inst = DI->second.getPointer()) 462 ReverseNonLocalDeps[Inst].erase(RemInst); 463 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; 470 471 // If we have a cached local dependence query for this instruction, remove it. 472 // 473 LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst); 474 if (LocalDepEntry != LocalDeps.end()) { 475 DepResultTy LocalDep = LocalDepEntry->second; 476 477 // Remove this local dependency info. 478 LocalDeps.erase(LocalDepEntry); 479 480 // Remove us from DepInst's reverse set now that the local dep info is gone. 481 if (Instruction *Inst = LocalDep.getPointer()) 482 ReverseLocalDeps[Inst].erase(RemInst); 483 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; 490 } else { 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); 495 } 496 } 497 } 498 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 502 // the cache. 503 if (NewDependency == DepResultTy(0, Dirty)) 504 NewDependency = DepResultTy(next(BasicBlock::iterator(RemInst)), Dirty); 505 506 // Loop over all of the things that depend on the instruction we're removing. 507 // 508 ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(RemInst); 509 if (ReverseDepIt != ReverseLocalDeps.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; 514 515 // If we thought the instruction depended on itself (possible for 516 // unconfirmed dependencies) ignore the update. 517 if (InstDependingOnRemInst == RemInst) continue; 518 519 // Insert the new dependencies. 520 LocalDeps[InstDependingOnRemInst] = NewDependency; 521 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 ReverseLocalDeps[Inst].insert(InstDependingOnRemInst); 526 } 527 ReverseLocalDeps.erase(RemInst); 528 } 529 530 ReverseDepIt = ReverseNonLocalDeps.find(RemInst); 531 if (ReverseDepIt != ReverseNonLocalDeps.end()) { 532 SmallPtrSet<Instruction*, 4>& set = ReverseDepIt->second; 533 for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end(); 534 I != E; ++I) 535 for (DenseMap<BasicBlock*, DepResultTy>::iterator 536 DI = NonLocalDeps[*I].begin(), DE = NonLocalDeps[*I].end(); 537 DI != DE; ++DI) 538 if (DI->second == DepResultTy(RemInst, Normal)) 539 // FIXME: Why not remember the old insertion point?? 540 DI->second = DepResultTy(0, Dirty); 541 ReverseNonLocalDeps.erase(ReverseDepIt); 542 } 543 544 NonLocalDeps.erase(RemInst); 545 546 getAnalysis<AliasAnalysis>().deleteValue(RemInst); 547 548 DEBUG(verifyRemoved(RemInst)); 549} 550