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