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