949 lines · cpp
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-exception6//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/LoopAccessAnalysis.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/ValueTracking.h"23#include "llvm/IR/DataLayout.h"24#include "llvm/IR/GetElementPtrTypeIterator.h"25#include "llvm/IR/IntrinsicInst.h"26#include "llvm/IR/Operator.h"27 28using namespace llvm;29 30static bool isAligned(const Value *Base, Align Alignment,31 const DataLayout &DL) {32 return Base->getPointerAlignment(DL) >= Alignment;33}34 35static bool isDereferenceableAndAlignedPointerViaAssumption(36 const Value *Ptr, Align Alignment,37 function_ref<bool(const RetainedKnowledge &RK)> CheckSize,38 const DataLayout &DL, const Instruction *CtxI, AssumptionCache *AC,39 const DominatorTree *DT) {40 if (!CtxI)41 return false;42 /// Look through assumes to see if both dereferencability and alignment can43 /// be proven by an assume if needed.44 RetainedKnowledge AlignRK;45 RetainedKnowledge DerefRK;46 bool PtrCanBeFreed = Ptr->canBeFreed();47 bool IsAligned = Ptr->getPointerAlignment(DL) >= Alignment;48 return getKnowledgeForValue(49 Ptr, {Attribute::Dereferenceable, Attribute::Alignment}, *AC,50 [&](RetainedKnowledge RK, Instruction *Assume, auto) {51 if (!isValidAssumeForContext(Assume, CtxI, DT))52 return false;53 if (RK.AttrKind == Attribute::Alignment)54 AlignRK = std::max(AlignRK, RK);55 56 // Dereferenceable information from assumptions is only valid if the57 // value cannot be freed between the assumption and use.58 if ((!PtrCanBeFreed || willNotFreeBetween(Assume, CtxI)) &&59 RK.AttrKind == Attribute::Dereferenceable)60 DerefRK = std::max(DerefRK, RK);61 IsAligned |= AlignRK && AlignRK.ArgValue >= Alignment.value();62 if (IsAligned && DerefRK && CheckSize(DerefRK))63 return true; // We have found what we needed so we stop looking64 return false; // Other assumes may have better information. so65 // keep looking66 });67}68 69/// Test if V is always a pointer to allocated and suitably aligned memory for70/// a simple load or store.71static bool isDereferenceableAndAlignedPointer(72 const Value *V, Align Alignment, const APInt &Size, const DataLayout &DL,73 const Instruction *CtxI, AssumptionCache *AC, const DominatorTree *DT,74 const TargetLibraryInfo *TLI, SmallPtrSetImpl<const Value *> &Visited,75 unsigned MaxDepth) {76 assert(V->getType()->isPointerTy() && "Base must be pointer");77 78 // Recursion limit.79 if (MaxDepth-- == 0)80 return false;81 82 // Already visited? Bail out, we've likely hit unreachable code.83 if (!Visited.insert(V).second)84 return false;85 86 // Note that it is not safe to speculate into a malloc'd region because87 // malloc may return null.88 89 // For GEPs, determine if the indexing lands within the allocated object.90 if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {91 const Value *Base = GEP->getPointerOperand();92 93 APInt Offset(DL.getIndexTypeSizeInBits(GEP->getType()), 0);94 if (!GEP->accumulateConstantOffset(DL, Offset) || Offset.isNegative() ||95 !Offset.urem(APInt(Offset.getBitWidth(), Alignment.value()))96 .isMinValue())97 return false;98 99 // If the base pointer is dereferenceable for Offset+Size bytes, then the100 // GEP (== Base + Offset) is dereferenceable for Size bytes. If the base101 // pointer is aligned to Align bytes, and the Offset is divisible by Align102 // then the GEP (== Base + Offset == k_0 * Align + k_1 * Align) is also103 // aligned to Align bytes.104 105 // Offset and Size may have different bit widths if we have visited an106 // addrspacecast, so we can't do arithmetic directly on the APInt values.107 return isDereferenceableAndAlignedPointer(108 Base, Alignment, Offset + Size.sextOrTrunc(Offset.getBitWidth()), DL,109 CtxI, AC, DT, TLI, Visited, MaxDepth);110 }111 112 // bitcast instructions are no-ops as far as dereferenceability is concerned.113 if (const BitCastOperator *BC = dyn_cast<BitCastOperator>(V)) {114 if (BC->getSrcTy()->isPointerTy())115 return isDereferenceableAndAlignedPointer(116 BC->getOperand(0), Alignment, Size, DL, CtxI, AC, DT, TLI,117 Visited, MaxDepth);118 }119 120 // Recurse into both hands of select.121 if (const SelectInst *Sel = dyn_cast<SelectInst>(V)) {122 return isDereferenceableAndAlignedPointer(Sel->getTrueValue(), Alignment,123 Size, DL, CtxI, AC, DT, TLI,124 Visited, MaxDepth) &&125 isDereferenceableAndAlignedPointer(Sel->getFalseValue(), Alignment,126 Size, DL, CtxI, AC, DT, TLI,127 Visited, MaxDepth);128 }129 130 auto IsKnownDeref = [&]() {131 bool CheckForNonNull, CheckForFreed;132 if (!Size.ule(V->getPointerDereferenceableBytes(DL, CheckForNonNull,133 CheckForFreed)) ||134 CheckForFreed)135 return false;136 if (CheckForNonNull &&137 !isKnownNonZero(V, SimplifyQuery(DL, DT, AC, CtxI)))138 return false;139 // When using something like !dereferenceable on a load, the140 // dereferenceability may only be valid on a specific control-flow path.141 // If the instruction doesn't dominate the context instruction, we're142 // asking about dereferenceability under the assumption that the143 // instruction has been speculated to the point of the context instruction,144 // in which case we don't know if the dereferenceability info still holds.145 // We don't bother handling allocas here, as they aren't speculatable146 // anyway.147 auto *I = dyn_cast<Instruction>(V);148 if (I && !isa<AllocaInst>(I))149 return CtxI && isValidAssumeForContext(I, CtxI, DT);150 return true;151 };152 if (IsKnownDeref()) {153 // As we recursed through GEPs to get here, we've incrementally checked154 // that each step advanced by a multiple of the alignment. If our base is155 // properly aligned, then the original offset accessed must also be.156 return isAligned(V, Alignment, DL);157 }158 159 /// TODO refactor this function to be able to search independently for160 /// Dereferencability and Alignment requirements.161 162 163 if (const auto *Call = dyn_cast<CallBase>(V)) {164 if (auto *RP = getArgumentAliasingToReturnedPointer(Call, true))165 return isDereferenceableAndAlignedPointer(RP, Alignment, Size, DL, CtxI,166 AC, DT, TLI, Visited, MaxDepth);167 168 // If we have a call we can't recurse through, check to see if this is an169 // allocation function for which we can establish an minimum object size.170 // Such a minimum object size is analogous to a deref_or_null attribute in171 // that we still need to prove the result non-null at point of use.172 // NOTE: We can only use the object size as a base fact as we a) need to173 // prove alignment too, and b) don't want the compile time impact of a174 // separate recursive walk.175 ObjectSizeOpts Opts;176 // TODO: It may be okay to round to align, but that would imply that177 // accessing slightly out of bounds was legal, and we're currently178 // inconsistent about that. For the moment, be conservative.179 Opts.RoundToAlign = false;180 Opts.NullIsUnknownSize = true;181 uint64_t ObjSize;182 if (getObjectSize(V, ObjSize, DL, TLI, Opts)) {183 APInt KnownDerefBytes(Size.getBitWidth(), ObjSize);184 if (KnownDerefBytes.getBoolValue() && KnownDerefBytes.uge(Size) &&185 isKnownNonZero(V, SimplifyQuery(DL, DT, AC, CtxI)) &&186 !V->canBeFreed()) {187 // As we recursed through GEPs to get here, we've incrementally188 // checked that each step advanced by a multiple of the alignment. If189 // our base is properly aligned, then the original offset accessed190 // must also be.191 return isAligned(V, Alignment, DL);192 }193 }194 }195 196 // For gc.relocate, look through relocations197 if (const GCRelocateInst *RelocateInst = dyn_cast<GCRelocateInst>(V))198 return isDereferenceableAndAlignedPointer(RelocateInst->getDerivedPtr(),199 Alignment, Size, DL, CtxI, AC, DT,200 TLI, Visited, MaxDepth);201 202 if (const AddrSpaceCastOperator *ASC = dyn_cast<AddrSpaceCastOperator>(V))203 return isDereferenceableAndAlignedPointer(ASC->getOperand(0), Alignment,204 Size, DL, CtxI, AC, DT, TLI,205 Visited, MaxDepth);206 207 return AC && isDereferenceableAndAlignedPointerViaAssumption(208 V, Alignment,209 [Size](const RetainedKnowledge &RK) {210 return RK.ArgValue >= Size.getZExtValue();211 },212 DL, CtxI, AC, DT);213}214 215bool llvm::isDereferenceableAndAlignedPointer(216 const Value *V, Align Alignment, const APInt &Size, const DataLayout &DL,217 const Instruction *CtxI, AssumptionCache *AC, const DominatorTree *DT,218 const TargetLibraryInfo *TLI) {219 // Note: At the moment, Size can be zero. This ends up being interpreted as220 // a query of whether [Base, V] is dereferenceable and V is aligned (since221 // that's what the implementation happened to do). It's unclear if this is222 // the desired semantic, but at least SelectionDAG does exercise this case.223 224 SmallPtrSet<const Value *, 32> Visited;225 return ::isDereferenceableAndAlignedPointer(V, Alignment, Size, DL, CtxI, AC,226 DT, TLI, Visited, 16);227}228 229bool llvm::isDereferenceableAndAlignedPointer(230 const Value *V, Type *Ty, Align Alignment, const DataLayout &DL,231 const Instruction *CtxI, AssumptionCache *AC, const DominatorTree *DT,232 const TargetLibraryInfo *TLI) {233 // For unsized types or scalable vectors we don't know exactly how many bytes234 // are dereferenced, so bail out.235 if (!Ty->isSized() || Ty->isScalableTy())236 return false;237 238 // When dereferenceability information is provided by a dereferenceable239 // attribute, we know exactly how many bytes are dereferenceable. If we can240 // determine the exact offset to the attributed variable, we can use that241 // information here.242 243 APInt AccessSize(DL.getPointerTypeSizeInBits(V->getType()),244 DL.getTypeStoreSize(Ty));245 return isDereferenceableAndAlignedPointer(V, Alignment, AccessSize, DL, CtxI,246 AC, DT, TLI);247}248 249bool llvm::isDereferenceablePointer(const Value *V, Type *Ty,250 const DataLayout &DL,251 const Instruction *CtxI,252 AssumptionCache *AC,253 const DominatorTree *DT,254 const TargetLibraryInfo *TLI) {255 return isDereferenceableAndAlignedPointer(V, Ty, Align(1), DL, CtxI, AC, DT,256 TLI);257}258 259/// Test if A and B will obviously have the same value.260///261/// This includes recognizing that %t0 and %t1 will have the same262/// value in code like this:263/// \code264/// %t0 = getelementptr \@a, 0, 3265/// store i32 0, i32* %t0266/// %t1 = getelementptr \@a, 0, 3267/// %t2 = load i32* %t1268/// \endcode269///270static bool AreEquivalentAddressValues(const Value *A, const Value *B) {271 // Test if the values are trivially equivalent.272 if (A == B)273 return true;274 275 // Test if the values come from identical arithmetic instructions.276 // Use isIdenticalToWhenDefined instead of isIdenticalTo because277 // this function is only used when one address use dominates the278 // other, which means that they'll always either have the same279 // value or one of them will have an undefined value.280 if (isa<CastInst>(A) || isa<PHINode>(A) || isa<GetElementPtrInst>(A))281 if (const Instruction *BI = dyn_cast<Instruction>(B))282 if (cast<Instruction>(A)->isIdenticalToWhenDefined(BI))283 return true;284 285 // Otherwise they may not be equivalent.286 return false;287}288 289bool llvm::isDereferenceableAndAlignedInLoop(290 LoadInst *LI, Loop *L, ScalarEvolution &SE, DominatorTree &DT,291 AssumptionCache *AC, SmallVectorImpl<const SCEVPredicate *> *Predicates) {292 const Align Alignment = LI->getAlign();293 auto &DL = LI->getDataLayout();294 Value *Ptr = LI->getPointerOperand();295 APInt EltSize(DL.getIndexTypeSizeInBits(Ptr->getType()),296 DL.getTypeStoreSize(LI->getType()).getFixedValue());297 298 // If given a uniform (i.e. non-varying) address, see if we can prove the299 // access is safe within the loop w/o needing predication.300 if (L->isLoopInvariant(Ptr))301 return isDereferenceableAndAlignedPointer(302 Ptr, Alignment, EltSize, DL, &*L->getHeader()->getFirstNonPHIIt(), AC,303 &DT);304 305 const SCEV *PtrScev = SE.getSCEV(Ptr);306 auto *AddRec = dyn_cast<SCEVAddRecExpr>(PtrScev);307 308 // Check to see if we have a repeating access pattern and it's possible309 // to prove all accesses are well aligned.310 if (!AddRec || AddRec->getLoop() != L || !AddRec->isAffine())311 return false;312 313 auto *Step = dyn_cast<SCEVConstant>(AddRec->getStepRecurrence(SE));314 if (!Step)315 return false;316 317 // For the moment, restrict ourselves to the case where the access size is a318 // multiple of the requested alignment and the base is aligned.319 // TODO: generalize if a case found which warrants320 if (EltSize.urem(Alignment.value()) != 0)321 return false;322 323 // TODO: Handle overlapping accesses.324 if (EltSize.ugt(Step->getAPInt().abs()))325 return false;326 327 const SCEV *MaxBECount =328 Predicates ? SE.getPredicatedSymbolicMaxBackedgeTakenCount(L, *Predicates)329 : SE.getSymbolicMaxBackedgeTakenCount(L);330 const SCEV *BECount = Predicates331 ? SE.getPredicatedBackedgeTakenCount(L, *Predicates)332 : SE.getBackedgeTakenCount(L);333 if (isa<SCEVCouldNotCompute>(MaxBECount))334 return false;335 std::optional<ScalarEvolution::LoopGuards> LoopGuards;336 const auto &[AccessStart, AccessEnd] =337 getStartAndEndForAccess(L, PtrScev, LI->getType(), BECount, MaxBECount,338 &SE, nullptr, &DT, AC, LoopGuards);339 if (isa<SCEVCouldNotCompute>(AccessStart) ||340 isa<SCEVCouldNotCompute>(AccessEnd))341 return false;342 343 // Try to get the access size.344 const SCEV *PtrDiff = SE.getMinusSCEV(AccessEnd, AccessStart);345 if (isa<SCEVCouldNotCompute>(PtrDiff))346 return false;347 348 if (!LoopGuards)349 LoopGuards.emplace(350 ScalarEvolution::LoopGuards::collect(AddRec->getLoop(), SE));351 352 APInt MaxPtrDiff =353 SE.getUnsignedRangeMax(SE.applyLoopGuards(PtrDiff, *LoopGuards));354 355 Value *Base = nullptr;356 APInt AccessSize;357 const SCEV *AccessSizeSCEV = nullptr;358 if (const SCEVUnknown *NewBase = dyn_cast<SCEVUnknown>(AccessStart)) {359 Base = NewBase->getValue();360 AccessSize = MaxPtrDiff;361 AccessSizeSCEV = PtrDiff;362 } else if (auto *MinAdd = dyn_cast<SCEVAddExpr>(AccessStart)) {363 if (MinAdd->getNumOperands() != 2)364 return false;365 366 const auto *Offset = dyn_cast<SCEVConstant>(MinAdd->getOperand(0));367 const auto *NewBase = dyn_cast<SCEVUnknown>(MinAdd->getOperand(1));368 if (!Offset || !NewBase)369 return false;370 371 // The following code below assumes the offset is unsigned, but GEP372 // offsets are treated as signed so we can end up with a signed value373 // here too. For example, suppose the initial PHI value is (i8 255),374 // the offset will be treated as (i8 -1) and sign-extended to (i64 -1).375 if (Offset->getAPInt().isNegative())376 return false;377 378 // For the moment, restrict ourselves to the case where the offset is a379 // multiple of the requested alignment and the base is aligned.380 // TODO: generalize if a case found which warrants381 if (Offset->getAPInt().urem(Alignment.value()) != 0)382 return false;383 384 bool Overflow = false;385 AccessSize = MaxPtrDiff.uadd_ov(Offset->getAPInt(), Overflow);386 if (Overflow)387 return false;388 AccessSizeSCEV = SE.getAddExpr(PtrDiff, Offset);389 Base = NewBase->getValue();390 } else391 return false;392 393 Instruction *CtxI = &*L->getHeader()->getFirstNonPHIIt();394 if (BasicBlock *LoopPred = L->getLoopPredecessor()) {395 if (isa<BranchInst>(LoopPred->getTerminator()))396 CtxI = LoopPred->getTerminator();397 }398 return isDereferenceableAndAlignedPointerViaAssumption(399 Base, Alignment,400 [&SE, AccessSizeSCEV, &LoopGuards](const RetainedKnowledge &RK) {401 return SE.isKnownPredicate(402 CmpInst::ICMP_ULE,403 SE.applyLoopGuards(AccessSizeSCEV, *LoopGuards),404 SE.applyLoopGuards(SE.getSCEV(RK.IRArgValue), *LoopGuards));405 },406 DL, CtxI, AC, &DT) ||407 isDereferenceableAndAlignedPointer(Base, Alignment, AccessSize, DL,408 CtxI, AC, &DT);409}410 411static bool suppressSpeculativeLoadForSanitizers(const Instruction &CtxI) {412 const Function &F = *CtxI.getFunction();413 // Speculative load may create a race that did not exist in the source.414 return F.hasFnAttribute(Attribute::SanitizeThread) ||415 // Speculative load may load data from dirty regions.416 F.hasFnAttribute(Attribute::SanitizeAddress) ||417 F.hasFnAttribute(Attribute::SanitizeHWAddress);418}419 420bool llvm::mustSuppressSpeculation(const LoadInst &LI) {421 return !LI.isUnordered() || suppressSpeculativeLoadForSanitizers(LI);422}423 424/// Check if executing a load of this pointer value cannot trap.425///426/// If DT and ScanFrom are specified this method performs context-sensitive427/// analysis and returns true if it is safe to load immediately before ScanFrom.428///429/// If it is not obviously safe to load from the specified pointer, we do430/// a quick local scan of the basic block containing \c ScanFrom, to determine431/// if the address is already accessed.432///433/// This uses the pointee type to determine how many bytes need to be safe to434/// load from the pointer.435bool llvm::isSafeToLoadUnconditionally(Value *V, Align Alignment, const APInt &Size,436 const DataLayout &DL,437 Instruction *ScanFrom,438 AssumptionCache *AC,439 const DominatorTree *DT,440 const TargetLibraryInfo *TLI) {441 // If DT is not specified we can't make context-sensitive query442 const Instruction* CtxI = DT ? ScanFrom : nullptr;443 if (isDereferenceableAndAlignedPointer(V, Alignment, Size, DL, CtxI, AC, DT,444 TLI)) {445 // With sanitizers `Dereferenceable` is not always enough for unconditional446 // load.447 if (!ScanFrom || !suppressSpeculativeLoadForSanitizers(*ScanFrom))448 return true;449 }450 451 if (!ScanFrom)452 return false;453 454 if (Size.getBitWidth() > 64)455 return false;456 const TypeSize LoadSize = TypeSize::getFixed(Size.getZExtValue());457 458 // Otherwise, be a little bit aggressive by scanning the local block where we459 // want to check to see if the pointer is already being loaded or stored460 // from/to. If so, the previous load or store would have already trapped,461 // so there is no harm doing an extra load (also, CSE will later eliminate462 // the load entirely).463 BasicBlock::iterator BBI = ScanFrom->getIterator(),464 E = ScanFrom->getParent()->begin();465 466 // We can at least always strip pointer casts even though we can't use the467 // base here.468 V = V->stripPointerCasts();469 470 while (BBI != E) {471 --BBI;472 473 // If we see a free or a call which may write to memory (i.e. which might do474 // a free) the pointer could be marked invalid.475 if (isa<CallInst>(BBI) && BBI->mayWriteToMemory() &&476 !isa<LifetimeIntrinsic>(BBI))477 return false;478 479 Value *AccessedPtr;480 Type *AccessedTy;481 Align AccessedAlign;482 if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {483 // Ignore volatile loads. The execution of a volatile load cannot484 // be used to prove an address is backed by regular memory; it can,485 // for example, point to an MMIO register.486 if (LI->isVolatile())487 continue;488 AccessedPtr = LI->getPointerOperand();489 AccessedTy = LI->getType();490 AccessedAlign = LI->getAlign();491 } else if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) {492 // Ignore volatile stores (see comment for loads).493 if (SI->isVolatile())494 continue;495 AccessedPtr = SI->getPointerOperand();496 AccessedTy = SI->getValueOperand()->getType();497 AccessedAlign = SI->getAlign();498 } else499 continue;500 501 if (AccessedAlign < Alignment)502 continue;503 504 // Handle trivial cases.505 if (AccessedPtr == V &&506 TypeSize::isKnownLE(LoadSize, DL.getTypeStoreSize(AccessedTy)))507 return true;508 509 if (AreEquivalentAddressValues(AccessedPtr->stripPointerCasts(), V) &&510 TypeSize::isKnownLE(LoadSize, DL.getTypeStoreSize(AccessedTy)))511 return true;512 }513 return false;514}515 516bool llvm::isSafeToLoadUnconditionally(Value *V, Type *Ty, Align Alignment,517 const DataLayout &DL,518 Instruction *ScanFrom,519 AssumptionCache *AC,520 const DominatorTree *DT,521 const TargetLibraryInfo *TLI) {522 TypeSize TySize = DL.getTypeStoreSize(Ty);523 if (TySize.isScalable())524 return false;525 APInt Size(DL.getIndexTypeSizeInBits(V->getType()), TySize.getFixedValue());526 return isSafeToLoadUnconditionally(V, Alignment, Size, DL, ScanFrom, AC, DT,527 TLI);528}529 530/// DefMaxInstsToScan - the default number of maximum instructions531/// to scan in the block, used by FindAvailableLoadedValue().532/// FindAvailableLoadedValue() was introduced in r60148, to improve jump533/// threading in part by eliminating partially redundant loads.534/// At that point, the value of MaxInstsToScan was already set to '6'535/// without documented explanation.536cl::opt<unsigned>537llvm::DefMaxInstsToScan("available-load-scan-limit", cl::init(6), cl::Hidden,538 cl::desc("Use this to specify the default maximum number of instructions "539 "to scan backward from a given instruction, when searching for "540 "available loaded value"));541 542Value *llvm::FindAvailableLoadedValue(LoadInst *Load, BasicBlock *ScanBB,543 BasicBlock::iterator &ScanFrom,544 unsigned MaxInstsToScan,545 BatchAAResults *AA, bool *IsLoad,546 unsigned *NumScanedInst) {547 // Don't CSE load that is volatile or anything stronger than unordered.548 if (!Load->isUnordered())549 return nullptr;550 551 MemoryLocation Loc = MemoryLocation::get(Load);552 return findAvailablePtrLoadStore(Loc, Load->getType(), Load->isAtomic(),553 ScanBB, ScanFrom, MaxInstsToScan, AA, IsLoad,554 NumScanedInst);555}556 557// Check if the load and the store have the same base, constant offsets and558// non-overlapping access ranges.559static bool areNonOverlapSameBaseLoadAndStore(const Value *LoadPtr,560 Type *LoadTy,561 const Value *StorePtr,562 Type *StoreTy,563 const DataLayout &DL) {564 APInt LoadOffset(DL.getIndexTypeSizeInBits(LoadPtr->getType()), 0);565 APInt StoreOffset(DL.getIndexTypeSizeInBits(StorePtr->getType()), 0);566 const Value *LoadBase = LoadPtr->stripAndAccumulateConstantOffsets(567 DL, LoadOffset, /* AllowNonInbounds */ false);568 const Value *StoreBase = StorePtr->stripAndAccumulateConstantOffsets(569 DL, StoreOffset, /* AllowNonInbounds */ false);570 if (LoadBase != StoreBase)571 return false;572 auto LoadAccessSize = LocationSize::precise(DL.getTypeStoreSize(LoadTy));573 auto StoreAccessSize = LocationSize::precise(DL.getTypeStoreSize(StoreTy));574 ConstantRange LoadRange(LoadOffset,575 LoadOffset + LoadAccessSize.toRaw());576 ConstantRange StoreRange(StoreOffset,577 StoreOffset + StoreAccessSize.toRaw());578 return LoadRange.intersectWith(StoreRange).isEmptySet();579}580 581static Value *getAvailableLoadStore(Instruction *Inst, const Value *Ptr,582 Type *AccessTy, bool AtLeastAtomic,583 const DataLayout &DL, bool *IsLoadCSE) {584 // If this is a load of Ptr, the loaded value is available.585 // (This is true even if the load is volatile or atomic, although586 // those cases are unlikely.)587 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {588 // We can value forward from an atomic to a non-atomic, but not the589 // other way around.590 if (LI->isAtomic() < AtLeastAtomic)591 return nullptr;592 593 Value *LoadPtr = LI->getPointerOperand()->stripPointerCasts();594 if (!AreEquivalentAddressValues(LoadPtr, Ptr))595 return nullptr;596 597 if (CastInst::isBitOrNoopPointerCastable(LI->getType(), AccessTy, DL)) {598 if (IsLoadCSE)599 *IsLoadCSE = true;600 return LI;601 }602 }603 604 // If this is a store through Ptr, the value is available!605 // (This is true even if the store is volatile or atomic, although606 // those cases are unlikely.)607 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {608 // We can value forward from an atomic to a non-atomic, but not the609 // other way around.610 if (SI->isAtomic() < AtLeastAtomic)611 return nullptr;612 613 Value *StorePtr = SI->getPointerOperand()->stripPointerCasts();614 if (!AreEquivalentAddressValues(StorePtr, Ptr))615 return nullptr;616 617 if (IsLoadCSE)618 *IsLoadCSE = false;619 620 Value *Val = SI->getValueOperand();621 if (CastInst::isBitOrNoopPointerCastable(Val->getType(), AccessTy, DL))622 return Val;623 624 TypeSize StoreSize = DL.getTypeSizeInBits(Val->getType());625 TypeSize LoadSize = DL.getTypeSizeInBits(AccessTy);626 if (TypeSize::isKnownLE(LoadSize, StoreSize))627 if (auto *C = dyn_cast<Constant>(Val))628 return ConstantFoldLoadFromConst(C, AccessTy, DL);629 }630 631 if (auto *MSI = dyn_cast<MemSetInst>(Inst)) {632 // Don't forward from (non-atomic) memset to atomic load.633 if (AtLeastAtomic)634 return nullptr;635 636 // Only handle constant memsets.637 auto *Val = dyn_cast<ConstantInt>(MSI->getValue());638 auto *Len = dyn_cast<ConstantInt>(MSI->getLength());639 if (!Val || !Len)640 return nullptr;641 642 // Handle offsets.643 int64_t StoreOffset = 0, LoadOffset = 0;644 const Value *StoreBase =645 GetPointerBaseWithConstantOffset(MSI->getDest(), StoreOffset, DL);646 const Value *LoadBase =647 GetPointerBaseWithConstantOffset(Ptr, LoadOffset, DL);648 if (StoreBase != LoadBase || LoadOffset < StoreOffset)649 return nullptr;650 651 if (IsLoadCSE)652 *IsLoadCSE = false;653 654 TypeSize LoadTypeSize = DL.getTypeSizeInBits(AccessTy);655 if (LoadTypeSize.isScalable())656 return nullptr;657 658 // Make sure the read bytes are contained in the memset.659 uint64_t LoadSize = LoadTypeSize.getFixedValue();660 if ((Len->getValue() * 8).ult(LoadSize + (LoadOffset - StoreOffset) * 8))661 return nullptr;662 663 APInt Splat = LoadSize >= 8 ? APInt::getSplat(LoadSize, Val->getValue())664 : Val->getValue().trunc(LoadSize);665 ConstantInt *SplatC = ConstantInt::get(MSI->getContext(), Splat);666 if (CastInst::isBitOrNoopPointerCastable(SplatC->getType(), AccessTy, DL))667 return SplatC;668 669 return nullptr;670 }671 672 return nullptr;673}674 675Value *llvm::findAvailablePtrLoadStore(676 const MemoryLocation &Loc, Type *AccessTy, bool AtLeastAtomic,677 BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan,678 BatchAAResults *AA, bool *IsLoadCSE, unsigned *NumScanedInst) {679 if (MaxInstsToScan == 0)680 MaxInstsToScan = ~0U;681 682 const DataLayout &DL = ScanBB->getDataLayout();683 const Value *StrippedPtr = Loc.Ptr->stripPointerCasts();684 685 while (ScanFrom != ScanBB->begin()) {686 // We must ignore debug info directives when counting (otherwise they687 // would affect codegen).688 Instruction *Inst = &*--ScanFrom;689 if (Inst->isDebugOrPseudoInst())690 continue;691 692 // Restore ScanFrom to expected value in case next test succeeds693 ScanFrom++;694 695 if (NumScanedInst)696 ++(*NumScanedInst);697 698 // Don't scan huge blocks.699 if (MaxInstsToScan-- == 0)700 return nullptr;701 702 --ScanFrom;703 704 if (Value *Available = getAvailableLoadStore(Inst, StrippedPtr, AccessTy,705 AtLeastAtomic, DL, IsLoadCSE))706 return Available;707 708 // Try to get the store size for the type.709 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {710 Value *StorePtr = SI->getPointerOperand()->stripPointerCasts();711 712 // If both StrippedPtr and StorePtr reach all the way to an alloca or713 // global and they are different, ignore the store. This is a trivial form714 // of alias analysis that is important for reg2mem'd code.715 if ((isa<AllocaInst>(StrippedPtr) || isa<GlobalVariable>(StrippedPtr)) &&716 (isa<AllocaInst>(StorePtr) || isa<GlobalVariable>(StorePtr)) &&717 StrippedPtr != StorePtr)718 continue;719 720 if (!AA) {721 // When AA isn't available, but if the load and the store have the same722 // base, constant offsets and non-overlapping access ranges, ignore the723 // store. This is a simple form of alias analysis that is used by the724 // inliner. FIXME: use BasicAA if possible.725 if (areNonOverlapSameBaseLoadAndStore(726 Loc.Ptr, AccessTy, SI->getPointerOperand(),727 SI->getValueOperand()->getType(), DL))728 continue;729 } else {730 // If we have alias analysis and it says the store won't modify the731 // loaded value, ignore the store.732 if (!isModSet(AA->getModRefInfo(SI, Loc)))733 continue;734 }735 736 // Otherwise the store that may or may not alias the pointer, bail out.737 ++ScanFrom;738 return nullptr;739 }740 741 // If this is some other instruction that may clobber Ptr, bail out.742 if (Inst->mayWriteToMemory()) {743 // If alias analysis claims that it really won't modify the load,744 // ignore it.745 if (AA && !isModSet(AA->getModRefInfo(Inst, Loc)))746 continue;747 748 // May modify the pointer, bail out.749 ++ScanFrom;750 return nullptr;751 }752 }753 754 // Got to the start of the block, we didn't find it, but are done for this755 // block.756 return nullptr;757}758 759Value *llvm::FindAvailableLoadedValue(LoadInst *Load, BatchAAResults &AA,760 bool *IsLoadCSE,761 unsigned MaxInstsToScan) {762 const DataLayout &DL = Load->getDataLayout();763 Value *StrippedPtr = Load->getPointerOperand()->stripPointerCasts();764 BasicBlock *ScanBB = Load->getParent();765 Type *AccessTy = Load->getType();766 bool AtLeastAtomic = Load->isAtomic();767 768 if (!Load->isUnordered())769 return nullptr;770 771 // Try to find an available value first, and delay expensive alias analysis772 // queries until later.773 Value *Available = nullptr;774 SmallVector<Instruction *> MustNotAliasInsts;775 for (Instruction &Inst : make_range(++Load->getReverseIterator(),776 ScanBB->rend())) {777 if (Inst.isDebugOrPseudoInst())778 continue;779 780 if (MaxInstsToScan-- == 0)781 return nullptr;782 783 Available = getAvailableLoadStore(&Inst, StrippedPtr, AccessTy,784 AtLeastAtomic, DL, IsLoadCSE);785 if (Available)786 break;787 788 if (Inst.mayWriteToMemory())789 MustNotAliasInsts.push_back(&Inst);790 }791 792 // If we found an available value, ensure that the instructions in between793 // did not modify the memory location.794 if (Available) {795 MemoryLocation Loc = MemoryLocation::get(Load);796 for (Instruction *Inst : MustNotAliasInsts)797 if (isModSet(AA.getModRefInfo(Inst, Loc)))798 return nullptr;799 }800 801 return Available;802}803 804// Returns true if a use is either in an ICmp/PtrToInt or a Phi/Select that only805// feeds into them.806static bool isPointerUseReplacable(const Use &U) {807 unsigned Limit = 40;808 SmallVector<const User *> Worklist({U.getUser()});809 SmallPtrSet<const User *, 8> Visited;810 811 while (!Worklist.empty() && --Limit) {812 auto *User = Worklist.pop_back_val();813 if (!Visited.insert(User).second)814 continue;815 // FIXME: The PtrToIntInst case here is not strictly correct, as it816 // changes which provenance is exposed.817 if (isa<ICmpInst, PtrToIntInst, PtrToAddrInst>(User))818 continue;819 if (isa<PHINode, SelectInst>(User))820 Worklist.append(User->user_begin(), User->user_end());821 else822 return false;823 }824 825 return Limit != 0;826}827 828// Returns true if `To` is a null pointer, constant dereferenceable pointer or829// both pointers have the same underlying objects.830static bool isPointerAlwaysReplaceable(const Value *From, const Value *To,831 const DataLayout &DL) {832 // This is not strictly correct, but we do it for now to retain important833 // optimizations.834 if (isa<ConstantPointerNull>(To))835 return true;836 if (isa<Constant>(To) &&837 isDereferenceablePointer(To, Type::getInt8Ty(To->getContext()), DL))838 return true;839 return getUnderlyingObjectAggressive(From) ==840 getUnderlyingObjectAggressive(To);841}842 843bool llvm::canReplacePointersInUseIfEqual(const Use &U, const Value *To,844 const DataLayout &DL) {845 assert(U->getType() == To->getType() && "values must have matching types");846 // Not a pointer, just return true.847 if (!To->getType()->isPointerTy())848 return true;849 850 // Do not perform replacements in lifetime intrinsic arguments.851 if (isa<LifetimeIntrinsic>(U.getUser()))852 return false;853 854 if (isPointerAlwaysReplaceable(&*U, To, DL))855 return true;856 return isPointerUseReplacable(U);857}858 859bool llvm::canReplacePointersIfEqual(const Value *From, const Value *To,860 const DataLayout &DL) {861 assert(From->getType() == To->getType() && "values must have matching types");862 // Not a pointer, just return true.863 if (!From->getType()->isPointerTy())864 return true;865 866 return isPointerAlwaysReplaceable(From, To, DL);867}868 869bool llvm::isReadOnlyLoop(870 Loop *L, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC,871 SmallVectorImpl<LoadInst *> &NonDereferenceableAndAlignedLoads,872 SmallVectorImpl<const SCEVPredicate *> *Predicates) {873 for (BasicBlock *BB : L->blocks()) {874 for (Instruction &I : *BB) {875 if (auto *LI = dyn_cast<LoadInst>(&I)) {876 if (!isDereferenceableAndAlignedInLoop(LI, L, *SE, *DT, AC, Predicates))877 NonDereferenceableAndAlignedLoads.push_back(LI);878 } else if (I.mayReadFromMemory() || I.mayWriteToMemory() ||879 I.mayThrow()) {880 return false;881 }882 }883 }884 return true;885}886 887LinearExpression llvm::decomposeLinearExpression(const DataLayout &DL,888 Value *Ptr) {889 assert(Ptr->getType()->isPointerTy() && "Must be called with pointer arg");890 891 unsigned BitWidth = DL.getIndexTypeSizeInBits(Ptr->getType());892 LinearExpression Expr(Ptr, BitWidth);893 894 while (true) {895 auto *GEP = dyn_cast<GEPOperator>(Expr.BasePtr);896 if (!GEP || GEP->getSourceElementType()->isScalableTy())897 return Expr;898 899 Value *VarIndex = nullptr;900 for (Value *Index : GEP->indices()) {901 if (isa<ConstantInt>(Index))902 continue;903 // Only allow a single variable index. We do not bother to handle the904 // case of the same variable index appearing multiple times.905 if (Expr.Index || VarIndex)906 return Expr;907 VarIndex = Index;908 }909 910 // Don't return non-canonical indexes.911 if (VarIndex && !VarIndex->getType()->isIntegerTy(BitWidth))912 return Expr;913 914 // We have verified that we can fully handle this GEP, so we can update Expr915 // members past this point.916 Expr.BasePtr = GEP->getPointerOperand();917 Expr.Flags = Expr.Flags.intersectForOffsetAdd(GEP->getNoWrapFlags());918 for (gep_type_iterator GTI = gep_type_begin(GEP), GTE = gep_type_end(GEP);919 GTI != GTE; ++GTI) {920 Value *Index = GTI.getOperand();921 if (auto *ConstOffset = dyn_cast<ConstantInt>(Index)) {922 if (ConstOffset->isZero())923 continue;924 if (StructType *STy = GTI.getStructTypeOrNull()) {925 unsigned ElementIdx = ConstOffset->getZExtValue();926 const StructLayout *SL = DL.getStructLayout(STy);927 Expr.Offset += SL->getElementOffset(ElementIdx);928 continue;929 }930 // Truncate if type size exceeds index space.931 APInt IndexedSize(BitWidth, GTI.getSequentialElementStride(DL),932 /*isSigned=*/false,933 /*implcitTrunc=*/true);934 Expr.Offset += ConstOffset->getValue() * IndexedSize;935 continue;936 }937 938 // FIXME: Also look through a mul/shl in the index.939 assert(Expr.Index == nullptr && "Shouldn't have index yet");940 Expr.Index = Index;941 // Truncate if type size exceeds index space.942 Expr.Scale = APInt(BitWidth, GTI.getSequentialElementStride(DL),943 /*isSigned=*/false, /*implicitTrunc=*/true);944 }945 }946 947 return Expr;948}949