MemoryDependenceAnalysis.cpp revision f062f10231590919d9d78ee2f7d3cb29f1c09e66
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 31namespace { 32 // Control the calculation of non-local dependencies by only examining the 33 // predecessors if the basic block has less than X amount (50 by default). 34 cl::opt<int> 35 PredLimit("nonlocaldep-threshold", cl::Hidden, cl::init(50), 36 cl::desc("Control the calculation of non-local" 37 "dependencies (default = 50)")); 38} 39 40STATISTIC(NumCacheNonlocal, "Number of cached non-local responses"); 41STATISTIC(NumUncacheNonlocal, "Number of uncached non-local responses"); 42 43char MemoryDependenceAnalysis::ID = 0; 44 45Instruction* const MemoryDependenceAnalysis::NonLocal = (Instruction*)-3; 46Instruction* const MemoryDependenceAnalysis::None = (Instruction*)-4; 47Instruction* const MemoryDependenceAnalysis::Dirty = (Instruction*)-5; 48 49// Register this pass... 50static RegisterPass<MemoryDependenceAnalysis> X("memdep", 51 "Memory Dependence Analysis", false, true); 52 53void MemoryDependenceAnalysis::ping(Instruction *D) { 54 for (depMapType::iterator I = depGraphLocal.begin(), E = depGraphLocal.end(); 55 I != E; ++I) { 56 assert(I->first != D); 57 assert(I->second.first != D); 58 } 59 60 for (nonLocalDepMapType::iterator I = depGraphNonLocal.begin(), E = depGraphNonLocal.end(); 61 I != E; ++I) { 62 assert(I->first != D); 63 } 64 65 for (reverseDepMapType::iterator I = reverseDep.begin(), E = reverseDep.end(); 66 I != E; ++I) 67 for (SmallPtrSet<Instruction*, 4>::iterator II = I->second.begin(), EE = I->second.end(); 68 II != EE; ++II) 69 assert(*II != D); 70 71 for (reverseDepMapType::iterator I = reverseDepNonLocal.begin(), E = reverseDepNonLocal.end(); 72 I != E; ++I) 73 for (SmallPtrSet<Instruction*, 4>::iterator II = I->second.begin(), EE = I->second.end(); 74 II != EE; ++II) 75 assert(*II != D); 76} 77 78/// getAnalysisUsage - Does not modify anything. It uses Alias Analysis. 79/// 80void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 81 AU.setPreservesAll(); 82 AU.addRequiredTransitive<AliasAnalysis>(); 83 AU.addRequiredTransitive<TargetData>(); 84} 85 86/// getCallSiteDependency - Private helper for finding the local dependencies 87/// of a call site. 88Instruction* MemoryDependenceAnalysis::getCallSiteDependency(CallSite C, 89 Instruction* start, 90 BasicBlock* block) { 91 92 std::pair<Instruction*, bool>& cachedResult = 93 depGraphLocal[C.getInstruction()]; 94 AliasAnalysis& AA = getAnalysis<AliasAnalysis>(); 95 TargetData& TD = getAnalysis<TargetData>(); 96 BasicBlock::iterator blockBegin = C.getInstruction()->getParent()->begin(); 97 BasicBlock::iterator QI = C.getInstruction(); 98 99 // If the starting point was specifiy, use it 100 if (start) { 101 QI = start; 102 blockBegin = start->getParent()->begin(); 103 // If the starting point wasn't specified, but the block was, use it 104 } else if (!start && block) { 105 QI = block->end(); 106 blockBegin = block->begin(); 107 } 108 109 // Walk backwards through the block, looking for dependencies 110 while (QI != blockBegin) { 111 --QI; 112 113 // If this inst is a memory op, get the pointer it accessed 114 Value* pointer = 0; 115 uint64_t pointerSize = 0; 116 if (StoreInst* S = dyn_cast<StoreInst>(QI)) { 117 pointer = S->getPointerOperand(); 118 pointerSize = TD.getTypeStoreSize(S->getOperand(0)->getType()); 119 } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) { 120 pointer = AI; 121 if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize())) 122 pointerSize = C->getZExtValue() * \ 123 TD.getABITypeSize(AI->getAllocatedType()); 124 else 125 pointerSize = ~0UL; 126 } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) { 127 pointer = V->getOperand(0); 128 pointerSize = TD.getTypeStoreSize(V->getType()); 129 } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) { 130 pointer = F->getPointerOperand(); 131 132 // FreeInsts erase the entire structure 133 pointerSize = ~0UL; 134 } else if (isa<CallInst>(QI)) { 135 AliasAnalysis::ModRefBehavior result = 136 AA.getModRefBehavior(CallSite::get(QI)); 137 if (result != AliasAnalysis::DoesNotAccessMemory && 138 result != AliasAnalysis::OnlyReadsMemory) { 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 return; 286 } else 287 NumUncacheNonlocal++; 288 289 // If not, go ahead and search for non-local deps. 290 nonLocalHelper(query, query->getParent(), resp); 291 292 // Update the non-local dependency cache 293 for (DenseMap<BasicBlock*, Value*>::iterator I = resp.begin(), E = resp.end(); 294 I != E; ++I) { 295 depGraphNonLocal[query].insert(*I); 296 reverseDepNonLocal[I->second].insert(query); 297 } 298} 299 300/// getDependency - Return the instruction on which a memory operation 301/// depends. The local paramter indicates if the query should only 302/// evaluate dependencies within the same basic block. 303Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query, 304 Instruction* start, 305 BasicBlock* block) { 306 // Start looking for dependencies with the queried inst 307 BasicBlock::iterator QI = query; 308 309 // Check for a cached result 310 std::pair<Instruction*, bool>& cachedResult = depGraphLocal[query]; 311 // If we have a _confirmed_ cached entry, return it 312 if (!block && !start) { 313 if (cachedResult.second) 314 return cachedResult.first; 315 else if (cachedResult.first && cachedResult.first != NonLocal) 316 // If we have an unconfirmed cached entry, we can start our search from there 317 QI = cachedResult.first; 318 } 319 320 if (start) 321 QI = start; 322 else if (!start && block) 323 QI = block->end(); 324 325 AliasAnalysis& AA = getAnalysis<AliasAnalysis>(); 326 TargetData& TD = getAnalysis<TargetData>(); 327 328 // Get the pointer value for which dependence will be determined 329 Value* dependee = 0; 330 uint64_t dependeeSize = 0; 331 bool queryIsVolatile = false; 332 if (StoreInst* S = dyn_cast<StoreInst>(query)) { 333 dependee = S->getPointerOperand(); 334 dependeeSize = TD.getTypeStoreSize(S->getOperand(0)->getType()); 335 queryIsVolatile = S->isVolatile(); 336 } else if (LoadInst* L = dyn_cast<LoadInst>(query)) { 337 dependee = L->getPointerOperand(); 338 dependeeSize = TD.getTypeStoreSize(L->getType()); 339 queryIsVolatile = L->isVolatile(); 340 } else if (VAArgInst* V = dyn_cast<VAArgInst>(query)) { 341 dependee = V->getOperand(0); 342 dependeeSize = TD.getTypeStoreSize(V->getType()); 343 } else if (FreeInst* F = dyn_cast<FreeInst>(query)) { 344 dependee = F->getPointerOperand(); 345 346 // FreeInsts erase the entire structure, not just a field 347 dependeeSize = ~0UL; 348 } else if (CallSite::get(query).getInstruction() != 0) 349 return getCallSiteDependency(CallSite::get(query), start, block); 350 else if (isa<AllocationInst>(query)) 351 return None; 352 else 353 return None; 354 355 BasicBlock::iterator blockBegin = block ? block->begin() 356 : query->getParent()->begin(); 357 358 // Walk backwards through the basic block, looking for dependencies 359 while (QI != blockBegin) { 360 --QI; 361 362 // If this inst is a memory op, get the pointer it accessed 363 Value* pointer = 0; 364 uint64_t pointerSize = 0; 365 if (StoreInst* S = dyn_cast<StoreInst>(QI)) { 366 // All volatile loads/stores depend on each other 367 if (queryIsVolatile && S->isVolatile()) { 368 if (!start && !block) { 369 cachedResult.first = S; 370 cachedResult.second = true; 371 reverseDep[S].insert(query); 372 } 373 374 return S; 375 } 376 377 pointer = S->getPointerOperand(); 378 pointerSize = TD.getTypeStoreSize(S->getOperand(0)->getType()); 379 } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) { 380 // All volatile loads/stores depend on each other 381 if (queryIsVolatile && L->isVolatile()) { 382 if (!start && !block) { 383 cachedResult.first = L; 384 cachedResult.second = true; 385 reverseDep[L].insert(query); 386 } 387 388 return L; 389 } 390 391 pointer = L->getPointerOperand(); 392 pointerSize = TD.getTypeStoreSize(L->getType()); 393 } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) { 394 pointer = AI; 395 if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize())) 396 pointerSize = C->getZExtValue() * \ 397 TD.getABITypeSize(AI->getAllocatedType()); 398 else 399 pointerSize = ~0UL; 400 } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) { 401 pointer = V->getOperand(0); 402 pointerSize = TD.getTypeStoreSize(V->getType()); 403 } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) { 404 pointer = F->getPointerOperand(); 405 406 // FreeInsts erase the entire structure 407 pointerSize = ~0UL; 408 } else if (CallSite::get(QI).getInstruction() != 0) { 409 // Call insts need special handling. Check if they can modify our pointer 410 AliasAnalysis::ModRefResult MR = AA.getModRefInfo(CallSite::get(QI), 411 dependee, dependeeSize); 412 413 if (MR != AliasAnalysis::NoModRef) { 414 // Loads don't depend on read-only calls 415 if (isa<LoadInst>(query) && MR == AliasAnalysis::Ref) 416 continue; 417 418 if (!start && !block) { 419 cachedResult.first = QI; 420 cachedResult.second = true; 421 reverseDep[QI].insert(query); 422 } 423 424 return QI; 425 } else { 426 continue; 427 } 428 } 429 430 // If we found a pointer, check if it could be the same as our pointer 431 if (pointer) { 432 AliasAnalysis::AliasResult R = AA.alias(pointer, pointerSize, 433 dependee, dependeeSize); 434 435 if (R != AliasAnalysis::NoAlias) { 436 // May-alias loads don't depend on each other 437 if (isa<LoadInst>(query) && isa<LoadInst>(QI) && 438 R == AliasAnalysis::MayAlias) 439 continue; 440 441 if (!start && !block) { 442 cachedResult.first = QI; 443 cachedResult.second = true; 444 reverseDep[QI].insert(query); 445 } 446 447 return QI; 448 } 449 } 450 } 451 452 // If we found nothing, return the non-local flag 453 if (!start && !block) { 454 cachedResult.first = NonLocal; 455 cachedResult.second = true; 456 reverseDep[NonLocal].insert(query); 457 } 458 459 return NonLocal; 460} 461 462/// dropInstruction - Remove an instruction from the analysis, making 463/// absolutely conservative assumptions when updating the cache. This is 464/// useful, for example when an instruction is changed rather than removed. 465void MemoryDependenceAnalysis::dropInstruction(Instruction* drop) { 466 depMapType::iterator depGraphEntry = depGraphLocal.find(drop); 467 if (depGraphEntry != depGraphLocal.end()) 468 reverseDep[depGraphEntry->second.first].erase(drop); 469 470 // Drop dependency information for things that depended on this instr 471 SmallPtrSet<Instruction*, 4>& set = reverseDep[drop]; 472 for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end(); 473 I != E; ++I) 474 depGraphLocal.erase(*I); 475 476 depGraphLocal.erase(drop); 477 reverseDep.erase(drop); 478 479 for (DenseMap<BasicBlock*, Value*>::iterator DI = 480 depGraphNonLocal[drop].begin(), DE = depGraphNonLocal[drop].end(); 481 DI != DE; ++DI) 482 if (DI->second != None) 483 reverseDepNonLocal[DI->second].erase(drop); 484 485 if (reverseDepNonLocal.count(drop)) { 486 SmallPtrSet<Instruction*, 4>& set = reverseDepNonLocal[drop]; 487 for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end(); 488 I != E; ++I) 489 for (DenseMap<BasicBlock*, Value*>::iterator DI = 490 depGraphNonLocal[*I].begin(), DE = depGraphNonLocal[*I].end(); 491 DI != DE; ++DI) 492 if (DI->second == drop) 493 DI->second = Dirty; 494 } 495 496 reverseDepNonLocal.erase(drop); 497 nonLocalDepMapType::iterator I = depGraphNonLocal.find(drop); 498 if (I != depGraphNonLocal.end()) 499 depGraphNonLocal.erase(I); 500} 501 502/// removeInstruction - Remove an instruction from the dependence analysis, 503/// updating the dependence of instructions that previously depended on it. 504/// This method attempts to keep the cache coherent using the reverse map. 505void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) { 506 // Figure out the new dep for things that currently depend on rem 507 Instruction* newDep = NonLocal; 508 509 for (DenseMap<BasicBlock*, Value*>::iterator DI = 510 depGraphNonLocal[rem].begin(), DE = depGraphNonLocal[rem].end(); 511 DI != DE; ++DI) 512 if (DI->second != None) 513 reverseDepNonLocal[DI->second].erase(rem); 514 515 depMapType::iterator depGraphEntry = depGraphLocal.find(rem); 516 517 if (depGraphEntry != depGraphLocal.end()) { 518 reverseDep[depGraphEntry->second.first].erase(rem); 519 520 if (depGraphEntry->second.first != NonLocal && 521 depGraphEntry->second.first != None && 522 depGraphEntry->second.second) { 523 // If we have dep info for rem, set them to it 524 BasicBlock::iterator RI = depGraphEntry->second.first; 525 RI++; 526 newDep = RI; 527 } else if ( (depGraphEntry->second.first == NonLocal || 528 depGraphEntry->second.first == None ) && 529 depGraphEntry->second.second ) { 530 // If we have a confirmed non-local flag, use it 531 newDep = depGraphEntry->second.first; 532 } else { 533 // Otherwise, use the immediate successor of rem 534 // NOTE: This is because, when getDependence is called, it will first 535 // check the immediate predecessor of what is in the cache. 536 BasicBlock::iterator RI = rem; 537 RI++; 538 newDep = RI; 539 } 540 } else { 541 // Otherwise, use the immediate successor of rem 542 // NOTE: This is because, when getDependence is called, it will first 543 // check the immediate predecessor of what is in the cache. 544 BasicBlock::iterator RI = rem; 545 RI++; 546 newDep = RI; 547 } 548 549 SmallPtrSet<Instruction*, 4>& set = reverseDep[rem]; 550 for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end(); 551 I != E; ++I) { 552 // Insert the new dependencies 553 // Mark it as unconfirmed as long as it is not the non-local flag 554 depGraphLocal[*I] = std::make_pair(newDep, (newDep == NonLocal || 555 newDep == None)); 556 } 557 558 depGraphLocal.erase(rem); 559 reverseDep.erase(rem); 560 561 if (reverseDepNonLocal.count(rem)) { 562 SmallPtrSet<Instruction*, 4>& set = reverseDepNonLocal[rem]; 563 for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end(); 564 I != E; ++I) 565 for (DenseMap<BasicBlock*, Value*>::iterator DI = 566 depGraphNonLocal[*I].begin(), DE = depGraphNonLocal[*I].end(); 567 DI != DE; ++DI) 568 if (DI->second == rem) 569 DI->second = Dirty; 570 571 } 572 573 reverseDepNonLocal.erase(rem); 574 nonLocalDepMapType::iterator I = depGraphNonLocal.find(rem); 575 if (I != depGraphNonLocal.end()) 576 depGraphNonLocal.erase(I); 577 578 getAnalysis<AliasAnalysis>().deleteValue(rem); 579} 580