LLVM 18.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 uint64_t LoadSize = 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 LoadSize <= DL.getTypeStoreSize(AccessedTy))
418 return true;
419
420 if (AreEquivalentAddressValues(AccessedPtr->stripPointerCasts(), V) &&
421 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 *ScanBB,
455 BasicBlock::iterator &ScanFrom,
456 unsigned MaxInstsToScan,
457 AAResults *AA, bool *IsLoad,
458 unsigned *NumScanedInst) {
459 // Don't CSE load that is volatile or anything stronger than unordered.
460 if (!Load->isUnordered())
461 return nullptr;
462
464 return findAvailablePtrLoadStore(Loc, Load->getType(), Load->isAtomic(),
465 ScanBB, ScanFrom, MaxInstsToScan, AA, IsLoad,
466 NumScanedInst);
467}
468
469// Check if the load and the store have the same base, constant offsets and
470// non-overlapping access ranges.
471static bool areNonOverlapSameBaseLoadAndStore(const Value *LoadPtr,
472 Type *LoadTy,
473 const Value *StorePtr,
474 Type *StoreTy,
475 const DataLayout &DL) {
476 APInt LoadOffset(DL.getIndexTypeSizeInBits(LoadPtr->getType()), 0);
477 APInt StoreOffset(DL.getIndexTypeSizeInBits(StorePtr->getType()), 0);
478 const Value *LoadBase = LoadPtr->stripAndAccumulateConstantOffsets(
479 DL, LoadOffset, /* AllowNonInbounds */ false);
480 const Value *StoreBase = StorePtr->stripAndAccumulateConstantOffsets(
481 DL, StoreOffset, /* AllowNonInbounds */ false);
482 if (LoadBase != StoreBase)
483 return false;
484 auto LoadAccessSize = LocationSize::precise(DL.getTypeStoreSize(LoadTy));
485 auto StoreAccessSize = LocationSize::precise(DL.getTypeStoreSize(StoreTy));
486 ConstantRange LoadRange(LoadOffset,
487 LoadOffset + LoadAccessSize.toRaw());
488 ConstantRange StoreRange(StoreOffset,
489 StoreOffset + StoreAccessSize.toRaw());
490 return LoadRange.intersectWith(StoreRange).isEmptySet();
491}
492
494 Type *AccessTy, bool AtLeastAtomic,
495 const DataLayout &DL, bool *IsLoadCSE) {
496 // If this is a load of Ptr, the loaded value is available.
497 // (This is true even if the load is volatile or atomic, although
498 // those cases are unlikely.)
499 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
500 // We can value forward from an atomic to a non-atomic, but not the
501 // other way around.
502 if (LI->isAtomic() < AtLeastAtomic)
503 return nullptr;
504
505 Value *LoadPtr = LI->getPointerOperand()->stripPointerCasts();
506 if (!AreEquivalentAddressValues(LoadPtr, Ptr))
507 return nullptr;
508
509 if (CastInst::isBitOrNoopPointerCastable(LI->getType(), AccessTy, DL)) {
510 if (IsLoadCSE)
511 *IsLoadCSE = true;
512 return LI;
513 }
514 }
515
516 // If this is a store through Ptr, the value is available!
517 // (This is true even if the store is volatile or atomic, although
518 // those cases are unlikely.)
519 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
520 // We can value forward from an atomic to a non-atomic, but not the
521 // other way around.
522 if (SI->isAtomic() < AtLeastAtomic)
523 return nullptr;
524
525 Value *StorePtr = SI->getPointerOperand()->stripPointerCasts();
526 if (!AreEquivalentAddressValues(StorePtr, Ptr))
527 return nullptr;
528
529 if (IsLoadCSE)
530 *IsLoadCSE = false;
531
532 Value *Val = SI->getValueOperand();
533 if (CastInst::isBitOrNoopPointerCastable(Val->getType(), AccessTy, DL))
534 return Val;
535
536 TypeSize StoreSize = DL.getTypeSizeInBits(Val->getType());
537 TypeSize LoadSize = DL.getTypeSizeInBits(AccessTy);
538 if (TypeSize::isKnownLE(LoadSize, StoreSize))
539 if (auto *C = dyn_cast<Constant>(Val))
540 return ConstantFoldLoadFromConst(C, AccessTy, DL);
541 }
542
543 if (auto *MSI = dyn_cast<MemSetInst>(Inst)) {
544 // Don't forward from (non-atomic) memset to atomic load.
545 if (AtLeastAtomic)
546 return nullptr;
547
548 // Only handle constant memsets.
549 auto *Val = dyn_cast<ConstantInt>(MSI->getValue());
550 auto *Len = dyn_cast<ConstantInt>(MSI->getLength());
551 if (!Val || !Len)
552 return nullptr;
553
554 // TODO: Handle offsets.
555 Value *Dst = MSI->getDest();
557 return nullptr;
558
559 if (IsLoadCSE)
560 *IsLoadCSE = false;
561
562 TypeSize LoadTypeSize = DL.getTypeSizeInBits(AccessTy);
563 if (LoadTypeSize.isScalable())
564 return nullptr;
565
566 // Make sure the read bytes are contained in the memset.
567 uint64_t LoadSize = LoadTypeSize.getFixedValue();
568 if ((Len->getValue() * 8).ult(LoadSize))
569 return nullptr;
570
571 APInt Splat = LoadSize >= 8 ? APInt::getSplat(LoadSize, Val->getValue())
572 : Val->getValue().trunc(LoadSize);
573 ConstantInt *SplatC = ConstantInt::get(MSI->getContext(), Splat);
574 if (CastInst::isBitOrNoopPointerCastable(SplatC->getType(), AccessTy, DL))
575 return SplatC;
576
577 return nullptr;
578 }
579
580 return nullptr;
581}
582
584 const MemoryLocation &Loc, Type *AccessTy, bool AtLeastAtomic,
585 BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan,
586 AAResults *AA, bool *IsLoadCSE, unsigned *NumScanedInst) {
587 if (MaxInstsToScan == 0)
588 MaxInstsToScan = ~0U;
589
590 const DataLayout &DL = ScanBB->getModule()->getDataLayout();
591 const Value *StrippedPtr = Loc.Ptr->stripPointerCasts();
592
593 while (ScanFrom != ScanBB->begin()) {
594 // We must ignore debug info directives when counting (otherwise they
595 // would affect codegen).
596 Instruction *Inst = &*--ScanFrom;
597 if (Inst->isDebugOrPseudoInst())
598 continue;
599
600 // Restore ScanFrom to expected value in case next test succeeds
601 ScanFrom++;
602
603 if (NumScanedInst)
604 ++(*NumScanedInst);
605
606 // Don't scan huge blocks.
607 if (MaxInstsToScan-- == 0)
608 return nullptr;
609
610 --ScanFrom;
611
612 if (Value *Available = getAvailableLoadStore(Inst, StrippedPtr, AccessTy,
613 AtLeastAtomic, DL, IsLoadCSE))
614 return Available;
615
616 // Try to get the store size for the type.
617 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
618 Value *StorePtr = SI->getPointerOperand()->stripPointerCasts();
619
620 // If both StrippedPtr and StorePtr reach all the way to an alloca or
621 // global and they are different, ignore the store. This is a trivial form
622 // of alias analysis that is important for reg2mem'd code.
623 if ((isa<AllocaInst>(StrippedPtr) || isa<GlobalVariable>(StrippedPtr)) &&
624 (isa<AllocaInst>(StorePtr) || isa<GlobalVariable>(StorePtr)) &&
625 StrippedPtr != StorePtr)
626 continue;
627
628 if (!AA) {
629 // When AA isn't available, but if the load and the store have the same
630 // base, constant offsets and non-overlapping access ranges, ignore the
631 // store. This is a simple form of alias analysis that is used by the
632 // inliner. FIXME: use BasicAA if possible.
634 Loc.Ptr, AccessTy, SI->getPointerOperand(),
635 SI->getValueOperand()->getType(), DL))
636 continue;
637 } else {
638 // If we have alias analysis and it says the store won't modify the
639 // loaded value, ignore the store.
640 if (!isModSet(AA->getModRefInfo(SI, Loc)))
641 continue;
642 }
643
644 // Otherwise the store that may or may not alias the pointer, bail out.
645 ++ScanFrom;
646 return nullptr;
647 }
648
649 // If this is some other instruction that may clobber Ptr, bail out.
650 if (Inst->mayWriteToMemory()) {
651 // If alias analysis claims that it really won't modify the load,
652 // ignore it.
653 if (AA && !isModSet(AA->getModRefInfo(Inst, Loc)))
654 continue;
655
656 // May modify the pointer, bail out.
657 ++ScanFrom;
658 return nullptr;
659 }
660 }
661
662 // Got to the start of the block, we didn't find it, but are done for this
663 // block.
664 return nullptr;
665}
666
668 bool *IsLoadCSE,
669 unsigned MaxInstsToScan) {
670 const DataLayout &DL = Load->getModule()->getDataLayout();
671 Value *StrippedPtr = Load->getPointerOperand()->stripPointerCasts();
672 BasicBlock *ScanBB = Load->getParent();
673 Type *AccessTy = Load->getType();
674 bool AtLeastAtomic = Load->isAtomic();
675
676 if (!Load->isUnordered())
677 return nullptr;
678
679 // Try to find an available value first, and delay expensive alias analysis
680 // queries until later.
681 Value *Available = nullptr;
682 SmallVector<Instruction *> MustNotAliasInsts;
683 for (Instruction &Inst : make_range(++Load->getReverseIterator(),
684 ScanBB->rend())) {
685 if (Inst.isDebugOrPseudoInst())
686 continue;
687
688 if (MaxInstsToScan-- == 0)
689 return nullptr;
690
691 Available = getAvailableLoadStore(&Inst, StrippedPtr, AccessTy,
692 AtLeastAtomic, DL, IsLoadCSE);
693 if (Available)
694 break;
695
696 if (Inst.mayWriteToMemory())
697 MustNotAliasInsts.push_back(&Inst);
698 }
699
700 // If we found an available value, ensure that the instructions in between
701 // did not modify the memory location.
702 if (Available) {
704 for (Instruction *Inst : MustNotAliasInsts)
705 if (isModSet(AA.getModRefInfo(Inst, Loc)))
706 return nullptr;
707 }
708
709 return Available;
710}
711
713 Instruction *CtxI) {
714 Type *Ty = A->getType();
715 assert(Ty == B->getType() && Ty->isPointerTy() &&
716 "values must have matching pointer types");
717
718 // NOTE: The checks in the function are incomplete and currently miss illegal
719 // cases! The current implementation is a starting point and the
720 // implementation should be made stricter over time.
721 if (auto *C = dyn_cast<Constant>(B)) {
722 // Do not allow replacing a pointer with a constant pointer, unless it is
723 // either null or at least one byte is dereferenceable.
724 APInt OneByte(DL.getPointerTypeSizeInBits(Ty), 1);
725 return C->isNullValue() ||
726 isDereferenceableAndAlignedPointer(B, Align(1), OneByte, DL, CtxI);
727 }
728
729 return true;
730}
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:471
static Value * getAvailableLoadStore(Instruction *Inst, const Value *Ptr, Type *AccessTy, bool AtLeastAtomic, const DataLayout &DL, bool *IsLoadCSE)
Definition: Loads.cpp:493
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())
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
Check whether or not an instruction may read or write the optionally specified memory location.
Class for arbitrary precision integers.
Definition: APInt.h:76
bool sgt(const APInt &RHS) const
Signed greater than comparison.
Definition: APInt.h:1173
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:1193
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:437
reverse_iterator rend()
Definition: BasicBlock.h:455
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:173
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:328
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:78
IntegerType * getType() const
getType - Specialize the getType() method to always return an IntegerType, which reduces the amount o...
Definition: Constants.h:176
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:888
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:165
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:71
const BasicBlock * getParent() const
Definition: Instruction.h:139
An instruction for reading from memory.
Definition: Instructions.h:177
Value * getPointerOperand()
Definition: Instructions.h:264
Align getAlign() const
Return the alignment of the access that is being performed.
Definition: Instructions.h:220
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:275
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:345
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:366
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
An instruction for storing to memory.
Definition: Instructions.h:301
Provides information about what library functions are available for the current target.
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:189
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
Definition: TypeSize.h:173
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:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:440
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.
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 * FindAvailableLoadedValue(LoadInst *Load, BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan=DefMaxInstsToScan, AAResults *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
Value * findAvailablePtrLoadStore(const MemoryLocation &Loc, Type *AccessTy, bool AtLeastAtomic, BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan, AAResults *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:583
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:712
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
bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI, const DominatorTree *DT=nullptr)
Return true if it is valid to use the assumptions provided by an assume intrinsic,...
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.