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