1 //===- Loads.cpp - Local load analysis ------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines simple local analyses for load instructions. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "llvm/Analysis/Loads.h" 14 #include "llvm/Analysis/AliasAnalysis.h" 15 #include "llvm/Analysis/AssumeBundleQueries.h" 16 #include "llvm/Analysis/CaptureTracking.h" 17 #include "llvm/Analysis/LoopInfo.h" 18 #include "llvm/Analysis/MemoryBuiltins.h" 19 #include "llvm/Analysis/MemoryLocation.h" 20 #include "llvm/Analysis/ScalarEvolution.h" 21 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 22 #include "llvm/Analysis/TargetLibraryInfo.h" 23 #include "llvm/Analysis/ValueTracking.h" 24 #include "llvm/IR/DataLayout.h" 25 #include "llvm/IR/GlobalAlias.h" 26 #include "llvm/IR/GlobalVariable.h" 27 #include "llvm/IR/IntrinsicInst.h" 28 #include "llvm/IR/LLVMContext.h" 29 #include "llvm/IR/Module.h" 30 #include "llvm/IR/Operator.h" 31 32 using namespace llvm; 33 34 static bool isAligned(const Value *Base, const APInt &Offset, Align Alignment, 35 const DataLayout &DL) { 36 Align BA = Base->getPointerAlignment(DL); 37 const APInt APAlign(Offset.getBitWidth(), Alignment.value()); 38 assert(APAlign.isPowerOf2() && "must be a power of 2!"); 39 return BA >= Alignment && !(Offset & (APAlign - 1)); 40 } 41 42 /// Test if V is always a pointer to allocated and suitably aligned memory for 43 /// a simple load or store. 44 static bool isDereferenceableAndAlignedPointer( 45 const Value *V, Align Alignment, const APInt &Size, const DataLayout &DL, 46 const Instruction *CtxI, const DominatorTree *DT, 47 const TargetLibraryInfo *TLI, SmallPtrSetImpl<const Value *> &Visited, 48 unsigned MaxDepth) { 49 assert(V->getType()->isPointerTy() && "Base must be pointer"); 50 51 // Recursion limit. 52 if (MaxDepth-- == 0) 53 return false; 54 55 // Already visited? Bail out, we've likely hit unreachable code. 56 if (!Visited.insert(V).second) 57 return false; 58 59 // Note that it is not safe to speculate into a malloc'd region because 60 // malloc may return null. 61 62 // Recurse into both hands of select. 63 if (const SelectInst *Sel = dyn_cast<SelectInst>(V)) { 64 return isDereferenceableAndAlignedPointer(Sel->getTrueValue(), Alignment, 65 Size, DL, CtxI, DT, TLI, Visited, 66 MaxDepth) && 67 isDereferenceableAndAlignedPointer(Sel->getFalseValue(), Alignment, 68 Size, DL, CtxI, DT, TLI, Visited, 69 MaxDepth); 70 } 71 72 // bitcast instructions are no-ops as far as dereferenceability is concerned. 73 if (const BitCastOperator *BC = dyn_cast<BitCastOperator>(V)) { 74 if (BC->getSrcTy()->isPointerTy()) 75 return isDereferenceableAndAlignedPointer( 76 BC->getOperand(0), Alignment, Size, DL, CtxI, DT, TLI, 77 Visited, MaxDepth); 78 } 79 80 bool CheckForNonNull, CheckForFreed; 81 APInt KnownDerefBytes(Size.getBitWidth(), 82 V->getPointerDereferenceableBytes(DL, CheckForNonNull, 83 CheckForFreed)); 84 if (KnownDerefBytes.getBoolValue() && KnownDerefBytes.uge(Size) && 85 !CheckForFreed) 86 if (!CheckForNonNull || isKnownNonZero(V, DL, 0, nullptr, CtxI, DT)) { 87 // As we recursed through GEPs to get here, we've incrementally checked 88 // that each step advanced by a multiple of the alignment. If our base is 89 // properly aligned, then the original offset accessed must also be. 90 Type *Ty = V->getType(); 91 assert(Ty->isSized() && "must be sized"); 92 APInt Offset(DL.getTypeStoreSizeInBits(Ty), 0); 93 return isAligned(V, Offset, Alignment, DL); 94 } 95 96 if (CtxI) { 97 /// Look through assumes to see if both dereferencability and alignment can 98 /// be provent by an assume 99 RetainedKnowledge AlignRK; 100 RetainedKnowledge DerefRK; 101 if (getKnowledgeForValue( 102 V, {Attribute::Dereferenceable, Attribute::Alignment}, nullptr, 103 [&](RetainedKnowledge RK, Instruction *Assume, auto) { 104 if (!isValidAssumeForContext(Assume, CtxI)) 105 return false; 106 if (RK.AttrKind == Attribute::Alignment) 107 AlignRK = std::max(AlignRK, RK); 108 if (RK.AttrKind == Attribute::Dereferenceable) 109 DerefRK = std::max(DerefRK, RK); 110 if (AlignRK && DerefRK && AlignRK.ArgValue >= Alignment.value() && 111 DerefRK.ArgValue >= Size.getZExtValue()) 112 return true; // We have found what we needed so we stop looking 113 return false; // Other assumes may have better information. so 114 // keep looking 115 })) 116 return true; 117 } 118 /// TODO refactor this function to be able to search independently for 119 /// Dereferencability and Alignment requirements. 120 121 // For GEPs, determine if the indexing lands within the allocated object. 122 if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 123 const Value *Base = GEP->getPointerOperand(); 124 125 APInt Offset(DL.getIndexTypeSizeInBits(GEP->getType()), 0); 126 if (!GEP->accumulateConstantOffset(DL, Offset) || Offset.isNegative() || 127 !Offset.urem(APInt(Offset.getBitWidth(), Alignment.value())) 128 .isMinValue()) 129 return false; 130 131 // If the base pointer is dereferenceable for Offset+Size bytes, then the 132 // GEP (== Base + Offset) is dereferenceable for Size bytes. If the base 133 // pointer is aligned to Align bytes, and the Offset is divisible by Align 134 // then the GEP (== Base + Offset == k_0 * Align + k_1 * Align) is also 135 // aligned to Align bytes. 136 137 // Offset and Size may have different bit widths if we have visited an 138 // addrspacecast, so we can't do arithmetic directly on the APInt values. 139 return isDereferenceableAndAlignedPointer( 140 Base, Alignment, Offset + Size.sextOrTrunc(Offset.getBitWidth()), DL, 141 CtxI, DT, TLI, Visited, MaxDepth); 142 } 143 144 // For gc.relocate, look through relocations 145 if (const GCRelocateInst *RelocateInst = dyn_cast<GCRelocateInst>(V)) 146 return isDereferenceableAndAlignedPointer(RelocateInst->getDerivedPtr(), 147 Alignment, Size, DL, CtxI, DT, 148 TLI, Visited, MaxDepth); 149 150 if (const AddrSpaceCastOperator *ASC = dyn_cast<AddrSpaceCastOperator>(V)) 151 return isDereferenceableAndAlignedPointer(ASC->getOperand(0), Alignment, 152 Size, DL, CtxI, DT, TLI, 153 Visited, MaxDepth); 154 155 if (const auto *Call = dyn_cast<CallBase>(V)) { 156 if (auto *RP = getArgumentAliasingToReturnedPointer(Call, true)) 157 return isDereferenceableAndAlignedPointer(RP, Alignment, Size, DL, CtxI, 158 DT, TLI, Visited, MaxDepth); 159 160 // If we have a call we can't recurse through, check to see if this is an 161 // allocation function for which we can establish an minimum object size. 162 // Such a minimum object size is analogous to a deref_or_null attribute in 163 // that we still need to prove the result non-null at point of use. 164 // NOTE: We can only use the object size as a base fact as we a) need to 165 // prove alignment too, and b) don't want the compile time impact of a 166 // separate recursive walk. 167 ObjectSizeOpts Opts; 168 // TODO: It may be okay to round to align, but that would imply that 169 // accessing slightly out of bounds was legal, and we're currently 170 // inconsistent about that. For the moment, be conservative. 171 Opts.RoundToAlign = false; 172 Opts.NullIsUnknownSize = true; 173 uint64_t ObjSize; 174 if (getObjectSize(V, ObjSize, DL, TLI, Opts)) { 175 APInt KnownDerefBytes(Size.getBitWidth(), ObjSize); 176 if (KnownDerefBytes.getBoolValue() && KnownDerefBytes.uge(Size) && 177 isKnownNonZero(V, DL, 0, nullptr, CtxI, DT) && !V->canBeFreed()) { 178 // As we recursed through GEPs to get here, we've incrementally 179 // checked that each step advanced by a multiple of the alignment. If 180 // our base is properly aligned, then the original offset accessed 181 // must also be. 182 Type *Ty = V->getType(); 183 assert(Ty->isSized() && "must be sized"); 184 APInt Offset(DL.getTypeStoreSizeInBits(Ty), 0); 185 return isAligned(V, Offset, Alignment, DL); 186 } 187 } 188 } 189 190 // If we don't know, assume the worst. 191 return false; 192 } 193 194 bool llvm::isDereferenceableAndAlignedPointer(const Value *V, Align Alignment, 195 const APInt &Size, 196 const DataLayout &DL, 197 const Instruction *CtxI, 198 const DominatorTree *DT, 199 const TargetLibraryInfo *TLI) { 200 // Note: At the moment, Size can be zero. This ends up being interpreted as 201 // a query of whether [Base, V] is dereferenceable and V is aligned (since 202 // that's what the implementation happened to do). It's unclear if this is 203 // the desired semantic, but at least SelectionDAG does exercise this case. 204 205 SmallPtrSet<const Value *, 32> Visited; 206 return ::isDereferenceableAndAlignedPointer(V, Alignment, Size, DL, CtxI, DT, 207 TLI, Visited, 16); 208 } 209 210 bool llvm::isDereferenceableAndAlignedPointer(const Value *V, Type *Ty, 211 Align Alignment, 212 const DataLayout &DL, 213 const Instruction *CtxI, 214 const DominatorTree *DT, 215 const TargetLibraryInfo *TLI) { 216 // For unsized types or scalable vectors we don't know exactly how many bytes 217 // are dereferenced, so bail out. 218 if (!Ty->isSized() || isa<ScalableVectorType>(Ty)) 219 return false; 220 221 // When dereferenceability information is provided by a dereferenceable 222 // attribute, we know exactly how many bytes are dereferenceable. If we can 223 // determine the exact offset to the attributed variable, we can use that 224 // information here. 225 226 APInt AccessSize(DL.getPointerTypeSizeInBits(V->getType()), 227 DL.getTypeStoreSize(Ty)); 228 return isDereferenceableAndAlignedPointer(V, Alignment, AccessSize, DL, CtxI, 229 DT, TLI); 230 } 231 232 bool llvm::isDereferenceablePointer(const Value *V, Type *Ty, 233 const DataLayout &DL, 234 const Instruction *CtxI, 235 const DominatorTree *DT, 236 const TargetLibraryInfo *TLI) { 237 return isDereferenceableAndAlignedPointer(V, Ty, Align(1), DL, CtxI, DT, TLI); 238 } 239 240 /// Test if A and B will obviously have the same value. 241 /// 242 /// This includes recognizing that %t0 and %t1 will have the same 243 /// value in code like this: 244 /// \code 245 /// %t0 = getelementptr \@a, 0, 3 246 /// store i32 0, i32* %t0 247 /// %t1 = getelementptr \@a, 0, 3 248 /// %t2 = load i32* %t1 249 /// \endcode 250 /// 251 static bool AreEquivalentAddressValues(const Value *A, const Value *B) { 252 // Test if the values are trivially equivalent. 253 if (A == B) 254 return true; 255 256 // Test if the values come from identical arithmetic instructions. 257 // Use isIdenticalToWhenDefined instead of isIdenticalTo because 258 // this function is only used when one address use dominates the 259 // other, which means that they'll always either have the same 260 // value or one of them will have an undefined value. 261 if (isa<BinaryOperator>(A) || isa<CastInst>(A) || isa<PHINode>(A) || 262 isa<GetElementPtrInst>(A)) 263 if (const Instruction *BI = dyn_cast<Instruction>(B)) 264 if (cast<Instruction>(A)->isIdenticalToWhenDefined(BI)) 265 return true; 266 267 // Otherwise they may not be equivalent. 268 return false; 269 } 270 271 bool llvm::isDereferenceableAndAlignedInLoop(LoadInst *LI, Loop *L, 272 ScalarEvolution &SE, 273 DominatorTree &DT) { 274 auto &DL = LI->getModule()->getDataLayout(); 275 Value *Ptr = LI->getPointerOperand(); 276 277 APInt EltSize(DL.getIndexTypeSizeInBits(Ptr->getType()), 278 DL.getTypeStoreSize(LI->getType()).getFixedSize()); 279 const Align Alignment = LI->getAlign(); 280 281 Instruction *HeaderFirstNonPHI = L->getHeader()->getFirstNonPHI(); 282 283 // If given a uniform (i.e. non-varying) address, see if we can prove the 284 // access is safe within the loop w/o needing predication. 285 if (L->isLoopInvariant(Ptr)) 286 return isDereferenceableAndAlignedPointer(Ptr, Alignment, EltSize, DL, 287 HeaderFirstNonPHI, &DT); 288 289 // Otherwise, check to see if we have a repeating access pattern where we can 290 // prove that all accesses are well aligned and dereferenceable. 291 auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(Ptr)); 292 if (!AddRec || AddRec->getLoop() != L || !AddRec->isAffine()) 293 return false; 294 auto* Step = dyn_cast<SCEVConstant>(AddRec->getStepRecurrence(SE)); 295 if (!Step) 296 return false; 297 // TODO: generalize to access patterns which have gaps 298 if (Step->getAPInt() != EltSize) 299 return false; 300 301 auto TC = SE.getSmallConstantMaxTripCount(L); 302 if (!TC) 303 return false; 304 305 const APInt AccessSize = TC * EltSize; 306 307 auto *StartS = dyn_cast<SCEVUnknown>(AddRec->getStart()); 308 if (!StartS) 309 return false; 310 assert(SE.isLoopInvariant(StartS, L) && "implied by addrec definition"); 311 Value *Base = StartS->getValue(); 312 313 // For the moment, restrict ourselves to the case where the access size is a 314 // multiple of the requested alignment and the base is aligned. 315 // TODO: generalize if a case found which warrants 316 if (EltSize.urem(Alignment.value()) != 0) 317 return false; 318 return isDereferenceableAndAlignedPointer(Base, Alignment, AccessSize, DL, 319 HeaderFirstNonPHI, &DT); 320 } 321 322 /// Check if executing a load of this pointer value cannot trap. 323 /// 324 /// If DT and ScanFrom are specified this method performs context-sensitive 325 /// analysis and returns true if it is safe to load immediately before ScanFrom. 326 /// 327 /// If it is not obviously safe to load from the specified pointer, we do 328 /// a quick local scan of the basic block containing \c ScanFrom, to determine 329 /// if the address is already accessed. 330 /// 331 /// This uses the pointee type to determine how many bytes need to be safe to 332 /// load from the pointer. 333 bool llvm::isSafeToLoadUnconditionally(Value *V, Align Alignment, APInt &Size, 334 const DataLayout &DL, 335 Instruction *ScanFrom, 336 const DominatorTree *DT, 337 const TargetLibraryInfo *TLI) { 338 // If DT is not specified we can't make context-sensitive query 339 const Instruction* CtxI = DT ? ScanFrom : nullptr; 340 if (isDereferenceableAndAlignedPointer(V, Alignment, Size, DL, CtxI, DT, TLI)) 341 return true; 342 343 if (!ScanFrom) 344 return false; 345 346 if (Size.getBitWidth() > 64) 347 return false; 348 const uint64_t LoadSize = Size.getZExtValue(); 349 350 // Otherwise, be a little bit aggressive by scanning the local block where we 351 // want to check to see if the pointer is already being loaded or stored 352 // from/to. If so, the previous load or store would have already trapped, 353 // so there is no harm doing an extra load (also, CSE will later eliminate 354 // the load entirely). 355 BasicBlock::iterator BBI = ScanFrom->getIterator(), 356 E = ScanFrom->getParent()->begin(); 357 358 // We can at least always strip pointer casts even though we can't use the 359 // base here. 360 V = V->stripPointerCasts(); 361 362 while (BBI != E) { 363 --BBI; 364 365 // If we see a free or a call which may write to memory (i.e. which might do 366 // a free) the pointer could be marked invalid. 367 if (isa<CallInst>(BBI) && BBI->mayWriteToMemory() && 368 !isa<DbgInfoIntrinsic>(BBI)) 369 return false; 370 371 Value *AccessedPtr; 372 Type *AccessedTy; 373 Align AccessedAlign; 374 if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) { 375 // Ignore volatile loads. The execution of a volatile load cannot 376 // be used to prove an address is backed by regular memory; it can, 377 // for example, point to an MMIO register. 378 if (LI->isVolatile()) 379 continue; 380 AccessedPtr = LI->getPointerOperand(); 381 AccessedTy = LI->getType(); 382 AccessedAlign = LI->getAlign(); 383 } else if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) { 384 // Ignore volatile stores (see comment for loads). 385 if (SI->isVolatile()) 386 continue; 387 AccessedPtr = SI->getPointerOperand(); 388 AccessedTy = SI->getValueOperand()->getType(); 389 AccessedAlign = SI->getAlign(); 390 } else 391 continue; 392 393 if (AccessedAlign < Alignment) 394 continue; 395 396 // Handle trivial cases. 397 if (AccessedPtr == V && 398 LoadSize <= DL.getTypeStoreSize(AccessedTy)) 399 return true; 400 401 if (AreEquivalentAddressValues(AccessedPtr->stripPointerCasts(), V) && 402 LoadSize <= DL.getTypeStoreSize(AccessedTy)) 403 return true; 404 } 405 return false; 406 } 407 408 bool llvm::isSafeToLoadUnconditionally(Value *V, Type *Ty, Align Alignment, 409 const DataLayout &DL, 410 Instruction *ScanFrom, 411 const DominatorTree *DT, 412 const TargetLibraryInfo *TLI) { 413 APInt Size(DL.getIndexTypeSizeInBits(V->getType()), DL.getTypeStoreSize(Ty)); 414 return isSafeToLoadUnconditionally(V, Alignment, Size, DL, ScanFrom, DT, TLI); 415 } 416 417 /// DefMaxInstsToScan - the default number of maximum instructions 418 /// to scan in the block, used by FindAvailableLoadedValue(). 419 /// FindAvailableLoadedValue() was introduced in r60148, to improve jump 420 /// threading in part by eliminating partially redundant loads. 421 /// At that point, the value of MaxInstsToScan was already set to '6' 422 /// without documented explanation. 423 cl::opt<unsigned> 424 llvm::DefMaxInstsToScan("available-load-scan-limit", cl::init(6), cl::Hidden, 425 cl::desc("Use this to specify the default maximum number of instructions " 426 "to scan backward from a given instruction, when searching for " 427 "available loaded value")); 428 429 Value *llvm::FindAvailableLoadedValue(LoadInst *Load, 430 BasicBlock *ScanBB, 431 BasicBlock::iterator &ScanFrom, 432 unsigned MaxInstsToScan, 433 AAResults *AA, bool *IsLoad, 434 unsigned *NumScanedInst) { 435 // Don't CSE load that is volatile or anything stronger than unordered. 436 if (!Load->isUnordered()) 437 return nullptr; 438 439 MemoryLocation Loc = MemoryLocation::get(Load); 440 return findAvailablePtrLoadStore(Loc, Load->getType(), Load->isAtomic(), 441 ScanBB, ScanFrom, MaxInstsToScan, AA, IsLoad, 442 NumScanedInst); 443 } 444 445 // Check if the load and the store have the same base, constant offsets and 446 // non-overlapping access ranges. 447 static bool areNonOverlapSameBaseLoadAndStore(const Value *LoadPtr, 448 Type *LoadTy, 449 const Value *StorePtr, 450 Type *StoreTy, 451 const DataLayout &DL) { 452 APInt LoadOffset(DL.getIndexTypeSizeInBits(LoadPtr->getType()), 0); 453 APInt StoreOffset(DL.getIndexTypeSizeInBits(StorePtr->getType()), 0); 454 const Value *LoadBase = LoadPtr->stripAndAccumulateConstantOffsets( 455 DL, LoadOffset, /* AllowNonInbounds */ false); 456 const Value *StoreBase = StorePtr->stripAndAccumulateConstantOffsets( 457 DL, StoreOffset, /* AllowNonInbounds */ false); 458 if (LoadBase != StoreBase) 459 return false; 460 auto LoadAccessSize = LocationSize::precise(DL.getTypeStoreSize(LoadTy)); 461 auto StoreAccessSize = LocationSize::precise(DL.getTypeStoreSize(StoreTy)); 462 ConstantRange LoadRange(LoadOffset, 463 LoadOffset + LoadAccessSize.toRaw()); 464 ConstantRange StoreRange(StoreOffset, 465 StoreOffset + StoreAccessSize.toRaw()); 466 return LoadRange.intersectWith(StoreRange).isEmptySet(); 467 } 468 469 static Value *getAvailableLoadStore(Instruction *Inst, const Value *Ptr, 470 Type *AccessTy, bool AtLeastAtomic, 471 const DataLayout &DL, bool *IsLoadCSE) { 472 // If this is a load of Ptr, the loaded value is available. 473 // (This is true even if the load is volatile or atomic, although 474 // those cases are unlikely.) 475 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) { 476 // We can value forward from an atomic to a non-atomic, but not the 477 // other way around. 478 if (LI->isAtomic() < AtLeastAtomic) 479 return nullptr; 480 481 Value *LoadPtr = LI->getPointerOperand()->stripPointerCasts(); 482 if (!AreEquivalentAddressValues(LoadPtr, Ptr)) 483 return nullptr; 484 485 if (CastInst::isBitOrNoopPointerCastable(LI->getType(), AccessTy, DL)) { 486 if (IsLoadCSE) 487 *IsLoadCSE = true; 488 return LI; 489 } 490 } 491 492 // If this is a store through Ptr, the value is available! 493 // (This is true even if the store is volatile or atomic, although 494 // those cases are unlikely.) 495 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 496 // We can value forward from an atomic to a non-atomic, but not the 497 // other way around. 498 if (SI->isAtomic() < AtLeastAtomic) 499 return nullptr; 500 501 Value *StorePtr = SI->getPointerOperand()->stripPointerCasts(); 502 if (!AreEquivalentAddressValues(StorePtr, Ptr)) 503 return nullptr; 504 505 if (IsLoadCSE) 506 *IsLoadCSE = false; 507 508 Value *Val = SI->getValueOperand(); 509 if (CastInst::isBitOrNoopPointerCastable(Val->getType(), AccessTy, DL)) 510 return Val; 511 512 TypeSize StoreSize = DL.getTypeStoreSize(Val->getType()); 513 TypeSize LoadSize = DL.getTypeStoreSize(AccessTy); 514 if (TypeSize::isKnownLE(LoadSize, StoreSize)) 515 if (auto *C = dyn_cast<Constant>(Val)) 516 return ConstantFoldLoadFromConst(C, AccessTy, DL); 517 } 518 519 return nullptr; 520 } 521 522 Value *llvm::findAvailablePtrLoadStore( 523 const MemoryLocation &Loc, Type *AccessTy, bool AtLeastAtomic, 524 BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan, 525 AAResults *AA, bool *IsLoadCSE, unsigned *NumScanedInst) { 526 if (MaxInstsToScan == 0) 527 MaxInstsToScan = ~0U; 528 529 const DataLayout &DL = ScanBB->getModule()->getDataLayout(); 530 const Value *StrippedPtr = Loc.Ptr->stripPointerCasts(); 531 532 while (ScanFrom != ScanBB->begin()) { 533 // We must ignore debug info directives when counting (otherwise they 534 // would affect codegen). 535 Instruction *Inst = &*--ScanFrom; 536 if (Inst->isDebugOrPseudoInst()) 537 continue; 538 539 // Restore ScanFrom to expected value in case next test succeeds 540 ScanFrom++; 541 542 if (NumScanedInst) 543 ++(*NumScanedInst); 544 545 // Don't scan huge blocks. 546 if (MaxInstsToScan-- == 0) 547 return nullptr; 548 549 --ScanFrom; 550 551 if (Value *Available = getAvailableLoadStore(Inst, StrippedPtr, AccessTy, 552 AtLeastAtomic, DL, IsLoadCSE)) 553 return Available; 554 555 // Try to get the store size for the type. 556 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 557 Value *StorePtr = SI->getPointerOperand()->stripPointerCasts(); 558 559 // If both StrippedPtr and StorePtr reach all the way to an alloca or 560 // global and they are different, ignore the store. This is a trivial form 561 // of alias analysis that is important for reg2mem'd code. 562 if ((isa<AllocaInst>(StrippedPtr) || isa<GlobalVariable>(StrippedPtr)) && 563 (isa<AllocaInst>(StorePtr) || isa<GlobalVariable>(StorePtr)) && 564 StrippedPtr != StorePtr) 565 continue; 566 567 if (!AA) { 568 // When AA isn't available, but if the load and the store have the same 569 // base, constant offsets and non-overlapping access ranges, ignore the 570 // store. This is a simple form of alias analysis that is used by the 571 // inliner. FIXME: use BasicAA if possible. 572 if (areNonOverlapSameBaseLoadAndStore( 573 Loc.Ptr, AccessTy, SI->getPointerOperand(), 574 SI->getValueOperand()->getType(), DL)) 575 continue; 576 } else { 577 // If we have alias analysis and it says the store won't modify the 578 // loaded value, ignore the store. 579 if (!isModSet(AA->getModRefInfo(SI, Loc))) 580 continue; 581 } 582 583 // Otherwise the store that may or may not alias the pointer, bail out. 584 ++ScanFrom; 585 return nullptr; 586 } 587 588 // If this is some other instruction that may clobber Ptr, bail out. 589 if (Inst->mayWriteToMemory()) { 590 // If alias analysis claims that it really won't modify the load, 591 // ignore it. 592 if (AA && !isModSet(AA->getModRefInfo(Inst, Loc))) 593 continue; 594 595 // May modify the pointer, bail out. 596 ++ScanFrom; 597 return nullptr; 598 } 599 } 600 601 // Got to the start of the block, we didn't find it, but are done for this 602 // block. 603 return nullptr; 604 } 605 606 Value *llvm::FindAvailableLoadedValue(LoadInst *Load, AAResults &AA, 607 bool *IsLoadCSE, 608 unsigned MaxInstsToScan) { 609 const DataLayout &DL = Load->getModule()->getDataLayout(); 610 Value *StrippedPtr = Load->getPointerOperand()->stripPointerCasts(); 611 BasicBlock *ScanBB = Load->getParent(); 612 Type *AccessTy = Load->getType(); 613 bool AtLeastAtomic = Load->isAtomic(); 614 615 if (!Load->isUnordered()) 616 return nullptr; 617 618 // Try to find an available value first, and delay expensive alias analysis 619 // queries until later. 620 Value *Available = nullptr;; 621 SmallVector<Instruction *> MustNotAliasInsts; 622 for (Instruction &Inst : make_range(++Load->getReverseIterator(), 623 ScanBB->rend())) { 624 if (Inst.isDebugOrPseudoInst()) 625 continue; 626 627 if (MaxInstsToScan-- == 0) 628 return nullptr; 629 630 Available = getAvailableLoadStore(&Inst, StrippedPtr, AccessTy, 631 AtLeastAtomic, DL, IsLoadCSE); 632 if (Available) 633 break; 634 635 if (Inst.mayWriteToMemory()) 636 MustNotAliasInsts.push_back(&Inst); 637 } 638 639 // If we found an available value, ensure that the instructions in between 640 // did not modify the memory location. 641 if (Available) { 642 MemoryLocation Loc = MemoryLocation::get(Load); 643 for (Instruction *Inst : MustNotAliasInsts) 644 if (isModSet(AA.getModRefInfo(Inst, Loc))) 645 return nullptr; 646 } 647 648 return Available; 649 } 650 651 bool llvm::canReplacePointersIfEqual(Value *A, Value *B, const DataLayout &DL, 652 Instruction *CtxI) { 653 Type *Ty = A->getType(); 654 assert(Ty == B->getType() && Ty->isPointerTy() && 655 "values must have matching pointer types"); 656 657 // NOTE: The checks in the function are incomplete and currently miss illegal 658 // cases! The current implementation is a starting point and the 659 // implementation should be made stricter over time. 660 if (auto *C = dyn_cast<Constant>(B)) { 661 // Do not allow replacing a pointer with a constant pointer, unless it is 662 // either null or at least one byte is dereferenceable. 663 APInt OneByte(DL.getPointerTypeSizeInBits(Ty), 1); 664 return C->isNullValue() || 665 isDereferenceableAndAlignedPointer(B, Align(1), OneByte, DL, CtxI); 666 } 667 668 return true; 669 } 670