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