1//===- Loads.cpp - Local load analysis ------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines simple local analyses for load instructions.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/Analysis/Loads.h"
14#include "llvm/Analysis/AliasAnalysis.h"
15#include "llvm/Analysis/AssumeBundleQueries.h"
16#include "llvm/Analysis/LoopAccessAnalysis.h"
17#include "llvm/Analysis/LoopInfo.h"
18#include "llvm/Analysis/MemoryBuiltins.h"
19#include "llvm/Analysis/MemoryLocation.h"
20#include "llvm/Analysis/ScalarEvolution.h"
21#include "llvm/Analysis/ScalarEvolutionExpressions.h"
22#include "llvm/Analysis/ValueTracking.h"
23#include "llvm/IR/DataLayout.h"
24#include "llvm/IR/GetElementPtrTypeIterator.h"
25#include "llvm/IR/IntrinsicInst.h"
26#include "llvm/IR/Operator.h"
27
28using namespace llvm;
29
30static bool isAligned(const Value *Base, Align Alignment,
31 const DataLayout &DL) {
32 return Base->getPointerAlignment(DL) >= Alignment;
33}
34
35static bool isDereferenceableAndAlignedPointerViaAssumption(
36 const Value *Ptr, Align Alignment, const SimplifyQuery &SQ, bool IgnoreFree,
37 function_ref<bool(const RetainedKnowledge &RK)> CheckSize) {
38 if (!SQ.CtxI)
39 return false;
40 // Look through assumes to see if both dereferenceability and alignment can
41 // be proven by an assume if needed.
42 bool PtrCanBeFreed = Ptr->canBeFreed() && !IgnoreFree;
43 bool IsAligned = Ptr->getPointerAlignment(DL: SQ.DL) >= Alignment;
44 bool IsDerefable = false;
45 return getKnowledgeForValue(
46 V: Ptr, AttrKinds: {Attribute::Dereferenceable, Attribute::Alignment}, AC&: *SQ.AC,
47 Filter: [&](RetainedKnowledge RK, Instruction *Assume, auto) {
48 if (!isValidAssumeForContext(I: Assume, CtxI: SQ.CtxI, DT: SQ.DT))
49 return false;
50 if (RK.AttrKind == Attribute::Alignment) {
51 IsAligned |= RK.ArgValue >= Alignment.value();
52 } else {
53 assert(RK.AttrKind == Attribute::Dereferenceable);
54 // Dereferenceable information from assumptions is only valid if the
55 // value cannot be freed between the assumption and use.
56 if (!IsDerefable &&
57 (!PtrCanBeFreed || willNotFreeBetween(Assume, CtxI: SQ.CtxI, DT: SQ.DT)) &&
58 CheckSize(RK))
59 IsDerefable = true;
60 }
61 // Stop looking if we have proven both necessary facts.
62 return IsAligned && IsDerefable;
63 });
64}
65
66/// Test if V is always a pointer to allocated and suitably aligned memory for
67/// a simple load or store.
68static bool isDereferenceableAndAlignedPointer(
69 const Value *V, Align Alignment, const APInt &Size, const SimplifyQuery &SQ,
70 bool IgnoreFree, SmallPtrSetImpl<const Value *> &Visited,
71 unsigned MaxDepth) {
72 assert(V->getType()->isPointerTy() && "Base must be pointer");
73
74 // Recursion limit.
75 if (MaxDepth-- == 0)
76 return false;
77
78 // Already visited? Bail out, we've likely hit unreachable code.
79 if (!Visited.insert(Ptr: V).second)
80 return false;
81
82 // Note that it is not safe to speculate into a malloc'd region because
83 // malloc may return null.
84
85 // For GEPs, determine if the indexing lands within the allocated object.
86 if (const GEPOperator *GEP = dyn_cast<GEPOperator>(Val: V)) {
87 const Value *Base = GEP->getPointerOperand();
88
89 APInt Offset(SQ.DL.getIndexTypeSizeInBits(Ty: GEP->getType()), 0);
90 if (!GEP->accumulateConstantOffset(DL: SQ.DL, Offset) || Offset.isNegative() ||
91 !Offset.urem(RHS: APInt(Offset.getBitWidth(), Alignment.value()))
92 .isMinValue())
93 return false;
94
95 // If the base pointer is dereferenceable for Offset+Size bytes, then the
96 // GEP (== Base + Offset) is dereferenceable for Size bytes. If the base
97 // pointer is aligned to Align bytes, and the Offset is divisible by Align
98 // then the GEP (== Base + Offset == k_0 * Align + k_1 * Align) is also
99 // aligned to Align bytes.
100
101 // Offset and Size may have different bit widths if we have visited an
102 // addrspacecast, so we can't do arithmetic directly on the APInt values.
103 return isDereferenceableAndAlignedPointer(
104 V: Base, Alignment, Size: Offset + Size.sextOrTrunc(width: Offset.getBitWidth()), SQ,
105 IgnoreFree, Visited, MaxDepth);
106 }
107
108 // bitcast instructions are no-ops as far as dereferenceability is concerned.
109 if (const BitCastOperator *BC = dyn_cast<BitCastOperator>(Val: V)) {
110 if (BC->getSrcTy()->isPointerTy())
111 return isDereferenceableAndAlignedPointer(V: BC->getOperand(i_nocapture: 0), Alignment,
112 Size, SQ, IgnoreFree, Visited,
113 MaxDepth);
114 }
115
116 // Recurse into both hands of select.
117 if (const SelectInst *Sel = dyn_cast<SelectInst>(Val: V)) {
118 return isDereferenceableAndAlignedPointer(V: Sel->getTrueValue(), Alignment,
119 Size, SQ, IgnoreFree, Visited,
120 MaxDepth) &&
121 isDereferenceableAndAlignedPointer(V: Sel->getFalseValue(), Alignment,
122 Size, SQ, IgnoreFree, Visited,
123 MaxDepth);
124 }
125
126 auto IsKnownDeref = [&]() {
127 bool CheckForNonNull, CheckForFreed;
128 if (!Size.ule(RHS: V->getPointerDereferenceableBytes(DL: SQ.DL, CanBeNull&: CheckForNonNull,
129 CanBeFreed: &CheckForFreed)))
130 return false;
131 if (CheckForNonNull && !isKnownNonZero(V, Q: SQ))
132 return false;
133
134 auto *I = dyn_cast<Instruction>(Val: V);
135 if (CheckForFreed && !IgnoreFree) {
136 const Instruction *DefI;
137 if (I) {
138 // We don't want to consider frees by the instruction producing the
139 // pointer, so skip it if we can.
140 if (auto *II = dyn_cast<InvokeInst>(Val: V)) {
141 DefI = &II->getNormalDest()->front();
142 } else if (!I->isTerminator()) {
143 DefI = I->getNextNode();
144 } else {
145 DefI = I;
146 }
147 } else {
148 // For arguments, check frees from the start of the entry block.
149 DefI = &cast<Argument>(Val: V)->getParent()->getEntryBlock().front();
150 }
151
152 if (!SQ.CtxI || !willNotFreeBetween(Assume: DefI, CtxI: SQ.CtxI, DT: SQ.DT))
153 return false;
154 }
155
156 // When using something like !dereferenceable on a load, the
157 // dereferenceability may only be valid on a specific control-flow path.
158 // If the instruction doesn't dominate the context instruction, we're
159 // asking about dereferenceability under the assumption that the
160 // instruction has been speculated to the point of the context instruction,
161 // in which case we don't know if the dereferenceability info still holds.
162 // We don't bother handling allocas here, as they aren't speculatable
163 // anyway.
164 if (I && !isa<AllocaInst>(Val: I))
165 return SQ.CtxI && isValidAssumeForContext(I, CtxI: SQ.CtxI, DT: SQ.DT);
166 return true;
167 };
168 if (IsKnownDeref()) {
169 // As we recursed through GEPs to get here, we've incrementally checked
170 // that each step advanced by a multiple of the alignment. If our base is
171 // properly aligned, then the original offset accessed must also be.
172 return isAligned(Base: V, Alignment, DL: SQ.DL);
173 }
174
175 /// TODO refactor this function to be able to search independently for
176 /// Dereferencability and Alignment requirements.
177
178
179 if (const auto *Call = dyn_cast<CallBase>(Val: V)) {
180 if (auto *RP = getArgumentAliasingToReturnedPointer(
181 Call, /*MustPreserveOffset=*/true))
182 return isDereferenceableAndAlignedPointer(V: RP, Alignment, Size, SQ,
183 IgnoreFree, Visited, MaxDepth);
184
185 // If we have a call we can't recurse through, check to see if this is an
186 // allocation function for which we can establish an minimum object size.
187 // Such a minimum object size is analogous to a deref_or_null attribute in
188 // that we still need to prove the result non-null at point of use.
189 // NOTE: We can only use the object size as a base fact as we a) need to
190 // prove alignment too, and b) don't want the compile time impact of a
191 // separate recursive walk.
192 ObjectSizeOpts Opts;
193 // TODO: It may be okay to round to align, but that would imply that
194 // accessing slightly out of bounds was legal, and we're currently
195 // inconsistent about that. For the moment, be conservative.
196 Opts.RoundToAlign = false;
197 Opts.NullIsUnknownSize = true;
198 uint64_t ObjSize;
199 if (getObjectSize(Ptr: V, Size&: ObjSize, DL: SQ.DL, TLI: SQ.TLI, Opts)) {
200 APInt KnownDerefBytes(Size.getBitWidth(), ObjSize);
201 if (KnownDerefBytes.getBoolValue() && KnownDerefBytes.uge(RHS: Size) &&
202 isKnownNonZero(V, Q: SQ) && !V->canBeFreed()) {
203 // As we recursed through GEPs to get here, we've incrementally
204 // checked that each step advanced by a multiple of the alignment. If
205 // our base is properly aligned, then the original offset accessed
206 // must also be.
207 return isAligned(Base: V, Alignment, DL: SQ.DL);
208 }
209 }
210 }
211
212 // For gc.relocate, look through relocations
213 if (const GCRelocateInst *RelocateInst = dyn_cast<GCRelocateInst>(Val: V))
214 return isDereferenceableAndAlignedPointer(V: RelocateInst->getDerivedPtr(),
215 Alignment, Size, SQ, IgnoreFree,
216 Visited, MaxDepth);
217
218 if (const AddrSpaceCastOperator *ASC = dyn_cast<AddrSpaceCastOperator>(Val: V))
219 return isDereferenceableAndAlignedPointer(
220 V: ASC->getOperand(i_nocapture: 0), Alignment, Size, SQ, IgnoreFree, Visited, MaxDepth);
221
222 return SQ.AC &&
223 isDereferenceableAndAlignedPointerViaAssumption(
224 Ptr: V, Alignment, SQ, IgnoreFree, CheckSize: [Size](const RetainedKnowledge &RK) {
225 return RK.ArgValue >= Size.getZExtValue();
226 });
227}
228
229bool llvm::isDereferenceableAndAlignedPointer(const Value *V, Align Alignment,
230 const APInt &Size,
231 const SimplifyQuery &SQ,
232 bool IgnoreFree) {
233 // Note: At the moment, Size can be zero. This ends up being interpreted as
234 // a query of whether [Base, V] is dereferenceable and V is aligned (since
235 // that's what the implementation happened to do). It's unclear if this is
236 // the desired semantic, but at least SelectionDAG does exercise this case.
237
238 SmallPtrSet<const Value *, 32> Visited;
239 return ::isDereferenceableAndAlignedPointer(V, Alignment, Size, SQ,
240 IgnoreFree, Visited,
241 /*MaxDepth=*/16);
242}
243
244bool llvm::isDereferenceableAndAlignedPointer(const Value *V, Type *Ty,
245 Align Alignment,
246 const SimplifyQuery &SQ,
247 bool IgnoreFree) {
248 // For unsized types or scalable vectors we don't know exactly how many bytes
249 // are dereferenced, so bail out.
250 if (!Ty->isSized() || Ty->isScalableTy())
251 return false;
252
253 // When dereferenceability information is provided by a dereferenceable
254 // attribute, we know exactly how many bytes are dereferenceable. If we can
255 // determine the exact offset to the attributed variable, we can use that
256 // information here.
257
258 APInt AccessSize(SQ.DL.getPointerTypeSizeInBits(V->getType()),
259 SQ.DL.getTypeStoreSize(Ty));
260 return isDereferenceableAndAlignedPointer(V, Alignment, Size: AccessSize, SQ,
261 IgnoreFree);
262}
263
264bool llvm::isDereferenceablePointer(const Value *V, Type *Ty,
265 const SimplifyQuery &SQ, bool IgnoreFree) {
266 return isDereferenceableAndAlignedPointer(V, Ty, Alignment: Align(1), SQ, IgnoreFree);
267}
268
269bool llvm::isDereferenceablePointer(const Value *V, const APInt &Size,
270 const SimplifyQuery &Q, bool IgnoreFree) {
271 return isDereferenceableAndAlignedPointer(V, Alignment: Align(1), Size, SQ: Q, IgnoreFree);
272}
273
274/// Test if A and B will obviously have the same value.
275///
276/// This includes recognizing that %t0 and %t1 will have the same
277/// value in code like this:
278/// \code
279/// %t0 = getelementptr \@a, 0, 3
280/// store i32 0, i32* %t0
281/// %t1 = getelementptr \@a, 0, 3
282/// %t2 = load i32* %t1
283/// \endcode
284///
285static bool AreEquivalentAddressValues(const Value *A, const Value *B) {
286 // Test if the values are trivially equivalent.
287 if (A == B)
288 return true;
289
290 // Test if the values come from identical arithmetic instructions.
291 // Use isIdenticalToWhenDefined instead of isIdenticalTo because
292 // this function is only used when one address use dominates the
293 // other, which means that they'll always either have the same
294 // value or one of them will have an undefined value.
295 if (isa<CastInst>(Val: A) || isa<PHINode>(Val: A) || isa<GetElementPtrInst>(Val: A))
296 if (const Instruction *BI = dyn_cast<Instruction>(Val: B))
297 if (cast<Instruction>(Val: A)->isIdenticalToWhenDefined(I: BI))
298 return true;
299
300 // Otherwise they may not be equivalent.
301 return false;
302}
303
304bool llvm::isDereferenceableAndAlignedInLoop(
305 LoadInst *LI, Loop *L, ScalarEvolution &SE, DominatorTree &DT,
306 AssumptionCache *AC, SmallVectorImpl<const SCEVPredicate *> *Predicates) {
307 auto &DL = LI->getDataLayout();
308 Value *Ptr = LI->getPointerOperand();
309 const SCEV *PtrSCEV = SE.getSCEV(V: Ptr);
310 APInt EltSize(DL.getIndexTypeSizeInBits(Ty: Ptr->getType()),
311 DL.getTypeStoreSize(Ty: LI->getType()).getFixedValue());
312
313 // If given a uniform (i.e. non-varying) address, see if we can prove the
314 // access is safe within the loop w/o needing predication.
315 if (L->isLoopInvariant(V: Ptr))
316 return isDereferenceableAndAlignedPointer(
317 V: Ptr, Alignment: LI->getAlign(), Size: EltSize,
318 SQ: SimplifyQuery(DL, &DT, AC, &*L->getHeader()->getFirstNonPHIIt()));
319
320 const SCEV *EltSizeSCEV = SE.getConstant(Val: EltSize);
321 return isDereferenceableAndAlignedInLoop(PtrSCEV, Alignment: LI->getAlign(), EltSizeSCEV,
322 L, SE, DT, AC, Predicates);
323}
324
325bool llvm::isDereferenceableAndAlignedInLoop(
326 const SCEV *PtrSCEV, Align Alignment, const SCEV *EltSizeSCEV, Loop *L,
327 ScalarEvolution &SE, DominatorTree &DT, AssumptionCache *AC,
328 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
329 auto *AddRec = dyn_cast<SCEVAddRecExpr>(Val: PtrSCEV);
330
331 // Check to see if we have a repeating access pattern and it's possible
332 // to prove all accesses are well aligned.
333 if (!AddRec || AddRec->getLoop() != L || !AddRec->isAffine())
334 return false;
335
336 auto *Step = dyn_cast<SCEVConstant>(Val: AddRec->getStepRecurrence(SE));
337 if (!Step)
338 return false;
339
340 const APInt &EltSize = cast<SCEVConstant>(Val: EltSizeSCEV)->getAPInt();
341 // For the moment, restrict ourselves to the case where the access size is a
342 // multiple of the requested alignment and the base is aligned.
343 // TODO: generalize if a case found which warrants
344 if (EltSize.urem(RHS: Alignment.value()) != 0)
345 return false;
346
347 // TODO: Handle overlapping accesses.
348 if (EltSize.ugt(RHS: Step->getAPInt().abs()))
349 return false;
350
351 const SCEV *MaxBECount =
352 Predicates ? SE.getPredicatedSymbolicMaxBackedgeTakenCount(L, Predicates&: *Predicates)
353 : SE.getSymbolicMaxBackedgeTakenCount(L);
354 const SCEV *BECount = Predicates
355 ? SE.getPredicatedBackedgeTakenCount(L, Predicates&: *Predicates)
356 : SE.getBackedgeTakenCount(L);
357 if (isa<SCEVCouldNotCompute>(Val: MaxBECount))
358 return false;
359 auto LoopGuards = ScalarEvolution::LoopGuards::collectOnDemand(L, SE);
360
361 auto &DL = L->getHeader()->getDataLayout();
362 const auto &[AccessStart, AccessEnd] =
363 getStartAndEndForAccess(Lp: L, PtrExpr: PtrSCEV, EltSizeSCEV, BTC: BECount, MaxBTC: MaxBECount, SE: &SE,
364 PointerBounds: nullptr, DT: &DT, AC, LoopGuards);
365 if (isa<SCEVCouldNotCompute>(Val: AccessStart) ||
366 isa<SCEVCouldNotCompute>(Val: AccessEnd))
367 return false;
368
369 // Try to get the access size.
370 const SCEV *PtrDiff = SE.getMinusSCEV(LHS: AccessEnd, RHS: AccessStart);
371 if (isa<SCEVCouldNotCompute>(Val: PtrDiff))
372 return false;
373
374 APInt MaxPtrDiff =
375 SE.getUnsignedRangeMax(S: SE.applyLoopGuards(Expr: PtrDiff, Guards&: LoopGuards));
376
377 Value *Base = nullptr;
378 APInt AccessSize;
379 const SCEV *AccessSizeSCEV = nullptr;
380 if (const SCEVUnknown *NewBase = dyn_cast<SCEVUnknown>(Val: AccessStart)) {
381 Base = NewBase->getValue();
382 AccessSize = std::move(MaxPtrDiff);
383 AccessSizeSCEV = PtrDiff;
384 } else if (auto *MinAdd = dyn_cast<SCEVAddExpr>(Val: AccessStart)) {
385 if (MinAdd->getNumOperands() != 2)
386 return false;
387
388 const auto *Offset = dyn_cast<SCEVConstant>(Val: MinAdd->getOperand(i: 0));
389 const auto *NewBase = dyn_cast<SCEVUnknown>(Val: MinAdd->getOperand(i: 1));
390 if (!Offset || !NewBase)
391 return false;
392
393 // The following code below assumes the offset is unsigned, but GEP
394 // offsets are treated as signed so we can end up with a signed value
395 // here too. For example, suppose the initial PHI value is (i8 255),
396 // the offset will be treated as (i8 -1) and sign-extended to (i64 -1).
397 if (Offset->getAPInt().isNegative())
398 return false;
399
400 // For the moment, restrict ourselves to the case where the offset is a
401 // multiple of the requested alignment and the base is aligned.
402 // TODO: generalize if a case found which warrants
403 if (Offset->getAPInt().urem(RHS: Alignment.value()) != 0)
404 return false;
405
406 bool Overflow = false;
407 AccessSize = MaxPtrDiff.uadd_ov(RHS: Offset->getAPInt(), Overflow);
408 if (Overflow)
409 return false;
410 AccessSizeSCEV = SE.getAddExpr(LHS: PtrDiff, RHS: Offset);
411 Base = NewBase->getValue();
412 } else
413 return false;
414
415 Instruction *CtxI = &*L->getHeader()->getFirstNonPHIIt();
416 if (BasicBlock *LoopPred = L->getLoopPredecessor()) {
417 if (isa<UncondBrInst, CondBrInst>(Val: LoopPred->getTerminator()))
418 CtxI = LoopPred->getTerminator();
419 }
420 SimplifyQuery SQ(DL, &DT, AC, CtxI);
421 return isDereferenceableAndAlignedPointerViaAssumption(
422 Ptr: Base, Alignment, SQ, /*IgnoreFree=*/false,
423 CheckSize: [&SE, AccessSizeSCEV, &LoopGuards](const RetainedKnowledge &RK) {
424 const SCEV *DerefBytesSCEV = SE.getSCEV(V: RK.IRArgValue);
425 Type *WiderTy = SE.getWiderType(Ty1: AccessSizeSCEV->getType(),
426 Ty2: DerefBytesSCEV->getType());
427 const SCEV *AccessSizeExt =
428 SE.getNoopOrZeroExtend(V: AccessSizeSCEV, Ty: WiderTy);
429 const SCEV *DerefBytesExt =
430 SE.getNoopOrZeroExtend(V: DerefBytesSCEV, Ty: WiderTy);
431 return SE.isKnownPredicate(
432 Pred: CmpInst::ICMP_ULE,
433 LHS: SE.applyLoopGuards(Expr: AccessSizeExt, Guards&: LoopGuards),
434 RHS: SE.applyLoopGuards(Expr: DerefBytesExt, Guards&: LoopGuards));
435 }) ||
436 isDereferenceableAndAlignedPointer(V: Base, Alignment, Size: AccessSize, SQ);
437}
438
439static bool suppressSpeculativeLoadForSanitizers(const Instruction &CtxI) {
440 const Function &F = *CtxI.getFunction();
441 // Speculative load may create a race that did not exist in the source.
442 return F.hasFnAttribute(Kind: Attribute::SanitizeThread) ||
443 // Speculative load may load data from dirty regions.
444 F.hasFnAttribute(Kind: Attribute::SanitizeAddress) ||
445 F.hasFnAttribute(Kind: Attribute::SanitizeHWAddress);
446}
447
448bool llvm::mustSuppressSpeculation(const LoadInst &LI) {
449 return !LI.isUnordered() || suppressSpeculativeLoadForSanitizers(CtxI: LI);
450}
451
452bool llvm::isSafeToLoadUnconditionally(Value *V, Align Alignment,
453 const APInt &Size,
454 const SimplifyQuery &SQ,
455 bool IgnoreFree) {
456 if (isDereferenceableAndAlignedPointer(V, Alignment, Size, SQ, IgnoreFree)) {
457 // With sanitizers `Dereferenceable` is not always enough for unconditional
458 // load.
459 if (!SQ.CtxI || !suppressSpeculativeLoadForSanitizers(CtxI: *SQ.CtxI))
460 return true;
461 }
462
463 if (!SQ.CtxI)
464 return false;
465
466 if (Size.getBitWidth() > 64)
467 return false;
468 const TypeSize LoadSize = TypeSize::getFixed(ExactSize: Size.getZExtValue());
469
470 // Otherwise, be a little bit aggressive by scanning the local block where we
471 // want to check to see if the pointer is already being loaded or stored
472 // from/to. If so, the previous load or store would have already trapped,
473 // so there is no harm doing an extra load (also, CSE will later eliminate
474 // the load entirely).
475 auto BBI = SQ.CtxI->getIterator(), E = SQ.CtxI->getParent()->begin();
476
477 // We can at least always strip pointer casts even though we can't use the
478 // base here.
479 V = V->stripPointerCasts();
480
481 while (BBI != E) {
482 --BBI;
483
484 // If we see a free or a call which may write to memory (i.e. which might do
485 // a free) the pointer could be marked invalid.
486 if (!IgnoreFree && isa<CallInst>(Val: BBI) && BBI->mayWriteToMemory() &&
487 !isa<LifetimeIntrinsic>(Val: BBI))
488 return false;
489
490 const Value *AccessedPtr;
491 Type *AccessedTy;
492 Align AccessedAlign;
493 if (const auto *LI = dyn_cast<LoadInst>(Val&: BBI)) {
494 // Ignore volatile loads. The execution of a volatile load cannot
495 // be used to prove an address is backed by regular memory; it can,
496 // for example, point to an MMIO register.
497 if (LI->isVolatile())
498 continue;
499 AccessedPtr = LI->getPointerOperand();
500 AccessedTy = LI->getType();
501 AccessedAlign = LI->getAlign();
502 } else if (const auto *SI = dyn_cast<StoreInst>(Val&: BBI)) {
503 // Ignore volatile stores (see comment for loads).
504 if (SI->isVolatile())
505 continue;
506 AccessedPtr = SI->getPointerOperand();
507 AccessedTy = SI->getValueOperand()->getType();
508 AccessedAlign = SI->getAlign();
509 } else
510 continue;
511
512 if (AccessedAlign < Alignment)
513 continue;
514
515 // Handle trivial cases.
516 if (AccessedPtr == V &&
517 TypeSize::isKnownLE(LHS: LoadSize, RHS: SQ.DL.getTypeStoreSize(Ty: AccessedTy)))
518 return true;
519
520 if (AreEquivalentAddressValues(A: AccessedPtr->stripPointerCasts(), B: V) &&
521 TypeSize::isKnownLE(LHS: LoadSize, RHS: SQ.DL.getTypeStoreSize(Ty: AccessedTy)))
522 return true;
523 }
524 return false;
525}
526
527bool llvm::isSafeToLoadUnconditionally(Value *V, Type *Ty, Align Alignment,
528 const SimplifyQuery &SQ,
529 bool IgnoreFree) {
530 TypeSize TySize = SQ.DL.getTypeStoreSize(Ty);
531 if (TySize.isScalable())
532 return false;
533 APInt Size(SQ.DL.getIndexTypeSizeInBits(Ty: V->getType()),
534 TySize.getFixedValue());
535 return isSafeToLoadUnconditionally(V, Alignment, Size, SQ, IgnoreFree);
536}
537
538/// DefMaxInstsToScan - the default number of maximum instructions
539/// to scan in the block, used by FindAvailableLoadedValue().
540/// FindAvailableLoadedValue() was introduced in r60148, to improve jump
541/// threading in part by eliminating partially redundant loads.
542/// At that point, the value of MaxInstsToScan was already set to '6'
543/// without documented explanation.
544cl::opt<unsigned>
545llvm::DefMaxInstsToScan("available-load-scan-limit", cl::init(Val: 6), cl::Hidden,
546 cl::desc("Use this to specify the default maximum number of instructions "
547 "to scan backward from a given instruction, when searching for "
548 "available loaded value"));
549
550Value *llvm::FindAvailableLoadedValue(LoadInst *Load, BasicBlock *ScanBB,
551 BasicBlock::iterator &ScanFrom,
552 unsigned MaxInstsToScan,
553 BatchAAResults *AA, bool *IsLoad,
554 unsigned *NumScanedInst) {
555 // Don't CSE load that is volatile or anything stronger than unordered.
556 if (!Load->isUnordered())
557 return nullptr;
558
559 MemoryLocation Loc = MemoryLocation::get(LI: Load);
560 return findAvailablePtrLoadStore(Loc, AccessTy: Load->getType(), AccessProps: Load->getProperties(),
561 ScanBB, ScanFrom, MaxInstsToScan, AA, IsLoadCSE: IsLoad,
562 NumScanedInst);
563}
564
565// Check if the load and the store have the same base, constant offsets and
566// non-overlapping access ranges.
567static bool areNonOverlapSameBaseLoadAndStore(const Value *LoadPtr,
568 Type *LoadTy,
569 const Value *StorePtr,
570 Type *StoreTy,
571 const DataLayout &DL) {
572 APInt LoadOffset(DL.getIndexTypeSizeInBits(Ty: LoadPtr->getType()), 0);
573 APInt StoreOffset(DL.getIndexTypeSizeInBits(Ty: StorePtr->getType()), 0);
574 if (LoadOffset.getBitWidth() != StoreOffset.getBitWidth())
575 return false;
576 const Value *LoadBase = LoadPtr->stripAndAccumulateConstantOffsets(
577 DL, Offset&: LoadOffset, /* AllowNonInbounds */ false);
578 const Value *StoreBase = StorePtr->stripAndAccumulateConstantOffsets(
579 DL, Offset&: StoreOffset, /* AllowNonInbounds */ false);
580 if (LoadBase != StoreBase)
581 return false;
582 auto LoadAccessSize = LocationSize::precise(Value: DL.getTypeStoreSize(Ty: LoadTy));
583 auto StoreAccessSize = LocationSize::precise(Value: DL.getTypeStoreSize(Ty: StoreTy));
584 ConstantRange LoadRange(LoadOffset,
585 LoadOffset + LoadAccessSize.toRaw());
586 ConstantRange StoreRange(StoreOffset,
587 StoreOffset + StoreAccessSize.toRaw());
588 return LoadRange.intersectWith(CR: StoreRange).isEmptySet();
589}
590
591// For elementwise atomics, each vector element is a separate atomic access.
592// Reusing an operation with a different access size would change atomicity.
593static bool hasCompatibleAtomicAccessSize(
594 Type *AccessTy, const LoadStoreInstProperties &AccessProps,
595 Type *OtherAccessTy, const LoadStoreInstProperties &OtherProps,
596 const DataLayout &DL) {
597 if (AccessProps.Ordering == AtomicOrdering::NotAtomic)
598 return true;
599
600 Type *AtomicAccessTy =
601 AccessProps.IsElementwise ? AccessTy->getScalarType() : AccessTy;
602 Type *OtherAtomicAccessTy =
603 OtherProps.IsElementwise ? OtherAccessTy->getScalarType() : OtherAccessTy;
604 return DL.getTypeStoreSize(Ty: AtomicAccessTy) ==
605 DL.getTypeStoreSize(Ty: OtherAtomicAccessTy);
606}
607
608static Value *getAvailableLoadStore(Instruction *Inst, const Value *Ptr,
609 Type *AccessTy,
610 const LoadStoreInstProperties &AccessProps,
611 const DataLayout &DL, bool *IsLoadCSE) {
612 const bool AtLeastAtomic = AccessProps.Ordering != AtomicOrdering::NotAtomic;
613
614 // If this is a load of Ptr, the loaded value is available.
615 // (This is true even if the load is volatile or atomic, although
616 // those cases are unlikely.)
617 if (LoadInst *LI = dyn_cast<LoadInst>(Val: Inst)) {
618 // We can value forward from an atomic to a non-atomic, but not the
619 // other way around.
620 if (LI->isAtomic() < AtLeastAtomic)
621 return nullptr;
622
623 Value *LoadPtr = LI->getPointerOperand()->stripPointerCasts();
624 if (!AreEquivalentAddressValues(A: LoadPtr, B: Ptr))
625 return nullptr;
626
627 if (hasCompatibleAtomicAccessSize(AccessTy, AccessProps, OtherAccessTy: LI->getType(),
628 OtherProps: LI->getProperties(), DL) &&
629 CastInst::isBitOrNoopPointerCastable(SrcTy: LI->getType(), DestTy: AccessTy, DL)) {
630 if (IsLoadCSE)
631 *IsLoadCSE = true;
632 return LI;
633 }
634 }
635
636 // If this is a store through Ptr, the value is available!
637 // (This is true even if the store is volatile or atomic, although
638 // those cases are unlikely.)
639 if (StoreInst *SI = dyn_cast<StoreInst>(Val: Inst)) {
640 // We can value forward from an atomic to a non-atomic, but not the
641 // other way around.
642 if (SI->isAtomic() < AtLeastAtomic)
643 return nullptr;
644
645 Value *StorePtr = SI->getPointerOperand()->stripPointerCasts();
646 if (!AreEquivalentAddressValues(A: StorePtr, B: Ptr))
647 return nullptr;
648
649 if (IsLoadCSE)
650 *IsLoadCSE = false;
651
652 Value *Val = SI->getValueOperand();
653 if (!hasCompatibleAtomicAccessSize(AccessTy, AccessProps, OtherAccessTy: Val->getType(),
654 OtherProps: SI->getProperties(), DL))
655 return nullptr;
656
657 if (CastInst::isBitOrNoopPointerCastable(SrcTy: Val->getType(), DestTy: AccessTy, DL))
658 return Val;
659
660 TypeSize StoreSize = DL.getTypeSizeInBits(Ty: Val->getType());
661 TypeSize LoadSize = DL.getTypeSizeInBits(Ty: AccessTy);
662 if (TypeSize::isKnownLE(LHS: LoadSize, RHS: StoreSize))
663 if (auto *C = dyn_cast<Constant>(Val))
664 return ConstantFoldLoadFromConst(C, Ty: AccessTy, DL);
665 }
666
667 if (auto *MSI = dyn_cast<MemSetInst>(Val: Inst)) {
668 // Don't forward from (non-atomic) memset to atomic load.
669 if (AtLeastAtomic)
670 return nullptr;
671
672 // Only handle constant memsets.
673 auto *Val = dyn_cast<ConstantInt>(Val: MSI->getValue());
674 auto *Len = dyn_cast<ConstantInt>(Val: MSI->getLength());
675 if (!Val || !Len)
676 return nullptr;
677
678 // Handle offsets.
679 int64_t StoreOffset = 0, LoadOffset = 0;
680 const Value *StoreBase =
681 GetPointerBaseWithConstantOffset(Ptr: MSI->getDest(), Offset&: StoreOffset, DL);
682 const Value *LoadBase =
683 GetPointerBaseWithConstantOffset(Ptr, Offset&: LoadOffset, DL);
684 if (StoreBase != LoadBase || LoadOffset < StoreOffset)
685 return nullptr;
686
687 if (IsLoadCSE)
688 *IsLoadCSE = false;
689
690 TypeSize LoadTypeSize = DL.getTypeSizeInBits(Ty: AccessTy);
691 if (LoadTypeSize.isScalable())
692 return nullptr;
693
694 // Make sure the read bytes are contained in the memset.
695 uint64_t LoadSize = LoadTypeSize.getFixedValue();
696 if ((Len->getValue() * 8).ult(RHS: LoadSize + (LoadOffset - StoreOffset) * 8))
697 return nullptr;
698
699 APInt Splat = LoadSize >= 8 ? APInt::getSplat(NewLen: LoadSize, V: Val->getValue())
700 : Val->getValue().trunc(width: LoadSize);
701 ConstantInt *SplatC = ConstantInt::get(Context&: MSI->getContext(), V: Splat);
702 if (CastInst::isBitOrNoopPointerCastable(SrcTy: SplatC->getType(), DestTy: AccessTy, DL))
703 return SplatC;
704
705 return nullptr;
706 }
707
708 return nullptr;
709}
710
711Value *llvm::findAvailablePtrLoadStore(
712 const MemoryLocation &Loc, Type *AccessTy,
713 const LoadStoreInstProperties &AccessProps, BasicBlock *ScanBB,
714 BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan, BatchAAResults *AA,
715 bool *IsLoadCSE, unsigned *NumScanedInst) {
716 if (MaxInstsToScan == 0)
717 MaxInstsToScan = ~0U;
718
719 const DataLayout &DL = ScanBB->getDataLayout();
720 const Value *StrippedPtr = Loc.Ptr->stripPointerCasts();
721
722 while (ScanFrom != ScanBB->begin()) {
723 // We must ignore pseudo probes when counting (otherwise they
724 // would affect codegen).
725 Instruction *Inst = &*--ScanFrom;
726 if (isa<PseudoProbeInst>(Val: Inst))
727 continue;
728
729 // Restore ScanFrom to expected value in case next test succeeds
730 ScanFrom++;
731
732 if (NumScanedInst)
733 ++(*NumScanedInst);
734
735 // Don't scan huge blocks.
736 if (MaxInstsToScan-- == 0)
737 return nullptr;
738
739 --ScanFrom;
740
741 if (Value *Available = getAvailableLoadStore(Inst, Ptr: StrippedPtr, AccessTy,
742 AccessProps, DL, IsLoadCSE))
743 return Available;
744
745 // Try to get the store size for the type.
746 if (StoreInst *SI = dyn_cast<StoreInst>(Val: Inst)) {
747 Value *StorePtr = SI->getPointerOperand()->stripPointerCasts();
748
749 // If both StrippedPtr and StorePtr reach all the way to an alloca or
750 // global and they are different, ignore the store. This is a trivial form
751 // of alias analysis that is important for reg2mem'd code.
752 if ((isa<AllocaInst>(Val: StrippedPtr) || isa<GlobalVariable>(Val: StrippedPtr)) &&
753 (isa<AllocaInst>(Val: StorePtr) || isa<GlobalVariable>(Val: StorePtr)) &&
754 StrippedPtr != StorePtr)
755 continue;
756
757 if (!AA) {
758 // When AA isn't available, but if the load and the store have the same
759 // base, constant offsets and non-overlapping access ranges, ignore the
760 // store. This is a simple form of alias analysis that is used by the
761 // inliner. FIXME: use BasicAA if possible.
762 if (areNonOverlapSameBaseLoadAndStore(
763 LoadPtr: Loc.Ptr, LoadTy: AccessTy, StorePtr: SI->getPointerOperand(),
764 StoreTy: SI->getValueOperand()->getType(), DL))
765 continue;
766 } else {
767 // If we have alias analysis and it says the store won't modify the
768 // loaded value, ignore the store.
769 if (!isModSet(MRI: AA->getModRefInfo(I: SI, OptLoc: Loc)))
770 continue;
771 }
772
773 // Otherwise the store that may or may not alias the pointer, bail out.
774 ++ScanFrom;
775 return nullptr;
776 }
777
778 // If this is some other instruction that may clobber Ptr, bail out.
779 if (Inst->mayWriteToMemory()) {
780 // If alias analysis claims that it really won't modify the load,
781 // ignore it.
782 if (AA && !isModSet(MRI: AA->getModRefInfo(I: Inst, OptLoc: Loc)))
783 continue;
784
785 // May modify the pointer, bail out.
786 ++ScanFrom;
787 return nullptr;
788 }
789 }
790
791 // Got to the start of the block, we didn't find it, but are done for this
792 // block.
793 return nullptr;
794}
795
796Value *llvm::FindAvailableLoadedValue(LoadInst *Load, BatchAAResults &AA,
797 bool *IsLoadCSE,
798 unsigned MaxInstsToScan) {
799 const DataLayout &DL = Load->getDataLayout();
800 Value *StrippedPtr = Load->getPointerOperand()->stripPointerCasts();
801 BasicBlock *ScanBB = Load->getParent();
802 Type *AccessTy = Load->getType();
803 LoadStoreInstProperties AccessProps = Load->getProperties();
804
805 if (!Load->isUnordered())
806 return nullptr;
807
808 // Try to find an available value first, and delay expensive alias analysis
809 // queries until later.
810 Value *Available = nullptr;
811 SmallVector<Instruction *> MustNotAliasInsts;
812 for (Instruction &Inst : make_range(x: ++Load->getReverseIterator(),
813 y: ScanBB->rend())) {
814 if (isa<PseudoProbeInst>(Val: Inst))
815 continue;
816
817 if (MaxInstsToScan-- == 0)
818 return nullptr;
819
820 Available = getAvailableLoadStore(Inst: &Inst, Ptr: StrippedPtr, AccessTy, AccessProps,
821 DL, IsLoadCSE);
822 if (Available)
823 break;
824
825 if (Inst.mayWriteToMemory())
826 MustNotAliasInsts.push_back(Elt: &Inst);
827 }
828
829 // If we found an available value, ensure that the instructions in between
830 // did not modify the memory location.
831 if (Available) {
832 MemoryLocation Loc = MemoryLocation::get(LI: Load);
833 for (Instruction *Inst : MustNotAliasInsts)
834 if (isModSet(MRI: AA.getModRefInfo(I: Inst, OptLoc: Loc)))
835 return nullptr;
836 }
837
838 return Available;
839}
840
841bool llvm::isStorePreservingMemoryLocation(const StoreInst *SI,
842 const MemoryLocation &MemLoc,
843 Align MemLocAlign,
844 BatchAAResults &AA,
845 unsigned ScanLimit) {
846 // Ensure no partial overlap is possible, and that the stored value is the
847 // current content of MemLoc.
848 if (!MemLoc.Size.hasValue() || MemLoc.Size.isScalable())
849 return false;
850 if (MemoryLocation::get(SI).Size != MemLoc.Size)
851 return false;
852 if (std::min(a: MemLocAlign, b: SI->getAlign()).value() <
853 MemLoc.Size.getValue().getFixedValue())
854 return false;
855
856 auto *LI = dyn_cast<LoadInst>(Val: SI->getValueOperand());
857 if (!LI || LI->getParent() != SI->getParent())
858 return false;
859 if (AA.alias(LocA: MemoryLocation::get(LI), LocB: MemLoc) != AliasResult::MustAlias)
860 return false;
861
862 // No memory operation in between may modify MemLoc.
863 unsigned NumVisited = 0;
864 for (const Instruction *I = LI; I != SI; I = I->getNextNode())
865 if (++NumVisited > ScanLimit || isModSet(MRI: AA.getModRefInfo(I, OptLoc: MemLoc)))
866 return false;
867
868 return true;
869}
870
871// Returns true if a use is either in an ICmp/PtrToInt or a Phi/Select that only
872// feeds into them.
873static bool isPointerUseReplaceable(const Use &U, bool HasNonAddressBits) {
874 unsigned Limit = 40;
875 SmallVector<const User *> Worklist({U.getUser()});
876 SmallPtrSet<const User *, 8> Visited;
877
878 while (!Worklist.empty() && --Limit) {
879 auto *User = Worklist.pop_back_val();
880 if (!Visited.insert(Ptr: User).second)
881 continue;
882 if (isa<ICmpInst, PtrToAddrInst>(Val: User))
883 continue;
884 // FIXME: The PtrToIntInst case here is not strictly correct, as it
885 // changes which provenance is exposed.
886 if (!HasNonAddressBits && isa<PtrToIntInst>(Val: User))
887 continue;
888 if (isa<PHINode, SelectInst>(Val: User))
889 Worklist.append(in_start: User->user_begin(), in_end: User->user_end());
890 else
891 return false;
892 }
893
894 return Limit != 0;
895}
896
897static bool isPointerAlwaysReplaceable(const Value *From, const Value *To,
898 const DataLayout &DL) {
899 // This is not strictly correct, but we do it for now to retain important
900 // optimizations.
901 if (isa<ConstantPointerNull>(Val: To))
902 return true;
903 // Conversely, replacing null in the default address space with destination
904 // pointer is always valid.
905 if (isa<ConstantPointerNull>(Val: From) &&
906 From->getType()->getPointerAddressSpace() == 0)
907 return true;
908 // Allow replacement with dereferenceable constants. This is not strictly
909 // correct, but required for vtable assumptions.
910 auto IsBasedOnConstantGlobal = [](const Value *V) {
911 auto *GV = dyn_cast<GlobalVariable>(Val: getUnderlyingObject(V));
912 return GV && GV->isConstant();
913 };
914 if (isa<Constant>(Val: To) && To->getType()->isPointerTy() &&
915 isDereferenceablePointer(V: To, Ty: Type::getInt8Ty(C&: To->getContext()), SQ: DL) &&
916 IsBasedOnConstantGlobal(To))
917 return true;
918 return getUnderlyingObjectAggressive(V: From, /*MustPreserveProvenance=*/true) ==
919 getUnderlyingObjectAggressive(V: To, /*MustPreserveProvenance=*/true);
920}
921
922bool llvm::canReplacePointersInUseIfEqual(const Use &U, const Value *To,
923 const DataLayout &DL) {
924 Type *Ty = To->getType();
925 assert(U->getType() == Ty && "values must have matching types");
926 // Not a pointer, just return true.
927 if (!Ty->isPtrOrPtrVectorTy())
928 return true;
929
930 // Do not perform replacements in lifetime intrinsic arguments.
931 if (isa<LifetimeIntrinsic>(Val: U.getUser()))
932 return false;
933
934 if (isPointerAlwaysReplaceable(From: &*U, To, DL))
935 return true;
936
937 bool HasNonAddressBits =
938 DL.getAddressSizeInBits(Ty) != DL.getPointerTypeSizeInBits(Ty);
939 return isPointerUseReplaceable(U, HasNonAddressBits);
940}
941
942bool llvm::canReplacePointersIfEqual(const Value *From, const Value *To,
943 const DataLayout &DL) {
944 assert(From->getType() == To->getType() && "values must have matching types");
945 // Not a pointer, just return true.
946 if (!From->getType()->isPtrOrPtrVectorTy())
947 return true;
948
949 return isPointerAlwaysReplaceable(From, To, DL);
950}
951
952bool llvm::isReadOnlyLoop(
953 Loop *L, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC,
954 SmallVectorImpl<LoadInst *> &NonDereferenceableAndAlignedLoads,
955 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
956 for (BasicBlock *BB : L->blocks()) {
957 for (Instruction &I : *BB) {
958 // Pseudo-probes are placeholders with side effects but
959 // no real memory access, and do not affect dereferenceability.
960 if (isa<PseudoProbeInst>(Val: I))
961 continue;
962 if (auto *LI = dyn_cast<LoadInst>(Val: &I)) {
963 if (!isDereferenceableAndAlignedInLoop(LI, L, SE&: *SE, DT&: *DT, AC, Predicates))
964 NonDereferenceableAndAlignedLoads.push_back(Elt: LI);
965 } else if (I.mayReadFromMemory() || I.mayWriteToMemory() ||
966 I.mayThrow()) {
967 return false;
968 }
969 }
970 }
971 return true;
972}
973
974LinearExpression llvm::decomposeLinearExpression(const DataLayout &DL,
975 Value *Ptr) {
976 assert(Ptr->getType()->isPointerTy() && "Must be called with pointer arg");
977
978 unsigned BitWidth = DL.getIndexTypeSizeInBits(Ty: Ptr->getType());
979 LinearExpression Expr(Ptr, BitWidth);
980
981 while (true) {
982 auto *GEP = dyn_cast<GEPOperator>(Val: Expr.BasePtr);
983 if (!GEP || GEP->getSourceElementType()->isScalableTy())
984 return Expr;
985
986 Value *VarIndex = nullptr;
987 for (Value *Index : GEP->indices()) {
988 if (isa<ConstantInt>(Val: Index))
989 continue;
990 // Only allow a single variable index. We do not bother to handle the
991 // case of the same variable index appearing multiple times.
992 if (Expr.Index || VarIndex)
993 return Expr;
994 VarIndex = Index;
995 }
996
997 // Don't return non-canonical indexes.
998 if (VarIndex && !VarIndex->getType()->isIntegerTy(BitWidth))
999 return Expr;
1000
1001 // We have verified that we can fully handle this GEP, so we can update Expr
1002 // members past this point.
1003 Expr.BasePtr = GEP->getPointerOperand();
1004 Expr.Flags = Expr.Flags.intersectForOffsetAdd(Other: GEP->getNoWrapFlags());
1005 for (gep_type_iterator GTI = gep_type_begin(GEP), GTE = gep_type_end(GEP);
1006 GTI != GTE; ++GTI) {
1007 Value *Index = GTI.getOperand();
1008 if (auto *ConstOffset = dyn_cast<ConstantInt>(Val: Index)) {
1009 if (ConstOffset->isZero())
1010 continue;
1011 if (StructType *STy = GTI.getStructTypeOrNull()) {
1012 unsigned ElementIdx = ConstOffset->getZExtValue();
1013 const StructLayout *SL = DL.getStructLayout(Ty: STy);
1014 Expr.Offset += SL->getElementOffset(Idx: ElementIdx);
1015 continue;
1016 }
1017 // Truncate if type size exceeds index space.
1018 APInt IndexedSize(BitWidth, GTI.getSequentialElementStride(DL),
1019 /*isSigned=*/false,
1020 /*implcitTrunc=*/true);
1021 Expr.Offset += ConstOffset->getValue() * IndexedSize;
1022 continue;
1023 }
1024
1025 // FIXME: Also look through a mul/shl in the index.
1026 assert(Expr.Index == nullptr && "Shouldn't have index yet");
1027 Expr.Index = Index;
1028 // Truncate if type size exceeds index space.
1029 Expr.Scale = APInt(BitWidth, GTI.getSequentialElementStride(DL),
1030 /*isSigned=*/false, /*implicitTrunc=*/true);
1031 }
1032 }
1033
1034 return Expr;
1035}
1036