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.CxtI)
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, CxtI: SQ.CxtI, 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.CxtI)) &&
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.CxtI || !willNotFreeBetween(Assume: DefI, CtxI: SQ.CxtI))
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.CxtI && isValidAssumeForContext(I, CxtI: SQ.CxtI, 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 std::optional<ScalarEvolution::LoopGuards> LoopGuards;
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 if (!LoopGuards)
375 LoopGuards.emplace(
376 args: ScalarEvolution::LoopGuards::collect(L: AddRec->getLoop(), SE));
377
378 APInt MaxPtrDiff =
379 SE.getUnsignedRangeMax(S: SE.applyLoopGuards(Expr: PtrDiff, Guards: *LoopGuards));
380
381 Value *Base = nullptr;
382 APInt AccessSize;
383 const SCEV *AccessSizeSCEV = nullptr;
384 if (const SCEVUnknown *NewBase = dyn_cast<SCEVUnknown>(Val: AccessStart)) {
385 Base = NewBase->getValue();
386 AccessSize = std::move(MaxPtrDiff);
387 AccessSizeSCEV = PtrDiff;
388 } else if (auto *MinAdd = dyn_cast<SCEVAddExpr>(Val: AccessStart)) {
389 if (MinAdd->getNumOperands() != 2)
390 return false;
391
392 const auto *Offset = dyn_cast<SCEVConstant>(Val: MinAdd->getOperand(i: 0));
393 const auto *NewBase = dyn_cast<SCEVUnknown>(Val: MinAdd->getOperand(i: 1));
394 if (!Offset || !NewBase)
395 return false;
396
397 // The following code below assumes the offset is unsigned, but GEP
398 // offsets are treated as signed so we can end up with a signed value
399 // here too. For example, suppose the initial PHI value is (i8 255),
400 // the offset will be treated as (i8 -1) and sign-extended to (i64 -1).
401 if (Offset->getAPInt().isNegative())
402 return false;
403
404 // For the moment, restrict ourselves to the case where the offset is a
405 // multiple of the requested alignment and the base is aligned.
406 // TODO: generalize if a case found which warrants
407 if (Offset->getAPInt().urem(RHS: Alignment.value()) != 0)
408 return false;
409
410 bool Overflow = false;
411 AccessSize = MaxPtrDiff.uadd_ov(RHS: Offset->getAPInt(), Overflow);
412 if (Overflow)
413 return false;
414 AccessSizeSCEV = SE.getAddExpr(LHS: PtrDiff, RHS: Offset);
415 Base = NewBase->getValue();
416 } else
417 return false;
418
419 Instruction *CtxI = &*L->getHeader()->getFirstNonPHIIt();
420 if (BasicBlock *LoopPred = L->getLoopPredecessor()) {
421 if (isa<UncondBrInst, CondBrInst>(Val: LoopPred->getTerminator()))
422 CtxI = LoopPred->getTerminator();
423 }
424 SimplifyQuery SQ(DL, &DT, AC, CtxI);
425 return isDereferenceableAndAlignedPointerViaAssumption(
426 Ptr: Base, Alignment, SQ, /*IgnoreFree=*/false,
427 CheckSize: [&SE, AccessSizeSCEV, &LoopGuards](const RetainedKnowledge &RK) {
428 const SCEV *DerefBytesSCEV = SE.getSCEV(V: RK.IRArgValue);
429 Type *WiderTy = SE.getWiderType(Ty1: AccessSizeSCEV->getType(),
430 Ty2: DerefBytesSCEV->getType());
431 const SCEV *AccessSizeExt =
432 SE.getNoopOrZeroExtend(V: AccessSizeSCEV, Ty: WiderTy);
433 const SCEV *DerefBytesExt =
434 SE.getNoopOrZeroExtend(V: DerefBytesSCEV, Ty: WiderTy);
435 return SE.isKnownPredicate(
436 Pred: CmpInst::ICMP_ULE,
437 LHS: SE.applyLoopGuards(Expr: AccessSizeExt, Guards: *LoopGuards),
438 RHS: SE.applyLoopGuards(Expr: DerefBytesExt, Guards: *LoopGuards));
439 }) ||
440 isDereferenceableAndAlignedPointer(V: Base, Alignment, Size: AccessSize, SQ);
441}
442
443static bool suppressSpeculativeLoadForSanitizers(const Instruction &CtxI) {
444 const Function &F = *CtxI.getFunction();
445 // Speculative load may create a race that did not exist in the source.
446 return F.hasFnAttribute(Kind: Attribute::SanitizeThread) ||
447 // Speculative load may load data from dirty regions.
448 F.hasFnAttribute(Kind: Attribute::SanitizeAddress) ||
449 F.hasFnAttribute(Kind: Attribute::SanitizeHWAddress);
450}
451
452bool llvm::mustSuppressSpeculation(const LoadInst &LI) {
453 return !LI.isUnordered() || suppressSpeculativeLoadForSanitizers(CtxI: LI);
454}
455
456bool llvm::isSafeToLoadUnconditionally(Value *V, Align Alignment,
457 const APInt &Size,
458 const SimplifyQuery &SQ) {
459 if (isDereferenceableAndAlignedPointer(V, Alignment, Size, SQ)) {
460 // With sanitizers `Dereferenceable` is not always enough for unconditional
461 // load.
462 if (!SQ.CxtI || !suppressSpeculativeLoadForSanitizers(CtxI: *SQ.CxtI))
463 return true;
464 }
465
466 if (!SQ.CxtI)
467 return false;
468
469 if (Size.getBitWidth() > 64)
470 return false;
471 const TypeSize LoadSize = TypeSize::getFixed(ExactSize: Size.getZExtValue());
472
473 // Otherwise, be a little bit aggressive by scanning the local block where we
474 // want to check to see if the pointer is already being loaded or stored
475 // from/to. If so, the previous load or store would have already trapped,
476 // so there is no harm doing an extra load (also, CSE will later eliminate
477 // the load entirely).
478 auto BBI = SQ.CxtI->getIterator(), E = SQ.CxtI->getParent()->begin();
479
480 // We can at least always strip pointer casts even though we can't use the
481 // base here.
482 V = V->stripPointerCasts();
483
484 while (BBI != E) {
485 --BBI;
486
487 // If we see a free or a call which may write to memory (i.e. which might do
488 // a free) the pointer could be marked invalid.
489 if (isa<CallInst>(Val: BBI) && BBI->mayWriteToMemory() &&
490 !isa<LifetimeIntrinsic>(Val: BBI))
491 return false;
492
493 const Value *AccessedPtr;
494 Type *AccessedTy;
495 Align AccessedAlign;
496 if (const auto *LI = dyn_cast<LoadInst>(Val&: BBI)) {
497 // Ignore volatile loads. The execution of a volatile load cannot
498 // be used to prove an address is backed by regular memory; it can,
499 // for example, point to an MMIO register.
500 if (LI->isVolatile())
501 continue;
502 AccessedPtr = LI->getPointerOperand();
503 AccessedTy = LI->getType();
504 AccessedAlign = LI->getAlign();
505 } else if (const auto *SI = dyn_cast<StoreInst>(Val&: BBI)) {
506 // Ignore volatile stores (see comment for loads).
507 if (SI->isVolatile())
508 continue;
509 AccessedPtr = SI->getPointerOperand();
510 AccessedTy = SI->getValueOperand()->getType();
511 AccessedAlign = SI->getAlign();
512 } else
513 continue;
514
515 if (AccessedAlign < Alignment)
516 continue;
517
518 // Handle trivial cases.
519 if (AccessedPtr == V &&
520 TypeSize::isKnownLE(LHS: LoadSize, RHS: SQ.DL.getTypeStoreSize(Ty: AccessedTy)))
521 return true;
522
523 if (AreEquivalentAddressValues(A: AccessedPtr->stripPointerCasts(), B: V) &&
524 TypeSize::isKnownLE(LHS: LoadSize, RHS: SQ.DL.getTypeStoreSize(Ty: AccessedTy)))
525 return true;
526 }
527 return false;
528}
529
530bool llvm::isSafeToLoadUnconditionally(Value *V, Type *Ty, Align Alignment,
531 const SimplifyQuery &SQ) {
532 TypeSize TySize = SQ.DL.getTypeStoreSize(Ty);
533 if (TySize.isScalable())
534 return false;
535 APInt Size(SQ.DL.getIndexTypeSizeInBits(Ty: V->getType()),
536 TySize.getFixedValue());
537 return isSafeToLoadUnconditionally(V, Alignment, Size, SQ);
538}
539
540/// DefMaxInstsToScan - the default number of maximum instructions
541/// to scan in the block, used by FindAvailableLoadedValue().
542/// FindAvailableLoadedValue() was introduced in r60148, to improve jump
543/// threading in part by eliminating partially redundant loads.
544/// At that point, the value of MaxInstsToScan was already set to '6'
545/// without documented explanation.
546cl::opt<unsigned>
547llvm::DefMaxInstsToScan("available-load-scan-limit", cl::init(Val: 6), cl::Hidden,
548 cl::desc("Use this to specify the default maximum number of instructions "
549 "to scan backward from a given instruction, when searching for "
550 "available loaded value"));
551
552Value *llvm::FindAvailableLoadedValue(LoadInst *Load, BasicBlock *ScanBB,
553 BasicBlock::iterator &ScanFrom,
554 unsigned MaxInstsToScan,
555 BatchAAResults *AA, bool *IsLoad,
556 unsigned *NumScanedInst) {
557 // Don't CSE load that is volatile or anything stronger than unordered.
558 if (!Load->isUnordered())
559 return nullptr;
560
561 MemoryLocation Loc = MemoryLocation::get(LI: Load);
562 return findAvailablePtrLoadStore(Loc, AccessTy: Load->getType(), AtLeastAtomic: Load->isAtomic(),
563 ScanBB, ScanFrom, MaxInstsToScan, AA, IsLoadCSE: IsLoad,
564 NumScanedInst);
565}
566
567// Check if the load and the store have the same base, constant offsets and
568// non-overlapping access ranges.
569static bool areNonOverlapSameBaseLoadAndStore(const Value *LoadPtr,
570 Type *LoadTy,
571 const Value *StorePtr,
572 Type *StoreTy,
573 const DataLayout &DL) {
574 APInt LoadOffset(DL.getIndexTypeSizeInBits(Ty: LoadPtr->getType()), 0);
575 APInt StoreOffset(DL.getIndexTypeSizeInBits(Ty: StorePtr->getType()), 0);
576 if (LoadOffset.getBitWidth() != StoreOffset.getBitWidth())
577 return false;
578 const Value *LoadBase = LoadPtr->stripAndAccumulateConstantOffsets(
579 DL, Offset&: LoadOffset, /* AllowNonInbounds */ false);
580 const Value *StoreBase = StorePtr->stripAndAccumulateConstantOffsets(
581 DL, Offset&: StoreOffset, /* AllowNonInbounds */ false);
582 if (LoadBase != StoreBase)
583 return false;
584 auto LoadAccessSize = LocationSize::precise(Value: DL.getTypeStoreSize(Ty: LoadTy));
585 auto StoreAccessSize = LocationSize::precise(Value: DL.getTypeStoreSize(Ty: StoreTy));
586 ConstantRange LoadRange(LoadOffset,
587 LoadOffset + LoadAccessSize.toRaw());
588 ConstantRange StoreRange(StoreOffset,
589 StoreOffset + StoreAccessSize.toRaw());
590 return LoadRange.intersectWith(CR: StoreRange).isEmptySet();
591}
592
593static Value *getAvailableLoadStore(Instruction *Inst, const Value *Ptr,
594 Type *AccessTy, bool AtLeastAtomic,
595 const DataLayout &DL, bool *IsLoadCSE) {
596 // If this is a load of Ptr, the loaded value is available.
597 // (This is true even if the load is volatile or atomic, although
598 // those cases are unlikely.)
599 if (LoadInst *LI = dyn_cast<LoadInst>(Val: Inst)) {
600 // We can value forward from an atomic to a non-atomic, but not the
601 // other way around.
602 if (LI->isAtomic() < AtLeastAtomic)
603 return nullptr;
604
605 Value *LoadPtr = LI->getPointerOperand()->stripPointerCasts();
606 if (!AreEquivalentAddressValues(A: LoadPtr, B: Ptr))
607 return nullptr;
608
609 if (CastInst::isBitOrNoopPointerCastable(SrcTy: LI->getType(), DestTy: AccessTy, DL)) {
610 if (IsLoadCSE)
611 *IsLoadCSE = true;
612 return LI;
613 }
614 }
615
616 // If this is a store through Ptr, the value is available!
617 // (This is true even if the store is volatile or atomic, although
618 // those cases are unlikely.)
619 if (StoreInst *SI = dyn_cast<StoreInst>(Val: Inst)) {
620 // We can value forward from an atomic to a non-atomic, but not the
621 // other way around.
622 if (SI->isAtomic() < AtLeastAtomic)
623 return nullptr;
624
625 Value *StorePtr = SI->getPointerOperand()->stripPointerCasts();
626 if (!AreEquivalentAddressValues(A: StorePtr, B: Ptr))
627 return nullptr;
628
629 if (IsLoadCSE)
630 *IsLoadCSE = false;
631
632 Value *Val = SI->getValueOperand();
633 if (CastInst::isBitOrNoopPointerCastable(SrcTy: Val->getType(), DestTy: AccessTy, DL))
634 return Val;
635
636 TypeSize StoreSize = DL.getTypeSizeInBits(Ty: Val->getType());
637 TypeSize LoadSize = DL.getTypeSizeInBits(Ty: AccessTy);
638 if (TypeSize::isKnownLE(LHS: LoadSize, RHS: StoreSize))
639 if (auto *C = dyn_cast<Constant>(Val))
640 return ConstantFoldLoadFromConst(C, Ty: AccessTy, DL);
641 }
642
643 if (auto *MSI = dyn_cast<MemSetInst>(Val: Inst)) {
644 // Don't forward from (non-atomic) memset to atomic load.
645 if (AtLeastAtomic)
646 return nullptr;
647
648 // Only handle constant memsets.
649 auto *Val = dyn_cast<ConstantInt>(Val: MSI->getValue());
650 auto *Len = dyn_cast<ConstantInt>(Val: MSI->getLength());
651 if (!Val || !Len)
652 return nullptr;
653
654 // Handle offsets.
655 int64_t StoreOffset = 0, LoadOffset = 0;
656 const Value *StoreBase =
657 GetPointerBaseWithConstantOffset(Ptr: MSI->getDest(), Offset&: StoreOffset, DL);
658 const Value *LoadBase =
659 GetPointerBaseWithConstantOffset(Ptr, Offset&: LoadOffset, DL);
660 if (StoreBase != LoadBase || LoadOffset < StoreOffset)
661 return nullptr;
662
663 if (IsLoadCSE)
664 *IsLoadCSE = false;
665
666 TypeSize LoadTypeSize = DL.getTypeSizeInBits(Ty: AccessTy);
667 if (LoadTypeSize.isScalable())
668 return nullptr;
669
670 // Make sure the read bytes are contained in the memset.
671 uint64_t LoadSize = LoadTypeSize.getFixedValue();
672 if ((Len->getValue() * 8).ult(RHS: LoadSize + (LoadOffset - StoreOffset) * 8))
673 return nullptr;
674
675 APInt Splat = LoadSize >= 8 ? APInt::getSplat(NewLen: LoadSize, V: Val->getValue())
676 : Val->getValue().trunc(width: LoadSize);
677 ConstantInt *SplatC = ConstantInt::get(Context&: MSI->getContext(), V: Splat);
678 if (CastInst::isBitOrNoopPointerCastable(SrcTy: SplatC->getType(), DestTy: AccessTy, DL))
679 return SplatC;
680
681 return nullptr;
682 }
683
684 return nullptr;
685}
686
687Value *llvm::findAvailablePtrLoadStore(
688 const MemoryLocation &Loc, Type *AccessTy, bool AtLeastAtomic,
689 BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan,
690 BatchAAResults *AA, bool *IsLoadCSE, unsigned *NumScanedInst) {
691 if (MaxInstsToScan == 0)
692 MaxInstsToScan = ~0U;
693
694 const DataLayout &DL = ScanBB->getDataLayout();
695 const Value *StrippedPtr = Loc.Ptr->stripPointerCasts();
696
697 while (ScanFrom != ScanBB->begin()) {
698 // We must ignore debug info directives when counting (otherwise they
699 // would affect codegen).
700 Instruction *Inst = &*--ScanFrom;
701 if (Inst->isDebugOrPseudoInst())
702 continue;
703
704 // Restore ScanFrom to expected value in case next test succeeds
705 ScanFrom++;
706
707 if (NumScanedInst)
708 ++(*NumScanedInst);
709
710 // Don't scan huge blocks.
711 if (MaxInstsToScan-- == 0)
712 return nullptr;
713
714 --ScanFrom;
715
716 if (Value *Available = getAvailableLoadStore(Inst, Ptr: StrippedPtr, AccessTy,
717 AtLeastAtomic, DL, IsLoadCSE))
718 return Available;
719
720 // Try to get the store size for the type.
721 if (StoreInst *SI = dyn_cast<StoreInst>(Val: Inst)) {
722 Value *StorePtr = SI->getPointerOperand()->stripPointerCasts();
723
724 // If both StrippedPtr and StorePtr reach all the way to an alloca or
725 // global and they are different, ignore the store. This is a trivial form
726 // of alias analysis that is important for reg2mem'd code.
727 if ((isa<AllocaInst>(Val: StrippedPtr) || isa<GlobalVariable>(Val: StrippedPtr)) &&
728 (isa<AllocaInst>(Val: StorePtr) || isa<GlobalVariable>(Val: StorePtr)) &&
729 StrippedPtr != StorePtr)
730 continue;
731
732 if (!AA) {
733 // When AA isn't available, but if the load and the store have the same
734 // base, constant offsets and non-overlapping access ranges, ignore the
735 // store. This is a simple form of alias analysis that is used by the
736 // inliner. FIXME: use BasicAA if possible.
737 if (areNonOverlapSameBaseLoadAndStore(
738 LoadPtr: Loc.Ptr, LoadTy: AccessTy, StorePtr: SI->getPointerOperand(),
739 StoreTy: SI->getValueOperand()->getType(), DL))
740 continue;
741 } else {
742 // If we have alias analysis and it says the store won't modify the
743 // loaded value, ignore the store.
744 if (!isModSet(MRI: AA->getModRefInfo(I: SI, OptLoc: Loc)))
745 continue;
746 }
747
748 // Otherwise the store that may or may not alias the pointer, bail out.
749 ++ScanFrom;
750 return nullptr;
751 }
752
753 // If this is some other instruction that may clobber Ptr, bail out.
754 if (Inst->mayWriteToMemory()) {
755 // If alias analysis claims that it really won't modify the load,
756 // ignore it.
757 if (AA && !isModSet(MRI: AA->getModRefInfo(I: Inst, OptLoc: Loc)))
758 continue;
759
760 // May modify the pointer, bail out.
761 ++ScanFrom;
762 return nullptr;
763 }
764 }
765
766 // Got to the start of the block, we didn't find it, but are done for this
767 // block.
768 return nullptr;
769}
770
771Value *llvm::FindAvailableLoadedValue(LoadInst *Load, BatchAAResults &AA,
772 bool *IsLoadCSE,
773 unsigned MaxInstsToScan) {
774 const DataLayout &DL = Load->getDataLayout();
775 Value *StrippedPtr = Load->getPointerOperand()->stripPointerCasts();
776 BasicBlock *ScanBB = Load->getParent();
777 Type *AccessTy = Load->getType();
778 bool AtLeastAtomic = Load->isAtomic();
779
780 if (!Load->isUnordered())
781 return nullptr;
782
783 // Try to find an available value first, and delay expensive alias analysis
784 // queries until later.
785 Value *Available = nullptr;
786 SmallVector<Instruction *> MustNotAliasInsts;
787 for (Instruction &Inst : make_range(x: ++Load->getReverseIterator(),
788 y: ScanBB->rend())) {
789 if (Inst.isDebugOrPseudoInst())
790 continue;
791
792 if (MaxInstsToScan-- == 0)
793 return nullptr;
794
795 Available = getAvailableLoadStore(Inst: &Inst, Ptr: StrippedPtr, AccessTy,
796 AtLeastAtomic, DL, IsLoadCSE);
797 if (Available)
798 break;
799
800 if (Inst.mayWriteToMemory())
801 MustNotAliasInsts.push_back(Elt: &Inst);
802 }
803
804 // If we found an available value, ensure that the instructions in between
805 // did not modify the memory location.
806 if (Available) {
807 MemoryLocation Loc = MemoryLocation::get(LI: Load);
808 for (Instruction *Inst : MustNotAliasInsts)
809 if (isModSet(MRI: AA.getModRefInfo(I: Inst, OptLoc: Loc)))
810 return nullptr;
811 }
812
813 return Available;
814}
815
816// Returns true if a use is either in an ICmp/PtrToInt or a Phi/Select that only
817// feeds into them.
818static bool isPointerUseReplaceable(const Use &U, bool HasNonAddressBits) {
819 unsigned Limit = 40;
820 SmallVector<const User *> Worklist({U.getUser()});
821 SmallPtrSet<const User *, 8> Visited;
822
823 while (!Worklist.empty() && --Limit) {
824 auto *User = Worklist.pop_back_val();
825 if (!Visited.insert(Ptr: User).second)
826 continue;
827 if (isa<ICmpInst, PtrToAddrInst>(Val: User))
828 continue;
829 // FIXME: The PtrToIntInst case here is not strictly correct, as it
830 // changes which provenance is exposed.
831 if (!HasNonAddressBits && isa<PtrToIntInst>(Val: User))
832 continue;
833 if (isa<PHINode, SelectInst>(Val: User))
834 Worklist.append(in_start: User->user_begin(), in_end: User->user_end());
835 else
836 return false;
837 }
838
839 return Limit != 0;
840}
841
842static bool isPointerAlwaysReplaceable(const Value *From, const Value *To,
843 const DataLayout &DL) {
844 // This is not strictly correct, but we do it for now to retain important
845 // optimizations.
846 if (isa<ConstantPointerNull>(Val: To))
847 return true;
848 // Conversely, replacing null in the default address space with destination
849 // pointer is always valid.
850 if (isa<ConstantPointerNull>(Val: From) &&
851 From->getType()->getPointerAddressSpace() == 0)
852 return true;
853 // Allow replacement with dereferenceable constants. This is not strictly
854 // correct, but required for vtable assumptions.
855 auto IsBasedOnConstantGlobal = [](const Value *V) {
856 auto *GV = dyn_cast<GlobalVariable>(Val: getUnderlyingObject(V));
857 return GV && GV->isConstant();
858 };
859 if (isa<Constant>(Val: To) && To->getType()->isPointerTy() &&
860 isDereferenceablePointer(V: To, Ty: Type::getInt8Ty(C&: To->getContext()), SQ: DL) &&
861 IsBasedOnConstantGlobal(To))
862 return true;
863 return getUnderlyingObjectAggressive(V: From) ==
864 getUnderlyingObjectAggressive(V: To);
865}
866
867bool llvm::canReplacePointersInUseIfEqual(const Use &U, const Value *To,
868 const DataLayout &DL) {
869 Type *Ty = To->getType();
870 assert(U->getType() == Ty && "values must have matching types");
871 // Not a pointer, just return true.
872 if (!Ty->isPtrOrPtrVectorTy())
873 return true;
874
875 // Do not perform replacements in lifetime intrinsic arguments.
876 if (isa<LifetimeIntrinsic>(Val: U.getUser()))
877 return false;
878
879 if (isPointerAlwaysReplaceable(From: &*U, To, DL))
880 return true;
881
882 bool HasNonAddressBits =
883 DL.getAddressSizeInBits(Ty) != DL.getPointerTypeSizeInBits(Ty);
884 return isPointerUseReplaceable(U, HasNonAddressBits);
885}
886
887bool llvm::canReplacePointersIfEqual(const Value *From, const Value *To,
888 const DataLayout &DL) {
889 assert(From->getType() == To->getType() && "values must have matching types");
890 // Not a pointer, just return true.
891 if (!From->getType()->isPtrOrPtrVectorTy())
892 return true;
893
894 return isPointerAlwaysReplaceable(From, To, DL);
895}
896
897bool llvm::isReadOnlyLoop(
898 Loop *L, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC,
899 SmallVectorImpl<LoadInst *> &NonDereferenceableAndAlignedLoads,
900 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
901 for (BasicBlock *BB : L->blocks()) {
902 for (Instruction &I : *BB) {
903 if (auto *LI = dyn_cast<LoadInst>(Val: &I)) {
904 if (!isDereferenceableAndAlignedInLoop(LI, L, SE&: *SE, DT&: *DT, AC, Predicates))
905 NonDereferenceableAndAlignedLoads.push_back(Elt: LI);
906 } else if (I.mayReadFromMemory() || I.mayWriteToMemory() ||
907 I.mayThrow()) {
908 return false;
909 }
910 }
911 }
912 return true;
913}
914
915LinearExpression llvm::decomposeLinearExpression(const DataLayout &DL,
916 Value *Ptr) {
917 assert(Ptr->getType()->isPointerTy() && "Must be called with pointer arg");
918
919 unsigned BitWidth = DL.getIndexTypeSizeInBits(Ty: Ptr->getType());
920 LinearExpression Expr(Ptr, BitWidth);
921
922 while (true) {
923 auto *GEP = dyn_cast<GEPOperator>(Val: Expr.BasePtr);
924 if (!GEP || GEP->getSourceElementType()->isScalableTy())
925 return Expr;
926
927 Value *VarIndex = nullptr;
928 for (Value *Index : GEP->indices()) {
929 if (isa<ConstantInt>(Val: Index))
930 continue;
931 // Only allow a single variable index. We do not bother to handle the
932 // case of the same variable index appearing multiple times.
933 if (Expr.Index || VarIndex)
934 return Expr;
935 VarIndex = Index;
936 }
937
938 // Don't return non-canonical indexes.
939 if (VarIndex && !VarIndex->getType()->isIntegerTy(BitWidth))
940 return Expr;
941
942 // We have verified that we can fully handle this GEP, so we can update Expr
943 // members past this point.
944 Expr.BasePtr = GEP->getPointerOperand();
945 Expr.Flags = Expr.Flags.intersectForOffsetAdd(Other: GEP->getNoWrapFlags());
946 for (gep_type_iterator GTI = gep_type_begin(GEP), GTE = gep_type_end(GEP);
947 GTI != GTE; ++GTI) {
948 Value *Index = GTI.getOperand();
949 if (auto *ConstOffset = dyn_cast<ConstantInt>(Val: Index)) {
950 if (ConstOffset->isZero())
951 continue;
952 if (StructType *STy = GTI.getStructTypeOrNull()) {
953 unsigned ElementIdx = ConstOffset->getZExtValue();
954 const StructLayout *SL = DL.getStructLayout(Ty: STy);
955 Expr.Offset += SL->getElementOffset(Idx: ElementIdx);
956 continue;
957 }
958 // Truncate if type size exceeds index space.
959 APInt IndexedSize(BitWidth, GTI.getSequentialElementStride(DL),
960 /*isSigned=*/false,
961 /*implcitTrunc=*/true);
962 Expr.Offset += ConstOffset->getValue() * IndexedSize;
963 continue;
964 }
965
966 // FIXME: Also look through a mul/shl in the index.
967 assert(Expr.Index == nullptr && "Shouldn't have index yet");
968 Expr.Index = Index;
969 // Truncate if type size exceeds index space.
970 Expr.Scale = APInt(BitWidth, GTI.getSequentialElementStride(DL),
971 /*isSigned=*/false, /*implicitTrunc=*/true);
972 }
973 }
974
975 return Expr;
976}
977