76#define DEBUG_TYPE "loop-accesses"
80 cl::desc(
"Sets the SIMD width. Zero is autoselect."),
86 cl::desc(
"Sets the vectorization interleave count. "
87 "Zero is autoselect."),
94 cl::desc(
"When performing memory disambiguation checks at runtime do not "
95 "generate more than this number of comparisons (default = 8)."),
100 "vectorize-memory-check-threshold",
cl::Hidden,
101 cl::desc(
"The maximum allowed number of runtime memory checks"),
112 "Hoist inner loop runtime memory checks to outer loop if possible"),
117 return ::VectorizationInterleave.getNumOccurrences() > 0;
145 LLVM_DEBUG(
dbgs() <<
"LAA: Replacing SCEV: " << *OrigSCEV <<
" by: " << *Expr
152 :
High(RtCheck.Pointers[Index].
End),
Low(RtCheck.Pointers[Index].Start),
190 bool CheckForNonNull;
191 Value *StartPtrV = StartPtr->getValue();
195 DL, CheckForNonNull,
nullptr);
199 if (DerefBytes && CheckForNonNull)
207 Instruction *CtxI = &*L->getHeader()->getFirstNonPHIIt();
208 if (
BasicBlock *LoopPred = L->getLoopPredecessor()) {
210 CtxI = LoopPred->getTerminator();
213 StartPtrV, Attribute::Dereferenceable, *AC,
222 DerefBytesSCEV = SE.
getUMaxExpr(DerefBytesSCEV, DerefRKSCEV);
227 if (DerefBytesSCEV->
isZero())
241 const SCEV *StartOffset =
252 if (!DistToLastIter) {
267 const SCEV *MaxOffset;
268 if (IsKnownNonNegative) {
286 MaxOffset = StartOffset;
308 assert(AR->getLoop() == L &&
309 "trying to check for AddRec in different loop");
316 if (!NAry->hasNoUnsignedWrap())
321 return isKnownNonDecreasingInLoop(Op, L, SE);
338static std::pair<const SCEV *, const SCEV *>
342 if (!PtrAdd || !PtrAdd->hasNoUnsignedWrap())
343 return {
nullptr,
nullptr};
346 return Op->getType()->isPointerTy();
349 return {
nullptr,
nullptr};
354 return {
nullptr,
nullptr};
360 return {
nullptr,
nullptr};
369 DenseMap<std::pair<const SCEV *, const SCEV *>,
383 const Loop *Lp,
const SCEV *PtrExpr,
const SCEV *EltSizeSCEV,
385 DenseMap<std::pair<const SCEV *, const SCEV *>,
389 std::pair<const SCEV *, const SCEV *> *PtrBoundsPair;
392 {{PtrExpr, EltSizeSCEV},
396 PtrBoundsPair = &Iter->second;
409 assert(AR->getLoop() == Lp &&
"LoopGuards must be the guards of Lp");
410 const SCEV *Step = AR->getStepRecurrence(*SE);
413 const SCEV *LastAddr =
nullptr;
419 LastAddr = AR->evaluateAtIteration(BTC, *SE);
421 AR, MaxBTC, EltSizeSCEV, *SE,
DL, DT, AC, LoopGuards)) {
422 LastAddr = AR->evaluateAtIteration(MaxBTC, *SE);
424 const SCEV *Start = AR->getStart();
425 Type *PtrTy = AR->getType();
441 ScEnd = SE->
getAddExpr(LastAddr, EltSizeSCEV);
457 std::tie(ScStart, ScEnd) =
466 std::pair<const SCEV *, const SCEV *> Res = {ScStart, ScEnd};
468 *PtrBoundsPair = Res;
476 LoopGuards(LoopGuards) {}
481 Type *AccessTy,
bool WritePtr,
482 unsigned DepSetId,
unsigned ASId,
484 bool NeedsFreeze,
bool IsForked) {
488 Lp, PtrExpr, AccessTy, BTC, SymbolicMaxBTC, PSE.
getSE(),
489 &DC.getPointerBounds(), DC.getDT(), DC.getAC(), LoopGuards);
492 Pointers.emplace_back(Ptr, ScStart, ScEnd, WritePtr, DepSetId, ASId, PtrExpr,
493 NeedsFreeze, IsForked);
497bool RuntimePointerChecking::tryToCreateDiffCheck(
520 if (AccSrc.
size() != 1 || AccSink.
size() != 1)
524 if (AccSink[0] < AccSrc[0])
528 const SCEV *SrcStart;
529 const SCEV *SinkStart;
531 if (!
match(Src->Expr,
550 std::max(
DL.getTypeAllocSize(SrcTy),
DL.getTypeAllocSize(DstTy));
576 const Loop *StartARLoop = SrcStartAR->getLoop();
577 if (StartARLoop == SinkStartAR->getLoop() &&
582 SrcStartAR->getStepRecurrence(*SE) !=
583 SinkStartAR->getStepRecurrence(*SE)) {
584 LLVM_DEBUG(
dbgs() <<
"LAA: Not creating diff runtime check, since these "
585 "cannot be hoisted out of the outer loop\n");
591 <<
"SrcStart: " << *SrcStartInt <<
'\n'
592 <<
"SinkStartInt: " << *SinkStartInt <<
'\n');
593 DiffChecks.emplace_back(SrcStartInt, SinkStartInt, AllocSize,
594 Src->NeedsFreeze || Sink->NeedsFreeze);
599 SmallVector<RuntimePointerCheck, 4> Checks;
607 CanUseDiffCheck = CanUseDiffCheck && tryToCreateDiffCheck(CGI, CGJ);
608 Checks.emplace_back(&CGI, &CGJ);
617 assert(Checks.empty() &&
"Checks is not empty");
618 groupChecks(DepCands);
619 mergeStencilGroups();
625 for (
const auto &
I : M.Members)
626 for (
const auto &J :
N.Members)
639 return Diff->isNegative() ? J :
I;
646 RtCheck.
Pointers[Index].PointerValue->getType()->getPointerAddressSpace(),
647 RtCheck.
Pointers[Index].NeedsFreeze, *RtCheck.SE);
655 "all pointers in a checking group must be in the same address space");
681void RuntimePointerChecking::groupChecks(
723 unsigned TotalComparisons = 0;
726 for (
unsigned Index = 0; Index <
Pointers.size(); ++Index)
761 for (
unsigned Pointer : PositionMap.
lookup(M)) {
773 if (TotalComparisons > Opts.memory_check_merge_threshold)
778 if (Group.addPointer(Pointer, *
this)) {
788 Groups.emplace_back(Pointer, *
this);
858 std::optional<int64_t>
V =
C->getAPInt().trySExtValue();
867 std::optional<int64_t>
V =
C->getAPInt().trySExtValue();
874 return addScaledStencilTerm(Op, Mult, Depth + 1, D);
879 int64_t &Coeff =
D.Coefficients[Term];
898static std::optional<StencilDecomposition>
923static std::optional<APInt>
927 if (AbsConstant > SignedMax)
929 uint64_t Budget = SignedMax - AbsConstant;
931 for (
const auto &[Stride, Coeff] :
D.Coefficients) {
933 if (AbsCoeff > Budget - CoeffSum)
935 CoeffSum += AbsCoeff;
937 return APInt(
BitWidth, CoeffSum ? Budget / CoeffSum : SignedMax);
950 bool NeedsPositive =
false;
951 std::optional<APInt>
Max;
953 SmallMapVector<const SCEV *, Limit, 4> Limits;
956 void requireLowerLimit(
const SCEV *Stride) {
957 Limits[Stride].NeedsPositive =
true;
960 void requireUpperLimit(
const SCEV *Stride,
const APInt &Max) {
961 std::optional<APInt> &Current = Limits[Stride].Max;
962 if (!Current ||
Max.ult(*Current))
967 void addFrom(
const StrideLimits &
Other) {
968 for (
const auto &[Stride, L] :
Other.Limits) {
970 requireLowerLimit(Stride);
972 requireUpperLimit(Stride, *
L.Max);
977 unsigned countNew(
const StrideLimits &Committed)
const {
978 return count_if(Limits, [&](
const auto &Entry) {
979 return !Committed.Limits.contains(
Entry.first);
984 void addPredicates(PredicatedScalarEvolution &PSE)
const {
985 ScalarEvolution &SE = *PSE.
getSE();
986 for (
const auto &[Stride, L] : Limits) {
987 if (
L.NeedsPositive) {
998 << *Stride <<
" <= " << *
L.Max <<
"\n");
1014 StrideLimits &Limits) {
1020 for (
const auto &[Stride, Coeff] :
D.Coefficients) {
1025 Limits.requireLowerLimit(Stride);
1027 Limits.requireUpperLimit(Stride, *UpperLimit);
1058 int64_t ACorner =
A.Constant, BCorner =
B.Constant;
1059 for (
const auto &[Stride, ACoeff] :
A.Coefficients) {
1060 if (ACoeff >
B.Coefficients.lookup(Stride))
1065 for (
const auto &[Stride, BCoeff] :
B.Coefficients) {
1066 if (
A.Coefficients.lookup(Stride) > BCoeff)
1071 return ACorner <= BCorner;
1091 auto Beats = [&](
unsigned A,
unsigned B) {
1098 for (
unsigned K = 0;
K < Offsets.size(); ++
K) {
1103 for (
unsigned J =
K + 1; J < Offsets.size(); ++J) {
1109 }
else if (Beats(J,
K)) {
1116 for (
unsigned K = 0;
K < Offsets.size(); ++
K)
1117 if (!Beaten.
test(
K))
1149 const StrideLimits &
Local,
const StrideLimits &Committed,
1150 unsigned NumBoundOperands) {
1151 unsigned NumGroups = GroupIndices.
size();
1152 unsigned NumExternalChecks =
1154 return any_of(GroupIndices, [&](unsigned GI) {
1155 return RtCheck.needsChecking(RtCheck.CheckingGroups[GI], G);
1159 unsigned NewPredicates =
Local.countNew(Committed);
1162 <<
", NumExternalChecks=" << NumExternalChecks
1163 <<
", predicates=" << NewPredicates
1164 <<
", bound operands=" << NumBoundOperands <<
", checks "
1165 << NumGroups * NumExternalChecks <<
"->"
1166 << NumExternalChecks + NewPredicates + NumBoundOperands
1169 return {NumGroups * NumExternalChecks,
1170 NumExternalChecks + NewPredicates + NumBoundOperands};
1180 const SCEV *MergedHigh,
1183 CandidateGroup.
Low = MergedLow;
1184 CandidateGroup.
High = MergedHigh;
1189 return CandidateGroup;
1192void RuntimePointerChecking::mergeStencilGroups() {
1244 const Loop &
L = *DC.getInnermostLoop();
1249 for (BasicBlock *BB :
L.blocks())
1250 if (BB !=
L.getHeader())
1251 for (PHINode &PN : BB->phis())
1252 if (PN.getType()->isPointerTy())
1264 <<
" groups exceeds stencil-merge-max-groups, skipping\n");
1269 unsigned TotalChecks = 0;
1279 <<
" checks <= threshold, skipping stencil merge\n");
1283 dbgs() <<
"LAA: " << TotalChecks
1284 <<
" checks > threshold, proceeding with stencil merge\n");
1293 using DepAliasKey = std::pair<unsigned, unsigned>;
1294 MapVector<DepAliasKey, SmallVector<unsigned, 4>> DepSetToGroups;
1297 DepSetToGroups[{
P.DependencySetId,
P.AliasSetId}].push_back(
I);
1300 SmallDenseSet<unsigned, 4> MergedGroupIndices;
1304 StrideLimits CommittedStrideLimits;
1306 for (
auto &[DepAliasKey, GroupIndices] : DepSetToGroups) {
1307 [[maybe_unused]]
auto [DepId, ASId] = DepAliasKey;
1308 if (GroupIndices.size() < 2)
1316 SmallVector<unsigned, 8> AllMembers;
1318 for (
unsigned GI : GroupIndices) {
1321 [&](
unsigned Idx) {
return Pointers[
Idx].IsWritePtr; })) {
1322 LLVM_DEBUG(
dbgs() <<
"LAA: Skipping DepSet(" << DepId <<
"," << ASId
1323 <<
") with write access\n");
1332 [&](
unsigned Idx) {
return Pointers[
Idx].IsForked; })) {
1333 LLVM_DEBUG(
dbgs() <<
"LAA: Skipping DepSet(" << DepId <<
"," << ASId
1334 <<
") with forked pointer\n");
1349 if (
any_of(AllMembers, [&](
unsigned Idx) {
1351 assert(!
P.IsWritePtr &&
"only read members reach this point");
1353 DC.getInstructionsForAccess(
P.PointerValue,
false),
1354 [&](Instruction *
I) {
1355 return LoopAccessInfo::blockNeedsPredication(I->getParent(), &L,
1359 LLVM_DEBUG(
dbgs() <<
"LAA: Skipping DepSet(" << DepId <<
"," << ASId
1360 <<
") with predicated access\n");
1368 unsigned Member0 = AllMembers[0];
1369 const SCEV *BaseLow =
Pointers[Member0].Start;
1370 const SCEV *BaseHigh =
Pointers[Member0].End;
1374 if (SE->getTypeSizeInBits(BaseLow->
getType()) > 64)
1377 LLVM_DEBUG(
dbgs() <<
"LAA: Analyzing DepSet(" << DepId <<
"," << ASId
1378 <<
") with " << AllMembers.
size()
1379 <<
" members, base: " << *BaseLow <<
"\n");
1381 auto GetStepForPointer = [&](
unsigned Idx) ->
const SCEV * {
1383 if (AR->getLoop() == &L)
1384 return AR->getStepRecurrence(*SE);
1388 const SCEV *BaseStep = GetStepForPointer(Member0);
1401 const SCEV *BaseRange = SE->getMinusSCEV(BaseHigh, BaseLow);
1404 "skipping DepSet\n");
1412 if (
Range == BaseRange)
1414 const SCEV *RangeDiff = SE->getMinusSCEV(
Range, BaseRange);
1418 dbgs() <<
"LAA: Member with different or not computable access "
1419 "range, skipping DepSet\n");
1431 return GetStepForPointer(Idx) != BaseStep;
1434 "skipping DepSet\n");
1445 StrideLimits LocalStrideLimits;
1450 const auto CollectOffset = [&](
unsigned Idx) ->
bool {
1451 const SCEV *LowOffset = SE->getMinusSCEV(
Pointers[Idx].Start, BaseLow);
1457 <<
" NOT decomposable: " << *LowOffset <<
"\n");
1461 SE->getTypeSizeInBits(LowOffset->
getType()), *SE,
1466 <<
": Const=" << DLow->Constant
1467 <<
", strides=" << DLow->Coefficients.size() <<
"\n");
1468 MemberOffsets.
push_back(std::move(*DLow));
1475 SmallVector<unsigned, 4> MinCandidates =
1477 SmallVector<unsigned, 4> MaxCandidates =
1480 "a non-empty member list always has a candidate");
1482 << MinCandidates.
size()
1483 <<
", max=" << MaxCandidates.
size() <<
" of "
1484 << MemberOffsets.
size() <<
"\n");
1488 unsigned NumBoundOperands =
1489 (MinCandidates.
size() - 1) + (MaxCandidates.
size() - 1);
1495 auto [ChecksBefore, ChecksAfter] =
1497 CommittedStrideLimits, NumBoundOperands);
1498 if (ChecksAfter >= ChecksBefore) {
1512 const auto BuildBound = [&](ArrayRef<unsigned> Candidates,
bool IsLow) {
1514 for (
unsigned K : Candidates) {
1516 Ops.push_back(IsLow ?
P.Start :
P.End);
1518 return IsLow ? SE->getUMinExpr(
Ops) : SE->getUMaxExpr(
Ops);
1521 const SCEV *MergedLow = BuildBound(MinCandidates,
true);
1522 const SCEV *MergedHigh = BuildBound(MaxCandidates,
false);
1525 <<
", High=" << *MergedHigh <<
"\n");
1527 << ChecksBefore - ChecksAfter <<
"\n");
1530 *
this, AllMembers, MergedLow, MergedHigh, GroupIndices));
1531 CommittedStrideLimits.addFrom(LocalStrideLimits);
1532 MergedGroupIndices.
insert(GroupIndices.begin(), GroupIndices.end());
1535 CommittedStrideLimits.addPredicates(DC.getPSE());
1538 if (!NewMergedGroups.
empty()) {
1543 FinalGroups.
append(std::make_move_iterator(NewMergedGroups.
begin()),
1544 std::make_move_iterator(NewMergedGroups.
end()));
1555 return (PtrToPartition[PtrIdx1] != -1 &&
1556 PtrToPartition[PtrIdx1] == PtrToPartition[PtrIdx2]);
1579 for (
const auto &[Idx, CG] :
enumerate(CheckingGroups))
1580 PtrIndices[&CG] = Idx;
1586 unsigned Depth)
const {
1589 for (
const auto &[Check1, Check2] : Checks) {
1590 const auto &
First = Check1->Members, &Second = Check2->Members;
1592 OS.
indent(
Depth + 2) <<
"Comparing group GRP" << PtrIndices.at(Check1)
1596 OS.
indent(
Depth + 2) <<
"Against group GRP" << PtrIndices.at(Check2)
1598 for (
unsigned K : Second)
1611 OS.
indent(
Depth + 2) <<
"Group GRP" << PtrIndices.at(&CG) <<
":\n";
1612 OS.
indent(
Depth + 4) <<
"(Low: " << *CG.Low <<
" High: " << *CG.High
1614 for (
unsigned Member : CG.Members) {
1626class AccessAnalysis {
1628 using MemAccessInfo =
1631 AccessAnalysis(
const AnalysisOptions &Opts,
const Loop *TheLoop,
1637 : Opts(Opts), TheLoop(TheLoop), EEA(DT, LI), BAA(*
AA, &EEA), AST(BAA),
1638 LI(LI), DT(DT),
TTI(
TTI), DepCands(DA), PSE(PSE),
1639 LoopAliasScopes(LoopAliasScopes) {
1641 BAA.enableCrossIterationMode();
1648 Accesses[MemAccessInfo(Ptr,
false)].insert(AccessTy);
1650 ReadOnlyPtr.insert(Ptr);
1654 void addStore(
const MemoryLocation &Loc,
Type *AccessTy) {
1657 Accesses[MemAccessInfo(Ptr,
true)].insert(AccessTy);
1667 bool createCheckForAccess(RuntimePointerChecking &RtCheck,
1670 DenseMap<Value *, unsigned> &DepSetId,
1671 Loop *TheLoop,
unsigned &RunningDepId,
1672 unsigned ASId,
bool Assume);
1683 bool canCheckPtrAtRT(RuntimePointerChecking &RtCheck,
Loop *TheLoop,
1685 Value *&UncomputablePtr,
bool AllowPartial,
1686 const MemoryDepChecker &DepChecker);
1691 void buildDependenceSets(
const MemoryDepChecker &DepChecker);
1698 bool isDependencyCheckNeeded()
const {
return !CheckDeps.empty(); }
1703 void resetDepChecks(MemoryDepChecker &DepChecker) {
1711 using PtrAccessMap = MapVector<MemAccessInfo, SmallSetVector<Type *, 1>>;
1715 MemoryLocation
adjustLoc(MemoryLocation Loc)
const {
1732 return LoopAliasScopes.contains(cast<MDNode>(Scope));
1739 const AnalysisOptions &Opts;
1746 const Loop *TheLoop;
1752 SmallPtrSet<Value*, 16> ReadOnlyPtr;
1755 EarliestEscapeAnalysis EEA;
1762 AliasSetTracker AST;
1771 const TargetTransformInfo *
TTI;
1785 bool IsRTCheckAnalysisNeeded =
false;
1788 PredicatedScalarEvolution &PSE;
1790 DenseMap<Value *, SmallVector<const Value *, 16>> UnderlyingObjects;
1794 SmallPtrSetImpl<MDNode *> &LoopAliasScopes;
1799std::optional<int64_t>
1804 LLVM_DEBUG(
dbgs() <<
"LAA: Bad stride - Scalable object: " << *AccessTy
1806 return std::nullopt;
1812 dbgs() <<
"LAA: Bad stride - Not striding over innermost loop ";
1814 dbgs() << *Ptr <<
" ";
1816 dbgs() <<
"SCEV: " << *AR <<
"\n";
1818 return std::nullopt;
1825 const APInt *APStepVal;
1828 dbgs() <<
"LAA: Bad stride - Not a constant strided ";
1830 dbgs() << *Ptr <<
" ";
1831 dbgs() <<
"SCEV: " << *AR <<
"\n";
1833 return std::nullopt;
1837 TypeSize AllocSize =
DL.getTypeAllocSize(AccessTy);
1841 return std::nullopt;
1844 std::optional<int64_t> StepVal = APStepVal->
trySExtValue();
1846 return std::nullopt;
1849 return *StepVal %
Size ? std::nullopt : std::make_optional(*StepVal /
Size);
1858 std::optional<int64_t> Stride = std::nullopt,
1870 GEP &&
GEP->hasNoUnsignedSignedWrap()) {
1873 if (L->getHeader() == L->getLoopLatch() ||
1875 if (getLoadStorePointerOperand(U) != GEP)
1877 BasicBlock *UserBB = cast<Instruction>(U)->getParent();
1878 if (!L->contains(UserBB))
1880 return !LoopAccessInfo::blockNeedsPredication(UserBB, L, &DT);
1893 (Stride == 1 || Stride == -1))
1900 if (Ptr && Predicates) {
1901 Predicates->push_back(WrapPred);
1903 <<
"LAA: Pointer: " << *Ptr <<
"\n"
1904 <<
"LAA: SCEV: " << *AR <<
"\n"
1905 <<
"LAA: Added an overflow assumption\n");
1921 while (!WorkList.
empty()) {
1923 if (!Visited.
insert(Ptr).second)
1929 if (PN && InnermostLoop.
contains(PN->getParent()) &&
1930 PN->getParent() != InnermostLoop.
getHeader()) {
1975 auto GetBinOpExpr = [&SE](
unsigned Opcode,
const SCEV *L,
1978 case Instruction::Add:
1980 case Instruction::Sub:
1988 unsigned Opcode =
I->getOpcode();
1990 case Instruction::GetElementPtr: {
1992 Type *SourceTy =
GEP->getSourceElementType();
1995 if (
I->getNumOperands() != 2 || SourceTy->
isVectorTy()) {
2005 bool NeedsFreeze =
any_of(BaseScevs, UndefPoisonCheck) ||
2006 any_of(OffsetScevs, UndefPoisonCheck);
2011 if (OffsetScevs.
size() == 2 && BaseScevs.
size() == 1)
2013 else if (BaseScevs.
size() == 2 && OffsetScevs.
size() == 1)
2016 ScevList.emplace_back(Scev, NeedsFreeze);
2027 for (
auto [
B, O] :
zip(BaseScevs, OffsetScevs)) {
2038 case Instruction::Select: {
2045 if (ChildScevs.
size() == 2)
2051 case Instruction::PHI: {
2056 if (
I->getNumOperands() == 2) {
2060 if (ChildScevs.
size() == 2)
2066 case Instruction::Add:
2067 case Instruction::Sub: {
2075 any_of(LScevs, UndefPoisonCheck) ||
any_of(RScevs, UndefPoisonCheck);
2080 if (LScevs.
size() == 2 && RScevs.
size() == 1)
2082 else if (RScevs.
size() == 2 && LScevs.
size() == 1)
2085 ScevList.emplace_back(Scev, NeedsFreeze);
2089 for (
auto [L, R] :
zip(LScevs, RScevs))
2090 ScevList.emplace_back(GetBinOpExpr(Opcode,
get<0>(L),
get<0>(R)),
2096 LLVM_DEBUG(
dbgs() <<
"ForkedPtr unhandled instruction: " << *
I <<
"\n");
2106 Loop *TheLoop,
unsigned &RunningDepId,
2107 unsigned ASId,
bool Assume) {
2114 findForkedSCEVs(SE, TheLoop, Ptr, RTCheckPtrs, Opts.max_forked_scev_depth);
2116 "Must have some runtime-check pointer candidates");
2120 auto IsLoopInvariantOrAR =
2125 if (RTCheckPtrs.
size() == 2 &&
all_of(RTCheckPtrs, IsLoopInvariantOrAR)) {
2126 LLVM_DEBUG(
dbgs() <<
"LAA: Found forked pointer: " << *Ptr <<
"\n";
2128 <<
"\t(" << Idx <<
") " << *Q.getPointer() <<
"\n");
2137 for (
auto &
P : RTCheckPtrs) {
2148 DL.getIndexType(
P.getPointer()->getType()), AccessTy);
2159 if (RTCheckPtrs.size() == 1) {
2168 if (!
isNoWrap(PSE, AR, RTCheckPtrs.size() == 1 ? Ptr :
nullptr, AccessTy,
2169 TheLoop, DT, std::nullopt,
2170 Assume ? &Predicates :
nullptr))
2178 unsigned NumPointers = RtCheck.
Pointers.size();
2179 for (
const auto &[PtrExpr, NeedsFreeze] : RTCheckPtrs) {
2185 unsigned &LeaderId = DepSetId[Leader];
2187 LeaderId = RunningDepId++;
2191 DepId = RunningDepId++;
2193 bool IsWrite =
Access.getInt();
2194 if (!RtCheck.
insert(TheLoop, Ptr, PtrExpr, AccessTy, IsWrite, DepId, ASId,
2196 RTCheckPtrs.size() > 1)) {
2197 RtCheck.
Pointers.truncate(NumPointers);
2200 LLVM_DEBUG(
dbgs() <<
"LAA: Found a runtime check ptr:" << *Ptr <<
'\n');
2210 return DL.getPointerSizeInBits(AS) ==
DL.getAddressSizeInBits(AS) &&
2211 !
DL.hasUnstableRepresentation(AS) && !
DL.hasExternalState(AS);
2220 return AS0 == AS1 ||
2221 (
TTI &&
TTI->isNoopAddrSpaceCast(AS0, AS1) &&
2222 TTI->isNoopAddrSpaceCast(AS1, AS0) &&
2225 DL.getPointerSizeInBits(AS0) ==
DL.getPointerSizeInBits(AS1));
2231 Value *&UncomputablePtr,
bool AllowPartial,
2235 bool CanDoRT =
true;
2237 bool MayNeedRTCheck =
false;
2238 if (!IsRTCheckAnalysisNeeded)
return true;
2246 for (
const auto &Dep : *Deps) {
2250 "Should only skip safe dependences");
2255 MemAccessInfo Src = DepChecker.
getAccess(Dep.Source);
2256 [[maybe_unused]] MemAccessInfo Dst =
2259 "Dependences must be between accesses in the same class");
2270 for (
const auto &AS : AST) {
2271 int NumReadPtrChecks = 0;
2272 int NumWritePtrChecks = 0;
2273 bool CanDoAliasSetRT =
true;
2275 auto ASPointers = AS.getPointers();
2279 unsigned RunningDepId = 1;
2287 for (
const Value *ConstPtr : ASPointers) {
2289 bool IsWrite =
Accesses.contains(MemAccessInfo(Ptr,
true));
2291 ++NumWritePtrChecks;
2299 if (NumWritePtrChecks == 0 ||
2300 (NumWritePtrChecks == 1 && NumReadPtrChecks == 0)) {
2301 assert((ASPointers.size() <= 1 ||
2303 [
this](
const Value *Ptr) {
2304 MemAccessInfo AccessWrite(
const_cast<Value *
>(Ptr),
2306 return !DepCands.
contains(AccessWrite);
2308 "Can only skip updating CanDoRT below, if all entries in AS "
2309 "are reads or there is at most 1 entry");
2314 auto StoreSize = [&
DL](
Type *Ty) {
return DL.getTypeStoreSize(Ty); };
2316 for (
auto &
Access : AccessInfos) {
2321 auto ReadIt =
Accesses.find(MemAccessInfo(
Access.getPointer(),
false));
2327 for (
bool Scalable : {
false,
true}) {
2328 auto HasMatchingSizeKind = [&](
Type *Ty) {
2329 return StoreSize(Ty).isScalable() == Scalable;
2339 if (!createCheckForAccess(RtCheck,
Access, AccessTy, StridesMap,
2340 DepSetId, TheLoop, RunningDepId, ASId,
2343 << *
Access.getPointer() <<
'\n');
2345 CanDoAliasSetRT =
false;
2359 bool NeedsAliasSetRTCheck = RunningDepId > 2 || !Retries.
empty();
2363 if (NeedsAliasSetRTCheck && !CanDoAliasSetRT) {
2367 CanDoAliasSetRT =
true;
2368 for (
const auto &[
Access, AccessTy] : Retries) {
2369 if (!createCheckForAccess(RtCheck,
Access, AccessTy, StridesMap,
2370 DepSetId, TheLoop, RunningDepId, ASId,
2372 CanDoAliasSetRT =
false;
2373 UncomputablePtr =
Access.getPointer();
2380 CanDoRT &= CanDoAliasSetRT;
2381 MayNeedRTCheck |= NeedsAliasSetRTCheck;
2388 unsigned NumPointers = RtCheck.
Pointers.size();
2389 for (
unsigned i = 0; i < NumPointers; ++i) {
2390 for (
unsigned j = i + 1;
j < NumPointers; ++
j) {
2392 if (RtCheck.
Pointers[i].DependencySetId ==
2393 RtCheck.
Pointers[j].DependencySetId)
2406 dbgs() <<
"LAA: Runtime check would require comparison between"
2407 " address spaces that cannot be compared\n");
2413 if (MayNeedRTCheck && (CanDoRT || AllowPartial))
2417 <<
" pointer comparisons.\n");
2424 bool CanDoRTIfNeeded = !RtCheck.
Need || CanDoRT;
2425 assert(CanDoRTIfNeeded == (CanDoRT || !MayNeedRTCheck) &&
2426 "CanDoRTIfNeeded depends on RtCheck.Need");
2427 if (!CanDoRTIfNeeded && !AllowPartial)
2429 return CanDoRTIfNeeded;
2432void AccessAnalysis::buildDependenceSets(
const MemoryDepChecker &DepChecker) {
2442 dbgs() <<
"\t" << *
A.getPointer() <<
" ("
2445 : (ReadOnlyPtr.contains(
A.getPointer()) ?
"read-only"
2454 auto HasPredicatedStores = [&](
Value *Ptr) {
2456 if (Stores.size() < 2 || SE.isLoopInvariant(SE.getSCEV(Ptr), TheLoop))
2468 for (
const auto &AS : AST) {
2469 bool AliasSetHasWrite =
false;
2473 using UnderlyingObjToAccessMap =
2475 UnderlyingObjToAccessMap ObjToLastAccess;
2478 PtrAccessMap DeferredAccesses;
2483 auto ProcessAccesses = [&](
bool UseDeferred) {
2484 PtrAccessMap &S = UseDeferred ? DeferredAccesses :
Accesses;
2489 for (
const Value *ConstPtr : AS.getPointers()) {
2494 for (
auto [AccessPtr, IsWrite] : S.keys()) {
2495 if (AccessPtr != Ptr)
2500 bool IsReadOnlyPtr = ReadOnlyPtr.contains(Ptr) && !IsWrite;
2501 if (UseDeferred && !IsReadOnlyPtr)
2505 assert(((IsReadOnlyPtr && UseDeferred) || IsWrite ||
2506 S.contains(MemAccessInfo(Ptr,
false))) &&
2507 "Alias-set pointer not in the access set?");
2509 MemAccessInfo
Access(Ptr, IsWrite);
2517 if (!UseDeferred && IsReadOnlyPtr) {
2520 DeferredAccesses.insert({
Access, {}});
2528 if (((IsWrite || IsReadOnlyPtr) && AliasSetHasWrite) ||
2529 (IsWrite && HasPredicatedStores(Ptr))) {
2530 CheckDeps.push_back(
Access);
2531 IsRTCheckAnalysisNeeded =
true;
2535 AliasSetHasWrite =
true;
2543 <<
"Underlying objects for pointer " << *Ptr <<
"\n");
2544 for (
const Value *UnderlyingObj : UOs) {
2553 auto [It,
Inserted] = ObjToLastAccess.try_emplace(
2568 ProcessAccesses(
false);
2569 ProcessAccesses(
true);
2574std::optional<int64_t>
2579 const SCEV *PtrScev =
2587 if (Predicates && !AR) {
2593 LLVM_DEBUG(
dbgs() <<
"LAA: Bad stride - Not an AddRecExpr pointer " << *Ptr
2594 <<
" SCEV: " << *PtrScev <<
"\n");
2595 return std::nullopt;
2598 std::optional<int64_t> Stride =
2600 if (!ShouldCheckWrap || !Stride)
2603 if (
isNoWrap(PSE, AR, Ptr, AccessTy, Lp, DT, Stride, Predicates))
2607 dbgs() <<
"LAA: Bad stride - Pointer may wrap in the address space "
2608 << *Ptr <<
" SCEV: " << *AR <<
"\n");
2609 return std::nullopt;
2617 assert(PtrA && PtrB &&
"Expected non-nullptr pointers.");
2625 return std::nullopt;
2632 return std::nullopt;
2633 unsigned IdxWidth =
DL.getIndexSizeInBits(ASA);
2635 APInt OffsetA(IdxWidth, 0), OffsetB(IdxWidth, 0);
2641 std::optional<int64_t> Val;
2642 if (PtrA1 == PtrB1) {
2649 return std::nullopt;
2651 IdxWidth =
DL.getIndexSizeInBits(ASA);
2652 OffsetA = OffsetA.sextOrTrunc(IdxWidth);
2661 std::optional<APInt> Diff =
2664 return std::nullopt;
2665 Val = Diff->trySExtValue();
2669 return std::nullopt;
2671 int64_t
Size =
DL.getTypeStoreSize(ElemTyA);
2672 int64_t Dist = *Val /
Size;
2676 if (!StrictCheck || Dist *
Size == Val)
2678 return std::nullopt;
2685 VL, [](
const Value *V) {
return V->getType()->isPointerTy(); }) &&
2686 "Expected list of pointer operands.");
2689 Value *Ptr0 = VL[0];
2691 using DistOrdPair = std::pair<int64_t, unsigned>;
2693 std::set<DistOrdPair,
decltype(Compare)> Offsets(Compare);
2694 Offsets.emplace(0, 0);
2695 bool IsConsecutive =
true;
2697 std::optional<int64_t> Diff =
2705 auto [It, IsInserted] = Offsets.emplace(
Offset, Idx);
2709 IsConsecutive &= std::next(It) == Offsets.end();
2711 SortedIndices.
clear();
2712 if (!IsConsecutive) {
2716 SortedIndices[Idx] =
Off.second;
2730 std::optional<int64_t> Diff =
2740 unsigned MaxTargetVectorWidthInBits,
2743 SymbolicStrides(SymbolicStrides),
2744 MaxTargetVectorWidthInBits(MaxTargetVectorWidthInBits),
2745 LoopGuards(LoopGuards) {}
2750 Accesses[MemAccessInfo(Ptr, true)].push_back(AccessIdx);
2751 InstMap.push_back(SI);
2752 AccessLocs.emplace_back(Ptr, true);
2759 [
this, LI](
Value *Ptr) {
2760 Accesses[MemAccessInfo(Ptr, false)].push_back(AccessIdx);
2761 InstMap.push_back(LI);
2762 AccessLocs.emplace_back(Ptr, false);
2828bool MemoryDepChecker::couldPreventStoreLoadForward(uint64_t Distance,
2829 uint64_t TypeByteSize,
2830 unsigned CommonStride) {
2842 uint64_t MaxVFWithoutSLForwardIssuesPowerOf2 =
2844 MaxStoreLoadForwardSafeDistanceInBits);
2848 for (uint64_t VF = 2 * TypeByteSize;
2849 VF <= MaxVFWithoutSLForwardIssuesPowerOf2; VF *= 2) {
2851 MaxVFWithoutSLForwardIssuesPowerOf2 = (VF >> 1);
2856 if (MaxVFWithoutSLForwardIssuesPowerOf2 < 2 * TypeByteSize) {
2858 dbgs() <<
"LAA: Distance " << Distance
2859 <<
" that could cause a store-load forwarding conflict\n");
2864 MaxVFWithoutSLForwardIssuesPowerOf2 <
2865 MaxStoreLoadForwardSafeDistanceInBits &&
2866 MaxVFWithoutSLForwardIssuesPowerOf2 !=
2869 bit_floor(MaxVFWithoutSLForwardIssuesPowerOf2 / CommonStride);
2870 uint64_t MaxVFInBits = MaxVF * TypeByteSize * 8;
2871 MaxStoreLoadForwardSafeDistanceInBits =
2872 std::min(MaxStoreLoadForwardSafeDistanceInBits, MaxVFInBits);
2876 dbgs() <<
"LAA: strided access with Distance " << Distance
2877 <<
" that could cause a store-load forwarding conflict\n");
2929 const SCEV *CastedProduct =
2952 assert(Stride > 1 &&
"The stride must be greater than 1");
2953 assert(TypeByteSize > 0 &&
"The type size in byte must be non-zero");
2954 assert(Distance > 0 &&
"The distance must be non-zero");
2957 if (Distance % TypeByteSize)
2976 return Distance % Stride;
2979bool MemoryDepChecker::areAccessesCompletelyBeforeOrAfter(
const SCEV *Src,
2983 const SCEV *BTC = PSE.getBackedgeTakenCount();
2984 const SCEV *SymbolicMaxBTC = PSE.getSymbolicMaxBackedgeTakenCount();
2985 ScalarEvolution &SE = *PSE.getSE();
2986 const auto &[SrcStart_, SrcEnd_] =
2988 &SE, &PointerBounds, DT, AC, LoopGuards);
2992 const auto &[SinkStart_, SinkEnd_] =
2994 &SE, &PointerBounds, DT, AC, LoopGuards);
3010 MemoryDepChecker::DepDistanceStrideAndSizeInfo>
3011MemoryDepChecker::getDependenceDistanceStrideAndSize(
3012 const AccessAnalysis::MemAccessInfo &
A, Instruction *AInst,
3013 const AccessAnalysis::MemAccessInfo &
B, Instruction *BInst) {
3014 const auto &
DL = InnermostLoop->getHeader()->getDataLayout();
3015 auto &SE = *PSE.getSE();
3016 const auto &[APtr, AIsWrite] =
A;
3017 const auto &[BPtr, BIsWrite] =
B;
3020 if (!AIsWrite && !BIsWrite)
3027 if (APtr->getType()->getPointerAddressSpace() !=
3028 BPtr->getType()->getPointerAddressSpace())
3032 std::optional<int64_t> StrideAPtr =
3033 getPtrStride(PSE, ATy, APtr, InnermostLoop, *DT, SymbolicStrides,
3035 std::optional<int64_t> StrideBPtr =
3036 getPtrStride(PSE, BTy, BPtr, InnermostLoop, *DT, SymbolicStrides,
3038 PSE.addPredicates(Predicates);
3040 const SCEV *Src = PSE.getSCEV(APtr);
3041 const SCEV *Sink = PSE.getSCEV(BPtr);
3046 if (StrideAPtr && *StrideAPtr < 0) {
3055 LLVM_DEBUG(
dbgs() <<
"LAA: Src Scev: " << *Src <<
"Sink Scev: " << *Sink
3057 LLVM_DEBUG(
dbgs() <<
"LAA: Distance for " << *AInst <<
" to " << *BInst
3058 <<
": " << *Dist <<
"\n");
3067 if (!StrideAPtr || !StrideBPtr) {
3068 LLVM_DEBUG(
dbgs() <<
"Pointer access with non-constant stride\n");
3072 int64_t StrideAPtrInt = *StrideAPtr;
3073 int64_t StrideBPtrInt = *StrideBPtr;
3074 LLVM_DEBUG(
dbgs() <<
"LAA: Src induction step: " << StrideAPtrInt
3075 <<
" Sink induction step: " << StrideBPtrInt <<
"\n");
3078 if (!StrideAPtrInt || !StrideBPtrInt) {
3081 if (!StrideAPtrInt && !StrideBPtrInt && Dist->
isZero())
3089 if ((StrideAPtrInt > 0) != (StrideBPtrInt > 0)) {
3091 dbgs() <<
"Pointer access with strides in different directions\n");
3095 TypeSize AStoreSz =
DL.getTypeStoreSize(ATy);
3096 TypeSize BStoreSz =
DL.getTypeStoreSize(BTy);
3102 uint64_t TypeByteSize = (AStoreSz == BStoreSz) ? BSz : 0;
3107 uint64_t MaxStride = std::max(StrideAScaled, StrideBScaled);
3109 std::optional<uint64_t> CommonStride;
3110 if (StrideAScaled == StrideBScaled)
3111 CommonStride = StrideAScaled;
3116 ShouldRetryWithRuntimeChecks |= StrideAPtrInt == StrideBPtrInt;
3124 return DepDistanceStrideAndSizeInfo(Dist, MaxStride, CommonStride,
3125 TypeByteSize, AIsWrite, BIsWrite);
3129MemoryDepChecker::isDependent(
const MemAccessInfo &
A,
unsigned AIdx,
3131 assert(AIdx < BIdx &&
"Must pass arguments in program order");
3136 auto CheckCompletelyBeforeOrAfter = [&]() {
3137 auto *APtr =
A.getPointer();
3138 auto *BPtr =
B.getPointer();
3141 const SCEV *Src = PSE.getSCEV(APtr);
3142 const SCEV *Sink = PSE.getSCEV(BPtr);
3143 return areAccessesCompletelyBeforeOrAfter(Src, ATy, Sink, BTy);
3149 getDependenceDistanceStrideAndSize(
A, InstMap[AIdx],
B, InstMap[BIdx]);
3150 if (std::holds_alternative<Dependence::DepType>(Res)) {
3152 CheckCompletelyBeforeOrAfter())
3154 return std::get<Dependence::DepType>(Res);
3157 auto &[Dist, MaxStride, CommonStride, TypeByteSize, AIsWrite, BIsWrite] =
3158 std::get<DepDistanceStrideAndSizeInfo>(Res);
3159 bool HasSameSize = TypeByteSize > 0;
3161 ScalarEvolution &SE = *PSE.getSE();
3162 auto &
DL = InnermostLoop->getHeader()->getDataLayout();
3174 const APInt *APDist =
nullptr;
3179 LLVM_DEBUG(
dbgs() <<
"LAA: Constant distance does not fit in 64 bits.\n");
3189 if (ConstDist > 0 && CommonStride && CommonStride > 1 && HasSameSize &&
3213 assert(*CommonStride >= std::max(ASz, BSz) &&
3214 "Invariant from getDependenceDistanceStrideAndSize broken!");
3217 LLVM_DEBUG(
dbgs() <<
"LAA: possibly zero dependence difference but "
3218 "different type sizes\n");
3222 bool IsTrueDataDependence = (AIsWrite && !BIsWrite);
3231 if (IsTrueDataDependence &&
3232 Opts.store_to_load_forwarding_conflict_detection) {
3238 couldPreventStoreLoadForward(ConstDist, TypeByteSize)) {
3240 dbgs() <<
"LAA: Forward but may prevent st->ld forwarding\n");
3249 std::optional<int64_t> MinDistanceOpt =
3251 if (!MinDistanceOpt) {
3252 LLVM_DEBUG(
dbgs() <<
"LAA: Minimum distance does not fit in 64 bits.\n");
3255 int64_t MinDistance = *MinDistanceOpt;
3257 if (MinDistance <= 0) {
3263 if (CheckCompletelyBeforeOrAfter())
3265 LLVM_DEBUG(
dbgs() <<
"LAA: ReadWrite-Write positive dependency with "
3266 "different type sizes\n");
3270 unsigned MinForcedFactor =
3275 unsigned MinNumIter = std::max(MinForcedFactor * ForcedUnroll, 2U);
3310 uint64_t MinDistanceNeeded = MaxStride * (MinNumIter - 1) + TypeByteSize;
3311 if (MinDistanceNeeded >
static_cast<uint64_t>(MinDistance)) {
3320 LLVM_DEBUG(
dbgs() <<
"LAA: Failure because of positive minimum distance "
3321 << MinDistance <<
'\n');
3327 if (MinDistanceNeeded > MinDepDistBytes) {
3329 << MinDistanceNeeded <<
" size in bytes\n");
3334 std::min(
static_cast<uint64_t>(MinDistance), MinDepDistBytes);
3336 bool IsTrueDataDependence = (!AIsWrite && BIsWrite);
3337 if (IsTrueDataDependence &&
3338 Opts.store_to_load_forwarding_conflict_detection && ConstDist &&
3339 couldPreventStoreLoadForward(MinDistance, TypeByteSize, *CommonStride))
3342 uint64_t MaxVF = MinDepDistBytes / MaxStride;
3343 LLVM_DEBUG(
dbgs() <<
"LAA: Positive min distance " << MinDistance
3344 <<
" with max VF = " << MaxVF <<
'\n');
3346 uint64_t MaxVFInBits = MaxVF * TypeByteSize * 8;
3347 if (!ConstDist && MaxVFInBits < MaxTargetVectorWidthInBits) {
3356 if (CheckCompletelyBeforeOrAfter())
3359 MaxSafeVectorWidthInBits = std::min(MaxSafeVectorWidthInBits, MaxVFInBits);
3366 MinDepDistBytes = -1;
3381 bool AIIsWrite = AI->getInt();
3385 (AIIsWrite ? AI : std::next(AI));
3388 auto &Acc = Accesses[*AI];
3389 for (std::vector<unsigned>::iterator I1 = Acc.begin(), I1E = Acc.end();
3394 for (std::vector<unsigned>::iterator
3395 I2 = (OI == AI ? std::next(I1) : Accesses[*OI].begin()),
3396 I2E = (OI == AI ? I1E : Accesses[*OI].end());
3398 auto A = std::make_pair(&*AI, *I1);
3399 auto B = std::make_pair(&*OI, *I2);
3406 isDependent(*
A.first,
A.second, *
B.first,
B.second);
3413 if (RecordDependences) {
3415 Dependences.emplace_back(
A.second,
B.second,
Type);
3417 if (Dependences.size() >= Opts.max_dependences) {
3418 RecordDependences =
false;
3419 Dependences.clear();
3421 <<
"Too many dependences, stopped recording\n");
3433 LLVM_DEBUG(
dbgs() <<
"Total Dependences: " << Dependences.size() <<
"\n");
3440 auto I = Accesses.find(
Access);
3442 if (
I != Accesses.end()) {
3443 transform(
I->second, std::back_inserter(Insts),
3444 [&](
unsigned Idx) { return this->InstMap[Idx]; });
3456 "ForwardButPreventsForwarding",
3458 "BackwardVectorizable",
3459 "BackwardVectorizableButPreventsForwarding"};
3469bool LoopAccessInfo::canAnalyzeLoop() {
3478 recordAnalysis(
"NotInnerMostLoop") <<
"loop is not the innermost loop";
3485 dbgs() <<
"LAA: loop control flow is not understood by analyzer\n");
3486 recordAnalysis(
"CFGNotUnderstood")
3487 <<
"loop control flow is not understood by analyzer";
3496 recordAnalysis(
"CantComputeNumberOfIterations")
3497 <<
"could not determine number of loop iterations";
3498 LLVM_DEBUG(
dbgs() <<
"LAA: SCEV could not compute the loop exit count.\n");
3507bool LoopAccessInfo::analyzeLoop(AAResults *AA,
const LoopInfo *LI,
3508 const TargetTransformInfo *
TTI,
3509 const TargetLibraryInfo *
TLI,
3510 DominatorTree *DT) {
3514 SmallPtrSet<MDNode *, 8> LoopAliasScopes;
3517 unsigned NumReads = 0;
3519 bool HasComplexMemInst =
false;
3522 HasConvergentOp =
false;
3524 PtrRtChecking->Pointers.
clear();
3525 PtrRtChecking->Need =
false;
3529 const bool EnableMemAccessVersioningOfLoop =
3530 Opts.enable_mem_access_versioning &&
3535 LoopBlocksRPO RPOT(TheLoop);
3541 for (BasicBlock *BB : RPOT) {
3544 for (Instruction &
I : *BB) {
3547 HasConvergentOp =
true;
3552 if (HasComplexMemInst && HasConvergentOp)
3556 if (HasComplexMemInst)
3561 for (
Metadata *
Op : Decl->getScopeList()->operands())
3566 if (CB && CB->hasReadingOperandBundles()) {
3567 recordAnalysis(
"CantVectorizeInstruction", &
I)
3568 <<
"call instruction with operand bundles cannot be vectorized";
3569 HasComplexMemInst =
true;
3583 if (
I.mayReadFromMemory()) {
3584 auto hasPointerArgs = [](CallBase *CB) {
3586 return Arg->getType()->isPointerTy();
3599 recordAnalysis(
"CantVectorizeInstruction", &
I)
3600 <<
"instruction cannot be vectorized";
3601 HasComplexMemInst =
true;
3604 if (!Ld->isSimple() && !IsAnnotatedParallel) {
3605 recordAnalysis(
"NonSimpleLoad", Ld)
3606 <<
"read with atomic ordering or volatile read";
3608 HasComplexMemInst =
true;
3613 if (EnableMemAccessVersioningOfLoop)
3614 collectStridedAccess(Ld);
3619 if (
I.mayWriteToMemory()) {
3622 recordAnalysis(
"CantVectorizeInstruction", &
I)
3623 <<
"instruction cannot be vectorized";
3624 HasComplexMemInst =
true;
3627 if (!St->isSimple() && !IsAnnotatedParallel) {
3628 recordAnalysis(
"NonSimpleStore", St)
3629 <<
"write with atomic ordering or volatile write";
3631 HasComplexMemInst =
true;
3636 if (EnableMemAccessVersioningOfLoop)
3637 collectStridedAccess(St);
3642 if (HasComplexMemInst)
3650 if (!Stores.
size()) {
3656 AccessAnalysis
Accesses(Opts, TheLoop, AA, LI, *DT,
TTI, DepCands, *PSE,
3664 SmallSet<std::pair<Value *, Type *>, 16> Seen;
3668 SmallPtrSet<Value *, 16> UniformStores;
3670 for (StoreInst *ST : Stores) {
3671 Value *Ptr =
ST->getPointerOperand();
3673 if (isInvariant(Ptr)) {
3675 StoresToInvariantAddresses.push_back(ST);
3676 HasStoreStoreDependenceInvolvingLoopInvariantAddress |=
3677 !UniformStores.
insert(Ptr).second;
3683 if (Seen.
insert({Ptr, AccessTy}).second) {
3688 if (blockNeedsPredication(
ST->getParent(), TheLoop, DT))
3694 [&Accesses, AccessTy, Loc](
Value *Ptr) {
3695 MemoryLocation NewLoc = Loc.getWithNewPtr(Ptr);
3696 Accesses.addStore(NewLoc, AccessTy);
3701 if (IsAnnotatedParallel) {
3703 dbgs() <<
"LAA: A loop annotated parallel, ignore memory dependency "
3708 for (LoadInst *LD : Loads) {
3709 Value *Ptr =
LD->getPointerOperand();
3718 bool IsReadOnlyPtr =
false;
3720 if (Seen.
insert({Ptr, AccessTy}).second ||
3721 !
getPtrStride(*PSE, AccessTy, Ptr, TheLoop, *DT, SymbolicStrides,
3724 IsReadOnlyPtr =
true;
3730 LLVM_DEBUG(
dbgs() <<
"LAA: Found an unsafe dependency between a uniform "
3731 "load and uniform store to the same address!\n");
3732 HasLoadStoreDependenceInvolvingLoopInvariantAddress =
true;
3739 if (blockNeedsPredication(
LD->getParent(), TheLoop, DT))
3745 [&Accesses, AccessTy, Loc, IsReadOnlyPtr](
Value *Ptr) {
3746 MemoryLocation NewLoc = Loc.getWithNewPtr(Ptr);
3747 Accesses.addLoad(NewLoc, AccessTy, IsReadOnlyPtr);
3754 if (Stores.size() == 1 && NumReads == 0) {
3761 Accesses.buildDependenceSets(getDepChecker());
3765 Value *UncomputablePtr =
nullptr;
3766 HasCompletePtrRtChecking =
3767 Accesses.canCheckPtrAtRT(*PtrRtChecking, TheLoop, SymbolicStrides,
3768 UncomputablePtr, AllowPartial, getDepChecker());
3769 if (!HasCompletePtrRtChecking) {
3771 recordAnalysis(
"CantIdentifyArrayBounds",
I)
3772 <<
"cannot identify array bounds";
3773 LLVM_DEBUG(
dbgs() <<
"LAA: We can't vectorize because we can't find "
3774 <<
"the array bounds.\n");
3779 dbgs() <<
"LAA: May be able to perform a memory runtime check if needed.\n");
3781 bool DepsAreSafe =
true;
3782 if (Accesses.isDependencyCheckNeeded()) {
3785 DepChecker->
areDepsSafe(DepCands, Accesses.getDependenciesToCheck());
3790 PtrRtChecking->reset();
3791 PtrRtChecking->Need =
true;
3793 UncomputablePtr =
nullptr;
3794 HasCompletePtrRtChecking = Accesses.canCheckPtrAtRT(
3795 *PtrRtChecking, TheLoop, SymbolicStrides, UncomputablePtr,
3796 AllowPartial, getDepChecker());
3799 if (!HasCompletePtrRtChecking) {
3801 recordAnalysis(
"CantCheckMemDepsAtRunTime",
I)
3802 <<
"cannot check memory dependencies at runtime";
3803 LLVM_DEBUG(
dbgs() <<
"LAA: Can't vectorize with memory checks\n");
3809 Accesses.resetDepChecks(*DepChecker);
3819 for (
const auto &Dep : *Deps) {
3823 Instruction *Dst = Dep.getDestination(*DepChecker);
3825 HasLoadStoreDependenceInvolvingLoopInvariantAddress =
true;
3828 "Expected both to be stores");
3829 HasStoreStoreDependenceInvolvingLoopInvariantAddress =
true;
3834 if (HasConvergentOp) {
3835 recordAnalysis(
"CantInsertRuntimeCheckWithConvergent")
3836 <<
"cannot add control dependency to convergent operation";
3837 LLVM_DEBUG(
dbgs() <<
"LAA: We can't vectorize because a runtime check "
3838 "would be needed with a convergent operation\n");
3844 dbgs() <<
"LAA: No unsafe dependent memory operations in loop. We"
3845 << (PtrRtChecking->Need ?
"" :
" don't")
3846 <<
" need runtime memory checks.\n");
3850 emitUnsafeDependenceRemark();
3854void LoopAccessInfo::emitUnsafeDependenceRemark() {
3855 const auto *Deps = getDepChecker().getDependences();
3863 if (Found == Deps->end())
3865 MemoryDepChecker::Dependence Dep = *Found;
3867 LLVM_DEBUG(
dbgs() <<
"LAA: unsafe dependent memory operations in loop\n");
3870 bool HasForcedDistribution =
3873 const std::string
Info =
3874 HasForcedDistribution
3875 ?
"unsafe dependent memory operations in loop."
3876 :
"unsafe dependent memory operations in loop. Use "
3877 "#pragma clang loop distribute(enable) to allow loop distribution "
3878 "to attempt to isolate the offending operations into a separate "
3880 OptimizationRemarkAnalysis &
R =
3889 R <<
"\nBackward loop carried data dependence.";
3892 R <<
"\nForward loop carried data dependence that prevents "
3893 "store-to-load forwarding.";
3896 R <<
"\nBackward loop carried data dependence that prevents "
3897 "store-to-load forwarding.";
3900 R <<
"\nUnsafe indirect dependence.";
3903 R <<
"\nUnsafe dependence on loop-invariant address.";
3906 R <<
"\nUnknown data dependence.";
3910 if (Instruction *
I = Dep.
getSource(getDepChecker())) {
3913 SourceLoc = DD->getDebugLoc();
3915 R <<
" Memory location is the same as accessed at "
3916 <<
ore::NV(
"Location", SourceLoc);
3921 const Loop *TheLoop,
3923 assert(TheLoop->contains(BB) &&
"Unknown block used");
3926 const BasicBlock *Latch = TheLoop->getLoopLatch();
3927 assert(Latch &&
"Loop expected to have a single latch.");
3933 assert(!Report &&
"Multiple reports generated");
3939 CodeRegion =
I->getParent();
3942 if (
I->getDebugLoc())
3943 DL =
I->getDebugLoc();
3946 Report = std::make_unique<OptimizationRemarkAnalysis>(
DEBUG_TYPE, RemarkName,
3952 auto *SE = PSE->getSE();
3953 if (TheLoop->isLoopInvariant(V))
3970 for (
const Use &U :
GEP->operands()) {
3992 Value *OrigPtr = Ptr;
4000 V =
C->getOperand();
4023void LoopAccessInfo::collectStridedAccess(
Value *MemAccess) {
4041 LLVM_DEBUG(
dbgs() <<
"LAA: Found a strided access that is a candidate for "
4043 LLVM_DEBUG(
dbgs() <<
" Ptr: " << *Ptr <<
" Stride: " << *StrideExpr <<
"\n");
4045 if (!Opts.laa_speculate_unit_stride) {
4046 LLVM_DEBUG(
dbgs() <<
" Chose not to due to -laa-speculate-unit-stride\n");
4063 const SCEV *MaxBTC = PSE->getSymbolicMaxBackedgeTakenCount();
4071 const SCEV *CastedStride = StrideExpr;
4072 const SCEV *CastedBECount = MaxBTC;
4073 ScalarEvolution *SE = PSE->getSE();
4074 if (BETypeSizeBits >= StrideTypeSizeBits)
4078 const SCEV *StrideMinusBETaken = SE->
getMinusSCEV(CastedStride, CastedBECount);
4084 dbgs() <<
"LAA: Stride>=TripCount; No point in versioning as the "
4085 "Stride==1 predicate will imply that the loop executes "
4089 LLVM_DEBUG(
dbgs() <<
"LAA: Found a strided access that we can version.\n");
4093 const SCEV *StrideBase = StrideExpr;
4095 StrideBase =
C->getOperand();
4097 "users of the map rely on the stride being loop invariant");
4108 PtrRtChecking(nullptr), TheLoop(L),
4110 AllowPartial(AllowPartial) {
4111 unsigned MaxTargetVectorWidthInBits = std::numeric_limits<unsigned>::max();
4112 if (
TTI && !
TTI->enableScalableVectorization())
4115 MaxTargetVectorWidthInBits =
4118 DepChecker = std::make_unique<MemoryDepChecker>(
4119 *PSE, AC, DT, L, SymbolicStrides, MaxTargetVectorWidthInBits, LoopGuards);
4121 std::make_unique<RuntimePointerChecking>(*DepChecker, SE, LoopGuards);
4122 if (canAnalyzeLoop())
4123 CanVecMem = analyzeLoop(
AA, LI,
TTI,
TLI, DT);
4128 OS.
indent(
Depth) <<
"Memory dependences are safe";
4131 OS <<
" with a maximum safe vector width of "
4135 OS <<
", with a maximum safe store-load forward width of " << SLDist
4138 if (PtrRtChecking->Need)
4139 OS <<
" with run-time checks";
4143 if (HasConvergentOp)
4144 OS.
indent(
Depth) <<
"Has convergent operation in loop\n";
4147 OS.
indent(
Depth) <<
"Report: " << Report->getMsg() <<
"\n";
4149 if (
auto *Dependences = DepChecker->getDependences()) {
4151 for (
const auto &Dep : *Dependences) {
4152 Dep.
print(OS,
Depth + 2, DepChecker->getMemoryInstructions());
4156 OS.
indent(
Depth) <<
"Too many dependences, not recorded\n";
4159 PtrRtChecking->print(OS,
Depth);
4160 if (PtrRtChecking->Need && !HasCompletePtrRtChecking)
4161 OS.
indent(
Depth) <<
"Generated run-time checks are incomplete\n";
4165 <<
"Non vectorizable stores to invariant address were "
4166 << (HasStoreStoreDependenceInvolvingLoopInvariantAddress ||
4167 HasLoadStoreDependenceInvolvingLoopInvariantAddress
4170 <<
"found in loop.\n";
4173 PSE->getPredicate().print(OS,
Depth);
4178 PSE->print(OS,
Depth);
4182 bool AllowPartial) {
4183 const auto &[It, Inserted] = LoopAccessInfoMap.try_emplace(&L);
4187 if (Inserted || It->second->hasAllowPartial() != AllowPartial)
4188 It->second = std::make_unique<LoopAccessInfo>(&L, &SE, TTI, TLI, &AA, &DT,
4189 &LI, AC, AllowPartial);
4198 LoopAccessInfoMap.remove_if([](
const auto &Entry) {
4199 const auto &LAI = Entry.second;
4200 return !(LAI->getRuntimePointerChecking()->getChecks().empty() &&
4201 LAI->getPSE().getPredicate().isAlwaysTrue());
4207 FunctionAnalysisManager::Invalidator &Inv) {
const TargetLowering & TLI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file implements the BitVector class.
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
DXIL Forward Handle Accesses
This file defines the DenseMap class.
static MDNode * adjustAliasScopeList(MDNode *ScopeList, const SmallPtrSetImpl< const MDNode * > &LoopAliasScopes)
Drop alias scopes that are only valid within a single loop iteration.
static MemoryLocation adjustLoc(MemoryLocation Loc, const SmallPtrSetImpl< const MDNode * > &LoopAliasScopes)
Generic implementation of equivalence classes through the use Tarjan's efficient union-find algorithm...
This header defines various interfaces for pass management in LLVM.
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
static bool isSafeDependenceDistance(ScalarEvolution &SE, const SCEV &MaxBTC, const SCEV &Dist, uint64_t MaxStride)
Given a dependence-distance Dist between two memory accesses, that have strides in the same direction...
static bool evaluatePtrAddRecAtMaxBTCWillNotWrap(const SCEVAddRecExpr *AR, const SCEV *MaxBTC, const SCEV *EltSize, ScalarEvolution &SE, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC, ScalarEvolution::LoopGuards &LoopGuards)
Return true, if evaluating AR at MaxBTC cannot wrap, because AR at MaxBTC is guaranteed inbounds of t...
static void findForkedSCEVs(ScalarEvolution *SE, const Loop *L, Value *Ptr, SmallVectorImpl< PointerIntPair< const SCEV *, 1, bool > > &ScevList, unsigned Depth)
static const SCEV * mulSCEVNoOverflow(const SCEV *A, const SCEV *B, ScalarEvolution &SE)
Returns A * B, if it is guaranteed not to unsigned wrap.
static bool isNoWrap(PredicatedScalarEvolution &PSE, const SCEVAddRecExpr *AR, Value *Ptr, Type *AccessTy, const Loop *L, const DominatorTree &DT, std::optional< int64_t > Stride=std::nullopt, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Check whether AR is a non-wrapping AddRec.
static RuntimeCheckingPtrGroup buildMergedStencilGroup(const RuntimePointerChecking &RtCheck, ArrayRef< unsigned > AllMembers, const SCEV *MergedLow, const SCEV *MergedHigh, ArrayRef< unsigned > GroupIndices)
Build the merged stencil group for one DepSet, after the cost model has decided the merge is profitab...
static bool areAddrSpacesComparable(unsigned AS0, unsigned AS1, const DataLayout &DL, const TargetTransformInfo *TTI)
Returns true if pointers in AS0 and AS1 can be compared in runtime checks, i.e.
static bool isNeverAbove(const StencilDecomposition &A, const StencilDecomposition &B)
Return true if offset A is never higher than offset B.
static std::optional< APInt > getStencilStrideUpperLimit(const StencilDecomposition &D, unsigned BitWidth)
Find a common upper limit M for the positive strides in D.
static const SCEV * getStrideFromPointer(Value *Ptr, ScalarEvolution *SE, Loop *Lp)
Get the stride of a pointer access in a loop.
static bool isKnownNonDecreasingInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)
Return true if S is known to be monotonically non-decreasing (in the unsigned sense,...
static cl::opt< ElementCount, true > VectorizationFactor("force-vector-width", cl::Hidden, cl::desc("Sets the SIMD width. Zero is autoselect."), cl::location(VectorizerParams::VectorizationFactor))
static cl::opt< unsigned, true > VectorizationInterleave("force-vector-interleave", cl::Hidden, cl::desc("Sets the vectorization interleave count. " "Zero is autoselect."), cl::location(VectorizerParams::VectorizationInterleave))
static cl::opt< bool, true > HoistRuntimeChecks("hoist-runtime-checks", cl::Hidden, cl::desc("Hoist inner loop runtime memory checks to outer loop if possible"), cl::location(VectorizerParams::HoistRuntimeChecks), cl::init(true))
static DenseMap< const RuntimeCheckingPtrGroup *, unsigned > getPtrToIdxMap(ArrayRef< RuntimeCheckingPtrGroup > CheckingGroups)
Assign each RuntimeCheckingPtrGroup pointer an index for stable UTC output.
static bool addressIdentifiesLocation(unsigned AS, const DataLayout &DL)
Returns true if the address of a pointer in AS identifies the accessed memory location,...
static cl::opt< unsigned, true > RuntimeMemoryCheckThreshold("runtime-memory-check-threshold", cl::Hidden, cl::desc("When performing memory disambiguation checks at runtime do not " "generate more than this number of comparisons (default = 8)."), cl::location(VectorizerParams::RuntimeMemoryCheckThreshold), cl::init(8))
static void visitPointers(Value *StartPtr, const Loop &InnermostLoop, function_ref< void(Value *)> AddPointer)
constexpr unsigned MaxStencilDecomposeDepth
Recursion cap for addScaledStencilTerm.
static SmallVector< unsigned, 4 > collectCandidateMembers(ArrayRef< StencilDecomposition > Offsets, bool ForMin)
Find the members that can define the merged bound on one side.
static bool addScaledStencilTerm(const SCEV *Term, int64_t Mult, unsigned Depth, StencilDecomposition &D)
Add one term of a stencil offset to D.
static cl::opt< unsigned, true > VectorizeMemoryCheckThreshold("vectorize-memory-check-threshold", cl::Hidden, cl::desc("The maximum allowed number of runtime memory checks"), cl::location(VectorizerParams::VectorizeMemoryCheckThreshold), cl::init(128))
static bool areStridedAccessesIndependent(uint64_t Distance, uint64_t Stride, uint64_t TypeByteSize)
Check the dependence for two accesses with the same stride Stride.
static const SCEV * getMinFromExprs(const SCEV *I, const SCEV *J, ScalarEvolution *SE)
Compare I and J and return the minimum.
static bool collectStrideLimits(const StencilDecomposition &D, unsigned BitWidth, ScalarEvolution &SE, StrideLimits &Limits)
Add to Limits the checks each stride s of D needs: 1 <= s isNeverAbove assumes every stride is 1 or m...
static std::pair< unsigned, unsigned > computeStencilMergeCost(const RuntimePointerChecking &RtCheck, ArrayRef< unsigned > GroupIndices, const StrideLimits &Local, const StrideLimits &Committed, unsigned NumBoundOperands)
Local cost model: count the runtime checks required before and after replacing one DepSet's groups (G...
static std::pair< const SCEV *, const SCEV * > getNonAffineMonotonicBounds(const Loop *Lp, const SCEV *PtrExpr, const SCEV *EltSizeSCEV, ScalarEvolution *SE)
Try to bound a loop-variant pointer that is not an affine AddRec.
static Value * getLoopVariantGEPOperand(Value *Ptr, ScalarEvolution *SE, Loop *Lp)
If Ptr is a GEP, which has a loop-variant operand, return that operand.
static std::optional< StencilDecomposition > decomposeStencilOffset(const SCEV *Expr, ScalarEvolution &SE, const Loop &L)
Try to decompose Expr into a stencil offset function of loop-invariant strides: C + a1*s1 + a2*s2 + ....
static const SCEV * addSCEVNoOverflow(const SCEV *A, const SCEV *B, ScalarEvolution &SE)
Returns A + B, if it is guaranteed not to unsigned wrap.
This header provides classes for managing per-loop analyses.
This file implements a map that provides insertion order iteration.
This file provides utility analysis objects describing memory locations.
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
FunctionAnalysisManager FAM
This file defines the PointerIntPair class.
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)
static const X86InstrFMA3Group Groups[]
A manager for alias analyses.
Class for arbitrary precision integers.
std::optional< uint64_t > tryZExtValue() const
Get zero extended value if possible.
APInt abs() const
Get the absolute value.
LLVM_ABI APInt sextOrTrunc(unsigned width) const
Sign extend or truncate to width.
std::optional< int64_t > trySExtValue() const
Get sign extended value if possible.
This templated class represents "all analyses that operate over <aparticular IR unit>" (e....
Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
Get the array size.
bool empty() const
Check if the array is empty.
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
const Function * getParent() const
Return the enclosing method, or null if none.
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
bool test(unsigned Idx) const
Returns true if bit Idx is set.
BitVector & set()
Set all bits in the bitvector.
bool isNoBuiltin() const
Return true if the call should not be treated as a call to a builtin.
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
bool isConvergent() const
Determine if the invoke is convergent.
@ ICMP_SLE
signed less or equal
@ ICMP_UGE
unsigned greater or equal
@ ICMP_SGT
signed greater than
@ ICMP_ULE
unsigned less or equal
static LLVM_ABI Constant * getIntToPtr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static LLVM_ABI Constant * getAllOnesValue(Type *Ty)
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
A parsed version of the target data layout string in and methods for querying it.
ValueT lookup(const_arg_type_t< KeyT > Val) const
Return the entry for the specified key, or a default constructed value if no such entry exists.
Analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
iterator_range< member_iterator > members(const ECValue &ECV) const
bool contains(const ElemTy &V) const
Returns true if V is contained an equivalence class.
const ECValue & insert(const ElemTy &Data)
Insert a new value into the union/find set, ignoring the request if the value already exists.
bool isEquivalent(const ElemTy &V1, const ElemTy &V2) const
member_iterator member_end() const
const ElemTy & getLeaderValue(const ElemTy &V) const
Return the leader for the specified value that is in the set.
member_iterator findLeader(const ElemTy &V) const
Given a value in the set, return a member iterator for the equivalence class it is in.
void eraseClass(const ElemTy &V)
Erase the class containing V, i.e.
member_iterator unionSets(const ElemTy &V1, const ElemTy &V2)
Merge the two equivalence sets for the specified values, inserting them if they do not already exist ...
bool hasOptSize() const
Optimize this function for size (-Os) or minimum size (-Oz).
PointerType * getType() const
Global values are always pointers.
An instruction for reading from memory.
Value * getPointerOperand()
static constexpr LocationSize beforeOrAfterPointer()
Any location before or after the base pointer (but still within the underlying object).
This analysis provides dependence information for the memory accesses of a loop.
LLVM_ABI Result run(Function &F, FunctionAnalysisManager &AM)
LLVM_ABI bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
LLVM_ABI const LoopAccessInfo & getInfo(Loop &L, bool AllowPartial=false)
Drive the analysis of memory accesses in the loop.
const MemoryDepChecker & getDepChecker() const
the Memory Dependence Checker which can determine the loop-independent and loop-carried dependences b...
LLVM_ABI bool isInvariant(Value *V) const
Returns true if value V is loop invariant.
LLVM_ABI void print(raw_ostream &OS, unsigned Depth=0) const
Print the information about the memory accesses in the loop.
static LLVM_ABI bool blockNeedsPredication(const BasicBlock *BB, const Loop *TheLoop, const DominatorTree *DT)
Return true if the block BB needs to be predicated in order for the loop to be vectorized.
LLVM_ABI LoopAccessInfo(Loop *L, ScalarEvolution *SE, const TargetTransformInfo *TTI, const TargetLibraryInfo *TLI, AAResults *AA, DominatorTree *DT, LoopInfo *LI, AssumptionCache *AC, bool AllowPartial=false)
Analysis pass that exposes the LoopInfo for a function.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within this loop.
bool isInnermost() const
Return true if the loop does not contain any (natural) loops.
unsigned getNumBackEdges() const
Calculate the number of back edges to the loop header.
BlockT * getHeader() const
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Represents a single loop in the control flow graph.
LLVM_ABI std::string getLocStr() const
Return a string containing the debug location of the loop (file name + line number if present,...
LLVM_ABI bool isAnnotatedParallel() const
Returns true if the loop is annotated parallel.
LLVM_ABI DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
ArrayRef< MDOperand > operands() const
Checks memory dependences among accesses to the same underlying object to determine whether there vec...
ArrayRef< unsigned > getOrderForAccess(Value *Ptr, bool IsWrite) const
Return the program order indices for the access location (Ptr, IsWrite).
bool isSafeForAnyStoreLoadForwardDistances() const
Return true if there are no store-load forwarding dependencies.
LLVM_ABI bool areDepsSafe(const DepCandidates &AccessSets, ArrayRef< MemAccessInfo > CheckDeps)
Check whether the dependencies between the accesses are safe, and records the dependence information ...
bool isSafeForAnyVectorWidth() const
Return true if the number of elements that are safe to operate on simultaneously is not bounded.
MemAccessInfo getAccess(unsigned Idx) const
Return the access location with program order index Idx.
static bool isStoreLoadForwardingConflict(uint64_t Distance, uint64_t VectorStoreSize, uint64_t TypeByteSize, uint64_t LoadElementSize=0)
Returns true if a memory dependence at byte distance Distance between a store (with element size Type...
PointerIntPair< Value *, 1, bool > MemAccessInfo
EquivalenceClasses< MemAccessInfo > DepCandidates
Set of potential dependent memory accesses.
bool shouldRetryWithRuntimeChecks() const
In same cases when the dependency check fails we can still vectorize the loop with a dynamic array ac...
const Loop * getInnermostLoop() const
uint64_t getMaxSafeVectorWidthInBits() const
Return the number of elements that are safe to operate on simultaneously, multiplied by the size of t...
bool isSafeForVectorization() const
No memory dependence was encountered that would inhibit vectorization.
const SmallVectorImpl< Dependence > * getDependences() const
Returns the memory dependences.
void removeUnknownDependences()
LLVM_ABI SmallVector< Instruction *, 4 > getInstructionsForAccess(Value *Ptr, bool isWrite) const
Find the set of instructions that read or write via Ptr.
VectorizationSafetyStatus
Type to keep track of the status of the dependence check.
@ PossiblySafeWithRtChecks
LLVM_ABI void addAccess(StoreInst *SI)
Register the location (instructions are given increasing numbers) of a write access.
uint64_t getStoreLoadForwardSafeDistanceInBits() const
Return safe power-of-2 number of elements, which do not prevent store-load forwarding,...
LLVM_ABI MemoryDepChecker(PredicatedScalarEvolution &PSE, AssumptionCache *AC, DominatorTree *DT, const Loop *L, const SymbolicStrideMap &SymbolicStrides, unsigned MaxTargetVectorWidthInBits, ScalarEvolution::LoopGuards &LoopGuards)
Representation for a specific memory location.
static LLVM_ABI MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known.
AAMDNodes AATags
The metadata nodes which describes the aliasing of the location (each member is null if that kind of ...
const Value * Ptr
The address of the start of the location.
PointerIntPair - This class implements a pair of a pointer and small integer.
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
LLVM_ABI void addPredicate(const SCEVPredicate &Pred)
Adds a new predicate.
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
LLVM_ABI const SCEVPredicate & getPredicate() const
LLVM_ABI const SCEVAddRecExpr * getAsAddRec(Value *V, SmallVectorImpl< const SCEVPredicate * > *WrapPredsAdded=nullptr)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
LLVM_ABI void addPredicates(ArrayRef< const SCEVPredicate * > Preds)
Adds all predicates in Preds.
LLVM_ABI const SCEV * getBackedgeTakenCount()
Get the (predicated) backedge count for the analyzed loop.
LLVM_ABI const SCEV * getSymbolicMaxBackedgeTakenCount()
Get the (predicated) symbolic max backedge count for the analyzed loop.
LLVM_ABI const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
A set of analyses that are preserved following a run of a transformation pass.
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Holds information about the memory runtime legality checks to verify that a group of pointers do not ...
bool Need
This flag indicates if we need to add the runtime check.
void reset()
Reset the state of the pointer runtime information.
unsigned getNumberOfChecks() const
Returns the number of run-time checks required according to needsChecking.
LLVM_ABI void printChecks(raw_ostream &OS, const SmallVectorImpl< RuntimePointerCheck > &Checks, unsigned Depth=0) const
Print Checks.
LLVM_ABI bool insert(Loop *Lp, Value *Ptr, const SCEV *PtrExpr, Type *AccessTy, bool WritePtr, unsigned DepSetId, unsigned ASId, PredicatedScalarEvolution &PSE, bool NeedsFreeze, bool IsForked)
Insert a pointer and calculate the start and end SCEVs.
LLVM_ABI bool needsChecking(const RuntimeCheckingPtrGroup &M, const RuntimeCheckingPtrGroup &N) const
Decide if we need to add a check between two groups of pointers, according to needsChecking.
LLVM_ABI void print(raw_ostream &OS, unsigned Depth=0) const
Print the list run-time memory checks necessary.
LLVM_ABI RuntimePointerChecking(MemoryDepChecker &DC, ScalarEvolution *SE, ScalarEvolution::LoopGuards &LoopGuards)
SmallVector< RuntimeCheckingPtrGroup, 2 > CheckingGroups
Holds a partitioning of pointers into "check groups".
friend struct RuntimeCheckingPtrGroup
static LLVM_ABI bool arePointersInSamePartition(const SmallVectorImpl< int > &PtrToPartition, unsigned PtrIdx1, unsigned PtrIdx2)
Check if pointers are in the same partition.
LLVM_ABI void generateChecks(MemoryDepChecker::DepCandidates &DepCands)
Generate the checks and store it.
SmallVector< PointerInfo, 2 > Pointers
Information about the pointers that may require checking.
This node represents a polynomial recurrence on the trip count of the specified loop.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
const Loop * getLoop() const
SCEVUse getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
This class represents a constant integer value.
ConstantInt * getValue() const
const APInt & getAPInt() const
SCEVFlags getNoWrapFlags(SCEVFlags Mask=FlagsNoWrapMask) const
This class represents an assumption made using SCEV expressions which can be checked at run-time.
virtual bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const =0
Returns true if this predicate implies N.
This class represents a composition of other SCEV predicates, and is the class that most clients will...
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
This class represents an analyzed expression in the program.
LLVM_ABI bool isZero() const
Return true if the expression is a constant zero.
Type * getType() const
Return the LLVM type of this SCEV expression.
SCEVTypes getSCEVType() const
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
LLVM_ABI bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
LLVM_ABI const SCEV * getZeroExtendExpr(SCEVUse Op, Type *Ty, unsigned Depth=0)
LLVM_ABI Type * getWiderType(Type *Ty1, Type *Ty2) const
LLVM_ABI const SCEV * getAbsExpr(const SCEV *Op, bool IsNSW)
LLVM_ABI bool isKnownNonPositive(const SCEV *S)
Test if the given expression is known to be non-positive.
LLVM_ABI bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
LLVM_ABI bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI=nullptr)
Is operation BinOp between LHS and RHS provably does not have a signed/unsigned overflow (Signed)?
LLVM_ABI const SCEV * getMinusSCEV(SCEVUse LHS, SCEVUse RHS, SCEVFlags Flags=SCEV::FlagNone, unsigned Depth=0)
Return LHS-RHS.
LLVM_ABI const SCEVPredicate * getEqualPredicate(const SCEV *LHS, const SCEV *RHS)
LLVM_ABI SCEVUse getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
LLVM_ABI const SCEV * getConstant(ConstantInt *V)
LLVM_ABI const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
LLVM_ABI const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
LLVM_ABI bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
LLVM_ABI bool isKnownPositive(const SCEV *S)
Test if the given expression is known to be positive.
LLVM_ABI SCEVUse getAddExpr(SmallVectorImpl< SCEVUse > &Ops, SCEVFlagsPair Flags={}, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
LLVM_ABI bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
LLVM_ABI Type * getEffectiveSCEVType(Type *Ty) const
Return a type with the same bitwidth as the given type and which represents how SCEV will treat the g...
LLVM_ABI const SCEVPredicate * getComparePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
APInt getSignedRangeMin(const SCEV *S)
Determine the min of the signed range for a particular SCEV.
LLVM_ABI const SCEV * getUMaxExpr(SCEVUse LHS, SCEVUse RHS)
@ MonotonicallyIncreasing
LLVM_ABI const SCEV * getStoreSizeOfExpr(Type *IntTy, Type *StoreTy)
Return an expression for the store size of StoreTy that is type IntTy.
LLVM_ABI const SCEVPredicate * getWrapPredicate(const SCEVAddRecExpr *AR, SCEVWrapPredicate::IncrementWrapFlags AddedFlags)
LLVM_ABI const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI std::optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)
If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...
LLVM_ABI const SCEV * getCouldNotCompute()
LLVM_ABI SCEVUse getMulExpr(SmallVectorImpl< SCEVUse > &Ops, SCEVFlagsPair Flags={}, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
LLVM_ABI const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
LLVM_ABI bool isKnownPredicate(CmpPredicate Pred, SCEVUse LHS, SCEVUse RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
LLVM_ABI const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)
Try to apply information from loop guards for L to Expr.
LLVM_ABI const SCEV * getPtrToAddrExpr(const SCEV *Op)
LLVM_ABI const SCEVAddRecExpr * convertSCEVToAddRecWithPredicates(const SCEV *S, const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Preds)
Tries to convert the S expression to an AddRec expression, adding additional predicates to Preds as r...
LLVM_ABI const SCEV * getSizeOfExpr(Type *IntTy, TypeSize Size)
Return an expression for a TypeSize.
LLVM_ABI std::optional< APInt > computeConstantDifference(const SCEV *LHS, const SCEV *RHS)
Compute LHS - RHS and returns the result as an APInt if it is a constant, and std::nullopt if it isn'...
LLVM_ABI const SCEV * getNegativeSCEV(const SCEV *V, SCEVFlags Flags=SCEV::FlagNone)
Return the SCEV object corresponding to -V.
LLVM_ABI const SCEV * rewriteUsingPredicate(const SCEV *S, const Loop *L, const SCEVPredicate &A)
Re-writes the SCEV according to the Predicates in A.
LLVM_ABI std::pair< const SCEV *, const SCEV * > SplitIntoInitAndPostInc(const Loop *L, const SCEV *S)
Splits SCEV expression S into two SCEVs.
LLVM_ABI const SCEV * getUMinExpr(SCEVUse LHS, SCEVUse RHS, bool Sequential=false)
LLVM_ABI const SCEV * getTruncateOrSignExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
void insert_range(Range &&R)
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
bool contains(const T &V) const
Check if the SmallSet contains the given element.
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
LLVM_NO_SANITIZE_CFI_UNRELATED_CAST iterator begin()
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Represent a constant reference to a string, i.e.
Analysis pass providing the TargetTransformInfo.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
bool isVectorTy() const
True if this is an instance of VectorType.
bool isPointerTy() const
True if this is an instance of PointerType.
LLVM_ABI unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
A Use represents the edge between a Value definition and its users.
static SmallVector< VFInfo, 8 > getMappings(const CallInst &CI)
Retrieve all the VFInfo instances associated to the CallInst CI.
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
LLVM_ABI const Value * stripAndAccumulateConstantOffsets(const DataLayout &DL, APInt &Offset, bool AllowNonInbounds, bool AllowInvariantGroup=false, function_ref< bool(Value &Value, APInt &Offset)> ExternalAnalysis=nullptr, bool LookThroughIntToPtr=false) const
Accumulate the constant offset this value has compared to a base pointer.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
LLVM_ABI uint64_t getPointerDereferenceableBytes(const DataLayout &DL, bool &CanBeNull, bool *CanBeFreed) const
Returns the number of bytes known to be dereferenceable for the pointer value.
std::pair< iterator, bool > insert(const ValueT &V)
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
constexpr ScalarTy getFixedValue() const
static constexpr bool isKnownLT(const FixedOrScalableQuantity &LHS, const FixedOrScalableQuantity &RHS)
An efficient, type-erasing, non-owning reference to a callable.
This class implements an extremely fast bulk output stream that can only output to a stream.
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Abstract Attribute helper functions.
bool match(Val *V, const Pattern &P)
bind_cst_ty m_scev_APInt(const APInt *&C)
Match an SCEV constant and bind it to an APInt.
is_undef_or_poison m_scev_UndefOrPoison()
Match an SCEVUnknown wrapping undef or poison.
specificloop_ty m_SpecificLoop(const Loop *L)
match_bind< const SCEVMulExpr > m_scev_Mul(const SCEVMulExpr *&V)
specificscev_ty m_scev_Specific(const SCEV *S)
Match if we have a specific specified SCEV.
SCEVAffineAddRec_match< Op0_t, Op1_t, match_isa< const Loop > > m_scev_AffineAddRec(const Op0_t &Op0, const Op1_t &Op1)
initializer< Ty > init(const Ty &Val)
LocationClass< Ty > location(Ty &L)
DiagnosticInfoOptimizationBase::Argument NV
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI RetainedKnowledge getKnowledgeForValue(const Value *V, ArrayRef< Attribute::AttrKind > AttrKinds, AssumptionCache &AC, function_ref< bool(RetainedKnowledge, Instruction *, const CallBase::BundleOpInfo *)> Filter=[](auto...) { return true;})
Return a valid Knowledge associated to the Value V if its Attribute kind is in AttrKinds and it match...
LLVM_ABI bool getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name)
Returns true if Name is applied to TheLoop and enabled.
LLVM_ABI Intrinsic::ID getVectorIntrinsicIDForCall(const CallInst *CI, const TargetLibraryInfo *TLI)
Returns intrinsic ID for call.
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are tuples (A, B,...
unsigned getPointerAddressSpace(const Type *T)
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
auto dyn_cast_if_present(const Y &Val)
dyn_cast_if_present<X> - Functionally identical to dyn_cast, except that a null (or none in the case ...
LLVM_ABI const SCEV * replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE, const Loop *Lp, const SymbolicStrideMap &PtrToStride, Value *Ptr, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Return the SCEV corresponding to a pointer with the symbolic stride replaced with constant one,...
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
constexpr std::enable_if_t< std::is_signed_v< T >, std::pair< T, bool > > AddOverflow(T X, T Y)
Add two signed integers, computing the two's complement truncated result, returning a pair {result,...
LLVM_ABI std::optional< int64_t > getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr, const Loop *Lp, const DominatorTree &DT, const SymbolicStrideMap &StridesMap=SymbolicStrideMap(), bool ShouldCheckWrap=true, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
If the pointer has a constant stride return it in units of the access type size.
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
LLVM_ABI bool isValidAssumeForContext(const Instruction *I, const Instruction *CtxI, const DominatorTree *DT=nullptr, bool AllowEphemerals=false)
Return true if it is valid to use the assumptions provided by an assume intrinsic,...
const AnalysisOptions & getAnalysisOptions(const LLVMContext &C)
auto dyn_cast_or_null(const Y &Val)
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.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
decltype(auto) get(const PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info > &Pair)
DenseMap< Value *, const SCEVUnknown * > SymbolicStrideMap
Maps a pointer to its symbolic (non-constant) stride.
LLVM_ABI bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
LLVM_ABI std::optional< int64_t > getPointersDiff(Type *ElemTyA, Value *PtrA, Type *ElemTyB, Value *PtrB, const DataLayout &DL, ScalarEvolution &SE, bool StrictCheck=false, bool CheckType=true)
Returns the distance between the pointers PtrA and PtrB iff they are compatible and it is possible to...
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
LLVM_ABI bool sortPtrAccesses(ArrayRef< Value * > VL, Type *ElemTy, const DataLayout &DL, ScalarEvolution &SE, SmallVectorImpl< unsigned > &SortedIndices)
Attempt to sort the pointers in VL and return the sorted indices in SortedIndices,...
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
LLVM_ABI bool isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL, ScalarEvolution &SE, bool CheckType=true)
Returns true if the memory operations A and B are consecutive.
DWARFExpression::Operation Op
auto max_element(R &&Range)
Provide wrappers to std::max_element which take ranges instead of having to pass begin/end explicitly...
LLVM_ABI bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
ArrayRef(const T &OneElt) -> ArrayRef< T >
constexpr U AbsoluteValue(T X)
Return the absolute value of a signed integer, converted to the corresponding unsigned integer type.
constexpr int64_t maxIntN(int64_t N)
Gets the maximum value for a N-bit signed integer.
constexpr unsigned BitWidth
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Type * getLoadStoreType(const Value *I)
A helper function that returns the type of a load or store instruction.
constexpr std::enable_if_t< std::is_signed_v< T >, std::pair< T, bool > > MulOverflow(T X, T Y)
Multiply two signed integers, computing the two's complement truncated result, returning a pair {resu...
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI std::optional< int64_t > getStrideFromAddRec(const SCEVAddRecExpr *AR, const Loop *Lp, Type *AccessTy, Value *Ptr, PredicatedScalarEvolution &PSE)
If AR is an affine AddRec for Lp with a constant step, return the step in units of AccessTy's allocat...
T bit_floor(T Value)
Returns the largest integral power of two no greater than Value if Value is nonzero.
@ End
Run the machine verifier once, at the end of the pipeline.
LLVM_ABI void getUnderlyingObjects(const Value *V, SmallVectorImpl< const Value * > &Objects, const LoopInfo *LI=nullptr, unsigned MaxLookup=MaxLookupSearchDepth)
This method is similar to getUnderlyingObject except that it can look through phi and select instruct...
LLVM_ABI std::pair< const SCEV *, const SCEV * > getStartAndEndForAccess(const Loop *Lp, const SCEV *PtrExpr, Type *AccessTy, const SCEV *BTC, const SCEV *MaxBTC, ScalarEvolution *SE, DenseMap< std::pair< const SCEV *, const SCEV * >, std::pair< const SCEV *, const SCEV * > > *PointerBounds, DominatorTree *DT, AssumptionCache *AC, ScalarEvolution::LoopGuards &LoopGuards)
Calculate Start and End points of memory access using exact backedge taken count BTC if computable or...
Implement std::hash so that hash_code can be used in STL containers.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
IR Values for the lower and upper bounds of a pointer evolution.
Result of decomposing a SCEV expression into stencil offset form: Offset = Constant + sum(Coefficient...
SmallMapVector< const SCEV *, int64_t, 4 > Coefficients
Map from loop-invariant stride SCEV to its integer coefficient.
MDNode * Scope
The tag for alias scope specification (used with noalias).
MDNode * TBAA
The tag for type-based alias analysis.
MDNode * NoAlias
The tag specifying the noalias scope.
A special type used by analysis passes to provide an address that identifies that particular analysis...
Instruction * getDestination(const MemoryDepChecker &DepChecker) const
Return the destination instruction of the dependence.
DepType Type
The type of the dependence.
unsigned Destination
Index of the destination of the dependence in the InstMap vector.
LLVM_ABI bool isPossiblyBackward() const
May be a lexically backward dependence type (includes Unknown).
Instruction * getSource(const MemoryDepChecker &DepChecker) const
Return the source instruction of the dependence.
LLVM_ABI bool isForward() const
Lexically forward dependence.
LLVM_ABI bool isBackward() const
Lexically backward dependence.
LLVM_ABI void print(raw_ostream &OS, unsigned Depth, const SmallVectorImpl< Instruction * > &Instrs) const
Print the dependence.
unsigned Source
Index of the source of the dependence in the InstMap vector.
DepType
The type of the dependence.
@ BackwardVectorizableButPreventsForwarding
@ ForwardButPreventsForwarding
static LLVM_ABI const char * DepName[]
String version of the types.
static LLVM_ABI VectorizationSafetyStatus isSafeForVectorization(DepType Type)
Dependence types that don't prevent vectorization.
Represent one information held inside an operand bundle of an llvm.assume.
unsigned AddressSpace
Address space of the involved pointers.
LLVM_ABI bool addPointer(unsigned Index, const RuntimePointerChecking &RtCheck)
Tries to add the pointer recorded in RtCheck at index Index to this pointer checking group.
bool NeedsFreeze
Whether the pointer needs to be frozen after expansion, e.g.
LLVM_ABI RuntimeCheckingPtrGroup(unsigned Index, const RuntimePointerChecking &RtCheck)
Create a new pointer checking group containing a single pointer, with index Index in RtCheck.
const SCEV * High
The SCEV expression which represents the upper bound of all the pointers in this group.
SmallVector< unsigned, 2 > Members
Indices of all the pointers that constitute this grouping.
const SCEV * Low
The SCEV expression which represents the lower bound of all the pointers in this group.
bool IsWritePtr
Holds the information if this pointer is used for writing to memory.
unsigned DependencySetId
Holds the id of the set of pointers that could be dependent because of a shared underlying object.
unsigned AliasSetId
Holds the id of the disjoint alias set to which this pointer belongs.
A MapVector that performs no allocations if smaller than a certain size.
static LLVM_ABI const unsigned MaxVectorWidth
Maximum SIMD width.
static LLVM_ABI unsigned VectorizeMemoryCheckThreshold
The maximum allowed number of runtime memory checks.
static LLVM_ABI unsigned RuntimeMemoryCheckThreshold
\When performing memory disambiguation checks at runtime do not make more than this number of compari...
static LLVM_ABI bool isInterleaveForced()
True if force-vector-interleave was specified by the user.
static LLVM_ABI unsigned VectorizationInterleave
Interleave factor as overridden by the user.
static LLVM_ABI ElementCount VectorizationFactor
VF as overridden by the user.
static LLVM_ABI bool HoistRuntimeChecks
Function object to check whether the first component of a container supported by std::get (like std::...