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