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