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