MemoryDependenceAnalysis.cpp revision 396a4a55e535728e2023aa331401c1a2b782cb9a
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 31STATISTIC(NumCacheNonlocal, "Number of cached non-local responses"); 32STATISTIC(NumUncacheNonlocal, "Number of uncached non-local responses"); 33 34char MemoryDependenceAnalysis::ID = 0; 35 36// Register this pass... 37static RegisterPass<MemoryDependenceAnalysis> X("memdep", 38 "Memory Dependence Analysis", false, true); 39 40/// getAnalysisUsage - Does not modify anything. It uses Alias Analysis. 41/// 42void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 43 AU.setPreservesAll(); 44 AU.addRequiredTransitive<AliasAnalysis>(); 45 AU.addRequiredTransitive<TargetData>(); 46} 47 48/// getCallSiteDependency - Private helper for finding the local dependencies 49/// of a call site. 50MemDepResult MemoryDependenceAnalysis:: 51getCallSiteDependency(CallSite C, BasicBlock::iterator ScanIt, 52 BasicBlock *BB) { 53 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 54 TargetData &TD = getAnalysis<TargetData>(); 55 56 // Walk backwards through the block, looking for dependencies 57 while (ScanIt != BB->begin()) { 58 Instruction *Inst = --ScanIt; 59 60 // If this inst is a memory op, get the pointer it accessed 61 Value *Pointer = 0; 62 uint64_t PointerSize = 0; 63 if (StoreInst *S = dyn_cast<StoreInst>(Inst)) { 64 Pointer = S->getPointerOperand(); 65 PointerSize = TD.getTypeStoreSize(S->getOperand(0)->getType()); 66 } else if (AllocationInst *AI = dyn_cast<AllocationInst>(Inst)) { 67 Pointer = AI; 68 if (ConstantInt *C = dyn_cast<ConstantInt>(AI->getArraySize())) 69 // Use ABI size (size between elements), not store size (size of one 70 // element without padding). 71 PointerSize = C->getZExtValue() * 72 TD.getABITypeSize(AI->getAllocatedType()); 73 else 74 PointerSize = ~0UL; 75 } else if (VAArgInst *V = dyn_cast<VAArgInst>(Inst)) { 76 Pointer = V->getOperand(0); 77 PointerSize = TD.getTypeStoreSize(V->getType()); 78 } else if (FreeInst *F = dyn_cast<FreeInst>(Inst)) { 79 Pointer = F->getPointerOperand(); 80 81 // FreeInsts erase the entire structure 82 PointerSize = ~0UL; 83 } else if (isa<CallInst>(Inst) || isa<InvokeInst>(Inst)) { 84 if (AA.getModRefBehavior(CallSite::get(Inst)) == 85 AliasAnalysis::DoesNotAccessMemory) 86 continue; 87 return MemDepResult::get(Inst); 88 } else 89 continue; 90 91 if (AA.getModRefInfo(C, Pointer, PointerSize) != AliasAnalysis::NoModRef) 92 return MemDepResult::get(Inst); 93 } 94 95 // No dependence found. 96 return MemDepResult::getNonLocal(); 97} 98 99/// getNonLocalDependency - Perform a full dependency query for the 100/// specified instruction, returning the set of blocks that the value is 101/// potentially live across. The returned set of results will include a 102/// "NonLocal" result for all blocks where the value is live across. 103/// 104/// This method assumes the instruction returns a "nonlocal" dependency 105/// within its own block. 106/// 107void MemoryDependenceAnalysis:: 108getNonLocalDependency(Instruction *QueryInst, 109 SmallVectorImpl<std::pair<BasicBlock*, 110 MemDepResult> > &Result) { 111 assert(getDependency(QueryInst).isNonLocal() && 112 "getNonLocalDependency should only be used on insts with non-local deps!"); 113 DenseMap<BasicBlock*, DepResultTy> &Cache = NonLocalDeps[QueryInst]; 114 115 /// DirtyBlocks - This is the set of blocks that need to be recomputed. This 116 /// can happen due to instructions being deleted etc. 117 SmallVector<BasicBlock*, 32> DirtyBlocks; 118 119 if (!Cache.empty()) { 120 // If we already have a partially computed set of results, scan them to 121 // determine what is dirty, seeding our initial DirtyBlocks worklist. 122 // FIXME: In the "don't need to be updated" case, this is expensive, why not 123 // have a per-"cache" flag saying it is undirty? 124 for (DenseMap<BasicBlock*, DepResultTy>::iterator I = Cache.begin(), 125 E = Cache.end(); I != E; ++I) 126 if (I->second.getInt() == Dirty) 127 DirtyBlocks.push_back(I->first); 128 129 NumCacheNonlocal++; 130 } else { 131 // Seed DirtyBlocks with each of the preds of QueryInst's block. 132 BasicBlock *QueryBB = QueryInst->getParent(); 133 DirtyBlocks.append(pred_begin(QueryBB), pred_end(QueryBB)); 134 NumUncacheNonlocal++; 135 } 136 137 // Iterate while we still have blocks to update. 138 while (!DirtyBlocks.empty()) { 139 BasicBlock *DirtyBB = DirtyBlocks.back(); 140 DirtyBlocks.pop_back(); 141 142 // Get the entry for this block. Note that this relies on DepResultTy 143 // default initializing to Dirty. 144 DepResultTy &DirtyBBEntry = Cache[DirtyBB]; 145 146 // If DirtyBBEntry isn't dirty, it ended up on the worklist multiple times. 147 if (DirtyBBEntry.getInt() != Dirty) continue; 148 149 // Find out if this block has a local dependency for QueryInst. 150 // FIXME: If the dirty entry has an instruction pointer, scan from it! 151 // FIXME: Don't convert back and forth for MemDepResult <-> DepResultTy. 152 DirtyBBEntry = ConvFromResult(getDependencyFrom(QueryInst, DirtyBB->end(), 153 DirtyBB)); 154 155 // If the block has a dependency (i.e. it isn't completely transparent to 156 // the value), remember it! 157 if (DirtyBBEntry.getInt() != NonLocal) { 158 // Keep the ReverseNonLocalDeps map up to date so we can efficiently 159 // update this when we remove instructions. 160 if (Instruction *Inst = DirtyBBEntry.getPointer()) 161 ReverseNonLocalDeps[Inst].insert(QueryInst); 162 continue; 163 } 164 165 // If the block *is* completely transparent to the load, we need to check 166 // the predecessors of this block. Add them to our worklist. 167 for (pred_iterator I = pred_begin(DirtyBB), E = pred_end(DirtyBB); 168 I != E; ++I) 169 DirtyBlocks.push_back(*I); 170 } 171 172 // Copy the result into the output set. 173 for (DenseMap<BasicBlock*, DepResultTy>::iterator I = Cache.begin(), 174 E = Cache.end(); I != E; ++I) 175 Result.push_back(std::make_pair(I->first, ConvToResult(I->second))); 176} 177 178/// getDependency - Return the instruction on which a memory operation 179/// depends. The local parameter indicates if the query should only 180/// evaluate dependencies within the same basic block. 181MemDepResult MemoryDependenceAnalysis:: 182getDependencyFrom(Instruction *QueryInst, BasicBlock::iterator ScanIt, 183 BasicBlock *BB) { 184 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 185 TargetData &TD = getAnalysis<TargetData>(); 186 187 // Get the pointer value for which dependence will be determined 188 Value *MemPtr = 0; 189 uint64_t MemSize = 0; 190 bool MemVolatile = false; 191 192 if (StoreInst* S = dyn_cast<StoreInst>(QueryInst)) { 193 MemPtr = S->getPointerOperand(); 194 MemSize = TD.getTypeStoreSize(S->getOperand(0)->getType()); 195 MemVolatile = S->isVolatile(); 196 } else if (LoadInst* L = dyn_cast<LoadInst>(QueryInst)) { 197 MemPtr = L->getPointerOperand(); 198 MemSize = TD.getTypeStoreSize(L->getType()); 199 MemVolatile = L->isVolatile(); 200 } else if (VAArgInst* V = dyn_cast<VAArgInst>(QueryInst)) { 201 MemPtr = V->getOperand(0); 202 MemSize = TD.getTypeStoreSize(V->getType()); 203 } else if (FreeInst* F = dyn_cast<FreeInst>(QueryInst)) { 204 MemPtr = F->getPointerOperand(); 205 // FreeInsts erase the entire structure, not just a field. 206 MemSize = ~0UL; 207 } else if (isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst)) 208 return getCallSiteDependency(CallSite::get(QueryInst), ScanIt, BB); 209 else // Non-memory instructions depend on nothing. 210 return MemDepResult::getNone(); 211 212 // Walk backwards through the basic block, looking for dependencies 213 while (ScanIt != BB->begin()) { 214 Instruction *Inst = --ScanIt; 215 216 // If the access is volatile and this is a volatile load/store, return a 217 // dependence. 218 if (MemVolatile && 219 ((isa<LoadInst>(Inst) && cast<LoadInst>(Inst)->isVolatile()) || 220 (isa<StoreInst>(Inst) && cast<StoreInst>(Inst)->isVolatile()))) 221 return MemDepResult::get(Inst); 222 223 // MemDep is broken w.r.t. loads: it says that two loads of the same pointer 224 // depend on each other. :( 225 // FIXME: ELIMINATE THIS! 226 if (LoadInst *L = dyn_cast<LoadInst>(Inst)) { 227 Value *Pointer = L->getPointerOperand(); 228 uint64_t PointerSize = TD.getTypeStoreSize(L->getType()); 229 230 // If we found a pointer, check if it could be the same as our pointer 231 AliasAnalysis::AliasResult R = 232 AA.alias(Pointer, PointerSize, MemPtr, MemSize); 233 234 if (R == AliasAnalysis::NoAlias) 235 continue; 236 237 // May-alias loads don't depend on each other without a dependence. 238 if (isa<LoadInst>(QueryInst) && R == AliasAnalysis::MayAlias) 239 continue; 240 return MemDepResult::get(Inst); 241 } 242 243 // FIXME: This claims that an access depends on the allocation. This may 244 // make sense, but is dubious at best. It would be better to fix GVN to 245 // handle a 'None' Query. 246 if (AllocationInst *AI = dyn_cast<AllocationInst>(Inst)) { 247 Value *Pointer = AI; 248 uint64_t PointerSize; 249 if (ConstantInt *C = dyn_cast<ConstantInt>(AI->getArraySize())) 250 // Use ABI size (size between elements), not store size (size of one 251 // element without padding). 252 PointerSize = C->getZExtValue() * 253 TD.getABITypeSize(AI->getAllocatedType()); 254 else 255 PointerSize = ~0UL; 256 257 AliasAnalysis::AliasResult R = 258 AA.alias(Pointer, PointerSize, MemPtr, MemSize); 259 260 if (R == AliasAnalysis::NoAlias) 261 continue; 262 return MemDepResult::get(Inst); 263 } 264 265 266 // See if this instruction mod/ref's the pointer. 267 AliasAnalysis::ModRefResult MRR = AA.getModRefInfo(Inst, MemPtr, MemSize); 268 269 if (MRR == AliasAnalysis::NoModRef) 270 continue; 271 272 // Loads don't depend on read-only instructions. 273 if (isa<LoadInst>(QueryInst) && MRR == AliasAnalysis::Ref) 274 continue; 275 276 // Otherwise, there is a dependence. 277 return MemDepResult::get(Inst); 278 } 279 280 // If we found nothing, return the non-local flag. 281 return MemDepResult::getNonLocal(); 282} 283 284/// getDependency - Return the instruction on which a memory operation 285/// depends. 286MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) { 287 Instruction *ScanPos = QueryInst; 288 289 // Check for a cached result 290 DepResultTy &LocalCache = LocalDeps[QueryInst]; 291 292 // If the cached entry is non-dirty, just return it. 293 if (LocalCache.getInt() != Dirty) 294 return ConvToResult(LocalCache); 295 296 // Otherwise, if we have a dirty entry, we know we can start the scan at that 297 // instruction, which may save us some work. 298 if (Instruction *Inst = LocalCache.getPointer()) 299 ScanPos = Inst; 300 301 // Do the scan. 302 MemDepResult Res = 303 getDependencyFrom(QueryInst, ScanPos, QueryInst->getParent()); 304 305 // Remember the result! 306 // FIXME: Don't convert back and forth! Make a shared helper function. 307 LocalCache = ConvFromResult(Res); 308 if (Instruction *I = Res.getInst()) 309 ReverseLocalDeps[I].insert(QueryInst); 310 311 return Res; 312} 313 314 315/// dropInstruction - Remove an instruction from the analysis, making 316/// absolutely conservative assumptions when updating the cache. This is 317/// useful, for example when an instruction is changed rather than removed. 318void MemoryDependenceAnalysis::dropInstruction(Instruction* drop) { 319 LocalDepMapType::iterator depGraphEntry = LocalDeps.find(drop); 320 if (depGraphEntry != LocalDeps.end()) 321 if (Instruction *Inst = depGraphEntry->second.getPointer()) 322 ReverseLocalDeps[Inst].erase(drop); 323 324 // Drop dependency information for things that depended on this instr 325 SmallPtrSet<Instruction*, 4>& set = ReverseLocalDeps[drop]; 326 for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end(); 327 I != E; ++I) 328 LocalDeps.erase(*I); 329 330 LocalDeps.erase(drop); 331 ReverseLocalDeps.erase(drop); 332 333 for (DenseMap<BasicBlock*, DepResultTy>::iterator DI = 334 NonLocalDeps[drop].begin(), DE = NonLocalDeps[drop].end(); 335 DI != DE; ++DI) 336 if (Instruction *Inst = DI->second.getPointer()) 337 ReverseNonLocalDeps[Inst].erase(drop); 338 339 if (ReverseNonLocalDeps.count(drop)) { 340 SmallPtrSet<Instruction*, 4>& set = 341 ReverseNonLocalDeps[drop]; 342 for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end(); 343 I != E; ++I) 344 for (DenseMap<BasicBlock*, DepResultTy>::iterator DI = 345 NonLocalDeps[*I].begin(), DE = NonLocalDeps[*I].end(); 346 DI != DE; ++DI) 347 if (DI->second == DepResultTy(drop, Normal)) 348 // FIXME: Why not remember the old insertion point?? 349 DI->second = DepResultTy(0, Dirty); 350 } 351 352 ReverseNonLocalDeps.erase(drop); 353 NonLocalDeps.erase(drop); 354} 355 356/// removeInstruction - Remove an instruction from the dependence analysis, 357/// updating the dependence of instructions that previously depended on it. 358/// This method attempts to keep the cache coherent using the reverse map. 359void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) { 360 // Walk through the Non-local dependencies, removing this one as the value 361 // for any cached queries. 362 for (DenseMap<BasicBlock*, DepResultTy>::iterator DI = 363 NonLocalDeps[RemInst].begin(), DE = NonLocalDeps[RemInst].end(); 364 DI != DE; ++DI) 365 if (Instruction *Inst = DI->second.getPointer()) 366 ReverseNonLocalDeps[Inst].erase(RemInst); 367 368 // Shortly after this, we will look for things that depend on RemInst. In 369 // order to update these, we'll need a new dependency to base them on. We 370 // could completely delete any entries that depend on this, but it is better 371 // to make a more accurate approximation where possible. Compute that better 372 // approximation if we can. 373 DepResultTy NewDependency; 374 375 // If we have a cached local dependence query for this instruction, remove it. 376 // 377 LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst); 378 if (LocalDepEntry != LocalDeps.end()) { 379 DepResultTy LocalDep = LocalDepEntry->second; 380 381 // Remove this local dependency info. 382 LocalDeps.erase(LocalDepEntry); 383 384 // Remove us from DepInst's reverse set now that the local dep info is gone. 385 if (Instruction *Inst = LocalDep.getPointer()) 386 ReverseLocalDeps[Inst].erase(RemInst); 387 388 // If we have unconfirmed info, don't trust it. 389 if (LocalDep.getInt() != Dirty) { 390 // If we have a confirmed non-local flag, use it. 391 if (LocalDep.getInt() == NonLocal || LocalDep.getInt() == None) { 392 // The only time this dependency is confirmed is if it is non-local. 393 NewDependency = LocalDep; 394 } else { 395 // If we have dep info for RemInst, set them to it. 396 Instruction *NDI = next(BasicBlock::iterator(LocalDep.getPointer())); 397 if (NDI != RemInst) // Don't use RemInst for the new dependency! 398 NewDependency = DepResultTy(NDI, Dirty); 399 } 400 } 401 } 402 403 // If we don't already have a local dependency answer for this instruction, 404 // use the immediate successor of RemInst. We use the successor because 405 // getDependence starts by checking the immediate predecessor of what is in 406 // the cache. 407 if (NewDependency == DepResultTy(0, Dirty)) 408 NewDependency = DepResultTy(next(BasicBlock::iterator(RemInst)), Dirty); 409 410 // Loop over all of the things that depend on the instruction we're removing. 411 // 412 ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(RemInst); 413 if (ReverseDepIt != ReverseLocalDeps.end()) { 414 SmallPtrSet<Instruction*, 4> &ReverseDeps = ReverseDepIt->second; 415 for (SmallPtrSet<Instruction*, 4>::iterator I = ReverseDeps.begin(), 416 E = ReverseDeps.end(); I != E; ++I) { 417 Instruction *InstDependingOnRemInst = *I; 418 419 // If we thought the instruction depended on itself (possible for 420 // unconfirmed dependencies) ignore the update. 421 if (InstDependingOnRemInst == RemInst) continue; 422 423 // Insert the new dependencies. 424 LocalDeps[InstDependingOnRemInst] = NewDependency; 425 426 // If our NewDependency is an instruction, make sure to remember that new 427 // things depend on it. 428 if (Instruction *Inst = NewDependency.getPointer()) 429 ReverseLocalDeps[Inst].insert(InstDependingOnRemInst); 430 } 431 ReverseLocalDeps.erase(RemInst); 432 } 433 434 ReverseDepIt = ReverseNonLocalDeps.find(RemInst); 435 if (ReverseDepIt != ReverseNonLocalDeps.end()) { 436 SmallPtrSet<Instruction*, 4>& set = ReverseDepIt->second; 437 for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end(); 438 I != E; ++I) 439 for (DenseMap<BasicBlock*, DepResultTy>::iterator 440 DI = NonLocalDeps[*I].begin(), DE = NonLocalDeps[*I].end(); 441 DI != DE; ++DI) 442 if (DI->second == DepResultTy(RemInst, Normal)) 443 // FIXME: Why not remember the old insertion point?? 444 DI->second = DepResultTy(0, Dirty); 445 ReverseNonLocalDeps.erase(ReverseDepIt); 446 } 447 448 NonLocalDeps.erase(RemInst); 449 450 getAnalysis<AliasAnalysis>().deleteValue(RemInst); 451 452 DEBUG(verifyRemoved(RemInst)); 453} 454 455/// verifyRemoved - Verify that the specified instruction does not occur 456/// in our internal data structures. 457void MemoryDependenceAnalysis::verifyRemoved(Instruction *D) const { 458 for (LocalDepMapType::const_iterator I = LocalDeps.begin(), 459 E = LocalDeps.end(); I != E; ++I) { 460 assert(I->first != D && "Inst occurs in data structures"); 461 assert(I->second.getPointer() != D && 462 "Inst occurs in data structures"); 463 } 464 465 for (NonLocalDepMapType::const_iterator I = NonLocalDeps.begin(), 466 E = NonLocalDeps.end(); I != E; ++I) { 467 assert(I->first != D && "Inst occurs in data structures"); 468 for (DenseMap<BasicBlock*, DepResultTy>::iterator II = I->second.begin(), 469 EE = I->second.end(); II != EE; ++II) 470 assert(II->second.getPointer() != D && "Inst occurs in data structures"); 471 } 472 473 for (ReverseDepMapType::const_iterator I = ReverseLocalDeps.begin(), 474 E = ReverseLocalDeps.end(); I != E; ++I) 475 for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(), 476 EE = I->second.end(); II != EE; ++II) 477 assert(*II != D && "Inst occurs in data structures"); 478 479 for (ReverseDepMapType::const_iterator I = ReverseNonLocalDeps.begin(), 480 E = ReverseNonLocalDeps.end(); 481 I != E; ++I) 482 for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(), 483 EE = I->second.end(); II != EE; ++II) 484 assert(*II != D && "Inst occurs in data structures"); 485} 486