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