MemoryDependenceAnalysis.cpp revision 8e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6
1544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin//===- MemoryDependenceAnalysis.cpp - Mem Deps Implementation --*- C++ -*-===// 2544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin// 3544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin// The LLVM Compiler Infrastructure 4544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin// 5544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin// This file is distributed under the University of Illinois Open Source 6544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin// License. See LICENSE.TXT for details. 7544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin// 8544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin//===----------------------------------------------------------------------===// 9544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin// 10544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin// This file implements an analysis that determines, for a given memory 11544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin// operation, what preceding memory operations it depends on. It builds on 12544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin// alias analysis information, and tries to provide a lazy, caching interface to 13544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin// a common kind of alias information query. 14544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin// 15544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin//===----------------------------------------------------------------------===// 16544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 17544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#define DEBUG_TYPE "memdep" 18544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#include "llvm/Analysis/MemoryDependenceAnalysis.h" 19544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#include "llvm/Instructions.h" 20544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#include "llvm/IntrinsicInst.h" 21544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#include "llvm/Function.h" 22544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#include "llvm/LLVMContext.h" 23544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#include "llvm/Analysis/AliasAnalysis.h" 24544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#include "llvm/Analysis/Dominators.h" 25544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#include "llvm/Analysis/InstructionSimplify.h" 26544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#include "llvm/Analysis/MemoryBuiltins.h" 27544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#include "llvm/Analysis/PHITransAddr.h" 28544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#include "llvm/Analysis/ValueTracking.h" 29544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#include "llvm/ADT/Statistic.h" 30544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#include "llvm/ADT/STLExtras.h" 31544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#include "llvm/Support/PredIteratorCache.h" 32544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#include "llvm/Support/Debug.h" 33287c94ea4987033f9c99a2f91c5750c9083504caKeith Whitwell#include "llvm/Target/TargetData.h" 34544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinusing namespace llvm; 35544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 36544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack RusinSTATISTIC(NumCacheNonLocal, "Number of fully cached non-local responses"); 37544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack RusinSTATISTIC(NumCacheDirtyNonLocal, "Number of dirty cached non-local responses"); 38544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack RusinSTATISTIC(NumUncacheNonLocal, "Number of uncached non-local responses"); 39544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 40544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack RusinSTATISTIC(NumCacheNonLocalPtr, 41544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin "Number of fully cached non-local ptr responses"); 42544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack RusinSTATISTIC(NumCacheDirtyNonLocalPtr, 43544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin "Number of cached, but dirty, non-local ptr responses"); 44544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack RusinSTATISTIC(NumUncacheNonLocalPtr, 45544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin "Number of uncached non-local ptr responses"); 46e5f0384ad06359aa1b9dc1b4bc6f475f7a119af2Roland ScheideggerSTATISTIC(NumCacheCompleteNonLocalPtr, 47544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin "Number of block queries that were completely cached"); 48544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 49544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin// Limit for the number of instructions to scan in a block. 50544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin// FIXME: Figure out what a sane value is for this. 51544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin// (500 is relatively insane.) 52544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinstatic const int BlockScanLimit = 500; 53544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 54544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinchar MemoryDependenceAnalysis::ID = 0; 55544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 56544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin// Register this pass... 57544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack RusinINITIALIZE_PASS_BEGIN(MemoryDependenceAnalysis, "memdep", 58544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin "Memory Dependence Analysis", false, true) 59544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack RusinINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 60544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack RusinINITIALIZE_PASS_END(MemoryDependenceAnalysis, "memdep", 61544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin "Memory Dependence Analysis", false, true) 62544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 63544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack RusinMemoryDependenceAnalysis::MemoryDependenceAnalysis() 64544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin: FunctionPass(ID), PredCache(0) { 65544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin initializeMemoryDependenceAnalysisPass(*PassRegistry::getPassRegistry()); 66544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 67544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack RusinMemoryDependenceAnalysis::~MemoryDependenceAnalysis() { 68544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 69544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 70544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin/// Clean up memory in between runs 71544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinvoid MemoryDependenceAnalysis::releaseMemory() { 72544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin LocalDeps.clear(); 73544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin NonLocalDeps.clear(); 74544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin NonLocalPointerDeps.clear(); 75544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin ReverseLocalDeps.clear(); 76544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin ReverseNonLocalDeps.clear(); 77544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin ReverseNonLocalPtrDeps.clear(); 78544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin PredCache->clear(); 79544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 80544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 81544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 8234f466d4e6a720138c0846ab6233c32dc039fe58Chia-I Wu 83544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin/// getAnalysisUsage - Does not modify anything. It uses Alias Analysis. 84544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin/// 85544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinvoid MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 86544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin AU.setPreservesAll(); 87544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin AU.addRequiredTransitive<AliasAnalysis>(); 88544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 89544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 90544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinbool MemoryDependenceAnalysis::runOnFunction(Function &) { 91544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin AA = &getAnalysis<AliasAnalysis>(); 92e5f0384ad06359aa1b9dc1b4bc6f475f7a119af2Roland Scheidegger TD = getAnalysisIfAvailable<TargetData>(); 93544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin DT = getAnalysisIfAvailable<DominatorTree>(); 94544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (PredCache == 0) 95544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin PredCache.reset(new PredIteratorCache()); 96544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin return false; 97544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 98544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 99544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin/// RemoveFromReverseMap - This is a helper function that removes Val from 100544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin/// 'Inst's set in ReverseMap. If the set becomes empty, remove Inst's entry. 101544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusintemplate <typename KeyTy> 102544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinstatic void RemoveFromReverseMap(DenseMap<Instruction*, 103544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin SmallPtrSet<KeyTy, 4> > &ReverseMap, 104544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin Instruction *Inst, KeyTy Val) { 105 typename DenseMap<Instruction*, SmallPtrSet<KeyTy, 4> >::iterator 106 InstIt = ReverseMap.find(Inst); 107 assert(InstIt != ReverseMap.end() && "Reverse map out of sync?"); 108 bool Found = InstIt->second.erase(Val); 109 assert(Found && "Invalid reverse map!"); (void)Found; 110 if (InstIt->second.empty()) 111 ReverseMap.erase(InstIt); 112} 113 114/// GetLocation - If the given instruction references a specific memory 115/// location, fill in Loc with the details, otherwise set Loc.Ptr to null. 116/// Return a ModRefInfo value describing the general behavior of the 117/// instruction. 118static 119AliasAnalysis::ModRefResult GetLocation(const Instruction *Inst, 120 AliasAnalysis::Location &Loc, 121 AliasAnalysis *AA) { 122 if (const LoadInst *LI = dyn_cast<LoadInst>(Inst)) { 123 if (LI->isUnordered()) { 124 Loc = AA->getLocation(LI); 125 return AliasAnalysis::Ref; 126 } else if (LI->getOrdering() == Monotonic) { 127 Loc = AA->getLocation(LI); 128 return AliasAnalysis::ModRef; 129 } 130 Loc = AliasAnalysis::Location(); 131 return AliasAnalysis::ModRef; 132 } 133 134 if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 135 if (SI->isUnordered()) { 136 Loc = AA->getLocation(SI); 137 return AliasAnalysis::Mod; 138 } else if (SI->getOrdering() == Monotonic) { 139 Loc = AA->getLocation(SI); 140 return AliasAnalysis::ModRef; 141 } 142 Loc = AliasAnalysis::Location(); 143 return AliasAnalysis::ModRef; 144 } 145 146 if (const VAArgInst *V = dyn_cast<VAArgInst>(Inst)) { 147 Loc = AA->getLocation(V); 148 return AliasAnalysis::ModRef; 149 } 150 151 if (const CallInst *CI = isFreeCall(Inst, AA->getTargetLibraryInfo())) { 152 // calls to free() deallocate the entire structure 153 Loc = AliasAnalysis::Location(CI->getArgOperand(0)); 154 return AliasAnalysis::Mod; 155 } 156 157 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) 158 switch (II->getIntrinsicID()) { 159 case Intrinsic::lifetime_start: 160 case Intrinsic::lifetime_end: 161 case Intrinsic::invariant_start: 162 Loc = AliasAnalysis::Location(II->getArgOperand(1), 163 cast<ConstantInt>(II->getArgOperand(0)) 164 ->getZExtValue(), 165 II->getMetadata(LLVMContext::MD_tbaa)); 166 // These intrinsics don't really modify the memory, but returning Mod 167 // will allow them to be handled conservatively. 168 return AliasAnalysis::Mod; 169 case Intrinsic::invariant_end: 170 Loc = AliasAnalysis::Location(II->getArgOperand(2), 171 cast<ConstantInt>(II->getArgOperand(1)) 172 ->getZExtValue(), 173 II->getMetadata(LLVMContext::MD_tbaa)); 174 // These intrinsics don't really modify the memory, but returning Mod 175 // will allow them to be handled conservatively. 176 return AliasAnalysis::Mod; 177 default: 178 break; 179 } 180 181 // Otherwise, just do the coarse-grained thing that always works. 182 if (Inst->mayWriteToMemory()) 183 return AliasAnalysis::ModRef; 184 if (Inst->mayReadFromMemory()) 185 return AliasAnalysis::Ref; 186 return AliasAnalysis::NoModRef; 187} 188 189/// getCallSiteDependencyFrom - Private helper for finding the local 190/// dependencies of a call site. 191MemDepResult MemoryDependenceAnalysis:: 192getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall, 193 BasicBlock::iterator ScanIt, BasicBlock *BB) { 194 unsigned Limit = BlockScanLimit; 195 196 // Walk backwards through the block, looking for dependencies 197 while (ScanIt != BB->begin()) { 198 // Limit the amount of scanning we do so we don't end up with quadratic 199 // running time on extreme testcases. 200 --Limit; 201 if (!Limit) 202 return MemDepResult::getUnknown(); 203 204 Instruction *Inst = --ScanIt; 205 206 // If this inst is a memory op, get the pointer it accessed 207 AliasAnalysis::Location Loc; 208 AliasAnalysis::ModRefResult MR = GetLocation(Inst, Loc, AA); 209 if (Loc.Ptr) { 210 // A simple instruction. 211 if (AA->getModRefInfo(CS, Loc) != AliasAnalysis::NoModRef) 212 return MemDepResult::getClobber(Inst); 213 continue; 214 } 215 216 if (CallSite InstCS = cast<Value>(Inst)) { 217 // Debug intrinsics don't cause dependences. 218 if (isa<DbgInfoIntrinsic>(Inst)) continue; 219 // If these two calls do not interfere, look past it. 220 switch (AA->getModRefInfo(CS, InstCS)) { 221 case AliasAnalysis::NoModRef: 222 // If the two calls are the same, return InstCS as a Def, so that 223 // CS can be found redundant and eliminated. 224 if (isReadOnlyCall && !(MR & AliasAnalysis::Mod) && 225 CS.getInstruction()->isIdenticalToWhenDefined(Inst)) 226 return MemDepResult::getDef(Inst); 227 228 // Otherwise if the two calls don't interact (e.g. InstCS is readnone) 229 // keep scanning. 230 continue; 231 default: 232 return MemDepResult::getClobber(Inst); 233 } 234 } 235 236 // If we could not obtain a pointer for the instruction and the instruction 237 // touches memory then assume that this is a dependency. 238 if (MR != AliasAnalysis::NoModRef) 239 return MemDepResult::getClobber(Inst); 240 } 241 242 // No dependence found. If this is the entry block of the function, it is 243 // unknown, otherwise it is non-local. 244 if (BB != &BB->getParent()->getEntryBlock()) 245 return MemDepResult::getNonLocal(); 246 return MemDepResult::getNonFuncLocal(); 247} 248 249/// isLoadLoadClobberIfExtendedToFullWidth - Return true if LI is a load that 250/// would fully overlap MemLoc if done as a wider legal integer load. 251/// 252/// MemLocBase, MemLocOffset are lazily computed here the first time the 253/// base/offs of memloc is needed. 254static bool 255isLoadLoadClobberIfExtendedToFullWidth(const AliasAnalysis::Location &MemLoc, 256 const Value *&MemLocBase, 257 int64_t &MemLocOffs, 258 const LoadInst *LI, 259 const TargetData *TD) { 260 // If we have no target data, we can't do this. 261 if (TD == 0) return false; 262 263 // If we haven't already computed the base/offset of MemLoc, do so now. 264 if (MemLocBase == 0) 265 MemLocBase = GetPointerBaseWithConstantOffset(MemLoc.Ptr, MemLocOffs, *TD); 266 267 unsigned Size = MemoryDependenceAnalysis:: 268 getLoadLoadClobberFullWidthSize(MemLocBase, MemLocOffs, MemLoc.Size, 269 LI, *TD); 270 return Size != 0; 271} 272 273/// getLoadLoadClobberFullWidthSize - This is a little bit of analysis that 274/// looks at a memory location for a load (specified by MemLocBase, Offs, 275/// and Size) and compares it against a load. If the specified load could 276/// be safely widened to a larger integer load that is 1) still efficient, 277/// 2) safe for the target, and 3) would provide the specified memory 278/// location value, then this function returns the size in bytes of the 279/// load width to use. If not, this returns zero. 280unsigned MemoryDependenceAnalysis:: 281getLoadLoadClobberFullWidthSize(const Value *MemLocBase, int64_t MemLocOffs, 282 unsigned MemLocSize, const LoadInst *LI, 283 const TargetData &TD) { 284 // We can only extend simple integer loads. 285 if (!isa<IntegerType>(LI->getType()) || !LI->isSimple()) return 0; 286 287 // Get the base of this load. 288 int64_t LIOffs = 0; 289 const Value *LIBase = 290 GetPointerBaseWithConstantOffset(LI->getPointerOperand(), LIOffs, TD); 291 292 // If the two pointers are not based on the same pointer, we can't tell that 293 // they are related. 294 if (LIBase != MemLocBase) return 0; 295 296 // Okay, the two values are based on the same pointer, but returned as 297 // no-alias. This happens when we have things like two byte loads at "P+1" 298 // and "P+3". Check to see if increasing the size of the "LI" load up to its 299 // alignment (or the largest native integer type) will allow us to load all 300 // the bits required by MemLoc. 301 302 // If MemLoc is before LI, then no widening of LI will help us out. 303 if (MemLocOffs < LIOffs) return 0; 304 305 // Get the alignment of the load in bytes. We assume that it is safe to load 306 // any legal integer up to this size without a problem. For example, if we're 307 // looking at an i8 load on x86-32 that is known 1024 byte aligned, we can 308 // widen it up to an i32 load. If it is known 2-byte aligned, we can widen it 309 // to i16. 310 unsigned LoadAlign = LI->getAlignment(); 311 312 int64_t MemLocEnd = MemLocOffs+MemLocSize; 313 314 // If no amount of rounding up will let MemLoc fit into LI, then bail out. 315 if (LIOffs+LoadAlign < MemLocEnd) return 0; 316 317 // This is the size of the load to try. Start with the next larger power of 318 // two. 319 unsigned NewLoadByteSize = LI->getType()->getPrimitiveSizeInBits()/8U; 320 NewLoadByteSize = NextPowerOf2(NewLoadByteSize); 321 322 while (1) { 323 // If this load size is bigger than our known alignment or would not fit 324 // into a native integer register, then we fail. 325 if (NewLoadByteSize > LoadAlign || 326 !TD.fitsInLegalInteger(NewLoadByteSize*8)) 327 return 0; 328 329 if (LIOffs+NewLoadByteSize > MemLocEnd && 330 LI->getParent()->getParent()->hasFnAttr(Attribute::AddressSafety)) { 331 // We will be reading past the location accessed by the original program. 332 // While this is safe in a regular build, Address Safety analysis tools 333 // may start reporting false warnings. So, don't do widening. 334 return 0; 335 } 336 337 // If a load of this width would include all of MemLoc, then we succeed. 338 if (LIOffs+NewLoadByteSize >= MemLocEnd) 339 return NewLoadByteSize; 340 341 NewLoadByteSize <<= 1; 342 } 343} 344 345/// getPointerDependencyFrom - Return the instruction on which a memory 346/// location depends. If isLoad is true, this routine ignores may-aliases with 347/// read-only operations. If isLoad is false, this routine ignores may-aliases 348/// with reads from read-only locations. 349MemDepResult MemoryDependenceAnalysis:: 350getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, 351 BasicBlock::iterator ScanIt, BasicBlock *BB) { 352 353 const Value *MemLocBase = 0; 354 int64_t MemLocOffset = 0; 355 356 unsigned Limit = BlockScanLimit; 357 358 // Walk backwards through the basic block, looking for dependencies. 359 while (ScanIt != BB->begin()) { 360 // Limit the amount of scanning we do so we don't end up with quadratic 361 // running time on extreme testcases. 362 --Limit; 363 if (!Limit) 364 return MemDepResult::getUnknown(); 365 366 Instruction *Inst = --ScanIt; 367 368 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) { 369 // Debug intrinsics don't (and can't) cause dependences. 370 if (isa<DbgInfoIntrinsic>(II)) continue; 371 372 // If we reach a lifetime begin or end marker, then the query ends here 373 // because the value is undefined. 374 if (II->getIntrinsicID() == Intrinsic::lifetime_start) { 375 // FIXME: This only considers queries directly on the invariant-tagged 376 // pointer, not on query pointers that are indexed off of them. It'd 377 // be nice to handle that at some point (the right approach is to use 378 // GetPointerBaseWithConstantOffset). 379 if (AA->isMustAlias(AliasAnalysis::Location(II->getArgOperand(1)), 380 MemLoc)) 381 return MemDepResult::getDef(II); 382 continue; 383 } 384 } 385 386 // Values depend on loads if the pointers are must aliased. This means that 387 // a load depends on another must aliased load from the same value. 388 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) { 389 // Atomic loads have complications involved. 390 // FIXME: This is overly conservative. 391 if (!LI->isUnordered()) 392 return MemDepResult::getClobber(LI); 393 394 AliasAnalysis::Location LoadLoc = AA->getLocation(LI); 395 396 // If we found a pointer, check if it could be the same as our pointer. 397 AliasAnalysis::AliasResult R = AA->alias(LoadLoc, MemLoc); 398 399 if (isLoad) { 400 if (R == AliasAnalysis::NoAlias) { 401 // If this is an over-aligned integer load (for example, 402 // "load i8* %P, align 4") see if it would obviously overlap with the 403 // queried location if widened to a larger load (e.g. if the queried 404 // location is 1 byte at P+1). If so, return it as a load/load 405 // clobber result, allowing the client to decide to widen the load if 406 // it wants to. 407 if (IntegerType *ITy = dyn_cast<IntegerType>(LI->getType())) 408 if (LI->getAlignment()*8 > ITy->getPrimitiveSizeInBits() && 409 isLoadLoadClobberIfExtendedToFullWidth(MemLoc, MemLocBase, 410 MemLocOffset, LI, TD)) 411 return MemDepResult::getClobber(Inst); 412 413 continue; 414 } 415 416 // Must aliased loads are defs of each other. 417 if (R == AliasAnalysis::MustAlias) 418 return MemDepResult::getDef(Inst); 419 420#if 0 // FIXME: Temporarily disabled. GVN is cleverly rewriting loads 421 // in terms of clobbering loads, but since it does this by looking 422 // at the clobbering load directly, it doesn't know about any 423 // phi translation that may have happened along the way. 424 425 // If we have a partial alias, then return this as a clobber for the 426 // client to handle. 427 if (R == AliasAnalysis::PartialAlias) 428 return MemDepResult::getClobber(Inst); 429#endif 430 431 // Random may-alias loads don't depend on each other without a 432 // dependence. 433 continue; 434 } 435 436 // Stores don't depend on other no-aliased accesses. 437 if (R == AliasAnalysis::NoAlias) 438 continue; 439 440 // Stores don't alias loads from read-only memory. 441 if (AA->pointsToConstantMemory(LoadLoc)) 442 continue; 443 444 // Stores depend on may/must aliased loads. 445 return MemDepResult::getDef(Inst); 446 } 447 448 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 449 // Atomic stores have complications involved. 450 // FIXME: This is overly conservative. 451 if (!SI->isUnordered()) 452 return MemDepResult::getClobber(SI); 453 454 // If alias analysis can tell that this store is guaranteed to not modify 455 // the query pointer, ignore it. Use getModRefInfo to handle cases where 456 // the query pointer points to constant memory etc. 457 if (AA->getModRefInfo(SI, MemLoc) == AliasAnalysis::NoModRef) 458 continue; 459 460 // Ok, this store might clobber the query pointer. Check to see if it is 461 // a must alias: in this case, we want to return this as a def. 462 AliasAnalysis::Location StoreLoc = AA->getLocation(SI); 463 464 // If we found a pointer, check if it could be the same as our pointer. 465 AliasAnalysis::AliasResult R = AA->alias(StoreLoc, MemLoc); 466 467 if (R == AliasAnalysis::NoAlias) 468 continue; 469 if (R == AliasAnalysis::MustAlias) 470 return MemDepResult::getDef(Inst); 471 return MemDepResult::getClobber(Inst); 472 } 473 474 // If this is an allocation, and if we know that the accessed pointer is to 475 // the allocation, return Def. This means that there is no dependence and 476 // the access can be optimized based on that. For example, a load could 477 // turn into undef. 478 // Note: Only determine this to be a malloc if Inst is the malloc call, not 479 // a subsequent bitcast of the malloc call result. There can be stores to 480 // the malloced memory between the malloc call and its bitcast uses, and we 481 // need to continue scanning until the malloc call. 482 if (isa<AllocaInst>(Inst) || isNoAliasFn(Inst, AA->getTargetLibraryInfo())){ 483 const Value *AccessPtr = GetUnderlyingObject(MemLoc.Ptr, TD); 484 485 if (AccessPtr == Inst || AA->isMustAlias(Inst, AccessPtr)) 486 return MemDepResult::getDef(Inst); 487 continue; 488 } 489 490 // See if this instruction (e.g. a call or vaarg) mod/ref's the pointer. 491 AliasAnalysis::ModRefResult MR = AA->getModRefInfo(Inst, MemLoc); 492 // If necessary, perform additional analysis. 493 if (MR == AliasAnalysis::ModRef) 494 MR = AA->callCapturesBefore(Inst, MemLoc, DT); 495 switch (MR) { 496 case AliasAnalysis::NoModRef: 497 // If the call has no effect on the queried pointer, just ignore it. 498 continue; 499 case AliasAnalysis::Mod: 500 return MemDepResult::getClobber(Inst); 501 case AliasAnalysis::Ref: 502 // If the call is known to never store to the pointer, and if this is a 503 // load query, we can safely ignore it (scan past it). 504 if (isLoad) 505 continue; 506 default: 507 // Otherwise, there is a potential dependence. Return a clobber. 508 return MemDepResult::getClobber(Inst); 509 } 510 } 511 512 // No dependence found. If this is the entry block of the function, it is 513 // unknown, otherwise it is non-local. 514 if (BB != &BB->getParent()->getEntryBlock()) 515 return MemDepResult::getNonLocal(); 516 return MemDepResult::getNonFuncLocal(); 517} 518 519/// getDependency - Return the instruction on which a memory operation 520/// depends. 521MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) { 522 Instruction *ScanPos = QueryInst; 523 524 // Check for a cached result 525 MemDepResult &LocalCache = LocalDeps[QueryInst]; 526 527 // If the cached entry is non-dirty, just return it. Note that this depends 528 // on MemDepResult's default constructing to 'dirty'. 529 if (!LocalCache.isDirty()) 530 return LocalCache; 531 532 // Otherwise, if we have a dirty entry, we know we can start the scan at that 533 // instruction, which may save us some work. 534 if (Instruction *Inst = LocalCache.getInst()) { 535 ScanPos = Inst; 536 537 RemoveFromReverseMap(ReverseLocalDeps, Inst, QueryInst); 538 } 539 540 BasicBlock *QueryParent = QueryInst->getParent(); 541 542 // Do the scan. 543 if (BasicBlock::iterator(QueryInst) == QueryParent->begin()) { 544 // No dependence found. If this is the entry block of the function, it is 545 // unknown, otherwise it is non-local. 546 if (QueryParent != &QueryParent->getParent()->getEntryBlock()) 547 LocalCache = MemDepResult::getNonLocal(); 548 else 549 LocalCache = MemDepResult::getNonFuncLocal(); 550 } else { 551 AliasAnalysis::Location MemLoc; 552 AliasAnalysis::ModRefResult MR = GetLocation(QueryInst, MemLoc, AA); 553 if (MemLoc.Ptr) { 554 // If we can do a pointer scan, make it happen. 555 bool isLoad = !(MR & AliasAnalysis::Mod); 556 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(QueryInst)) 557 isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_start; 558 559 LocalCache = getPointerDependencyFrom(MemLoc, isLoad, ScanPos, 560 QueryParent); 561 } else if (isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst)) { 562 CallSite QueryCS(QueryInst); 563 bool isReadOnly = AA->onlyReadsMemory(QueryCS); 564 LocalCache = getCallSiteDependencyFrom(QueryCS, isReadOnly, ScanPos, 565 QueryParent); 566 } else 567 // Non-memory instruction. 568 LocalCache = MemDepResult::getUnknown(); 569 } 570 571 // Remember the result! 572 if (Instruction *I = LocalCache.getInst()) 573 ReverseLocalDeps[I].insert(QueryInst); 574 575 return LocalCache; 576} 577 578#ifndef NDEBUG 579/// AssertSorted - This method is used when -debug is specified to verify that 580/// cache arrays are properly kept sorted. 581static void AssertSorted(MemoryDependenceAnalysis::NonLocalDepInfo &Cache, 582 int Count = -1) { 583 if (Count == -1) Count = Cache.size(); 584 if (Count == 0) return; 585 586 for (unsigned i = 1; i != unsigned(Count); ++i) 587 assert(!(Cache[i] < Cache[i-1]) && "Cache isn't sorted!"); 588} 589#endif 590 591/// getNonLocalCallDependency - Perform a full dependency query for the 592/// specified call, returning the set of blocks that the value is 593/// potentially live across. The returned set of results will include a 594/// "NonLocal" result for all blocks where the value is live across. 595/// 596/// This method assumes the instruction returns a "NonLocal" dependency 597/// within its own block. 598/// 599/// This returns a reference to an internal data structure that may be 600/// invalidated on the next non-local query or when an instruction is 601/// removed. Clients must copy this data if they want it around longer than 602/// that. 603const MemoryDependenceAnalysis::NonLocalDepInfo & 604MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { 605 assert(getDependency(QueryCS.getInstruction()).isNonLocal() && 606 "getNonLocalCallDependency should only be used on calls with non-local deps!"); 607 PerInstNLInfo &CacheP = NonLocalDeps[QueryCS.getInstruction()]; 608 NonLocalDepInfo &Cache = CacheP.first; 609 610 /// DirtyBlocks - This is the set of blocks that need to be recomputed. In 611 /// the cached case, this can happen due to instructions being deleted etc. In 612 /// the uncached case, this starts out as the set of predecessors we care 613 /// about. 614 SmallVector<BasicBlock*, 32> DirtyBlocks; 615 616 if (!Cache.empty()) { 617 // Okay, we have a cache entry. If we know it is not dirty, just return it 618 // with no computation. 619 if (!CacheP.second) { 620 ++NumCacheNonLocal; 621 return Cache; 622 } 623 624 // If we already have a partially computed set of results, scan them to 625 // determine what is dirty, seeding our initial DirtyBlocks worklist. 626 for (NonLocalDepInfo::iterator I = Cache.begin(), E = Cache.end(); 627 I != E; ++I) 628 if (I->getResult().isDirty()) 629 DirtyBlocks.push_back(I->getBB()); 630 631 // Sort the cache so that we can do fast binary search lookups below. 632 std::sort(Cache.begin(), Cache.end()); 633 634 ++NumCacheDirtyNonLocal; 635 //cerr << "CACHED CASE: " << DirtyBlocks.size() << " dirty: " 636 // << Cache.size() << " cached: " << *QueryInst; 637 } else { 638 // Seed DirtyBlocks with each of the preds of QueryInst's block. 639 BasicBlock *QueryBB = QueryCS.getInstruction()->getParent(); 640 for (BasicBlock **PI = PredCache->GetPreds(QueryBB); *PI; ++PI) 641 DirtyBlocks.push_back(*PI); 642 ++NumUncacheNonLocal; 643 } 644 645 // isReadonlyCall - If this is a read-only call, we can be more aggressive. 646 bool isReadonlyCall = AA->onlyReadsMemory(QueryCS); 647 648 SmallPtrSet<BasicBlock*, 64> Visited; 649 650 unsigned NumSortedEntries = Cache.size(); 651 DEBUG(AssertSorted(Cache)); 652 653 // Iterate while we still have blocks to update. 654 while (!DirtyBlocks.empty()) { 655 BasicBlock *DirtyBB = DirtyBlocks.back(); 656 DirtyBlocks.pop_back(); 657 658 // Already processed this block? 659 if (!Visited.insert(DirtyBB)) 660 continue; 661 662 // Do a binary search to see if we already have an entry for this block in 663 // the cache set. If so, find it. 664 DEBUG(AssertSorted(Cache, NumSortedEntries)); 665 NonLocalDepInfo::iterator Entry = 666 std::upper_bound(Cache.begin(), Cache.begin()+NumSortedEntries, 667 NonLocalDepEntry(DirtyBB)); 668 if (Entry != Cache.begin() && prior(Entry)->getBB() == DirtyBB) 669 --Entry; 670 671 NonLocalDepEntry *ExistingResult = 0; 672 if (Entry != Cache.begin()+NumSortedEntries && 673 Entry->getBB() == DirtyBB) { 674 // If we already have an entry, and if it isn't already dirty, the block 675 // is done. 676 if (!Entry->getResult().isDirty()) 677 continue; 678 679 // Otherwise, remember this slot so we can update the value. 680 ExistingResult = &*Entry; 681 } 682 683 // If the dirty entry has a pointer, start scanning from it so we don't have 684 // to rescan the entire block. 685 BasicBlock::iterator ScanPos = DirtyBB->end(); 686 if (ExistingResult) { 687 if (Instruction *Inst = ExistingResult->getResult().getInst()) { 688 ScanPos = Inst; 689 // We're removing QueryInst's use of Inst. 690 RemoveFromReverseMap(ReverseNonLocalDeps, Inst, 691 QueryCS.getInstruction()); 692 } 693 } 694 695 // Find out if this block has a local dependency for QueryInst. 696 MemDepResult Dep; 697 698 if (ScanPos != DirtyBB->begin()) { 699 Dep = getCallSiteDependencyFrom(QueryCS, isReadonlyCall,ScanPos, DirtyBB); 700 } else if (DirtyBB != &DirtyBB->getParent()->getEntryBlock()) { 701 // No dependence found. If this is the entry block of the function, it is 702 // a clobber, otherwise it is unknown. 703 Dep = MemDepResult::getNonLocal(); 704 } else { 705 Dep = MemDepResult::getNonFuncLocal(); 706 } 707 708 // If we had a dirty entry for the block, update it. Otherwise, just add 709 // a new entry. 710 if (ExistingResult) 711 ExistingResult->setResult(Dep); 712 else 713 Cache.push_back(NonLocalDepEntry(DirtyBB, Dep)); 714 715 // If the block has a dependency (i.e. it isn't completely transparent to 716 // the value), remember the association! 717 if (!Dep.isNonLocal()) { 718 // Keep the ReverseNonLocalDeps map up to date so we can efficiently 719 // update this when we remove instructions. 720 if (Instruction *Inst = Dep.getInst()) 721 ReverseNonLocalDeps[Inst].insert(QueryCS.getInstruction()); 722 } else { 723 724 // If the block *is* completely transparent to the load, we need to check 725 // the predecessors of this block. Add them to our worklist. 726 for (BasicBlock **PI = PredCache->GetPreds(DirtyBB); *PI; ++PI) 727 DirtyBlocks.push_back(*PI); 728 } 729 } 730 731 return Cache; 732} 733 734/// getNonLocalPointerDependency - Perform a full dependency query for an 735/// access to the specified (non-volatile) memory location, returning the 736/// set of instructions that either define or clobber the value. 737/// 738/// This method assumes the pointer has a "NonLocal" dependency within its 739/// own block. 740/// 741void MemoryDependenceAnalysis:: 742getNonLocalPointerDependency(const AliasAnalysis::Location &Loc, bool isLoad, 743 BasicBlock *FromBB, 744 SmallVectorImpl<NonLocalDepResult> &Result) { 745 assert(Loc.Ptr->getType()->isPointerTy() && 746 "Can't get pointer deps of a non-pointer!"); 747 Result.clear(); 748 749 PHITransAddr Address(const_cast<Value *>(Loc.Ptr), TD); 750 751 // This is the set of blocks we've inspected, and the pointer we consider in 752 // each block. Because of critical edges, we currently bail out if querying 753 // a block with multiple different pointers. This can happen during PHI 754 // translation. 755 DenseMap<BasicBlock*, Value*> Visited; 756 if (!getNonLocalPointerDepFromBB(Address, Loc, isLoad, FromBB, 757 Result, Visited, true)) 758 return; 759 Result.clear(); 760 Result.push_back(NonLocalDepResult(FromBB, 761 MemDepResult::getUnknown(), 762 const_cast<Value *>(Loc.Ptr))); 763} 764 765/// GetNonLocalInfoForBlock - Compute the memdep value for BB with 766/// Pointer/PointeeSize using either cached information in Cache or by doing a 767/// lookup (which may use dirty cache info if available). If we do a lookup, 768/// add the result to the cache. 769MemDepResult MemoryDependenceAnalysis:: 770GetNonLocalInfoForBlock(const AliasAnalysis::Location &Loc, 771 bool isLoad, BasicBlock *BB, 772 NonLocalDepInfo *Cache, unsigned NumSortedEntries) { 773 774 // Do a binary search to see if we already have an entry for this block in 775 // the cache set. If so, find it. 776 NonLocalDepInfo::iterator Entry = 777 std::upper_bound(Cache->begin(), Cache->begin()+NumSortedEntries, 778 NonLocalDepEntry(BB)); 779 if (Entry != Cache->begin() && (Entry-1)->getBB() == BB) 780 --Entry; 781 782 NonLocalDepEntry *ExistingResult = 0; 783 if (Entry != Cache->begin()+NumSortedEntries && Entry->getBB() == BB) 784 ExistingResult = &*Entry; 785 786 // If we have a cached entry, and it is non-dirty, use it as the value for 787 // this dependency. 788 if (ExistingResult && !ExistingResult->getResult().isDirty()) { 789 ++NumCacheNonLocalPtr; 790 return ExistingResult->getResult(); 791 } 792 793 // Otherwise, we have to scan for the value. If we have a dirty cache 794 // entry, start scanning from its position, otherwise we scan from the end 795 // of the block. 796 BasicBlock::iterator ScanPos = BB->end(); 797 if (ExistingResult && ExistingResult->getResult().getInst()) { 798 assert(ExistingResult->getResult().getInst()->getParent() == BB && 799 "Instruction invalidated?"); 800 ++NumCacheDirtyNonLocalPtr; 801 ScanPos = ExistingResult->getResult().getInst(); 802 803 // Eliminating the dirty entry from 'Cache', so update the reverse info. 804 ValueIsLoadPair CacheKey(Loc.Ptr, isLoad); 805 RemoveFromReverseMap(ReverseNonLocalPtrDeps, ScanPos, CacheKey); 806 } else { 807 ++NumUncacheNonLocalPtr; 808 } 809 810 // Scan the block for the dependency. 811 MemDepResult Dep = getPointerDependencyFrom(Loc, isLoad, ScanPos, BB); 812 813 // If we had a dirty entry for the block, update it. Otherwise, just add 814 // a new entry. 815 if (ExistingResult) 816 ExistingResult->setResult(Dep); 817 else 818 Cache->push_back(NonLocalDepEntry(BB, Dep)); 819 820 // If the block has a dependency (i.e. it isn't completely transparent to 821 // the value), remember the reverse association because we just added it 822 // to Cache! 823 if (!Dep.isDef() && !Dep.isClobber()) 824 return Dep; 825 826 // Keep the ReverseNonLocalPtrDeps map up to date so we can efficiently 827 // update MemDep when we remove instructions. 828 Instruction *Inst = Dep.getInst(); 829 assert(Inst && "Didn't depend on anything?"); 830 ValueIsLoadPair CacheKey(Loc.Ptr, isLoad); 831 ReverseNonLocalPtrDeps[Inst].insert(CacheKey); 832 return Dep; 833} 834 835/// SortNonLocalDepInfoCache - Sort the a NonLocalDepInfo cache, given a certain 836/// number of elements in the array that are already properly ordered. This is 837/// optimized for the case when only a few entries are added. 838static void 839SortNonLocalDepInfoCache(MemoryDependenceAnalysis::NonLocalDepInfo &Cache, 840 unsigned NumSortedEntries) { 841 switch (Cache.size() - NumSortedEntries) { 842 case 0: 843 // done, no new entries. 844 break; 845 case 2: { 846 // Two new entries, insert the last one into place. 847 NonLocalDepEntry Val = Cache.back(); 848 Cache.pop_back(); 849 MemoryDependenceAnalysis::NonLocalDepInfo::iterator Entry = 850 std::upper_bound(Cache.begin(), Cache.end()-1, Val); 851 Cache.insert(Entry, Val); 852 // FALL THROUGH. 853 } 854 case 1: 855 // One new entry, Just insert the new value at the appropriate position. 856 if (Cache.size() != 1) { 857 NonLocalDepEntry Val = Cache.back(); 858 Cache.pop_back(); 859 MemoryDependenceAnalysis::NonLocalDepInfo::iterator Entry = 860 std::upper_bound(Cache.begin(), Cache.end(), Val); 861 Cache.insert(Entry, Val); 862 } 863 break; 864 default: 865 // Added many values, do a full scale sort. 866 std::sort(Cache.begin(), Cache.end()); 867 break; 868 } 869} 870 871/// getNonLocalPointerDepFromBB - Perform a dependency query based on 872/// pointer/pointeesize starting at the end of StartBB. Add any clobber/def 873/// results to the results vector and keep track of which blocks are visited in 874/// 'Visited'. 875/// 876/// This has special behavior for the first block queries (when SkipFirstBlock 877/// is true). In this special case, it ignores the contents of the specified 878/// block and starts returning dependence info for its predecessors. 879/// 880/// This function returns false on success, or true to indicate that it could 881/// not compute dependence information for some reason. This should be treated 882/// as a clobber dependence on the first instruction in the predecessor block. 883bool MemoryDependenceAnalysis:: 884getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, 885 const AliasAnalysis::Location &Loc, 886 bool isLoad, BasicBlock *StartBB, 887 SmallVectorImpl<NonLocalDepResult> &Result, 888 DenseMap<BasicBlock*, Value*> &Visited, 889 bool SkipFirstBlock) { 890 891 // Look up the cached info for Pointer. 892 ValueIsLoadPair CacheKey(Pointer.getAddr(), isLoad); 893 894 // Set up a temporary NLPI value. If the map doesn't yet have an entry for 895 // CacheKey, this value will be inserted as the associated value. Otherwise, 896 // it'll be ignored, and we'll have to check to see if the cached size and 897 // tbaa tag are consistent with the current query. 898 NonLocalPointerInfo InitialNLPI; 899 InitialNLPI.Size = Loc.Size; 900 InitialNLPI.TBAATag = Loc.TBAATag; 901 902 // Get the NLPI for CacheKey, inserting one into the map if it doesn't 903 // already have one. 904 std::pair<CachedNonLocalPointerInfo::iterator, bool> Pair = 905 NonLocalPointerDeps.insert(std::make_pair(CacheKey, InitialNLPI)); 906 NonLocalPointerInfo *CacheInfo = &Pair.first->second; 907 908 // If we already have a cache entry for this CacheKey, we may need to do some 909 // work to reconcile the cache entry and the current query. 910 if (!Pair.second) { 911 if (CacheInfo->Size < Loc.Size) { 912 // The query's Size is greater than the cached one. Throw out the 913 // cached data and proceed with the query at the greater size. 914 CacheInfo->Pair = BBSkipFirstBlockPair(); 915 CacheInfo->Size = Loc.Size; 916 for (NonLocalDepInfo::iterator DI = CacheInfo->NonLocalDeps.begin(), 917 DE = CacheInfo->NonLocalDeps.end(); DI != DE; ++DI) 918 if (Instruction *Inst = DI->getResult().getInst()) 919 RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey); 920 CacheInfo->NonLocalDeps.clear(); 921 } else if (CacheInfo->Size > Loc.Size) { 922 // This query's Size is less than the cached one. Conservatively restart 923 // the query using the greater size. 924 return getNonLocalPointerDepFromBB(Pointer, 925 Loc.getWithNewSize(CacheInfo->Size), 926 isLoad, StartBB, Result, Visited, 927 SkipFirstBlock); 928 } 929 930 // If the query's TBAATag is inconsistent with the cached one, 931 // conservatively throw out the cached data and restart the query with 932 // no tag if needed. 933 if (CacheInfo->TBAATag != Loc.TBAATag) { 934 if (CacheInfo->TBAATag) { 935 CacheInfo->Pair = BBSkipFirstBlockPair(); 936 CacheInfo->TBAATag = 0; 937 for (NonLocalDepInfo::iterator DI = CacheInfo->NonLocalDeps.begin(), 938 DE = CacheInfo->NonLocalDeps.end(); DI != DE; ++DI) 939 if (Instruction *Inst = DI->getResult().getInst()) 940 RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey); 941 CacheInfo->NonLocalDeps.clear(); 942 } 943 if (Loc.TBAATag) 944 return getNonLocalPointerDepFromBB(Pointer, Loc.getWithoutTBAATag(), 945 isLoad, StartBB, Result, Visited, 946 SkipFirstBlock); 947 } 948 } 949 950 NonLocalDepInfo *Cache = &CacheInfo->NonLocalDeps; 951 952 // If we have valid cached information for exactly the block we are 953 // investigating, just return it with no recomputation. 954 if (CacheInfo->Pair == BBSkipFirstBlockPair(StartBB, SkipFirstBlock)) { 955 // We have a fully cached result for this query then we can just return the 956 // cached results and populate the visited set. However, we have to verify 957 // that we don't already have conflicting results for these blocks. Check 958 // to ensure that if a block in the results set is in the visited set that 959 // it was for the same pointer query. 960 if (!Visited.empty()) { 961 for (NonLocalDepInfo::iterator I = Cache->begin(), E = Cache->end(); 962 I != E; ++I) { 963 DenseMap<BasicBlock*, Value*>::iterator VI = Visited.find(I->getBB()); 964 if (VI == Visited.end() || VI->second == Pointer.getAddr()) 965 continue; 966 967 // We have a pointer mismatch in a block. Just return clobber, saying 968 // that something was clobbered in this result. We could also do a 969 // non-fully cached query, but there is little point in doing this. 970 return true; 971 } 972 } 973 974 Value *Addr = Pointer.getAddr(); 975 for (NonLocalDepInfo::iterator I = Cache->begin(), E = Cache->end(); 976 I != E; ++I) { 977 Visited.insert(std::make_pair(I->getBB(), Addr)); 978 if (!I->getResult().isNonLocal()) 979 Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(), Addr)); 980 } 981 ++NumCacheCompleteNonLocalPtr; 982 return false; 983 } 984 985 // Otherwise, either this is a new block, a block with an invalid cache 986 // pointer or one that we're about to invalidate by putting more info into it 987 // than its valid cache info. If empty, the result will be valid cache info, 988 // otherwise it isn't. 989 if (Cache->empty()) 990 CacheInfo->Pair = BBSkipFirstBlockPair(StartBB, SkipFirstBlock); 991 else 992 CacheInfo->Pair = BBSkipFirstBlockPair(); 993 994 SmallVector<BasicBlock*, 32> Worklist; 995 Worklist.push_back(StartBB); 996 997 // PredList used inside loop. 998 SmallVector<std::pair<BasicBlock*, PHITransAddr>, 16> PredList; 999 1000 // Keep track of the entries that we know are sorted. Previously cached 1001 // entries will all be sorted. The entries we add we only sort on demand (we 1002 // don't insert every element into its sorted position). We know that we 1003 // won't get any reuse from currently inserted values, because we don't 1004 // revisit blocks after we insert info for them. 1005 unsigned NumSortedEntries = Cache->size(); 1006 DEBUG(AssertSorted(*Cache)); 1007 1008 while (!Worklist.empty()) { 1009 BasicBlock *BB = Worklist.pop_back_val(); 1010 1011 // Skip the first block if we have it. 1012 if (!SkipFirstBlock) { 1013 // Analyze the dependency of *Pointer in FromBB. See if we already have 1014 // been here. 1015 assert(Visited.count(BB) && "Should check 'visited' before adding to WL"); 1016 1017 // Get the dependency info for Pointer in BB. If we have cached 1018 // information, we will use it, otherwise we compute it. 1019 DEBUG(AssertSorted(*Cache, NumSortedEntries)); 1020 MemDepResult Dep = GetNonLocalInfoForBlock(Loc, isLoad, BB, Cache, 1021 NumSortedEntries); 1022 1023 // If we got a Def or Clobber, add this to the list of results. 1024 if (!Dep.isNonLocal()) { 1025 Result.push_back(NonLocalDepResult(BB, Dep, Pointer.getAddr())); 1026 continue; 1027 } 1028 } 1029 1030 // If 'Pointer' is an instruction defined in this block, then we need to do 1031 // phi translation to change it into a value live in the predecessor block. 1032 // If not, we just add the predecessors to the worklist and scan them with 1033 // the same Pointer. 1034 if (!Pointer.NeedsPHITranslationFromBlock(BB)) { 1035 SkipFirstBlock = false; 1036 SmallVector<BasicBlock*, 16> NewBlocks; 1037 for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) { 1038 // Verify that we haven't looked at this block yet. 1039 std::pair<DenseMap<BasicBlock*,Value*>::iterator, bool> 1040 InsertRes = Visited.insert(std::make_pair(*PI, Pointer.getAddr())); 1041 if (InsertRes.second) { 1042 // First time we've looked at *PI. 1043 NewBlocks.push_back(*PI); 1044 continue; 1045 } 1046 1047 // If we have seen this block before, but it was with a different 1048 // pointer then we have a phi translation failure and we have to treat 1049 // this as a clobber. 1050 if (InsertRes.first->second != Pointer.getAddr()) { 1051 // Make sure to clean up the Visited map before continuing on to 1052 // PredTranslationFailure. 1053 for (unsigned i = 0; i < NewBlocks.size(); i++) 1054 Visited.erase(NewBlocks[i]); 1055 goto PredTranslationFailure; 1056 } 1057 } 1058 Worklist.append(NewBlocks.begin(), NewBlocks.end()); 1059 continue; 1060 } 1061 1062 // We do need to do phi translation, if we know ahead of time we can't phi 1063 // translate this value, don't even try. 1064 if (!Pointer.IsPotentiallyPHITranslatable()) 1065 goto PredTranslationFailure; 1066 1067 // We may have added values to the cache list before this PHI translation. 1068 // If so, we haven't done anything to ensure that the cache remains sorted. 1069 // Sort it now (if needed) so that recursive invocations of 1070 // getNonLocalPointerDepFromBB and other routines that could reuse the cache 1071 // value will only see properly sorted cache arrays. 1072 if (Cache && NumSortedEntries != Cache->size()) { 1073 SortNonLocalDepInfoCache(*Cache, NumSortedEntries); 1074 NumSortedEntries = Cache->size(); 1075 } 1076 Cache = 0; 1077 1078 PredList.clear(); 1079 for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) { 1080 BasicBlock *Pred = *PI; 1081 PredList.push_back(std::make_pair(Pred, Pointer)); 1082 1083 // Get the PHI translated pointer in this predecessor. This can fail if 1084 // not translatable, in which case the getAddr() returns null. 1085 PHITransAddr &PredPointer = PredList.back().second; 1086 PredPointer.PHITranslateValue(BB, Pred, 0); 1087 1088 Value *PredPtrVal = PredPointer.getAddr(); 1089 1090 // Check to see if we have already visited this pred block with another 1091 // pointer. If so, we can't do this lookup. This failure can occur 1092 // with PHI translation when a critical edge exists and the PHI node in 1093 // the successor translates to a pointer value different than the 1094 // pointer the block was first analyzed with. 1095 std::pair<DenseMap<BasicBlock*,Value*>::iterator, bool> 1096 InsertRes = Visited.insert(std::make_pair(Pred, PredPtrVal)); 1097 1098 if (!InsertRes.second) { 1099 // We found the pred; take it off the list of preds to visit. 1100 PredList.pop_back(); 1101 1102 // If the predecessor was visited with PredPtr, then we already did 1103 // the analysis and can ignore it. 1104 if (InsertRes.first->second == PredPtrVal) 1105 continue; 1106 1107 // Otherwise, the block was previously analyzed with a different 1108 // pointer. We can't represent the result of this case, so we just 1109 // treat this as a phi translation failure. 1110 1111 // Make sure to clean up the Visited map before continuing on to 1112 // PredTranslationFailure. 1113 for (unsigned i = 0; i < PredList.size(); i++) 1114 Visited.erase(PredList[i].first); 1115 1116 goto PredTranslationFailure; 1117 } 1118 } 1119 1120 // Actually process results here; this need to be a separate loop to avoid 1121 // calling getNonLocalPointerDepFromBB for blocks we don't want to return 1122 // any results for. (getNonLocalPointerDepFromBB will modify our 1123 // datastructures in ways the code after the PredTranslationFailure label 1124 // doesn't expect.) 1125 for (unsigned i = 0; i < PredList.size(); i++) { 1126 BasicBlock *Pred = PredList[i].first; 1127 PHITransAddr &PredPointer = PredList[i].second; 1128 Value *PredPtrVal = PredPointer.getAddr(); 1129 1130 bool CanTranslate = true; 1131 // If PHI translation was unable to find an available pointer in this 1132 // predecessor, then we have to assume that the pointer is clobbered in 1133 // that predecessor. We can still do PRE of the load, which would insert 1134 // a computation of the pointer in this predecessor. 1135 if (PredPtrVal == 0) 1136 CanTranslate = false; 1137 1138 // FIXME: it is entirely possible that PHI translating will end up with 1139 // the same value. Consider PHI translating something like: 1140 // X = phi [x, bb1], [y, bb2]. PHI translating for bb1 doesn't *need* 1141 // to recurse here, pedantically speaking. 1142 1143 // If getNonLocalPointerDepFromBB fails here, that means the cached 1144 // result conflicted with the Visited list; we have to conservatively 1145 // assume it is unknown, but this also does not block PRE of the load. 1146 if (!CanTranslate || 1147 getNonLocalPointerDepFromBB(PredPointer, 1148 Loc.getWithNewPtr(PredPtrVal), 1149 isLoad, Pred, 1150 Result, Visited)) { 1151 // Add the entry to the Result list. 1152 NonLocalDepResult Entry(Pred, MemDepResult::getUnknown(), PredPtrVal); 1153 Result.push_back(Entry); 1154 1155 // Since we had a phi translation failure, the cache for CacheKey won't 1156 // include all of the entries that we need to immediately satisfy future 1157 // queries. Mark this in NonLocalPointerDeps by setting the 1158 // BBSkipFirstBlockPair pointer to null. This requires reuse of the 1159 // cached value to do more work but not miss the phi trans failure. 1160 NonLocalPointerInfo &NLPI = NonLocalPointerDeps[CacheKey]; 1161 NLPI.Pair = BBSkipFirstBlockPair(); 1162 continue; 1163 } 1164 } 1165 1166 // Refresh the CacheInfo/Cache pointer so that it isn't invalidated. 1167 CacheInfo = &NonLocalPointerDeps[CacheKey]; 1168 Cache = &CacheInfo->NonLocalDeps; 1169 NumSortedEntries = Cache->size(); 1170 1171 // Since we did phi translation, the "Cache" set won't contain all of the 1172 // results for the query. This is ok (we can still use it to accelerate 1173 // specific block queries) but we can't do the fastpath "return all 1174 // results from the set" Clear out the indicator for this. 1175 CacheInfo->Pair = BBSkipFirstBlockPair(); 1176 SkipFirstBlock = false; 1177 continue; 1178 1179 PredTranslationFailure: 1180 // The following code is "failure"; we can't produce a sane translation 1181 // for the given block. It assumes that we haven't modified any of 1182 // our datastructures while processing the current block. 1183 1184 if (Cache == 0) { 1185 // Refresh the CacheInfo/Cache pointer if it got invalidated. 1186 CacheInfo = &NonLocalPointerDeps[CacheKey]; 1187 Cache = &CacheInfo->NonLocalDeps; 1188 NumSortedEntries = Cache->size(); 1189 } 1190 1191 // Since we failed phi translation, the "Cache" set won't contain all of the 1192 // results for the query. This is ok (we can still use it to accelerate 1193 // specific block queries) but we can't do the fastpath "return all 1194 // results from the set". Clear out the indicator for this. 1195 CacheInfo->Pair = BBSkipFirstBlockPair(); 1196 1197 // If *nothing* works, mark the pointer as unknown. 1198 // 1199 // If this is the magic first block, return this as a clobber of the whole 1200 // incoming value. Since we can't phi translate to one of the predecessors, 1201 // we have to bail out. 1202 if (SkipFirstBlock) 1203 return true; 1204 1205 for (NonLocalDepInfo::reverse_iterator I = Cache->rbegin(); ; ++I) { 1206 assert(I != Cache->rend() && "Didn't find current block??"); 1207 if (I->getBB() != BB) 1208 continue; 1209 1210 assert(I->getResult().isNonLocal() && 1211 "Should only be here with transparent block"); 1212 I->setResult(MemDepResult::getUnknown()); 1213 Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(), 1214 Pointer.getAddr())); 1215 break; 1216 } 1217 } 1218 1219 // Okay, we're done now. If we added new values to the cache, re-sort it. 1220 SortNonLocalDepInfoCache(*Cache, NumSortedEntries); 1221 DEBUG(AssertSorted(*Cache)); 1222 return false; 1223} 1224 1225/// RemoveCachedNonLocalPointerDependencies - If P exists in 1226/// CachedNonLocalPointerInfo, remove it. 1227void MemoryDependenceAnalysis:: 1228RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P) { 1229 CachedNonLocalPointerInfo::iterator It = 1230 NonLocalPointerDeps.find(P); 1231 if (It == NonLocalPointerDeps.end()) return; 1232 1233 // Remove all of the entries in the BB->val map. This involves removing 1234 // instructions from the reverse map. 1235 NonLocalDepInfo &PInfo = It->second.NonLocalDeps; 1236 1237 for (unsigned i = 0, e = PInfo.size(); i != e; ++i) { 1238 Instruction *Target = PInfo[i].getResult().getInst(); 1239 if (Target == 0) continue; // Ignore non-local dep results. 1240 assert(Target->getParent() == PInfo[i].getBB()); 1241 1242 // Eliminating the dirty entry from 'Cache', so update the reverse info. 1243 RemoveFromReverseMap(ReverseNonLocalPtrDeps, Target, P); 1244 } 1245 1246 // Remove P from NonLocalPointerDeps (which deletes NonLocalDepInfo). 1247 NonLocalPointerDeps.erase(It); 1248} 1249 1250 1251/// invalidateCachedPointerInfo - This method is used to invalidate cached 1252/// information about the specified pointer, because it may be too 1253/// conservative in memdep. This is an optional call that can be used when 1254/// the client detects an equivalence between the pointer and some other 1255/// value and replaces the other value with ptr. This can make Ptr available 1256/// in more places that cached info does not necessarily keep. 1257void MemoryDependenceAnalysis::invalidateCachedPointerInfo(Value *Ptr) { 1258 // If Ptr isn't really a pointer, just ignore it. 1259 if (!Ptr->getType()->isPointerTy()) return; 1260 // Flush store info for the pointer. 1261 RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, false)); 1262 // Flush load info for the pointer. 1263 RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, true)); 1264} 1265 1266/// invalidateCachedPredecessors - Clear the PredIteratorCache info. 1267/// This needs to be done when the CFG changes, e.g., due to splitting 1268/// critical edges. 1269void MemoryDependenceAnalysis::invalidateCachedPredecessors() { 1270 PredCache->clear(); 1271} 1272 1273/// removeInstruction - Remove an instruction from the dependence analysis, 1274/// updating the dependence of instructions that previously depended on it. 1275/// This method attempts to keep the cache coherent using the reverse map. 1276void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) { 1277 // Walk through the Non-local dependencies, removing this one as the value 1278 // for any cached queries. 1279 NonLocalDepMapType::iterator NLDI = NonLocalDeps.find(RemInst); 1280 if (NLDI != NonLocalDeps.end()) { 1281 NonLocalDepInfo &BlockMap = NLDI->second.first; 1282 for (NonLocalDepInfo::iterator DI = BlockMap.begin(), DE = BlockMap.end(); 1283 DI != DE; ++DI) 1284 if (Instruction *Inst = DI->getResult().getInst()) 1285 RemoveFromReverseMap(ReverseNonLocalDeps, Inst, RemInst); 1286 NonLocalDeps.erase(NLDI); 1287 } 1288 1289 // If we have a cached local dependence query for this instruction, remove it. 1290 // 1291 LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst); 1292 if (LocalDepEntry != LocalDeps.end()) { 1293 // Remove us from DepInst's reverse set now that the local dep info is gone. 1294 if (Instruction *Inst = LocalDepEntry->second.getInst()) 1295 RemoveFromReverseMap(ReverseLocalDeps, Inst, RemInst); 1296 1297 // Remove this local dependency info. 1298 LocalDeps.erase(LocalDepEntry); 1299 } 1300 1301 // If we have any cached pointer dependencies on this instruction, remove 1302 // them. If the instruction has non-pointer type, then it can't be a pointer 1303 // base. 1304 1305 // Remove it from both the load info and the store info. The instruction 1306 // can't be in either of these maps if it is non-pointer. 1307 if (RemInst->getType()->isPointerTy()) { 1308 RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, false)); 1309 RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, true)); 1310 } 1311 1312 // Loop over all of the things that depend on the instruction we're removing. 1313 // 1314 SmallVector<std::pair<Instruction*, Instruction*>, 8> ReverseDepsToAdd; 1315 1316 // If we find RemInst as a clobber or Def in any of the maps for other values, 1317 // we need to replace its entry with a dirty version of the instruction after 1318 // it. If RemInst is a terminator, we use a null dirty value. 1319 // 1320 // Using a dirty version of the instruction after RemInst saves having to scan 1321 // the entire block to get to this point. 1322 MemDepResult NewDirtyVal; 1323 if (!RemInst->isTerminator()) 1324 NewDirtyVal = MemDepResult::getDirty(++BasicBlock::iterator(RemInst)); 1325 1326 ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(RemInst); 1327 if (ReverseDepIt != ReverseLocalDeps.end()) { 1328 SmallPtrSet<Instruction*, 4> &ReverseDeps = ReverseDepIt->second; 1329 // RemInst can't be the terminator if it has local stuff depending on it. 1330 assert(!ReverseDeps.empty() && !isa<TerminatorInst>(RemInst) && 1331 "Nothing can locally depend on a terminator"); 1332 1333 for (SmallPtrSet<Instruction*, 4>::iterator I = ReverseDeps.begin(), 1334 E = ReverseDeps.end(); I != E; ++I) { 1335 Instruction *InstDependingOnRemInst = *I; 1336 assert(InstDependingOnRemInst != RemInst && 1337 "Already removed our local dep info"); 1338 1339 LocalDeps[InstDependingOnRemInst] = NewDirtyVal; 1340 1341 // Make sure to remember that new things depend on NewDepInst. 1342 assert(NewDirtyVal.getInst() && "There is no way something else can have " 1343 "a local dep on this if it is a terminator!"); 1344 ReverseDepsToAdd.push_back(std::make_pair(NewDirtyVal.getInst(), 1345 InstDependingOnRemInst)); 1346 } 1347 1348 ReverseLocalDeps.erase(ReverseDepIt); 1349 1350 // Add new reverse deps after scanning the set, to avoid invalidating the 1351 // 'ReverseDeps' reference. 1352 while (!ReverseDepsToAdd.empty()) { 1353 ReverseLocalDeps[ReverseDepsToAdd.back().first] 1354 .insert(ReverseDepsToAdd.back().second); 1355 ReverseDepsToAdd.pop_back(); 1356 } 1357 } 1358 1359 ReverseDepIt = ReverseNonLocalDeps.find(RemInst); 1360 if (ReverseDepIt != ReverseNonLocalDeps.end()) { 1361 SmallPtrSet<Instruction*, 4> &Set = ReverseDepIt->second; 1362 for (SmallPtrSet<Instruction*, 4>::iterator I = Set.begin(), E = Set.end(); 1363 I != E; ++I) { 1364 assert(*I != RemInst && "Already removed NonLocalDep info for RemInst"); 1365 1366 PerInstNLInfo &INLD = NonLocalDeps[*I]; 1367 // The information is now dirty! 1368 INLD.second = true; 1369 1370 for (NonLocalDepInfo::iterator DI = INLD.first.begin(), 1371 DE = INLD.first.end(); DI != DE; ++DI) { 1372 if (DI->getResult().getInst() != RemInst) continue; 1373 1374 // Convert to a dirty entry for the subsequent instruction. 1375 DI->setResult(NewDirtyVal); 1376 1377 if (Instruction *NextI = NewDirtyVal.getInst()) 1378 ReverseDepsToAdd.push_back(std::make_pair(NextI, *I)); 1379 } 1380 } 1381 1382 ReverseNonLocalDeps.erase(ReverseDepIt); 1383 1384 // Add new reverse deps after scanning the set, to avoid invalidating 'Set' 1385 while (!ReverseDepsToAdd.empty()) { 1386 ReverseNonLocalDeps[ReverseDepsToAdd.back().first] 1387 .insert(ReverseDepsToAdd.back().second); 1388 ReverseDepsToAdd.pop_back(); 1389 } 1390 } 1391 1392 // If the instruction is in ReverseNonLocalPtrDeps then it appears as a 1393 // value in the NonLocalPointerDeps info. 1394 ReverseNonLocalPtrDepTy::iterator ReversePtrDepIt = 1395 ReverseNonLocalPtrDeps.find(RemInst); 1396 if (ReversePtrDepIt != ReverseNonLocalPtrDeps.end()) { 1397 SmallPtrSet<ValueIsLoadPair, 4> &Set = ReversePtrDepIt->second; 1398 SmallVector<std::pair<Instruction*, ValueIsLoadPair>,8> ReversePtrDepsToAdd; 1399 1400 for (SmallPtrSet<ValueIsLoadPair, 4>::iterator I = Set.begin(), 1401 E = Set.end(); I != E; ++I) { 1402 ValueIsLoadPair P = *I; 1403 assert(P.getPointer() != RemInst && 1404 "Already removed NonLocalPointerDeps info for RemInst"); 1405 1406 NonLocalDepInfo &NLPDI = NonLocalPointerDeps[P].NonLocalDeps; 1407 1408 // The cache is not valid for any specific block anymore. 1409 NonLocalPointerDeps[P].Pair = BBSkipFirstBlockPair(); 1410 1411 // Update any entries for RemInst to use the instruction after it. 1412 for (NonLocalDepInfo::iterator DI = NLPDI.begin(), DE = NLPDI.end(); 1413 DI != DE; ++DI) { 1414 if (DI->getResult().getInst() != RemInst) continue; 1415 1416 // Convert to a dirty entry for the subsequent instruction. 1417 DI->setResult(NewDirtyVal); 1418 1419 if (Instruction *NewDirtyInst = NewDirtyVal.getInst()) 1420 ReversePtrDepsToAdd.push_back(std::make_pair(NewDirtyInst, P)); 1421 } 1422 1423 // Re-sort the NonLocalDepInfo. Changing the dirty entry to its 1424 // subsequent value may invalidate the sortedness. 1425 std::sort(NLPDI.begin(), NLPDI.end()); 1426 } 1427 1428 ReverseNonLocalPtrDeps.erase(ReversePtrDepIt); 1429 1430 while (!ReversePtrDepsToAdd.empty()) { 1431 ReverseNonLocalPtrDeps[ReversePtrDepsToAdd.back().first] 1432 .insert(ReversePtrDepsToAdd.back().second); 1433 ReversePtrDepsToAdd.pop_back(); 1434 } 1435 } 1436 1437 1438 assert(!NonLocalDeps.count(RemInst) && "RemInst got reinserted?"); 1439 AA->deleteValue(RemInst); 1440 DEBUG(verifyRemoved(RemInst)); 1441} 1442/// verifyRemoved - Verify that the specified instruction does not occur 1443/// in our internal data structures. 1444void MemoryDependenceAnalysis::verifyRemoved(Instruction *D) const { 1445 for (LocalDepMapType::const_iterator I = LocalDeps.begin(), 1446 E = LocalDeps.end(); I != E; ++I) { 1447 assert(I->first != D && "Inst occurs in data structures"); 1448 assert(I->second.getInst() != D && 1449 "Inst occurs in data structures"); 1450 } 1451 1452 for (CachedNonLocalPointerInfo::const_iterator I =NonLocalPointerDeps.begin(), 1453 E = NonLocalPointerDeps.end(); I != E; ++I) { 1454 assert(I->first.getPointer() != D && "Inst occurs in NLPD map key"); 1455 const NonLocalDepInfo &Val = I->second.NonLocalDeps; 1456 for (NonLocalDepInfo::const_iterator II = Val.begin(), E = Val.end(); 1457 II != E; ++II) 1458 assert(II->getResult().getInst() != D && "Inst occurs as NLPD value"); 1459 } 1460 1461 for (NonLocalDepMapType::const_iterator I = NonLocalDeps.begin(), 1462 E = NonLocalDeps.end(); I != E; ++I) { 1463 assert(I->first != D && "Inst occurs in data structures"); 1464 const PerInstNLInfo &INLD = I->second; 1465 for (NonLocalDepInfo::const_iterator II = INLD.first.begin(), 1466 EE = INLD.first.end(); II != EE; ++II) 1467 assert(II->getResult().getInst() != D && "Inst occurs in data structures"); 1468 } 1469 1470 for (ReverseDepMapType::const_iterator I = ReverseLocalDeps.begin(), 1471 E = ReverseLocalDeps.end(); I != E; ++I) { 1472 assert(I->first != D && "Inst occurs in data structures"); 1473 for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(), 1474 EE = I->second.end(); II != EE; ++II) 1475 assert(*II != D && "Inst occurs in data structures"); 1476 } 1477 1478 for (ReverseDepMapType::const_iterator I = ReverseNonLocalDeps.begin(), 1479 E = ReverseNonLocalDeps.end(); 1480 I != E; ++I) { 1481 assert(I->first != D && "Inst occurs in data structures"); 1482 for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(), 1483 EE = I->second.end(); II != EE; ++II) 1484 assert(*II != D && "Inst occurs in data structures"); 1485 } 1486 1487 for (ReverseNonLocalPtrDepTy::const_iterator 1488 I = ReverseNonLocalPtrDeps.begin(), 1489 E = ReverseNonLocalPtrDeps.end(); I != E; ++I) { 1490 assert(I->first != D && "Inst occurs in rev NLPD map"); 1491 1492 for (SmallPtrSet<ValueIsLoadPair, 4>::const_iterator II = I->second.begin(), 1493 E = I->second.end(); II != E; ++II) 1494 assert(*II != ValueIsLoadPair(D, false) && 1495 *II != ValueIsLoadPair(D, true) && 1496 "Inst occurs in ReverseNonLocalPtrDeps map"); 1497 } 1498 1499} 1500