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