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