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