72#define DEBUG_TYPE "loop-accesses"
76 cl::desc(
"Sets the SIMD width. Zero is autoselect."),
82 cl::desc(
"Sets the vectorization interleave count. "
83 "Zero is autoselect."),
90 cl::desc(
"When performing memory disambiguation checks at runtime do not "
91 "generate more than this number of comparisons (default = 8)."),
98 cl::desc(
"Maximum number of comparisons done when trying to merge "
99 "runtime memory checks. (default = 100)"),
108 cl::desc(
"Maximum number of dependences collected by "
109 "loop-access analysis (default = 100)"),
125 cl::desc(
"Enable symbolic stride memory access versioning"));
130 "store-to-load-forwarding-conflict-detection",
cl::Hidden,
131 cl::desc(
"Enable conflict detection in loop-access analysis"),
136 cl::desc(
"Maximum recursion depth when finding forked SCEVs (default = 5)"),
141 cl::desc(
"Speculate that non-constant strides are unit in LAA"),
147 "Hoist inner loop runtime memory checks to outer loop if possible"),
152 return ::VectorizationInterleave.getNumOccurrences() > 0;
179 <<
" by: " << *Expr <<
"\n");
185 :
High(RtCheck.Pointers[Index].End),
Low(RtCheck.Pointers[Index].Start),
217 std::optional<ScalarEvolution::LoopGuards> &LoopGuards) {
223 bool CheckForNonNull, CheckForFreed;
224 Value *StartPtrV = StartPtr->getValue();
226 DL, CheckForNonNull, CheckForFreed);
228 if (DerefBytes && (CheckForNonNull || CheckForFreed))
237 Instruction *CtxI = &*L->getHeader()->getFirstNonPHIIt();
238 if (
BasicBlock *LoopPred = L->getLoopPredecessor()) {
240 CtxI = LoopPred->getTerminator();
244 StartPtrV, {Attribute::Dereferenceable}, *AC, CtxI, DT);
251 if (DerefBytesSCEV->
isZero())
271 const SCEV *OffsetAtLastIter =
273 if (!OffsetAtLastIter) {
283 if (!OffsetAtLastIter)
292 if (IsKnownNonNegative) {
315 DenseMap<std::pair<const SCEV *, Type *>,
318 std::optional<ScalarEvolution::LoopGuards> &LoopGuards) {
319 std::pair<const SCEV *, const SCEV *> *PtrBoundsPair;
322 {{PtrExpr, AccessTy},
326 PtrBoundsPair = &Iter->second;
336 ScStart = ScEnd = PtrExpr;
338 ScStart = AR->getStart();
344 ScEnd = AR->evaluateAtIteration(BTC, *SE);
354 DT, AC, LoopGuards)) {
355 ScEnd = AR->evaluateAtIteration(MaxBTC, *SE);
360 ConstantInt::get(EltSizeSCEV->
getType(), -1), AR->getType())));
363 const SCEV *Step = AR->getStepRecurrence(*SE);
368 if (CStep->getValue()->isNegative())
386 std::pair<const SCEV *, const SCEV *> Res = {ScStart, ScEnd};
388 *PtrBoundsPair = Res;
395 Type *AccessTy,
bool WritePtr,
396 unsigned DepSetId,
unsigned ASId,
402 Lp, PtrExpr, AccessTy, BTC, SymbolicMaxBTC, PSE.
getSE(),
403 &DC.getPointerBounds(), DC.getDT(), DC.getAC(), LoopGuards);
406 "must be able to compute both start and end expressions");
407 Pointers.emplace_back(
Ptr, ScStart, ScEnd, WritePtr, DepSetId, ASId, PtrExpr,
411bool RuntimePointerChecking::tryToCreateDiffCheck(
434 if (AccSrc.
size() != 1 || AccSink.
size() != 1)
438 if (AccSink[0] < AccSrc[0])
442 const SCEV *SrcStart;
443 const SCEV *SinkStart;
445 if (!
match(Src->Expr,
464 std::max(
DL.getTypeAllocSize(SrcTy),
DL.getTypeAllocSize(DstTy));
494 const Loop *StartARLoop = SrcStartAR->getLoop();
495 if (StartARLoop == SinkStartAR->getLoop() &&
500 SrcStartAR->getStepRecurrence(*SE) !=
501 SinkStartAR->getStepRecurrence(*SE)) {
502 LLVM_DEBUG(
dbgs() <<
"LAA: Not creating diff runtime check, since these "
503 "cannot be hoisted out of the outer loop\n");
509 <<
"SrcStart: " << *SrcStartInt <<
'\n'
510 <<
"SinkStartInt: " << *SinkStartInt <<
'\n');
511 DiffChecks.emplace_back(SrcStartInt, SinkStartInt, AllocSize,
512 Src->NeedsFreeze ||
Sink->NeedsFreeze);
517 SmallVector<RuntimePointerCheck, 4> Checks;
525 CanUseDiffCheck = CanUseDiffCheck && tryToCreateDiffCheck(CGI, CGJ);
526 Checks.emplace_back(&CGI, &CGJ);
535 assert(Checks.empty() &&
"Checks is not empty");
536 groupChecks(DepCands, UseDependencies);
542 for (
const auto &
I : M.Members)
543 for (
const auto &J :
N.Members)
556 return Diff->isNegative() ? J :
I;
563 RtCheck.
Pointers[Index].PointerValue->getType()->getPointerAddressSpace(),
564 RtCheck.
Pointers[Index].NeedsFreeze, *RtCheck.SE);
568 const SCEV *End,
unsigned AS,
572 "all pointers in a checking group must be in the same address space");
598void RuntimePointerChecking::groupChecks(
644 if (!UseDependencies) {
650 unsigned TotalComparisons = 0;
653 for (
unsigned Index = 0; Index <
Pointers.size(); ++Index)
654 PositionMap[
Pointers[Index].PointerValue].push_back(Index);
680 auto PointerI = PositionMap.
find(M.getPointer());
683 if (PointerI == PositionMap.
end())
685 for (
unsigned Pointer : PointerI->second) {
702 if (Group.addPointer(Pointer, *
this)) {
712 Groups.emplace_back(Pointer, *
this);
725 return (PtrToPartition[PtrIdx1] != -1 &&
726 PtrToPartition[PtrIdx1] == PtrToPartition[PtrIdx2]);
749 for (
const auto &[Idx, CG] :
enumerate(CheckingGroups))
750 PtrIndices[&CG] = Idx;
756 unsigned Depth)
const {
759 for (
const auto &[Check1, Check2] : Checks) {
760 const auto &
First = Check1->Members, &Second = Check2->Members;
762 OS.
indent(
Depth + 2) <<
"Comparing group GRP" << PtrIndices.at(Check1)
764 for (
unsigned K :
First)
766 OS.
indent(
Depth + 2) <<
"Against group GRP" << PtrIndices.at(Check2)
768 for (
unsigned K : Second)
781 OS.
indent(
Depth + 2) <<
"Group GRP" << PtrIndices.at(&CG) <<
":\n";
782 OS.
indent(
Depth + 4) <<
"(Low: " << *CG.Low <<
" High: " << *CG.High
784 for (
unsigned Member : CG.Members) {
796class AccessAnalysis {
806 : TheLoop(TheLoop), BAA(*
AA), AST(BAA), LI(LI), DepCands(DA), PSE(PSE),
807 LoopAliasScopes(LoopAliasScopes) {
809 BAA.enableCrossIterationMode();
815 AST.add(adjustLoc(
Loc));
816 Accesses[MemAccessInfo(
Ptr,
false)].insert(AccessTy);
818 ReadOnlyPtr.insert(
Ptr);
822 void addStore(
const MemoryLocation &Loc,
Type *AccessTy) {
824 AST.add(adjustLoc(Loc));
825 Accesses[MemAccessInfo(
Ptr,
true)].insert(AccessTy);
835 bool createCheckForAccess(RuntimePointerChecking &RtCheck,
837 const DenseMap<Value *, const SCEV *> &Strides,
838 DenseMap<Value *, unsigned> &DepSetId,
839 Loop *TheLoop,
unsigned &RunningDepId,
840 unsigned ASId,
bool Assume);
850 bool canCheckPtrAtRT(RuntimePointerChecking &RtCheck, Loop *TheLoop,
851 const DenseMap<Value *, const SCEV *> &Strides,
852 Value *&UncomputablePtr,
bool AllowPartial);
856 void buildDependenceSets() {
857 processMemAccesses();
865 bool isDependencyCheckNeeded()
const {
return !CheckDeps.empty(); }
868 void resetDepChecks(MemoryDepChecker &DepChecker) {
873 const MemAccessInfoList &getDependenciesToCheck()
const {
return CheckDeps; }
876 typedef MapVector<MemAccessInfo, SmallSetVector<Type *, 1>> PtrAccessMap;
880 MemoryLocation adjustLoc(MemoryLocation Loc)
const {
890 MDNode *adjustAliasScopeList(MDNode *ScopeList)
const {
897 return LoopAliasScopes.contains(cast<MDNode>(Scope));
906 void processMemAccesses();
916 MemAccessInfoList CheckDeps;
919 SmallPtrSet<Value*, 16> ReadOnlyPtr;
943 bool IsRTCheckAnalysisNeeded =
false;
946 PredicatedScalarEvolution &PSE;
948 DenseMap<Value *, SmallVector<const Value *, 16>> UnderlyingObjects;
952 SmallPtrSetImpl<MDNode *> &LoopAliasScopes;
959static std::optional<int64_t>
963 LLVM_DEBUG(
dbgs() <<
"LAA: Bad stride - Scalable object: " << *AccessTy
971 dbgs() <<
"LAA: Bad stride - Not striding over innermost loop ";
975 dbgs() <<
"SCEV: " << *AR <<
"\n";
984 const APInt *APStepVal;
987 dbgs() <<
"LAA: Bad stride - Not a constant strided ";
990 dbgs() <<
"SCEV: " << *AR <<
"\n";
996 TypeSize AllocSize =
DL.getTypeAllocSize(AccessTy);
1000 std::optional<int64_t> StepVal = APStepVal->
trySExtValue();
1002 return std::nullopt;
1005 return *StepVal %
Size ? std::nullopt : std::make_optional(*StepVal /
Size);
1012 std::optional<int64_t> Stride = std::nullopt) {
1026 GEP &&
GEP->hasNoUnsignedSignedWrap())
1037 (Stride == 1 || Stride == -1))
1041 if (
Ptr && Assume) {
1044 <<
"LAA: Pointer: " << *
Ptr <<
"\n"
1045 <<
"LAA: SCEV: " << *AR <<
"\n"
1046 <<
"LAA: Added an overflow assumption\n");
1059 while (!WorkList.
empty()) {
1067 if (PN && InnermostLoop.
contains(PN->getParent()) &&
1068 PN->getParent() != InnermostLoop.
getHeader()) {
1113 auto GetBinOpExpr = [&SE](
unsigned Opcode,
const SCEV *L,
const SCEV *R) {
1115 case Instruction::Add:
1117 case Instruction::Sub:
1125 unsigned Opcode =
I->getOpcode();
1127 case Instruction::GetElementPtr: {
1129 Type *SourceTy =
GEP->getSourceElementType();
1132 if (
I->getNumOperands() != 2 || SourceTy->
isVectorTy()) {
1142 bool NeedsFreeze =
any_of(BaseScevs, UndefPoisonCheck) ||
1143 any_of(OffsetScevs, UndefPoisonCheck);
1148 if (OffsetScevs.
size() == 2 && BaseScevs.
size() == 1)
1150 else if (BaseScevs.
size() == 2 && OffsetScevs.
size() == 1)
1153 ScevList.emplace_back(Scev, NeedsFreeze);
1164 for (
auto [
B, O] :
zip(BaseScevs, OffsetScevs)) {
1175 case Instruction::Select: {
1182 if (ChildScevs.
size() == 2)
1188 case Instruction::PHI: {
1193 if (
I->getNumOperands() == 2) {
1197 if (ChildScevs.
size() == 2)
1203 case Instruction::Add:
1204 case Instruction::Sub: {
1212 any_of(LScevs, UndefPoisonCheck) ||
any_of(RScevs, UndefPoisonCheck);
1217 if (LScevs.
size() == 2 && RScevs.
size() == 1)
1219 else if (RScevs.
size() == 2 && LScevs.
size() == 1)
1222 ScevList.emplace_back(Scev, NeedsFreeze);
1226 for (
auto [L, R] :
zip(LScevs, RScevs))
1227 ScevList.emplace_back(GetBinOpExpr(Opcode,
get<0>(L),
get<0>(R)),
1233 LLVM_DEBUG(
dbgs() <<
"ForkedPtr unhandled instruction: " << *
I <<
"\n");
1239bool AccessAnalysis::createCheckForAccess(
1243 unsigned &RunningDepId,
unsigned ASId,
bool Assume) {
1251 "Must have some runtime-check pointer candidates");
1255 auto IsLoopInvariantOrAR =
1260 if (RTCheckPtrs.
size() == 2 &&
all_of(RTCheckPtrs, IsLoopInvariantOrAR)) {
1263 <<
"\t(" << Idx <<
") " << *Q.getPointer() <<
"\n");
1270 for (
auto &
P : RTCheckPtrs) {
1283 if (RTCheckPtrs.size() == 1) {
1289 if (!
isNoWrap(PSE, AR, RTCheckPtrs.size() == 1 ?
Ptr :
nullptr, AccessTy,
1294 for (
const auto &[PtrExpr, NeedsFreeze] : RTCheckPtrs) {
1298 if (isDependencyCheckNeeded()) {
1300 unsigned &LeaderId = DepSetId[Leader];
1302 LeaderId = RunningDepId++;
1306 DepId = RunningDepId++;
1308 bool IsWrite =
Access.getInt();
1309 RtCheck.
insert(TheLoop,
Ptr, PtrExpr, AccessTy, IsWrite, DepId, ASId, PSE,
1317bool AccessAnalysis::canCheckPtrAtRT(
1320 bool AllowPartial) {
1323 bool CanDoRT =
true;
1325 bool MayNeedRTCheck =
false;
1326 if (!IsRTCheckAnalysisNeeded)
return true;
1328 bool IsDepCheckNeeded = isDependencyCheckNeeded();
1333 for (
const auto &AS : AST) {
1334 int NumReadPtrChecks = 0;
1335 int NumWritePtrChecks = 0;
1336 bool CanDoAliasSetRT =
true;
1338 auto ASPointers = AS.getPointers();
1342 unsigned RunningDepId = 1;
1350 for (
const Value *ConstPtr : ASPointers) {
1352 bool IsWrite =
Accesses.contains(MemAccessInfo(
Ptr,
true));
1354 ++NumWritePtrChecks;
1362 if (NumWritePtrChecks == 0 ||
1363 (NumWritePtrChecks == 1 && NumReadPtrChecks == 0)) {
1364 assert((ASPointers.size() <= 1 ||
1367 MemAccessInfo AccessWrite(
const_cast<Value *
>(
Ptr),
1369 return !DepCands.
contains(AccessWrite);
1371 "Can only skip updating CanDoRT below, if all entries in AS "
1372 "are reads or there is at most 1 entry");
1376 for (
auto &
Access : AccessInfos) {
1378 if (!createCheckForAccess(RtCheck,
Access, AccessTy, StridesMap,
1379 DepSetId, TheLoop, RunningDepId, ASId,
1382 << *
Access.getPointer() <<
'\n');
1384 CanDoAliasSetRT =
false;
1398 bool NeedsAliasSetRTCheck = RunningDepId > 2 || !Retries.
empty();
1402 if (NeedsAliasSetRTCheck && !CanDoAliasSetRT) {
1406 CanDoAliasSetRT =
true;
1407 for (
const auto &[
Access, AccessTy] : Retries) {
1408 if (!createCheckForAccess(RtCheck,
Access, AccessTy, StridesMap,
1409 DepSetId, TheLoop, RunningDepId, ASId,
1411 CanDoAliasSetRT =
false;
1412 UncomputablePtr =
Access.getPointer();
1419 CanDoRT &= CanDoAliasSetRT;
1420 MayNeedRTCheck |= NeedsAliasSetRTCheck;
1429 unsigned NumPointers = RtCheck.
Pointers.size();
1430 for (
unsigned i = 0; i < NumPointers; ++i) {
1431 for (
unsigned j = i + 1;
j < NumPointers; ++
j) {
1433 if (RtCheck.
Pointers[i].DependencySetId ==
1434 RtCheck.
Pointers[j].DependencySetId)
1447 dbgs() <<
"LAA: Runtime check would require comparison between"
1448 " different address spaces\n");
1454 if (MayNeedRTCheck && (CanDoRT || AllowPartial))
1458 <<
" pointer comparisons.\n");
1465 bool CanDoRTIfNeeded = !RtCheck.
Need || CanDoRT;
1466 assert(CanDoRTIfNeeded == (CanDoRT || !MayNeedRTCheck) &&
1467 "CanDoRTIfNeeded depends on RtCheck.Need");
1468 if (!CanDoRTIfNeeded && !AllowPartial)
1470 return CanDoRTIfNeeded;
1473void AccessAnalysis::processMemAccesses() {
1483 dbgs() <<
"\t" << *
A.getPointer() <<
" ("
1486 : (ReadOnlyPtr.contains(
A.getPointer()) ?
"read-only"
1495 for (
const auto &AS : AST) {
1499 auto ASPointers = AS.getPointers();
1501 bool SetHasWrite =
false;
1506 UnderlyingObjToAccessMap;
1507 UnderlyingObjToAccessMap ObjToLastAccess;
1510 PtrAccessMap DeferredAccesses;
1514 for (
int SetIteration = 0; SetIteration < 2; ++SetIteration) {
1515 bool UseDeferred = SetIteration > 0;
1516 PtrAccessMap &S = UseDeferred ? DeferredAccesses :
Accesses;
1518 for (
const Value *ConstPtr : ASPointers) {
1523 for (
const auto &[AC,
_] : S) {
1524 if (AC.getPointer() !=
Ptr)
1527 bool IsWrite = AC.getInt();
1531 bool IsReadOnlyPtr = ReadOnlyPtr.contains(
Ptr) && !IsWrite;
1532 if (UseDeferred && !IsReadOnlyPtr)
1536 assert(((IsReadOnlyPtr && UseDeferred) || IsWrite ||
1537 S.contains(MemAccessInfo(
Ptr,
false))) &&
1538 "Alias-set pointer not in the access set?");
1548 if (!UseDeferred && IsReadOnlyPtr) {
1551 DeferredAccesses.insert({
Access, {}});
1559 if ((IsWrite || IsReadOnlyPtr) && SetHasWrite) {
1560 CheckDeps.push_back(
Access);
1561 IsRTCheckAnalysisNeeded =
true;
1573 <<
"Underlying objects for pointer " << *
Ptr <<
"\n");
1574 for (
const Value *UnderlyingObj : UOs) {
1583 auto [It,
Inserted] = ObjToLastAccess.try_emplace(
1601std::optional<int64_t>
1605 bool Assume,
bool ShouldCheckWrap) {
1610 assert(
Ptr->getType()->isPointerTy() &&
"Unexpected non-ptr");
1618 <<
" SCEV: " << *PtrScev <<
"\n");
1619 return std::nullopt;
1622 std::optional<int64_t> Stride =
1624 if (!ShouldCheckWrap || !Stride)
1627 if (
isNoWrap(PSE, AR,
Ptr, AccessTy, Lp, Assume, Stride))
1631 dbgs() <<
"LAA: Bad stride - Pointer may wrap in the address space "
1632 << *
Ptr <<
" SCEV: " << *AR <<
"\n");
1633 return std::nullopt;
1641 assert(PtrA && PtrB &&
"Expected non-nullptr pointers.");
1649 return std::nullopt;
1656 return std::nullopt;
1657 unsigned IdxWidth =
DL.getIndexSizeInBits(ASA);
1659 APInt OffsetA(IdxWidth, 0), OffsetB(IdxWidth, 0);
1665 std::optional<int64_t> Val;
1666 if (PtrA1 == PtrB1) {
1673 return std::nullopt;
1675 IdxWidth =
DL.getIndexSizeInBits(ASA);
1676 OffsetA = OffsetA.sextOrTrunc(IdxWidth);
1685 std::optional<APInt> Diff =
1688 return std::nullopt;
1689 Val = Diff->trySExtValue();
1693 return std::nullopt;
1695 int64_t
Size =
DL.getTypeStoreSize(ElemTyA);
1696 int64_t Dist = *Val /
Size;
1700 if (!StrictCheck || Dist *
Size == Val)
1702 return std::nullopt;
1709 VL, [](
const Value *V) {
return V->getType()->isPointerTy(); }) &&
1710 "Expected list of pointer operands.");
1713 Value *Ptr0 = VL[0];
1715 using DistOrdPair = std::pair<int64_t, unsigned>;
1717 std::set<DistOrdPair,
decltype(Compare)> Offsets(Compare);
1718 Offsets.emplace(0, 0);
1719 bool IsConsecutive =
true;
1721 std::optional<int64_t> Diff =
1729 auto [It, IsInserted] = Offsets.emplace(
Offset, Idx);
1733 IsConsecutive &= std::next(It) == Offsets.end();
1735 SortedIndices.
clear();
1736 if (!IsConsecutive) {
1739 for (
auto [Idx, Off] :
enumerate(Offsets))
1740 SortedIndices[Idx] = Off.second;
1754 std::optional<int64_t> Diff =
1763 Accesses[MemAccessInfo(Ptr, true)].push_back(AccessIdx);
1764 InstMap.push_back(SI);
1772 Accesses[MemAccessInfo(Ptr, false)].push_back(AccessIdx);
1773 InstMap.push_back(LI);
1835bool MemoryDepChecker::couldPreventStoreLoadForward(
uint64_t Distance,
1837 unsigned CommonStride) {
1850 const uint64_t NumItersForStoreLoadThroughMemory = 8 * TypeByteSize;
1852 uint64_t MaxVFWithoutSLForwardIssuesPowerOf2 =
1854 MaxStoreLoadForwardSafeDistanceInBits);
1857 for (
uint64_t VF = 2 * TypeByteSize;
1858 VF <= MaxVFWithoutSLForwardIssuesPowerOf2; VF *= 2) {
1861 if (Distance % VF && Distance / VF < NumItersForStoreLoadThroughMemory) {
1862 MaxVFWithoutSLForwardIssuesPowerOf2 = (VF >> 1);
1867 if (MaxVFWithoutSLForwardIssuesPowerOf2 < 2 * TypeByteSize) {
1869 dbgs() <<
"LAA: Distance " << Distance
1870 <<
" that could cause a store-load forwarding conflict\n");
1875 MaxVFWithoutSLForwardIssuesPowerOf2 <
1876 MaxStoreLoadForwardSafeDistanceInBits &&
1877 MaxVFWithoutSLForwardIssuesPowerOf2 !=
1880 bit_floor(MaxVFWithoutSLForwardIssuesPowerOf2 / CommonStride);
1881 uint64_t MaxVFInBits = MaxVF * TypeByteSize * 8;
1882 MaxStoreLoadForwardSafeDistanceInBits =
1883 std::min(MaxStoreLoadForwardSafeDistanceInBits, MaxVFInBits);
1906 const SCEV &MaxBTC,
const SCEV &Dist,
1929 const SCEV *CastedDist = &Dist;
1930 const SCEV *CastedProduct = Product;
1937 if (DistTypeSizeBits > ProductTypeSizeBits)
1962 assert(Stride > 1 &&
"The stride must be greater than 1");
1963 assert(TypeByteSize > 0 &&
"The type size in byte must be non-zero");
1964 assert(Distance > 0 &&
"The distance must be non-zero");
1967 if (Distance % TypeByteSize)
1986 return Distance % Stride;
1989bool MemoryDepChecker::areAccessesCompletelyBeforeOrAfter(
const SCEV *Src,
1993 const SCEV *BTC = PSE.getBackedgeTakenCount();
1994 const SCEV *SymbolicMaxBTC = PSE.getSymbolicMaxBackedgeTakenCount();
1995 ScalarEvolution &SE = *PSE.getSE();
1996 const auto &[SrcStart_, SrcEnd_] =
1998 &SE, &PointerBounds, DT, AC, LoopGuards);
2002 const auto &[SinkStart_, SinkEnd_] =
2004 &SE, &PointerBounds, DT, AC, LoopGuards);
2023 MemoryDepChecker::DepDistanceStrideAndSizeInfo>
2024MemoryDepChecker::getDependenceDistanceStrideAndSize(
2025 const AccessAnalysis::MemAccessInfo &
A, Instruction *AInst,
2026 const AccessAnalysis::MemAccessInfo &
B, Instruction *BInst) {
2027 const auto &
DL = InnermostLoop->getHeader()->getDataLayout();
2028 auto &SE = *PSE.getSE();
2029 const auto &[APtr, AIsWrite] =
A;
2030 const auto &[BPtr, BIsWrite] =
B;
2033 if (!AIsWrite && !BIsWrite)
2040 if (APtr->getType()->getPointerAddressSpace() !=
2041 BPtr->getType()->getPointerAddressSpace())
2044 std::optional<int64_t> StrideAPtr =
2045 getPtrStride(PSE, ATy, APtr, InnermostLoop, SymbolicStrides,
true,
true);
2046 std::optional<int64_t> StrideBPtr =
2047 getPtrStride(PSE, BTy, BPtr, InnermostLoop, SymbolicStrides,
true,
true);
2049 const SCEV *Src = PSE.getSCEV(APtr);
2050 const SCEV *
Sink = PSE.getSCEV(BPtr);
2055 if (StrideAPtr && *StrideAPtr < 0) {
2064 LLVM_DEBUG(
dbgs() <<
"LAA: Src Scev: " << *Src <<
"Sink Scev: " << *Sink
2066 LLVM_DEBUG(
dbgs() <<
"LAA: Distance for " << *AInst <<
" to " << *BInst
2067 <<
": " << *Dist <<
"\n");
2076 if (!StrideAPtr || !StrideBPtr) {
2077 LLVM_DEBUG(
dbgs() <<
"Pointer access with non-constant stride\n");
2081 int64_t StrideAPtrInt = *StrideAPtr;
2082 int64_t StrideBPtrInt = *StrideBPtr;
2083 LLVM_DEBUG(
dbgs() <<
"LAA: Src induction step: " << StrideAPtrInt
2084 <<
" Sink induction step: " << StrideBPtrInt <<
"\n");
2087 if (!StrideAPtrInt || !StrideBPtrInt)
2092 if ((StrideAPtrInt > 0) != (StrideBPtrInt > 0)) {
2094 dbgs() <<
"Pointer access with strides in different directions\n");
2098 TypeSize AStoreSz =
DL.getTypeStoreSize(ATy);
2099 TypeSize BStoreSz =
DL.getTypeStoreSize(BTy);
2103 uint64_t ASz =
DL.getTypeAllocSize(ATy);
2104 uint64_t BSz =
DL.getTypeAllocSize(BTy);
2105 uint64_t TypeByteSize = (AStoreSz == BStoreSz) ? BSz : 0;
2107 uint64_t StrideAScaled = std::abs(StrideAPtrInt) * ASz;
2108 uint64_t StrideBScaled = std::abs(StrideBPtrInt) * BSz;
2110 uint64_t MaxStride = std::max(StrideAScaled, StrideBScaled);
2112 std::optional<uint64_t> CommonStride;
2113 if (StrideAScaled == StrideBScaled)
2114 CommonStride = StrideAScaled;
2119 ShouldRetryWithRuntimeChecks |= StrideAPtrInt == StrideBPtrInt;
2127 return DepDistanceStrideAndSizeInfo(Dist, MaxStride, CommonStride,
2128 TypeByteSize, AIsWrite, BIsWrite);
2132MemoryDepChecker::isDependent(
const MemAccessInfo &
A,
unsigned AIdx,
2134 assert(AIdx < BIdx &&
"Must pass arguments in program order");
2139 auto CheckCompletelyBeforeOrAfter = [&]() {
2140 auto *APtr =
A.getPointer();
2141 auto *BPtr =
B.getPointer();
2144 const SCEV *Src = PSE.getSCEV(APtr);
2145 const SCEV *
Sink = PSE.getSCEV(BPtr);
2146 return areAccessesCompletelyBeforeOrAfter(Src, ATy, Sink, BTy);
2152 getDependenceDistanceStrideAndSize(
A, InstMap[AIdx],
B, InstMap[BIdx]);
2153 if (std::holds_alternative<Dependence::DepType>(Res)) {
2155 CheckCompletelyBeforeOrAfter())
2157 return std::get<Dependence::DepType>(Res);
2160 auto &[Dist, MaxStride, CommonStride, TypeByteSize, AIsWrite, BIsWrite] =
2161 std::get<DepDistanceStrideAndSizeInfo>(Res);
2162 bool HasSameSize = TypeByteSize > 0;
2164 ScalarEvolution &SE = *PSE.getSE();
2165 auto &
DL = InnermostLoop->getHeader()->getDataLayout();
2174 DL, SE, *(PSE.getSymbolicMaxBackedgeTakenCount()), *Dist, MaxStride))
2179 const APInt *APDist =
nullptr;
2180 uint64_t ConstDist =
2187 if (ConstDist > 0 && CommonStride && CommonStride > 1 && HasSameSize &&
2206 LLVM_DEBUG(
dbgs() <<
"LAA: possibly zero dependence difference but "
2207 "different type sizes\n");
2211 bool IsTrueDataDependence = (AIsWrite && !BIsWrite);
2226 couldPreventStoreLoadForward(ConstDist, TypeByteSize)) {
2228 dbgs() <<
"LAA: Forward but may prevent st->ld forwarding\n");
2239 if (MinDistance <= 0) {
2245 if (CheckCompletelyBeforeOrAfter())
2247 LLVM_DEBUG(
dbgs() <<
"LAA: ReadWrite-Write positive dependency with "
2248 "different type sizes\n");
2257 unsigned MinNumIter = std::max(ForcedFactor * ForcedUnroll, 2U);
2292 uint64_t MinDistanceNeeded = MaxStride * (MinNumIter - 1) + TypeByteSize;
2293 if (MinDistanceNeeded >
static_cast<uint64_t
>(MinDistance)) {
2302 LLVM_DEBUG(
dbgs() <<
"LAA: Failure because of positive minimum distance "
2303 << MinDistance <<
'\n');
2309 if (MinDistanceNeeded > MinDepDistBytes) {
2311 << MinDistanceNeeded <<
" size in bytes\n");
2316 std::min(
static_cast<uint64_t
>(MinDistance), MinDepDistBytes);
2318 bool IsTrueDataDependence = (!AIsWrite && BIsWrite);
2320 couldPreventStoreLoadForward(MinDistance, TypeByteSize, *CommonStride))
2323 uint64_t MaxVF = MinDepDistBytes / MaxStride;
2324 LLVM_DEBUG(
dbgs() <<
"LAA: Positive min distance " << MinDistance
2325 <<
" with max VF = " << MaxVF <<
'\n');
2327 uint64_t MaxVFInBits = MaxVF * TypeByteSize * 8;
2328 if (!ConstDist && MaxVFInBits < MaxTargetVectorWidthInBits) {
2337 if (CheckCompletelyBeforeOrAfter())
2340 MaxSafeVectorWidthInBits = std::min(MaxSafeVectorWidthInBits, MaxVFInBits);
2347 MinDepDistBytes = -1;
2362 bool AIIsWrite = AI->getInt();
2366 (AIIsWrite ? AI : std::next(AI));
2369 auto &Acc = Accesses[*AI];
2370 for (std::vector<unsigned>::iterator I1 = Acc.begin(), I1E = Acc.end();
2374 for (std::vector<unsigned>::iterator
2375 I2 = (OI == AI ? std::next(I1) : Accesses[*OI].begin()),
2376 I2E = (OI == AI ? I1E : Accesses[*OI].end());
2378 auto A = std::make_pair(&*AI, *I1);
2379 auto B = std::make_pair(&*OI, *I2);
2386 isDependent(*
A.first,
A.second, *
B.first,
B.second);
2393 if (RecordDependences) {
2395 Dependences.emplace_back(
A.second,
B.second,
Type);
2398 RecordDependences =
false;
2399 Dependences.clear();
2401 <<
"Too many dependences, stopped recording\n");
2413 LLVM_DEBUG(
dbgs() <<
"Total Dependences: " << Dependences.size() <<
"\n");
2420 auto I = Accesses.find(
Access);
2422 if (
I != Accesses.end()) {
2423 transform(
I->second, std::back_inserter(Insts),
2424 [&](
unsigned Idx) { return this->InstMap[Idx]; });
2435 "ForwardButPreventsForwarding",
2437 "BackwardVectorizable",
2438 "BackwardVectorizableButPreventsForwarding"};
2448bool LoopAccessInfo::canAnalyzeLoop() {
2457 recordAnalysis(
"NotInnerMostLoop") <<
"loop is not the innermost loop";
2464 dbgs() <<
"LAA: loop control flow is not understood by analyzer\n");
2465 recordAnalysis(
"CFGNotUnderstood")
2466 <<
"loop control flow is not understood by analyzer";
2475 recordAnalysis(
"CantComputeNumberOfIterations")
2476 <<
"could not determine number of loop iterations";
2477 LLVM_DEBUG(
dbgs() <<
"LAA: SCEV could not compute the loop exit count.\n");
2486bool LoopAccessInfo::analyzeLoop(AAResults *AA,
const LoopInfo *LI,
2487 const TargetLibraryInfo *TLI,
2488 DominatorTree *DT) {
2492 SmallPtrSet<MDNode *, 8> LoopAliasScopes;
2495 unsigned NumReads = 0;
2496 unsigned NumReadWrites = 0;
2498 bool HasComplexMemInst =
false;
2501 HasConvergentOp =
false;
2503 PtrRtChecking->Pointers.
clear();
2504 PtrRtChecking->Need =
false;
2508 const bool EnableMemAccessVersioningOfLoop =
2514 LoopBlocksRPO RPOT(TheLoop);
2516 for (BasicBlock *BB : RPOT) {
2519 for (Instruction &
I : *BB) {
2522 HasConvergentOp =
true;
2527 if (HasComplexMemInst && HasConvergentOp)
2531 if (HasComplexMemInst)
2536 for (
Metadata *
Op : Decl->getScopeList()->operands())
2549 if (
I.mayReadFromMemory()) {
2550 auto hasPointerArgs = [](CallBase *CB) {
2552 return Arg->getType()->isPointerTy();
2565 recordAnalysis(
"CantVectorizeInstruction", Ld)
2566 <<
"instruction cannot be vectorized";
2567 HasComplexMemInst =
true;
2570 if (!Ld->isSimple() && !IsAnnotatedParallel) {
2571 recordAnalysis(
"NonSimpleLoad", Ld)
2572 <<
"read with atomic ordering or volatile read";
2574 HasComplexMemInst =
true;
2580 if (EnableMemAccessVersioningOfLoop)
2581 collectStridedAccess(Ld);
2586 if (
I.mayWriteToMemory()) {
2589 recordAnalysis(
"CantVectorizeInstruction", St)
2590 <<
"instruction cannot be vectorized";
2591 HasComplexMemInst =
true;
2594 if (!St->isSimple() && !IsAnnotatedParallel) {
2595 recordAnalysis(
"NonSimpleStore", St)
2596 <<
"write with atomic ordering or volatile write";
2598 HasComplexMemInst =
true;
2604 if (EnableMemAccessVersioningOfLoop)
2605 collectStridedAccess(St);
2610 if (HasComplexMemInst)
2618 if (!Stores.
size()) {
2624 AccessAnalysis
Accesses(TheLoop, AA, LI, DepCands, *PSE, LoopAliasScopes);
2631 SmallSet<std::pair<Value *, Type *>, 16> Seen;
2635 SmallPtrSet<Value *, 16> UniformStores;
2637 for (StoreInst *ST : Stores) {
2640 if (isInvariant(
Ptr)) {
2642 StoresToInvariantAddresses.push_back(ST);
2643 HasStoreStoreDependenceInvolvingLoopInvariantAddress |=
2650 if (Seen.
insert({Ptr, AccessTy}).second) {
2657 if (blockNeedsPredication(
ST->getParent(), TheLoop, DT))
2661 [&Accesses, AccessTy, Loc](
Value *
Ptr) {
2662 MemoryLocation NewLoc = Loc.getWithNewPtr(Ptr);
2663 Accesses.addStore(NewLoc, AccessTy);
2668 if (IsAnnotatedParallel) {
2670 dbgs() <<
"LAA: A loop annotated parallel, ignore memory dependency "
2675 for (LoadInst *LD : Loads) {
2685 bool IsReadOnlyPtr =
false;
2687 if (Seen.
insert({Ptr, AccessTy}).second ||
2690 IsReadOnlyPtr =
true;
2696 LLVM_DEBUG(
dbgs() <<
"LAA: Found an unsafe dependency between a uniform "
2697 "load and uniform store to the same address!\n");
2698 HasLoadStoreDependenceInvolvingLoopInvariantAddress =
true;
2705 if (blockNeedsPredication(
LD->getParent(), TheLoop, DT))
2709 [&Accesses, AccessTy, Loc, IsReadOnlyPtr](
Value *
Ptr) {
2710 MemoryLocation NewLoc = Loc.getWithNewPtr(Ptr);
2711 Accesses.addLoad(NewLoc, AccessTy, IsReadOnlyPtr);
2717 if (NumReadWrites == 1 && NumReads == 0) {
2724 Accesses.buildDependenceSets();
2728 Value *UncomputablePtr =
nullptr;
2729 HasCompletePtrRtChecking = Accesses.canCheckPtrAtRT(
2730 *PtrRtChecking, TheLoop, SymbolicStrides, UncomputablePtr, AllowPartial);
2731 if (!HasCompletePtrRtChecking) {
2733 recordAnalysis(
"CantIdentifyArrayBounds",
I)
2734 <<
"cannot identify array bounds";
2735 LLVM_DEBUG(
dbgs() <<
"LAA: We can't vectorize because we can't find "
2736 <<
"the array bounds.\n");
2741 dbgs() <<
"LAA: May be able to perform a memory runtime check if needed.\n");
2743 bool DepsAreSafe =
true;
2744 if (Accesses.isDependencyCheckNeeded()) {
2747 DepChecker->
areDepsSafe(DepCands, Accesses.getDependenciesToCheck());
2753 Accesses.resetDepChecks(*DepChecker);
2755 PtrRtChecking->reset();
2756 PtrRtChecking->Need =
true;
2758 UncomputablePtr =
nullptr;
2759 HasCompletePtrRtChecking =
2760 Accesses.canCheckPtrAtRT(*PtrRtChecking, TheLoop, SymbolicStrides,
2761 UncomputablePtr, AllowPartial);
2764 if (!HasCompletePtrRtChecking) {
2766 recordAnalysis(
"CantCheckMemDepsAtRunTime",
I)
2767 <<
"cannot check memory dependencies at runtime";
2768 LLVM_DEBUG(
dbgs() <<
"LAA: Can't vectorize with memory checks\n");
2775 if (HasConvergentOp) {
2776 recordAnalysis(
"CantInsertRuntimeCheckWithConvergent")
2777 <<
"cannot add control dependency to convergent operation";
2778 LLVM_DEBUG(
dbgs() <<
"LAA: We can't vectorize because a runtime check "
2779 "would be needed with a convergent operation\n");
2785 dbgs() <<
"LAA: No unsafe dependent memory operations in loop. We"
2786 << (PtrRtChecking->Need ?
"" :
" don't")
2787 <<
" need runtime memory checks.\n");
2791 emitUnsafeDependenceRemark();
2795void LoopAccessInfo::emitUnsafeDependenceRemark() {
2796 const auto *Deps = getDepChecker().getDependences();
2804 if (Found == Deps->end())
2806 MemoryDepChecker::Dependence Dep = *Found;
2808 LLVM_DEBUG(
dbgs() <<
"LAA: unsafe dependent memory operations in loop\n");
2811 bool HasForcedDistribution =
false;
2812 std::optional<const MDOperand *>
Value =
2820 const std::string
Info =
2821 HasForcedDistribution
2822 ?
"unsafe dependent memory operations in loop."
2823 :
"unsafe dependent memory operations in loop. Use "
2824 "#pragma clang loop distribute(enable) to allow loop distribution "
2825 "to attempt to isolate the offending operations into a separate "
2827 OptimizationRemarkAnalysis &
R =
2836 R <<
"\nBackward loop carried data dependence.";
2839 R <<
"\nForward loop carried data dependence that prevents "
2840 "store-to-load forwarding.";
2843 R <<
"\nBackward loop carried data dependence that prevents "
2844 "store-to-load forwarding.";
2847 R <<
"\nUnsafe indirect dependence.";
2850 R <<
"\nUnknown data dependence.";
2854 if (Instruction *
I = Dep.
getSource(getDepChecker())) {
2857 SourceLoc = DD->getDebugLoc();
2859 R <<
" Memory location is the same as accessed at "
2860 <<
ore::NV(
"Location", SourceLoc);
2865 const Loop *TheLoop,
2867 assert(TheLoop->contains(BB) &&
"Unknown block used");
2870 const BasicBlock *Latch = TheLoop->getLoopLatch();
2876 assert(!Report &&
"Multiple reports generated");
2882 CodeRegion =
I->getParent();
2885 if (
I->getDebugLoc())
2886 DL =
I->getDebugLoc();
2889 Report = std::make_unique<OptimizationRemarkAnalysis>(
DEBUG_TYPE, RemarkName,
2895 auto *SE = PSE->getSE();
2896 if (TheLoop->isLoopInvariant(V))
2913 for (
const Use &U :
GEP->operands()) {
2943 V =
C->getOperand();
2964void LoopAccessInfo::collectStridedAccess(
Value *MemAccess) {
2979 LLVM_DEBUG(
dbgs() <<
"LAA: Found a strided access that is a candidate for "
2984 LLVM_DEBUG(
dbgs() <<
" Chose not to due to -laa-speculate-unit-stride\n");
3001 const SCEV *MaxBTC = PSE->getSymbolicMaxBackedgeTakenCount();
3007 uint64_t StrideTypeSizeBits =
DL.getTypeSizeInBits(StrideExpr->
getType());
3008 uint64_t BETypeSizeBits =
DL.getTypeSizeInBits(MaxBTC->
getType());
3009 const SCEV *CastedStride = StrideExpr;
3010 const SCEV *CastedBECount = MaxBTC;
3011 ScalarEvolution *SE = PSE->getSE();
3012 if (BETypeSizeBits >= StrideTypeSizeBits)
3016 const SCEV *StrideMinusBETaken = SE->
getMinusSCEV(CastedStride, CastedBECount);
3022 dbgs() <<
"LAA: Stride>=TripCount; No point in versioning as the "
3023 "Stride==1 predicate will imply that the loop executes "
3027 LLVM_DEBUG(
dbgs() <<
"LAA: Found a strided access that we can version.\n");
3031 const SCEV *StrideBase = StrideExpr;
3033 StrideBase =
C->getOperand();
3043 PtrRtChecking(nullptr), TheLoop(L), AllowPartial(AllowPartial) {
3044 unsigned MaxTargetVectorWidthInBits = std::numeric_limits<unsigned>::max();
3045 if (
TTI && !
TTI->enableScalableVectorization())
3048 MaxTargetVectorWidthInBits =
3051 DepChecker = std::make_unique<MemoryDepChecker>(
3052 *PSE, AC, DT, L, SymbolicStrides, MaxTargetVectorWidthInBits, LoopGuards);
3054 std::make_unique<RuntimePointerChecking>(*DepChecker, SE, LoopGuards);
3055 if (canAnalyzeLoop())
3056 CanVecMem = analyzeLoop(
AA, LI, TLI, DT);
3061 OS.
indent(
Depth) <<
"Memory dependences are safe";
3064 OS <<
" with a maximum safe vector width of "
3068 OS <<
", with a maximum safe store-load forward width of " << SLDist
3071 if (PtrRtChecking->Need)
3072 OS <<
" with run-time checks";
3076 if (HasConvergentOp)
3077 OS.
indent(
Depth) <<
"Has convergent operation in loop\n";
3080 OS.
indent(
Depth) <<
"Report: " << Report->getMsg() <<
"\n";
3082 if (
auto *Dependences = DepChecker->getDependences()) {
3084 for (
const auto &Dep : *Dependences) {
3085 Dep.
print(OS,
Depth + 2, DepChecker->getMemoryInstructions());
3089 OS.
indent(
Depth) <<
"Too many dependences, not recorded\n";
3092 PtrRtChecking->print(OS,
Depth);
3093 if (PtrRtChecking->Need && !HasCompletePtrRtChecking)
3094 OS.
indent(
Depth) <<
"Generated run-time checks are incomplete\n";
3098 <<
"Non vectorizable stores to invariant address were "
3099 << (HasStoreStoreDependenceInvolvingLoopInvariantAddress ||
3100 HasLoadStoreDependenceInvolvingLoopInvariantAddress
3103 <<
"found in loop.\n";
3106 PSE->getPredicate().print(OS,
Depth);
3111 PSE->print(OS,
Depth);
3115 bool AllowPartial) {
3116 const auto &[It, Inserted] = LoopAccessInfoMap.try_emplace(&L);
3120 if (Inserted || It->second->hasAllowPartial() != AllowPartial)
3121 It->second = std::make_unique<LoopAccessInfo>(&L, &SE, TTI, TLI, &AA, &DT,
3122 &LI, AC, AllowPartial);
3131 for (
const auto &[L, LAI] : LoopAccessInfoMap) {
3132 if (LAI->getRuntimePointerChecking()->getChecks().empty() &&
3133 LAI->getPSE().getPredicate().isAlwaysTrue())
3135 LoopAccessInfoMap.erase(L);
3141 FunctionAnalysisManager::Invalidator &Inv) {
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
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")
Analysis containing CSE Info
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.
Generic implementation of equivalence classes through the use Tarjan's efficient union-find algorithm...
This header defines various interfaces for pass management in LLVM.
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 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 const SCEV * getStrideFromPointer(Value *Ptr, ScalarEvolution *SE, Loop *Lp)
Get the stride of a pointer access in a loop.
static bool evaluatePtrAddRecAtMaxBTCWillNotWrap(const SCEVAddRecExpr *AR, const SCEV *MaxBTC, const SCEV *EltSize, ScalarEvolution &SE, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC, std::optional< ScalarEvolution::LoopGuards > &LoopGuards)
Return true, if evaluating AR at MaxBTC cannot wrap, because AR at MaxBTC is guaranteed inbounds of t...
static std::optional< int64_t > getStrideFromAddRec(const SCEVAddRecExpr *AR, const Loop *Lp, Type *AccessTy, Value *Ptr, PredicatedScalarEvolution &PSE)
Try to compute a constant stride for AR.
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 cl::opt< unsigned, 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 > 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 isNoWrap(PredicatedScalarEvolution &PSE, const SCEVAddRecExpr *AR, Value *Ptr, Type *AccessTy, const Loop *L, bool Assume, std::optional< int64_t > Stride=std::nullopt)
Check whether AR is a non-wrapping AddRec.
static bool isSafeDependenceDistance(const DataLayout &DL, 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 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 const SCEV * mulSCEVOverflow(const SCEV *A, const SCEV *B, ScalarEvolution &SE)
Returns A * B, if it is guaranteed not to unsigned wrap.
static Value * getLoopVariantGEPOperand(Value *Ptr, ScalarEvolution *SE, Loop *Lp)
If Ptr is a GEP, which has a loop-variant operand, return that operand.
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 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...
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 provides utility analysis objects describing memory locations.
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.
uint64_t getZExtValue() const
Get zero extended value.
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.
int64_t getSExtValue() const
Get sign extended value.
This templated class represents "all analyses that operate over <aparticular IR unit>" (e....
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
size - Get the array size.
bool empty() const
empty - 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 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_UGE
unsigned greater or equal
@ ICMP_SGE
signed greater or equal
@ ICMP_ULE
unsigned less or equal
static LLVM_ABI Constant * getIntToPtr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
A parsed version of the target data layout string in and methods for querying it.
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
iterator find(const_arg_type_t< KeyT > Val)
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 - Insert a new value into the union/find set, ignoring the request if the value already exists...
member_iterator member_end() const
const ElemTy & getLeaderValue(const ElemTy &V) const
getLeaderValue - Return the leader for the specified value that is in the set.
member_iterator findLeader(const ElemTy &V) const
findLeader - Given a value in the set, return a member iterator for the equivalence class it is in.
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...
bool hasOptSize() const
Optimize this function for size (-Os) or minimum size (-Oz).
PointerType * getType() const
Global values are always pointers.
Class to represent integer types.
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
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 in 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.
std::string getLocStr() const
Return a string containing the debug location of the loop (file name + line number if present,...
bool isAnnotatedParallel() const
Returns true if the loop is annotated parallel.
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.
bool isSafeForAnyVectorWidth() const
Return true if the number of elements that are safe to operate on simultaneously is not bounded.
LLVM_ABI bool areDepsSafe(const DepCandidates &AccessSets, const MemAccessInfoList &CheckDeps)
Check whether the dependencies between the accesses are safe, and records the dependence information ...
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.
SmallVector< MemAccessInfo, 8 > MemAccessInfoList
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.
PointerIntPair< Value *, 1, bool > MemAccessInfo
uint64_t getStoreLoadForwardSafeDistanceInBits() const
Return safe power-of-2 number of elements, which do not prevent store-load forwarding,...
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 bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Returns true if we've proved that V doesn't wrap by means of a SCEV predicate.
LLVM_ABI void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Proves that V doesn't overflow by adding SCEV predicate.
LLVM_ABI const SCEVAddRecExpr * getAsAddRec(Value *V)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
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 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.
SmallVector< RuntimeCheckingPtrGroup, 2 > CheckingGroups
Holds a partitioning of pointers into "check groups".
LLVM_ABI void generateChecks(MemoryDepChecker::DepCandidates &DepCands, bool UseDependencies)
Generate the checks and store it.
friend struct RuntimeCheckingPtrGroup
static LLVM_ABI 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.
LLVM_ABI 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 * getStart() const
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.
const Loop * getLoop() const
This class represents a constant integer value.
ConstantInt * getValue() const
const APInt & getAPInt() const
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
This class represents an analyzed expression in the program.
LLVM_ABI bool isZero() const
Return true if the expression is a constant zero.
LLVM_ABI Type * getType() const
Return the LLVM type of this SCEV expression.
Analysis pass that exposes the ScalarEvolution for a function.
static LLVM_ABI LoopGuards collect(const Loop *L, ScalarEvolution &SE)
Collect rewrite map for loop guards for loop L, together with flags indicating if NUW and NSW can be ...
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 * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
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.
LLVM_ABI const SCEV * getUMaxExpr(const SCEV *LHS, const SCEV *RHS)
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 SCEVPredicate * getEqualPredicate(const SCEV *LHS, const SCEV *RHS)
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 const SCEV * getPtrToIntExpr(const SCEV *Op, Type *Ty)
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 const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
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 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.
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 SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
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 const SCEV * getCouldNotCompute()
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 const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)
Try to apply information from loop guards for L to Expr.
LLVM_ABI 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.
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 * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
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.
LLVM_ABI bool isKnownPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
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.
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 push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
StringRef - 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.
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 bool canBeFreed() const
Return true if the memory object referred to by V can by freed in the scope for which the SSA value d...
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 uint64_t getPointerDereferenceableBytes(const DataLayout &DL, bool &CanBeNull, bool &CanBeFreed) const
Returns the number of bytes known to be dereferenceable for the pointer value.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
constexpr ScalarTy getFixedValue() const
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.
@ C
The default llvm calling convention, compatible with C.
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.
class_match< const SCEVConstant > m_SCEVConstant()
specificloop_ty m_SpecificLoop(const Loop *L)
SCEVAffineAddRec_match< Op0_t, Op1_t, class_match< const Loop > > m_scev_AffineAddRec(const Op0_t &Op0, const Op1_t &Op1)
specificscev_ty m_scev_Specific(const SCEV *S)
Match if we have a specific specified SCEV.
class_match< const SCEV > m_SCEV()
initializer< Ty > init(const Ty &Val)
LocationClass< Ty > location(Ty &L)
std::enable_if_t< detail::IsValidPointer< X, Y >::value, bool > hasa(Y &&MD)
Check whether Metadata has a Value.
std::enable_if_t< detail::IsValidPointer< X, Y >::value, X * > extract(Y &&MD)
Extract a Value from Metadata.
DiagnosticInfoOptimizationBase::Argument NV
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.
FunctionAddr VTableAddr Value
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 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.
LLVM_ABI std::optional< const MDOperand * > findStringMetadataForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for loop.
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 ...
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
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)
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 > 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.
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...
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...
LLVM_ABI RetainedKnowledge getKnowledgeValidInContext(const Value *V, ArrayRef< Attribute::AttrKind > AttrKinds, AssumptionCache &AC, const Instruction *CtxI, const DominatorTree *DT=nullptr)
Return a valid Knowledge associated to the Value V if its Attribute kind is in AttrKinds and the know...
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
LLVM_ABI 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,...
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
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.
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.
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
T bit_floor(T Value)
Returns the largest integral power of two no greater than Value if Value is nonzero.
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 *, Type * >, std::pair< const SCEV *, const SCEV * > > *PointerBounds, DominatorTree *DT, AssumptionCache *AC, std::optional< 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.
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.
static LLVM_ABI const unsigned MaxVectorWidth
Maximum SIMD width.
static LLVM_ABI unsigned VectorizationFactor
VF as overridden by the user.
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 bool HoistRuntimeChecks
Function object to check whether the first component of a container supported by std::get (like std::...