MemoryDependenceAnalysis.cpp revision f2aa160b357c98d8c37b69ea9775aa3e097d1319
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#include "llvm/Analysis/MemoryDependenceAnalysis.h" 18#include "llvm/Constants.h" 19#include "llvm/Instructions.h" 20#include "llvm/Function.h" 21#include "llvm/Analysis/AliasAnalysis.h" 22#include "llvm/Support/CFG.h" 23#include "llvm/Support/CommandLine.h" 24#include "llvm/Target/TargetData.h" 25#include "llvm/ADT/Statistic.h" 26 27#define DEBUG_TYPE "memdep" 28 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 43Instruction* const MemoryDependenceAnalysis::NonLocal = (Instruction*)-3; 44Instruction* const MemoryDependenceAnalysis::None = (Instruction*)-4; 45Instruction* const MemoryDependenceAnalysis::Dirty = (Instruction*)-5; 46 47// Register this pass... 48static RegisterPass<MemoryDependenceAnalysis> X("memdep", 49 "Memory Dependence Analysis", false, true); 50 51void MemoryDependenceAnalysis::ping(Instruction *D) { 52 for (depMapType::iterator I = depGraphLocal.begin(), E = depGraphLocal.end(); 53 I != E; ++I) { 54 assert(I->first != D); 55 assert(I->second.first != D); 56 } 57 58 for (nonLocalDepMapType::iterator I = depGraphNonLocal.begin(), E = depGraphNonLocal.end(); 59 I != E; ++I) { 60 assert(I->first != D); 61 for (DenseMap<BasicBlock*, Value*>::iterator II = I->second.begin(), 62 EE = I->second.end(); II != EE; ++II) 63 assert(II->second != D); 64 } 65 66 for (reverseDepMapType::iterator I = reverseDep.begin(), E = reverseDep.end(); 67 I != E; ++I) 68 for (SmallPtrSet<Instruction*, 4>::iterator II = I->second.begin(), EE = I->second.end(); 69 II != EE; ++II) 70 assert(*II != D); 71 72 for (reverseDepMapType::iterator I = reverseDepNonLocal.begin(), E = reverseDepNonLocal.end(); 73 I != E; ++I) 74 for (SmallPtrSet<Instruction*, 4>::iterator II = I->second.begin(), EE = I->second.end(); 75 II != EE; ++II) 76 assert(*II != D); 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. 89Instruction* MemoryDependenceAnalysis::getCallSiteDependency(CallSite C, 90 Instruction* start, 91 BasicBlock* block) { 92 93 std::pair<Instruction*, bool>& cachedResult = 94 depGraphLocal[C.getInstruction()]; 95 AliasAnalysis& AA = getAnalysis<AliasAnalysis>(); 96 TargetData& TD = getAnalysis<TargetData>(); 97 BasicBlock::iterator blockBegin = C.getInstruction()->getParent()->begin(); 98 BasicBlock::iterator QI = C.getInstruction(); 99 100 // If the starting point was specifiy, use it 101 if (start) { 102 QI = start; 103 blockBegin = start->getParent()->begin(); 104 // If the starting point wasn't specified, but the block was, use it 105 } else if (!start && block) { 106 QI = block->end(); 107 blockBegin = block->begin(); 108 } 109 110 // Walk backwards through the block, looking for dependencies 111 while (QI != blockBegin) { 112 --QI; 113 114 // If this inst is a memory op, get the pointer it accessed 115 Value* pointer = 0; 116 uint64_t pointerSize = 0; 117 if (StoreInst* S = dyn_cast<StoreInst>(QI)) { 118 pointer = S->getPointerOperand(); 119 pointerSize = TD.getTypeStoreSize(S->getOperand(0)->getType()); 120 } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) { 121 pointer = AI; 122 if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize())) 123 pointerSize = C->getZExtValue() * \ 124 TD.getABITypeSize(AI->getAllocatedType()); 125 else 126 pointerSize = ~0UL; 127 } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) { 128 pointer = V->getOperand(0); 129 pointerSize = TD.getTypeStoreSize(V->getType()); 130 } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) { 131 pointer = F->getPointerOperand(); 132 133 // FreeInsts erase the entire structure 134 pointerSize = ~0UL; 135 } else if (CallSite::get(QI).getInstruction() != 0) { 136 AliasAnalysis::ModRefBehavior result = 137 AA.getModRefBehavior(CallSite::get(QI)); 138 if (result != AliasAnalysis::DoesNotAccessMemory) { 139 if (!start && !block) { 140 cachedResult.first = QI; 141 cachedResult.second = true; 142 reverseDep[QI].insert(C.getInstruction()); 143 } 144 return QI; 145 } else { 146 continue; 147 } 148 } else 149 continue; 150 151 if (AA.getModRefInfo(C, pointer, pointerSize) != AliasAnalysis::NoModRef) { 152 if (!start && !block) { 153 cachedResult.first = QI; 154 cachedResult.second = true; 155 reverseDep[QI].insert(C.getInstruction()); 156 } 157 return QI; 158 } 159 } 160 161 // No dependence found 162 cachedResult.first = NonLocal; 163 cachedResult.second = true; 164 reverseDep[NonLocal].insert(C.getInstruction()); 165 return NonLocal; 166} 167 168/// nonLocalHelper - Private helper used to calculate non-local dependencies 169/// by doing DFS on the predecessors of a block to find its dependencies 170void MemoryDependenceAnalysis::nonLocalHelper(Instruction* query, 171 BasicBlock* block, 172 DenseMap<BasicBlock*, Value*>& resp) { 173 // Set of blocks that we've already visited in our DFS 174 SmallPtrSet<BasicBlock*, 4> visited; 175 // If we're updating a dirtied cache entry, we don't need to reprocess 176 // already computed entries. 177 for (DenseMap<BasicBlock*, Value*>::iterator I = resp.begin(), 178 E = resp.end(); I != E; ++I) 179 if (I->second != Dirty) 180 visited.insert(I->first); 181 182 // Current stack of the DFS 183 SmallVector<BasicBlock*, 4> stack; 184 for (pred_iterator PI = pred_begin(block), PE = pred_end(block); 185 PI != PE; ++PI) 186 stack.push_back(*PI); 187 188 // Do a basic DFS 189 while (!stack.empty()) { 190 BasicBlock* BB = stack.back(); 191 192 // If we've already visited this block, no need to revist 193 if (visited.count(BB)) { 194 stack.pop_back(); 195 continue; 196 } 197 198 // If we find a new block with a local dependency for query, 199 // then we insert the new dependency and backtrack. 200 if (BB != block) { 201 visited.insert(BB); 202 203 Instruction* localDep = getDependency(query, 0, BB); 204 if (localDep != NonLocal) { 205 resp.insert(std::make_pair(BB, localDep)); 206 stack.pop_back(); 207 208 continue; 209 } 210 // If we re-encounter the starting block, we still need to search it 211 // because there might be a dependency in the starting block AFTER 212 // the position of the query. This is necessary to get loops right. 213 } else if (BB == block) { 214 visited.insert(BB); 215 216 Instruction* localDep = getDependency(query, 0, BB); 217 if (localDep != query) 218 resp.insert(std::make_pair(BB, localDep)); 219 220 stack.pop_back(); 221 222 continue; 223 } 224 225 // If we didn't find anything, recurse on the precessors of this block 226 // Only do this for blocks with a small number of predecessors. 227 bool predOnStack = false; 228 bool inserted = false; 229 if (std::distance(pred_begin(BB), pred_end(BB)) <= PredLimit) { 230 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); 231 PI != PE; ++PI) 232 if (!visited.count(*PI)) { 233 stack.push_back(*PI); 234 inserted = true; 235 } else 236 predOnStack = true; 237 } 238 239 // If we inserted a new predecessor, then we'll come back to this block 240 if (inserted) 241 continue; 242 // If we didn't insert because we have no predecessors, then this 243 // query has no dependency at all. 244 else if (!inserted && !predOnStack) { 245 resp.insert(std::make_pair(BB, None)); 246 // If we didn't insert because our predecessors are already on the stack, 247 // then we might still have a dependency, but it will be discovered during 248 // backtracking. 249 } else if (!inserted && predOnStack){ 250 resp.insert(std::make_pair(BB, NonLocal)); 251 } 252 253 stack.pop_back(); 254 } 255} 256 257/// getNonLocalDependency - Fills the passed-in map with the non-local 258/// dependencies of the queries. The map will contain NonLocal for 259/// blocks between the query and its dependencies. 260void MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query, 261 DenseMap<BasicBlock*, Value*>& resp) { 262 if (depGraphNonLocal.count(query)) { 263 DenseMap<BasicBlock*, Value*>& cached = depGraphNonLocal[query]; 264 NumCacheNonlocal++; 265 266 SmallVector<BasicBlock*, 4> dirtied; 267 for (DenseMap<BasicBlock*, Value*>::iterator I = cached.begin(), 268 E = cached.end(); I != E; ++I) 269 if (I->second == Dirty) 270 dirtied.push_back(I->first); 271 272 for (SmallVector<BasicBlock*, 4>::iterator I = dirtied.begin(), 273 E = dirtied.end(); I != E; ++I) { 274 Instruction* localDep = getDependency(query, 0, *I); 275 if (localDep != NonLocal) 276 cached[*I] = localDep; 277 else { 278 cached.erase(*I); 279 nonLocalHelper(query, *I, cached); 280 } 281 } 282 283 resp = cached; 284 285 // Update the reverse non-local dependency cache 286 for (DenseMap<BasicBlock*, Value*>::iterator I = resp.begin(), E = resp.end(); 287 I != E; ++I) 288 reverseDepNonLocal[I->second].insert(query); 289 290 return; 291 } else 292 NumUncacheNonlocal++; 293 294 // If not, go ahead and search for non-local deps. 295 nonLocalHelper(query, query->getParent(), resp); 296 297 // Update the non-local dependency cache 298 for (DenseMap<BasicBlock*, Value*>::iterator I = resp.begin(), E = resp.end(); 299 I != E; ++I) { 300 depGraphNonLocal[query].insert(*I); 301 reverseDepNonLocal[I->second].insert(query); 302 } 303} 304 305/// getDependency - Return the instruction on which a memory operation 306/// depends. The local parameter indicates if the query should only 307/// evaluate dependencies within the same basic block. 308Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query, 309 Instruction* start, 310 BasicBlock* block) { 311 // Start looking for dependencies with the queried inst 312 BasicBlock::iterator QI = query; 313 314 // Check for a cached result 315 std::pair<Instruction*, bool>& cachedResult = depGraphLocal[query]; 316 // If we have a _confirmed_ cached entry, return it 317 if (!block && !start) { 318 if (cachedResult.second) 319 return cachedResult.first; 320 else if (cachedResult.first && cachedResult.first != NonLocal) 321 // If we have an unconfirmed cached entry, we can start our search from there 322 QI = cachedResult.first; 323 } 324 325 if (start) 326 QI = start; 327 else if (!start && block) 328 QI = block->end(); 329 330 AliasAnalysis& AA = getAnalysis<AliasAnalysis>(); 331 TargetData& TD = getAnalysis<TargetData>(); 332 333 // Get the pointer value for which dependence will be determined 334 Value* dependee = 0; 335 uint64_t dependeeSize = 0; 336 bool queryIsVolatile = false; 337 if (StoreInst* S = dyn_cast<StoreInst>(query)) { 338 dependee = S->getPointerOperand(); 339 dependeeSize = TD.getTypeStoreSize(S->getOperand(0)->getType()); 340 queryIsVolatile = S->isVolatile(); 341 } else if (LoadInst* L = dyn_cast<LoadInst>(query)) { 342 dependee = L->getPointerOperand(); 343 dependeeSize = TD.getTypeStoreSize(L->getType()); 344 queryIsVolatile = L->isVolatile(); 345 } else if (VAArgInst* V = dyn_cast<VAArgInst>(query)) { 346 dependee = V->getOperand(0); 347 dependeeSize = TD.getTypeStoreSize(V->getType()); 348 } else if (FreeInst* F = dyn_cast<FreeInst>(query)) { 349 dependee = F->getPointerOperand(); 350 351 // FreeInsts erase the entire structure, not just a field 352 dependeeSize = ~0UL; 353 } else if (CallSite::get(query).getInstruction() != 0) 354 return getCallSiteDependency(CallSite::get(query), start, block); 355 else if (isa<AllocationInst>(query)) 356 return None; 357 else 358 return None; 359 360 BasicBlock::iterator blockBegin = block ? block->begin() 361 : query->getParent()->begin(); 362 363 // Walk backwards through the basic block, looking for dependencies 364 while (QI != blockBegin) { 365 --QI; 366 367 // If this inst is a memory op, get the pointer it accessed 368 Value* pointer = 0; 369 uint64_t pointerSize = 0; 370 if (StoreInst* S = dyn_cast<StoreInst>(QI)) { 371 // All volatile loads/stores depend on each other 372 if (queryIsVolatile && S->isVolatile()) { 373 if (!start && !block) { 374 cachedResult.first = S; 375 cachedResult.second = true; 376 reverseDep[S].insert(query); 377 } 378 379 return S; 380 } 381 382 pointer = S->getPointerOperand(); 383 pointerSize = TD.getTypeStoreSize(S->getOperand(0)->getType()); 384 } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) { 385 // All volatile loads/stores depend on each other 386 if (queryIsVolatile && L->isVolatile()) { 387 if (!start && !block) { 388 cachedResult.first = L; 389 cachedResult.second = true; 390 reverseDep[L].insert(query); 391 } 392 393 return L; 394 } 395 396 pointer = L->getPointerOperand(); 397 pointerSize = TD.getTypeStoreSize(L->getType()); 398 } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) { 399 pointer = AI; 400 if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize())) 401 pointerSize = C->getZExtValue() * \ 402 TD.getABITypeSize(AI->getAllocatedType()); 403 else 404 pointerSize = ~0UL; 405 } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) { 406 pointer = V->getOperand(0); 407 pointerSize = TD.getTypeStoreSize(V->getType()); 408 } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) { 409 pointer = F->getPointerOperand(); 410 411 // FreeInsts erase the entire structure 412 pointerSize = ~0UL; 413 } else if (CallSite::get(QI).getInstruction() != 0) { 414 // Call insts need special handling. Check if they can modify our pointer 415 AliasAnalysis::ModRefResult MR = AA.getModRefInfo(CallSite::get(QI), 416 dependee, dependeeSize); 417 418 if (MR != AliasAnalysis::NoModRef) { 419 // Loads don't depend on read-only calls 420 if (isa<LoadInst>(query) && MR == AliasAnalysis::Ref) 421 continue; 422 423 if (!start && !block) { 424 cachedResult.first = QI; 425 cachedResult.second = true; 426 reverseDep[QI].insert(query); 427 } 428 429 return QI; 430 } else { 431 continue; 432 } 433 } 434 435 // If we found a pointer, check if it could be the same as our pointer 436 if (pointer) { 437 AliasAnalysis::AliasResult R = AA.alias(pointer, pointerSize, 438 dependee, dependeeSize); 439 440 if (R != AliasAnalysis::NoAlias) { 441 // May-alias loads don't depend on each other 442 if (isa<LoadInst>(query) && isa<LoadInst>(QI) && 443 R == AliasAnalysis::MayAlias) 444 continue; 445 446 if (!start && !block) { 447 cachedResult.first = QI; 448 cachedResult.second = true; 449 reverseDep[QI].insert(query); 450 } 451 452 return QI; 453 } 454 } 455 } 456 457 // If we found nothing, return the non-local flag 458 if (!start && !block) { 459 cachedResult.first = NonLocal; 460 cachedResult.second = true; 461 reverseDep[NonLocal].insert(query); 462 } 463 464 return NonLocal; 465} 466 467/// dropInstruction - Remove an instruction from the analysis, making 468/// absolutely conservative assumptions when updating the cache. This is 469/// useful, for example when an instruction is changed rather than removed. 470void MemoryDependenceAnalysis::dropInstruction(Instruction* drop) { 471 depMapType::iterator depGraphEntry = depGraphLocal.find(drop); 472 if (depGraphEntry != depGraphLocal.end()) 473 reverseDep[depGraphEntry->second.first].erase(drop); 474 475 // Drop dependency information for things that depended on this instr 476 SmallPtrSet<Instruction*, 4>& set = reverseDep[drop]; 477 for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end(); 478 I != E; ++I) 479 depGraphLocal.erase(*I); 480 481 depGraphLocal.erase(drop); 482 reverseDep.erase(drop); 483 484 for (DenseMap<BasicBlock*, Value*>::iterator DI = 485 depGraphNonLocal[drop].begin(), DE = depGraphNonLocal[drop].end(); 486 DI != DE; ++DI) 487 if (DI->second != None) 488 reverseDepNonLocal[DI->second].erase(drop); 489 490 if (reverseDepNonLocal.count(drop)) { 491 SmallPtrSet<Instruction*, 4>& set = reverseDepNonLocal[drop]; 492 for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end(); 493 I != E; ++I) 494 for (DenseMap<BasicBlock*, Value*>::iterator DI = 495 depGraphNonLocal[*I].begin(), DE = depGraphNonLocal[*I].end(); 496 DI != DE; ++DI) 497 if (DI->second == drop) 498 DI->second = Dirty; 499 } 500 501 reverseDepNonLocal.erase(drop); 502 nonLocalDepMapType::iterator I = depGraphNonLocal.find(drop); 503 if (I != depGraphNonLocal.end()) 504 depGraphNonLocal.erase(I); 505} 506 507/// removeInstruction - Remove an instruction from the dependence analysis, 508/// updating the dependence of instructions that previously depended on it. 509/// This method attempts to keep the cache coherent using the reverse map. 510void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) { 511 // Figure out the new dep for things that currently depend on rem 512 Instruction* newDep = NonLocal; 513 514 for (DenseMap<BasicBlock*, Value*>::iterator DI = 515 depGraphNonLocal[rem].begin(), DE = depGraphNonLocal[rem].end(); 516 DI != DE; ++DI) 517 if (DI->second != None) 518 reverseDepNonLocal[DI->second].erase(rem); 519 520 depMapType::iterator depGraphEntry = depGraphLocal.find(rem); 521 522 if (depGraphEntry != depGraphLocal.end()) { 523 reverseDep[depGraphEntry->second.first].erase(rem); 524 525 if (depGraphEntry->second.first != NonLocal && 526 depGraphEntry->second.first != None && 527 depGraphEntry->second.second) { 528 // If we have dep info for rem, set them to it 529 BasicBlock::iterator RI = depGraphEntry->second.first; 530 RI++; 531 newDep = RI; 532 } else if ( (depGraphEntry->second.first == NonLocal || 533 depGraphEntry->second.first == None ) && 534 depGraphEntry->second.second ) { 535 // If we have a confirmed non-local flag, use it 536 newDep = depGraphEntry->second.first; 537 } else { 538 // Otherwise, use the immediate successor of rem 539 // NOTE: This is because, when getDependence is called, it will first 540 // check the immediate predecessor of what is in the cache. 541 BasicBlock::iterator RI = rem; 542 RI++; 543 newDep = RI; 544 } 545 } else { 546 // Otherwise, use the immediate successor of rem 547 // NOTE: This is because, when getDependence is called, it will first 548 // check the immediate predecessor of what is in the cache. 549 BasicBlock::iterator RI = rem; 550 RI++; 551 newDep = RI; 552 } 553 554 SmallPtrSet<Instruction*, 4>& set = reverseDep[rem]; 555 for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end(); 556 I != E; ++I) { 557 // Insert the new dependencies 558 // Mark it as unconfirmed as long as it is not the non-local flag 559 depGraphLocal[*I] = std::make_pair(newDep, (newDep == NonLocal || 560 newDep == None)); 561 } 562 563 depGraphLocal.erase(rem); 564 reverseDep.erase(rem); 565 566 if (reverseDepNonLocal.count(rem)) { 567 SmallPtrSet<Instruction*, 4>& set = reverseDepNonLocal[rem]; 568 for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end(); 569 I != E; ++I) 570 for (DenseMap<BasicBlock*, Value*>::iterator DI = 571 depGraphNonLocal[*I].begin(), DE = depGraphNonLocal[*I].end(); 572 DI != DE; ++DI) 573 if (DI->second == rem) 574 DI->second = Dirty; 575 576 } 577 578 reverseDepNonLocal.erase(rem); 579 nonLocalDepMapType::iterator I = depGraphNonLocal.find(rem); 580 if (I != depGraphNonLocal.end()) 581 depGraphNonLocal.erase(I); 582 583 getAnalysis<AliasAnalysis>().deleteValue(rem); 584} 585