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