1192886Sedwin//===- MemoryDependenceAnalysis.cpp - Mem Deps Implementation -------------===// 2192886Sedwin// 367578Swollman// The LLVM Compiler Infrastructure 4273718Sedwin// 52742Swollman// This file is distributed under the University of Illinois Open Source 6273718Sedwin// License. See LICENSE.TXT for details. 7273718Sedwin// 82742Swollman//===----------------------------------------------------------------------===// 9325324Sgordon// 102742Swollman// This file implements an analysis that determines, for a given memory 11274559Sedwin// operation, what preceding memory operations it depends on. It builds on 12158421Swollman// alias analysis information, and tries to provide a lazy, caching interface to 13158421Swollman// a common kind of alias information query. 14274559Sedwin// 152742Swollman//===----------------------------------------------------------------------===// 16325324Sgordon 17325324Sgordon#define DEBUG_TYPE "memdep" 1820094Swollman#include "llvm/Analysis/MemoryDependenceAnalysis.h" 1920094Swollman#include "llvm/ADT/STLExtras.h" 20274559Sedwin#include "llvm/ADT/Statistic.h" 21274559Sedwin#include "llvm/Analysis/AliasAnalysis.h" 2220094Swollman#include "llvm/Analysis/Dominators.h" 232742Swollman#include "llvm/Analysis/InstructionSimplify.h" 242742Swollman#include "llvm/Analysis/MemoryBuiltins.h" 252742Swollman#include "llvm/Analysis/PHITransAddr.h" 262742Swollman#include "llvm/Analysis/ValueTracking.h" 27248307Sedwin#include "llvm/IR/DataLayout.h" 28273718Sedwin#include "llvm/IR/Function.h" 29325324Sgordon#include "llvm/IR/Instructions.h" 30248307Sedwin#include "llvm/IR/IntrinsicInst.h" 3114343Swollman#include "llvm/IR/LLVMContext.h" 3258787Sru#include "llvm/Support/Debug.h" 3314343Swollman#include "llvm/Support/PredIteratorCache.h" 34325324Sgordonusing namespace llvm; 35325324Sgordon 3630711SwollmanSTATISTIC(NumCacheNonLocal, "Number of fully cached non-local responses"); 37325324SgordonSTATISTIC(NumCacheDirtyNonLocal, "Number of dirty cached non-local responses"); 38325324SgordonSTATISTIC(NumUncacheNonLocal, "Number of uncached non-local responses"); 39325324Sgordon 40325324SgordonSTATISTIC(NumCacheNonLocalPtr, 41325324Sgordon "Number of fully cached non-local ptr responses"); 42270728SpluknetSTATISTIC(NumCacheDirtyNonLocalPtr, 432742Swollman "Number of cached, but dirty, non-local ptr responses"); 44325324SgordonSTATISTIC(NumUncacheNonLocalPtr, 45325324Sgordon "Number of uncached non-local ptr responses"); 46325324SgordonSTATISTIC(NumCacheCompleteNonLocalPtr, 47325324Sgordon "Number of block queries that were completely cached"); 48325324Sgordon 49325324Sgordon// Limit for the number of instructions to scan in a block. 50325324Sgordonstatic const int BlockScanLimit = 100; 51325324Sgordon 52325324Sgordonchar MemoryDependenceAnalysis::ID = 0; 532742Swollman 5430711Swollman// Register this pass... 55325324SgordonINITIALIZE_PASS_BEGIN(MemoryDependenceAnalysis, "memdep", 56325324Sgordon "Memory Dependence Analysis", false, true) 57325324SgordonINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 58325324SgordonINITIALIZE_PASS_END(MemoryDependenceAnalysis, "memdep", 59325324Sgordon "Memory Dependence Analysis", false, true) 60325324Sgordon 612742SwollmanMemoryDependenceAnalysis::MemoryDependenceAnalysis() 622742Swollman: FunctionPass(ID), PredCache(0) { 632742Swollman initializeMemoryDependenceAnalysisPass(*PassRegistry::getPassRegistry()); 6419878Swollman} 65158421SwollmanMemoryDependenceAnalysis::~MemoryDependenceAnalysis() { 6619878Swollman} 6719878Swollman 6819878Swollman/// Clean up memory in between runs 6919878Swollmanvoid MemoryDependenceAnalysis::releaseMemory() { 702742Swollman LocalDeps.clear(); 7119878Swollman NonLocalDeps.clear(); 722742Swollman NonLocalPointerDeps.clear(); 7319878Swollman ReverseLocalDeps.clear(); 742742Swollman ReverseNonLocalDeps.clear(); 75158421Swollman ReverseNonLocalPtrDeps.clear(); 762742Swollman PredCache->clear(); 772742Swollman} 7819878Swollman 792742Swollman 8019878Swollman 812742Swollman/// getAnalysisUsage - Does not modify anything. It uses Alias Analysis. 8219878Swollman/// 832742Swollmanvoid MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 8419878Swollman AU.setPreservesAll(); 852742Swollman AU.addRequiredTransitive<AliasAnalysis>(); 86158421Swollman} 87158421Swollman 882742Swollmanbool MemoryDependenceAnalysis::runOnFunction(Function &) { 89273718Sedwin AA = &getAnalysis<AliasAnalysis>(); 90273718Sedwin TD = getAnalysisIfAvailable<DataLayout>(); 91273718Sedwin DT = getAnalysisIfAvailable<DominatorTree>(); 9219878Swollman if (!PredCache) 932742Swollman PredCache.reset(new PredIteratorCache()); 9419878Swollman return false; 9519878Swollman} 9619878Swollman 9719878Swollman/// RemoveFromReverseMap - This is a helper function that removes Val from 9819878Swollman/// 'Inst's set in ReverseMap. If the set becomes empty, remove Inst's entry. 992742Swollmantemplate <typename KeyTy> 1002742Swollmanstatic void RemoveFromReverseMap(DenseMap<Instruction*, 1012742Swollman SmallPtrSet<KeyTy, 4> > &ReverseMap, 102273718Sedwin Instruction *Inst, KeyTy Val) { 1032742Swollman typename DenseMap<Instruction*, SmallPtrSet<KeyTy, 4> >::iterator 1042742Swollman InstIt = ReverseMap.find(Inst); 105273718Sedwin assert(InstIt != ReverseMap.end() && "Reverse map out of sync?"); 1062742Swollman bool Found = InstIt->second.erase(Val); 1072742Swollman assert(Found && "Invalid reverse map!"); (void)Found; 108270728Spluknet if (InstIt->second.empty()) 1092742Swollman ReverseMap.erase(InstIt); 1102742Swollman} 111273718Sedwin 1122742Swollman/// GetLocation - If the given instruction references a specific memory 1132742Swollman/// location, fill in Loc with the details, otherwise set Loc.Ptr to null. 114273718Sedwin/// Return a ModRefInfo value describing the general behavior of the 1152742Swollman/// instruction. 116325324Sgordonstatic 117273718SedwinAliasAnalysis::ModRefResult GetLocation(const Instruction *Inst, 118325324Sgordon AliasAnalysis::Location &Loc, 119273718Sedwin AliasAnalysis *AA) { 120325324Sgordon if (const LoadInst *LI = dyn_cast<LoadInst>(Inst)) { 121273718Sedwin if (LI->isUnordered()) { 122273718Sedwin Loc = AA->getLocation(LI); 1232742Swollman return AliasAnalysis::Ref; 124273718Sedwin } 125325324Sgordon if (LI->getOrdering() == Monotonic) { 126325324Sgordon Loc = AA->getLocation(LI); 127325324Sgordon return AliasAnalysis::ModRef; 128325324Sgordon } 1292742Swollman Loc = AliasAnalysis::Location(); 1302742Swollman return AliasAnalysis::ModRef; 131273718Sedwin } 1322742Swollman 1332742Swollman if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 1342742Swollman if (SI->isUnordered()) { 135273718Sedwin Loc = AA->getLocation(SI); 13630711Swollman return AliasAnalysis::Mod; 13730711Swollman } 13830711Swollman if (SI->getOrdering() == Monotonic) { 1392742Swollman Loc = AA->getLocation(SI); 1402742Swollman return AliasAnalysis::ModRef; 141274559Sedwin } 1422742Swollman Loc = AliasAnalysis::Location(); 143273718Sedwin return AliasAnalysis::ModRef; 144273718Sedwin } 14530711Swollman 14630711Swollman if (const VAArgInst *V = dyn_cast<VAArgInst>(Inst)) { 147273718Sedwin Loc = AA->getLocation(V); 1482742Swollman return AliasAnalysis::ModRef; 149273718Sedwin } 1502742Swollman 1512742Swollman if (const CallInst *CI = isFreeCall(Inst, AA->getTargetLibraryInfo())) { 15230711Swollman // calls to free() deallocate the entire structure 153270728Spluknet Loc = AliasAnalysis::Location(CI->getArgOperand(0)); 154270728Spluknet return AliasAnalysis::Mod; 155270728Spluknet } 156270728Spluknet 157270728Spluknet if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) 158270728Spluknet switch (II->getIntrinsicID()) { 159270728Spluknet case Intrinsic::lifetime_start: 160270728Spluknet case Intrinsic::lifetime_end: 161270728Spluknet case Intrinsic::invariant_start: 162270728Spluknet Loc = AliasAnalysis::Location(II->getArgOperand(1), 1632742Swollman cast<ConstantInt>(II->getArgOperand(0)) 1642742Swollman ->getZExtValue(), 165274559Sedwin II->getMetadata(LLVMContext::MD_tbaa)); 1662742Swollman // These intrinsics don't really modify the memory, but returning Mod 1672742Swollman // will allow them to be handled conservatively. 1682742Swollman return AliasAnalysis::Mod; 1692742Swollman case Intrinsic::invariant_end: 1702742Swollman Loc = AliasAnalysis::Location(II->getArgOperand(2), 171248307Sedwin cast<ConstantInt>(II->getArgOperand(1)) 172248307Sedwin ->getZExtValue(), 173248307Sedwin II->getMetadata(LLVMContext::MD_tbaa)); 174248307Sedwin // These intrinsics don't really modify the memory, but returning Mod 175248307Sedwin // will allow them to be handled conservatively. 1762742Swollman return AliasAnalysis::Mod; 17719878Swollman default: 1782742Swollman break; 17919878Swollman } 1802742Swollman 18119878Swollman // Otherwise, just do the coarse-grained thing that always works. 1822742Swollman if (Inst->mayWriteToMemory()) 1832742Swollman return AliasAnalysis::ModRef; 18419878Swollman if (Inst->mayReadFromMemory()) 18519878Swollman return AliasAnalysis::Ref; 1862742Swollman return AliasAnalysis::NoModRef; 18719878Swollman} 18819878Swollman 1892742Swollman/// getCallSiteDependencyFrom - Private helper for finding the local 19030711Swollman/// dependencies of a call site. 19119878SwollmanMemDepResult MemoryDependenceAnalysis:: 19219878SwollmangetCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall, 19319878Swollman BasicBlock::iterator ScanIt, BasicBlock *BB) { 19419878Swollman unsigned Limit = BlockScanLimit; 19530711Swollman 19643014Swollman // Walk backwards through the block, looking for dependencies 19743543Swollman while (ScanIt != BB->begin()) { 198221092Sedwin // Limit the amount of scanning we do so we don't end up with quadratic 199221092Sedwin // running time on extreme testcases. 200221092Sedwin --Limit; 201221092Sedwin if (!Limit) 202221092Sedwin return MemDepResult::getUnknown(); 203221092Sedwin 204221092Sedwin Instruction *Inst = --ScanIt; 205221092Sedwin 206221092Sedwin // If this inst is a memory op, get the pointer it accessed 207221092Sedwin AliasAnalysis::Location Loc; 208221092Sedwin AliasAnalysis::ModRefResult MR = GetLocation(Inst, Loc, AA); 209267473Sedwin if (Loc.Ptr) { 210163302Sru // A simple instruction. 211163302Sru if (AA->getModRefInfo(CS, Loc) != AliasAnalysis::NoModRef) 212163302Sru return MemDepResult::getClobber(Inst); 213163302Sru continue; 214163302Sru } 215267473Sedwin 216171948Sedwin if (CallSite InstCS = cast<Value>(Inst)) { 217171948Sedwin // Debug intrinsics don't cause dependences. 218171948Sedwin if (isa<DbgInfoIntrinsic>(Inst)) continue; 219270728Spluknet // If these two calls do not interfere, look past it. 220240457Sedwin switch (AA->getModRefInfo(CS, InstCS)) { 221325324Sgordon case AliasAnalysis::NoModRef: 222172479Sedwin // If the two calls are the same, return InstCS as a Def, so that 223172479Sedwin // CS can be found redundant and eliminated. 224267473Sedwin if (isReadOnlyCall && !(MR & AliasAnalysis::Mod) && 225172479Sedwin CS.getInstruction()->isIdenticalToWhenDefined(Inst)) 226172479Sedwin return MemDepResult::getDef(Inst); 227172479Sedwin 228172479Sedwin // Otherwise if the two calls don't interact (e.g. InstCS is readnone) 229172479Sedwin // keep scanning. 230172479Sedwin continue; 231172479Sedwin default: 232171948Sedwin return MemDepResult::getClobber(Inst); 233172479Sedwin } 23420094Swollman } 235191618Sedwin 236191618Sedwin // If we could not obtain a pointer for the instruction and the instruction 237191618Sedwin // touches memory then assume that this is a dependency. 238191618Sedwin if (MR != AliasAnalysis::NoModRef) 239192886Sedwin return MemDepResult::getClobber(Inst); 240191618Sedwin } 241192886Sedwin 242192886Sedwin // No dependence found. If this is the entry block of the function, it is 243191618Sedwin // unknown, otherwise it is non-local. 244192886Sedwin if (BB != &BB->getParent()->getEntryBlock()) 245192886Sedwin return MemDepResult::getNonLocal(); 246191618Sedwin return MemDepResult::getNonFuncLocal(); 247192886Sedwin} 248192886Sedwin 249191618Sedwin/// isLoadLoadClobberIfExtendedToFullWidth - Return true if LI is a load that 250192886Sedwin/// would fully overlap MemLoc if done as a wider legal integer load. 251191618Sedwin/// 252191618Sedwin/// MemLocBase, MemLocOffset are lazily computed here the first time the 253191618Sedwin/// base/offs of memloc is needed. 254191618Sedwinstatic bool 255191618SedwinisLoadLoadClobberIfExtendedToFullWidth(const AliasAnalysis::Location &MemLoc, 256191618Sedwin const Value *&MemLocBase, 257191618Sedwin int64_t &MemLocOffs, 258270728Spluknet const LoadInst *LI, 259325324Sgordon const DataLayout *TD) { 260325324Sgordon // If we have no target data, we can't do this. 261191618Sedwin if (TD == 0) return false; 262191618Sedwin 263191618Sedwin // If we haven't already computed the base/offset of MemLoc, do so now. 264191618Sedwin if (MemLocBase == 0) 265191618Sedwin MemLocBase = GetPointerBaseWithConstantOffset(MemLoc.Ptr, MemLocOffs, TD); 266196582Sedwin 267196582Sedwin unsigned Size = MemoryDependenceAnalysis:: 268240457Sedwin getLoadLoadClobberFullWidthSize(MemLocBase, MemLocOffs, MemLoc.Size, 269196582Sedwin LI, *TD); 270325324Sgordon return Size != 0; 271240457Sedwin} 272196582Sedwin 273325324Sgordon/// getLoadLoadClobberFullWidthSize - This is a little bit of analysis that 274196582Sedwin/// looks at a memory location for a load (specified by MemLocBase, Offs, 275240457Sedwin/// and Size) and compares it against a load. If the specified load could 276196582Sedwin/// be safely widened to a larger integer load that is 1) still efficient, 277196582Sedwin/// 2) safe for the target, and 3) would provide the specified memory 278196582Sedwin/// location value, then this function returns the size in bytes of the 279196582Sedwin/// load width to use. If not, this returns zero. 280210718Sedwinunsigned MemoryDependenceAnalysis:: 281270728SpluknetgetLoadLoadClobberFullWidthSize(const Value *MemLocBase, int64_t MemLocOffs, 282210718Sedwin unsigned MemLocSize, const LoadInst *LI, 283210718Sedwin const DataLayout &TD) { 284210718Sedwin // We can only extend simple integer loads. 285210718Sedwin if (!isa<IntegerType>(LI->getType()) || !LI->isSimple()) return 0; 286270728Spluknet 287210718Sedwin // Load widening is hostile to ThreadSanitizer: it may cause false positives 288210718Sedwin // or make the reports more cryptic (access sizes are wrong). 289210718Sedwin if (LI->getParent()->getParent()->getAttributes(). 290265978Sedwin hasAttribute(AttributeSet::FunctionIndex, Attribute::SanitizeThread)) 291265978Sedwin return 0; 292265978Sedwin 293265978Sedwin // Get the base of this load. 294273718Sedwin int64_t LIOffs = 0; 295265978Sedwin const Value *LIBase = 296265978Sedwin GetPointerBaseWithConstantOffset(LI->getPointerOperand(), LIOffs, &TD); 297267473Sedwin 298267473Sedwin // If the two pointers are not based on the same pointer, we can't tell that 299267473Sedwin // they are related. 300267473Sedwin if (LIBase != MemLocBase) return 0; 301267473Sedwin 302267473Sedwin // Okay, the two values are based on the same pointer, but returned as 303267473Sedwin // no-alias. This happens when we have things like two byte loads at "P+1" 304267473Sedwin // and "P+3". Check to see if increasing the size of the "LI" load up to its 305267473Sedwin // alignment (or the largest native integer type) will allow us to load all 306267473Sedwin // the bits required by MemLoc. 307267473Sedwin 308267473Sedwin // If MemLoc is before LI, then no widening of LI will help us out. 309267473Sedwin if (MemLocOffs < LIOffs) return 0; 310267473Sedwin 311265978Sedwin // Get the alignment of the load in bytes. We assume that it is safe to load 312265978Sedwin // any legal integer up to this size without a problem. For example, if we're 313267473Sedwin // looking at an i8 load on x86-32 that is known 1024 byte aligned, we can 314267473Sedwin // widen it up to an i32 load. If it is known 2-byte aligned, we can widen it 315265978Sedwin // to i16. 316283042Sedwin unsigned LoadAlign = LI->getAlignment(); 317283042Sedwin 318283042Sedwin int64_t MemLocEnd = MemLocOffs+MemLocSize; 319283042Sedwin 320283042Sedwin // If no amount of rounding up will let MemLoc fit into LI, then bail out. 321283042Sedwin if (LIOffs+LoadAlign < MemLocEnd) return 0; 322283042Sedwin 323325324Sgordon // This is the size of the load to try. Start with the next larger power of 324283042Sedwin // two. 325283079Sedwin unsigned NewLoadByteSize = LI->getType()->getPrimitiveSizeInBits()/8U; 326283079Sedwin NewLoadByteSize = NextPowerOf2(NewLoadByteSize); 327283079Sedwin 328283079Sedwin while (1) { 329283079Sedwin // If this load size is bigger than our known alignment or would not fit 330283079Sedwin // into a native integer register, then we fail. 331283079Sedwin if (NewLoadByteSize > LoadAlign || 332283079Sedwin !TD.fitsInLegalInteger(NewLoadByteSize*8)) 333283079Sedwin return 0; 334283079Sedwin 335284397Sedwin if (LIOffs+NewLoadByteSize > MemLocEnd && 336284397Sedwin LI->getParent()->getParent()->getAttributes(). 337284397Sedwin hasAttribute(AttributeSet::FunctionIndex, Attribute::SanitizeAddress)) 338284397Sedwin // We will be reading past the location accessed by the original program. 339283079Sedwin // While this is safe in a regular build, Address Safety analysis tools 340309583Sglebius // may start reporting false warnings. So, don't do widening. 341309583Sglebius return 0; 342309583Sglebius 343309583Sglebius // If a load of this width would include all of MemLoc, then we succeed. 344309583Sglebius if (LIOffs+NewLoadByteSize >= MemLocEnd) 345309583Sglebius return NewLoadByteSize; 346267473Sedwin 347267473Sedwin NewLoadByteSize <<= 1; 348267473Sedwin } 349267473Sedwin} 350267473Sedwin 351265978Sedwin/// getPointerDependencyFrom - Return the instruction on which a memory 352267473Sedwin/// location depends. If isLoad is true, this routine ignores may-aliases with 353267473Sedwin/// read-only operations. If isLoad is false, this routine ignores may-aliases 354283079Sedwin/// with reads from read-only locations. If possible, pass the query 355191618Sedwin/// instruction as well; this function may take advantage of the metadata 3562742Swollman/// annotated to the query instruction to refine the result. 357248307SedwinMemDepResult MemoryDependenceAnalysis:: 35819878SwollmangetPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, 3592742Swollman BasicBlock::iterator ScanIt, BasicBlock *BB, 3602742Swollman Instruction *QueryInst) { 361273718Sedwin 3622742Swollman const Value *MemLocBase = 0; 3632742Swollman int64_t MemLocOffset = 0; 3642742Swollman unsigned Limit = BlockScanLimit; 365274559Sedwin bool isInvariantLoad = false; 3662742Swollman if (isLoad && QueryInst) { 3672742Swollman LoadInst *LI = dyn_cast<LoadInst>(QueryInst); 368273718Sedwin if (LI && LI->getMetadata(LLVMContext::MD_invariant_load) != 0) 3692742Swollman isInvariantLoad = true; 3702742Swollman } 371270728Spluknet 3722742Swollman // Walk backwards through the basic block, looking for dependencies. 3732742Swollman while (ScanIt != BB->begin()) { 3742742Swollman Instruction *Inst = --ScanIt; 375270728Spluknet 376270728Spluknet if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) 377270728Spluknet // Debug intrinsics don't (and can't) cause dependencies. 378270728Spluknet if (isa<DbgInfoIntrinsic>(II)) continue; 379270728Spluknet 380270728Spluknet // Limit the amount of scanning we do so we don't end up with quadratic 381270728Spluknet // running time on extreme testcases. 382270728Spluknet --Limit; 3832742Swollman if (!Limit) 3842742Swollman return MemDepResult::getUnknown(); 385325324Sgordon 3862742Swollman if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) { 3872742Swollman // If we reach a lifetime begin or end marker, then the query ends here 388270728Spluknet // because the value is undefined. 3892742Swollman if (II->getIntrinsicID() == Intrinsic::lifetime_start) { 3902742Swollman // FIXME: This only considers queries directly on the invariant-tagged 391273718Sedwin // pointer, not on query pointers that are indexed off of them. It'd 392273718Sedwin // be nice to handle that at some point (the right approach is to use 393273718Sedwin // GetPointerBaseWithConstantOffset). 394325324Sgordon if (AA->isMustAlias(AliasAnalysis::Location(II->getArgOperand(1)), 395273718Sedwin MemLoc)) 396273718Sedwin return MemDepResult::getDef(II); 3972742Swollman continue; 398273718Sedwin } 399325324Sgordon } 40030711Swollman 4012742Swollman // Values depend on loads if the pointers are must aliased. This means that 4022742Swollman // a load depends on another must aliased load from the same value. 4032742Swollman if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) { 4042742Swollman // Atomic loads have complications involved. 4052742Swollman // FIXME: This is overly conservative. 406325324Sgordon if (!LI->isUnordered()) 407325324Sgordon return MemDepResult::getClobber(LI); 4082742Swollman 409274559Sedwin AliasAnalysis::Location LoadLoc = AA->getLocation(LI); 410274559Sedwin 411274559Sedwin // If we found a pointer, check if it could be the same as our pointer. 412274559Sedwin AliasAnalysis::AliasResult R = AA->alias(LoadLoc, MemLoc); 413274559Sedwin 414274559Sedwin if (isLoad) { 415274559Sedwin if (R == AliasAnalysis::NoAlias) { 416274559Sedwin // If this is an over-aligned integer load (for example, 417274559Sedwin // "load i8* %P, align 4") see if it would obviously overlap with the 4182742Swollman // queried location if widened to a larger load (e.g. if the queried 4192742Swollman // location is 1 byte at P+1). If so, return it as a load/load 420273718Sedwin // clobber result, allowing the client to decide to widen the load if 4212742Swollman // it wants to. 4222742Swollman if (IntegerType *ITy = dyn_cast<IntegerType>(LI->getType())) 423325324Sgordon if (LI->getAlignment()*8 > ITy->getPrimitiveSizeInBits() && 424325324Sgordon isLoadLoadClobberIfExtendedToFullWidth(MemLoc, MemLocBase, 425325324Sgordon MemLocOffset, LI, TD)) 426325324Sgordon return MemDepResult::getClobber(Inst); 427325324Sgordon 428325324Sgordon continue; 429325324Sgordon } 430325324Sgordon 431325324Sgordon // Must aliased loads are defs of each other. 432325324Sgordon if (R == AliasAnalysis::MustAlias) 433325324Sgordon return MemDepResult::getDef(Inst); 434325324Sgordon 435325324Sgordon#if 0 // FIXME: Temporarily disabled. GVN is cleverly rewriting loads 436325324Sgordon // in terms of clobbering loads, but since it does this by looking 437325324Sgordon // at the clobbering load directly, it doesn't know about any 4382742Swollman // phi translation that may have happened along the way. 4392742Swollman 4402742Swollman // If we have a partial alias, then return this as a clobber for the 441325324Sgordon // client to handle. 44230711Swollman if (R == AliasAnalysis::PartialAlias) 4432742Swollman return MemDepResult::getClobber(Inst); 4442742Swollman#endif 4452742Swollman 4462742Swollman // Random may-alias loads don't depend on each other without a 4472742Swollman // dependence. 448243003Sedwin continue; 449243003Sedwin } 450325324Sgordon 451243003Sedwin // Stores don't depend on other no-aliased accesses. 452243003Sedwin if (R == AliasAnalysis::NoAlias) 453243003Sedwin continue; 454325324Sgordon 455243003Sedwin // Stores don't alias loads from read-only memory. 456243003Sedwin if (AA->pointsToConstantMemory(LoadLoc)) 457243003Sedwin continue; 458243003Sedwin 459243003Sedwin // Stores depend on may/must aliased loads. 460243003Sedwin return MemDepResult::getDef(Inst); 461243003Sedwin } 462257681Sedwin 463257681Sedwin if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 464257681Sedwin // Atomic stores have complications involved. 465325324Sgordon // FIXME: This is overly conservative. 466257681Sedwin if (!SI->isUnordered()) 467257681Sedwin return MemDepResult::getClobber(SI); 468309583Sglebius 469257681Sedwin // If alias analysis can tell that this store is guaranteed to not modify 4702742Swollman // the query pointer, ignore it. Use getModRefInfo to handle cases where 47119878Swollman // the query pointer points to constant memory etc. 4722742Swollman if (AA->getModRefInfo(SI, MemLoc) == AliasAnalysis::NoModRef) 47319878Swollman continue; 4742742Swollman 47519878Swollman // Ok, this store might clobber the query pointer. Check to see if it is 4762742Swollman // a must alias: in this case, we want to return this as a def. 47719878Swollman AliasAnalysis::Location StoreLoc = AA->getLocation(SI); 4782742Swollman 47919878Swollman // If we found a pointer, check if it could be the same as our pointer. 48019878Swollman AliasAnalysis::AliasResult R = AA->alias(StoreLoc, MemLoc); 4812742Swollman 48219878Swollman if (R == AliasAnalysis::NoAlias) 483149514Swollman continue; 484243003Sedwin if (R == AliasAnalysis::MustAlias) 485243003Sedwin return MemDepResult::getDef(Inst); 486257681Sedwin if (isInvariantLoad) 487257681Sedwin continue; 4882742Swollman return MemDepResult::getClobber(Inst); 4892742Swollman } 49019878Swollman 4912742Swollman // If this is an allocation, and if we know that the accessed pointer is to 49258787Sru // the allocation, return Def. This means that there is no dependence and 493243003Sedwin // the access can be optimized based on that. For example, a load could 494273718Sedwin // turn into undef. 49558787Sru // Note: Only determine this to be a malloc if Inst is the malloc call, not 496243003Sedwin // a subsequent bitcast of the malloc call result. There can be stores to 497273718Sedwin // the malloced memory between the malloc call and its bitcast uses, and we 498273718Sedwin // need to continue scanning until the malloc call. 499257681Sedwin const TargetLibraryInfo *TLI = AA->getTargetLibraryInfo(); 5002742Swollman if (isa<AllocaInst>(Inst) || isNoAliasFn(Inst, TLI)) { 5012742Swollman const Value *AccessPtr = GetUnderlyingObject(MemLoc.Ptr, TD); 502274559Sedwin 5032742Swollman if (AccessPtr == Inst || AA->isMustAlias(Inst, AccessPtr)) 5042742Swollman return MemDepResult::getDef(Inst); 505273718Sedwin // Be conservative if the accessed pointer may alias the allocation. 5062742Swollman if (AA->alias(Inst, AccessPtr) != AliasAnalysis::NoAlias) 5072742Swollman return MemDepResult::getClobber(Inst); 5082742Swollman // If the allocation is not aliased and does not read memory (like 509270728Spluknet // strdup), it is safe to ignore. 5102742Swollman if (isa<AllocaInst>(Inst) || 5112742Swollman isMallocLikeFn(Inst, TLI) || isCallocLikeFn(Inst, TLI)) 512181421Sedwin continue; 513181421Sedwin } 514181421Sedwin 515181421Sedwin // See if this instruction (e.g. a call or vaarg) mod/ref's the pointer. 516240457Sedwin AliasAnalysis::ModRefResult MR = AA->getModRefInfo(Inst, MemLoc); 517181421Sedwin // If necessary, perform additional analysis. 518325324Sgordon if (MR == AliasAnalysis::ModRef) 519181424Sedwin MR = AA->callCapturesBefore(Inst, MemLoc, DT); 520181421Sedwin switch (MR) { 521181421Sedwin case AliasAnalysis::NoModRef: 522181424Sedwin // If the call has no effect on the queried pointer, just ignore it. 523181421Sedwin continue; 524181421Sedwin case AliasAnalysis::Mod: 525181421Sedwin return MemDepResult::getClobber(Inst); 526181421Sedwin case AliasAnalysis::Ref: 527181424Sedwin // If the call is known to never store to the pointer, and if this is a 528181421Sedwin // load query, we can safely ignore it (scan past it). 529181421Sedwin if (isLoad) 530181421Sedwin continue; 531181424Sedwin default: 532181424Sedwin // Otherwise, there is a potential dependence. Return a clobber. 533181424Sedwin return MemDepResult::getClobber(Inst); 534181424Sedwin } 535181424Sedwin } 536181424Sedwin 537181424Sedwin // No dependence found. If this is the entry block of the function, it is 538240457Sedwin // unknown, otherwise it is non-local. 539240457Sedwin if (BB != &BB->getParent()->getEntryBlock()) 540240457Sedwin return MemDepResult::getNonLocal(); 541240457Sedwin return MemDepResult::getNonFuncLocal(); 542240457Sedwin} 543240457Sedwin 544181424Sedwin/// getDependency - Return the instruction on which a memory operation 545181424Sedwin/// depends. 546181424SedwinMemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) { 547181424Sedwin Instruction *ScanPos = QueryInst; 548286750Sedwin 549181424Sedwin // Check for a cached result 550181424Sedwin MemDepResult &LocalCache = LocalDeps[QueryInst]; 551181424Sedwin 552270728Spluknet // If the cached entry is non-dirty, just return it. Note that this depends 553270728Spluknet // on MemDepResult's default constructing to 'dirty'. 554181424Sedwin if (!LocalCache.isDirty()) 555181424Sedwin return LocalCache; 556183066Sedwin 557183066Sedwin // Otherwise, if we have a dirty entry, we know we can start the scan at that 558192886Sedwin // instruction, which may save us some work. 559183066Sedwin if (Instruction *Inst = LocalCache.getInst()) { 560183066Sedwin ScanPos = Inst; 561183066Sedwin 562183066Sedwin RemoveFromReverseMap(ReverseLocalDeps, Inst, QueryInst); 563183066Sedwin } 564183066Sedwin 565183066Sedwin BasicBlock *QueryParent = QueryInst->getParent(); 566183066Sedwin 567183066Sedwin // Do the scan. 568270728Spluknet if (BasicBlock::iterator(QueryInst) == QueryParent->begin()) { 569183066Sedwin // No dependence found. If this is the entry block of the function, it is 570183066Sedwin // unknown, otherwise it is non-local. 571183864Sedwin if (QueryParent != &QueryParent->getParent()->getEntryBlock()) 572183864Sedwin LocalCache = MemDepResult::getNonLocal(); 573183864Sedwin else 574183864Sedwin LocalCache = MemDepResult::getNonFuncLocal(); 575183864Sedwin } else { 576183864Sedwin AliasAnalysis::Location MemLoc; 577196581Sedwin AliasAnalysis::ModRefResult MR = GetLocation(QueryInst, MemLoc, AA); 578196581Sedwin if (MemLoc.Ptr) { 579196581Sedwin // If we can do a pointer scan, make it happen. 580196581Sedwin bool isLoad = !(MR & AliasAnalysis::Mod); 581196581Sedwin if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(QueryInst)) 582196581Sedwin isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_start; 583196581Sedwin 584196581Sedwin LocalCache = getPointerDependencyFrom(MemLoc, isLoad, ScanPos, 585196581Sedwin QueryParent, QueryInst); 586325324Sgordon } else if (isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst)) { 587196581Sedwin CallSite QueryCS(QueryInst); 588196581Sedwin bool isReadOnly = AA->onlyReadsMemory(QueryCS); 589240457Sedwin LocalCache = getCallSiteDependencyFrom(QueryCS, isReadOnly, ScanPos, 590196581Sedwin QueryParent); 591196581Sedwin } else 592196581Sedwin // Non-memory instruction. 593181421Sedwin LocalCache = MemDepResult::getUnknown(); 594181421Sedwin } 595181421Sedwin 596196581Sedwin // Remember the result! 597196581Sedwin if (Instruction *I = LocalCache.getInst()) 5982742Swollman ReverseLocalDeps[I].insert(QueryInst); 599273718Sedwin 600325324Sgordon return LocalCache; 6012742Swollman} 6022742Swollman 6032742Swollman#ifndef NDEBUG 6042742Swollman/// AssertSorted - This method is used when -debug is specified to verify that 605274559Sedwin/// cache arrays are properly kept sorted. 6062742Swollmanstatic void AssertSorted(MemoryDependenceAnalysis::NonLocalDepInfo &Cache, 6072742Swollman int Count = -1) { 608270728Spluknet if (Count == -1) Count = Cache.size(); 609181418Sedwin if (Count == 0) return; 610181418Sedwin 611181418Sedwin for (unsigned i = 1; i != unsigned(Count); ++i) 612181418Sedwin assert(!(Cache[i] < Cache[i-1]) && "Cache isn't sorted!"); 613181418Sedwin} 614181418Sedwin#endif 615181418Sedwin 616270728Spluknet/// getNonLocalCallDependency - Perform a full dependency query for the 617181418Sedwin/// specified call, returning the set of blocks that the value is 618325324Sgordon/// potentially live across. The returned set of results will include a 619181418Sedwin/// "NonLocal" result for all blocks where the value is live across. 620181418Sedwin/// 621181418Sedwin/// This method assumes the instruction returns a "NonLocal" dependency 622273718Sedwin/// within its own block. 623273718Sedwin/// 624181418Sedwin/// This returns a reference to an internal data structure that may be 625181418Sedwin/// invalidated on the next non-local query or when an instruction is 626181418Sedwin/// removed. Clients must copy this data if they want it around longer than 627181418Sedwin/// that. 628181418Sedwinconst MemoryDependenceAnalysis::NonLocalDepInfo & 629181418SedwinMemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { 630181418Sedwin assert(getDependency(QueryCS.getInstruction()).isNonLocal() && 631325324Sgordon "getNonLocalCallDependency should only be used on calls with non-local deps!"); 632270728Spluknet PerInstNLInfo &CacheP = NonLocalDeps[QueryCS.getInstruction()]; 633270728Spluknet NonLocalDepInfo &Cache = CacheP.first; 634181418Sedwin 635270728Spluknet /// DirtyBlocks - This is the set of blocks that need to be recomputed. In 636270728Spluknet /// the cached case, this can happen due to instructions being deleted etc. In 637270728Spluknet /// the uncached case, this starts out as the set of predecessors we care 638181418Sedwin /// about. 639270728Spluknet SmallVector<BasicBlock*, 32> DirtyBlocks; 640270728Spluknet 641270728Spluknet if (!Cache.empty()) { 642270728Spluknet // Okay, we have a cache entry. If we know it is not dirty, just return it 643181418Sedwin // with no computation. 644181418Sedwin if (!CacheP.second) { 645181418Sedwin ++NumCacheNonLocal; 646181418Sedwin return Cache; 647181418Sedwin } 648181418Sedwin 649270728Spluknet // If we already have a partially computed set of results, scan them to 650270728Spluknet // determine what is dirty, seeding our initial DirtyBlocks worklist. 651181418Sedwin for (NonLocalDepInfo::iterator I = Cache.begin(), E = Cache.end(); 652270728Spluknet I != E; ++I) 653325324Sgordon if (I->getResult().isDirty()) 654181418Sedwin DirtyBlocks.push_back(I->getBB()); 655183066Sedwin 656240457Sedwin // Sort the cache so that we can do fast binary search lookups below. 657240457Sedwin std::sort(Cache.begin(), Cache.end()); 658183066Sedwin 659183066Sedwin ++NumCacheDirtyNonLocal; 660183066Sedwin //cerr << "CACHED CASE: " << DirtyBlocks.size() << " dirty: " 661183066Sedwin // << Cache.size() << " cached: " << *QueryInst; 662183066Sedwin } else { 663183066Sedwin // Seed DirtyBlocks with each of the preds of QueryInst's block. 664325324Sgordon BasicBlock *QueryBB = QueryCS.getInstruction()->getParent(); 665190372Sedwin for (BasicBlock **PI = PredCache->GetPreds(QueryBB); *PI; ++PI) 666190372Sedwin DirtyBlocks.push_back(*PI); 667190372Sedwin ++NumUncacheNonLocal; 668190372Sedwin } 669190372Sedwin 670190372Sedwin // isReadonlyCall - If this is a read-only call, we can be more aggressive. 671190372Sedwin bool isReadonlyCall = AA->onlyReadsMemory(QueryCS); 672190372Sedwin 673190372Sedwin SmallPtrSet<BasicBlock*, 64> Visited; 674325324Sgordon 675190372Sedwin unsigned NumSortedEntries = Cache.size(); 676190372Sedwin DEBUG(AssertSorted(Cache)); 677190372Sedwin 678270728Spluknet // Iterate while we still have blocks to update. 679190372Sedwin while (!DirtyBlocks.empty()) { 680286750Sedwin BasicBlock *DirtyBB = DirtyBlocks.back(); 681190372Sedwin DirtyBlocks.pop_back(); 682190372Sedwin 683190372Sedwin // Already processed this block? 684190372Sedwin if (!Visited.insert(DirtyBB)) 685190372Sedwin continue; 686190372Sedwin 687190372Sedwin // Do a binary search to see if we already have an entry for this block in 688206868Sedwin // the cache set. If so, find it. 689206868Sedwin DEBUG(AssertSorted(Cache, NumSortedEntries)); 690206868Sedwin NonLocalDepInfo::iterator Entry = 691206868Sedwin std::upper_bound(Cache.begin(), Cache.begin()+NumSortedEntries, 692206868Sedwin NonLocalDepEntry(DirtyBB)); 693206868Sedwin if (Entry != Cache.begin() && prior(Entry)->getBB() == DirtyBB) 694206868Sedwin --Entry; 695206868Sedwin 696206868Sedwin NonLocalDepEntry *ExistingResult = 0; 697325324Sgordon if (Entry != Cache.begin()+NumSortedEntries && 698206868Sedwin Entry->getBB() == DirtyBB) { 699220286Sedwin // If we already have an entry, and if it isn't already dirty, the block 700220286Sedwin // is done. 701273718Sedwin if (!Entry->getResult().isDirty()) 702273718Sedwin continue; 703220286Sedwin 704220286Sedwin // Otherwise, remember this slot so we can update the value. 705220286Sedwin ExistingResult = &*Entry; 706220286Sedwin } 707220286Sedwin 708220286Sedwin // If the dirty entry has a pointer, start scanning from it so we don't have 709220286Sedwin // to rescan the entire block. 710220286Sedwin BasicBlock::iterator ScanPos = DirtyBB->end(); 711220286Sedwin if (ExistingResult) { 712220286Sedwin if (Instruction *Inst = ExistingResult->getResult().getInst()) { 713220286Sedwin ScanPos = Inst; 714325324Sgordon // We're removing QueryInst's use of Inst. 715220286Sedwin RemoveFromReverseMap(ReverseNonLocalDeps, Inst, 716220286Sedwin QueryCS.getInstruction()); 717220286Sedwin } 718220286Sedwin } 719220286Sedwin 720220286Sedwin // Find out if this block has a local dependency for QueryInst. 721220286Sedwin MemDepResult Dep; 722220286Sedwin 723220286Sedwin if (ScanPos != DirtyBB->begin()) { 724220286Sedwin Dep = getCallSiteDependencyFrom(QueryCS, isReadonlyCall,ScanPos, DirtyBB); 725220286Sedwin } else if (DirtyBB != &DirtyBB->getParent()->getEntryBlock()) { 726220286Sedwin // No dependence found. If this is the entry block of the function, it is 727240457Sedwin // a clobber, otherwise it is unknown. 728270728Spluknet Dep = MemDepResult::getNonLocal(); 729270728Spluknet } else { 730270728Spluknet Dep = MemDepResult::getNonFuncLocal(); 731240457Sedwin } 732240457Sedwin 733240457Sedwin // If we had a dirty entry for the block, update it. Otherwise, just add 734240457Sedwin // a new entry. 735240457Sedwin if (ExistingResult) 736240457Sedwin ExistingResult->setResult(Dep); 737240457Sedwin else 738240457Sedwin Cache.push_back(NonLocalDepEntry(DirtyBB, Dep)); 739240457Sedwin 740240457Sedwin // If the block has a dependency (i.e. it isn't completely transparent to 741240457Sedwin // the value), remember the association! 742240457Sedwin if (!Dep.isNonLocal()) { 743240457Sedwin // Keep the ReverseNonLocalDeps map up to date so we can efficiently 744240457Sedwin // update this when we remove instructions. 745240457Sedwin if (Instruction *Inst = Dep.getInst()) 746240457Sedwin ReverseNonLocalDeps[Inst].insert(QueryCS.getInstruction()); 747240457Sedwin } else { 748240457Sedwin 749270728Spluknet // If the block *is* completely transparent to the load, we need to check 750270728Spluknet // the predecessors of this block. Add them to our worklist. 751240457Sedwin for (BasicBlock **PI = PredCache->GetPreds(DirtyBB); *PI; ++PI) 752240457Sedwin DirtyBlocks.push_back(*PI); 753240457Sedwin } 754240457Sedwin } 755240457Sedwin 756240457Sedwin return Cache; 757240457Sedwin} 758240457Sedwin 759240457Sedwin/// getNonLocalPointerDependency - Perform a full dependency query for an 760240457Sedwin/// access to the specified (non-volatile) memory location, returning the 761240457Sedwin/// set of instructions that either define or clobber the value. 762240457Sedwin/// 763240457Sedwin/// This method assumes the pointer has a "NonLocal" dependency within its 764240457Sedwin/// own block. 765240457Sedwin/// 766240457Sedwinvoid MemoryDependenceAnalysis:: 767248307SedwingetNonLocalPointerDependency(const AliasAnalysis::Location &Loc, bool isLoad, 768248307Sedwin BasicBlock *FromBB, 769248307Sedwin SmallVectorImpl<NonLocalDepResult> &Result) { 770248307Sedwin assert(Loc.Ptr->getType()->isPointerTy() && 771248307Sedwin "Can't get pointer deps of a non-pointer!"); 772273718Sedwin Result.clear(); 773253009Sedwin 774253009Sedwin PHITransAddr Address(const_cast<Value *>(Loc.Ptr), TD); 775253009Sedwin 776253009Sedwin // This is the set of blocks we've inspected, and the pointer we consider in 777253009Sedwin // each block. Because of critical edges, we currently bail out if querying 778253009Sedwin // a block with multiple different pointers. This can happen during PHI 779257681Sedwin // translation. 780257681Sedwin DenseMap<BasicBlock*, Value*> Visited; 781257681Sedwin if (!getNonLocalPointerDepFromBB(Address, Loc, isLoad, FromBB, 782257681Sedwin Result, Visited, true)) 783257681Sedwin return; 784257681Sedwin Result.clear(); 785257681Sedwin Result.push_back(NonLocalDepResult(FromBB, 786257681Sedwin MemDepResult::getUnknown(), 787257681Sedwin const_cast<Value *>(Loc.Ptr))); 788257681Sedwin} 789263901Sedwin 790263901Sedwin/// GetNonLocalInfoForBlock - Compute the memdep value for BB with 791263901Sedwin/// Pointer/PointeeSize using either cached information in Cache or by doing a 792267473Sedwin/// lookup (which may use dirty cache info if available). If we do a lookup, 793267473Sedwin/// add the result to the cache. 794267473SedwinMemDepResult MemoryDependenceAnalysis:: 795267473SedwinGetNonLocalInfoForBlock(const AliasAnalysis::Location &Loc, 796267473Sedwin bool isLoad, BasicBlock *BB, 797267473Sedwin NonLocalDepInfo *Cache, unsigned NumSortedEntries) { 798284397Sedwin 799284397Sedwin // Do a binary search to see if we already have an entry for this block in 800284397Sedwin // the cache set. If so, find it. 801284397Sedwin NonLocalDepInfo::iterator Entry = 802284397Sedwin std::upper_bound(Cache->begin(), Cache->begin()+NumSortedEntries, 803284397Sedwin NonLocalDepEntry(BB)); 804284397Sedwin if (Entry != Cache->begin() && (Entry-1)->getBB() == BB) 805284397Sedwin --Entry; 806325324Sgordon 807284397Sedwin NonLocalDepEntry *ExistingResult = 0; 808284397Sedwin if (Entry != Cache->begin()+NumSortedEntries && Entry->getBB() == BB) 809284397Sedwin ExistingResult = &*Entry; 810284397Sedwin 811284397Sedwin // If we have a cached entry, and it is non-dirty, use it as the value for 812284397Sedwin // this dependency. 813284397Sedwin if (ExistingResult && !ExistingResult->getResult().isDirty()) { 814284397Sedwin ++NumCacheNonLocalPtr; 815325324Sgordon return ExistingResult->getResult(); 816284397Sedwin } 817284397Sedwin 818284397Sedwin // Otherwise, we have to scan for the value. If we have a dirty cache 819284397Sedwin // entry, start scanning from its position, otherwise we scan from the end 820267473Sedwin // of the block. 821284397Sedwin BasicBlock::iterator ScanPos = BB->end(); 822284397Sedwin if (ExistingResult && ExistingResult->getResult().getInst()) { 823267473Sedwin assert(ExistingResult->getResult().getInst()->getParent() == BB && 824267473Sedwin "Instruction invalidated?"); 825284397Sedwin ++NumCacheDirtyNonLocalPtr; 826284397Sedwin ScanPos = ExistingResult->getResult().getInst(); 827267473Sedwin 828267473Sedwin // Eliminating the dirty entry from 'Cache', so update the reverse info. 829267473Sedwin ValueIsLoadPair CacheKey(Loc.Ptr, isLoad); 830284397Sedwin RemoveFromReverseMap(ReverseNonLocalPtrDeps, ScanPos, CacheKey); 831284397Sedwin } else { 832284397Sedwin ++NumUncacheNonLocalPtr; 833267473Sedwin } 834267473Sedwin 835267473Sedwin // Scan the block for the dependency. 836267473Sedwin MemDepResult Dep = getPointerDependencyFrom(Loc, isLoad, ScanPos, BB); 837267473Sedwin 838267473Sedwin // If we had a dirty entry for the block, update it. Otherwise, just add 839267473Sedwin // a new entry. 840267473Sedwin if (ExistingResult) 841267473Sedwin ExistingResult->setResult(Dep); 842248307Sedwin else 843248307Sedwin Cache->push_back(NonLocalDepEntry(BB, Dep)); 84420094Swollman 845183066Sedwin // If the block has a dependency (i.e. it isn't completely transparent to 84619878Swollman // the value), remember the reverse association because we just added it 8472742Swollman // to Cache! 84819878Swollman if (!Dep.isDef() && !Dep.isClobber()) 8492742Swollman return Dep; 85019878Swollman 8512742Swollman // Keep the ReverseNonLocalPtrDeps map up to date so we can efficiently 85219878Swollman // update MemDep when we remove instructions. 8532742Swollman Instruction *Inst = Dep.getInst(); 85419878Swollman assert(Inst && "Didn't depend on anything?"); 8552742Swollman ValueIsLoadPair CacheKey(Loc.Ptr, isLoad); 85619878Swollman ReverseNonLocalPtrDeps[Inst].insert(CacheKey); 8572742Swollman return Dep; 8582742Swollman} 85919878Swollman 8602742Swollman/// SortNonLocalDepInfoCache - Sort the a NonLocalDepInfo cache, given a certain 861181418Sedwin/// number of elements in the array that are already properly ordered. This is 862183066Sedwin/// optimized for the case when only a few entries are added. 863190372Sedwinstatic void 864267473SedwinSortNonLocalDepInfoCache(MemoryDependenceAnalysis::NonLocalDepInfo &Cache, 865206868Sedwin unsigned NumSortedEntries) { 866206868Sedwin switch (Cache.size() - NumSortedEntries) { 867220286Sedwin case 0: 868309583Sglebius // done, no new entries. 869267473Sedwin break; 870267473Sedwin case 2: { 871267473Sedwin // Two new entries, insert the last one into place. 872309583Sglebius NonLocalDepEntry Val = Cache.back(); 873267473Sedwin Cache.pop_back(); 874267473Sedwin MemoryDependenceAnalysis::NonLocalDepInfo::iterator Entry = 875267473Sedwin std::upper_bound(Cache.begin(), Cache.end()-1, Val); 876284397Sedwin Cache.insert(Entry, Val); 877267473Sedwin // FALL THROUGH. 878267473Sedwin } 879284397Sedwin case 1: 880284397Sedwin // One new entry, Just insert the new value at the appropriate position. 881284397Sedwin if (Cache.size() != 1) { 882284397Sedwin NonLocalDepEntry Val = Cache.back(); 883284397Sedwin Cache.pop_back(); 884284397Sedwin MemoryDependenceAnalysis::NonLocalDepInfo::iterator Entry = 885284397Sedwin std::upper_bound(Cache.begin(), Cache.end(), Val); 886284397Sedwin Cache.insert(Entry, Val); 887284397Sedwin } 888284397Sedwin break; 889284397Sedwin default: 890284397Sedwin // Added many values, do a full scale sort. 891284397Sedwin std::sort(Cache.begin(), Cache.end()); 892284397Sedwin break; 893284397Sedwin } 894284397Sedwin} 895284397Sedwin 896284397Sedwin/// getNonLocalPointerDepFromBB - Perform a dependency query based on 897267473Sedwin/// pointer/pointeesize starting at the end of StartBB. Add any clobber/def 898284397Sedwin/// results to the results vector and keep track of which blocks are visited in 899284397Sedwin/// 'Visited'. 900240457Sedwin/// 9012742Swollman/// This has special behavior for the first block queries (when SkipFirstBlock 9022742Swollman/// is true). In this special case, it ignores the contents of the specified 90319878Swollman/// block and starts returning dependence info for its predecessors. 90419878Swollman/// 905181418Sedwin/// This function returns false on success, or true to indicate that it could 906257681Sedwin/// not compute dependence information for some reason. This should be treated 90719878Swollman/// as a clobber dependence on the first instruction in the predecessor block. 908257681Sedwinbool MemoryDependenceAnalysis:: 909257681SedwingetNonLocalPointerDepFromBB(const PHITransAddr &Pointer, 910257681Sedwin const AliasAnalysis::Location &Loc, 911257681Sedwin bool isLoad, BasicBlock *StartBB, 912257681Sedwin SmallVectorImpl<NonLocalDepResult> &Result, 913257681Sedwin DenseMap<BasicBlock*, Value*> &Visited, 914257681Sedwin bool SkipFirstBlock) { 915257681Sedwin // Look up the cached info for Pointer. 916257681Sedwin ValueIsLoadPair CacheKey(Pointer.getAddr(), isLoad); 917257681Sedwin 918270728Spluknet // Set up a temporary NLPI value. If the map doesn't yet have an entry for 919325324Sgordon // CacheKey, this value will be inserted as the associated value. Otherwise, 920257681Sedwin // it'll be ignored, and we'll have to check to see if the cached size and 9218029Swollman // tbaa tag are consistent with the current query. 9222742Swollman NonLocalPointerInfo InitialNLPI; 923273718Sedwin InitialNLPI.Size = Loc.Size; 924273718Sedwin InitialNLPI.TBAATag = Loc.TBAATag; 925273718Sedwin 926325324Sgordon // Get the NLPI for CacheKey, inserting one into the map if it doesn't 927273718Sedwin // already have one. 928273718Sedwin std::pair<CachedNonLocalPointerInfo::iterator, bool> Pair = 9292742Swollman NonLocalPointerDeps.insert(std::make_pair(CacheKey, InitialNLPI)); 9302742Swollman NonLocalPointerInfo *CacheInfo = &Pair.first->second; 93130711Swollman 932273718Sedwin // If we already have a cache entry for this CacheKey, we may need to do some 933273718Sedwin // work to reconcile the cache entry and the current query. 934273718Sedwin if (!Pair.second) { 935273718Sedwin if (CacheInfo->Size < Loc.Size) { 936273718Sedwin // The query's Size is greater than the cached one. Throw out the 937273718Sedwin // cached data and proceed with the query at the greater size. 938273718Sedwin CacheInfo->Pair = BBSkipFirstBlockPair(); 9392742Swollman CacheInfo->Size = Loc.Size; 940325324Sgordon for (NonLocalDepInfo::iterator DI = CacheInfo->NonLocalDeps.begin(), 9412742Swollman DE = CacheInfo->NonLocalDeps.end(); DI != DE; ++DI) 942169811Swollman if (Instruction *Inst = DI->getResult().getInst()) 943325324Sgordon RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey); 944325324Sgordon CacheInfo->NonLocalDeps.clear(); 945325324Sgordon } else if (CacheInfo->Size > Loc.Size) { 946325324Sgordon // This query's Size is less than the cached one. Conservatively restart 947325324Sgordon // the query using the greater size. 948325324Sgordon return getNonLocalPointerDepFromBB(Pointer, 949325324Sgordon Loc.getWithNewSize(CacheInfo->Size), 950325324Sgordon isLoad, StartBB, Result, Visited, 951325324Sgordon SkipFirstBlock); 952273718Sedwin } 953273718Sedwin 954169811Swollman // If the query's TBAATag is inconsistent with the cached one, 955169811Swollman // conservatively throw out the cached data and restart the query with 956169811Swollman // no tag if needed. 957169811Swollman if (CacheInfo->TBAATag != Loc.TBAATag) { 958169811Swollman if (CacheInfo->TBAATag) { 959169811Swollman CacheInfo->Pair = BBSkipFirstBlockPair(); 960240457Sedwin CacheInfo->TBAATag = 0; 961325324Sgordon for (NonLocalDepInfo::iterator DI = CacheInfo->NonLocalDeps.begin(), 962325324Sgordon DE = CacheInfo->NonLocalDeps.end(); DI != DE; ++DI) 963325324Sgordon if (Instruction *Inst = DI->getResult().getInst()) 964325324Sgordon RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey); 965325324Sgordon CacheInfo->NonLocalDeps.clear(); 966325324Sgordon } 967169811Swollman if (Loc.TBAATag) 968325324Sgordon return getNonLocalPointerDepFromBB(Pointer, Loc.getWithoutTBAATag(), 969325324Sgordon isLoad, StartBB, Result, Visited, 970325324Sgordon SkipFirstBlock); 971325324Sgordon } 972325324Sgordon } 973325324Sgordon 974325324Sgordon NonLocalDepInfo *Cache = &CacheInfo->NonLocalDeps; 975325324Sgordon 976325324Sgordon // If we have valid cached information for exactly the block we are 97720094Swollman // investigating, just return it with no recomputation. 978325324Sgordon if (CacheInfo->Pair == BBSkipFirstBlockPair(StartBB, SkipFirstBlock)) { 979325324Sgordon // We have a fully cached result for this query then we can just return the 980325324Sgordon // cached results and populate the visited set. However, we have to verify 9812742Swollman // that we don't already have conflicting results for these blocks. Check 9822742Swollman // to ensure that if a block in the results set is in the visited set that 983325324Sgordon // it was for the same pointer query. 984273718Sedwin if (!Visited.empty()) { 985273718Sedwin for (NonLocalDepInfo::iterator I = Cache->begin(), E = Cache->end(); 98630711Swollman I != E; ++I) { 987325324Sgordon DenseMap<BasicBlock*, Value*>::iterator VI = Visited.find(I->getBB()); 988325324Sgordon if (VI == Visited.end() || VI->second == Pointer.getAddr()) 989325324Sgordon continue; 9902742Swollman 9912742Swollman // We have a pointer mismatch in a block. Just return clobber, saying 992273718Sedwin // that something was clobbered in this result. We could also do a 9932742Swollman // non-fully cached query, but there is little point in doing this. 9942742Swollman return true; 9952742Swollman } 9962742Swollman } 99730711Swollman 998273718Sedwin Value *Addr = Pointer.getAddr(); 999273718Sedwin for (NonLocalDepInfo::iterator I = Cache->begin(), E = Cache->end(); 1000273718Sedwin I != E; ++I) { 1001273718Sedwin Visited.insert(std::make_pair(I->getBB(), Addr)); 1002273718Sedwin if (I->getResult().isNonLocal()) { 1003273718Sedwin continue; 1004273718Sedwin } 1005273718Sedwin 1006273718Sedwin if (!DT) { 10072742Swollman Result.push_back(NonLocalDepResult(I->getBB(), 1008270728Spluknet MemDepResult::getUnknown(), 10092742Swollman Addr)); 1010273718Sedwin } else if (DT->isReachableFromEntry(I->getBB())) { 1011325324Sgordon Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(), Addr)); 101243014Swollman } 1013270728Spluknet } 1014270728Spluknet ++NumCacheCompleteNonLocalPtr; 1015270728Spluknet return false; 101643014Swollman } 1017270728Spluknet 1018270728Spluknet // Otherwise, either this is a new block, a block with an invalid cache 101958787Sru // pointer or one that we're about to invalidate by putting more info into it 102043014Swollman // than its valid cache info. If empty, the result will be valid cache info, 102143014Swollman // otherwise it isn't. 102243014Swollman if (Cache->empty()) 102343014Swollman CacheInfo->Pair = BBSkipFirstBlockPair(StartBB, SkipFirstBlock); 102443014Swollman else 102543014Swollman CacheInfo->Pair = BBSkipFirstBlockPair(); 10262742Swollman 10272742Swollman SmallVector<BasicBlock*, 32> Worklist; 1028273718Sedwin Worklist.push_back(StartBB); 10292742Swollman 10302742Swollman // PredList used inside loop. 1031270728Spluknet SmallVector<std::pair<BasicBlock*, PHITransAddr>, 16> PredList; 103214343Swollman 103330711Swollman // Keep track of the entries that we know are sorted. Previously cached 1034270728Spluknet // entries will all be sorted. The entries we add we only sort on demand (we 103558787Sru // don't insert every element into its sorted position). We know that we 103658787Sru // won't get any reuse from currently inserted values, because we don't 1037270728Spluknet // revisit blocks after we insert info for them. 103814343Swollman unsigned NumSortedEntries = Cache->size(); 1039270728Spluknet DEBUG(AssertSorted(*Cache)); 10402742Swollman 1041270728Spluknet while (!Worklist.empty()) { 10422742Swollman BasicBlock *BB = Worklist.pop_back_val(); 10432742Swollman 10442742Swollman // Skip the first block if we have it. 1045273718Sedwin if (!SkipFirstBlock) { 1046325324Sgordon // Analyze the dependency of *Pointer in FromBB. See if we already have 104786222Swollman // been here. 104886222Swollman assert(Visited.count(BB) && "Should check 'visited' before adding to WL"); 104986222Swollman 105086222Swollman // Get the dependency info for Pointer in BB. If we have cached 105186222Swollman // information, we will use it, otherwise we compute it. 105286222Swollman DEBUG(AssertSorted(*Cache, NumSortedEntries)); 10532742Swollman MemDepResult Dep = GetNonLocalInfoForBlock(Loc, isLoad, BB, Cache, 10542742Swollman NumSortedEntries); 1055270728Spluknet 10562742Swollman // If we got a Def or Clobber, add this to the list of results. 10572742Swollman if (!Dep.isNonLocal()) { 1058274559Sedwin if (!DT) { 10592742Swollman Result.push_back(NonLocalDepResult(BB, 10602742Swollman MemDepResult::getUnknown(), 10612742Swollman Pointer.getAddr())); 106230711Swollman continue; 10632742Swollman } else if (DT->isReachableFromEntry(BB)) { 10642742Swollman Result.push_back(NonLocalDepResult(BB, Dep, Pointer.getAddr())); 10652742Swollman continue; 106630711Swollman } 106730711Swollman } 1068273718Sedwin } 1069273718Sedwin 1070273718Sedwin // If 'Pointer' is an instruction defined in this block, then we need to do 107130711Swollman // phi translation to change it into a value live in the predecessor block. 107258787Sru // If not, we just add the predecessors to the worklist and scan them with 10732742Swollman // the same Pointer. 10742742Swollman if (!Pointer.NeedsPHITranslationFromBlock(BB)) { 10752742Swollman SkipFirstBlock = false; 1076325324Sgordon SmallVector<BasicBlock*, 16> NewBlocks; 1077270728Spluknet for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) { 1078270728Spluknet // Verify that we haven't looked at this block yet. 1079270728Spluknet std::pair<DenseMap<BasicBlock*,Value*>::iterator, bool> 108058787Sru InsertRes = Visited.insert(std::make_pair(*PI, Pointer.getAddr())); 108158787Sru if (InsertRes.second) { 108258787Sru // First time we've looked at *PI. 1083325324Sgordon NewBlocks.push_back(*PI); 1084325324Sgordon continue; 1085325324Sgordon } 1086325324Sgordon 108758787Sru // If we have seen this block before, but it was with a different 1088325324Sgordon // pointer then we have a phi translation failure and we have to treat 1089325324Sgordon // this as a clobber. 1090325324Sgordon if (InsertRes.first->second != Pointer.getAddr()) { 1091325324Sgordon // Make sure to clean up the Visited map before continuing on to 1092325324Sgordon // PredTranslationFailure. 1093325324Sgordon for (unsigned i = 0; i < NewBlocks.size(); i++) 10942742Swollman Visited.erase(NewBlocks[i]); 109519878Swollman goto PredTranslationFailure; 109614343Swollman } 109719878Swollman } 109819878Swollman Worklist.append(NewBlocks.begin(), NewBlocks.end()); 10992742Swollman continue; 11002742Swollman } 110158787Sru 1102325324Sgordon // We do need to do phi translation, if we know ahead of time we can't phi 1103325324Sgordon // translate this value, don't even try. 11042742Swollman if (!Pointer.IsPotentiallyPHITranslatable()) 1105226289Sedwin goto PredTranslationFailure; 1106325324Sgordon 1107325324Sgordon // We may have added values to the cache list before this PHI translation. 1108325324Sgordon // If so, we haven't done anything to ensure that the cache remains sorted. 1109325324Sgordon // Sort it now (if needed) so that recursive invocations of 1110226289Sedwin // getNonLocalPointerDepFromBB and other routines that could reuse the cache 11112742Swollman // value will only see properly sorted cache arrays. 1112273718Sedwin if (Cache && NumSortedEntries != Cache->size()) { 11132742Swollman SortNonLocalDepInfoCache(*Cache, NumSortedEntries); 11142742Swollman NumSortedEntries = Cache->size(); 1115274559Sedwin } 11162742Swollman Cache = 0; 11172742Swollman 1118270728Spluknet PredList.clear(); 11192742Swollman for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) { 11202742Swollman BasicBlock *Pred = *PI; 1121149514Swollman PredList.push_back(std::make_pair(Pred, Pointer)); 1122149514Swollman 1123270728Spluknet // Get the PHI translated pointer in this predecessor. This can fail if 1124149514Swollman // not translatable, in which case the getAddr() returns null. 1125149514Swollman PHITransAddr &PredPointer = PredList.back().second; 1126149514Swollman PredPointer.PHITranslateValue(BB, Pred, 0); 1127149514Swollman 1128149514Swollman Value *PredPtrVal = PredPointer.getAddr(); 1129149514Swollman 1130149514Swollman // Check to see if we have already visited this pred block with another 1131149514Swollman // pointer. If so, we can't do this lookup. This failure can occur 1132270728Spluknet // with PHI translation when a critical edge exists and the PHI node in 1133273718Sedwin // the successor translates to a pointer value different than the 1134149514Swollman // pointer the block was first analyzed with. 1135149514Swollman std::pair<DenseMap<BasicBlock*,Value*>::iterator, bool> 1136158421Swollman InsertRes = Visited.insert(std::make_pair(Pred, PredPtrVal)); 1137158421Swollman 1138158421Swollman if (!InsertRes.second) { 1139158421Swollman // We found the pred; take it off the list of preds to visit. 1140158421Swollman PredList.pop_back(); 1141158421Swollman 1142149514Swollman // If the predecessor was visited with PredPtr, then we already did 1143190372Sedwin // the analysis and can ignore it. 1144190372Sedwin if (InsertRes.first->second == PredPtrVal) 1145190372Sedwin continue; 1146190372Sedwin 1147325324Sgordon // Otherwise, the block was previously analyzed with a different 1148190372Sedwin // pointer. We can't represent the result of this case, so we just 1149190372Sedwin // treat this as a phi translation failure. 1150190372Sedwin 1151325324Sgordon // Make sure to clean up the Visited map before continuing on to 1152190372Sedwin // PredTranslationFailure. 1153190372Sedwin for (unsigned i = 0, n = PredList.size(); i < n; ++i) 1154190372Sedwin Visited.erase(PredList[i].first); 1155190372Sedwin 1156190372Sedwin goto PredTranslationFailure; 1157190372Sedwin } 1158190372Sedwin } 1159190372Sedwin 1160190372Sedwin // Actually process results here; this need to be a separate loop to avoid 1161190372Sedwin // calling getNonLocalPointerDepFromBB for blocks we don't want to return 1162190372Sedwin // any results for. (getNonLocalPointerDepFromBB will modify our 1163190372Sedwin // datastructures in ways the code after the PredTranslationFailure label 1164270728Spluknet // doesn't expect.) 1165270728Spluknet for (unsigned i = 0, n = PredList.size(); i < n; ++i) { 1166270728Spluknet BasicBlock *Pred = PredList[i].first; 1167270728Spluknet PHITransAddr &PredPointer = PredList[i].second; 1168270728Spluknet Value *PredPtrVal = PredPointer.getAddr(); 1169270728Spluknet 1170190372Sedwin bool CanTranslate = true; 1171206868Sedwin // If PHI translation was unable to find an available pointer in this 1172206868Sedwin // predecessor, then we have to assume that the pointer is clobbered in 1173206868Sedwin // that predecessor. We can still do PRE of the load, which would insert 1174206868Sedwin // a computation of the pointer in this predecessor. 1175206868Sedwin if (PredPtrVal == 0) 1176206868Sedwin CanTranslate = false; 1177206868Sedwin 1178206868Sedwin // FIXME: it is entirely possible that PHI translating will end up with 1179206868Sedwin // the same value. Consider PHI translating something like: 1180206868Sedwin // X = phi [x, bb1], [y, bb2]. PHI translating for bb1 doesn't *need* 1181206868Sedwin // to recurse here, pedantically speaking. 1182206868Sedwin 1183206868Sedwin // If getNonLocalPointerDepFromBB fails here, that means the cached 1184206868Sedwin // result conflicted with the Visited list; we have to conservatively 11852742Swollman // assume it is unknown, but this also does not block PRE of the load. 118619878Swollman if (!CanTranslate || 11872742Swollman getNonLocalPointerDepFromBB(PredPointer, 118819878Swollman Loc.getWithNewPtr(PredPtrVal), 11892742Swollman isLoad, Pred, 119019878Swollman Result, Visited)) { 11912742Swollman // Add the entry to the Result list. 119219878Swollman NonLocalDepResult Entry(Pred, MemDepResult::getUnknown(), PredPtrVal); 11932742Swollman Result.push_back(Entry); 119419878Swollman 11952742Swollman // Since we had a phi translation failure, the cache for CacheKey won't 119619878Swollman // include all of the entries that we need to immediately satisfy future 11972742Swollman // queries. Mark this in NonLocalPointerDeps by setting the 11982742Swollman // BBSkipFirstBlockPair pointer to null. This requires reuse of the 119919878Swollman // cached value to do more work but not miss the phi trans failure. 12002742Swollman NonLocalPointerInfo &NLPI = NonLocalPointerDeps[CacheKey]; 120119878Swollman NLPI.Pair = BBSkipFirstBlockPair(); 12022742Swollman continue; 120319878Swollman } 120420094Swollman } 120519878Swollman 120619878Swollman // Refresh the CacheInfo/Cache pointer so that it isn't invalidated. 1207149514Swollman CacheInfo = &NonLocalPointerDeps[CacheKey]; 1208149514Swollman Cache = &CacheInfo->NonLocalDeps; 1209190372Sedwin NumSortedEntries = Cache->size(); 1210190372Sedwin 1211206868Sedwin // Since we did phi translation, the "Cache" set won't contain all of the 1212158421Swollman // results for the query. This is ok (we can still use it to accelerate 1213158421Swollman // specific block queries) but we can't do the fastpath "return all 1214158421Swollman // results from the set" Clear out the indicator for this. 12152742Swollman CacheInfo->Pair = BBSkipFirstBlockPair(); 12162742Swollman SkipFirstBlock = false; 1217273718Sedwin continue; 121819878Swollman 12192742Swollman PredTranslationFailure: 12202742Swollman // The following code is "failure"; we can't produce a sane translation 1221274559Sedwin // for the given block. It assumes that we haven't modified any of 12222742Swollman // our datastructures while processing the current block. 12232742Swollman 12242742Swollman if (Cache == 0) { 1225273718Sedwin // Refresh the CacheInfo/Cache pointer if it got invalidated. 1226 CacheInfo = &NonLocalPointerDeps[CacheKey]; 1227 Cache = &CacheInfo->NonLocalDeps; 1228 NumSortedEntries = Cache->size(); 1229 } 1230 1231 // Since we failed phi translation, the "Cache" set won't contain all of the 1232 // results for the query. This is ok (we can still use it to accelerate 1233 // specific block queries) but we can't do the fastpath "return all 1234 // results from the set". Clear out the indicator for this. 1235 CacheInfo->Pair = BBSkipFirstBlockPair(); 1236 1237 // If *nothing* works, mark the pointer as unknown. 1238 // 1239 // If this is the magic first block, return this as a clobber of the whole 1240 // incoming value. Since we can't phi translate to one of the predecessors, 1241 // we have to bail out. 1242 if (SkipFirstBlock) 1243 return true; 1244 1245 for (NonLocalDepInfo::reverse_iterator I = Cache->rbegin(); ; ++I) { 1246 assert(I != Cache->rend() && "Didn't find current block??"); 1247 if (I->getBB() != BB) 1248 continue; 1249 1250 assert(I->getResult().isNonLocal() && 1251 "Should only be here with transparent block"); 1252 I->setResult(MemDepResult::getUnknown()); 1253 Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(), 1254 Pointer.getAddr())); 1255 break; 1256 } 1257 } 1258 1259 // Okay, we're done now. If we added new values to the cache, re-sort it. 1260 SortNonLocalDepInfoCache(*Cache, NumSortedEntries); 1261 DEBUG(AssertSorted(*Cache)); 1262 return false; 1263} 1264 1265/// RemoveCachedNonLocalPointerDependencies - If P exists in 1266/// CachedNonLocalPointerInfo, remove it. 1267void MemoryDependenceAnalysis:: 1268RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P) { 1269 CachedNonLocalPointerInfo::iterator It = 1270 NonLocalPointerDeps.find(P); 1271 if (It == NonLocalPointerDeps.end()) return; 1272 1273 // Remove all of the entries in the BB->val map. This involves removing 1274 // instructions from the reverse map. 1275 NonLocalDepInfo &PInfo = It->second.NonLocalDeps; 1276 1277 for (unsigned i = 0, e = PInfo.size(); i != e; ++i) { 1278 Instruction *Target = PInfo[i].getResult().getInst(); 1279 if (Target == 0) continue; // Ignore non-local dep results. 1280 assert(Target->getParent() == PInfo[i].getBB()); 1281 1282 // Eliminating the dirty entry from 'Cache', so update the reverse info. 1283 RemoveFromReverseMap(ReverseNonLocalPtrDeps, Target, P); 1284 } 1285 1286 // Remove P from NonLocalPointerDeps (which deletes NonLocalDepInfo). 1287 NonLocalPointerDeps.erase(It); 1288} 1289 1290 1291/// invalidateCachedPointerInfo - This method is used to invalidate cached 1292/// information about the specified pointer, because it may be too 1293/// conservative in memdep. This is an optional call that can be used when 1294/// the client detects an equivalence between the pointer and some other 1295/// value and replaces the other value with ptr. This can make Ptr available 1296/// in more places that cached info does not necessarily keep. 1297void MemoryDependenceAnalysis::invalidateCachedPointerInfo(Value *Ptr) { 1298 // If Ptr isn't really a pointer, just ignore it. 1299 if (!Ptr->getType()->isPointerTy()) return; 1300 // Flush store info for the pointer. 1301 RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, false)); 1302 // Flush load info for the pointer. 1303 RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, true)); 1304} 1305 1306/// invalidateCachedPredecessors - Clear the PredIteratorCache info. 1307/// This needs to be done when the CFG changes, e.g., due to splitting 1308/// critical edges. 1309void MemoryDependenceAnalysis::invalidateCachedPredecessors() { 1310 PredCache->clear(); 1311} 1312 1313/// removeInstruction - Remove an instruction from the dependence analysis, 1314/// updating the dependence of instructions that previously depended on it. 1315/// This method attempts to keep the cache coherent using the reverse map. 1316void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) { 1317 // Walk through the Non-local dependencies, removing this one as the value 1318 // for any cached queries. 1319 NonLocalDepMapType::iterator NLDI = NonLocalDeps.find(RemInst); 1320 if (NLDI != NonLocalDeps.end()) { 1321 NonLocalDepInfo &BlockMap = NLDI->second.first; 1322 for (NonLocalDepInfo::iterator DI = BlockMap.begin(), DE = BlockMap.end(); 1323 DI != DE; ++DI) 1324 if (Instruction *Inst = DI->getResult().getInst()) 1325 RemoveFromReverseMap(ReverseNonLocalDeps, Inst, RemInst); 1326 NonLocalDeps.erase(NLDI); 1327 } 1328 1329 // If we have a cached local dependence query for this instruction, remove it. 1330 // 1331 LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst); 1332 if (LocalDepEntry != LocalDeps.end()) { 1333 // Remove us from DepInst's reverse set now that the local dep info is gone. 1334 if (Instruction *Inst = LocalDepEntry->second.getInst()) 1335 RemoveFromReverseMap(ReverseLocalDeps, Inst, RemInst); 1336 1337 // Remove this local dependency info. 1338 LocalDeps.erase(LocalDepEntry); 1339 } 1340 1341 // If we have any cached pointer dependencies on this instruction, remove 1342 // them. If the instruction has non-pointer type, then it can't be a pointer 1343 // base. 1344 1345 // Remove it from both the load info and the store info. The instruction 1346 // can't be in either of these maps if it is non-pointer. 1347 if (RemInst->getType()->isPointerTy()) { 1348 RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, false)); 1349 RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, true)); 1350 } 1351 1352 // Loop over all of the things that depend on the instruction we're removing. 1353 // 1354 SmallVector<std::pair<Instruction*, Instruction*>, 8> ReverseDepsToAdd; 1355 1356 // If we find RemInst as a clobber or Def in any of the maps for other values, 1357 // we need to replace its entry with a dirty version of the instruction after 1358 // it. If RemInst is a terminator, we use a null dirty value. 1359 // 1360 // Using a dirty version of the instruction after RemInst saves having to scan 1361 // the entire block to get to this point. 1362 MemDepResult NewDirtyVal; 1363 if (!RemInst->isTerminator()) 1364 NewDirtyVal = MemDepResult::getDirty(++BasicBlock::iterator(RemInst)); 1365 1366 ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(RemInst); 1367 if (ReverseDepIt != ReverseLocalDeps.end()) { 1368 SmallPtrSet<Instruction*, 4> &ReverseDeps = ReverseDepIt->second; 1369 // RemInst can't be the terminator if it has local stuff depending on it. 1370 assert(!ReverseDeps.empty() && !isa<TerminatorInst>(RemInst) && 1371 "Nothing can locally depend on a terminator"); 1372 1373 for (SmallPtrSet<Instruction*, 4>::iterator I = ReverseDeps.begin(), 1374 E = ReverseDeps.end(); I != E; ++I) { 1375 Instruction *InstDependingOnRemInst = *I; 1376 assert(InstDependingOnRemInst != RemInst && 1377 "Already removed our local dep info"); 1378 1379 LocalDeps[InstDependingOnRemInst] = NewDirtyVal; 1380 1381 // Make sure to remember that new things depend on NewDepInst. 1382 assert(NewDirtyVal.getInst() && "There is no way something else can have " 1383 "a local dep on this if it is a terminator!"); 1384 ReverseDepsToAdd.push_back(std::make_pair(NewDirtyVal.getInst(), 1385 InstDependingOnRemInst)); 1386 } 1387 1388 ReverseLocalDeps.erase(ReverseDepIt); 1389 1390 // Add new reverse deps after scanning the set, to avoid invalidating the 1391 // 'ReverseDeps' reference. 1392 while (!ReverseDepsToAdd.empty()) { 1393 ReverseLocalDeps[ReverseDepsToAdd.back().first] 1394 .insert(ReverseDepsToAdd.back().second); 1395 ReverseDepsToAdd.pop_back(); 1396 } 1397 } 1398 1399 ReverseDepIt = ReverseNonLocalDeps.find(RemInst); 1400 if (ReverseDepIt != ReverseNonLocalDeps.end()) { 1401 SmallPtrSet<Instruction*, 4> &Set = ReverseDepIt->second; 1402 for (SmallPtrSet<Instruction*, 4>::iterator I = Set.begin(), E = Set.end(); 1403 I != E; ++I) { 1404 assert(*I != RemInst && "Already removed NonLocalDep info for RemInst"); 1405 1406 PerInstNLInfo &INLD = NonLocalDeps[*I]; 1407 // The information is now dirty! 1408 INLD.second = true; 1409 1410 for (NonLocalDepInfo::iterator DI = INLD.first.begin(), 1411 DE = INLD.first.end(); DI != DE; ++DI) { 1412 if (DI->getResult().getInst() != RemInst) continue; 1413 1414 // Convert to a dirty entry for the subsequent instruction. 1415 DI->setResult(NewDirtyVal); 1416 1417 if (Instruction *NextI = NewDirtyVal.getInst()) 1418 ReverseDepsToAdd.push_back(std::make_pair(NextI, *I)); 1419 } 1420 } 1421 1422 ReverseNonLocalDeps.erase(ReverseDepIt); 1423 1424 // Add new reverse deps after scanning the set, to avoid invalidating 'Set' 1425 while (!ReverseDepsToAdd.empty()) { 1426 ReverseNonLocalDeps[ReverseDepsToAdd.back().first] 1427 .insert(ReverseDepsToAdd.back().second); 1428 ReverseDepsToAdd.pop_back(); 1429 } 1430 } 1431 1432 // If the instruction is in ReverseNonLocalPtrDeps then it appears as a 1433 // value in the NonLocalPointerDeps info. 1434 ReverseNonLocalPtrDepTy::iterator ReversePtrDepIt = 1435 ReverseNonLocalPtrDeps.find(RemInst); 1436 if (ReversePtrDepIt != ReverseNonLocalPtrDeps.end()) { 1437 SmallPtrSet<ValueIsLoadPair, 4> &Set = ReversePtrDepIt->second; 1438 SmallVector<std::pair<Instruction*, ValueIsLoadPair>,8> ReversePtrDepsToAdd; 1439 1440 for (SmallPtrSet<ValueIsLoadPair, 4>::iterator I = Set.begin(), 1441 E = Set.end(); I != E; ++I) { 1442 ValueIsLoadPair P = *I; 1443 assert(P.getPointer() != RemInst && 1444 "Already removed NonLocalPointerDeps info for RemInst"); 1445 1446 NonLocalDepInfo &NLPDI = NonLocalPointerDeps[P].NonLocalDeps; 1447 1448 // The cache is not valid for any specific block anymore. 1449 NonLocalPointerDeps[P].Pair = BBSkipFirstBlockPair(); 1450 1451 // Update any entries for RemInst to use the instruction after it. 1452 for (NonLocalDepInfo::iterator DI = NLPDI.begin(), DE = NLPDI.end(); 1453 DI != DE; ++DI) { 1454 if (DI->getResult().getInst() != RemInst) continue; 1455 1456 // Convert to a dirty entry for the subsequent instruction. 1457 DI->setResult(NewDirtyVal); 1458 1459 if (Instruction *NewDirtyInst = NewDirtyVal.getInst()) 1460 ReversePtrDepsToAdd.push_back(std::make_pair(NewDirtyInst, P)); 1461 } 1462 1463 // Re-sort the NonLocalDepInfo. Changing the dirty entry to its 1464 // subsequent value may invalidate the sortedness. 1465 std::sort(NLPDI.begin(), NLPDI.end()); 1466 } 1467 1468 ReverseNonLocalPtrDeps.erase(ReversePtrDepIt); 1469 1470 while (!ReversePtrDepsToAdd.empty()) { 1471 ReverseNonLocalPtrDeps[ReversePtrDepsToAdd.back().first] 1472 .insert(ReversePtrDepsToAdd.back().second); 1473 ReversePtrDepsToAdd.pop_back(); 1474 } 1475 } 1476 1477 1478 assert(!NonLocalDeps.count(RemInst) && "RemInst got reinserted?"); 1479 AA->deleteValue(RemInst); 1480 DEBUG(verifyRemoved(RemInst)); 1481} 1482/// verifyRemoved - Verify that the specified instruction does not occur 1483/// in our internal data structures. 1484void MemoryDependenceAnalysis::verifyRemoved(Instruction *D) const { 1485 for (LocalDepMapType::const_iterator I = LocalDeps.begin(), 1486 E = LocalDeps.end(); I != E; ++I) { 1487 assert(I->first != D && "Inst occurs in data structures"); 1488 assert(I->second.getInst() != D && 1489 "Inst occurs in data structures"); 1490 } 1491 1492 for (CachedNonLocalPointerInfo::const_iterator I =NonLocalPointerDeps.begin(), 1493 E = NonLocalPointerDeps.end(); I != E; ++I) { 1494 assert(I->first.getPointer() != D && "Inst occurs in NLPD map key"); 1495 const NonLocalDepInfo &Val = I->second.NonLocalDeps; 1496 for (NonLocalDepInfo::const_iterator II = Val.begin(), E = Val.end(); 1497 II != E; ++II) 1498 assert(II->getResult().getInst() != D && "Inst occurs as NLPD value"); 1499 } 1500 1501 for (NonLocalDepMapType::const_iterator I = NonLocalDeps.begin(), 1502 E = NonLocalDeps.end(); I != E; ++I) { 1503 assert(I->first != D && "Inst occurs in data structures"); 1504 const PerInstNLInfo &INLD = I->second; 1505 for (NonLocalDepInfo::const_iterator II = INLD.first.begin(), 1506 EE = INLD.first.end(); II != EE; ++II) 1507 assert(II->getResult().getInst() != D && "Inst occurs in data structures"); 1508 } 1509 1510 for (ReverseDepMapType::const_iterator I = ReverseLocalDeps.begin(), 1511 E = ReverseLocalDeps.end(); I != E; ++I) { 1512 assert(I->first != D && "Inst occurs in data structures"); 1513 for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(), 1514 EE = I->second.end(); II != EE; ++II) 1515 assert(*II != D && "Inst occurs in data structures"); 1516 } 1517 1518 for (ReverseDepMapType::const_iterator I = ReverseNonLocalDeps.begin(), 1519 E = ReverseNonLocalDeps.end(); 1520 I != E; ++I) { 1521 assert(I->first != D && "Inst occurs in data structures"); 1522 for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(), 1523 EE = I->second.end(); II != EE; ++II) 1524 assert(*II != D && "Inst occurs in data structures"); 1525 } 1526 1527 for (ReverseNonLocalPtrDepTy::const_iterator 1528 I = ReverseNonLocalPtrDeps.begin(), 1529 E = ReverseNonLocalPtrDeps.end(); I != E; ++I) { 1530 assert(I->first != D && "Inst occurs in rev NLPD map"); 1531 1532 for (SmallPtrSet<ValueIsLoadPair, 4>::const_iterator II = I->second.begin(), 1533 E = I->second.end(); II != E; ++II) 1534 assert(*II != ValueIsLoadPair(D, false) && 1535 *II != ValueIsLoadPair(D, true) && 1536 "Inst occurs in ReverseNonLocalPtrDeps map"); 1537 } 1538 1539} 1540