MemoryDependenceAnalysis.cpp revision 5391a1d8046396fb4dd005b1910973789f5427f4
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 = 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"); 63 } 64 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"); 70 71 for (reverseDepMapType::const_iterator I = reverseDepNonLocal.begin(), 72 E = reverseDepNonLocal.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.getABITypeSize(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 (CallSite::get(Inst).getInstruction() != 0) { 121 if (AA.getModRefBehavior(CallSite::get(Inst)) != 122 AliasAnalysis::DoesNotAccessMemory) 123 return MemDepResult::get(Inst); 124 continue; 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 (depGraphNonLocal.count(query)) { 229 DenseMap<BasicBlock*, DepResultTy> &cached = depGraphNonLocal[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 reverseDepNonLocal[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 = depGraphNonLocal[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 reverseDepNonLocal[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. 279/// FIXME: ELIMINATE START/BLOCK and make the caching happen in a higher level 280/// METHOD. 281MemDepResult MemoryDependenceAnalysis:: 282getDependencyFrom(Instruction *QueryInst, BasicBlock::iterator ScanIt, 283 BasicBlock *BB) { 284 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 285 TargetData &TD = getAnalysis<TargetData>(); 286 287 // Get the pointer value for which dependence will be determined 288 Value* dependee = 0; 289 uint64_t dependeeSize = 0; 290 bool queryIsVolatile = false; 291 292 if (StoreInst* S = dyn_cast<StoreInst>(QueryInst)) { 293 dependee = S->getPointerOperand(); 294 dependeeSize = TD.getTypeStoreSize(S->getOperand(0)->getType()); 295 queryIsVolatile = S->isVolatile(); 296 } else if (LoadInst* L = dyn_cast<LoadInst>(QueryInst)) { 297 dependee = L->getPointerOperand(); 298 dependeeSize = TD.getTypeStoreSize(L->getType()); 299 queryIsVolatile = L->isVolatile(); 300 } else if (VAArgInst* V = dyn_cast<VAArgInst>(QueryInst)) { 301 dependee = V->getOperand(0); 302 dependeeSize = TD.getTypeStoreSize(V->getType()); 303 } else if (FreeInst* F = dyn_cast<FreeInst>(QueryInst)) { 304 dependee = F->getPointerOperand(); 305 // FreeInsts erase the entire structure, not just a field 306 dependeeSize = ~0UL; 307 } else if (CallSite::get(QueryInst).getInstruction() != 0) 308 return getCallSiteDependency(CallSite::get(QueryInst), ScanIt, BB); 309 else 310 return MemDepResult::getNone(); 311 312 // Walk backwards through the basic block, looking for dependencies 313 while (ScanIt != BB->begin()) { 314 Instruction *Inst = --ScanIt; 315 316 // If this inst is a memory op, get the pointer it accessed 317 Value* pointer = 0; 318 uint64_t pointerSize = 0; 319 if (StoreInst* S = dyn_cast<StoreInst>(Inst)) { 320 // All volatile loads/stores depend on each other 321 if (queryIsVolatile && S->isVolatile()) 322 return MemDepResult::get(S); 323 324 pointer = S->getPointerOperand(); 325 pointerSize = TD.getTypeStoreSize(S->getOperand(0)->getType()); 326 } else if (LoadInst* L = dyn_cast<LoadInst>(Inst)) { 327 // All volatile loads/stores depend on each other 328 if (queryIsVolatile && L->isVolatile()) 329 return MemDepResult::get(L); 330 331 pointer = L->getPointerOperand(); 332 pointerSize = TD.getTypeStoreSize(L->getType()); 333 } else if (AllocationInst* AI = dyn_cast<AllocationInst>(Inst)) { 334 pointer = AI; 335 if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize())) 336 pointerSize = C->getZExtValue() * 337 TD.getABITypeSize(AI->getAllocatedType()); 338 else 339 pointerSize = ~0UL; 340 } else if (VAArgInst* V = dyn_cast<VAArgInst>(Inst)) { 341 pointer = V->getOperand(0); 342 pointerSize = TD.getTypeStoreSize(V->getType()); 343 } else if (FreeInst* F = dyn_cast<FreeInst>(Inst)) { 344 pointer = F->getPointerOperand(); 345 346 // FreeInsts erase the entire structure 347 pointerSize = ~0UL; 348 } else if (isa<CallInst>(Inst) || isa<InvokeInst>(Inst)) { 349 // Call insts need special handling. Check if they can modify our pointer 350 AliasAnalysis::ModRefResult MR = AA.getModRefInfo(CallSite::get(Inst), 351 dependee, dependeeSize); 352 353 if (MR != AliasAnalysis::NoModRef) { 354 // Loads don't depend on read-only calls 355 if (isa<LoadInst>(QueryInst) && MR == AliasAnalysis::Ref) 356 continue; 357 return MemDepResult::get(Inst); 358 } 359 360 continue; 361 } 362 363 // If we found a pointer, check if it could be the same as our pointer 364 if (pointer) { 365 AliasAnalysis::AliasResult R = AA.alias(pointer, pointerSize, 366 dependee, dependeeSize); 367 368 if (R != AliasAnalysis::NoAlias) { 369 // May-alias loads don't depend on each other 370 if (isa<LoadInst>(QueryInst) && isa<LoadInst>(Inst) && 371 R == AliasAnalysis::MayAlias) 372 continue; 373 return MemDepResult::get(Inst); 374 } 375 } 376 } 377 378 // If we found nothing, return the non-local flag. 379 return MemDepResult::getNonLocal(); 380} 381 382/// getDependency - Return the instruction on which a memory operation 383/// depends. 384MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) { 385 Instruction *ScanPos = QueryInst; 386 387 // Check for a cached result 388 DepResultTy &LocalCache = LocalDeps[QueryInst]; 389 390 // If the cached entry is non-dirty, just return it. 391 if (LocalCache.getInt() != Dirty) 392 return ConvToResult(LocalCache); 393 394 // Otherwise, if we have a dirty entry, we know we can start the scan at that 395 // instruction, which may save us some work. 396 if (Instruction *Inst = LocalCache.getPointer()) 397 ScanPos = Inst; 398 399 // Do the scan. 400 MemDepResult Res = 401 getDependencyFrom(QueryInst, ScanPos, QueryInst->getParent()); 402 403 // Remember the result! 404 // FIXME: Don't convert back and forth! Make a shared helper function. 405 LocalCache = ConvFromResult(Res); 406 if (Instruction *I = Res.getInst()) 407 reverseDep[I].insert(QueryInst); 408 409 return Res; 410} 411 412 413/// dropInstruction - Remove an instruction from the analysis, making 414/// absolutely conservative assumptions when updating the cache. This is 415/// useful, for example when an instruction is changed rather than removed. 416void MemoryDependenceAnalysis::dropInstruction(Instruction* drop) { 417 LocalDepMapType::iterator depGraphEntry = LocalDeps.find(drop); 418 if (depGraphEntry != LocalDeps.end()) 419 if (Instruction *Inst = depGraphEntry->second.getPointer()) 420 reverseDep[Inst].erase(drop); 421 422 // Drop dependency information for things that depended on this instr 423 SmallPtrSet<Instruction*, 4>& set = reverseDep[drop]; 424 for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end(); 425 I != E; ++I) 426 LocalDeps.erase(*I); 427 428 LocalDeps.erase(drop); 429 reverseDep.erase(drop); 430 431 for (DenseMap<BasicBlock*, DepResultTy>::iterator DI = 432 depGraphNonLocal[drop].begin(), DE = depGraphNonLocal[drop].end(); 433 DI != DE; ++DI) 434 if (Instruction *Inst = DI->second.getPointer()) 435 reverseDepNonLocal[Inst].erase(drop); 436 437 if (reverseDepNonLocal.count(drop)) { 438 SmallPtrSet<Instruction*, 4>& set = 439 reverseDepNonLocal[drop]; 440 for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end(); 441 I != E; ++I) 442 for (DenseMap<BasicBlock*, DepResultTy>::iterator DI = 443 depGraphNonLocal[*I].begin(), DE = depGraphNonLocal[*I].end(); 444 DI != DE; ++DI) 445 if (DI->second == DepResultTy(drop, Normal)) 446 // FIXME: Why not remember the old insertion point?? 447 DI->second = DepResultTy(0, Dirty); 448 } 449 450 reverseDepNonLocal.erase(drop); 451 depGraphNonLocal.erase(drop); 452} 453 454/// removeInstruction - Remove an instruction from the dependence analysis, 455/// updating the dependence of instructions that previously depended on it. 456/// This method attempts to keep the cache coherent using the reverse map. 457void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) { 458 // Walk through the Non-local dependencies, removing this one as the value 459 // for any cached queries. 460 for (DenseMap<BasicBlock*, DepResultTy>::iterator DI = 461 depGraphNonLocal[RemInst].begin(), DE = depGraphNonLocal[RemInst].end(); 462 DI != DE; ++DI) 463 if (Instruction *Inst = DI->second.getPointer()) 464 reverseDepNonLocal[Inst].erase(RemInst); 465 466 // Shortly after this, we will look for things that depend on RemInst. In 467 // order to update these, we'll need a new dependency to base them on. We 468 // could completely delete any entries that depend on this, but it is better 469 // to make a more accurate approximation where possible. Compute that better 470 // approximation if we can. 471 DepResultTy NewDependency; 472 473 // If we have a cached local dependence query for this instruction, remove it. 474 // 475 LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst); 476 if (LocalDepEntry != LocalDeps.end()) { 477 DepResultTy LocalDep = LocalDepEntry->second; 478 479 // Remove this local dependency info. 480 LocalDeps.erase(LocalDepEntry); 481 482 // Remove us from DepInst's reverse set now that the local dep info is gone. 483 if (Instruction *Inst = LocalDep.getPointer()) 484 reverseDep[Inst].erase(RemInst); 485 486 // If we have unconfirmed info, don't trust it. 487 if (LocalDep.getInt() != Dirty) { 488 // If we have a confirmed non-local flag, use it. 489 if (LocalDep.getInt() == NonLocal || LocalDep.getInt() == None) { 490 // The only time this dependency is confirmed is if it is non-local. 491 NewDependency = LocalDep; 492 } else { 493 // If we have dep info for RemInst, set them to it. 494 Instruction *NDI = next(BasicBlock::iterator(LocalDep.getPointer())); 495 if (NDI != RemInst) // Don't use RemInst for the new dependency! 496 NewDependency = DepResultTy(NDI, Dirty); 497 } 498 } 499 } 500 501 // If we don't already have a local dependency answer for this instruction, 502 // use the immediate successor of RemInst. We use the successor because 503 // getDependence starts by checking the immediate predecessor of what is in 504 // the cache. 505 if (NewDependency == DepResultTy(0, Dirty)) 506 NewDependency = DepResultTy(next(BasicBlock::iterator(RemInst)), Dirty); 507 508 // Loop over all of the things that depend on the instruction we're removing. 509 // 510 reverseDepMapType::iterator ReverseDepIt = reverseDep.find(RemInst); 511 if (ReverseDepIt != reverseDep.end()) { 512 SmallPtrSet<Instruction*, 4> &ReverseDeps = ReverseDepIt->second; 513 for (SmallPtrSet<Instruction*, 4>::iterator I = ReverseDeps.begin(), 514 E = ReverseDeps.end(); I != E; ++I) { 515 Instruction *InstDependingOnRemInst = *I; 516 517 // If we thought the instruction depended on itself (possible for 518 // unconfirmed dependencies) ignore the update. 519 if (InstDependingOnRemInst == RemInst) continue; 520 521 // Insert the new dependencies. 522 LocalDeps[InstDependingOnRemInst] = NewDependency; 523 524 // If our NewDependency is an instruction, make sure to remember that new 525 // things depend on it. 526 if (Instruction *Inst = NewDependency.getPointer()) 527 reverseDep[Inst].insert(InstDependingOnRemInst); 528 } 529 reverseDep.erase(RemInst); 530 } 531 532 ReverseDepIt = reverseDepNonLocal.find(RemInst); 533 if (ReverseDepIt != reverseDepNonLocal.end()) { 534 SmallPtrSet<Instruction*, 4>& set = ReverseDepIt->second; 535 for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end(); 536 I != E; ++I) 537 for (DenseMap<BasicBlock*, DepResultTy>::iterator DI = 538 depGraphNonLocal[*I].begin(), DE = depGraphNonLocal[*I].end(); 539 DI != DE; ++DI) 540 if (DI->second == DepResultTy(RemInst, Normal)) 541 // FIXME: Why not remember the old insertion point?? 542 DI->second = DepResultTy(0, Dirty); 543 reverseDepNonLocal.erase(ReverseDepIt); 544 } 545 546 depGraphNonLocal.erase(RemInst); 547 548 getAnalysis<AliasAnalysis>().deleteValue(RemInst); 549 550 DEBUG(verifyRemoved(RemInst)); 551} 552