LLVM 20.0.0git
Loads.cpp
Go to the documentation of this file.
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"
22#include "llvm/IR/DataLayout.h"
24#include "llvm/IR/Operator.h"
25
26using namespace llvm;
27
28static bool isAligned(const Value *Base, Align Alignment,
29 const DataLayout &DL) {
30 return Base->getPointerAlignment(DL) >= Alignment;
31}
32
33/// Test if V is always a pointer to allocated and suitably aligned memory for
34/// a simple load or store.
36 const Value *V, Align Alignment, const APInt &Size, const DataLayout &DL,
37 const Instruction *CtxI, AssumptionCache *AC, const DominatorTree *DT,
39 unsigned MaxDepth) {
40 assert(V->getType()->isPointerTy() && "Base must be pointer");
41
42 // Recursion limit.
43 if (MaxDepth-- == 0)
44 return false;
45
46 // Already visited? Bail out, we've likely hit unreachable code.
47 if (!Visited.insert(V).second)
48 return false;
49
50 // Note that it is not safe to speculate into a malloc'd region because
51 // malloc may return null.
52
53 // For GEPs, determine if the indexing lands within the allocated object.
54 if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
55 const Value *Base = GEP->getPointerOperand();
56
57 APInt Offset(DL.getIndexTypeSizeInBits(GEP->getType()), 0);
58 if (!GEP->accumulateConstantOffset(DL, Offset) || Offset.isNegative() ||
59 !Offset.urem(APInt(Offset.getBitWidth(), Alignment.value()))
60 .isMinValue())
61 return false;
62
63 // If the base pointer is dereferenceable for Offset+Size bytes, then the
64 // GEP (== Base + Offset) is dereferenceable for Size bytes. If the base
65 // pointer is aligned to Align bytes, and the Offset is divisible by Align
66 // then the GEP (== Base + Offset == k_0 * Align + k_1 * Align) is also
67 // aligned to Align bytes.
68
69 // Offset and Size may have different bit widths if we have visited an
70 // addrspacecast, so we can't do arithmetic directly on the APInt values.
72 Base, Alignment, Offset + Size.sextOrTrunc(Offset.getBitWidth()), DL,
73 CtxI, AC, DT, TLI, Visited, MaxDepth);
74 }
75
76 // bitcast instructions are no-ops as far as dereferenceability is concerned.
77 if (const BitCastOperator *BC = dyn_cast<BitCastOperator>(V)) {
78 if (BC->getSrcTy()->isPointerTy())
80 BC->getOperand(0), Alignment, Size, DL, CtxI, AC, DT, TLI,
81 Visited, MaxDepth);
82 }
83
84 // Recurse into both hands of select.
85 if (const SelectInst *Sel = dyn_cast<SelectInst>(V)) {
86 return isDereferenceableAndAlignedPointer(Sel->getTrueValue(), Alignment,
87 Size, DL, CtxI, AC, DT, TLI,
88 Visited, MaxDepth) &&
89 isDereferenceableAndAlignedPointer(Sel->getFalseValue(), Alignment,
90 Size, DL, CtxI, AC, DT, TLI,
91 Visited, MaxDepth);
92 }
93
94 auto IsKnownDeref = [&]() {
95 bool CheckForNonNull, CheckForFreed;
96 if (!Size.ule(V->getPointerDereferenceableBytes(DL, CheckForNonNull,
97 CheckForFreed)) ||
98 CheckForFreed)
99 return false;
100 if (CheckForNonNull &&
101 !isKnownNonZero(V, SimplifyQuery(DL, DT, AC, CtxI)))
102 return false;
103 // When using something like !dereferenceable on a load, the
104 // dereferenceability may only be valid on a specific control-flow path.
105 // If the instruction doesn't dominate the context instruction, we're
106 // asking about dereferenceability under the assumption that the
107 // instruction has been speculated to the point of the context instruction,
108 // in which case we don't know if the dereferenceability info still holds.
109 // We don't bother handling allocas here, as they aren't speculatable
110 // anyway.
111 auto *I = dyn_cast<Instruction>(V);
112 if (I && !isa<AllocaInst>(I))
113 return CtxI && isValidAssumeForContext(I, CtxI, DT);
114 return true;
115 };
116 if (IsKnownDeref()) {
117 // As we recursed through GEPs to get here, we've incrementally checked
118 // that each step advanced by a multiple of the alignment. If our base is
119 // properly aligned, then the original offset accessed must also be.
120 return isAligned(V, Alignment, DL);
121 }
122
123 /// TODO refactor this function to be able to search independently for
124 /// Dereferencability and Alignment requirements.
125
126
127 if (const auto *Call = dyn_cast<CallBase>(V)) {
128 if (auto *RP = getArgumentAliasingToReturnedPointer(Call, true))
129 return isDereferenceableAndAlignedPointer(RP, Alignment, Size, DL, CtxI,
130 AC, DT, TLI, Visited, MaxDepth);
131
132 // If we have a call we can't recurse through, check to see if this is an
133 // allocation function for which we can establish an minimum object size.
134 // Such a minimum object size is analogous to a deref_or_null attribute in
135 // that we still need to prove the result non-null at point of use.
136 // NOTE: We can only use the object size as a base fact as we a) need to
137 // prove alignment too, and b) don't want the compile time impact of a
138 // separate recursive walk.
139 ObjectSizeOpts Opts;
140 // TODO: It may be okay to round to align, but that would imply that
141 // accessing slightly out of bounds was legal, and we're currently
142 // inconsistent about that. For the moment, be conservative.
143 Opts.RoundToAlign = false;
144 Opts.NullIsUnknownSize = true;
145 uint64_t ObjSize;
146 if (getObjectSize(V, ObjSize, DL, TLI, Opts)) {
147 APInt KnownDerefBytes(Size.getBitWidth(), ObjSize);
148 if (KnownDerefBytes.getBoolValue() && KnownDerefBytes.uge(Size) &&
149 isKnownNonZero(V, SimplifyQuery(DL, DT, AC, CtxI)) &&
150 !V->canBeFreed()) {
151 // As we recursed through GEPs to get here, we've incrementally
152 // checked that each step advanced by a multiple of the alignment. If
153 // our base is properly aligned, then the original offset accessed
154 // must also be.
155 return isAligned(V, Alignment, DL);
156 }
157 }
158 }
159
160 // For gc.relocate, look through relocations
161 if (const GCRelocateInst *RelocateInst = dyn_cast<GCRelocateInst>(V))
162 return isDereferenceableAndAlignedPointer(RelocateInst->getDerivedPtr(),
163 Alignment, Size, DL, CtxI, AC, DT,
164 TLI, Visited, MaxDepth);
165
166 if (const AddrSpaceCastOperator *ASC = dyn_cast<AddrSpaceCastOperator>(V))
167 return isDereferenceableAndAlignedPointer(ASC->getOperand(0), Alignment,
168 Size, DL, CtxI, AC, DT, TLI,
169 Visited, MaxDepth);
170
171 if (CtxI) {
172 /// Look through assumes to see if both dereferencability and alignment can
173 /// be proven by an assume if needed.
174 RetainedKnowledge AlignRK;
175 RetainedKnowledge DerefRK;
176 bool IsAligned = V->getPointerAlignment(DL) >= Alignment;
178 V, {Attribute::Dereferenceable, Attribute::Alignment}, AC,
179 [&](RetainedKnowledge RK, Instruction *Assume, auto) {
180 if (!isValidAssumeForContext(Assume, CtxI, DT))
181 return false;
182 if (RK.AttrKind == Attribute::Alignment)
183 AlignRK = std::max(AlignRK, RK);
184 if (RK.AttrKind == Attribute::Dereferenceable)
185 DerefRK = std::max(DerefRK, RK);
186 IsAligned |= AlignRK && AlignRK.ArgValue >= Alignment.value();
187 if (IsAligned && DerefRK &&
188 DerefRK.ArgValue >= Size.getZExtValue())
189 return true; // We have found what we needed so we stop looking
190 return false; // Other assumes may have better information. so
191 // keep looking
192 }))
193 return true;
194 }
195
196 // If we don't know, assume the worst.
197 return false;
198}
199
201 const Value *V, Align Alignment, const APInt &Size, const DataLayout &DL,
202 const Instruction *CtxI, AssumptionCache *AC, const DominatorTree *DT,
203 const TargetLibraryInfo *TLI) {
204 // Note: At the moment, Size can be zero. This ends up being interpreted as
205 // a query of whether [Base, V] is dereferenceable and V is aligned (since
206 // that's what the implementation happened to do). It's unclear if this is
207 // the desired semantic, but at least SelectionDAG does exercise this case.
208
210 return ::isDereferenceableAndAlignedPointer(V, Alignment, Size, DL, CtxI, AC,
211 DT, TLI, Visited, 16);
212}
213
215 const Value *V, Type *Ty, Align Alignment, const DataLayout &DL,
216 const Instruction *CtxI, AssumptionCache *AC, const DominatorTree *DT,
217 const TargetLibraryInfo *TLI) {
218 // For unsized types or scalable vectors we don't know exactly how many bytes
219 // are dereferenced, so bail out.
220 if (!Ty->isSized() || Ty->isScalableTy())
221 return false;
222
223 // When dereferenceability information is provided by a dereferenceable
224 // attribute, we know exactly how many bytes are dereferenceable. If we can
225 // determine the exact offset to the attributed variable, we can use that
226 // information here.
227
228 APInt AccessSize(DL.getPointerTypeSizeInBits(V->getType()),
229 DL.getTypeStoreSize(Ty));
230 return isDereferenceableAndAlignedPointer(V, Alignment, AccessSize, DL, CtxI,
231 AC, DT, TLI);
232}
233
235 const DataLayout &DL,
236 const Instruction *CtxI,
237 AssumptionCache *AC,
238 const DominatorTree *DT,
239 const TargetLibraryInfo *TLI) {
240 return isDereferenceableAndAlignedPointer(V, Ty, Align(1), DL, CtxI, AC, DT,
241 TLI);
242}
243
244/// Test if A and B will obviously have the same value.
245///
246/// This includes recognizing that %t0 and %t1 will have the same
247/// value in code like this:
248/// \code
249/// %t0 = getelementptr \@a, 0, 3
250/// store i32 0, i32* %t0
251/// %t1 = getelementptr \@a, 0, 3
252/// %t2 = load i32* %t1
253/// \endcode
254///
255static bool AreEquivalentAddressValues(const Value *A, const Value *B) {
256 // Test if the values are trivially equivalent.
257 if (A == B)
258 return true;
259
260 // Test if the values come from identical arithmetic instructions.
261 // Use isIdenticalToWhenDefined instead of isIdenticalTo because
262 // this function is only used when one address use dominates the
263 // other, which means that they'll always either have the same
264 // value or one of them will have an undefined value.
265 if (isa<BinaryOperator>(A) || isa<CastInst>(A) || isa<PHINode>(A) ||
266 isa<GetElementPtrInst>(A))
267 if (const Instruction *BI = dyn_cast<Instruction>(B))
268 if (cast<Instruction>(A)->isIdenticalToWhenDefined(BI))
269 return true;
270
271 // Otherwise they may not be equivalent.
272 return false;
273}
274
276 LoadInst *LI, Loop *L, ScalarEvolution &SE, DominatorTree &DT,
278 auto &DL = LI->getDataLayout();
279 Value *Ptr = LI->getPointerOperand();
280
281 APInt EltSize(DL.getIndexTypeSizeInBits(Ptr->getType()),
282 DL.getTypeStoreSize(LI->getType()).getFixedValue());
283 const Align Alignment = LI->getAlign();
284
285 Instruction *HeaderFirstNonPHI = L->getHeader()->getFirstNonPHI();
286
287 // If given a uniform (i.e. non-varying) address, see if we can prove the
288 // access is safe within the loop w/o needing predication.
289 if (L->isLoopInvariant(Ptr))
290 return isDereferenceableAndAlignedPointer(Ptr, Alignment, EltSize, DL,
291 HeaderFirstNonPHI, AC, &DT);
292
293 // Otherwise, check to see if we have a repeating access pattern where we can
294 // prove that all accesses are well aligned and dereferenceable.
295 auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(Ptr));
296 if (!AddRec || AddRec->getLoop() != L || !AddRec->isAffine())
297 return false;
298 auto* Step = dyn_cast<SCEVConstant>(AddRec->getStepRecurrence(SE));
299 if (!Step)
300 return false;
301
302 auto TC = SE.getSmallConstantMaxTripCount(L, Predicates);
303 if (!TC)
304 return false;
305
306 // TODO: Handle overlapping accesses.
307 // We should be computing AccessSize as (TC - 1) * Step + EltSize.
308 if (EltSize.sgt(Step->getAPInt()))
309 return false;
310
311 // Compute the total access size for access patterns with unit stride and
312 // patterns with gaps. For patterns with unit stride, Step and EltSize are the
313 // same.
314 // For patterns with gaps (i.e. non unit stride), we are
315 // accessing EltSize bytes at every Step.
316 APInt AccessSize = TC * Step->getAPInt();
317
318 assert(SE.isLoopInvariant(AddRec->getStart(), L) &&
319 "implied by addrec definition");
320 Value *Base = nullptr;
321 if (auto *StartS = dyn_cast<SCEVUnknown>(AddRec->getStart())) {
322 Base = StartS->getValue();
323 } else if (auto *StartS = dyn_cast<SCEVAddExpr>(AddRec->getStart())) {
324 // Handle (NewBase + offset) as start value.
325 const auto *Offset = dyn_cast<SCEVConstant>(StartS->getOperand(0));
326 const auto *NewBase = dyn_cast<SCEVUnknown>(StartS->getOperand(1));
327 if (StartS->getNumOperands() == 2 && Offset && NewBase) {
328 // The following code below assumes the offset is unsigned, but GEP
329 // offsets are treated as signed so we can end up with a signed value
330 // here too. For example, suppose the initial PHI value is (i8 255),
331 // the offset will be treated as (i8 -1) and sign-extended to (i64 -1).
332 if (Offset->getAPInt().isNegative())
333 return false;
334
335 // For the moment, restrict ourselves to the case where the offset is a
336 // multiple of the requested alignment and the base is aligned.
337 // TODO: generalize if a case found which warrants
338 if (Offset->getAPInt().urem(Alignment.value()) != 0)
339 return false;
340 Base = NewBase->getValue();
341 bool Overflow = false;
342 AccessSize = AccessSize.uadd_ov(Offset->getAPInt(), Overflow);
343 if (Overflow)
344 return false;
345 }
346 }
347
348 if (!Base)
349 return false;
350
351 // For the moment, restrict ourselves to the case where the access size is a
352 // multiple of the requested alignment and the base is aligned.
353 // TODO: generalize if a case found which warrants
354 if (EltSize.urem(Alignment.value()) != 0)
355 return false;
356 return isDereferenceableAndAlignedPointer(Base, Alignment, AccessSize, DL,
357 HeaderFirstNonPHI, AC, &DT);
358}
359
361 const Function &F = *CtxI.getFunction();
362 // Speculative load may create a race that did not exist in the source.
363 return F.hasFnAttribute(Attribute::SanitizeThread) ||
364 // Speculative load may load data from dirty regions.
365 F.hasFnAttribute(Attribute::SanitizeAddress) ||
366 F.hasFnAttribute(Attribute::SanitizeHWAddress);
367}
368
371}
372
373/// Check if executing a load of this pointer value cannot trap.
374///
375/// If DT and ScanFrom are specified this method performs context-sensitive
376/// analysis and returns true if it is safe to load immediately before ScanFrom.
377///
378/// If it is not obviously safe to load from the specified pointer, we do
379/// a quick local scan of the basic block containing \c ScanFrom, to determine
380/// if the address is already accessed.
381///
382/// This uses the pointee type to determine how many bytes need to be safe to
383/// load from the pointer.
385 const DataLayout &DL,
386 Instruction *ScanFrom,
387 AssumptionCache *AC,
388 const DominatorTree *DT,
389 const TargetLibraryInfo *TLI) {
390 // If DT is not specified we can't make context-sensitive query
391 const Instruction* CtxI = DT ? ScanFrom : nullptr;
392 if (isDereferenceableAndAlignedPointer(V, Alignment, Size, DL, CtxI, AC, DT,
393 TLI)) {
394 // With sanitizers `Dereferenceable` is not always enough for unconditional
395 // load.
396 if (!ScanFrom || !suppressSpeculativeLoadForSanitizers(*ScanFrom))
397 return true;
398 }
399
400 if (!ScanFrom)
401 return false;
402
403 if (Size.getBitWidth() > 64)
404 return false;
405 const TypeSize LoadSize = TypeSize::getFixed(Size.getZExtValue());
406
407 // Otherwise, be a little bit aggressive by scanning the local block where we
408 // want to check to see if the pointer is already being loaded or stored
409 // from/to. If so, the previous load or store would have already trapped,
410 // so there is no harm doing an extra load (also, CSE will later eliminate
411 // the load entirely).
412 BasicBlock::iterator BBI = ScanFrom->getIterator(),
413 E = ScanFrom->getParent()->begin();
414
415 // We can at least always strip pointer casts even though we can't use the
416 // base here.
417 V = V->stripPointerCasts();
418
419 while (BBI != E) {
420 --BBI;
421
422 // If we see a free or a call which may write to memory (i.e. which might do
423 // a free) the pointer could be marked invalid.
424 if (isa<CallInst>(BBI) && BBI->mayWriteToMemory() &&
425 !isa<LifetimeIntrinsic>(BBI) && !isa<DbgInfoIntrinsic>(BBI))
426 return false;
427
428 Value *AccessedPtr;
429 Type *AccessedTy;
430 Align AccessedAlign;
431 if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
432 // Ignore volatile loads. The execution of a volatile load cannot
433 // be used to prove an address is backed by regular memory; it can,
434 // for example, point to an MMIO register.
435 if (LI->isVolatile())
436 continue;
437 AccessedPtr = LI->getPointerOperand();
438 AccessedTy = LI->getType();
439 AccessedAlign = LI->getAlign();
440 } else if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) {
441 // Ignore volatile stores (see comment for loads).
442 if (SI->isVolatile())
443 continue;
444 AccessedPtr = SI->getPointerOperand();
445 AccessedTy = SI->getValueOperand()->getType();
446 AccessedAlign = SI->getAlign();
447 } else
448 continue;
449
450 if (AccessedAlign < Alignment)
451 continue;
452
453 // Handle trivial cases.
454 if (AccessedPtr == V &&
455 TypeSize::isKnownLE(LoadSize, DL.getTypeStoreSize(AccessedTy)))
456 return true;
457
458 if (AreEquivalentAddressValues(AccessedPtr->stripPointerCasts(), V) &&
459 TypeSize::isKnownLE(LoadSize, DL.getTypeStoreSize(AccessedTy)))
460 return true;
461 }
462 return false;
463}
464
466 const DataLayout &DL,
467 Instruction *ScanFrom,
468 AssumptionCache *AC,
469 const DominatorTree *DT,
470 const TargetLibraryInfo *TLI) {
471 TypeSize TySize = DL.getTypeStoreSize(Ty);
472 if (TySize.isScalable())
473 return false;
474 APInt Size(DL.getIndexTypeSizeInBits(V->getType()), TySize.getFixedValue());
475 return isSafeToLoadUnconditionally(V, Alignment, Size, DL, ScanFrom, AC, DT,
476 TLI);
477}
478
479/// DefMaxInstsToScan - the default number of maximum instructions
480/// to scan in the block, used by FindAvailableLoadedValue().
481/// FindAvailableLoadedValue() was introduced in r60148, to improve jump
482/// threading in part by eliminating partially redundant loads.
483/// At that point, the value of MaxInstsToScan was already set to '6'
484/// without documented explanation.
486llvm::DefMaxInstsToScan("available-load-scan-limit", cl::init(6), cl::Hidden,
487 cl::desc("Use this to specify the default maximum number of instructions "
488 "to scan backward from a given instruction, when searching for "
489 "available loaded value"));
490
492 BasicBlock::iterator &ScanFrom,
493 unsigned MaxInstsToScan,
494 BatchAAResults *AA, bool *IsLoad,
495 unsigned *NumScanedInst) {
496 // Don't CSE load that is volatile or anything stronger than unordered.
497 if (!Load->isUnordered())
498 return nullptr;
499
501 return findAvailablePtrLoadStore(Loc, Load->getType(), Load->isAtomic(),
502 ScanBB, ScanFrom, MaxInstsToScan, AA, IsLoad,
503 NumScanedInst);
504}
505
506// Check if the load and the store have the same base, constant offsets and
507// non-overlapping access ranges.
508static bool areNonOverlapSameBaseLoadAndStore(const Value *LoadPtr,
509 Type *LoadTy,
510 const Value *StorePtr,
511 Type *StoreTy,
512 const DataLayout &DL) {
513 APInt LoadOffset(DL.getIndexTypeSizeInBits(LoadPtr->getType()), 0);
514 APInt StoreOffset(DL.getIndexTypeSizeInBits(StorePtr->getType()), 0);
515 const Value *LoadBase = LoadPtr->stripAndAccumulateConstantOffsets(
516 DL, LoadOffset, /* AllowNonInbounds */ false);
517 const Value *StoreBase = StorePtr->stripAndAccumulateConstantOffsets(
518 DL, StoreOffset, /* AllowNonInbounds */ false);
519 if (LoadBase != StoreBase)
520 return false;
521 auto LoadAccessSize = LocationSize::precise(DL.getTypeStoreSize(LoadTy));
522 auto StoreAccessSize = LocationSize::precise(DL.getTypeStoreSize(StoreTy));
523 ConstantRange LoadRange(LoadOffset,
524 LoadOffset + LoadAccessSize.toRaw());
525 ConstantRange StoreRange(StoreOffset,
526 StoreOffset + StoreAccessSize.toRaw());
527 return LoadRange.intersectWith(StoreRange).isEmptySet();
528}
529
531 Type *AccessTy, bool AtLeastAtomic,
532 const DataLayout &DL, bool *IsLoadCSE) {
533 // If this is a load of Ptr, the loaded value is available.
534 // (This is true even if the load is volatile or atomic, although
535 // those cases are unlikely.)
536 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
537 // We can value forward from an atomic to a non-atomic, but not the
538 // other way around.
539 if (LI->isAtomic() < AtLeastAtomic)
540 return nullptr;
541
542 Value *LoadPtr = LI->getPointerOperand()->stripPointerCasts();
543 if (!AreEquivalentAddressValues(LoadPtr, Ptr))
544 return nullptr;
545
546 if (CastInst::isBitOrNoopPointerCastable(LI->getType(), AccessTy, DL)) {
547 if (IsLoadCSE)
548 *IsLoadCSE = true;
549 return LI;
550 }
551 }
552
553 // If this is a store through Ptr, the value is available!
554 // (This is true even if the store is volatile or atomic, although
555 // those cases are unlikely.)
556 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
557 // We can value forward from an atomic to a non-atomic, but not the
558 // other way around.
559 if (SI->isAtomic() < AtLeastAtomic)
560 return nullptr;
561
562 Value *StorePtr = SI->getPointerOperand()->stripPointerCasts();
563 if (!AreEquivalentAddressValues(StorePtr, Ptr))
564 return nullptr;
565
566 if (IsLoadCSE)
567 *IsLoadCSE = false;
568
569 Value *Val = SI->getValueOperand();
570 if (CastInst::isBitOrNoopPointerCastable(Val->getType(), AccessTy, DL))
571 return Val;
572
573 TypeSize StoreSize = DL.getTypeSizeInBits(Val->getType());
574 TypeSize LoadSize = DL.getTypeSizeInBits(AccessTy);
575 if (TypeSize::isKnownLE(LoadSize, StoreSize))
576 if (auto *C = dyn_cast<Constant>(Val))
577 return ConstantFoldLoadFromConst(C, AccessTy, DL);
578 }
579
580 if (auto *MSI = dyn_cast<MemSetInst>(Inst)) {
581 // Don't forward from (non-atomic) memset to atomic load.
582 if (AtLeastAtomic)
583 return nullptr;
584
585 // Only handle constant memsets.
586 auto *Val = dyn_cast<ConstantInt>(MSI->getValue());
587 auto *Len = dyn_cast<ConstantInt>(MSI->getLength());
588 if (!Val || !Len)
589 return nullptr;
590
591 // TODO: Handle offsets.
592 Value *Dst = MSI->getDest();
594 return nullptr;
595
596 if (IsLoadCSE)
597 *IsLoadCSE = false;
598
599 TypeSize LoadTypeSize = DL.getTypeSizeInBits(AccessTy);
600 if (LoadTypeSize.isScalable())
601 return nullptr;
602
603 // Make sure the read bytes are contained in the memset.
604 uint64_t LoadSize = LoadTypeSize.getFixedValue();
605 if ((Len->getValue() * 8).ult(LoadSize))
606 return nullptr;
607
608 APInt Splat = LoadSize >= 8 ? APInt::getSplat(LoadSize, Val->getValue())
609 : Val->getValue().trunc(LoadSize);
610 ConstantInt *SplatC = ConstantInt::get(MSI->getContext(), Splat);
611 if (CastInst::isBitOrNoopPointerCastable(SplatC->getType(), AccessTy, DL))
612 return SplatC;
613
614 return nullptr;
615 }
616
617 return nullptr;
618}
619
621 const MemoryLocation &Loc, Type *AccessTy, bool AtLeastAtomic,
622 BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan,
623 BatchAAResults *AA, bool *IsLoadCSE, unsigned *NumScanedInst) {
624 if (MaxInstsToScan == 0)
625 MaxInstsToScan = ~0U;
626
627 const DataLayout &DL = ScanBB->getDataLayout();
628 const Value *StrippedPtr = Loc.Ptr->stripPointerCasts();
629
630 while (ScanFrom != ScanBB->begin()) {
631 // We must ignore debug info directives when counting (otherwise they
632 // would affect codegen).
633 Instruction *Inst = &*--ScanFrom;
634 if (Inst->isDebugOrPseudoInst())
635 continue;
636
637 // Restore ScanFrom to expected value in case next test succeeds
638 ScanFrom++;
639
640 if (NumScanedInst)
641 ++(*NumScanedInst);
642
643 // Don't scan huge blocks.
644 if (MaxInstsToScan-- == 0)
645 return nullptr;
646
647 --ScanFrom;
648
649 if (Value *Available = getAvailableLoadStore(Inst, StrippedPtr, AccessTy,
650 AtLeastAtomic, DL, IsLoadCSE))
651 return Available;
652
653 // Try to get the store size for the type.
654 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
655 Value *StorePtr = SI->getPointerOperand()->stripPointerCasts();
656
657 // If both StrippedPtr and StorePtr reach all the way to an alloca or
658 // global and they are different, ignore the store. This is a trivial form
659 // of alias analysis that is important for reg2mem'd code.
660 if ((isa<AllocaInst>(StrippedPtr) || isa<GlobalVariable>(StrippedPtr)) &&
661 (isa<AllocaInst>(StorePtr) || isa<GlobalVariable>(StorePtr)) &&
662 StrippedPtr != StorePtr)
663 continue;
664
665 if (!AA) {
666 // When AA isn't available, but if the load and the store have the same
667 // base, constant offsets and non-overlapping access ranges, ignore the
668 // store. This is a simple form of alias analysis that is used by the
669 // inliner. FIXME: use BasicAA if possible.
671 Loc.Ptr, AccessTy, SI->getPointerOperand(),
672 SI->getValueOperand()->getType(), DL))
673 continue;
674 } else {
675 // If we have alias analysis and it says the store won't modify the
676 // loaded value, ignore the store.
677 if (!isModSet(AA->getModRefInfo(SI, Loc)))
678 continue;
679 }
680
681 // Otherwise the store that may or may not alias the pointer, bail out.
682 ++ScanFrom;
683 return nullptr;
684 }
685
686 // If this is some other instruction that may clobber Ptr, bail out.
687 if (Inst->mayWriteToMemory()) {
688 // If alias analysis claims that it really won't modify the load,
689 // ignore it.
690 if (AA && !isModSet(AA->getModRefInfo(Inst, Loc)))
691 continue;
692
693 // May modify the pointer, bail out.
694 ++ScanFrom;
695 return nullptr;
696 }
697 }
698
699 // Got to the start of the block, we didn't find it, but are done for this
700 // block.
701 return nullptr;
702}
703
705 bool *IsLoadCSE,
706 unsigned MaxInstsToScan) {
707 const DataLayout &DL = Load->getDataLayout();
708 Value *StrippedPtr = Load->getPointerOperand()->stripPointerCasts();
709 BasicBlock *ScanBB = Load->getParent();
710 Type *AccessTy = Load->getType();
711 bool AtLeastAtomic = Load->isAtomic();
712
713 if (!Load->isUnordered())
714 return nullptr;
715
716 // Try to find an available value first, and delay expensive alias analysis
717 // queries until later.
718 Value *Available = nullptr;
719 SmallVector<Instruction *> MustNotAliasInsts;
720 for (Instruction &Inst : make_range(++Load->getReverseIterator(),
721 ScanBB->rend())) {
722 if (Inst.isDebugOrPseudoInst())
723 continue;
724
725 if (MaxInstsToScan-- == 0)
726 return nullptr;
727
728 Available = getAvailableLoadStore(&Inst, StrippedPtr, AccessTy,
729 AtLeastAtomic, DL, IsLoadCSE);
730 if (Available)
731 break;
732
733 if (Inst.mayWriteToMemory())
734 MustNotAliasInsts.push_back(&Inst);
735 }
736
737 // If we found an available value, ensure that the instructions in between
738 // did not modify the memory location.
739 if (Available) {
741 for (Instruction *Inst : MustNotAliasInsts)
742 if (isModSet(AA.getModRefInfo(Inst, Loc)))
743 return nullptr;
744 }
745
746 return Available;
747}
748
749// Returns true if a use is either in an ICmp/PtrToInt or a Phi/Select that only
750// feeds into them.
751static bool isPointerUseReplacable(const Use &U) {
752 unsigned Limit = 40;
753 SmallVector<const User *> Worklist({U.getUser()});
755
756 while (!Worklist.empty() && --Limit) {
757 auto *User = Worklist.pop_back_val();
758 if (!Visited.insert(User).second)
759 continue;
760 if (isa<ICmpInst, PtrToIntInst>(User))
761 continue;
762 if (isa<PHINode, SelectInst>(User))
763 Worklist.append(User->user_begin(), User->user_end());
764 else
765 return false;
766 }
767
768 return Limit != 0;
769}
770
771// Returns true if `To` is a null pointer, constant dereferenceable pointer or
772// both pointers have the same underlying objects.
773static bool isPointerAlwaysReplaceable(const Value *From, const Value *To,
774 const DataLayout &DL) {
775 // This is not strictly correct, but we do it for now to retain important
776 // optimizations.
777 if (isa<ConstantPointerNull>(To))
778 return true;
779 if (isa<Constant>(To) &&
781 return true;
784}
785
787 const DataLayout &DL) {
788 assert(U->getType() == To->getType() && "values must have matching types");
789 // Not a pointer, just return true.
790 if (!To->getType()->isPointerTy())
791 return true;
792
793 if (isPointerAlwaysReplaceable(&*U, To, DL))
794 return true;
795 return isPointerUseReplacable(U);
796}
797
799 const DataLayout &DL) {
800 assert(From->getType() == To->getType() && "values must have matching types");
801 // Not a pointer, just return true.
802 if (!From->getType()->isPointerTy())
803 return true;
804
806}
807
811 for (BasicBlock *BB : L->blocks()) {
812 for (Instruction &I : *BB) {
813 if (auto *LI = dyn_cast<LoadInst>(&I)) {
814 if (!isDereferenceableAndAlignedInLoop(LI, L, *SE, *DT, AC, Predicates))
815 return false;
816 } else if (I.mayReadFromMemory() || I.mayWriteToMemory() || I.mayThrow())
817 return false;
818 }
819 }
820 return true;
821}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
uint64_t Size
@ Available
We know the block is fully available. This is a fixpoint.
Hexagon Common GEP
static const unsigned MaxDepth
static bool isAligned(const Value *Base, Align Alignment, const DataLayout &DL)
Definition: Loads.cpp:28
static bool AreEquivalentAddressValues(const Value *A, const Value *B)
Test if A and B will obviously have the same value.
Definition: Loads.cpp:255
static bool isDereferenceableAndAlignedPointer(const Value *V, Align Alignment, const APInt &Size, const DataLayout &DL, const Instruction *CtxI, AssumptionCache *AC, const DominatorTree *DT, const TargetLibraryInfo *TLI, SmallPtrSetImpl< const Value * > &Visited, unsigned MaxDepth)
Test if V is always a pointer to allocated and suitably aligned memory for a simple load or store.
Definition: Loads.cpp:35
static bool isPointerAlwaysReplaceable(const Value *From, const Value *To, const DataLayout &DL)
Definition: Loads.cpp:773
static bool areNonOverlapSameBaseLoadAndStore(const Value *LoadPtr, Type *LoadTy, const Value *StorePtr, Type *StoreTy, const DataLayout &DL)
Definition: Loads.cpp:508
static bool isPointerUseReplacable(const Use &U)
Definition: Loads.cpp:751
static Value * getAvailableLoadStore(Instruction *Inst, const Value *Ptr, Type *AccessTy, bool AtLeastAtomic, const DataLayout &DL, bool *IsLoadCSE)
Definition: Loads.cpp:530
static bool suppressSpeculativeLoadForSanitizers(const Instruction &CtxI)
Definition: Loads.cpp:360
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This file provides utility analysis objects describing memory locations.
if(PassOpts->AAPipeline)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Class for arbitrary precision integers.
Definition: APInt.h:78
bool sgt(const APInt &RHS) const
Signed greater than comparison.
Definition: APInt.h:1201
APInt urem(const APInt &RHS) const
Unsigned remainder operation.
Definition: APInt.cpp:1640
APInt uadd_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1909
static APInt getSplat(unsigned NewLen, const APInt &V)
Return a value containing V broadcasted over NewLen bits.
Definition: APInt.cpp:624
bool getBoolValue() const
Convert APInt to a boolean value.
Definition: APInt.h:471
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1221
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:448
const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
Definition: BasicBlock.cpp:296
reverse_iterator rend()
Definition: BasicBlock.h:466
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:177
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
static bool isBitOrNoopPointerCastable(Type *SrcTy, Type *DestTy, const DataLayout &DL)
Check whether a bitcast, inttoptr, or ptrtoint cast between these types is valid and a no-op.
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
This class represents a range of values.
Definition: ConstantRange.h:47
bool isEmptySet() const
Return true if this set contains no members.
ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:63
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
Represents calls to the gc.relocate intrinsic.
bool isDebugOrPseudoInst() const LLVM_READONLY
Return true if the instruction is a DbgInfoIntrinsic or PseudoProbeInst.
bool mayWriteToMemory() const LLVM_READONLY
Return true if this instruction may modify memory.
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:72
const DataLayout & getDataLayout() const
Get the data layout of the module this instruction belongs to.
Definition: Instruction.cpp:76
An instruction for reading from memory.
Definition: Instructions.h:176
Value * getPointerOperand()
Definition: Instructions.h:255
bool isUnordered() const
Definition: Instructions.h:249
Align getAlign() const
Return the alignment of the access that is being performed.
Definition: Instructions.h:211
static LocationSize precise(uint64_t Value)
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:39
Representation for a specific memory location.
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
const Value * Ptr
The address of the start of the location.
The main scalar evolution driver.
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
unsigned getSmallConstantMaxTripCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Returns the upper bound of the loop trip count as a normal unsigned value.
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
This class represents the LLVM 'select' instruction.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:363
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:384
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:519
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:573
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:805
void push_back(const T &Elt)
Definition: SmallVector.h:413
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1196
An instruction for storing to memory.
Definition: Instructions.h:292
Provides information about what library functions are available for the current target.
static constexpr TypeSize getFixed(ScalarTy ExactSize)
Definition: TypeSize.h:345
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:264
bool isSized(SmallPtrSetImpl< Type * > *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:310
bool isScalableTy(SmallPtrSetImpl< const Type * > &Visited) const
Return true if this is a type whose size is a known multiple of vscale.
static IntegerType * getInt8Ty(LLVMContext &C)
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
user_iterator user_begin()
Definition: Value.h:397
const Value * stripAndAccumulateConstantOffsets(const DataLayout &DL, APInt &Offset, bool AllowNonInbounds, bool AllowInvariantGroup=false, function_ref< bool(Value &Value, APInt &Offset)> ExternalAnalysis=nullptr) const
Accumulate the constant offset this value has compared to a base pointer.
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:694
user_iterator user_end()
Definition: Value.h:405
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:1075
constexpr ScalarTy getFixedValue() const
Definition: TypeSize.h:202
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
Definition: TypeSize.h:171
const ParentTy * getParent() const
Definition: ilist_node.h:32
self_iterator getIterator()
Definition: ilist_node.h:132
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:480
bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI, const DominatorTree *DT=nullptr, bool AllowEphemerals=false)
Return true if it is valid to use the assumptions provided by an assume intrinsic,...
const Value * getArgumentAliasingToReturnedPointer(const CallBase *Call, bool MustPreserveNullness)
This function returns call pointer argument that is considered the same by aliasing rules.
bool isDereferenceableAndAlignedPointer(const Value *V, Type *Ty, Align Alignment, const DataLayout &DL, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Returns true if V is always a dereferenceable pointer with alignment greater or equal than requested.
Definition: Loads.cpp:214
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Value * findAvailablePtrLoadStore(const MemoryLocation &Loc, Type *AccessTy, bool AtLeastAtomic, BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan, BatchAAResults *AA, bool *IsLoadCSE, unsigned *NumScanedInst)
Scan backwards to see if we have the value of the given pointer available locally within a small numb...
Definition: Loads.cpp:620
bool mustSuppressSpeculation(const LoadInst &LI)
Return true if speculation of the given load must be suppressed to avoid ordering or interfering with...
Definition: Loads.cpp:369
Value * FindAvailableLoadedValue(LoadInst *Load, BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan=DefMaxInstsToScan, BatchAAResults *AA=nullptr, bool *IsLoadCSE=nullptr, unsigned *NumScanedInst=nullptr)
Scan backwards to see if we have the value of the given load available locally within a small number ...
Definition: Loads.cpp:491
bool isDereferenceableReadOnlyLoop(Loop *L, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Return true if the loop L cannot fault on any iteration and only contains read-only memory accesses.
Definition: Loads.cpp:808
RetainedKnowledge getKnowledgeForValue(const Value *V, ArrayRef< Attribute::AttrKind > AttrKinds, AssumptionCache *AC=nullptr, function_ref< bool(RetainedKnowledge, Instruction *, const CallBase::BundleOpInfo *)> Filter=[](auto...) { return true;})
Return a valid Knowledge associated to the Value V if its Attribute kind is in AttrKinds and it match...
bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL, const TargetLibraryInfo *TLI, ObjectSizeOpts Opts={})
Compute the size of the object pointed by Ptr.
bool canReplacePointersInUseIfEqual(const Use &U, const Value *To, const DataLayout &DL)
Definition: Loads.cpp:786
bool canReplacePointersIfEqual(const Value *From, const Value *To, const DataLayout &DL)
Returns true if a pointer value From can be replaced with another pointer value \To if they are deeme...
Definition: Loads.cpp:798
bool isModSet(const ModRefInfo MRI)
Definition: ModRef.h:48
bool isSafeToLoadUnconditionally(Value *V, Align Alignment, const APInt &Size, const DataLayout &DL, Instruction *ScanFrom, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if we know that executing a load from this value cannot trap.
Definition: Loads.cpp:384
Constant * ConstantFoldLoadFromConst(Constant *C, Type *Ty, const APInt &Offset, const DataLayout &DL)
Extract value of C at the given Offset reinterpreted as Ty.
cl::opt< unsigned > DefMaxInstsToScan
The default number of maximum instructions to scan in the block, used by FindAvailableLoadedValue().
bool isKnownNonZero(const Value *V, const SimplifyQuery &Q, unsigned Depth=0)
Return true if the given value is known to be non-zero when defined.
const Value * getUnderlyingObjectAggressive(const Value *V)
Like getUnderlyingObject(), but will try harder to find a single underlying object.
bool isDereferenceablePointer(const Value *V, Type *Ty, const DataLayout &DL, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if this is always a dereferenceable pointer.
Definition: Loads.cpp:234
bool isDereferenceableAndAlignedInLoop(LoadInst *LI, Loop *L, ScalarEvolution &SE, DominatorTree &DT, AssumptionCache *AC=nullptr, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Return true if we can prove that the given load (which is assumed to be within the specified loop) wo...
Definition: Loads.cpp:275
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
uint64_t value() const
This is a hole in the type system and should not be abused.
Definition: Alignment.h:85
Various options to control the behavior of getObjectSize.
bool NullIsUnknownSize
If this is true, null pointers in address space 0 will be treated as though they can't be evaluated.
bool RoundToAlign
Whether to round the result up to the alignment of allocas, byval arguments, and global variables.
Represent one information held inside an operand bundle of an llvm.assume.