1//===- LoopAccessAnalysis.cpp - Loop Access Analysis Implementation --------==//
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// The implementation for the loop memory dependence that was originally
10// developed for the loop vectorizer.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/Analysis/LoopAccessAnalysis.h"
15#include "llvm/ADT/APInt.h"
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/EquivalenceClasses.h"
18#include "llvm/ADT/PointerIntPair.h"
19#include "llvm/ADT/STLExtras.h"
20#include "llvm/ADT/SetVector.h"
21#include "llvm/ADT/SmallPtrSet.h"
22#include "llvm/ADT/SmallSet.h"
23#include "llvm/ADT/SmallVector.h"
24#include "llvm/Analysis/AliasAnalysis.h"
25#include "llvm/Analysis/AliasSetTracker.h"
26#include "llvm/Analysis/AssumeBundleQueries.h"
27#include "llvm/Analysis/AssumptionCache.h"
28#include "llvm/Analysis/LoopAnalysisManager.h"
29#include "llvm/Analysis/LoopInfo.h"
30#include "llvm/Analysis/LoopIterator.h"
31#include "llvm/Analysis/MemoryLocation.h"
32#include "llvm/Analysis/OptimizationRemarkEmitter.h"
33#include "llvm/Analysis/ScalarEvolution.h"
34#include "llvm/Analysis/ScalarEvolutionExpressions.h"
35#include "llvm/Analysis/ScalarEvolutionPatternMatch.h"
36#include "llvm/Analysis/TargetLibraryInfo.h"
37#include "llvm/Analysis/TargetTransformInfo.h"
38#include "llvm/Analysis/ValueTracking.h"
39#include "llvm/Analysis/VectorUtils.h"
40#include "llvm/IR/BasicBlock.h"
41#include "llvm/IR/Constants.h"
42#include "llvm/IR/DataLayout.h"
43#include "llvm/IR/DebugLoc.h"
44#include "llvm/IR/DerivedTypes.h"
45#include "llvm/IR/DiagnosticInfo.h"
46#include "llvm/IR/Dominators.h"
47#include "llvm/IR/Function.h"
48#include "llvm/IR/InstrTypes.h"
49#include "llvm/IR/Instruction.h"
50#include "llvm/IR/Instructions.h"
51#include "llvm/IR/IntrinsicInst.h"
52#include "llvm/IR/PassManager.h"
53#include "llvm/IR/Type.h"
54#include "llvm/IR/Value.h"
55#include "llvm/IR/ValueHandle.h"
56#include "llvm/Support/Casting.h"
57#include "llvm/Support/CommandLine.h"
58#include "llvm/Support/Debug.h"
59#include "llvm/Support/ErrorHandling.h"
60#include "llvm/Support/MathExtras.h"
61#include "llvm/Support/raw_ostream.h"
62#include <algorithm>
63#include <cassert>
64#include <cstdint>
65#include <iterator>
66#include <utility>
67#include <variant>
68#include <vector>
69
70using namespace llvm;
71using namespace llvm::SCEVPatternMatch;
72
73#define DEBUG_TYPE "loop-accesses"
74
75static cl::opt<ElementCount, true>
76 VectorizationFactor("force-vector-width", cl::Hidden,
77 cl::desc("Sets the SIMD width. Zero is autoselect."),
78 cl::location(L&: VectorizerParams::VectorizationFactor));
79ElementCount VectorizerParams::VectorizationFactor;
80
81static cl::opt<unsigned, true>
82VectorizationInterleave("force-vector-interleave", cl::Hidden,
83 cl::desc("Sets the vectorization interleave count. "
84 "Zero is autoselect."),
85 cl::location(
86 L&: VectorizerParams::VectorizationInterleave));
87unsigned VectorizerParams::VectorizationInterleave;
88
89static cl::opt<unsigned, true> RuntimeMemoryCheckThreshold(
90 "runtime-memory-check-threshold", cl::Hidden,
91 cl::desc("When performing memory disambiguation checks at runtime do not "
92 "generate more than this number of comparisons (default = 8)."),
93 cl::location(L&: VectorizerParams::RuntimeMemoryCheckThreshold), cl::init(Val: 8));
94unsigned VectorizerParams::RuntimeMemoryCheckThreshold;
95
96/// The maximum iterations used to merge memory checks
97static cl::opt<unsigned> MemoryCheckMergeThreshold(
98 "memory-check-merge-threshold", cl::Hidden,
99 cl::desc("Maximum number of comparisons done when trying to merge "
100 "runtime memory checks. (default = 100)"),
101 cl::init(Val: 100));
102
103/// Maximum SIMD width.
104const unsigned VectorizerParams::MaxVectorWidth = 64;
105
106/// We collect dependences up to this threshold.
107static cl::opt<unsigned>
108 MaxDependences("max-dependences", cl::Hidden,
109 cl::desc("Maximum number of dependences collected by "
110 "loop-access analysis (default = 100)"),
111 cl::init(Val: 100));
112
113/// This enables versioning on the strides of symbolically striding memory
114/// accesses in code like the following.
115/// for (i = 0; i < N; ++i)
116/// A[i * Stride1] += B[i * Stride2] ...
117///
118/// Will be roughly translated to
119/// if (Stride1 == 1 && Stride2 == 1) {
120/// for (i = 0; i < N; i+=4)
121/// A[i:i+3] += ...
122/// } else
123/// ...
124static cl::opt<bool> EnableMemAccessVersioning(
125 "enable-mem-access-versioning", cl::init(Val: true), cl::Hidden,
126 cl::desc("Enable symbolic stride memory access versioning"));
127
128/// Enable store-to-load forwarding conflict detection. This option can
129/// be disabled for correctness testing.
130static cl::opt<bool> EnableForwardingConflictDetection(
131 "store-to-load-forwarding-conflict-detection", cl::Hidden,
132 cl::desc("Enable conflict detection in loop-access analysis"),
133 cl::init(Val: true));
134
135static cl::opt<unsigned> MaxForkedSCEVDepth(
136 "max-forked-scev-depth", cl::Hidden,
137 cl::desc("Maximum recursion depth when finding forked SCEVs (default = 5)"),
138 cl::init(Val: 5));
139
140static cl::opt<bool> SpeculateUnitStride(
141 "laa-speculate-unit-stride", cl::Hidden,
142 cl::desc("Speculate that non-constant strides are unit in LAA"),
143 cl::init(Val: true));
144
145static cl::opt<bool, true> HoistRuntimeChecks(
146 "hoist-runtime-checks", cl::Hidden,
147 cl::desc(
148 "Hoist inner loop runtime memory checks to outer loop if possible"),
149 cl::location(L&: VectorizerParams::HoistRuntimeChecks), cl::init(Val: true));
150bool VectorizerParams::HoistRuntimeChecks;
151
152bool VectorizerParams::isInterleaveForced() {
153 return ::VectorizationInterleave.getNumOccurrences() > 0;
154}
155
156const SCEV *
157llvm::replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE,
158 const SymbolicStrideMap &PtrToStride,
159 Value *Ptr) {
160 const SCEV *OrigSCEV = PSE.getSCEV(V: Ptr);
161
162 // If there is an entry in the map return the SCEV of the pointer with the
163 // symbolic stride replaced by one.
164 const SCEVUnknown *StrideSCEV = PtrToStride.lookup(Val: Ptr);
165 if (!StrideSCEV)
166 // For a non-symbolic stride, just return the original expression.
167 return OrigSCEV;
168
169 ScalarEvolution *SE = PSE.getSE();
170 const SCEV *CT = SE->getOne(Ty: StrideSCEV->getType());
171 PSE.addPredicate(Pred: *SE->getEqualPredicate(LHS: StrideSCEV, RHS: CT));
172 const SCEV *Expr = PSE.getSCEV(V: Ptr);
173
174 LLVM_DEBUG(dbgs() << "LAA: Replacing SCEV: " << *OrigSCEV
175 << " by: " << *Expr << "\n");
176 return Expr;
177}
178
179RuntimeCheckingPtrGroup::RuntimeCheckingPtrGroup(
180 unsigned Index, const RuntimePointerChecking &RtCheck)
181 : High(RtCheck.Pointers[Index].End), Low(RtCheck.Pointers[Index].Start),
182 AddressSpace(RtCheck.Pointers[Index]
183 .PointerValue->getType()
184 ->getPointerAddressSpace()),
185 NeedsFreeze(RtCheck.Pointers[Index].NeedsFreeze) {
186 Members.push_back(Elt: Index);
187}
188
189/// Returns \p A + \p B, if it is guaranteed not to unsigned wrap. Otherwise
190/// return nullptr. \p A and \p B must have the same type.
191static const SCEV *addSCEVNoOverflow(const SCEV *A, const SCEV *B,
192 ScalarEvolution &SE) {
193 if (!SE.willNotOverflow(BinOp: Instruction::Add, /*IsSigned=*/Signed: false, LHS: A, RHS: B))
194 return nullptr;
195 return SE.getAddExpr(LHS: A, RHS: B);
196}
197
198/// Returns \p A * \p B, if it is guaranteed not to unsigned wrap. Otherwise
199/// return nullptr. \p A and \p B must have the same type.
200static const SCEV *mulSCEVNoOverflow(const SCEV *A, const SCEV *B,
201 ScalarEvolution &SE) {
202 if (!SE.willNotOverflow(BinOp: Instruction::Mul, /*IsSigned=*/Signed: false, LHS: A, RHS: B))
203 return nullptr;
204 return SE.getMulExpr(LHS: A, RHS: B);
205}
206
207/// Return true, if evaluating \p AR at \p MaxBTC cannot wrap, because \p AR at
208/// \p MaxBTC is guaranteed inbounds of the accessed object.
209static bool evaluatePtrAddRecAtMaxBTCWillNotWrap(
210 const SCEVAddRecExpr *AR, const SCEV *MaxBTC, const SCEV *EltSize,
211 ScalarEvolution &SE, const DataLayout &DL, DominatorTree *DT,
212 AssumptionCache *AC,
213 std::optional<ScalarEvolution::LoopGuards> &LoopGuards) {
214 auto *PointerBase = SE.getPointerBase(V: AR->getStart());
215 auto *StartPtr = dyn_cast<SCEVUnknown>(Val: PointerBase);
216 if (!StartPtr)
217 return false;
218 const Loop *L = AR->getLoop();
219 bool CheckForNonNull;
220 Value *StartPtrV = StartPtr->getValue();
221 // We can ignore frees, as the fact that an object of a certain size existed
222 // at the location *at some point* is sufficient to derive the nowrap fact.
223 uint64_t DerefBytes = StartPtrV->getPointerDereferenceableBytes(
224 DL, CanBeNull&: CheckForNonNull, /*CanBeFreed=*/nullptr);
225
226 // If the deref size is only known when the pointer is non-null, ignore it
227 // here and fall back to a dereferenceable assumption below.
228 if (DerefBytes && CheckForNonNull)
229 DerefBytes = 0;
230
231 const SCEV *Step = AR->getStepRecurrence(SE);
232 Type *WiderTy = SE.getWiderType(Ty1: MaxBTC->getType(), Ty2: Step->getType());
233 const SCEV *DerefBytesSCEV = SE.getConstant(Ty: WiderTy, V: DerefBytes);
234
235 // Check if we have a suitable dereferencable assumption we can use.
236 Instruction *CtxI = &*L->getHeader()->getFirstNonPHIIt();
237 if (BasicBlock *LoopPred = L->getLoopPredecessor()) {
238 if (isa<UncondBrInst, CondBrInst>(Val: LoopPred->getTerminator()))
239 CtxI = LoopPred->getTerminator();
240 }
241 getKnowledgeForValue(
242 V: StartPtrV, AttrKinds: Attribute::Dereferenceable, AC&: *AC,
243 Filter: [&](RetainedKnowledge RK, Instruction *Assume, auto) {
244 if (!isValidAssumeForContext(I: Assume, CxtI: CtxI, DT))
245 return false;
246 const SCEV *DerefRKSCEV = SE.getSCEV(V: RK.IRArgValue);
247 Type *CommonTy =
248 SE.getWiderType(Ty1: DerefBytesSCEV->getType(), Ty2: DerefRKSCEV->getType());
249 DerefBytesSCEV = SE.getNoopOrZeroExtend(V: DerefBytesSCEV, Ty: CommonTy);
250 DerefRKSCEV = SE.getNoopOrZeroExtend(V: DerefRKSCEV, Ty: CommonTy);
251 DerefBytesSCEV = SE.getUMaxExpr(LHS: DerefBytesSCEV, RHS: DerefRKSCEV);
252 // Continue with other assumptions.
253 return false;
254 });
255
256 if (DerefBytesSCEV->isZero())
257 return false;
258
259 bool IsKnownNonNegative = SE.isKnownNonNegative(S: Step);
260 if (!IsKnownNonNegative && !SE.isKnownNegative(S: Step))
261 return false;
262
263 WiderTy = SE.getWiderType(Ty1: WiderTy, Ty2: DerefBytesSCEV->getType());
264 Step = SE.getNoopOrSignExtend(V: Step, Ty: WiderTy);
265 MaxBTC = SE.getNoopOrZeroExtend(V: MaxBTC, Ty: WiderTy);
266
267 // For the computations below, make sure they don't unsigned wrap.
268 // FIXME: for a negative step the lowest accessed address is not
269 // AR->getStart() but AR->evaluateAtIteration(MaxBTC, SE); the check below
270 // therefore compares StartPtr against the highest accessed address instead
271 // of the lowest.
272 if (!SE.isKnownPredicate(Pred: CmpInst::ICMP_UGE, LHS: AR->getStart(), RHS: StartPtr))
273 return false;
274 const SCEV *StartOffset = SE.getNoopOrZeroExtend(
275 V: SE.getMinusSCEV(LHS: AR->getStart(), RHS: StartPtr), Ty: WiderTy);
276
277 if (!LoopGuards)
278 LoopGuards.emplace(args: ScalarEvolution::LoopGuards::collect(L: AR->getLoop(), SE));
279 MaxBTC = SE.applyLoopGuards(Expr: MaxBTC, Guards: *LoopGuards);
280
281 const SCEV *AbsStep = SE.getAbsExpr(Op: Step, /*IsNSW=*/false);
282 // Total distance (in bytes) between the first and the last
283 // accessed pointer.
284 const SCEV *DistToLastIter = mulSCEVNoOverflow(A: MaxBTC, B: AbsStep, SE);
285 if (!DistToLastIter) {
286 // Re-try with constant max backedge-taken count if using the symbolic one
287 // failed.
288 MaxBTC = SE.getConstantMaxBackedgeTakenCount(L: AR->getLoop());
289 if (isa<SCEVCouldNotCompute>(Val: MaxBTC))
290 return false;
291 MaxBTC = SE.getNoopOrZeroExtend(V: MaxBTC, Ty: WiderTy);
292 DistToLastIter = mulSCEVNoOverflow(A: MaxBTC, B: AbsStep, SE);
293 if (!DistToLastIter)
294 return false;
295 }
296
297 // Total length in bytes of the accessed range (from the first accessed
298 // byte through the end of the last access).
299 const SCEV *AccessedBytes = addSCEVNoOverflow(
300 A: DistToLastIter, B: SE.getNoopOrZeroExtend(V: EltSize, Ty: WiderTy), SE);
301 if (!AccessedBytes)
302 return false;
303
304 // Compute MaxOffset per direction: exclusive upper offset of the
305 // accessed range.
306 const SCEV *MaxOffset;
307 if (IsKnownNonNegative) {
308 MaxOffset = addSCEVNoOverflow(A: StartOffset, B: AccessedBytes, SE);
309 if (!MaxOffset)
310 return false;
311 DerefBytesSCEV = SE.applyLoopGuards(Expr: DerefBytesSCEV, Guards: *LoopGuards);
312 } else {
313 // FIXME: two independent off-by-EltSize bugs on this branch:
314 // 1. StartOffset here is actually the HIGHEST offset, because it is
315 // computed from AR->getStart() rather than
316 // AR->evaluateAtIteration(MaxBTC, SE) (see FIXME above).
317 // 2. The lower check is over-strict by EltSize and the upper is
318 // under-counted by EltSize.
319 assert(SE.isKnownNegative(Step) && "must be known negative");
320 if (!SE.isKnownPredicate(Pred: CmpInst::ICMP_SGE, LHS: StartOffset, RHS: AccessedBytes))
321 return false;
322 MaxOffset = StartOffset;
323 }
324 // MaxOffset must not exceed the deref-region end.
325 return SE.isKnownPredicate(Pred: CmpInst::ICMP_ULE, LHS: MaxOffset, RHS: DerefBytesSCEV);
326}
327
328/// Return true if \p S is known to be monotonically non-decreasing
329/// (in the unsigned sense, without unsigned wrap) across iterations of \p L.
330static bool isKnownNonDecreasingInLoop(const SCEV *S, const Loop *L,
331 ScalarEvolution &SE) {
332 if (SE.isLoopInvariant(S, L))
333 return true;
334
335 switch (S->getSCEVType()) {
336 case scUDivExpr: {
337 // Non-decreasing in the numerator when the divisor is loop-invariant.
338 const auto *UDiv = cast<SCEVUDivExpr>(Val: S);
339 return SE.isLoopInvariant(S: UDiv->getRHS(), L) &&
340 isKnownNonDecreasingInLoop(S: UDiv->getLHS(), L, SE);
341 }
342 case scAddRecExpr: {
343 auto *AR = cast<SCEVAddRecExpr>(Val: S);
344 assert(AR->getLoop() == L &&
345 "trying to check for AddRec in different loop");
346 return SE.getMonotonicPredicateType(LHS: AR, Pred: ICmpInst::ICMP_UGE) ==
347 ScalarEvolution::MonotonicPredicateType::MonotonicallyIncreasing;
348 }
349 default:
350 return false;
351 }
352}
353
354/// Try to bound a loop-variant pointer that is not an affine AddRec.
355///
356/// If the offset is provably monotonically non-decreasing the accessed range is
357/// bounded by the offset's value at the first iteration (via
358/// SplitIntoInitAndPostInc) and last iteration (via getSCEVAtScope). The
359/// returned range is half-open: \p EltSizeSCEV is added to the address of the
360/// last accessed element to form the end.
361///
362/// Returns {nullptr, nullptr} if no such bound can be formed.
363static std::pair<const SCEV *, const SCEV *>
364getNonAffineMonotonicBounds(const Loop *Lp, const SCEV *PtrExpr,
365 const SCEV *EltSizeSCEV, ScalarEvolution *SE) {
366 const auto *PtrAdd = dyn_cast<SCEVAddExpr>(Val: PtrExpr);
367 if (!PtrAdd || !PtrAdd->hasNoUnsignedWrap())
368 return {nullptr, nullptr};
369
370 const SCEV *Base = *find_if(Range: PtrAdd->operands(), P: [](const auto &Op) {
371 return Op->getType()->isPointerTy();
372 });
373 if (isa<SCEVCouldNotCompute>(Val: Base) || !SE->isLoopInvariant(S: Base, L: Lp))
374 return {nullptr, nullptr};
375
376 const SCEV *Offset = SE->getMinusSCEV(LHS: PtrExpr, RHS: Base);
377 if (isa<SCEVCouldNotCompute>(Val: Offset) ||
378 !isKnownNonDecreasingInLoop(S: Offset, L: Lp, SE&: *SE))
379 return {nullptr, nullptr};
380
381 const SCEV *OffStart = SE->SplitIntoInitAndPostInc(L: Lp, S: Offset).first;
382 const SCEV *OffEnd = SE->getSCEVAtScope(S: Offset, L: Lp->getParentLoop());
383 if (isa<SCEVCouldNotCompute>(Val: OffStart) || isa<SCEVCouldNotCompute>(Val: OffEnd) ||
384 !SE->isLoopInvariant(S: OffStart, L: Lp) || !SE->isLoopInvariant(S: OffEnd, L: Lp))
385 return {nullptr, nullptr};
386
387 return {SE->getAddExpr(LHS: Base, RHS: OffStart),
388 SE->getAddExpr(Op0: Base, Op1: OffEnd, Op2: EltSizeSCEV)};
389}
390
391std::pair<const SCEV *, const SCEV *> llvm::getStartAndEndForAccess(
392 const Loop *Lp, const SCEV *PtrExpr, Type *AccessTy, const SCEV *BTC,
393 const SCEV *MaxBTC, ScalarEvolution *SE,
394 DenseMap<std::pair<const SCEV *, const SCEV *>,
395 std::pair<const SCEV *, const SCEV *>> *PointerBounds,
396 DominatorTree *DT, AssumptionCache *AC,
397 std::optional<ScalarEvolution::LoopGuards> &LoopGuards) {
398 auto &DL = Lp->getHeader()->getDataLayout();
399 Type *IdxTy = DL.getIndexType(PtrTy: PtrExpr->getType());
400 const SCEV *EltSizeSCEV = SE->getStoreSizeOfExpr(IntTy: IdxTy, StoreTy: AccessTy);
401
402 // Delegate to the SCEV-based overload, passing through the cache.
403 return getStartAndEndForAccess(Lp, PtrExpr, EltSizeSCEV, BTC, MaxBTC, SE,
404 PointerBounds, DT, AC, LoopGuards);
405}
406
407std::pair<const SCEV *, const SCEV *> llvm::getStartAndEndForAccess(
408 const Loop *Lp, const SCEV *PtrExpr, const SCEV *EltSizeSCEV,
409 const SCEV *BTC, const SCEV *MaxBTC, ScalarEvolution *SE,
410 DenseMap<std::pair<const SCEV *, const SCEV *>,
411 std::pair<const SCEV *, const SCEV *>> *PointerBounds,
412 DominatorTree *DT, AssumptionCache *AC,
413 std::optional<ScalarEvolution::LoopGuards> &LoopGuards) {
414 std::pair<const SCEV *, const SCEV *> *PtrBoundsPair;
415 if (PointerBounds) {
416 auto [Iter, Ins] = PointerBounds->insert(
417 KV: {{PtrExpr, EltSizeSCEV},
418 {SE->getCouldNotCompute(), SE->getCouldNotCompute()}});
419 if (!Ins)
420 return Iter->second;
421 PtrBoundsPair = &Iter->second;
422 }
423
424 // ScStart is the lowest accessed address; ScEnd is the highest one plus the
425 // size of the accessed element.
426 const SCEV *ScStart;
427 const SCEV *ScEnd;
428
429 auto &DL = Lp->getHeader()->getDataLayout();
430 if (SE->isLoopInvariant(S: PtrExpr, L: Lp)) {
431 ScStart = PtrExpr;
432 ScEnd = SE->getAddExpr(LHS: PtrExpr, RHS: EltSizeSCEV);
433 } else if (auto *AR = dyn_cast<SCEVAddRecExpr>(Val: PtrExpr)) {
434 const SCEV *Step = AR->getStepRecurrence(SE&: *SE);
435 // The address of the last accessed element, if it can be computed
436 // precisely.
437 const SCEV *LastAddr = nullptr;
438 if (!isa<SCEVCouldNotCompute>(Val: BTC)) {
439 // Evaluating AR at an exact BTC is safe: LAA separately checks that
440 // accesses cannot wrap in the loop. If evaluating AR at BTC wraps, then
441 // the loop either triggers UB when executing a memory access with a
442 // poison pointer or the wrapping/poisoned pointer is not used.
443 LastAddr = AR->evaluateAtIteration(It: BTC, SE&: *SE);
444 } else if (evaluatePtrAddRecAtMaxBTCWillNotWrap(
445 AR, MaxBTC, EltSize: EltSizeSCEV, SE&: *SE, DL, DT, AC, LoopGuards)) {
446 LastAddr = AR->evaluateAtIteration(It: MaxBTC, SE&: *SE);
447 }
448 const SCEV *Start = AR->getStart();
449 Type *PtrTy = AR->getType();
450 if (SE->isKnownNegative(S: Step)) {
451 ScStart =
452 LastAddr
453 ? LastAddr
454 : SE->getSCEV(V: ConstantExpr::getIntToPtr(
455 C: Constant::getNullValue(Ty: DL.getIndexType(PtrTy)), Ty: PtrTy));
456 ScEnd = SE->getAddExpr(LHS: Start, RHS: EltSizeSCEV);
457 } else if (SE->isKnownNonNegative(S: Step)) {
458 ScStart = Start;
459 // The highest address for the type saturates; adding EltSize to it would
460 // wrap to the start of the address space.
461 if (LastAddr)
462 ScEnd = SE->getAddExpr(LHS: LastAddr, RHS: EltSizeSCEV);
463 else
464 ScEnd = SE->getSCEV(V: ConstantExpr::getIntToPtr(
465 C: Constant::getAllOnesValue(Ty: DL.getIndexType(PtrTy)), Ty: PtrTy));
466 } else {
467 if (!LastAddr)
468 return {SE->getCouldNotCompute(), SE->getCouldNotCompute()};
469 // Fallback case: the step is not constant, but we can still
470 // get the upper and lower bounds of the interval by using min/max
471 // expressions.
472 ScStart = SE->getUMinExpr(LHS: Start, RHS: LastAddr);
473 ScEnd = SE->getAddExpr(LHS: SE->getUMaxExpr(LHS: Start, RHS: LastAddr), RHS: EltSizeSCEV);
474 }
475 } else {
476 // The pointer is loop-variant but not an affine AddRec. Try to form a
477 // tight bound for a monotonic offset (see getNonAffineMonotonicBounds).
478 std::tie(args&: ScStart, args&: ScEnd) =
479 getNonAffineMonotonicBounds(Lp, PtrExpr, EltSizeSCEV, SE);
480 if (!ScStart)
481 return {SE->getCouldNotCompute(), SE->getCouldNotCompute()};
482 }
483
484 assert(SE->isLoopInvariant(ScStart, Lp) && "ScStart needs to be invariant");
485 assert(SE->isLoopInvariant(ScEnd, Lp) && "ScEnd needs to be invariant");
486
487 std::pair<const SCEV *, const SCEV *> Res = {ScStart, ScEnd};
488 if (PointerBounds)
489 *PtrBoundsPair = Res;
490 return Res;
491}
492
493/// Calculate Start and End points of memory access using
494/// getStartAndEndForAccess.
495bool RuntimePointerChecking::insert(Loop *Lp, Value *Ptr, const SCEV *PtrExpr,
496 Type *AccessTy, bool WritePtr,
497 unsigned DepSetId, unsigned ASId,
498 PredicatedScalarEvolution &PSE,
499 bool NeedsFreeze) {
500 const SCEV *SymbolicMaxBTC = PSE.getSymbolicMaxBackedgeTakenCount();
501 const SCEV *BTC = PSE.getBackedgeTakenCount();
502 const auto &[ScStart, ScEnd] = getStartAndEndForAccess(
503 Lp, PtrExpr, AccessTy, BTC, MaxBTC: SymbolicMaxBTC, SE: PSE.getSE(),
504 PointerBounds: &DC.getPointerBounds(), DT: DC.getDT(), AC: DC.getAC(), LoopGuards);
505 if (isa<SCEVCouldNotCompute>(Val: ScStart) || isa<SCEVCouldNotCompute>(Val: ScEnd))
506 return false;
507 Pointers.emplace_back(Args&: Ptr, Args: ScStart, Args: ScEnd, Args&: WritePtr, Args&: DepSetId, Args&: ASId, Args&: PtrExpr,
508 Args&: NeedsFreeze);
509 return true;
510}
511
512bool RuntimePointerChecking::tryToCreateDiffCheck(
513 const RuntimeCheckingPtrGroup &CGI, const RuntimeCheckingPtrGroup &CGJ) {
514 // If either group contains multiple different pointers, bail out.
515 // TODO: Support multiple pointers by using the minimum or maximum pointer,
516 // depending on src & sink.
517 if (CGI.Members.size() != 1 || CGJ.Members.size() != 1)
518 return false;
519
520 const PointerInfo *Src = &Pointers[CGI.Members[0]];
521 const PointerInfo *Sink = &Pointers[CGJ.Members[0]];
522
523 // If either pointer is read and written, multiple checks may be needed. Bail
524 // out.
525 if (!DC.getOrderForAccess(Ptr: Src->PointerValue, IsWrite: !Src->IsWritePtr).empty() ||
526 !DC.getOrderForAccess(Ptr: Sink->PointerValue, IsWrite: !Sink->IsWritePtr).empty())
527 return false;
528
529 ArrayRef<unsigned> AccSrc =
530 DC.getOrderForAccess(Ptr: Src->PointerValue, IsWrite: Src->IsWritePtr);
531 ArrayRef<unsigned> AccSink =
532 DC.getOrderForAccess(Ptr: Sink->PointerValue, IsWrite: Sink->IsWritePtr);
533 // If either pointer is accessed multiple times, there may not be a clear
534 // src/sink relation. Bail out for now.
535 if (AccSrc.size() != 1 || AccSink.size() != 1)
536 return false;
537
538 // If the sink is accessed before src, swap src/sink.
539 if (AccSink[0] < AccSrc[0])
540 std::swap(a&: Src, b&: Sink);
541
542 const SCEVConstant *Step;
543 const SCEV *SrcStart;
544 const SCEV *SinkStart;
545 const Loop *InnerLoop = DC.getInnermostLoop();
546 if (!match(S: Src->Expr,
547 P: m_scev_AffineAddRec(Op0: m_SCEV(V&: SrcStart), Op1: m_SCEVConstant(V&: Step),
548 L: m_SpecificLoop(L: InnerLoop))) ||
549 !match(S: Sink->Expr,
550 P: m_scev_AffineAddRec(Op0: m_SCEV(V&: SinkStart), Op1: m_scev_Specific(S: Step),
551 L: m_SpecificLoop(L: InnerLoop))))
552 return false;
553
554 SmallVector<Instruction *, 4> SrcInsts =
555 DC.getInstructionsForAccess(Ptr: Src->PointerValue, isWrite: Src->IsWritePtr);
556 SmallVector<Instruction *, 4> SinkInsts =
557 DC.getInstructionsForAccess(Ptr: Sink->PointerValue, isWrite: Sink->IsWritePtr);
558 Type *SrcTy = getLoadStoreType(I: SrcInsts[0]);
559 Type *DstTy = getLoadStoreType(I: SinkInsts[0]);
560 if (isa<ScalableVectorType>(Val: SrcTy) || isa<ScalableVectorType>(Val: DstTy))
561 return false;
562
563 const DataLayout &DL = InnerLoop->getHeader()->getDataLayout();
564 unsigned AllocSize =
565 std::max(a: DL.getTypeAllocSize(Ty: SrcTy), b: DL.getTypeAllocSize(Ty: DstTy));
566
567 // Only matching constant steps matching the AllocSize are supported at the
568 // moment. This simplifies the difference computation. Can be extended in the
569 // future.
570 if (Step->getAPInt().abs() != AllocSize)
571 return false;
572
573 // When counting down, the dependence distance needs to be swapped.
574 if (Step->getValue()->isNegative())
575 std::swap(a&: SinkStart, b&: SrcStart);
576
577 const SCEV *SinkStartInt = SE->getPtrToAddrExpr(Op: SinkStart);
578 const SCEV *SrcStartInt = SE->getPtrToAddrExpr(Op: SrcStart);
579 if (isa<SCEVCouldNotCompute>(Val: SinkStartInt) ||
580 isa<SCEVCouldNotCompute>(Val: SrcStartInt))
581 return false;
582
583 // If the start values for both Src and Sink also vary according to an outer
584 // loop, then it's probably better to avoid creating diff checks because
585 // they may not be hoisted. We should instead let llvm::addRuntimeChecks
586 // do the expanded full range overlap checks, which can be hoisted.
587 if (HoistRuntimeChecks && InnerLoop->getParentLoop() &&
588 isa<SCEVAddRecExpr>(Val: SinkStartInt) && isa<SCEVAddRecExpr>(Val: SrcStartInt)) {
589 auto *SrcStartAR = cast<SCEVAddRecExpr>(Val: SrcStartInt);
590 auto *SinkStartAR = cast<SCEVAddRecExpr>(Val: SinkStartInt);
591 const Loop *StartARLoop = SrcStartAR->getLoop();
592 if (StartARLoop == SinkStartAR->getLoop() &&
593 StartARLoop == InnerLoop->getParentLoop() &&
594 // If the diff check would already be loop invariant (due to the
595 // recurrences being the same), then we prefer to keep the diff checks
596 // because they are cheaper.
597 SrcStartAR->getStepRecurrence(SE&: *SE) !=
598 SinkStartAR->getStepRecurrence(SE&: *SE)) {
599 LLVM_DEBUG(dbgs() << "LAA: Not creating diff runtime check, since these "
600 "cannot be hoisted out of the outer loop\n");
601 return false;
602 }
603 }
604
605 LLVM_DEBUG(dbgs() << "LAA: Creating diff runtime check for:\n"
606 << "SrcStart: " << *SrcStartInt << '\n'
607 << "SinkStartInt: " << *SinkStartInt << '\n');
608 DiffChecks.emplace_back(Args&: SrcStartInt, Args&: SinkStartInt, Args&: AllocSize,
609 Args: Src->NeedsFreeze || Sink->NeedsFreeze);
610 return true;
611}
612
613SmallVector<RuntimePointerCheck, 4> RuntimePointerChecking::generateChecks() {
614 SmallVector<RuntimePointerCheck, 4> Checks;
615
616 for (unsigned I = 0; I < CheckingGroups.size(); ++I) {
617 for (unsigned J = I + 1; J < CheckingGroups.size(); ++J) {
618 const RuntimeCheckingPtrGroup &CGI = CheckingGroups[I];
619 const RuntimeCheckingPtrGroup &CGJ = CheckingGroups[J];
620
621 if (needsChecking(M: CGI, N: CGJ)) {
622 CanUseDiffCheck = CanUseDiffCheck && tryToCreateDiffCheck(CGI, CGJ);
623 Checks.emplace_back(Args: &CGI, Args: &CGJ);
624 }
625 }
626 }
627 return Checks;
628}
629
630void RuntimePointerChecking::generateChecks(
631 MemoryDepChecker::DepCandidates &DepCands) {
632 assert(Checks.empty() && "Checks is not empty");
633 groupChecks(DepCands);
634 Checks = generateChecks();
635}
636
637bool RuntimePointerChecking::needsChecking(
638 const RuntimeCheckingPtrGroup &M, const RuntimeCheckingPtrGroup &N) const {
639 for (const auto &I : M.Members)
640 for (const auto &J : N.Members)
641 if (needsChecking(I, J))
642 return true;
643 return false;
644}
645
646/// Compare \p I and \p J and return the minimum.
647/// Return nullptr in case we couldn't find an answer.
648static const SCEV *getMinFromExprs(const SCEV *I, const SCEV *J,
649 ScalarEvolution *SE) {
650 std::optional<APInt> Diff = SE->computeConstantDifference(LHS: J, RHS: I);
651 if (!Diff)
652 return nullptr;
653 return Diff->isNegative() ? J : I;
654}
655
656bool RuntimeCheckingPtrGroup::addPointer(
657 unsigned Index, const RuntimePointerChecking &RtCheck) {
658 return addPointer(
659 Index, Start: RtCheck.Pointers[Index].Start, End: RtCheck.Pointers[Index].End,
660 AS: RtCheck.Pointers[Index].PointerValue->getType()->getPointerAddressSpace(),
661 NeedsFreeze: RtCheck.Pointers[Index].NeedsFreeze, SE&: *RtCheck.SE);
662}
663
664bool RuntimeCheckingPtrGroup::addPointer(unsigned Index, const SCEV *Start,
665 const SCEV *End, unsigned AS,
666 bool NeedsFreeze,
667 ScalarEvolution &SE) {
668 assert(AddressSpace == AS &&
669 "all pointers in a checking group must be in the same address space");
670
671 // Compare the starts and ends with the known minimum and maximum
672 // of this set. We need to know how we compare against the min/max
673 // of the set in order to be able to emit memchecks.
674 const SCEV *Min0 = getMinFromExprs(I: Start, J: Low, SE: &SE);
675 if (!Min0)
676 return false;
677
678 const SCEV *Min1 = getMinFromExprs(I: End, J: High, SE: &SE);
679 if (!Min1)
680 return false;
681
682 // Update the low bound expression if we've found a new min value.
683 if (Min0 == Start)
684 Low = Start;
685
686 // Update the high bound expression if we've found a new max value.
687 if (Min1 != End)
688 High = End;
689
690 Members.push_back(Elt: Index);
691 this->NeedsFreeze |= NeedsFreeze;
692 return true;
693}
694
695void RuntimePointerChecking::groupChecks(
696 MemoryDepChecker::DepCandidates &DepCands) {
697 // We build the groups from dependency candidates equivalence classes
698 // because:
699 // - We know that pointers in the same equivalence class share
700 // the same underlying object and therefore there is a chance
701 // that we can compare pointers
702 // - We wouldn't be able to merge two pointers for which we need
703 // to emit a memcheck. The classes in DepCands are already
704 // conveniently built such that no two pointers in the same
705 // class need checking against each other.
706
707 // We use the following (greedy) algorithm to construct the groups
708 // For every pointer in the equivalence class:
709 // For each existing group:
710 // - if the difference between this pointer and the min/max bounds
711 // of the group is a constant, then make the pointer part of the
712 // group and update the min/max bounds of that group as required.
713
714 CheckingGroups.clear();
715
716 // If we need to check two pointers to the same underlying object
717 // with a non-constant difference, we shouldn't perform any pointer
718 // grouping with those pointers. This is because we can easily get
719 // into cases where the resulting check would return false, even when
720 // the accesses are safe.
721 //
722 // The following example shows this:
723 // for (i = 0; i < 1000; ++i)
724 // a[5000 + i * m] = a[i] + a[i + 9000]
725 //
726 // Here grouping gives a check of (5000, 5000 + 1000 * m) against
727 // (0, 10000) which is always false. However, if m is 1, there is no
728 // dependence. Not grouping the checks for a[i] and a[i + 9000] allows
729 // us to perform an accurate check in this case.
730 //
731 // In the above case, we have a non-constant distance and an Unknown
732 // dependence between accesses to the same underlying object, and could retry
733 // with runtime checks without dependency information being available. In this
734 // case we will use the fallback path and create separate checking groups for
735 // accesses not present in DepCands.
736
737 unsigned TotalComparisons = 0;
738
739 DenseMap<Value *, SmallVector<unsigned>> PositionMap;
740 for (unsigned Index = 0; Index < Pointers.size(); ++Index)
741 PositionMap[Pointers[Index].PointerValue].push_back(Elt: Index);
742
743 // We need to keep track of what pointers we've already seen so we
744 // don't process them twice.
745 SmallSet<unsigned, 2> Seen;
746
747 // Go through all equivalence classes, get the "pointer check groups"
748 // and add them to the overall solution. We use the order in which accesses
749 // appear in 'Pointers' to enforce determinism.
750 for (unsigned I = 0; I < Pointers.size(); ++I) {
751 // We've seen this pointer before, and therefore already processed
752 // its equivalence class.
753 if (Seen.contains(V: I))
754 continue;
755
756 MemoryDepChecker::MemAccessInfo Access(Pointers[I].PointerValue,
757 Pointers[I].IsWritePtr);
758
759 // If there is no entry in the dependency partition, there are no potential
760 // accesses to merge; simply add a new pointer checking group.
761 if (!DepCands.contains(V: Access)) {
762 CheckingGroups.push_back(Elt: RuntimeCheckingPtrGroup(I, *this));
763 continue;
764 }
765
766 SmallVector<RuntimeCheckingPtrGroup, 2> Groups;
767
768 // Because DepCands is constructed by visiting accesses in the order in
769 // which they appear in alias sets (which is deterministic) and the
770 // iteration order within an equivalence class member is only dependent on
771 // the order in which unions and insertions are performed on the
772 // equivalence class, the iteration order is deterministic.
773 for (auto M : DepCands.members(V: Access)) {
774 auto PointerI = PositionMap.find(Val: M.getPointer());
775 // If we can't find the pointer in PositionMap that means we can't
776 // generate a memcheck for it.
777 if (PointerI == PositionMap.end())
778 continue;
779 for (unsigned Pointer : PointerI->second) {
780 bool Merged = false;
781 // Mark this pointer as seen.
782 Seen.insert(V: Pointer);
783
784 // Go through all the existing sets and see if we can find one
785 // which can include this pointer.
786 for (RuntimeCheckingPtrGroup &Group : Groups) {
787 // Don't perform more than a certain amount of comparisons.
788 // This should limit the cost of grouping the pointers to something
789 // reasonable. If we do end up hitting this threshold, the algorithm
790 // will create separate groups for all remaining pointers.
791 if (TotalComparisons > MemoryCheckMergeThreshold)
792 break;
793
794 TotalComparisons++;
795
796 if (Group.addPointer(Index: Pointer, RtCheck: *this)) {
797 Merged = true;
798 break;
799 }
800 }
801
802 if (!Merged)
803 // We couldn't add this pointer to any existing set or the threshold
804 // for the number of comparisons has been reached. Create a new group
805 // to hold the current pointer.
806 Groups.emplace_back(Args&: Pointer, Args&: *this);
807 }
808 }
809
810 // We've computed the grouped checks for this partition.
811 // Save the results and continue with the next one.
812 llvm::append_range(C&: CheckingGroups, R&: Groups);
813 }
814}
815
816bool RuntimePointerChecking::arePointersInSamePartition(
817 const SmallVectorImpl<int> &PtrToPartition, unsigned PtrIdx1,
818 unsigned PtrIdx2) {
819 return (PtrToPartition[PtrIdx1] != -1 &&
820 PtrToPartition[PtrIdx1] == PtrToPartition[PtrIdx2]);
821}
822
823bool RuntimePointerChecking::needsChecking(unsigned I, unsigned J) const {
824 const PointerInfo &PointerI = Pointers[I];
825 const PointerInfo &PointerJ = Pointers[J];
826
827 // No need to check if two readonly pointers intersect.
828 if (!PointerI.IsWritePtr && !PointerJ.IsWritePtr)
829 return false;
830
831 // Only need to check pointers between two different dependency sets.
832 if (PointerI.DependencySetId == PointerJ.DependencySetId)
833 return false;
834
835 // Only need to check pointers in the same alias set.
836 return PointerI.AliasSetId == PointerJ.AliasSetId;
837}
838
839/// Assign each RuntimeCheckingPtrGroup pointer an index for stable UTC output.
840static DenseMap<const RuntimeCheckingPtrGroup *, unsigned>
841getPtrToIdxMap(ArrayRef<RuntimeCheckingPtrGroup> CheckingGroups) {
842 DenseMap<const RuntimeCheckingPtrGroup *, unsigned> PtrIndices;
843 for (const auto &[Idx, CG] : enumerate(First&: CheckingGroups))
844 PtrIndices[&CG] = Idx;
845 return PtrIndices;
846}
847
848void RuntimePointerChecking::printChecks(
849 raw_ostream &OS, const SmallVectorImpl<RuntimePointerCheck> &Checks,
850 unsigned Depth) const {
851 unsigned N = 0;
852 auto PtrIndices = getPtrToIdxMap(CheckingGroups);
853 for (const auto &[Check1, Check2] : Checks) {
854 const auto &First = Check1->Members, &Second = Check2->Members;
855 OS.indent(NumSpaces: Depth) << "Check " << N++ << ":\n";
856 OS.indent(NumSpaces: Depth + 2) << "Comparing group GRP" << PtrIndices.at(Val: Check1)
857 << ":\n";
858 for (unsigned K : First)
859 OS.indent(NumSpaces: Depth + 2) << *Pointers[K].PointerValue << "\n";
860 OS.indent(NumSpaces: Depth + 2) << "Against group GRP" << PtrIndices.at(Val: Check2)
861 << ":\n";
862 for (unsigned K : Second)
863 OS.indent(NumSpaces: Depth + 2) << *Pointers[K].PointerValue << "\n";
864 }
865}
866
867void RuntimePointerChecking::print(raw_ostream &OS, unsigned Depth) const {
868
869 OS.indent(NumSpaces: Depth) << "Run-time memory checks:\n";
870 printChecks(OS, Checks, Depth);
871
872 OS.indent(NumSpaces: Depth) << "Grouped accesses:\n";
873 auto PtrIndices = getPtrToIdxMap(CheckingGroups);
874 for (const auto &CG : CheckingGroups) {
875 OS.indent(NumSpaces: Depth + 2) << "Group GRP" << PtrIndices.at(Val: &CG) << ":\n";
876 OS.indent(NumSpaces: Depth + 4) << "(Low: " << *CG.Low << " High: " << *CG.High
877 << ")\n";
878 for (unsigned Member : CG.Members) {
879 OS.indent(NumSpaces: Depth + 6) << "Member: " << *Pointers[Member].Expr << "\n";
880 }
881 }
882}
883
884namespace {
885
886/// Analyses memory accesses in a loop.
887///
888/// Checks whether run time pointer checks are needed and builds sets for data
889/// dependence checking.
890class AccessAnalysis {
891public:
892 using MemAccessInfo =
893 PointerIntPair<Value * /* AccessPtr */, 1, bool /* IsWrite */>;
894
895 AccessAnalysis(const Loop *TheLoop, AAResults *AA, const LoopInfo *LI,
896 DominatorTree &DT, MemoryDepChecker::DepCandidates &DA,
897 PredicatedScalarEvolution &PSE,
898 SmallPtrSetImpl<MDNode *> &LoopAliasScopes)
899 : TheLoop(TheLoop), BAA(*AA), AST(BAA), LI(LI), DT(DT), DepCands(DA),
900 PSE(PSE), LoopAliasScopes(LoopAliasScopes) {
901 // We're analyzing dependences across loop iterations.
902 BAA.enableCrossIterationMode();
903 }
904
905 /// Register a load and whether it is only read from.
906 void addLoad(const MemoryLocation &Loc, Type *AccessTy, bool IsReadOnly) {
907 Value *Ptr = const_cast<Value *>(Loc.Ptr);
908 AST.add(Loc: adjustLoc(Loc));
909 Accesses[MemAccessInfo(Ptr, false)].insert(X: AccessTy);
910 if (IsReadOnly)
911 ReadOnlyPtr.insert(Ptr);
912 }
913
914 /// Register a store.
915 void addStore(const MemoryLocation &Loc, Type *AccessTy) {
916 Value *Ptr = const_cast<Value *>(Loc.Ptr);
917 AST.add(Loc: adjustLoc(Loc));
918 Accesses[MemAccessInfo(Ptr, true)].insert(X: AccessTy);
919 }
920
921 /// Check if we can emit a run-time no-alias check for \p Access.
922 ///
923 /// Returns true if we can emit a run-time no alias check for \p Access.
924 /// If we can check this access, this also adds it to a dependence set and
925 /// adds a run-time to check for it to \p RtCheck. If \p Assume is true,
926 /// we will attempt to use additional run-time checks in order to get
927 /// the bounds of the pointer.
928 bool createCheckForAccess(RuntimePointerChecking &RtCheck,
929 MemAccessInfo Access, Type *AccessTy,
930 const SymbolicStrideMap &Strides,
931 DenseMap<Value *, unsigned> &DepSetId,
932 Loop *TheLoop, unsigned &RunningDepId,
933 unsigned ASId, bool Assume);
934
935 /// Check whether we can check the pointers at runtime for
936 /// non-intersection.
937 ///
938 /// Returns true if we need no check or if we do and we can generate them
939 /// (i.e. the pointers have computable bounds). A return value of false means
940 /// we couldn't analyze and generate runtime checks for all pointers in the
941 /// loop, but if \p AllowPartial is set then we will have checks for those
942 /// pointers we could analyze. \p DepChecker is used to remove unknown
943 /// dependences from DepCands.
944 bool canCheckPtrAtRT(RuntimePointerChecking &RtCheck, Loop *TheLoop,
945 const SymbolicStrideMap &Strides,
946 Value *&UncomputablePtr, bool AllowPartial,
947 const MemoryDepChecker &DepChecker);
948
949 /// Goes over all memory accesses, checks whether a RT check is needed
950 /// and builds sets of dependent accesses.
951 void buildDependenceSets();
952
953 /// Initial processing of memory accesses determined that we need to
954 /// perform dependency checking.
955 ///
956 /// Note that this can later be cleared if we retry memcheck analysis without
957 /// dependency checking (i.e. ShouldRetryWithRuntimeChecks).
958 bool isDependencyCheckNeeded() const { return !CheckDeps.empty(); }
959
960 /// We decided that no dependence analysis would be used. Reset the state.
961 void resetDepChecks(MemoryDepChecker &DepChecker) {
962 CheckDeps.clear();
963 DepChecker.clearDependences();
964 }
965
966 ArrayRef<MemAccessInfo> getDependenciesToCheck() const { return CheckDeps; }
967
968private:
969 using PtrAccessMap = MapVector<MemAccessInfo, SmallSetVector<Type *, 1>>;
970
971 /// Adjust the MemoryLocation so that it represents accesses to this
972 /// location across all iterations, rather than a single one.
973 MemoryLocation adjustLoc(MemoryLocation Loc) const {
974 // The accessed location varies within the loop, but remains within the
975 // underlying object.
976 Loc.Size = LocationSize::beforeOrAfterPointer();
977 Loc.AATags.Scope = adjustAliasScopeList(ScopeList: Loc.AATags.Scope);
978 Loc.AATags.NoAlias = adjustAliasScopeList(ScopeList: Loc.AATags.NoAlias);
979 return Loc;
980 }
981
982 /// Drop alias scopes that are only valid within a single loop iteration.
983 MDNode *adjustAliasScopeList(MDNode *ScopeList) const {
984 if (!ScopeList)
985 return nullptr;
986
987 // For the sake of simplicity, drop the whole scope list if any scope is
988 // iteration-local.
989 if (any_of(Range: ScopeList->operands(), P: [&](Metadata *Scope) {
990 return LoopAliasScopes.contains(Ptr: cast<MDNode>(Val: Scope));
991 }))
992 return nullptr;
993
994 return ScopeList;
995 }
996
997 /// Map of all accesses. Values are the types used to access memory pointed to
998 /// by the pointer.
999 PtrAccessMap Accesses;
1000
1001 /// The loop being checked.
1002 const Loop *TheLoop;
1003
1004 /// List of accesses that need a further dependence check.
1005 SmallVector<MemAccessInfo, 8> CheckDeps;
1006
1007 /// Set of pointers that are read only.
1008 SmallPtrSet<Value*, 16> ReadOnlyPtr;
1009
1010 /// Batched alias analysis results.
1011 BatchAAResults BAA;
1012
1013 /// An alias set tracker to partition the access set by underlying object and
1014 //intrinsic property (such as TBAA metadata).
1015 AliasSetTracker AST;
1016
1017 /// The LoopInfo of the loop being checked.
1018 const LoopInfo *LI;
1019
1020 /// The dominator tree of the function.
1021 DominatorTree &DT;
1022
1023 /// Sets of potentially dependent accesses - members of one set share an
1024 /// underlying pointer. The set "CheckDeps" identfies which sets really need a
1025 /// dependence check.
1026 MemoryDepChecker::DepCandidates &DepCands;
1027
1028 /// Initial processing of memory accesses determined that we may need
1029 /// to add memchecks. Perform the analysis to determine the necessary checks.
1030 ///
1031 /// Note that, this is different from isDependencyCheckNeeded. When we retry
1032 /// memcheck analysis without dependency checking
1033 /// (i.e. ShouldRetryWithRuntimeChecks), isDependencyCheckNeeded is
1034 /// cleared while this remains set if we have potentially dependent accesses.
1035 bool IsRTCheckAnalysisNeeded = false;
1036
1037 /// The SCEV predicate containing all the SCEV-related assumptions.
1038 PredicatedScalarEvolution &PSE;
1039
1040 DenseMap<Value *, SmallVector<const Value *, 16>> UnderlyingObjects;
1041
1042 /// Alias scopes that are declared inside the loop, and as such not valid
1043 /// across iterations.
1044 SmallPtrSetImpl<MDNode *> &LoopAliasScopes;
1045};
1046
1047} // end anonymous namespace
1048
1049std::optional<int64_t>
1050llvm::getStrideFromAddRec(const SCEVAddRecExpr *AR, const Loop *Lp,
1051 Type *AccessTy, Value *Ptr,
1052 PredicatedScalarEvolution &PSE) {
1053 if (isa<ScalableVectorType>(Val: AccessTy)) {
1054 LLVM_DEBUG(dbgs() << "LAA: Bad stride - Scalable object: " << *AccessTy
1055 << "\n");
1056 return std::nullopt;
1057 }
1058
1059 // The access function must stride over the innermost loop.
1060 if (Lp != AR->getLoop()) {
1061 LLVM_DEBUG({
1062 dbgs() << "LAA: Bad stride - Not striding over innermost loop ";
1063 if (Ptr)
1064 dbgs() << *Ptr << " ";
1065
1066 dbgs() << "SCEV: " << *AR << "\n";
1067 });
1068 return std::nullopt;
1069 }
1070
1071 // Check the step is constant.
1072 const SCEV *Step = AR->getStepRecurrence(SE&: *PSE.getSE());
1073
1074 // Calculate the pointer stride and check if it is constant.
1075 const APInt *APStepVal;
1076 if (!match(S: Step, P: m_scev_APInt(C&: APStepVal))) {
1077 LLVM_DEBUG({
1078 dbgs() << "LAA: Bad stride - Not a constant strided ";
1079 if (Ptr)
1080 dbgs() << *Ptr << " ";
1081 dbgs() << "SCEV: " << *AR << "\n";
1082 });
1083 return std::nullopt;
1084 }
1085
1086 const auto &DL = Lp->getHeader()->getDataLayout();
1087 TypeSize AllocSize = DL.getTypeAllocSize(Ty: AccessTy);
1088 int64_t Size = AllocSize.getFixedValue();
1089
1090 // Huge step value - give up.
1091 std::optional<int64_t> StepVal = APStepVal->trySExtValue();
1092 if (!StepVal)
1093 return std::nullopt;
1094
1095 // Strided access.
1096 return *StepVal % Size ? std::nullopt : std::make_optional(t: *StepVal / Size);
1097}
1098
1099/// Check whether \p AR is a non-wrapping AddRec. If \p Ptr is not nullptr, use
1100/// information from the IR pointer value to determine no-wrap. If \p Predicates
1101/// is not nullptr add no-wrap assumptions if needed.
1102static bool
1103isNoWrap(PredicatedScalarEvolution &PSE, const SCEVAddRecExpr *AR, Value *Ptr,
1104 Type *AccessTy, const Loop *L, const DominatorTree &DT,
1105 std::optional<int64_t> Stride = std::nullopt,
1106 SmallVectorImpl<const SCEVPredicate *> *Predicates = nullptr) {
1107 // FIXME: This should probably only return true for NUW.
1108 if (any(Val: AR->getNoWrapFlags(Mask: SCEV::NoWrapMask)))
1109 return true;
1110
1111 if (Ptr && PSE.hasNoOverflow(V: Ptr, Flags: SCEVWrapPredicate::IncrementNUSW))
1112 return true;
1113
1114 // An nusw getelementptr that is an AddRec cannot wrap. If it would wrap,
1115 // the distance between the previously accessed location and the wrapped
1116 // location will be larger than half the pointer index type space. In that
1117 // case, the GEP would be poison and any memory access dependent on it would
1118 // be immediate UB when executed.
1119 if (auto *GEP = dyn_cast_if_present<GetElementPtrInst>(Val: Ptr);
1120 GEP && GEP->hasNoUnsignedSignedWrap()) {
1121 // For the above reasoning to apply, the pointer must be dereferenced in
1122 // every iteration.
1123 if (L->getHeader() == L->getLoopLatch() ||
1124 any_of(Range: GEP->users(), P: [L, &DT, GEP](User *U) {
1125 if (getLoadStorePointerOperand(V: U) != GEP)
1126 return false;
1127 BasicBlock *UserBB = cast<Instruction>(Val: U)->getParent();
1128 if (!L->contains(BB: UserBB))
1129 return false;
1130 return !LoopAccessInfo::blockNeedsPredication(BB: UserBB, TheLoop: L, DT: &DT);
1131 }))
1132 return true;
1133 }
1134
1135 if (!Stride)
1136 Stride = getStrideFromAddRec(AR, Lp: L, AccessTy, Ptr, PSE);
1137 if (Stride) {
1138 // If the null pointer is undefined, then a access sequence which would
1139 // otherwise access it can be assumed not to unsigned wrap. Note that this
1140 // assumes the object in memory is aligned to the natural alignment.
1141 unsigned AddrSpace = AR->getType()->getPointerAddressSpace();
1142 if (!NullPointerIsDefined(F: L->getHeader()->getParent(), AS: AddrSpace) &&
1143 (Stride == 1 || Stride == -1))
1144 return true;
1145 }
1146
1147 if (Ptr && Predicates) {
1148 ScalarEvolution &SE = *PSE.getSE();
1149 SCEVWrapPredicate::IncrementWrapFlags Flags = SCEVWrapPredicate::clearFlags(
1150 Flags: SCEVWrapPredicate::IncrementNUSW,
1151 OffFlags: SCEVWrapPredicate::getImpliedFlags(AR, SE));
1152 Predicates->push_back(Elt: SE.getWrapPredicate(AR, AddedFlags: Flags));
1153 LLVM_DEBUG(dbgs() << "LAA: Pointer may wrap:\n"
1154 << "LAA: Pointer: " << *Ptr << "\n"
1155 << "LAA: SCEV: " << *AR << "\n"
1156 << "LAA: Added an overflow assumption\n");
1157 return true;
1158 }
1159
1160 return false;
1161}
1162
1163static void visitPointers(Value *StartPtr, const Loop &InnermostLoop,
1164 function_ref<void(Value *)> AddPointer) {
1165 SmallPtrSet<Value *, 8> Visited;
1166 SmallVector<Value *> WorkList;
1167 WorkList.push_back(Elt: StartPtr);
1168
1169 while (!WorkList.empty()) {
1170 Value *Ptr = WorkList.pop_back_val();
1171 if (!Visited.insert(Ptr).second)
1172 continue;
1173 auto *PN = dyn_cast<PHINode>(Val: Ptr);
1174 // SCEV does not look through non-header PHIs inside the loop. Such phis
1175 // can be analyzed by adding separate accesses for each incoming pointer
1176 // value.
1177 if (PN && InnermostLoop.contains(BB: PN->getParent()) &&
1178 PN->getParent() != InnermostLoop.getHeader()) {
1179 llvm::append_range(C&: WorkList, R: PN->incoming_values());
1180 } else
1181 AddPointer(Ptr);
1182 }
1183}
1184
1185// Walk back through the IR for a pointer, looking for a select like the
1186// following:
1187//
1188// %offset = select i1 %cmp, i64 %a, i64 %b
1189// %addr = getelementptr double, double* %base, i64 %offset
1190// %ld = load double, double* %addr, align 8
1191//
1192// We won't be able to form a single SCEVAddRecExpr from this since the
1193// address for each loop iteration depends on %cmp. We could potentially
1194// produce multiple valid SCEVAddRecExprs, though, and check all of them for
1195// memory safety/aliasing if needed.
1196//
1197// If we encounter some IR we don't yet handle, or something obviously fine
1198// like a constant, then we just add the SCEV for that term to the list passed
1199// in by the caller. If we have a node that may potentially yield a valid
1200// SCEVAddRecExpr then we decompose it into parts and build the SCEV terms
1201// ourselves before adding to the list.
1202static void findForkedSCEVs(
1203 ScalarEvolution *SE, const Loop *L, Value *Ptr,
1204 SmallVectorImpl<PointerIntPair<const SCEV *, 1, bool>> &ScevList,
1205 unsigned Depth) {
1206 // If our Value is a SCEVAddRecExpr, loop invariant, not an instruction, or
1207 // we've exceeded our limit on recursion, just return whatever we have
1208 // regardless of whether it can be used for a forked pointer or not, along
1209 // with an indication of whether it might be a poison or undef value.
1210 const SCEV *Scev = SE->getSCEV(V: Ptr);
1211 if (isa<SCEVAddRecExpr>(Val: Scev) || L->isLoopInvariant(V: Ptr) ||
1212 !isa<Instruction>(Val: Ptr) || Depth == 0) {
1213 ScevList.emplace_back(Args&: Scev, Args: !isGuaranteedNotToBeUndefOrPoison(V: Ptr));
1214 return;
1215 }
1216
1217 Depth--;
1218
1219 auto UndefPoisonCheck = [](PointerIntPair<const SCEV *, 1, bool> S) {
1220 return get<1>(Pair: S);
1221 };
1222
1223 auto GetBinOpExpr = [&SE](unsigned Opcode, const SCEV *L,
1224 const SCEV *R) -> const SCEV * {
1225 switch (Opcode) {
1226 case Instruction::Add:
1227 return SE->getAddExpr(LHS: L, RHS: R);
1228 case Instruction::Sub:
1229 return SE->getMinusSCEV(LHS: L, RHS: R);
1230 default:
1231 llvm_unreachable("Unexpected binary operator when walking ForkedPtrs");
1232 }
1233 };
1234
1235 Instruction *I = cast<Instruction>(Val: Ptr);
1236 unsigned Opcode = I->getOpcode();
1237 switch (Opcode) {
1238 case Instruction::GetElementPtr: {
1239 auto *GEP = cast<GetElementPtrInst>(Val: I);
1240 Type *SourceTy = GEP->getSourceElementType();
1241 // We only handle base + single offset GEPs here for now.
1242 // Not dealing with preexisting gathers yet, so no vectors.
1243 if (I->getNumOperands() != 2 || SourceTy->isVectorTy()) {
1244 ScevList.emplace_back(Args&: Scev, Args: !isGuaranteedNotToBeUndefOrPoison(V: GEP));
1245 break;
1246 }
1247 SmallVector<PointerIntPair<const SCEV *, 1, bool>, 2> BaseScevs;
1248 SmallVector<PointerIntPair<const SCEV *, 1, bool>, 2> OffsetScevs;
1249 findForkedSCEVs(SE, L, Ptr: I->getOperand(i: 0), ScevList&: BaseScevs, Depth);
1250 findForkedSCEVs(SE, L, Ptr: I->getOperand(i: 1), ScevList&: OffsetScevs, Depth);
1251
1252 // See if we need to freeze our fork...
1253 bool NeedsFreeze = any_of(Range&: BaseScevs, P: UndefPoisonCheck) ||
1254 any_of(Range&: OffsetScevs, P: UndefPoisonCheck);
1255
1256 // Check that we only have a single fork, on either the base or the offset.
1257 // Copy the SCEV across for the one without a fork in order to generate
1258 // the full SCEV for both sides of the GEP.
1259 if (OffsetScevs.size() == 2 && BaseScevs.size() == 1)
1260 BaseScevs.push_back(Elt: BaseScevs[0]);
1261 else if (BaseScevs.size() == 2 && OffsetScevs.size() == 1)
1262 OffsetScevs.push_back(Elt: OffsetScevs[0]);
1263 else {
1264 ScevList.emplace_back(Args&: Scev, Args&: NeedsFreeze);
1265 break;
1266 }
1267
1268 Type *IntPtrTy = SE->getEffectiveSCEVType(Ty: GEP->getPointerOperandType());
1269
1270 // Find the size of the type being pointed to. We only have a single
1271 // index term (guarded above) so we don't need to index into arrays or
1272 // structures, just get the size of the scalar value.
1273 const SCEV *Size = SE->getSizeOfExpr(IntTy: IntPtrTy, AllocTy: SourceTy);
1274
1275 for (auto [B, O] : zip(t&: BaseScevs, u&: OffsetScevs)) {
1276 const SCEV *Base = get<0>(Pair: B);
1277 const SCEV *Offset = get<0>(Pair: O);
1278
1279 // Scale up the offsets by the size of the type, then add to the bases.
1280 const SCEV *Scaled =
1281 SE->getMulExpr(LHS: Size, RHS: SE->getTruncateOrSignExtend(V: Offset, Ty: IntPtrTy));
1282 ScevList.emplace_back(Args: SE->getAddExpr(LHS: Base, RHS: Scaled), Args&: NeedsFreeze);
1283 }
1284 break;
1285 }
1286 case Instruction::Select: {
1287 SmallVector<PointerIntPair<const SCEV *, 1, bool>, 2> ChildScevs;
1288 // A select means we've found a forked pointer, but we currently only
1289 // support a single select per pointer so if there's another behind this
1290 // then we just bail out and return the generic SCEV.
1291 findForkedSCEVs(SE, L, Ptr: I->getOperand(i: 1), ScevList&: ChildScevs, Depth);
1292 findForkedSCEVs(SE, L, Ptr: I->getOperand(i: 2), ScevList&: ChildScevs, Depth);
1293 if (ChildScevs.size() == 2)
1294 append_range(C&: ScevList, R&: ChildScevs);
1295 else
1296 ScevList.emplace_back(Args&: Scev, Args: !isGuaranteedNotToBeUndefOrPoison(V: Ptr));
1297 break;
1298 }
1299 case Instruction::PHI: {
1300 SmallVector<PointerIntPair<const SCEV *, 1, bool>, 2> ChildScevs;
1301 // A phi means we've found a forked pointer, but we currently only
1302 // support a single phi per pointer so if there's another behind this
1303 // then we just bail out and return the generic SCEV.
1304 if (I->getNumOperands() == 2) {
1305 findForkedSCEVs(SE, L, Ptr: I->getOperand(i: 0), ScevList&: ChildScevs, Depth);
1306 findForkedSCEVs(SE, L, Ptr: I->getOperand(i: 1), ScevList&: ChildScevs, Depth);
1307 }
1308 if (ChildScevs.size() == 2)
1309 append_range(C&: ScevList, R&: ChildScevs);
1310 else
1311 ScevList.emplace_back(Args&: Scev, Args: !isGuaranteedNotToBeUndefOrPoison(V: Ptr));
1312 break;
1313 }
1314 case Instruction::Add:
1315 case Instruction::Sub: {
1316 SmallVector<PointerIntPair<const SCEV *, 1, bool>> LScevs;
1317 SmallVector<PointerIntPair<const SCEV *, 1, bool>> RScevs;
1318 findForkedSCEVs(SE, L, Ptr: I->getOperand(i: 0), ScevList&: LScevs, Depth);
1319 findForkedSCEVs(SE, L, Ptr: I->getOperand(i: 1), ScevList&: RScevs, Depth);
1320
1321 // See if we need to freeze our fork...
1322 bool NeedsFreeze =
1323 any_of(Range&: LScevs, P: UndefPoisonCheck) || any_of(Range&: RScevs, P: UndefPoisonCheck);
1324
1325 // Check that we only have a single fork, on either the left or right side.
1326 // Copy the SCEV across for the one without a fork in order to generate
1327 // the full SCEV for both sides of the BinOp.
1328 if (LScevs.size() == 2 && RScevs.size() == 1)
1329 RScevs.push_back(Elt: RScevs[0]);
1330 else if (RScevs.size() == 2 && LScevs.size() == 1)
1331 LScevs.push_back(Elt: LScevs[0]);
1332 else {
1333 ScevList.emplace_back(Args&: Scev, Args&: NeedsFreeze);
1334 break;
1335 }
1336
1337 for (auto [L, R] : zip(t&: LScevs, u&: RScevs))
1338 ScevList.emplace_back(Args: GetBinOpExpr(Opcode, get<0>(Pair: L), get<0>(Pair: R)),
1339 Args&: NeedsFreeze);
1340 break;
1341 }
1342 default:
1343 // Just return the current SCEV if we haven't handled the instruction yet.
1344 LLVM_DEBUG(dbgs() << "ForkedPtr unhandled instruction: " << *I << "\n");
1345 ScevList.emplace_back(Args&: Scev, Args: !isGuaranteedNotToBeUndefOrPoison(V: Ptr));
1346 break;
1347 }
1348}
1349
1350bool AccessAnalysis::createCheckForAccess(RuntimePointerChecking &RtCheck,
1351 MemAccessInfo Access, Type *AccessTy,
1352 const SymbolicStrideMap &StridesMap,
1353 DenseMap<Value *, unsigned> &DepSetId,
1354 Loop *TheLoop, unsigned &RunningDepId,
1355 unsigned ASId, bool Assume) {
1356 Value *Ptr = Access.getPointer();
1357 ScalarEvolution *SE = PSE.getSE();
1358 const DataLayout &DL = TheLoop->getHeader()->getDataLayout();
1359 assert(SE->isSCEVable(Ptr->getType()) && "Value is not SCEVable!");
1360
1361 SmallVector<PointerIntPair<const SCEV *, 1, bool>> RTCheckPtrs;
1362 findForkedSCEVs(SE, L: TheLoop, Ptr, ScevList&: RTCheckPtrs, Depth: MaxForkedSCEVDepth);
1363 assert(!RTCheckPtrs.empty() &&
1364 "Must have some runtime-check pointer candidates");
1365
1366 // RTCheckPtrs must have size 2 if there are forked pointers. Otherwise, there
1367 // are no forked pointers; replaceSymbolicStridesSCEV in this case.
1368 auto IsLoopInvariantOrAR =
1369 [&SE, &TheLoop](const PointerIntPair<const SCEV *, 1, bool> &P) {
1370 return SE->isLoopInvariant(S: P.getPointer(), L: TheLoop) ||
1371 isa<SCEVAddRecExpr>(Val: P.getPointer());
1372 };
1373 if (RTCheckPtrs.size() == 2 && all_of(Range&: RTCheckPtrs, P: IsLoopInvariantOrAR)) {
1374 LLVM_DEBUG(dbgs() << "LAA: Found forked pointer: " << *Ptr << "\n";
1375 for (const auto &[Idx, Q] : enumerate(RTCheckPtrs)) dbgs()
1376 << "\t(" << Idx << ") " << *Q.getPointer() << "\n");
1377 } else {
1378 RTCheckPtrs = {{replaceSymbolicStrideSCEV(PSE, PtrToStride: StridesMap, Ptr), false}};
1379 }
1380
1381 /// Check whether all pointers can participate in a runtime bounds check. They
1382 /// must either be invariant or non-wrapping affine AddRecs.
1383 SmallVector<const SCEVPredicate *> Predicates;
1384 for (auto &P : RTCheckPtrs) {
1385 // The bounds for loop-invariant pointer is trivial.
1386 if (SE->isLoopInvariant(S: P.getPointer(), L: TheLoop))
1387 continue;
1388
1389 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Val: P.getPointer());
1390 if (!AR && Assume)
1391 AR = PSE.getAsAddRec(V: Ptr, WrapPredsAdded: &Predicates);
1392 if (!AR || !AR->isAffine()) {
1393 // Check if bounds for non-affine monotonic expressions can be formed.
1394 const SCEV *EltSizeSCEV = SE->getStoreSizeOfExpr(
1395 IntTy: DL.getIndexType(PtrTy: P.getPointer()->getType()), StoreTy: AccessTy);
1396 if (!Assume ||
1397 !getNonAffineMonotonicBounds(Lp: TheLoop, PtrExpr: P.getPointer(), EltSizeSCEV, SE)
1398 .first)
1399 return false;
1400 continue;
1401 }
1402
1403 // If there's only one option for Ptr, commit the predicates collected by
1404 // getAsAddRec and look Ptr up again afterwards: the lookup below reads the
1405 // assumptions back from PSE, so they need to be committed first.
1406 if (RTCheckPtrs.size() == 1) {
1407 PSE.addPredicates(Preds: Predicates);
1408 Predicates.clear();
1409 if (auto *StrideAR = dyn_cast<SCEVAddRecExpr>(
1410 Val: replaceSymbolicStrideSCEV(PSE, PtrToStride: StridesMap, Ptr)))
1411 AR = StrideAR;
1412 P.setPointer(AR);
1413 }
1414
1415 if (!isNoWrap(PSE, AR, Ptr: RTCheckPtrs.size() == 1 ? Ptr : nullptr, AccessTy,
1416 L: TheLoop, DT, /*Stride=*/std::nullopt,
1417 Predicates: Assume ? &Predicates : nullptr))
1418 return false;
1419 }
1420 PSE.addPredicates(Preds: Predicates);
1421
1422 // Remember the number of pointers inserted so far, to remove the pointers of
1423 // this access again if the bounds of any of them cannot be computed, to avoid
1424 // partial inserts.
1425 unsigned NumPointers = RtCheck.Pointers.size();
1426 for (const auto &[PtrExpr, NeedsFreeze] : RTCheckPtrs) {
1427 // The id of the dependence set.
1428 unsigned DepId;
1429
1430 if (DepCands.contains(V: Access)) {
1431 Value *Leader = DepCands.getLeaderValue(V: Access).getPointer();
1432 unsigned &LeaderId = DepSetId[Leader];
1433 if (!LeaderId)
1434 LeaderId = RunningDepId++;
1435 DepId = LeaderId;
1436 } else
1437 // Each access has its own dependence set.
1438 DepId = RunningDepId++;
1439
1440 bool IsWrite = Access.getInt();
1441 if (!RtCheck.insert(Lp: TheLoop, Ptr, PtrExpr, AccessTy, WritePtr: IsWrite, DepSetId: DepId, ASId,
1442 PSE, NeedsFreeze)) {
1443 RtCheck.Pointers.truncate(N: NumPointers);
1444 return false;
1445 }
1446 LLVM_DEBUG(dbgs() << "LAA: Found a runtime check ptr:" << *Ptr << '\n');
1447 }
1448
1449 return true;
1450}
1451
1452bool AccessAnalysis::canCheckPtrAtRT(RuntimePointerChecking &RtCheck,
1453 Loop *TheLoop,
1454 const SymbolicStrideMap &StridesMap,
1455 Value *&UncomputablePtr, bool AllowPartial,
1456 const MemoryDepChecker &DepChecker) {
1457 // Find pointers with computable bounds. We are going to use this information
1458 // to place a runtime bound check.
1459 bool CanDoRT = true;
1460
1461 bool MayNeedRTCheck = false;
1462 if (!IsRTCheckAnalysisNeeded) return true;
1463
1464 if (auto *Deps = DepChecker.getDependences()) {
1465 // If there are unknown dependences, this means runtime checks are needed to
1466 // ensure there's no overlap between accesses to the same underlying object.
1467 // Remove the equivalence classes containing both source and destination
1468 // accesses from DepCands. This ensures runtime checks will be generated
1469 // between those accesses and prevents them from being grouped together.
1470 for (const auto &Dep : *Deps) {
1471 if (Dep.Type != MemoryDepChecker::Dependence::Unknown) {
1472 assert(MemoryDepChecker::Dependence::isSafeForVectorization(Dep.Type) ==
1473 MemoryDepChecker::VectorizationSafetyStatus::Safe &&
1474 "Should only skip safe dependences");
1475 continue;
1476 }
1477 Instruction *Src = Dep.getSource(DepChecker);
1478 Instruction *Dst = Dep.getDestination(DepChecker);
1479 DepCands.eraseClass(V: {getPointerOperand(V: Src), Src->mayWriteToMemory()});
1480 DepCands.eraseClass(V: {getPointerOperand(V: Dst), Dst->mayWriteToMemory()});
1481 }
1482 } else {
1483 CheckDeps.clear();
1484 DepCands = {};
1485 }
1486
1487 // We assign a consecutive id to access from different alias sets.
1488 // Accesses between different groups doesn't need to be checked.
1489 unsigned ASId = 0;
1490 for (const auto &AS : AST) {
1491 int NumReadPtrChecks = 0;
1492 int NumWritePtrChecks = 0;
1493 bool CanDoAliasSetRT = true;
1494 ++ASId;
1495 auto ASPointers = AS.getPointers();
1496
1497 // We assign consecutive id to access from different dependence sets.
1498 // Accesses within the same set don't need a runtime check.
1499 unsigned RunningDepId = 1;
1500 DenseMap<Value *, unsigned> DepSetId;
1501
1502 SmallVector<std::pair<MemAccessInfo, Type *>, 4> Retries;
1503
1504 // First, count how many write and read accesses are in the alias set. Also
1505 // collect MemAccessInfos for later.
1506 SmallVector<MemAccessInfo, 4> AccessInfos;
1507 for (const Value *ConstPtr : ASPointers) {
1508 Value *Ptr = const_cast<Value *>(ConstPtr);
1509 bool IsWrite = Accesses.contains(Key: MemAccessInfo(Ptr, true));
1510 if (IsWrite)
1511 ++NumWritePtrChecks;
1512 else
1513 ++NumReadPtrChecks;
1514 AccessInfos.emplace_back(Args&: Ptr, Args&: IsWrite);
1515 }
1516
1517 // We do not need runtime checks for this alias set, if there are no writes
1518 // or a single write and no reads.
1519 if (NumWritePtrChecks == 0 ||
1520 (NumWritePtrChecks == 1 && NumReadPtrChecks == 0)) {
1521 assert((ASPointers.size() <= 1 ||
1522 all_of(ASPointers,
1523 [this](const Value *Ptr) {
1524 MemAccessInfo AccessWrite(const_cast<Value *>(Ptr),
1525 true);
1526 return !DepCands.contains(AccessWrite);
1527 })) &&
1528 "Can only skip updating CanDoRT below, if all entries in AS "
1529 "are reads or there is at most 1 entry");
1530 continue;
1531 }
1532
1533 for (auto &Access : AccessInfos) {
1534 for (const auto &AccessTy : Accesses[Access]) {
1535 if (!createCheckForAccess(RtCheck, Access, AccessTy, StridesMap,
1536 DepSetId, TheLoop, RunningDepId, ASId,
1537 Assume: false)) {
1538 LLVM_DEBUG(dbgs() << "LAA: Can't find bounds for ptr:"
1539 << *Access.getPointer() << '\n');
1540 Retries.emplace_back(Args&: Access, Args: AccessTy);
1541 CanDoAliasSetRT = false;
1542 }
1543 }
1544 }
1545
1546 // Note that this function computes CanDoRT and MayNeedRTCheck
1547 // independently. For example CanDoRT=false, MayNeedRTCheck=false means that
1548 // we have a pointer for which we couldn't find the bounds but we don't
1549 // actually need to emit any checks so it does not matter.
1550 //
1551 // We need runtime checks for this alias set, if there are at least 2
1552 // dependence sets (in which case RunningDepId > 2) or if we need to re-try
1553 // any bound checks (because in that case the number of dependence sets is
1554 // incomplete).
1555 bool NeedsAliasSetRTCheck = RunningDepId > 2 || !Retries.empty();
1556
1557 // We need to perform run-time alias checks, but some pointers had bounds
1558 // that couldn't be checked.
1559 if (NeedsAliasSetRTCheck && !CanDoAliasSetRT) {
1560 // Reset the CanDoSetRt flag and retry all accesses that have failed.
1561 // We know that we need these checks, so we can now be more aggressive
1562 // and add further checks if required (overflow checks).
1563 CanDoAliasSetRT = true;
1564 for (const auto &[Access, AccessTy] : Retries) {
1565 if (!createCheckForAccess(RtCheck, Access, AccessTy, StridesMap,
1566 DepSetId, TheLoop, RunningDepId, ASId,
1567 /*Assume=*/true)) {
1568 CanDoAliasSetRT = false;
1569 UncomputablePtr = Access.getPointer();
1570 if (!AllowPartial)
1571 break;
1572 }
1573 }
1574 }
1575
1576 CanDoRT &= CanDoAliasSetRT;
1577 MayNeedRTCheck |= NeedsAliasSetRTCheck;
1578 ++ASId;
1579 }
1580
1581 // If the pointers that we would use for the bounds comparison have different
1582 // address spaces, assume the values aren't directly comparable, so we can't
1583 // use them for the runtime check. We also have to assume they could
1584 // overlap. In the future there should be metadata for whether address spaces
1585 // are disjoint.
1586 unsigned NumPointers = RtCheck.Pointers.size();
1587 for (unsigned i = 0; i < NumPointers; ++i) {
1588 for (unsigned j = i + 1; j < NumPointers; ++j) {
1589 // Only need to check pointers between two different dependency sets.
1590 if (RtCheck.Pointers[i].DependencySetId ==
1591 RtCheck.Pointers[j].DependencySetId)
1592 continue;
1593 // Only need to check pointers in the same alias set.
1594 if (RtCheck.Pointers[i].AliasSetId != RtCheck.Pointers[j].AliasSetId)
1595 continue;
1596
1597 Value *PtrI = RtCheck.Pointers[i].PointerValue;
1598 Value *PtrJ = RtCheck.Pointers[j].PointerValue;
1599
1600 unsigned ASi = PtrI->getType()->getPointerAddressSpace();
1601 unsigned ASj = PtrJ->getType()->getPointerAddressSpace();
1602 if (ASi != ASj) {
1603 LLVM_DEBUG(
1604 dbgs() << "LAA: Runtime check would require comparison between"
1605 " different address spaces\n");
1606 return false;
1607 }
1608 }
1609 }
1610
1611 if (MayNeedRTCheck && (CanDoRT || AllowPartial))
1612 RtCheck.generateChecks(DepCands);
1613
1614 LLVM_DEBUG(dbgs() << "LAA: We need to do " << RtCheck.getNumberOfChecks()
1615 << " pointer comparisons.\n");
1616
1617 // If we can do run-time checks, but there are no checks, no runtime checks
1618 // are needed. This can happen when all pointers point to the same underlying
1619 // object for example.
1620 RtCheck.Need = CanDoRT ? RtCheck.getNumberOfChecks() != 0 : MayNeedRTCheck;
1621
1622 bool CanDoRTIfNeeded = !RtCheck.Need || CanDoRT;
1623 assert(CanDoRTIfNeeded == (CanDoRT || !MayNeedRTCheck) &&
1624 "CanDoRTIfNeeded depends on RtCheck.Need");
1625 if (!CanDoRTIfNeeded && !AllowPartial)
1626 RtCheck.reset();
1627 return CanDoRTIfNeeded;
1628}
1629
1630void AccessAnalysis::buildDependenceSets() {
1631 // We process the set twice: first we process read-write pointers, last we
1632 // process read-only pointers. This allows us to skip dependence tests for
1633 // read-only pointers.
1634
1635 LLVM_DEBUG(dbgs() << "LAA: Processing memory accesses...\n");
1636 LLVM_DEBUG(dbgs() << " AST: "; AST.dump());
1637 LLVM_DEBUG(dbgs() << "LAA: Accesses(" << Accesses.size() << "):\n");
1638 LLVM_DEBUG({
1639 for (const auto &[A, _] : Accesses)
1640 dbgs() << "\t" << *A.getPointer() << " ("
1641 << (A.getInt()
1642 ? "write"
1643 : (ReadOnlyPtr.contains(A.getPointer()) ? "read-only"
1644 : "read"))
1645 << ")\n";
1646 });
1647
1648 // The AliasSetTracker has nicely partitioned our pointers by metadata
1649 // compatibility and potential for underlying-object overlap. As a result, we
1650 // only need to check for potential pointer dependencies within each alias
1651 // set.
1652 for (const auto &AS : AST) {
1653 bool AliasSetHasWrite = false;
1654
1655 // Map of (pointer to underlying objects, accessed address space) to last
1656 // access encountered.
1657 using UnderlyingObjToAccessMap =
1658 DenseMap<std::pair<const Value *, unsigned>, MemAccessInfo>;
1659 UnderlyingObjToAccessMap ObjToLastAccess;
1660
1661 // Set of access to check after all writes have been processed.
1662 PtrAccessMap DeferredAccesses;
1663
1664 // Iterate over each alias set twice, once to process read/write pointers,
1665 // and then to process read-only pointers.
1666
1667 auto ProcessAccesses = [&](bool UseDeferred) {
1668 PtrAccessMap &S = UseDeferred ? DeferredAccesses : Accesses;
1669
1670 // Note that both the alias-set tracker and the alias sets themselves used
1671 // ordered collections internally and so the iteration order here is
1672 // deterministic.
1673 for (const Value *ConstPtr : AS.getPointers()) {
1674 Value *Ptr = const_cast<Value *>(ConstPtr);
1675
1676 // For a single memory access in AliasSetTracker, Accesses may contain
1677 // both read and write, and they both need to be handled for CheckDeps.
1678 for (auto [AccessPtr, IsWrite] : S.keys()) {
1679 if (AccessPtr != Ptr)
1680 continue;
1681
1682 // If we're using the deferred access set, then it contains only
1683 // reads.
1684 bool IsReadOnlyPtr = ReadOnlyPtr.contains(Ptr) && !IsWrite;
1685 if (UseDeferred && !IsReadOnlyPtr)
1686 continue;
1687 // Otherwise, the pointer must be in the PtrAccessSet, either as a
1688 // read or a write.
1689 assert(((IsReadOnlyPtr && UseDeferred) || IsWrite ||
1690 S.contains(MemAccessInfo(Ptr, false))) &&
1691 "Alias-set pointer not in the access set?");
1692
1693 MemAccessInfo Access(Ptr, IsWrite);
1694 DepCands.insert(Data: Access);
1695
1696 // Memorize read-only pointers for later processing and skip them in
1697 // the first round (they need to be checked after we have seen all
1698 // write pointers). Note: we also mark pointer that are not
1699 // consecutive as "read-only" pointers (so that we check
1700 // "a[b[i]] +="). Hence, we need the second check for "!IsWrite".
1701 if (!UseDeferred && IsReadOnlyPtr) {
1702 // We only use the pointer keys, the types vector values don't
1703 // matter.
1704 DeferredAccesses.insert(KV: {Access, {}});
1705 continue;
1706 }
1707
1708 // If this is a write - check other reads and writes for conflicts. If
1709 // this is a read only check other writes for conflicts (but only if
1710 // there is no other write to the ptr - this is an optimization to
1711 // catch "a[i] = a[i] + " without having to do a dependence check).
1712 if ((IsWrite || IsReadOnlyPtr) && AliasSetHasWrite) {
1713 CheckDeps.push_back(Elt: Access);
1714 IsRTCheckAnalysisNeeded = true;
1715 }
1716
1717 if (IsWrite)
1718 AliasSetHasWrite = true;
1719
1720 // Create sets of pointers connected by a shared alias set and
1721 // underlying object.
1722 SmallVector<const Value *, 16> &UOs = UnderlyingObjects[Ptr];
1723 UOs = {};
1724 ::getUnderlyingObjects(V: Ptr, Objects&: UOs, LI);
1725 LLVM_DEBUG(dbgs()
1726 << "Underlying objects for pointer " << *Ptr << "\n");
1727 for (const Value *UnderlyingObj : UOs) {
1728 // nullptr never alias, don't join sets for pointer that have "null"
1729 // in their UnderlyingObjects list.
1730 if (isa<ConstantPointerNull>(Val: UnderlyingObj) &&
1731 !NullPointerIsDefined(
1732 F: TheLoop->getHeader()->getParent(),
1733 AS: UnderlyingObj->getType()->getPointerAddressSpace()))
1734 continue;
1735
1736 auto [It, Inserted] = ObjToLastAccess.try_emplace(
1737 Key: {UnderlyingObj,
1738 cast<PointerType>(Val: Ptr->getType())->getAddressSpace()},
1739 Args&: Access);
1740 if (!Inserted) {
1741 DepCands.unionSets(V1: Access, V2: It->second);
1742 It->second = Access;
1743 }
1744
1745 LLVM_DEBUG(dbgs() << " " << *UnderlyingObj << "\n");
1746 }
1747 }
1748 }
1749 };
1750
1751 ProcessAccesses(false);
1752 ProcessAccesses(true);
1753 }
1754}
1755
1756/// Check whether the access through \p Ptr has a constant stride.
1757std::optional<int64_t>
1758llvm::getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr,
1759 const Loop *Lp, const DominatorTree &DT,
1760 const SymbolicStrideMap &StridesMap, bool ShouldCheckWrap,
1761 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
1762 const SCEV *PtrScev = replaceSymbolicStrideSCEV(PSE, PtrToStride: StridesMap, Ptr);
1763 if (PSE.getSE()->isLoopInvariant(S: PtrScev, L: Lp))
1764 return 0;
1765
1766 assert(Ptr->getType()->isPointerTy() && "Unexpected non-ptr");
1767
1768 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Val: PtrScev);
1769 if (Predicates && !AR) {
1770 AR = PSE.getSE()->convertSCEVToAddRecWithPredicates(S: PtrScev, L: Lp,
1771 Preds&: *Predicates);
1772 }
1773
1774 if (!AR) {
1775 LLVM_DEBUG(dbgs() << "LAA: Bad stride - Not an AddRecExpr pointer " << *Ptr
1776 << " SCEV: " << *PtrScev << "\n");
1777 return std::nullopt;
1778 }
1779
1780 std::optional<int64_t> Stride =
1781 getStrideFromAddRec(AR, Lp, AccessTy, Ptr, PSE);
1782 if (!ShouldCheckWrap || !Stride)
1783 return Stride;
1784
1785 if (isNoWrap(PSE, AR, Ptr, AccessTy, L: Lp, DT, Stride, Predicates))
1786 return Stride;
1787
1788 LLVM_DEBUG(
1789 dbgs() << "LAA: Bad stride - Pointer may wrap in the address space "
1790 << *Ptr << " SCEV: " << *AR << "\n");
1791 return std::nullopt;
1792}
1793
1794/// Check whether the access through \p Ptr has a constant stride.
1795std::optional<int64_t> llvm::getPtrStride(PredicatedScalarEvolution &PSE,
1796 Type *AccessTy, Value *Ptr,
1797 const Loop *Lp,
1798 const DominatorTree &DT,
1799 const SymbolicStrideMap &StridesMap,
1800 bool Assume, bool ShouldCheckWrap) {
1801 SmallVector<const SCEVPredicate *> Predicates;
1802 std::optional<int64_t> Stride =
1803 getPtrStride(PSE, AccessTy, Ptr, Lp, DT, StridesMap, ShouldCheckWrap,
1804 Predicates: Assume ? &Predicates : nullptr);
1805 PSE.addPredicates(Preds: Predicates);
1806 return Stride;
1807}
1808
1809std::optional<int64_t> llvm::getPointersDiff(Type *ElemTyA, Value *PtrA,
1810 Type *ElemTyB, Value *PtrB,
1811 const DataLayout &DL,
1812 ScalarEvolution &SE,
1813 bool StrictCheck, bool CheckType) {
1814 assert(PtrA && PtrB && "Expected non-nullptr pointers.");
1815
1816 // Make sure that A and B are different pointers.
1817 if (PtrA == PtrB)
1818 return 0;
1819
1820 // Make sure that the element types are the same if required.
1821 if (CheckType && ElemTyA != ElemTyB)
1822 return std::nullopt;
1823
1824 unsigned ASA = PtrA->getType()->getPointerAddressSpace();
1825 unsigned ASB = PtrB->getType()->getPointerAddressSpace();
1826
1827 // Check that the address spaces match.
1828 if (ASA != ASB)
1829 return std::nullopt;
1830 unsigned IdxWidth = DL.getIndexSizeInBits(AS: ASA);
1831
1832 APInt OffsetA(IdxWidth, 0), OffsetB(IdxWidth, 0);
1833 const Value *PtrA1 = PtrA->stripAndAccumulateConstantOffsets(
1834 DL, Offset&: OffsetA, /*AllowNonInbounds=*/true);
1835 const Value *PtrB1 = PtrB->stripAndAccumulateConstantOffsets(
1836 DL, Offset&: OffsetB, /*AllowNonInbounds=*/true);
1837
1838 std::optional<int64_t> Val;
1839 if (PtrA1 == PtrB1) {
1840 // Retrieve the address space again as pointer stripping now tracks through
1841 // `addrspacecast`.
1842 ASA = cast<PointerType>(Val: PtrA1->getType())->getAddressSpace();
1843 ASB = cast<PointerType>(Val: PtrB1->getType())->getAddressSpace();
1844 // Check that the address spaces match and that the pointers are valid.
1845 if (ASA != ASB)
1846 return std::nullopt;
1847
1848 IdxWidth = DL.getIndexSizeInBits(AS: ASA);
1849 OffsetA = OffsetA.sextOrTrunc(width: IdxWidth);
1850 OffsetB = OffsetB.sextOrTrunc(width: IdxWidth);
1851
1852 OffsetB -= OffsetA;
1853 Val = OffsetB.trySExtValue();
1854 } else {
1855 // Otherwise compute the distance with SCEV between the base pointers.
1856 const SCEV *PtrSCEVA = SE.getSCEV(V: PtrA);
1857 const SCEV *PtrSCEVB = SE.getSCEV(V: PtrB);
1858 std::optional<APInt> Diff =
1859 SE.computeConstantDifference(LHS: PtrSCEVB, RHS: PtrSCEVA);
1860 if (!Diff)
1861 return std::nullopt;
1862 Val = Diff->trySExtValue();
1863 }
1864
1865 if (!Val)
1866 return std::nullopt;
1867
1868 int64_t Size = DL.getTypeStoreSize(Ty: ElemTyA);
1869 int64_t Dist = *Val / Size;
1870
1871 // Ensure that the calculated distance matches the type-based one after all
1872 // the bitcasts removal in the provided pointers.
1873 if (!StrictCheck || Dist * Size == Val)
1874 return Dist;
1875 return std::nullopt;
1876}
1877
1878bool llvm::sortPtrAccesses(ArrayRef<Value *> VL, Type *ElemTy,
1879 const DataLayout &DL, ScalarEvolution &SE,
1880 SmallVectorImpl<unsigned> &SortedIndices) {
1881 assert(llvm::all_of(
1882 VL, [](const Value *V) { return V->getType()->isPointerTy(); }) &&
1883 "Expected list of pointer operands.");
1884 // Walk over the pointers, and map each of them to an offset relative to
1885 // first pointer in the array.
1886 Value *Ptr0 = VL[0];
1887
1888 using DistOrdPair = std::pair<int64_t, unsigned>;
1889 auto Compare = llvm::less_first();
1890 std::set<DistOrdPair, decltype(Compare)> Offsets(Compare);
1891 Offsets.emplace(args: 0, args: 0);
1892 bool IsConsecutive = true;
1893 for (auto [Idx, Ptr] : drop_begin(RangeOrContainer: enumerate(First&: VL))) {
1894 std::optional<int64_t> Diff =
1895 getPointersDiff(ElemTyA: ElemTy, PtrA: Ptr0, ElemTyB: ElemTy, PtrB: Ptr, DL, SE,
1896 /*StrictCheck=*/true);
1897 if (!Diff)
1898 return false;
1899
1900 // Check if the pointer with the same offset is found.
1901 int64_t Offset = *Diff;
1902 auto [It, IsInserted] = Offsets.emplace(args&: Offset, args&: Idx);
1903 if (!IsInserted)
1904 return false;
1905 // Consecutive order if the inserted element is the last one.
1906 IsConsecutive &= std::next(x: It) == Offsets.end();
1907 }
1908 SortedIndices.clear();
1909 if (!IsConsecutive) {
1910 // Fill SortedIndices array only if it is non-consecutive.
1911 SortedIndices.resize(N: VL.size());
1912 for (auto [Idx, Off] : enumerate(First&: Offsets))
1913 SortedIndices[Idx] = Off.second;
1914 }
1915 return true;
1916}
1917
1918/// Returns true if the memory operations \p A and \p B are consecutive.
1919bool llvm::isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL,
1920 ScalarEvolution &SE, bool CheckType) {
1921 Value *PtrA = getLoadStorePointerOperand(V: A);
1922 Value *PtrB = getLoadStorePointerOperand(V: B);
1923 if (!PtrA || !PtrB)
1924 return false;
1925 Type *ElemTyA = getLoadStoreType(I: A);
1926 Type *ElemTyB = getLoadStoreType(I: B);
1927 std::optional<int64_t> Diff =
1928 getPointersDiff(ElemTyA, PtrA, ElemTyB, PtrB, DL, SE,
1929 /*StrictCheck=*/true, CheckType);
1930 return Diff == 1;
1931}
1932
1933void MemoryDepChecker::addAccess(StoreInst *SI) {
1934 visitPointers(StartPtr: SI->getPointerOperand(), InnermostLoop: *InnermostLoop,
1935 AddPointer: [this, SI](Value *Ptr) {
1936 Accesses[MemAccessInfo(Ptr, true)].push_back(x: AccessIdx);
1937 InstMap.push_back(Elt: SI);
1938 ++AccessIdx;
1939 });
1940}
1941
1942void MemoryDepChecker::addAccess(LoadInst *LI) {
1943 visitPointers(StartPtr: LI->getPointerOperand(), InnermostLoop: *InnermostLoop,
1944 AddPointer: [this, LI](Value *Ptr) {
1945 Accesses[MemAccessInfo(Ptr, false)].push_back(x: AccessIdx);
1946 InstMap.push_back(Elt: LI);
1947 ++AccessIdx;
1948 });
1949}
1950
1951MemoryDepChecker::VectorizationSafetyStatus
1952MemoryDepChecker::Dependence::isSafeForVectorization(DepType Type) {
1953 switch (Type) {
1954 case NoDep:
1955 case Forward:
1956 case BackwardVectorizable:
1957 return VectorizationSafetyStatus::Safe;
1958
1959 case Unknown:
1960 return VectorizationSafetyStatus::PossiblySafeWithRtChecks;
1961 case ForwardButPreventsForwarding:
1962 case Backward:
1963 case BackwardVectorizableButPreventsForwarding:
1964 case IndirectUnsafe:
1965 case InvariantUnsafe:
1966 return VectorizationSafetyStatus::Unsafe;
1967 }
1968 llvm_unreachable("unexpected DepType!");
1969}
1970
1971bool MemoryDepChecker::Dependence::isBackward() const {
1972 switch (Type) {
1973 case NoDep:
1974 case Forward:
1975 case ForwardButPreventsForwarding:
1976 case Unknown:
1977 case IndirectUnsafe:
1978 case InvariantUnsafe:
1979 return false;
1980
1981 case BackwardVectorizable:
1982 case Backward:
1983 case BackwardVectorizableButPreventsForwarding:
1984 return true;
1985 }
1986 llvm_unreachable("unexpected DepType!");
1987}
1988
1989bool MemoryDepChecker::Dependence::isPossiblyBackward() const {
1990 return isBackward() || Type == Unknown || Type == IndirectUnsafe ||
1991 Type == InvariantUnsafe;
1992}
1993
1994bool MemoryDepChecker::Dependence::isForward() const {
1995 switch (Type) {
1996 case Forward:
1997 case ForwardButPreventsForwarding:
1998 return true;
1999
2000 case NoDep:
2001 case Unknown:
2002 case BackwardVectorizable:
2003 case Backward:
2004 case BackwardVectorizableButPreventsForwarding:
2005 case IndirectUnsafe:
2006 case InvariantUnsafe:
2007 return false;
2008 }
2009 llvm_unreachable("unexpected DepType!");
2010}
2011
2012bool MemoryDepChecker::couldPreventStoreLoadForward(uint64_t Distance,
2013 uint64_t TypeByteSize,
2014 unsigned CommonStride) {
2015 // If loads occur at a distance that is not a multiple of a feasible vector
2016 // factor store-load forwarding does not take place.
2017 // Positive dependences might cause troubles because vectorizing them might
2018 // prevent store-load forwarding making vectorized code run a lot slower.
2019 // a[i] = a[i-3] ^ a[i-8];
2020 // The stores to a[i:i+1] don't align with the stores to a[i-3:i-2] and
2021 // hence on your typical architecture store-load forwarding does not take
2022 // place. Vectorizing in such cases does not make sense.
2023 // Store-load forwarding distance.
2024
2025 // Maximum vector factor.
2026 uint64_t MaxVFWithoutSLForwardIssuesPowerOf2 =
2027 std::min(a: VectorizerParams::MaxVectorWidth * TypeByteSize,
2028 b: MaxStoreLoadForwardSafeDistanceInBits);
2029
2030 // Compute the smallest VF at which the store and load would be misaligned
2031 // and recent enough to still be in the store buffer.
2032 for (uint64_t VF = 2 * TypeByteSize;
2033 VF <= MaxVFWithoutSLForwardIssuesPowerOf2; VF *= 2) {
2034 if (isStoreLoadForwardingConflict(Distance, VectorStoreSize: VF, TypeByteSize, LoadElementSize: VF)) {
2035 MaxVFWithoutSLForwardIssuesPowerOf2 = (VF >> 1);
2036 break;
2037 }
2038 }
2039
2040 if (MaxVFWithoutSLForwardIssuesPowerOf2 < 2 * TypeByteSize) {
2041 LLVM_DEBUG(
2042 dbgs() << "LAA: Distance " << Distance
2043 << " that could cause a store-load forwarding conflict\n");
2044 return true;
2045 }
2046
2047 if (CommonStride &&
2048 MaxVFWithoutSLForwardIssuesPowerOf2 <
2049 MaxStoreLoadForwardSafeDistanceInBits &&
2050 MaxVFWithoutSLForwardIssuesPowerOf2 !=
2051 VectorizerParams::MaxVectorWidth * TypeByteSize) {
2052 uint64_t MaxVF =
2053 bit_floor(Value: MaxVFWithoutSLForwardIssuesPowerOf2 / CommonStride);
2054 uint64_t MaxVFInBits = MaxVF * TypeByteSize * 8;
2055 MaxStoreLoadForwardSafeDistanceInBits =
2056 std::min(a: MaxStoreLoadForwardSafeDistanceInBits, b: MaxVFInBits);
2057
2058 if (MaxVF < 2) {
2059 LLVM_DEBUG(
2060 dbgs() << "LAA: strided access with Distance " << Distance
2061 << " that could cause a store-load forwarding conflict\n");
2062 return true;
2063 }
2064 }
2065 return false;
2066}
2067
2068void MemoryDepChecker::mergeInStatus(VectorizationSafetyStatus S) {
2069 if (Status < S)
2070 Status = S;
2071}
2072
2073/// Given a dependence-distance \p Dist between two memory accesses, that have
2074/// strides in the same direction whose absolute value of the maximum stride is
2075/// given in \p MaxStride, in a loop whose maximum backedge taken count is \p
2076/// MaxBTC, check if it is possible to prove statically that the dependence
2077/// distance is larger than the range that the accesses will travel through the
2078/// execution of the loop. If so, return true; false otherwise. This is useful
2079/// for example in loops such as the following (PR31098):
2080///
2081/// for (i = 0; i < D; ++i) {
2082/// = out[i];
2083/// out[i+D] =
2084/// }
2085static bool isSafeDependenceDistance(const DataLayout &DL, ScalarEvolution &SE,
2086 const SCEV &MaxBTC, const SCEV &Dist,
2087 uint64_t MaxStride) {
2088
2089 // If we can prove that
2090 // (**) |Dist| > MaxBTC * Step
2091 // where Step is the absolute stride of the memory accesses in bytes,
2092 // then there is no dependence.
2093 //
2094 // Rationale:
2095 // We basically want to check if the absolute distance (|Dist/Step|)
2096 // is >= the loop iteration count (or > MaxBTC).
2097 // This is equivalent to the Strong SIV Test (Practical Dependence Testing,
2098 // Section 4.2.1); Note, that for vectorization it is sufficient to prove
2099 // that the dependence distance is >= VF; This is checked elsewhere.
2100 // But in some cases we can prune dependence distances early, and
2101 // even before selecting the VF, and without a runtime test, by comparing
2102 // the distance against the loop iteration count. Since the vectorized code
2103 // will be executed only if LoopCount >= VF, proving distance >= LoopCount
2104 // also guarantees that distance >= VF.
2105 //
2106 const SCEV *Step = SE.getConstant(Ty: MaxBTC.getType(), V: MaxStride);
2107 const SCEV *Product = SE.getMulExpr(LHS: &MaxBTC, RHS: Step);
2108
2109 const SCEV *CastedDist = &Dist;
2110 const SCEV *CastedProduct = Product;
2111 uint64_t DistTypeSizeBits = DL.getTypeSizeInBits(Ty: Dist.getType());
2112 uint64_t ProductTypeSizeBits = DL.getTypeSizeInBits(Ty: Product->getType());
2113
2114 // The dependence distance can be positive/negative, so we sign extend Dist;
2115 // The multiplication of the absolute stride in bytes and the
2116 // backedgeTakenCount is non-negative, so we zero extend Product.
2117 if (DistTypeSizeBits > ProductTypeSizeBits)
2118 CastedProduct = SE.getZeroExtendExpr(Op: Product, Ty: Dist.getType());
2119 else
2120 CastedDist = SE.getNoopOrSignExtend(V: &Dist, Ty: Product->getType());
2121
2122 // Is Dist - (MaxBTC * Step) > 0 ?
2123 // (If so, then we have proven (**) because |Dist| >= Dist)
2124 const SCEV *Minus = SE.getMinusSCEV(LHS: CastedDist, RHS: CastedProduct);
2125 if (SE.isKnownPositive(S: Minus))
2126 return true;
2127
2128 // Second try: Is -Dist - (MaxBTC * Step) > 0 ?
2129 // (If so, then we have proven (**) because |Dist| >= -1*Dist)
2130 const SCEV *NegDist = SE.getNegativeSCEV(V: CastedDist);
2131 Minus = SE.getMinusSCEV(LHS: NegDist, RHS: CastedProduct);
2132 return SE.isKnownPositive(S: Minus);
2133}
2134
2135/// Check the dependence for two accesses with the same stride \p Stride.
2136/// \p Distance is the positive distance in bytes, and \p TypeByteSize is type
2137/// size in bytes.
2138///
2139/// \returns true if they are independent.
2140static bool areStridedAccessesIndependent(uint64_t Distance, uint64_t Stride,
2141 uint64_t TypeByteSize) {
2142 assert(Stride > 1 && "The stride must be greater than 1");
2143 assert(TypeByteSize > 0 && "The type size in byte must be non-zero");
2144 assert(Distance > 0 && "The distance must be non-zero");
2145
2146 // Skip if the distance is not multiple of type byte size.
2147 if (Distance % TypeByteSize)
2148 return false;
2149
2150 // No dependence if the distance is not multiple of the stride.
2151 // E.g.
2152 // for (i = 0; i < 1024 ; i += 4)
2153 // A[i+2] = A[i] + 1;
2154 //
2155 // Two accesses in memory (distance is 2, stride is 4):
2156 // | A[0] | | | | A[4] | | | |
2157 // | | | A[2] | | | | A[6] | |
2158 //
2159 // E.g.
2160 // for (i = 0; i < 1024 ; i += 3)
2161 // A[i+4] = A[i] + 1;
2162 //
2163 // Two accesses in memory (distance is 4, stride is 3):
2164 // | A[0] | | | A[3] | | | A[6] | | |
2165 // | | | | | A[4] | | | A[7] | |
2166 return Distance % Stride;
2167}
2168
2169bool MemoryDepChecker::areAccessesCompletelyBeforeOrAfter(const SCEV *Src,
2170 Type *SrcTy,
2171 const SCEV *Sink,
2172 Type *SinkTy) {
2173 const SCEV *BTC = PSE.getBackedgeTakenCount();
2174 const SCEV *SymbolicMaxBTC = PSE.getSymbolicMaxBackedgeTakenCount();
2175 ScalarEvolution &SE = *PSE.getSE();
2176 const auto &[SrcStart_, SrcEnd_] =
2177 getStartAndEndForAccess(Lp: InnermostLoop, PtrExpr: Src, AccessTy: SrcTy, BTC, MaxBTC: SymbolicMaxBTC,
2178 SE: &SE, PointerBounds: &PointerBounds, DT, AC, LoopGuards);
2179 if (isa<SCEVCouldNotCompute>(Val: SrcStart_) || isa<SCEVCouldNotCompute>(Val: SrcEnd_))
2180 return false;
2181
2182 const auto &[SinkStart_, SinkEnd_] =
2183 getStartAndEndForAccess(Lp: InnermostLoop, PtrExpr: Sink, AccessTy: SinkTy, BTC, MaxBTC: SymbolicMaxBTC,
2184 SE: &SE, PointerBounds: &PointerBounds, DT, AC, LoopGuards);
2185 if (isa<SCEVCouldNotCompute>(Val: SinkStart_) ||
2186 isa<SCEVCouldNotCompute>(Val: SinkEnd_))
2187 return false;
2188
2189 if (!LoopGuards)
2190 LoopGuards.emplace(args: ScalarEvolution::LoopGuards::collect(L: InnermostLoop, SE));
2191
2192 auto SrcEnd = SE.applyLoopGuards(Expr: SrcEnd_, Guards: *LoopGuards);
2193 auto SinkStart = SE.applyLoopGuards(Expr: SinkStart_, Guards: *LoopGuards);
2194 if (SE.isKnownPredicate(Pred: CmpInst::ICMP_ULE, LHS: SrcEnd, RHS: SinkStart))
2195 return true;
2196
2197 auto SinkEnd = SE.applyLoopGuards(Expr: SinkEnd_, Guards: *LoopGuards);
2198 auto SrcStart = SE.applyLoopGuards(Expr: SrcStart_, Guards: *LoopGuards);
2199 return SE.isKnownPredicate(Pred: CmpInst::ICMP_ULE, LHS: SinkEnd, RHS: SrcStart);
2200}
2201
2202std::variant<MemoryDepChecker::Dependence::DepType,
2203 MemoryDepChecker::DepDistanceStrideAndSizeInfo>
2204MemoryDepChecker::getDependenceDistanceStrideAndSize(
2205 const AccessAnalysis::MemAccessInfo &A, Instruction *AInst,
2206 const AccessAnalysis::MemAccessInfo &B, Instruction *BInst) {
2207 const auto &DL = InnermostLoop->getHeader()->getDataLayout();
2208 auto &SE = *PSE.getSE();
2209 const auto &[APtr, AIsWrite] = A;
2210 const auto &[BPtr, BIsWrite] = B;
2211
2212 // Two reads are independent.
2213 if (!AIsWrite && !BIsWrite)
2214 return MemoryDepChecker::Dependence::NoDep;
2215
2216 Type *ATy = getLoadStoreType(I: AInst);
2217 Type *BTy = getLoadStoreType(I: BInst);
2218
2219 // We cannot check pointers in different address spaces.
2220 if (APtr->getType()->getPointerAddressSpace() !=
2221 BPtr->getType()->getPointerAddressSpace())
2222 return MemoryDepChecker::Dependence::Unknown;
2223
2224 SmallVector<const SCEVPredicate *> Predicates;
2225 std::optional<int64_t> StrideAPtr =
2226 getPtrStride(PSE, AccessTy: ATy, Ptr: APtr, Lp: InnermostLoop, DT: *DT, StridesMap: SymbolicStrides,
2227 /*ShouldCheckWrap=*/true, Predicates: &Predicates);
2228 std::optional<int64_t> StrideBPtr =
2229 getPtrStride(PSE, AccessTy: BTy, Ptr: BPtr, Lp: InnermostLoop, DT: *DT, StridesMap: SymbolicStrides,
2230 /*ShouldCheckWrap=*/true, Predicates: &Predicates);
2231 PSE.addPredicates(Preds: Predicates);
2232
2233 const SCEV *Src = PSE.getSCEV(V: APtr);
2234 const SCEV *Sink = PSE.getSCEV(V: BPtr);
2235
2236 // If the induction step is negative we have to invert source and sink of the
2237 // dependence when measuring the distance between them. We should not swap
2238 // AIsWrite with BIsWrite, as their uses expect them in program order.
2239 if (StrideAPtr && *StrideAPtr < 0) {
2240 std::swap(a&: Src, b&: Sink);
2241 std::swap(a&: AInst, b&: BInst);
2242 std::swap(a&: ATy, b&: BTy);
2243 std::swap(lhs&: StrideAPtr, rhs&: StrideBPtr);
2244 }
2245
2246 const SCEV *Dist = SE.getMinusSCEV(LHS: Sink, RHS: Src);
2247
2248 LLVM_DEBUG(dbgs() << "LAA: Src Scev: " << *Src << "Sink Scev: " << *Sink
2249 << "\n");
2250 LLVM_DEBUG(dbgs() << "LAA: Distance for " << *AInst << " to " << *BInst
2251 << ": " << *Dist << "\n");
2252
2253 // Need accesses with constant strides and the same direction for further
2254 // dependence analysis. We don't want to vectorize "A[B[i]] += ..." and
2255 // similar code or pointer arithmetic that could wrap in the address space.
2256
2257 // If either Src or Sink are not strided (i.e. not a non-wrapping AddRec) and
2258 // not loop-invariant (stride will be 0 in that case), we cannot analyze the
2259 // dependence further and also cannot generate runtime checks.
2260 if (!StrideAPtr || !StrideBPtr) {
2261 LLVM_DEBUG(dbgs() << "Pointer access with non-constant stride\n");
2262 return MemoryDepChecker::Dependence::IndirectUnsafe;
2263 }
2264
2265 int64_t StrideAPtrInt = *StrideAPtr;
2266 int64_t StrideBPtrInt = *StrideBPtr;
2267 LLVM_DEBUG(dbgs() << "LAA: Src induction step: " << StrideAPtrInt
2268 << " Sink induction step: " << StrideBPtrInt << "\n");
2269 // At least Src or Sink are loop invariant and the other is strided or
2270 // invariant.
2271 if (!StrideAPtrInt || !StrideBPtrInt) {
2272 // If both are loop-invariant and access the same location, we cannot
2273 // vectorize.
2274 if (!StrideAPtrInt && !StrideBPtrInt && Dist->isZero())
2275 return MemoryDepChecker::Dependence::InvariantUnsafe;
2276 // Otherwise, we can generate a runtime check to disambiguate the accesses.
2277 return MemoryDepChecker::Dependence::Unknown;
2278 }
2279
2280 // Both Src and Sink have a constant stride, check if they are in the same
2281 // direction.
2282 if ((StrideAPtrInt > 0) != (StrideBPtrInt > 0)) {
2283 LLVM_DEBUG(
2284 dbgs() << "Pointer access with strides in different directions\n");
2285 return MemoryDepChecker::Dependence::Unknown;
2286 }
2287
2288 TypeSize AStoreSz = DL.getTypeStoreSize(Ty: ATy);
2289 TypeSize BStoreSz = DL.getTypeStoreSize(Ty: BTy);
2290
2291 // If store sizes are not the same, set TypeByteSize to zero, so we can check
2292 // it in the caller isDependent.
2293 uint64_t ASz = DL.getTypeAllocSize(Ty: ATy);
2294 uint64_t BSz = DL.getTypeAllocSize(Ty: BTy);
2295 uint64_t TypeByteSize = (AStoreSz == BStoreSz) ? BSz : 0;
2296
2297 uint64_t StrideAScaled = AbsoluteValue(X: StrideAPtrInt) * ASz;
2298 uint64_t StrideBScaled = AbsoluteValue(X: StrideBPtrInt) * BSz;
2299
2300 uint64_t MaxStride = std::max(a: StrideAScaled, b: StrideBScaled);
2301
2302 std::optional<uint64_t> CommonStride;
2303 if (StrideAScaled == StrideBScaled)
2304 CommonStride = StrideAScaled;
2305
2306 // TODO: Historically, we didn't retry with runtime checks when (unscaled)
2307 // strides were different but there is no inherent reason to.
2308 if (!isa<SCEVConstant>(Val: Dist))
2309 ShouldRetryWithRuntimeChecks |= StrideAPtrInt == StrideBPtrInt;
2310
2311 // If distance is a SCEVCouldNotCompute, return Unknown immediately.
2312 if (isa<SCEVCouldNotCompute>(Val: Dist)) {
2313 LLVM_DEBUG(dbgs() << "LAA: Uncomputable distance.\n");
2314 return Dependence::Unknown;
2315 }
2316
2317 return DepDistanceStrideAndSizeInfo(Dist, MaxStride, CommonStride,
2318 TypeByteSize, AIsWrite, BIsWrite);
2319}
2320
2321MemoryDepChecker::Dependence::DepType
2322MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
2323 const MemAccessInfo &B, unsigned BIdx) {
2324 assert(AIdx < BIdx && "Must pass arguments in program order");
2325
2326 // Check if we can prove that Sink only accesses memory after Src's end or
2327 // vice versa. The helper is used to perform the checks only on the exit paths
2328 // where it helps to improve the analysis result.
2329 auto CheckCompletelyBeforeOrAfter = [&]() {
2330 auto *APtr = A.getPointer();
2331 auto *BPtr = B.getPointer();
2332 Type *ATy = getLoadStoreType(I: InstMap[AIdx]);
2333 Type *BTy = getLoadStoreType(I: InstMap[BIdx]);
2334 const SCEV *Src = PSE.getSCEV(V: APtr);
2335 const SCEV *Sink = PSE.getSCEV(V: BPtr);
2336 return areAccessesCompletelyBeforeOrAfter(Src, SrcTy: ATy, Sink, SinkTy: BTy);
2337 };
2338
2339 // Get the dependence distance, stride, type size and what access writes for
2340 // the dependence between A and B.
2341 auto Res =
2342 getDependenceDistanceStrideAndSize(A, AInst: InstMap[AIdx], B, BInst: InstMap[BIdx]);
2343 if (std::holds_alternative<Dependence::DepType>(v: Res)) {
2344 if (std::get<Dependence::DepType>(v&: Res) == Dependence::Unknown &&
2345 CheckCompletelyBeforeOrAfter())
2346 return Dependence::NoDep;
2347 return std::get<Dependence::DepType>(v&: Res);
2348 }
2349
2350 auto &[Dist, MaxStride, CommonStride, TypeByteSize, AIsWrite, BIsWrite] =
2351 std::get<DepDistanceStrideAndSizeInfo>(v&: Res);
2352 bool HasSameSize = TypeByteSize > 0;
2353
2354 ScalarEvolution &SE = *PSE.getSE();
2355 auto &DL = InnermostLoop->getHeader()->getDataLayout();
2356
2357 // If the distance between the acecsses is larger than their maximum absolute
2358 // stride multiplied by the symbolic maximum backedge taken count (which is an
2359 // upper bound of the number of iterations), the accesses are independet, i.e.
2360 // they are far enough appart that accesses won't access the same location
2361 // across all loop ierations.
2362 if (HasSameSize &&
2363 isSafeDependenceDistance(
2364 DL, SE, MaxBTC: *(PSE.getSymbolicMaxBackedgeTakenCount()), Dist: *Dist, MaxStride))
2365 return Dependence::NoDep;
2366
2367 const APInt *APDist = nullptr;
2368 uint64_t ConstDist = 0;
2369 if (match(S: Dist, P: m_scev_APInt(C&: APDist))) {
2370 std::optional<uint64_t> Val = APDist->abs().tryZExtValue();
2371 if (!Val) {
2372 LLVM_DEBUG(dbgs() << "LAA: Constant distance does not fit in 64 bits.\n");
2373 return Dependence::Unknown;
2374 }
2375 ConstDist = *Val;
2376 }
2377
2378 // Attempt to prove strided accesses independent.
2379 if (APDist) {
2380 // If the distance between accesses and their strides are known constants,
2381 // check whether the accesses interlace each other.
2382 if (ConstDist > 0 && CommonStride && CommonStride > 1 && HasSameSize &&
2383 areStridedAccessesIndependent(Distance: ConstDist, Stride: *CommonStride, TypeByteSize)) {
2384 LLVM_DEBUG(dbgs() << "LAA: Strided accesses are independent\n");
2385 return Dependence::NoDep;
2386 }
2387 } else {
2388 if (!LoopGuards)
2389 LoopGuards.emplace(
2390 args: ScalarEvolution::LoopGuards::collect(L: InnermostLoop, SE));
2391 Dist = SE.applyLoopGuards(Expr: Dist, Guards: *LoopGuards);
2392 }
2393
2394 // Negative distances are not plausible dependencies.
2395 if (SE.isKnownNonPositive(S: Dist)) {
2396 if (SE.isKnownNonNegative(S: Dist)) {
2397 // Equal-sized accesses to the same location are forward.
2398 if (HasSameSize)
2399 return Dependence::Forward;
2400
2401 if (CommonStride) {
2402 // For mixed sizes, CommonStride is asserted to cover both accesses when
2403 // computed in getDependenceDistanceStrideAndSize, so different
2404 // iterations cannot overlap.
2405 [[maybe_unused]] uint64_t ASz =
2406 DL.getTypeAllocSize(Ty: getLoadStoreType(I: InstMap[AIdx]));
2407 [[maybe_unused]] uint64_t BSz =
2408 DL.getTypeAllocSize(Ty: getLoadStoreType(I: InstMap[BIdx]));
2409 assert(*CommonStride >= std::max(ASz, BSz) &&
2410 "Invariant from getDependenceDistanceStrideAndSize broken!");
2411 return Dependence::Forward;
2412 }
2413 LLVM_DEBUG(dbgs() << "LAA: possibly zero dependence difference but "
2414 "different type sizes\n");
2415 return Dependence::Unknown;
2416 }
2417
2418 bool IsTrueDataDependence = (AIsWrite && !BIsWrite);
2419 // Check if the first access writes to a location that is read in a later
2420 // iteration, where the distance between them is not a multiple of a vector
2421 // factor and relatively small.
2422 //
2423 // NOTE: There is no need to update MaxSafeVectorWidthInBits after call to
2424 // couldPreventStoreLoadForward, even if it changed MinDepDistBytes, since a
2425 // forward dependency will allow vectorization using any width.
2426
2427 if (IsTrueDataDependence && EnableForwardingConflictDetection) {
2428 if (!ConstDist) {
2429 return CheckCompletelyBeforeOrAfter() ? Dependence::NoDep
2430 : Dependence::Unknown;
2431 }
2432 if (!HasSameSize ||
2433 couldPreventStoreLoadForward(Distance: ConstDist, TypeByteSize)) {
2434 LLVM_DEBUG(
2435 dbgs() << "LAA: Forward but may prevent st->ld forwarding\n");
2436 return Dependence::ForwardButPreventsForwarding;
2437 }
2438 }
2439
2440 LLVM_DEBUG(dbgs() << "LAA: Dependence is negative\n");
2441 return Dependence::Forward;
2442 }
2443
2444 std::optional<int64_t> MinDistanceOpt =
2445 SE.getSignedRangeMin(S: Dist).trySExtValue();
2446 if (!MinDistanceOpt) {
2447 LLVM_DEBUG(dbgs() << "LAA: Minimum distance does not fit in 64 bits.\n");
2448 return Dependence::Unknown;
2449 }
2450 int64_t MinDistance = *MinDistanceOpt;
2451 // Below we only handle strictly positive distances.
2452 if (MinDistance <= 0) {
2453 return CheckCompletelyBeforeOrAfter() ? Dependence::NoDep
2454 : Dependence::Unknown;
2455 }
2456
2457 if (!HasSameSize) {
2458 if (CheckCompletelyBeforeOrAfter())
2459 return Dependence::NoDep;
2460 LLVM_DEBUG(dbgs() << "LAA: ReadWrite-Write positive dependency with "
2461 "different type sizes\n");
2462 return Dependence::Unknown;
2463 }
2464 // Bail out early if passed-in parameters make vectorization not feasible.
2465 unsigned MinForcedFactor =
2466 std::max(a: 1U, b: VectorizerParams::VectorizationFactor.getKnownMinValue());
2467 unsigned ForcedUnroll = (VectorizerParams::VectorizationInterleave ?
2468 VectorizerParams::VectorizationInterleave : 1);
2469 // The minimum number of iterations for a vectorized/unrolled version.
2470 unsigned MinNumIter = std::max(a: MinForcedFactor * ForcedUnroll, b: 2U);
2471
2472 // It's not vectorizable if the distance is smaller than the minimum distance
2473 // needed for a vectroized/unrolled version. Vectorizing one iteration in
2474 // front needs MaxStride. Vectorizing the last iteration needs TypeByteSize.
2475 // (No need to plus the last gap distance).
2476 //
2477 // E.g. Assume one char is 1 byte in memory and one int is 4 bytes.
2478 // foo(int *A) {
2479 // int *B = (int *)((char *)A + 14);
2480 // for (i = 0 ; i < 1024 ; i += 2)
2481 // B[i] = A[i] + 1;
2482 // }
2483 //
2484 // Two accesses in memory (stride is 4 * 2):
2485 // | A[0] | | A[2] | | A[4] | | A[6] | |
2486 // | B[0] | | B[2] | | B[4] |
2487 //
2488 // MinDistance needs for vectorizing iterations except the last iteration:
2489 // 4 * 2 * (MinNumIter - 1). MinDistance needs for the last iteration: 4.
2490 // So the minimum distance needed is: 4 * 2 * (MinNumIter - 1) + 4.
2491 //
2492 // If MinNumIter is 2, it is vectorizable as the minimum distance needed is
2493 // 12, which is less than distance.
2494 //
2495 // If MinNumIter is 4 (Say if a user forces the vectorization factor to be 4),
2496 // the minimum distance needed is 28, which is greater than distance. It is
2497 // not safe to do vectorization.
2498 //
2499 // We use MaxStride (maximum of src and sink strides) to get a conservative
2500 // lower bound on the MinDistanceNeeded in case of different strides.
2501
2502 // We know that Dist is positive, but it may not be constant. Use the signed
2503 // minimum for computations below, as this ensures we compute the closest
2504 // possible dependence distance.
2505 uint64_t MinDistanceNeeded = MaxStride * (MinNumIter - 1) + TypeByteSize;
2506 if (MinDistanceNeeded > static_cast<uint64_t>(MinDistance)) {
2507 if (!ConstDist) {
2508 // For non-constant distances, we checked the lower bound of the
2509 // dependence distance and the distance may be larger at runtime (and safe
2510 // for vectorization). Classify it as Unknown, so we re-try with runtime
2511 // checks, unless we can prove both accesses cannot overlap.
2512 return CheckCompletelyBeforeOrAfter() ? Dependence::NoDep
2513 : Dependence::Unknown;
2514 }
2515 LLVM_DEBUG(dbgs() << "LAA: Failure because of positive minimum distance "
2516 << MinDistance << '\n');
2517 return Dependence::Backward;
2518 }
2519
2520 // Unsafe if the minimum distance needed is greater than smallest dependence
2521 // distance distance.
2522 if (MinDistanceNeeded > MinDepDistBytes) {
2523 LLVM_DEBUG(dbgs() << "LAA: Failure because it needs at least "
2524 << MinDistanceNeeded << " size in bytes\n");
2525 return Dependence::Backward;
2526 }
2527
2528 MinDepDistBytes =
2529 std::min(a: static_cast<uint64_t>(MinDistance), b: MinDepDistBytes);
2530
2531 bool IsTrueDataDependence = (!AIsWrite && BIsWrite);
2532 if (IsTrueDataDependence && EnableForwardingConflictDetection && ConstDist &&
2533 couldPreventStoreLoadForward(Distance: MinDistance, TypeByteSize, CommonStride: *CommonStride))
2534 return Dependence::BackwardVectorizableButPreventsForwarding;
2535
2536 uint64_t MaxVF = MinDepDistBytes / MaxStride;
2537 LLVM_DEBUG(dbgs() << "LAA: Positive min distance " << MinDistance
2538 << " with max VF = " << MaxVF << '\n');
2539
2540 uint64_t MaxVFInBits = MaxVF * TypeByteSize * 8;
2541 if (!ConstDist && MaxVFInBits < MaxTargetVectorWidthInBits) {
2542 // For non-constant distances, we checked the lower bound of the dependence
2543 // distance and the distance may be larger at runtime (and safe for
2544 // vectorization). Classify it as Unknown, so we re-try with runtime checks,
2545 // unless we can prove both accesses cannot overlap.
2546 return CheckCompletelyBeforeOrAfter() ? Dependence::NoDep
2547 : Dependence::Unknown;
2548 }
2549
2550 if (CheckCompletelyBeforeOrAfter())
2551 return Dependence::NoDep;
2552
2553 MaxSafeVectorWidthInBits = std::min(a: MaxSafeVectorWidthInBits, b: MaxVFInBits);
2554 return Dependence::BackwardVectorizable;
2555}
2556
2557bool MemoryDepChecker::areDepsSafe(const DepCandidates &DepCands,
2558 ArrayRef<MemAccessInfo> CheckDeps) {
2559
2560 MinDepDistBytes = -1;
2561 SmallPtrSet<MemAccessInfo, 8> Visited;
2562 for (MemAccessInfo CurAccess : CheckDeps) {
2563 if (Visited.contains(Ptr: CurAccess))
2564 continue;
2565
2566 // Check accesses within this set.
2567 EquivalenceClasses<MemAccessInfo>::member_iterator AI =
2568 DepCands.findLeader(V: CurAccess);
2569 EquivalenceClasses<MemAccessInfo>::member_iterator AE =
2570 DepCands.member_end();
2571
2572 // Check every access pair.
2573 while (AI != AE) {
2574 Visited.insert(Ptr: *AI);
2575 bool AIIsWrite = AI->getInt();
2576 // Reads from the same pointer don't create extra hazards, but multiple
2577 // stores do (WAW), so start from AI for writes and next(AI) for reads.
2578 EquivalenceClasses<MemAccessInfo>::member_iterator OI =
2579 (AIIsWrite ? AI : std::next(x: AI));
2580 while (OI != AE) {
2581 // Check every accessing instruction pair in program order.
2582 auto &Acc = Accesses[*AI];
2583 for (std::vector<unsigned>::iterator I1 = Acc.begin(), I1E = Acc.end();
2584 I1 != I1E; ++I1)
2585 // When checking for WAW (OI == AI) caused by multiple writes to the
2586 // same pointer, start I2 at the next access past I1 to avoid
2587 // self-comparison.
2588 for (std::vector<unsigned>::iterator
2589 I2 = (OI == AI ? std::next(x: I1) : Accesses[*OI].begin()),
2590 I2E = (OI == AI ? I1E : Accesses[*OI].end());
2591 I2 != I2E; ++I2) {
2592 auto A = std::make_pair(x: &*AI, y&: *I1);
2593 auto B = std::make_pair(x: &*OI, y&: *I2);
2594
2595 assert(*I1 != *I2);
2596 if (*I1 > *I2)
2597 std::swap(x&: A, y&: B);
2598
2599 Dependence::DepType Type =
2600 isDependent(A: *A.first, AIdx: A.second, B: *B.first, BIdx: B.second);
2601 mergeInStatus(S: Dependence::isSafeForVectorization(Type));
2602
2603 // Gather dependences unless we accumulated MaxDependences
2604 // dependences. In that case return as soon as we find the first
2605 // unsafe dependence. This puts a limit on this quadratic
2606 // algorithm.
2607 if (RecordDependences) {
2608 if (Type != Dependence::NoDep)
2609 Dependences.emplace_back(Args&: A.second, Args&: B.second, Args&: Type);
2610
2611 if (Dependences.size() >= MaxDependences) {
2612 RecordDependences = false;
2613 Dependences.clear();
2614 LLVM_DEBUG(dbgs()
2615 << "Too many dependences, stopped recording\n");
2616 }
2617 }
2618 if (!RecordDependences && !isSafeForVectorization())
2619 return false;
2620 }
2621 ++OI;
2622 }
2623 ++AI;
2624 }
2625 }
2626
2627 LLVM_DEBUG(dbgs() << "Total Dependences: " << Dependences.size() << "\n");
2628 return isSafeForVectorization();
2629}
2630
2631SmallVector<Instruction *, 4>
2632MemoryDepChecker::getInstructionsForAccess(Value *Ptr, bool IsWrite) const {
2633 MemAccessInfo Access(Ptr, IsWrite);
2634 auto I = Accesses.find(Val: Access);
2635 SmallVector<Instruction *, 4> Insts;
2636 if (I != Accesses.end()) {
2637 transform(Range: I->second, d_first: std::back_inserter(x&: Insts),
2638 F: [&](unsigned Idx) { return this->InstMap[Idx]; });
2639 }
2640
2641 return Insts;
2642}
2643
2644const char *MemoryDepChecker::Dependence::DepName[] = {
2645 "NoDep",
2646 "Unknown",
2647 "IndirectUnsafe",
2648 "InvariantUnsafe",
2649 "Forward",
2650 "ForwardButPreventsForwarding",
2651 "Backward",
2652 "BackwardVectorizable",
2653 "BackwardVectorizableButPreventsForwarding"};
2654
2655void MemoryDepChecker::Dependence::print(
2656 raw_ostream &OS, unsigned Depth,
2657 const SmallVectorImpl<Instruction *> &Instrs) const {
2658 OS.indent(NumSpaces: Depth) << DepName[Type] << ":\n";
2659 OS.indent(NumSpaces: Depth + 2) << *Instrs[Source] << " -> \n";
2660 OS.indent(NumSpaces: Depth + 2) << *Instrs[Destination] << "\n";
2661}
2662
2663bool LoopAccessInfo::canAnalyzeLoop() {
2664 // We need to have a loop header.
2665 LLVM_DEBUG(dbgs() << "\nLAA: Checking a loop in '"
2666 << TheLoop->getHeader()->getParent()->getName() << "' from "
2667 << TheLoop->getLocStr() << "\n");
2668
2669 // We can only analyze innermost loops.
2670 if (!TheLoop->isInnermost()) {
2671 LLVM_DEBUG(dbgs() << "LAA: loop is not the innermost loop\n");
2672 recordAnalysis(RemarkName: "NotInnerMostLoop") << "loop is not the innermost loop";
2673 return false;
2674 }
2675
2676 // We must have a single backedge.
2677 if (TheLoop->getNumBackEdges() != 1) {
2678 LLVM_DEBUG(
2679 dbgs() << "LAA: loop control flow is not understood by analyzer\n");
2680 recordAnalysis(RemarkName: "CFGNotUnderstood")
2681 << "loop control flow is not understood by analyzer";
2682 return false;
2683 }
2684
2685 // ScalarEvolution needs to be able to find the symbolic max backedge taken
2686 // count, which is an upper bound on the number of loop iterations. The loop
2687 // may execute fewer iterations, if it exits via an uncountable exit.
2688 const SCEV *ExitCount = PSE->getSymbolicMaxBackedgeTakenCount();
2689 if (isa<SCEVCouldNotCompute>(Val: ExitCount)) {
2690 recordAnalysis(RemarkName: "CantComputeNumberOfIterations")
2691 << "could not determine number of loop iterations";
2692 LLVM_DEBUG(dbgs() << "LAA: SCEV could not compute the loop exit count.\n");
2693 return false;
2694 }
2695
2696 LLVM_DEBUG(dbgs() << "LAA: Found an analyzable loop: "
2697 << TheLoop->getHeader()->getName() << "\n");
2698 return true;
2699}
2700
2701bool LoopAccessInfo::analyzeLoop(AAResults *AA, const LoopInfo *LI,
2702 const TargetLibraryInfo *TLI,
2703 DominatorTree *DT) {
2704 // Holds the Load and Store instructions.
2705 SmallVector<LoadInst *, 16> Loads;
2706 SmallVector<StoreInst *, 16> Stores;
2707 SmallPtrSet<MDNode *, 8> LoopAliasScopes;
2708
2709 // Holds all the different accesses in the loop.
2710 unsigned NumReads = 0;
2711 unsigned NumReadWrites = 0;
2712
2713 bool HasComplexMemInst = false;
2714
2715 // A runtime check is only legal to insert if there are no convergent calls.
2716 HasConvergentOp = false;
2717
2718 PtrRtChecking->Pointers.clear();
2719 PtrRtChecking->Need = false;
2720
2721 const bool IsAnnotatedParallel = TheLoop->isAnnotatedParallel();
2722
2723 const bool EnableMemAccessVersioningOfLoop =
2724 EnableMemAccessVersioning &&
2725 !TheLoop->getHeader()->getParent()->hasOptSize();
2726
2727 // Traverse blocks in fixed RPOT order, regardless of their storage in the
2728 // loop info, as it may be arbitrary.
2729 LoopBlocksRPO RPOT(TheLoop);
2730 RPOT.perform(LI);
2731
2732 // Don't return early as soon as we found a memory access that cannot be
2733 // vectorize - HasConvergentOp must still be computed as it is part of LAI's
2734 // public API (used by LoopDistribute).
2735 for (BasicBlock *BB : RPOT) {
2736 // Scan the BB and collect legal loads and stores. Also detect any
2737 // convergent instructions.
2738 for (Instruction &I : *BB) {
2739 if (auto *Call = dyn_cast<CallBase>(Val: &I)) {
2740 if (Call->isConvergent())
2741 HasConvergentOp = true;
2742 }
2743
2744 // Unsafe to vectorize and we already found a convergent operation, can
2745 // early return now.
2746 if (HasComplexMemInst && HasConvergentOp)
2747 return false;
2748
2749 // Already unsafe to vectorize; keep scanning for convergent ops.
2750 if (HasComplexMemInst)
2751 continue;
2752
2753 // Record alias scopes defined inside the loop.
2754 if (auto *Decl = dyn_cast<NoAliasScopeDeclInst>(Val: &I))
2755 for (Metadata *Op : Decl->getScopeList()->operands())
2756 LoopAliasScopes.insert(Ptr: cast<MDNode>(Val: Op));
2757
2758 // Many math library functions read the rounding mode. We will only
2759 // vectorize a loop if it contains known function calls that don't set
2760 // the flag. Therefore, it is safe to ignore this read from memory.
2761 auto *Call = dyn_cast<CallInst>(Val: &I);
2762 if (Call && getVectorIntrinsicIDForCall(CI: Call, TLI))
2763 continue;
2764
2765 // If this is a load, save it. If this instruction can read from memory
2766 // but is not a load, we only allow it if it's a call to a function with a
2767 // vector mapping and no pointer arguments.
2768 if (I.mayReadFromMemory()) {
2769 auto hasPointerArgs = [](CallBase *CB) {
2770 return any_of(Range: CB->args(), P: [](Value const *Arg) {
2771 return Arg->getType()->isPointerTy();
2772 });
2773 };
2774
2775 // If the function has an explicit vectorized counterpart, and does not
2776 // take output/input pointers, we can safely assume that it can be
2777 // vectorized.
2778 if (Call && !Call->isNoBuiltin() && Call->getCalledFunction() &&
2779 !hasPointerArgs(Call) && !VFDatabase::getMappings(CI: *Call).empty())
2780 continue;
2781
2782 auto *Ld = dyn_cast<LoadInst>(Val: &I);
2783 if (!Ld) {
2784 recordAnalysis(RemarkName: "CantVectorizeInstruction", Instr: &I)
2785 << "instruction cannot be vectorized";
2786 HasComplexMemInst = true;
2787 continue;
2788 }
2789 if (!Ld->isSimple() && !IsAnnotatedParallel) {
2790 recordAnalysis(RemarkName: "NonSimpleLoad", Instr: Ld)
2791 << "read with atomic ordering or volatile read";
2792 LLVM_DEBUG(dbgs() << "LAA: Found a non-simple load.\n");
2793 HasComplexMemInst = true;
2794 continue;
2795 }
2796 NumLoads++;
2797 Loads.push_back(Elt: Ld);
2798 DepChecker->addAccess(LI: Ld);
2799 if (EnableMemAccessVersioningOfLoop)
2800 collectStridedAccess(LoadOrStoreInst: Ld);
2801 continue;
2802 }
2803
2804 // Save 'store' instructions. Abort if other instructions write to memory.
2805 if (I.mayWriteToMemory()) {
2806 auto *St = dyn_cast<StoreInst>(Val: &I);
2807 if (!St) {
2808 recordAnalysis(RemarkName: "CantVectorizeInstruction", Instr: &I)
2809 << "instruction cannot be vectorized";
2810 HasComplexMemInst = true;
2811 continue;
2812 }
2813 if (!St->isSimple() && !IsAnnotatedParallel) {
2814 recordAnalysis(RemarkName: "NonSimpleStore", Instr: St)
2815 << "write with atomic ordering or volatile write";
2816 LLVM_DEBUG(dbgs() << "LAA: Found a non-simple store.\n");
2817 HasComplexMemInst = true;
2818 continue;
2819 }
2820 NumStores++;
2821 Stores.push_back(Elt: St);
2822 DepChecker->addAccess(SI: St);
2823 if (EnableMemAccessVersioningOfLoop)
2824 collectStridedAccess(LoadOrStoreInst: St);
2825 }
2826 } // Next instr.
2827 } // Next block.
2828
2829 if (HasComplexMemInst)
2830 return false;
2831
2832 // Now we have two lists that hold the loads and the stores.
2833 // Next, we find the pointers that they use.
2834
2835 // Check if we see any stores. If there are no stores, then we don't
2836 // care if the pointers are *restrict*.
2837 if (!Stores.size()) {
2838 LLVM_DEBUG(dbgs() << "LAA: Found a read-only loop!\n");
2839 return true;
2840 }
2841
2842 MemoryDepChecker::DepCandidates DepCands;
2843 AccessAnalysis Accesses(TheLoop, AA, LI, *DT, DepCands, *PSE,
2844 LoopAliasScopes);
2845
2846 // Holds the analyzed pointers. We don't want to call getUnderlyingObjects
2847 // multiple times on the same object. If the ptr is accessed twice, once
2848 // for read and once for write, it will only appear once (on the write
2849 // list). This is okay, since we are going to check for conflicts between
2850 // writes and between reads and writes, but not between reads and reads.
2851 SmallSet<std::pair<Value *, Type *>, 16> Seen;
2852
2853 // Record uniform store addresses to identify if we have multiple stores
2854 // to the same address.
2855 SmallPtrSet<Value *, 16> UniformStores;
2856
2857 for (StoreInst *ST : Stores) {
2858 Value *Ptr = ST->getPointerOperand();
2859
2860 if (isInvariant(V: Ptr)) {
2861 // Record store instructions to loop invariant addresses
2862 StoresToInvariantAddresses.push_back(Elt: ST);
2863 HasStoreStoreDependenceInvolvingLoopInvariantAddress |=
2864 !UniformStores.insert(Ptr).second;
2865 }
2866
2867 // If we did *not* see this pointer before, insert it to the read-write
2868 // list. At this phase it is only a 'write' list.
2869 Type *AccessTy = getLoadStoreType(I: ST);
2870 if (Seen.insert(V: {Ptr, AccessTy}).second) {
2871 ++NumReadWrites;
2872
2873 MemoryLocation Loc = MemoryLocation::get(SI: ST);
2874 // The TBAA metadata could have a control dependency on the predication
2875 // condition, so we cannot rely on it when determining whether or not we
2876 // need runtime pointer checks.
2877 if (blockNeedsPredication(BB: ST->getParent(), TheLoop, DT))
2878 Loc.AATags.TBAA = nullptr;
2879
2880 // Expand forked pointers (i.e., a phi of multiple strided pointers) into
2881 // all alternatives.
2882 visitPointers(StartPtr: const_cast<Value *>(Loc.Ptr), InnermostLoop: *TheLoop,
2883 AddPointer: [&Accesses, AccessTy, Loc](Value *Ptr) {
2884 MemoryLocation NewLoc = Loc.getWithNewPtr(NewPtr: Ptr);
2885 Accesses.addStore(Loc: NewLoc, AccessTy);
2886 });
2887 }
2888 }
2889
2890 if (IsAnnotatedParallel) {
2891 LLVM_DEBUG(
2892 dbgs() << "LAA: A loop annotated parallel, ignore memory dependency "
2893 << "checks.\n");
2894 return true;
2895 }
2896
2897 for (LoadInst *LD : Loads) {
2898 Value *Ptr = LD->getPointerOperand();
2899 // If we did *not* see this pointer before, insert it to the read list. If
2900 // we *did* see it before, then it is already in the read-write list. This
2901 // allows us to vectorize expressions such as A[i] += x; Because the address
2902 // of A[i] is a read-write pointer. This only works if the index of A[i] is
2903 // strictly monotonic, which we approximate (conservatively) via
2904 // getPtrStride. If the address is unknown (e.g. A[B[i]]) then we may read,
2905 // modify, and write overlapping words. Note that "zero stride" is unsafe
2906 // and is being handled below.
2907 bool IsReadOnlyPtr = false;
2908 Type *AccessTy = getLoadStoreType(I: LD);
2909 if (Seen.insert(V: {Ptr, AccessTy}).second ||
2910 !getPtrStride(PSE&: *PSE, AccessTy, Ptr, Lp: TheLoop, DT: *DT, StridesMap: SymbolicStrides, Assume: false,
2911 ShouldCheckWrap: true)) {
2912 ++NumReads;
2913 IsReadOnlyPtr = true;
2914 }
2915
2916 // See if there is an unsafe dependency between a load to a uniform address and
2917 // store to the same uniform address.
2918 if (UniformStores.contains(Ptr)) {
2919 LLVM_DEBUG(dbgs() << "LAA: Found an unsafe dependency between a uniform "
2920 "load and uniform store to the same address!\n");
2921 HasLoadStoreDependenceInvolvingLoopInvariantAddress = true;
2922 }
2923
2924 MemoryLocation Loc = MemoryLocation::get(LI: LD);
2925 // The TBAA metadata could have a control dependency on the predication
2926 // condition, so we cannot rely on it when determining whether or not we
2927 // need runtime pointer checks.
2928 if (blockNeedsPredication(BB: LD->getParent(), TheLoop, DT))
2929 Loc.AATags.TBAA = nullptr;
2930
2931 // Expand forked pointers (i.e., a phi of multiple strided pointers) into
2932 // all alternatives.
2933 visitPointers(StartPtr: const_cast<Value *>(Loc.Ptr), InnermostLoop: *TheLoop,
2934 AddPointer: [&Accesses, AccessTy, Loc, IsReadOnlyPtr](Value *Ptr) {
2935 MemoryLocation NewLoc = Loc.getWithNewPtr(NewPtr: Ptr);
2936 Accesses.addLoad(Loc: NewLoc, AccessTy, IsReadOnly: IsReadOnlyPtr);
2937 });
2938 }
2939
2940 // If we write (or read-write) to a single destination and there are no other
2941 // reads in this loop then is it safe to vectorize: the vectorized stores
2942 // preserve ordering via replication or order-preserving @llvm.masked.scatter.
2943 if (NumReadWrites == 1 && NumReads == 0) {
2944 LLVM_DEBUG(dbgs() << "LAA: Found a write-only loop!\n");
2945 return true;
2946 }
2947
2948 // Build dependence sets and check whether we need a runtime pointer bounds
2949 // check.
2950 Accesses.buildDependenceSets();
2951
2952 // Find pointers with computable bounds. We are going to use this information
2953 // to place a runtime bound check.
2954 Value *UncomputablePtr = nullptr;
2955 HasCompletePtrRtChecking =
2956 Accesses.canCheckPtrAtRT(RtCheck&: *PtrRtChecking, TheLoop, StridesMap: SymbolicStrides,
2957 UncomputablePtr, AllowPartial, DepChecker: getDepChecker());
2958 if (!HasCompletePtrRtChecking) {
2959 const auto *I = dyn_cast_or_null<Instruction>(Val: UncomputablePtr);
2960 recordAnalysis(RemarkName: "CantIdentifyArrayBounds", Instr: I)
2961 << "cannot identify array bounds";
2962 LLVM_DEBUG(dbgs() << "LAA: We can't vectorize because we can't find "
2963 << "the array bounds.\n");
2964 return false;
2965 }
2966
2967 LLVM_DEBUG(
2968 dbgs() << "LAA: May be able to perform a memory runtime check if needed.\n");
2969
2970 bool DepsAreSafe = true;
2971 if (Accesses.isDependencyCheckNeeded()) {
2972 LLVM_DEBUG(dbgs() << "LAA: Checking memory dependencies\n");
2973 DepsAreSafe =
2974 DepChecker->areDepsSafe(DepCands, CheckDeps: Accesses.getDependenciesToCheck());
2975
2976 if (!DepsAreSafe && DepChecker->shouldRetryWithRuntimeChecks()) {
2977 LLVM_DEBUG(dbgs() << "LAA: Retrying with memory checks\n");
2978
2979 PtrRtChecking->reset();
2980 PtrRtChecking->Need = true;
2981
2982 UncomputablePtr = nullptr;
2983 HasCompletePtrRtChecking = Accesses.canCheckPtrAtRT(
2984 RtCheck&: *PtrRtChecking, TheLoop, StridesMap: SymbolicStrides, UncomputablePtr,
2985 AllowPartial, DepChecker: getDepChecker());
2986
2987 // Check that we found the bounds for the pointer.
2988 if (!HasCompletePtrRtChecking) {
2989 auto *I = dyn_cast_or_null<Instruction>(Val: UncomputablePtr);
2990 recordAnalysis(RemarkName: "CantCheckMemDepsAtRunTime", Instr: I)
2991 << "cannot check memory dependencies at runtime";
2992 LLVM_DEBUG(dbgs() << "LAA: Can't vectorize with memory checks\n");
2993 return false;
2994 }
2995
2996 // Clear the dependency checks. They are no longer needed.
2997 Accesses.resetDepChecks(DepChecker&: *DepChecker);
2998
2999 DepsAreSafe = true;
3000 }
3001 }
3002
3003 // Update the invariant address dependence flags based on dependences found
3004 // by the dep checker. Even if dependences were not recorded (too many to
3005 // track), any InvariantUnsafe dep would still have set the status to Unsafe
3006 if (const auto *Deps = DepChecker->getDependences()) {
3007 for (const auto &Dep : *Deps) {
3008 if (Dep.Type != MemoryDepChecker::Dependence::InvariantUnsafe)
3009 continue;
3010 Instruction *Src = Dep.getSource(DepChecker: *DepChecker);
3011 Instruction *Dst = Dep.getDestination(DepChecker: *DepChecker);
3012 if (isa<LoadInst>(Val: Src) != isa<LoadInst>(Val: Dst)) {
3013 HasLoadStoreDependenceInvolvingLoopInvariantAddress = true;
3014 } else {
3015 assert(isa<StoreInst>(Src) && isa<StoreInst>(Dst) &&
3016 "Expected both to be stores");
3017 HasStoreStoreDependenceInvolvingLoopInvariantAddress = true;
3018 }
3019 }
3020 }
3021
3022 if (HasConvergentOp) {
3023 recordAnalysis(RemarkName: "CantInsertRuntimeCheckWithConvergent")
3024 << "cannot add control dependency to convergent operation";
3025 LLVM_DEBUG(dbgs() << "LAA: We can't vectorize because a runtime check "
3026 "would be needed with a convergent operation\n");
3027 return false;
3028 }
3029
3030 if (DepsAreSafe) {
3031 LLVM_DEBUG(
3032 dbgs() << "LAA: No unsafe dependent memory operations in loop. We"
3033 << (PtrRtChecking->Need ? "" : " don't")
3034 << " need runtime memory checks.\n");
3035 return true;
3036 }
3037
3038 emitUnsafeDependenceRemark();
3039 return false;
3040}
3041
3042void LoopAccessInfo::emitUnsafeDependenceRemark() {
3043 const auto *Deps = getDepChecker().getDependences();
3044 if (!Deps)
3045 return;
3046 const auto *Found =
3047 llvm::find_if(Range: *Deps, P: [](const MemoryDepChecker::Dependence &D) {
3048 return MemoryDepChecker::Dependence::isSafeForVectorization(Type: D.Type) !=
3049 MemoryDepChecker::VectorizationSafetyStatus::Safe;
3050 });
3051 if (Found == Deps->end())
3052 return;
3053 MemoryDepChecker::Dependence Dep = *Found;
3054
3055 LLVM_DEBUG(dbgs() << "LAA: unsafe dependent memory operations in loop\n");
3056
3057 // Emit remark for first unsafe dependence
3058 bool HasForcedDistribution =
3059 getBooleanLoopAttribute(TheLoop, Name: "llvm.loop.distribute.enable");
3060
3061 const std::string Info =
3062 HasForcedDistribution
3063 ? "unsafe dependent memory operations in loop."
3064 : "unsafe dependent memory operations in loop. Use "
3065 "#pragma clang loop distribute(enable) to allow loop distribution "
3066 "to attempt to isolate the offending operations into a separate "
3067 "loop";
3068 OptimizationRemarkAnalysis &R =
3069 recordAnalysis(RemarkName: "UnsafeDep", Instr: Dep.getDestination(DepChecker: getDepChecker())) << Info;
3070
3071 switch (Dep.Type) {
3072 case MemoryDepChecker::Dependence::NoDep:
3073 case MemoryDepChecker::Dependence::Forward:
3074 case MemoryDepChecker::Dependence::BackwardVectorizable:
3075 llvm_unreachable("Unexpected dependence");
3076 case MemoryDepChecker::Dependence::Backward:
3077 R << "\nBackward loop carried data dependence.";
3078 break;
3079 case MemoryDepChecker::Dependence::ForwardButPreventsForwarding:
3080 R << "\nForward loop carried data dependence that prevents "
3081 "store-to-load forwarding.";
3082 break;
3083 case MemoryDepChecker::Dependence::BackwardVectorizableButPreventsForwarding:
3084 R << "\nBackward loop carried data dependence that prevents "
3085 "store-to-load forwarding.";
3086 break;
3087 case MemoryDepChecker::Dependence::IndirectUnsafe:
3088 R << "\nUnsafe indirect dependence.";
3089 break;
3090 case MemoryDepChecker::Dependence::InvariantUnsafe:
3091 R << "\nUnsafe dependence on loop-invariant address.";
3092 break;
3093 case MemoryDepChecker::Dependence::Unknown:
3094 R << "\nUnknown data dependence.";
3095 break;
3096 }
3097
3098 if (Instruction *I = Dep.getSource(DepChecker: getDepChecker())) {
3099 DebugLoc SourceLoc = I->getDebugLoc();
3100 if (auto *DD = dyn_cast_or_null<Instruction>(Val: getPointerOperand(V: I)))
3101 SourceLoc = DD->getDebugLoc();
3102 if (SourceLoc)
3103 R << " Memory location is the same as accessed at "
3104 << ore::NV("Location", SourceLoc);
3105 }
3106}
3107
3108bool LoopAccessInfo::blockNeedsPredication(const BasicBlock *BB,
3109 const Loop *TheLoop,
3110 const DominatorTree *DT) {
3111 assert(TheLoop->contains(BB) && "Unknown block used");
3112
3113 // Blocks that do not dominate the latch need predication.
3114 const BasicBlock *Latch = TheLoop->getLoopLatch();
3115 assert(Latch && "Loop expected to have a single latch.");
3116 return !DT->dominates(A: BB, B: Latch);
3117}
3118
3119OptimizationRemarkAnalysis &
3120LoopAccessInfo::recordAnalysis(StringRef RemarkName, const Instruction *I) {
3121 assert(!Report && "Multiple reports generated");
3122
3123 const BasicBlock *CodeRegion = TheLoop->getHeader();
3124 DebugLoc DL = TheLoop->getStartLoc();
3125
3126 if (I) {
3127 CodeRegion = I->getParent();
3128 // If there is no debug location attached to the instruction, revert back to
3129 // using the loop's.
3130 if (I->getDebugLoc())
3131 DL = I->getDebugLoc();
3132 }
3133
3134 Report = std::make_unique<OptimizationRemarkAnalysis>(DEBUG_TYPE, args&: RemarkName,
3135 args&: DL, args&: CodeRegion);
3136 return *Report;
3137}
3138
3139bool LoopAccessInfo::isInvariant(Value *V) const {
3140 auto *SE = PSE->getSE();
3141 if (TheLoop->isLoopInvariant(V))
3142 return true;
3143 if (!SE->isSCEVable(Ty: V->getType()))
3144 return false;
3145 const SCEV *S = SE->getSCEV(V);
3146 return SE->isLoopInvariant(S, L: TheLoop);
3147}
3148
3149/// If \p Ptr is a GEP, which has a loop-variant operand, return that operand.
3150/// Otherwise, return \p Ptr.
3151static Value *getLoopVariantGEPOperand(Value *Ptr, ScalarEvolution *SE,
3152 Loop *Lp) {
3153 auto *GEP = dyn_cast<GetElementPtrInst>(Val: Ptr);
3154 if (!GEP)
3155 return Ptr;
3156
3157 Value *V = Ptr;
3158 for (const Use &U : GEP->operands()) {
3159 if (!SE->isLoopInvariant(S: SE->getSCEV(V: U), L: Lp)) {
3160 if (V == Ptr)
3161 V = U;
3162 else
3163 // There must be exactly one loop-variant operand.
3164 return Ptr;
3165 }
3166 }
3167 return V;
3168}
3169
3170/// Get the stride of a pointer access in a loop. Looks for symbolic
3171/// strides "a[i*stride]". Returns the symbolic stride, or null otherwise.
3172static const SCEV *getStrideFromPointer(Value *Ptr, ScalarEvolution *SE, Loop *Lp) {
3173 auto *PtrTy = dyn_cast<PointerType>(Val: Ptr->getType());
3174 if (!PtrTy)
3175 return nullptr;
3176
3177 // Try to remove a gep instruction to make the pointer (actually index at this
3178 // point) easier analyzable. If OrigPtr is equal to Ptr we are analyzing the
3179 // pointer, otherwise, we are analyzing the index.
3180 Value *OrigPtr = Ptr;
3181
3182 Ptr = getLoopVariantGEPOperand(Ptr, SE, Lp);
3183 const SCEV *V = SE->getSCEV(V: Ptr);
3184
3185 if (Ptr != OrigPtr)
3186 // Strip off casts.
3187 while (auto *C = dyn_cast<SCEVIntegralCastExpr>(Val: V))
3188 V = C->getOperand();
3189
3190 if (!match(S: V, P: m_scev_AffineAddRec(Op0: m_SCEV(), Op1: m_SCEV(V), L: m_SpecificLoop(L: Lp))))
3191 return nullptr;
3192
3193 // Note that the restriction after this loop invariant check are only
3194 // profitability restrictions.
3195 if (!SE->isLoopInvariant(S: V, L: Lp))
3196 return nullptr;
3197
3198 // Look for the loop invariant symbolic value.
3199 if (isa<SCEVUnknown>(Val: V))
3200 return V;
3201
3202 // Look through multiplies that scale a stride by a constant.
3203 match(S: V, P: m_scev_Mul(Op0: m_SCEVConstant(), Op1: m_SCEV(V)));
3204 if (auto *C = dyn_cast<SCEVIntegralCastExpr>(Val: V))
3205 if (isa<SCEVUnknown>(Val: C->getOperand()))
3206 return V;
3207
3208 return nullptr;
3209}
3210
3211void LoopAccessInfo::collectStridedAccess(Value *MemAccess) {
3212 Value *Ptr = getLoadStorePointerOperand(V: MemAccess);
3213 if (!Ptr)
3214 return;
3215
3216 // Note: getStrideFromPointer is a *profitability* heuristic. We
3217 // could broaden the scope of values returned here - to anything
3218 // which happens to be loop invariant and contributes to the
3219 // computation of an interesting IV - but we chose not to as we
3220 // don't have a cost model here, and broadening the scope exposes
3221 // far too many unprofitable cases.
3222 const SCEV *StrideExpr = getStrideFromPointer(Ptr, SE: PSE->getSE(), Lp: TheLoop);
3223 if (!StrideExpr)
3224 return;
3225
3226 if (match(S: StrideExpr, P: m_scev_UndefOrPoison()))
3227 return;
3228
3229 LLVM_DEBUG(dbgs() << "LAA: Found a strided access that is a candidate for "
3230 "versioning:");
3231 LLVM_DEBUG(dbgs() << " Ptr: " << *Ptr << " Stride: " << *StrideExpr << "\n");
3232
3233 if (!SpeculateUnitStride) {
3234 LLVM_DEBUG(dbgs() << " Chose not to due to -laa-speculate-unit-stride\n");
3235 return;
3236 }
3237
3238 // Avoid adding the "Stride == 1" predicate when we know that
3239 // Stride >= Trip-Count. Such a predicate will effectively optimize a single
3240 // or zero iteration loop, as Trip-Count <= Stride == 1.
3241 //
3242 // TODO: We are currently not making a very informed decision on when it is
3243 // beneficial to apply stride versioning. It might make more sense that the
3244 // users of this analysis (such as the vectorizer) will trigger it, based on
3245 // their specific cost considerations; For example, in cases where stride
3246 // versioning does not help resolving memory accesses/dependences, the
3247 // vectorizer should evaluate the cost of the runtime test, and the benefit
3248 // of various possible stride specializations, considering the alternatives
3249 // of using gather/scatters (if available).
3250
3251 const SCEV *MaxBTC = PSE->getSymbolicMaxBackedgeTakenCount();
3252
3253 // Match the types so we can compare the stride and the MaxBTC.
3254 // The Stride can be positive/negative, so we sign extend Stride;
3255 // The backedgeTakenCount is non-negative, so we zero extend MaxBTC.
3256 const DataLayout &DL = TheLoop->getHeader()->getDataLayout();
3257 uint64_t StrideTypeSizeBits = DL.getTypeSizeInBits(Ty: StrideExpr->getType());
3258 uint64_t BETypeSizeBits = DL.getTypeSizeInBits(Ty: MaxBTC->getType());
3259 const SCEV *CastedStride = StrideExpr;
3260 const SCEV *CastedBECount = MaxBTC;
3261 ScalarEvolution *SE = PSE->getSE();
3262 if (BETypeSizeBits >= StrideTypeSizeBits)
3263 CastedStride = SE->getNoopOrSignExtend(V: StrideExpr, Ty: MaxBTC->getType());
3264 else
3265 CastedBECount = SE->getZeroExtendExpr(Op: MaxBTC, Ty: StrideExpr->getType());
3266 const SCEV *StrideMinusBETaken = SE->getMinusSCEV(LHS: CastedStride, RHS: CastedBECount);
3267 // Since TripCount == BackEdgeTakenCount + 1, checking:
3268 // "Stride >= TripCount" is equivalent to checking:
3269 // Stride - MaxBTC> 0
3270 if (SE->isKnownPositive(S: StrideMinusBETaken)) {
3271 LLVM_DEBUG(
3272 dbgs() << "LAA: Stride>=TripCount; No point in versioning as the "
3273 "Stride==1 predicate will imply that the loop executes "
3274 "at most once.\n");
3275 return;
3276 }
3277 LLVM_DEBUG(dbgs() << "LAA: Found a strided access that we can version.\n");
3278
3279 // Strip back off the integer cast, and check that our result is a
3280 // SCEVUnknown as we expect.
3281 const SCEV *StrideBase = StrideExpr;
3282 if (const auto *C = dyn_cast<SCEVIntegralCastExpr>(Val: StrideBase))
3283 StrideBase = C->getOperand();
3284 assert(SE->isLoopInvariant(StrideBase, TheLoop) &&
3285 "users of the map rely on the stride being loop invariant");
3286 SymbolicStrides[Ptr] = cast<SCEVUnknown>(Val: StrideBase);
3287}
3288
3289LoopAccessInfo::LoopAccessInfo(Loop *L, ScalarEvolution *SE,
3290 const TargetTransformInfo *TTI,
3291 const TargetLibraryInfo *TLI, AAResults *AA,
3292 DominatorTree *DT, LoopInfo *LI,
3293 AssumptionCache *AC, bool AllowPartial)
3294 : PSE(std::make_unique<PredicatedScalarEvolution>(args&: *SE, args&: *L)),
3295 PtrRtChecking(nullptr), TheLoop(L), AllowPartial(AllowPartial) {
3296 unsigned MaxTargetVectorWidthInBits = std::numeric_limits<unsigned>::max();
3297 if (TTI && !TTI->enableScalableVectorization())
3298 // Scale the vector width by 2 as rough estimate to also consider
3299 // interleaving.
3300 MaxTargetVectorWidthInBits =
3301 TTI->getRegisterBitWidth(K: TargetTransformInfo::RGK_FixedWidthVector) * 2;
3302
3303 DepChecker = std::make_unique<MemoryDepChecker>(
3304 args&: *PSE, args&: AC, args&: DT, args&: L, args&: SymbolicStrides, args&: MaxTargetVectorWidthInBits, args&: LoopGuards);
3305 PtrRtChecking =
3306 std::make_unique<RuntimePointerChecking>(args&: *DepChecker, args&: SE, args&: LoopGuards);
3307 if (canAnalyzeLoop())
3308 CanVecMem = analyzeLoop(AA, LI, TLI, DT);
3309}
3310
3311void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const {
3312 if (CanVecMem) {
3313 OS.indent(NumSpaces: Depth) << "Memory dependences are safe";
3314 const MemoryDepChecker &DC = getDepChecker();
3315 if (!DC.isSafeForAnyVectorWidth())
3316 OS << " with a maximum safe vector width of "
3317 << DC.getMaxSafeVectorWidthInBits() << " bits";
3318 if (!DC.isSafeForAnyStoreLoadForwardDistances()) {
3319 uint64_t SLDist = DC.getStoreLoadForwardSafeDistanceInBits();
3320 OS << ", with a maximum safe store-load forward width of " << SLDist
3321 << " bits";
3322 }
3323 if (PtrRtChecking->Need)
3324 OS << " with run-time checks";
3325 OS << "\n";
3326 }
3327
3328 if (HasConvergentOp)
3329 OS.indent(NumSpaces: Depth) << "Has convergent operation in loop\n";
3330
3331 if (Report)
3332 OS.indent(NumSpaces: Depth) << "Report: " << Report->getMsg() << "\n";
3333
3334 if (auto *Dependences = DepChecker->getDependences()) {
3335 OS.indent(NumSpaces: Depth) << "Dependences:\n";
3336 for (const auto &Dep : *Dependences) {
3337 Dep.print(OS, Depth: Depth + 2, Instrs: DepChecker->getMemoryInstructions());
3338 OS << "\n";
3339 }
3340 } else
3341 OS.indent(NumSpaces: Depth) << "Too many dependences, not recorded\n";
3342
3343 // List the pair of accesses need run-time checks to prove independence.
3344 PtrRtChecking->print(OS, Depth);
3345 if (PtrRtChecking->Need && !HasCompletePtrRtChecking)
3346 OS.indent(NumSpaces: Depth) << "Generated run-time checks are incomplete\n";
3347 OS << "\n";
3348
3349 OS.indent(NumSpaces: Depth)
3350 << "Non vectorizable stores to invariant address were "
3351 << (HasStoreStoreDependenceInvolvingLoopInvariantAddress ||
3352 HasLoadStoreDependenceInvolvingLoopInvariantAddress
3353 ? ""
3354 : "not ")
3355 << "found in loop.\n";
3356
3357 OS.indent(NumSpaces: Depth) << "SCEV assumptions:\n";
3358 PSE->getPredicate().print(OS, Depth);
3359
3360 OS << "\n";
3361
3362 OS.indent(NumSpaces: Depth) << "Expressions re-written:\n";
3363 PSE->print(OS, Depth);
3364}
3365
3366const LoopAccessInfo &LoopAccessInfoManager::getInfo(Loop &L,
3367 bool AllowPartial) {
3368 const auto &[It, Inserted] = LoopAccessInfoMap.try_emplace(Key: &L);
3369
3370 // We need to create the LoopAccessInfo if either we don't already have one,
3371 // or if it was created with a different value of AllowPartial.
3372 if (Inserted || It->second->hasAllowPartial() != AllowPartial)
3373 It->second = std::make_unique<LoopAccessInfo>(args: &L, args: &SE, args&: TTI, args&: TLI, args: &AA, args: &DT,
3374 args: &LI, args&: AC, args&: AllowPartial);
3375
3376 return *It->second;
3377}
3378void LoopAccessInfoManager::clear() {
3379 // Collect LoopAccessInfo entries that may keep references to IR outside the
3380 // analyzed loop or SCEVs that may have been modified or invalidated. At the
3381 // moment, that is loops requiring memory or SCEV runtime checks, as those cache
3382 // SCEVs, e.g. for pointer expressions.
3383 LoopAccessInfoMap.remove_if(Pred: [](const auto &Entry) {
3384 const auto &LAI = Entry.second;
3385 return !(LAI->getRuntimePointerChecking()->getChecks().empty() &&
3386 LAI->getPSE().getPredicate().isAlwaysTrue());
3387 });
3388}
3389
3390bool LoopAccessInfoManager::invalidate(
3391 Function &F, const PreservedAnalyses &PA,
3392 FunctionAnalysisManager::Invalidator &Inv) {
3393 // Check whether our analysis is preserved.
3394 auto PAC = PA.getChecker<LoopAccessAnalysis>();
3395 if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Function>>())
3396 // If not, give up now.
3397 return true;
3398
3399 // Check whether the analyses we depend on became invalid for any reason.
3400 // Skip checking TargetLibraryAnalysis as it is immutable and can't become
3401 // invalid.
3402 return Inv.invalidate<AAManager>(IR&: F, PA) ||
3403 Inv.invalidate<ScalarEvolutionAnalysis>(IR&: F, PA) ||
3404 Inv.invalidate<LoopAnalysis>(IR&: F, PA) ||
3405 Inv.invalidate<DominatorTreeAnalysis>(IR&: F, PA);
3406}
3407
3408LoopAccessInfoManager LoopAccessAnalysis::run(Function &F,
3409 FunctionAnalysisManager &FAM) {
3410 auto &SE = FAM.getResult<ScalarEvolutionAnalysis>(IR&: F);
3411 auto &AA = FAM.getResult<AAManager>(IR&: F);
3412 auto &DT = FAM.getResult<DominatorTreeAnalysis>(IR&: F);
3413 auto &LI = FAM.getResult<LoopAnalysis>(IR&: F);
3414 auto &TTI = FAM.getResult<TargetIRAnalysis>(IR&: F);
3415 auto &TLI = FAM.getResult<TargetLibraryAnalysis>(IR&: F);
3416 auto &AC = FAM.getResult<AssumptionAnalysis>(IR&: F);
3417 return LoopAccessInfoManager(SE, AA, DT, LI, &TTI, &TLI, &AC);
3418}
3419
3420AnalysisKey LoopAccessAnalysis::Key;
3421