73#define DEBUG_TYPE "loop-accesses"
77 cl::desc(
"Sets the SIMD width. Zero is autoselect."),
83 cl::desc(
"Sets the vectorization interleave count. "
84 "Zero is autoselect."),
91 cl::desc(
"When performing memory disambiguation checks at runtime do not "
92 "generate more than this number of comparisons (default = 8)."),
99 cl::desc(
"Maximum number of comparisons done when trying to merge "
100 "runtime memory checks. (default = 100)"),
109 cl::desc(
"Maximum number of dependences collected by "
110 "loop-access analysis (default = 100)"),
126 cl::desc(
"Enable symbolic stride memory access versioning"));
131 "store-to-load-forwarding-conflict-detection",
cl::Hidden,
132 cl::desc(
"Enable conflict detection in loop-access analysis"),
137 cl::desc(
"Maximum recursion depth when finding forked SCEVs (default = 5)"),
142 cl::desc(
"Speculate that non-constant strides are unit in LAA"),
146 return ::VectorizationInterleave.getNumOccurrences() > 0;
157 if (
SI == PtrToStride.
end())
161 const SCEV *StrideSCEV =
SI->second;
166 assert(isa<SCEVUnknown>(StrideSCEV) &&
"shouldn't be in map");
174 <<
" by: " << *Expr <<
"\n");
183 ->getPointerAddressSpace()),
184 NeedsFreeze(RtCheck.Pointers[
Index].NeedsFreeze) {
202 Type *AccessTy,
bool WritePtr,
203 unsigned DepSetId,
unsigned ASId,
212 ScStart = ScEnd = PtrExpr;
215 assert(AR &&
"Invalid addrec expression");
224 if (
const auto *CStep = dyn_cast<SCEVConstant>(Step)) {
225 if (CStep->getValue()->isNegative())
237 Type *IdxTy =
DL.getIndexType(
Ptr->getType());
241 Pointers.emplace_back(
Ptr, ScStart, ScEnd, WritePtr, DepSetId, ASId, PtrExpr,
245void RuntimePointerChecking::tryToCreateDiffCheck(
247 if (!CanUseDiffCheck)
254 CanUseDiffCheck =
false;
265 CanUseDiffCheck =
false;
275 if (AccSrc.
size() != 1 || AccSink.
size() != 1) {
276 CanUseDiffCheck =
false;
280 if (AccSink[0] < AccSrc[0])
283 auto *SrcAR = dyn_cast<SCEVAddRecExpr>(Src->Expr);
284 auto *SinkAR = dyn_cast<SCEVAddRecExpr>(
Sink->Expr);
287 CanUseDiffCheck =
false;
297 if (isa<ScalableVectorType>(SrcTy) || isa<ScalableVectorType>(DstTy)) {
298 CanUseDiffCheck =
false;
302 SinkAR->getLoop()->getHeader()->getModule()->getDataLayout();
304 std::max(
DL.getTypeAllocSize(SrcTy),
DL.getTypeAllocSize(DstTy));
309 auto *Step = dyn_cast<SCEVConstant>(SinkAR->getStepRecurrence(*SE));
310 if (!Step || Step != SrcAR->getStepRecurrence(*SE) ||
311 Step->getAPInt().abs() != AllocSize) {
312 CanUseDiffCheck =
false;
321 if (Step->getValue()->isNegative())
326 if (isa<SCEVCouldNotCompute>(SinkStartInt) ||
327 isa<SCEVCouldNotCompute>(SrcStartInt)) {
328 CanUseDiffCheck =
false;
331 DiffChecks.emplace_back(SrcStartInt, SinkStartInt, AllocSize,
332 Src->NeedsFreeze ||
Sink->NeedsFreeze);
344 tryToCreateDiffCheck(CGI, CGJ);
345 Checks.
push_back(std::make_pair(&CGI, &CGJ));
352void RuntimePointerChecking::generateChecks(
355 groupChecks(DepCands, UseDependencies);
361 for (
unsigned I = 0, EI = M.Members.size(); EI !=
I; ++
I)
362 for (
unsigned J = 0, EJ =
N.Members.size(); EJ != J; ++J)
377 if (
C->getValue()->isNegative())
386 RtCheck.
Pointers[
Index].PointerValue->getType()->getPointerAddressSpace(),
395 "all pointers in a checking group must be in the same address space");
421void RuntimePointerChecking::groupChecks(
467 if (!UseDependencies) {
473 unsigned TotalComparisons = 0;
478 Iter.first->second.push_back(
Index);
507 auto PointerI = PositionMap.
find(
MI->getPointer());
509 "pointer in equivalence class not found in PositionMap");
510 for (
unsigned Pointer : PointerI->second) {
527 if (Group.addPointer(Pointer, *
this)) {
550 return (PtrToPartition[PtrIdx1] != -1 &&
551 PtrToPartition[PtrIdx1] == PtrToPartition[PtrIdx2]);
575 unsigned Depth)
const {
577 for (
const auto &
Check : Checks) {
578 const auto &First =
Check.first->Members, &Second =
Check.second->Members;
583 for (
unsigned K = 0; K < First.size(); ++K)
587 for (
unsigned K = 0; K < Second.size(); ++K)
602 OS.
indent(
Depth + 4) <<
"(Low: " << *CG.Low <<
" High: " << *CG.High
604 for (
unsigned J = 0; J < CG.Members.size(); ++J) {
617class AccessAnalysis {
626 : TheLoop(TheLoop), BAA(*AA), AST(BAA), LI(LI), DepCands(DA), PSE(PSE) {
628 BAA.enableCrossIterationMode();
635 Accesses[MemAccessInfo(
Ptr,
false)].insert(AccessTy);
637 ReadOnlyPtr.insert(
Ptr);
644 Accesses[MemAccessInfo(
Ptr,
true)].insert(AccessTy);
655 MemAccessInfo Access,
Type *AccessTy,
658 Loop *TheLoop,
unsigned &RunningDepId,
659 unsigned ASId,
bool ShouldCheckStride,
bool Assume);
668 Value *&UncomputablePtr,
bool ShouldCheckWrap =
false);
672 void buildDependenceSets() {
673 processMemAccesses();
681 bool isDependencyCheckNeeded() {
return !CheckDeps.empty(); }
689 MemAccessInfoList &getDependenciesToCheck() {
return CheckDeps; }
696 void processMemAccesses();
700 PtrAccessMap Accesses;
706 MemAccessInfoList CheckDeps;
732 bool IsRTCheckAnalysisNeeded =
false;
744 const SCEV *PtrScev,
Loop *L,
bool Assume) {
768 int64_t Stride =
getPtrStride(PSE, AccessTy,
Ptr, L, Strides).value_or(0);
781 while (!WorkList.
empty()) {
785 auto *PN = dyn_cast<PHINode>(
Ptr);
789 if (PN && InnermostLoop.
contains(PN->getParent()) &&
790 PN->getParent() != InnermostLoop.
getHeader()) {
791 for (
const Use &Inc : PN->incoming_values())
824 if (isa<SCEVAddRecExpr>(Scev) || L->isLoopInvariant(
Ptr) ||
825 !isa<Instruction>(
Ptr) ||
Depth == 0) {
836 auto GetBinOpExpr = [&SE](
unsigned Opcode,
const SCEV *L,
const SCEV *R) {
838 case Instruction::Add:
840 case Instruction::Sub:
848 unsigned Opcode =
I->getOpcode();
850 case Instruction::GetElementPtr: {
852 Type *SourceTy =
GEP->getSourceElementType();
855 if (
I->getNumOperands() != 2 || SourceTy->
isVectorTy()) {
865 bool NeedsFreeze =
any_of(BaseScevs, UndefPoisonCheck) ||
866 any_of(OffsetScevs, UndefPoisonCheck);
871 if (OffsetScevs.
size() == 2 && BaseScevs.
size() == 1)
873 else if (BaseScevs.
size() == 2 && OffsetScevs.
size() == 1)
876 ScevList.emplace_back(Scev, NeedsFreeze);
894 ScevList.emplace_back(SE->
getAddExpr(get<0>(BaseScevs[0]), Scaled1),
896 ScevList.emplace_back(SE->
getAddExpr(get<0>(BaseScevs[1]), Scaled2),
900 case Instruction::Select: {
907 if (ChildScevs.
size() == 2) {
908 ScevList.push_back(ChildScevs[0]);
909 ScevList.push_back(ChildScevs[1]);
914 case Instruction::Add:
915 case Instruction::Sub: {
923 any_of(LScevs, UndefPoisonCheck) ||
any_of(RScevs, UndefPoisonCheck);
928 if (LScevs.
size() == 2 && RScevs.
size() == 1)
930 else if (RScevs.
size() == 2 && LScevs.
size() == 1)
933 ScevList.emplace_back(Scev, NeedsFreeze);
937 ScevList.emplace_back(
938 GetBinOpExpr(Opcode, get<0>(LScevs[0]), get<0>(RScevs[0])),
940 ScevList.emplace_back(
941 GetBinOpExpr(Opcode, get<0>(LScevs[1]), get<0>(RScevs[1])),
947 LLVM_DEBUG(
dbgs() <<
"ForkedPtr unhandled instruction: " << *
I <<
"\n");
964 if (Scevs.
size() == 2 &&
965 (isa<SCEVAddRecExpr>(get<0>(Scevs[0])) ||
967 (isa<SCEVAddRecExpr>(get<0>(Scevs[1])) ||
979 MemAccessInfo Access,
Type *AccessTy,
982 Loop *TheLoop,
unsigned &RunningDepId,
983 unsigned ASId,
bool ShouldCheckWrap,
990 for (
auto &
P : TranslatedPtrs) {
991 const SCEV *PtrExpr = get<0>(
P);
997 if (ShouldCheckWrap) {
999 if (TranslatedPtrs.size() > 1)
1002 if (!
isNoWrap(PSE, StridesMap,
Ptr, AccessTy, TheLoop)) {
1004 if (!Assume || !isa<SCEVAddRecExpr>(Expr))
1011 if (TranslatedPtrs.size() == 1)
1016 for (
auto [PtrExpr, NeedsFreeze] : TranslatedPtrs) {
1020 if (isDependencyCheckNeeded()) {
1022 unsigned &LeaderId = DepSetId[Leader];
1024 LeaderId = RunningDepId++;
1028 DepId = RunningDepId++;
1030 bool IsWrite = Access.getInt();
1031 RtCheck.
insert(TheLoop,
Ptr, PtrExpr, AccessTy, IsWrite, DepId, ASId, PSE,
1042 Value *&UncomputablePtr,
bool ShouldCheckWrap) {
1045 bool CanDoRT =
true;
1047 bool MayNeedRTCheck =
false;
1048 if (!IsRTCheckAnalysisNeeded)
return true;
1050 bool IsDepCheckNeeded = isDependencyCheckNeeded();
1055 for (
auto &AS : AST) {
1056 int NumReadPtrChecks = 0;
1057 int NumWritePtrChecks = 0;
1058 bool CanDoAliasSetRT =
true;
1063 unsigned RunningDepId = 1;
1071 for (
const auto &
A : AS) {
1073 bool IsWrite = Accesses.count(MemAccessInfo(
Ptr,
true));
1076 ++NumWritePtrChecks;
1084 if (NumWritePtrChecks == 0 ||
1085 (NumWritePtrChecks == 1 && NumReadPtrChecks == 0)) {
1086 assert((AS.size() <= 1 ||
1089 MemAccessInfo AccessWrite(AC.getValue(),
true);
1090 return DepCands.
findValue(AccessWrite) == DepCands.
end();
1092 "Can only skip updating CanDoRT below, if all entries in AS "
1093 "are reads or there is at most 1 entry");
1097 for (
auto &Access : AccessInfos) {
1098 for (
const auto &AccessTy : Accesses[Access]) {
1099 if (!createCheckForAccess(RtCheck, Access, AccessTy, StridesMap,
1100 DepSetId, TheLoop, RunningDepId, ASId,
1101 ShouldCheckWrap,
false)) {
1103 << *Access.getPointer() <<
'\n');
1105 CanDoAliasSetRT =
false;
1119 bool NeedsAliasSetRTCheck = RunningDepId > 2 || !Retries.
empty();
1123 if (NeedsAliasSetRTCheck && !CanDoAliasSetRT) {
1127 CanDoAliasSetRT =
true;
1128 for (
auto Retry : Retries) {
1129 MemAccessInfo Access = Retry.first;
1130 Type *AccessTy = Retry.second;
1131 if (!createCheckForAccess(RtCheck, Access, AccessTy, StridesMap,
1132 DepSetId, TheLoop, RunningDepId, ASId,
1133 ShouldCheckWrap,
true)) {
1134 CanDoAliasSetRT =
false;
1135 UncomputablePtr = Access.getPointer();
1141 CanDoRT &= CanDoAliasSetRT;
1142 MayNeedRTCheck |= NeedsAliasSetRTCheck;
1151 unsigned NumPointers = RtCheck.
Pointers.size();
1152 for (
unsigned i = 0; i < NumPointers; ++i) {
1153 for (
unsigned j = i + 1;
j < NumPointers; ++
j) {
1155 if (RtCheck.
Pointers[i].DependencySetId ==
1156 RtCheck.
Pointers[j].DependencySetId)
1169 dbgs() <<
"LAA: Runtime check would require comparison between"
1170 " different address spaces\n");
1176 if (MayNeedRTCheck && CanDoRT)
1180 <<
" pointer comparisons.\n");
1187 bool CanDoRTIfNeeded = !RtCheck.
Need || CanDoRT;
1188 if (!CanDoRTIfNeeded)
1190 return CanDoRTIfNeeded;
1193void AccessAnalysis::processMemAccesses() {
1200 LLVM_DEBUG(
dbgs() <<
"LAA: Accesses(" << Accesses.size() <<
"):\n");
1202 for (
auto A : Accesses)
1203 dbgs() <<
"\t" << *
A.first.getPointer() <<
" ("
1204 << (
A.first.getInt()
1206 : (ReadOnlyPtr.count(
A.first.getPointer()) ?
"read-only"
1215 for (
const auto &AS : AST) {
1220 bool SetHasWrite =
false;
1224 UnderlyingObjToAccessMap ObjToLastAccess;
1227 PtrAccessMap DeferredAccesses;
1231 for (
int SetIteration = 0; SetIteration < 2; ++SetIteration) {
1232 bool UseDeferred = SetIteration > 0;
1233 PtrAccessMap &S = UseDeferred ? DeferredAccesses : Accesses;
1235 for (
const auto &AV : AS) {
1240 for (
const auto &AC : S) {
1241 if (AC.first.getPointer() !=
Ptr)
1244 bool IsWrite = AC.first.getInt();
1248 bool IsReadOnlyPtr = ReadOnlyPtr.count(
Ptr) && !IsWrite;
1249 if (UseDeferred && !IsReadOnlyPtr)
1253 assert(((IsReadOnlyPtr && UseDeferred) || IsWrite ||
1254 S.count(MemAccessInfo(
Ptr,
false))) &&
1255 "Alias-set pointer not in the access set?");
1257 MemAccessInfo Access(
Ptr, IsWrite);
1265 if (!UseDeferred && IsReadOnlyPtr) {
1268 DeferredAccesses.insert({Access, {}});
1276 if ((IsWrite || IsReadOnlyPtr) && SetHasWrite) {
1277 CheckDeps.push_back(Access);
1278 IsRTCheckAnalysisNeeded =
true;
1287 ValueVector TempObjects;
1291 <<
"Underlying objects for pointer " << *
Ptr <<
"\n");
1292 for (
const Value *UnderlyingObj : TempObjects) {
1295 if (isa<ConstantPointerNull>(UnderlyingObj) &&
1301 UnderlyingObjToAccessMap::iterator Prev =
1302 ObjToLastAccess.find(UnderlyingObj);
1303 if (Prev != ObjToLastAccess.end())
1304 DepCands.
unionSets(Access, Prev->second);
1306 ObjToLastAccess[UnderlyingObj] = Access;
1335 auto *
GEP = dyn_cast<GetElementPtrInst>(
Ptr);
1336 if (!
GEP || !
GEP->isInBounds())
1340 Value *NonConstIndex =
nullptr;
1342 if (!isa<ConstantInt>(
Index)) {
1345 NonConstIndex =
Index;
1353 if (
auto *OBO = dyn_cast<OverflowingBinaryOperator>(NonConstIndex))
1354 if (OBO->hasNoSignedWrap() &&
1357 isa<ConstantInt>(OBO->getOperand(1))) {
1358 auto *OpScev = PSE.
getSCEV(OBO->getOperand(0));
1360 if (
auto *OpAR = dyn_cast<SCEVAddRecExpr>(OpScev))
1361 return OpAR->getLoop() == L && OpAR->getNoWrapFlags(
SCEV::FlagNSW);
1372 bool Assume,
bool ShouldCheckWrap) {
1376 if (isa<ScalableVectorType>(AccessTy)) {
1377 LLVM_DEBUG(
dbgs() <<
"LAA: Bad stride - Scalable object: " << *AccessTy
1379 return std::nullopt;
1390 <<
" SCEV: " << *PtrScev <<
"\n");
1391 return std::nullopt;
1396 LLVM_DEBUG(
dbgs() <<
"LAA: Bad stride - Not striding over innermost loop "
1397 << *
Ptr <<
" SCEV: " << *AR <<
"\n");
1398 return std::nullopt;
1408 <<
" SCEV: " << *AR <<
"\n");
1409 return std::nullopt;
1413 TypeSize AllocSize =
DL.getTypeAllocSize(AccessTy);
1415 const APInt &APStepVal =
C->getAPInt();
1419 return std::nullopt;
1424 int64_t Stride = StepVal /
Size;
1425 int64_t Rem = StepVal %
Size;
1427 return std::nullopt;
1429 if (!ShouldCheckWrap)
1441 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(
Ptr);
1442 GEP &&
GEP->isInBounds() && (Stride == 1 || Stride == -1))
1450 (Stride == 1 || Stride == -1))
1456 <<
"LAA: Pointer: " << *
Ptr <<
"\n"
1457 <<
"LAA: SCEV: " << *AR <<
"\n"
1458 <<
"LAA: Added an overflow assumption\n");
1462 dbgs() <<
"LAA: Bad stride - Pointer may wrap in the address space "
1463 << *
Ptr <<
" SCEV: " << *AR <<
"\n");
1464 return std::nullopt;
1472 assert(PtrA && PtrB &&
"Expected non-nullptr pointers.");
1474 ->isOpaqueOrPointeeTypeMatches(ElemTyA) &&
"Wrong PtrA type");
1476 ->isOpaqueOrPointeeTypeMatches(ElemTyB) &&
"Wrong PtrB type");
1484 return std::nullopt;
1491 return std::nullopt;
1492 unsigned IdxWidth =
DL.getIndexSizeInBits(ASA);
1494 APInt OffsetA(IdxWidth, 0), OffsetB(IdxWidth, 0);
1499 if (PtrA1 == PtrB1) {
1502 ASA = cast<PointerType>(PtrA1->
getType())->getAddressSpace();
1503 ASB = cast<PointerType>(PtrB1->
getType())->getAddressSpace();
1506 return std::nullopt;
1508 IdxWidth =
DL.getIndexSizeInBits(ASA);
1509 OffsetA = OffsetA.sextOrTrunc(IdxWidth);
1519 dyn_cast<SCEVConstant>(SE.
getMinusSCEV(PtrSCEVB, PtrSCEVA));
1521 return std::nullopt;
1522 Val = Diff->getAPInt().getSExtValue();
1524 int Size =
DL.getTypeStoreSize(ElemTyA);
1525 int Dist = Val /
Size;
1529 if (!StrictCheck || Dist *
Size == Val)
1531 return std::nullopt;
1538 VL, [](
const Value *V) {
return V->getType()->isPointerTy(); }) &&
1539 "Expected list of pointer operands.");
1542 Value *Ptr0 = VL[0];
1544 using DistOrdPair = std::pair<int64_t, int>;
1546 std::set<DistOrdPair,
decltype(Compare)> Offsets(Compare);
1547 Offsets.emplace(0, 0);
1549 bool IsConsecutive =
true;
1558 auto Res = Offsets.emplace(
Offset, Cnt);
1562 IsConsecutive = IsConsecutive && std::next(Res.first) == Offsets.end();
1565 SortedIndices.
clear();
1566 if (!IsConsecutive) {
1570 for (
const std::pair<int64_t, int> &Pair : Offsets) {
1571 SortedIndices[Cnt] = Pair.second;
1587 std::optional<int> Diff =
1590 return Diff && *Diff == 1;
1596 Accesses[MemAccessInfo(Ptr, true)].push_back(AccessIdx);
1597 InstMap.push_back(SI);
1605 Accesses[MemAccessInfo(Ptr, false)].push_back(AccessIdx);
1606 InstMap.push_back(LI);
1633 case ForwardButPreventsForwarding:
1637 case BackwardVectorizable:
1639 case BackwardVectorizableButPreventsForwarding:
1652 case ForwardButPreventsForwarding:
1657 case BackwardVectorizable:
1659 case BackwardVectorizableButPreventsForwarding:
1665bool MemoryDepChecker::couldPreventStoreLoadForward(
uint64_t Distance,
1679 const uint64_t NumItersForStoreLoadThroughMemory = 8 * TypeByteSize;
1681 uint64_t MaxVFWithoutSLForwardIssues = std::min(
1685 for (
uint64_t VF = 2 * TypeByteSize; VF <= MaxVFWithoutSLForwardIssues;
1689 if (Distance % VF && Distance / VF < NumItersForStoreLoadThroughMemory) {
1690 MaxVFWithoutSLForwardIssues = (VF >> 1);
1695 if (MaxVFWithoutSLForwardIssues < 2 * TypeByteSize) {
1697 dbgs() <<
"LAA: Distance " << Distance
1698 <<
" that could cause a store-load forwarding conflict\n");
1702 if (MaxVFWithoutSLForwardIssues < MaxSafeDepDistBytes &&
1703 MaxVFWithoutSLForwardIssues !=
1705 MaxSafeDepDistBytes = MaxVFWithoutSLForwardIssues;
1727 const SCEV &BackedgeTakenCount,
1748 const uint64_t ByteStride = Stride * TypeByteSize;
1752 const SCEV *CastedDist = &Dist;
1753 const SCEV *CastedProduct = Product;
1760 if (DistTypeSizeBits > ProductTypeSizeBits)
1788 assert(Stride > 1 &&
"The stride must be greater than 1");
1789 assert(TypeByteSize > 0 &&
"The type size in byte must be non-zero");
1790 assert(Distance > 0 &&
"The distance must be non-zero");
1793 if (Distance % TypeByteSize)
1796 uint64_t ScaledDist = Distance / TypeByteSize;
1814 return ScaledDist % Stride;
1818MemoryDepChecker::isDependent(
const MemAccessInfo &
A,
unsigned AIdx,
1821 assert (AIdx < BIdx &&
"Must pass arguments in program order");
1823 auto [APtr, AIsWrite] =
A;
1824 auto [BPtr, BIsWrite] =
B;
1829 if (!AIsWrite && !BIsWrite)
1833 if (APtr->getType()->getPointerAddressSpace() !=
1834 BPtr->getType()->getPointerAddressSpace())
1837 int64_t StrideAPtr =
1838 getPtrStride(PSE, ATy, APtr, InnermostLoop, Strides,
true).value_or(0);
1839 int64_t StrideBPtr =
1840 getPtrStride(PSE, BTy, BPtr, InnermostLoop, Strides,
true).value_or(0);
1847 if (StrideAPtr < 0) {
1859 LLVM_DEBUG(
dbgs() <<
"LAA: Src Scev: " << *Src <<
"Sink Scev: " << *Sink
1860 <<
"(Induction step: " << StrideAPtr <<
")\n");
1861 LLVM_DEBUG(
dbgs() <<
"LAA: Distance for " << *InstMap[AIdx] <<
" to "
1862 << *InstMap[BIdx] <<
": " << *Dist <<
"\n");
1867 if (!StrideAPtr || !StrideBPtr || StrideAPtr != StrideBPtr){
1868 LLVM_DEBUG(
dbgs() <<
"Pointer access with non-constant stride\n");
1873 uint64_t TypeByteSize =
DL.getTypeAllocSize(ATy);
1875 DL.getTypeStoreSizeInBits(ATy) ==
DL.getTypeStoreSizeInBits(BTy);
1876 uint64_t Stride = std::abs(StrideAPtr);
1878 if (!isa<SCEVCouldNotCompute>(Dist) && HasSameSize &&
1880 Stride, TypeByteSize))
1885 LLVM_DEBUG(
dbgs() <<
"LAA: Dependence because of non-constant distance\n");
1886 FoundNonConstantDistanceDependence =
true;
1890 const APInt &Val =
C->getAPInt();
1894 if (std::abs(Distance) > 0 && Stride > 1 && HasSameSize &&
1902 bool IsTrueDataDependence = (AIsWrite && !BIsWrite);
1904 (couldPreventStoreLoadForward(Val.
abs().
getZExtValue(), TypeByteSize) ||
1906 LLVM_DEBUG(
dbgs() <<
"LAA: Forward but may prevent st->ld forwarding\n");
1919 dbgs() <<
"LAA: Zero dependence difference but different type sizes\n");
1926 LLVM_DEBUG(
dbgs() <<
"LAA: ReadWrite-Write positive dependency with "
1927 "different type sizes\n");
1937 unsigned MinNumIter = std::max(ForcedFactor * ForcedUnroll, 2U);
1966 TypeByteSize * Stride * (MinNumIter - 1) + TypeByteSize;
1967 if (MinDistanceNeeded >
static_cast<uint64_t>(Distance)) {
1968 LLVM_DEBUG(
dbgs() <<
"LAA: Failure because of positive distance "
1969 << Distance <<
'\n');
1974 if (MinDistanceNeeded > MaxSafeDepDistBytes) {
1976 << MinDistanceNeeded <<
" size in bytes\n");
1996 MaxSafeDepDistBytes =
1997 std::min(
static_cast<uint64_t>(Distance), MaxSafeDepDistBytes);
1999 bool IsTrueDataDependence = (!AIsWrite && BIsWrite);
2001 couldPreventStoreLoadForward(Distance, TypeByteSize))
2004 uint64_t MaxVF = MaxSafeDepDistBytes / (TypeByteSize * Stride);
2006 <<
" with max VF = " << MaxVF <<
'\n');
2007 uint64_t MaxVFInBits = MaxVF * TypeByteSize * 8;
2008 MaxSafeVectorWidthInBits = std::min(MaxSafeVectorWidthInBits, MaxVFInBits);
2016 MaxSafeDepDistBytes = -1;
2019 if (Visited.
count(CurAccess))
2035 bool AIIsWrite = AI->getInt();
2039 (AIIsWrite ? AI : std::next(AI));
2042 for (std::vector<unsigned>::iterator I1 = Accesses[*AI].begin(),
2043 I1E = Accesses[*AI].
end(); I1 != I1E; ++I1)
2046 for (std::vector<unsigned>::iterator
2047 I2 = (OI == AI ? std::next(I1) : Accesses[*OI].begin()),
2048 I2E = (OI == AI ? I1E : Accesses[*OI].end());
2050 auto A = std::make_pair(&*AI, *I1);
2051 auto B = std::make_pair(&*OI, *I2);
2058 isDependent(*
A.first,
A.second, *
B.first,
B.second, Strides);
2065 if (RecordDependences) {
2070 RecordDependences =
false;
2071 Dependences.clear();
2073 <<
"Too many dependences, stopped recording\n");
2085 LLVM_DEBUG(
dbgs() <<
"Total Dependences: " << Dependences.size() <<
"\n");
2092 auto &IndexVector = Accesses.find(Access)->second;
2096 std::back_inserter(Insts),
2097 [&](
unsigned Idx) {
return this->InstMap[
Idx]; });
2102 "NoDep",
"Unknown",
"Forward",
"ForwardButPreventsForwarding",
"Backward",
2103 "BackwardVectorizable",
"BackwardVectorizableButPreventsForwarding"};
2113bool LoopAccessInfo::canAnalyzeLoop() {
2122 recordAnalysis(
"NotInnerMostLoop") <<
"loop is not the innermost loop";
2129 dbgs() <<
"LAA: loop control flow is not understood by analyzer\n");
2130 recordAnalysis(
"CFGNotUnderstood")
2131 <<
"loop control flow is not understood by analyzer";
2137 if (isa<SCEVCouldNotCompute>(ExitCount)) {
2138 recordAnalysis(
"CantComputeNumberOfIterations")
2139 <<
"could not determine number of loop iterations";
2140 LLVM_DEBUG(
dbgs() <<
"LAA: SCEV could not compute the loop exit count.\n");
2155 unsigned NumReads = 0;
2156 unsigned NumReadWrites = 0;
2158 bool HasComplexMemInst =
false;
2161 HasConvergentOp =
false;
2163 PtrRtChecking->Pointers.
clear();
2164 PtrRtChecking->Need =
false;
2168 const bool EnableMemAccessVersioningOfLoop =
2180 if (
auto *Call = dyn_cast<CallBase>(&
I)) {
2181 if (
Call->isConvergent())
2182 HasConvergentOp =
true;
2187 if (HasComplexMemInst && HasConvergentOp) {
2193 if (HasComplexMemInst)
2199 if (
I.mayReadFromMemory()) {
2203 auto *
Call = dyn_cast<CallInst>(&
I);
2209 if (Call && !
Call->isNoBuiltin() &&
Call->getCalledFunction() &&
2213 auto *Ld = dyn_cast<LoadInst>(&
I);
2215 recordAnalysis(
"CantVectorizeInstruction", Ld)
2216 <<
"instruction cannot be vectorized";
2217 HasComplexMemInst =
true;
2220 if (!Ld->isSimple() && !IsAnnotatedParallel) {
2221 recordAnalysis(
"NonSimpleLoad", Ld)
2222 <<
"read with atomic ordering or volatile read";
2224 HasComplexMemInst =
true;
2229 DepChecker->addAccess(Ld);
2230 if (EnableMemAccessVersioningOfLoop)
2231 collectStridedAccess(Ld);
2236 if (
I.mayWriteToMemory()) {
2237 auto *St = dyn_cast<StoreInst>(&
I);
2239 recordAnalysis(
"CantVectorizeInstruction", St)
2240 <<
"instruction cannot be vectorized";
2241 HasComplexMemInst =
true;
2244 if (!St->isSimple() && !IsAnnotatedParallel) {
2245 recordAnalysis(
"NonSimpleStore", St)
2246 <<
"write with atomic ordering or volatile write";
2248 HasComplexMemInst =
true;
2253 DepChecker->addAccess(St);
2254 if (EnableMemAccessVersioningOfLoop)
2255 collectStridedAccess(St);
2260 if (HasComplexMemInst) {
2270 if (!Stores.
size()) {
2277 AccessAnalysis Accesses(TheLoop, AA, LI, DependentAccesses, *PSE);
2293 if (isInvariant(
Ptr)) {
2295 StoresToInvariantAddresses.push_back(ST);
2296 HasDependenceInvolvingLoopInvariantAddress |=
2303 if (Seen.
insert({Ptr, AccessTy}).second) {
2310 if (blockNeedsPredication(
ST->getParent(), TheLoop, DT))
2314 [&Accesses, AccessTy, Loc](
Value *
Ptr) {
2315 MemoryLocation NewLoc = Loc.getWithNewPtr(Ptr);
2316 Accesses.addStore(NewLoc, AccessTy);
2321 if (IsAnnotatedParallel) {
2323 dbgs() <<
"LAA: A loop annotated parallel, ignore memory dependency "
2339 bool IsReadOnlyPtr =
false;
2341 if (Seen.
insert({Ptr, AccessTy}).second ||
2342 !
getPtrStride(*PSE,
LD->getType(),
Ptr, TheLoop, SymbolicStrides).value_or(0)) {
2344 IsReadOnlyPtr =
true;
2350 LLVM_DEBUG(
dbgs() <<
"LAA: Found an unsafe dependency between a uniform "
2351 "load and uniform store to the same address!\n");
2352 HasDependenceInvolvingLoopInvariantAddress =
true;
2359 if (blockNeedsPredication(
LD->getParent(), TheLoop, DT))
2363 [&Accesses, AccessTy, Loc, IsReadOnlyPtr](
Value *
Ptr) {
2364 MemoryLocation NewLoc = Loc.getWithNewPtr(Ptr);
2365 Accesses.addLoad(NewLoc, AccessTy, IsReadOnlyPtr);
2371 if (NumReadWrites == 1 && NumReads == 0) {
2379 Accesses.buildDependenceSets();
2383 Value *UncomputablePtr =
nullptr;
2384 bool CanDoRTIfNeeded =
2385 Accesses.canCheckPtrAtRT(*PtrRtChecking, PSE->
getSE(), TheLoop,
2386 SymbolicStrides, UncomputablePtr,
false);
2387 if (!CanDoRTIfNeeded) {
2388 auto *
I = dyn_cast_or_null<Instruction>(UncomputablePtr);
2389 recordAnalysis(
"CantIdentifyArrayBounds",
I)
2390 <<
"cannot identify array bounds";
2391 LLVM_DEBUG(
dbgs() <<
"LAA: We can't vectorize because we can't find "
2392 <<
"the array bounds.\n");
2398 dbgs() <<
"LAA: May be able to perform a memory runtime check if needed.\n");
2401 if (Accesses.isDependencyCheckNeeded()) {
2403 CanVecMem = DepChecker->areDepsSafe(
2404 DependentAccesses, Accesses.getDependenciesToCheck(), SymbolicStrides);
2405 MaxSafeDepDistBytes = DepChecker->getMaxSafeDepDistBytes();
2407 if (!CanVecMem && DepChecker->shouldRetryWithRuntimeCheck()) {
2411 Accesses.resetDepChecks(*DepChecker);
2413 PtrRtChecking->reset();
2414 PtrRtChecking->Need =
true;
2416 auto *SE = PSE->
getSE();
2417 UncomputablePtr =
nullptr;
2418 CanDoRTIfNeeded = Accesses.canCheckPtrAtRT(
2419 *PtrRtChecking, SE, TheLoop, SymbolicStrides, UncomputablePtr,
true);
2422 if (!CanDoRTIfNeeded) {
2423 auto *
I = dyn_cast_or_null<Instruction>(UncomputablePtr);
2424 recordAnalysis(
"CantCheckMemDepsAtRunTime",
I)
2425 <<
"cannot check memory dependencies at runtime";
2426 LLVM_DEBUG(
dbgs() <<
"LAA: Can't vectorize with memory checks\n");
2435 if (HasConvergentOp) {
2436 recordAnalysis(
"CantInsertRuntimeCheckWithConvergent")
2437 <<
"cannot add control dependency to convergent operation";
2438 LLVM_DEBUG(
dbgs() <<
"LAA: We can't vectorize because a runtime check "
2439 "would be needed with a convergent operation\n");
2446 dbgs() <<
"LAA: No unsafe dependent memory operations in loop. We"
2447 << (PtrRtChecking->Need ?
"" :
" don't")
2448 <<
" need runtime memory checks.\n");
2450 emitUnsafeDependenceRemark();
2453void LoopAccessInfo::emitUnsafeDependenceRemark() {
2454 auto Deps = getDepChecker().getDependences();
2461 if (Found == Deps->end())
2465 LLVM_DEBUG(
dbgs() <<
"LAA: unsafe dependent memory operations in loop\n");
2470 <<
"unsafe dependent memory operations in loop. Use "
2471 "#pragma loop distribute(enable) to allow loop distribution "
2472 "to attempt to isolate the offending operations into a separate "
2481 R <<
"\nBackward loop carried data dependence.";
2484 R <<
"\nForward loop carried data dependence that prevents "
2485 "store-to-load forwarding.";
2488 R <<
"\nBackward loop carried data dependence that prevents "
2489 "store-to-load forwarding.";
2492 R <<
"\nUnknown data dependence.";
2499 SourceLoc = DD->getDebugLoc();
2501 R <<
" Memory location is the same as accessed at "
2502 <<
ore::NV(
"Location", SourceLoc);
2517 assert(!Report &&
"Multiple reports generated");
2523 CodeRegion =
I->getParent();
2526 if (
I->getDebugLoc())
2527 DL =
I->getDebugLoc();
2530 Report = std::make_unique<OptimizationRemarkAnalysis>(
DEBUG_TYPE, RemarkName,
DL,
2536 auto *SE = PSE->
getSE();
2557 std::advance(GEPTI, LastOperand - 2);
2581 for (
unsigned i = 0, e =
GEP->getNumOperands(); i != e; ++i)
2582 if (i != InductionOperand &&
2585 return GEP->getOperand(InductionOperand);
2590 Value *UniqueCast =
nullptr;
2591 for (
User *U :
Ptr->users()) {
2592 CastInst *CI = dyn_cast<CastInst>(U);
2593 if (CI && CI->
getType() == Ty) {
2606 auto *PtrTy = dyn_cast<PointerType>(
Ptr->getType());
2607 if (!PtrTy || PtrTy->isAggregateType())
2616 int64_t PtrAccessSize = 1;
2624 V =
C->getOperand();
2641 if (OrigPtr ==
Ptr) {
2642 if (
const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(V)) {
2643 if (M->getOperand(0)->getSCEVType() !=
scConstant)
2646 const APInt &APStepVal = cast<SCEVConstant>(M->getOperand(0))->getAPInt();
2653 if (PtrAccessSize != StepVal)
2655 V = M->getOperand(1);
2667 const auto *
C = dyn_cast<SCEVIntegralCastExpr>(V);
2670 U = dyn_cast<SCEVUnknown>(
C->getOperand());
2682void LoopAccessInfo::collectStridedAccess(
Value *MemAccess) {
2697 LLVM_DEBUG(
dbgs() <<
"LAA: Found a strided access that is a candidate for "
2702 LLVM_DEBUG(
dbgs() <<
" Chose not to due to -laa-speculate-unit-stride\n");
2727 const SCEV *CastedStride = StrideExpr;
2728 const SCEV *CastedBECount = BETakenCount;
2730 if (BETypeSizeBits >= StrideTypeSizeBits)
2734 const SCEV *StrideMinusBETaken = SE->
getMinusSCEV(CastedStride, CastedBECount);
2740 dbgs() <<
"LAA: Stride>=TripCount; No point in versioning as the "
2741 "Stride==1 predicate will imply that the loop executes "
2745 LLVM_DEBUG(
dbgs() <<
"LAA: Found a strided access that we can version.\n");
2749 const SCEV *StrideBase = StrideExpr;
2750 if (
const auto *
C = dyn_cast<SCEVIntegralCastExpr>(StrideBase))
2751 StrideBase =
C->getOperand();
2752 SymbolicStrides[
Ptr] = cast<SCEVUnknown>(StrideBase);
2759 PtrRtChecking(nullptr),
2761 PtrRtChecking = std::make_unique<RuntimePointerChecking>(*DepChecker, SE);
2762 if (canAnalyzeLoop()) {
2763 analyzeLoop(AA, LI, TLI, DT);
2770 if (MaxSafeDepDistBytes != -1ULL)
2771 OS <<
" with a maximum dependence distance of " << MaxSafeDepDistBytes
2773 if (PtrRtChecking->Need)
2774 OS <<
" with run-time checks";
2778 if (HasConvergentOp)
2784 if (
auto *Dependences = DepChecker->getDependences()) {
2786 for (
const auto &Dep : *Dependences) {
2787 Dep.
print(
OS,
Depth + 2, DepChecker->getMemoryInstructions());
2794 PtrRtChecking->print(
OS,
Depth);
2797 OS.
indent(
Depth) <<
"Non vectorizable stores to invariant address were "
2798 << (HasDependenceInvolvingLoopInvariantAddress ?
"" :
"not ")
2799 <<
"found in loop.\n";
2811 auto I = LoopAccessInfoMap.insert({&L,
nullptr});
2815 std::make_unique<LoopAccessInfo>(&L, &SE, TLI, &AA, &DT, &LI);
2817 return *
I.first->second;
2825 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
2826 auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
2827 auto *TLI = TLIP ? &TLIP->getTLI(
F) :
nullptr;
2828 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
2829 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2830 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
2831 LAIs = std::make_unique<LoopAccessInfoManager>(SE, AA, DT, LI, TLI);
2874#define LAA_NAME "loop-accesses"
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file implements a class to represent arbitrary precision integral constant values and operations...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
Generic implementation of equivalence classes through the use Tarjan's efficient union-find algorithm...
static cl::opt< unsigned > MaxDependences("max-dependences", cl::Hidden, cl::desc("Maximum number of dependences collected by " "loop-access analysis (default = 100)"), cl::init(100))
We collect dependences up to this threshold.
static cl::opt< bool > EnableForwardingConflictDetection("store-to-load-forwarding-conflict-detection", cl::Hidden, cl::desc("Enable conflict detection in loop-access analysis"), cl::init(true))
Enable store-to-load forwarding conflict detection.
static void findForkedSCEVs(ScalarEvolution *SE, const Loop *L, Value *Ptr, SmallVectorImpl< PointerIntPair< const SCEV *, 1, bool > > &ScevList, unsigned Depth)
static bool hasComputableBounds(PredicatedScalarEvolution &PSE, Value *Ptr, const SCEV *PtrScev, Loop *L, bool Assume)
Check whether a pointer can participate in a runtime bounds check.
static cl::opt< unsigned > MemoryCheckMergeThreshold("memory-check-merge-threshold", cl::Hidden, cl::desc("Maximum number of comparisons done when trying to merge " "runtime memory checks. (default = 100)"), cl::init(100))
The maximum iterations used to merge memory checks.
static bool isNoWrap(PredicatedScalarEvolution &PSE, const DenseMap< Value *, const SCEV * > &Strides, Value *Ptr, Type *AccessTy, Loop *L)
Check whether a pointer address cannot wrap.
static const SCEV * getStrideFromPointer(Value *Ptr, ScalarEvolution *SE, Loop *Lp)
Get the stride of a pointer access in a loop.
static unsigned getGEPInductionOperand(const GetElementPtrInst *Gep)
Find the operand of the GEP that should be checked for consecutive stores.
static cl::opt< unsigned, true > VectorizationInterleave("force-vector-interleave", cl::Hidden, cl::desc("Sets the vectorization interleave count. " "Zero is autoselect."), cl::location(VectorizerParams::VectorizationInterleave))
static Value * getUniqueCastUse(Value *Ptr, Loop *Lp, Type *Ty)
If a value has only one user that is a CastInst, return it.
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 const char laa_name[]
static cl::opt< unsigned, true > RuntimeMemoryCheckThreshold("runtime-memory-check-threshold", cl::Hidden, cl::desc("When performing memory disambiguation checks at runtime do not " "generate more than this number of comparisons (default = 8)."), cl::location(VectorizerParams::RuntimeMemoryCheckThreshold), cl::init(8))
static void visitPointers(Value *StartPtr, const Loop &InnermostLoop, function_ref< void(Value *)> AddPointer)
static bool isNoWrapAddRec(Value *Ptr, const SCEVAddRecExpr *AR, PredicatedScalarEvolution &PSE, const Loop *L)
Return true if an AddRec pointer Ptr is unsigned non-wrapping, i.e.
static Value * stripGetElementPtr(Value *Ptr, ScalarEvolution *SE, Loop *Lp)
If the argument is a GEP, then returns the operand identified by getGEPInductionOperand.
static bool isSafeDependenceDistance(const DataLayout &DL, ScalarEvolution &SE, const SCEV &BackedgeTakenCount, const SCEV &Dist, uint64_t Stride, uint64_t TypeByteSize)
Given a dependence-distance Dist between two memory accesses, that have the same stride whose absolut...
static bool areStridedAccessesIndependent(uint64_t Distance, uint64_t Stride, uint64_t TypeByteSize)
Check the dependence for two accesses with the same stride Stride.
static const SCEV * getMinFromExprs(const SCEV *I, const SCEV *J, ScalarEvolution *SE)
Compare I and J and return the minimum.
static cl::opt< unsigned > MaxForkedSCEVDepth("max-forked-scev-depth", cl::Hidden, cl::desc("Maximum recursion depth when finding forked SCEVs (default = 5)"), cl::init(5))
static cl::opt< bool > SpeculateUnitStride("laa-speculate-unit-stride", cl::Hidden, cl::desc("Speculate that non-constant strides are unit in LAA"), cl::init(true))
static SmallVector< PointerIntPair< const SCEV *, 1, bool > > findForkedPointer(PredicatedScalarEvolution &PSE, const DenseMap< Value *, const SCEV * > &StridesMap, Value *Ptr, const Loop *L)
static cl::opt< bool > EnableMemAccessVersioning("enable-mem-access-versioning", cl::init(true), cl::Hidden, cl::desc("Enable symbolic stride memory access versioning"))
This enables versioning on the strides of symbolically striding memory accesses in code like the foll...
This header provides classes for managing per-loop analyses.
This file provides utility analysis objects describing memory locations.
FunctionAnalysisManager FAM
This header defines various interfaces for pass management in LLVM.
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
This file defines the PointerIntPair class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckType(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N, const TargetLowering *TLI, const DataLayout &DL)
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SmallSet class.
This file defines the SmallVector class.
static SymbolRef::Type getType(const Symbol *Sym)
static const X86InstrFMA3Group Groups[]
A manager for alias analyses.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Class for arbitrary precision integers.
uint64_t getZExtValue() const
Get zero extended value.
APInt abs() const
Get the absolute value.
unsigned getBitWidth() const
Return the number of bits in the APInt.
bool isNegative() const
Determine sign of this APInt.
APInt sextOrTrunc(unsigned width) const
Sign extend or truncate to width.
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
int64_t getSExtValue() const
Get sign extended value.
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
API to communicate dependencies between analyses during invalidation.
bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Trigger the invalidation of some other analysis pass if not already handled and return whether it was...
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
AnalysisUsage & addRequiredTransitive()
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
ArrayRef< T > drop_front(size_t N=1) const
Drop the first N elements of the array.
size_t size() const
size - Get the array size.
bool empty() const
empty - Check if the array is empty.
LLVM Basic Block Representation.
const Function * getParent() const
Return the enclosing method, or null if none.
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
This is the base class for all instructions that perform data casts.
A parsed version of the target data layout string in and methods for querying it.
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Analysis pass which computes a DominatorTree.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient...
iterator findValue(const ElemTy &V) const
findValue - Return an iterator to the specified value.
iterator insert(const ElemTy &Data)
insert - Insert a new value into the union/find set, ignoring the request if the value already exists...
member_iterator member_end() const
typename std::set< ECValue, ECValueComparator >::const_iterator iterator
iterator* - Provides a way to iterate over all values in the set.
member_iterator member_begin(iterator I) const
member_iterator unionSets(const ElemTy &V1, const ElemTy &V2)
union - Merge the two equivalence sets for the specified values, inserting them if they do not alread...
const ElemTy & getLeaderValue(const ElemTy &V) const
getLeaderValue - Return the leader for the specified value that is in the set.
FunctionPass class - This class is used to implement most global optimizations.
bool hasOptSize() const
Optimize this function for size (-Os) or minimum size (-Oz).
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Type * getResultElementType() const
PointerType * getType() const
Global values are always pointers.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Class to represent integer types.
static 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.
Result run(Function &F, FunctionAnalysisManager &AM)
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
const LoopAccessInfo & getInfo(Loop &L)
Drive the analysis of memory accesses in the loop.
bool isInvariant(Value *V) const
Returns true if value V is loop invariant.
void print(raw_ostream &OS, unsigned Depth=0) const
Print the information about the memory accesses in the loop.
LoopAccessInfo(Loop *L, ScalarEvolution *SE, const TargetLibraryInfo *TLI, AAResults *AA, DominatorTree *DT, LoopInfo *LI)
static bool blockNeedsPredication(BasicBlock *BB, Loop *TheLoop, DominatorTree *DT)
Return true if the block BB needs to be predicated in order for the loop to be vectorized.
This analysis provides dependence information for the memory accesses of a loop.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
LoopAccessLegacyAnalysis()
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
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.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
bool isInnermost() const
Return true if the loop does not contain any (natural) loops.
unsigned getNumBackEdges() const
Calculate the number of back edges to the loop header.
BlockT * getHeader() const
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
The legacy pass manager's analysis pass to compute loop information.
Represents a single loop in the control flow graph.
bool isAnnotatedParallel() const
Returns true if the loop is annotated parallel.
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
This class implements a map that also provides access to all stored values in a deterministic order.
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).
const Loop * getInnermostLoop() const
bool isSafeForVectorization() const
No memory dependence was encountered that would inhibit vectorization.
bool areDepsSafe(DepCandidates &AccessSets, MemAccessInfoList &CheckDeps, const DenseMap< Value *, const SCEV * > &Strides)
Check whether the dependencies between the accesses are safe.
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
void addAccess(StoreInst *SI)
Register the location (instructions are given increasing numbers) of a write access.
PointerIntPair< Value *, 1, bool > MemAccessInfo
Representation for a specific memory location.
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
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.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
void addPredicate(const SCEVPredicate &Pred)
Adds a new predicate.
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
const SCEVPredicate & getPredicate() const
bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Returns true if we've proved that V doesn't wrap by means of a SCEV predicate.
void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Proves that V doesn't overflow by adding SCEV predicate.
void print(raw_ostream &OS, unsigned Depth) const
Print the SCEV mappings done by the Predicated Scalar Evolution.
const SCEVAddRecExpr * getAsAddRec(Value *V)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
const SCEV * getBackedgeTakenCount()
Get the (predicated) backedge count for the analyzed loop.
const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
A set of analyses that are preserved following a run of a transformation pass.
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.
void printChecks(raw_ostream &OS, const SmallVectorImpl< RuntimePointerCheck > &Checks, unsigned Depth=0) const
Print Checks.
bool needsChecking(const RuntimeCheckingPtrGroup &M, const RuntimeCheckingPtrGroup &N) const
Decide if we need to add a check between two groups of pointers, according to needsChecking.
void print(raw_ostream &OS, unsigned Depth=0) const
Print the list run-time memory checks necessary.
SmallVector< RuntimeCheckingPtrGroup, 2 > CheckingGroups
Holds a partitioning of pointers into "check groups".
void generateChecks(MemoryDepChecker::DepCandidates &DepCands, bool UseDependencies)
Generate the checks and store it.
friend struct RuntimeCheckingPtrGroup
static bool arePointersInSamePartition(const SmallVectorImpl< int > &PtrToPartition, unsigned PtrIdx1, unsigned PtrIdx2)
Check if pointers are in the same partition.
SmallVector< PointerInfo, 2 > Pointers
Information about the pointers that may require checking.
void insert(Loop *Lp, Value *Ptr, const SCEV *PtrExpr, Type *AccessTy, bool WritePtr, unsigned DepSetId, unsigned ASId, PredicatedScalarEvolution &PSE, bool NeedsFreeze)
Insert a pointer and calculate the start and end SCEVs.
This node represents a polynomial recurrence on the trip count of the specified loop.
const SCEV * getStart() const
const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
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.
This is the base class for unary integral cast operator classes.
This node represents multiplication of some number of SCEVs.
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
virtual void print(raw_ostream &OS, unsigned Depth=0) const =0
Prints a textual representation of this predicate with an indentation of Depth.
This 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.
Type * getType() const
Return the LLVM type of this SCEV expression.
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
const SCEV * getUMaxExpr(const SCEV *LHS, const SCEV *RHS)
const SCEVPredicate * getEqualPredicate(const SCEV *LHS, const SCEV *RHS)
const SCEV * getConstant(ConstantInt *V)
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
const SCEV * getPtrToIntExpr(const SCEV *Op, Type *Ty)
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
bool isKnownPositive(const SCEV *S)
Test if the given expression is known to be positive.
const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
Type * getEffectiveSCEVType(Type *Ty) const
Return a type with the same bitwidth as the given type and which represents how SCEV will treat the g...
const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
const SCEV * getStoreSizeOfExpr(Type *IntTy, Type *StoreTy)
Return an expression for the store size of StoreTy that is type IntTy.
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
const SCEV * getSizeOfExpr(Type *IntTy, TypeSize Size)
Return an expression for a TypeSize.
const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
const SCEV * getTruncateOrSignExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
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...
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
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 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.
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.
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
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.
const Value * stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL, APInt &Offset) const
This is a wrapper around stripAndAccumulateConstantOffsets with the in-bounds requirement set to fals...
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.
Type * getIndexedType() const
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.
friend const_iterator end(StringRef path)
Get end iterator over path.
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
bool match(Val *V, const Pattern &P)
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
initializer< Ty > init(const Ty &Val)
LocationClass< Ty > location(Ty &L)
DiagnosticInfoOptimizationBase::Argument NV
This is an optimization pass for GlobalISel generic memory operations.
std::optional< int > getPointersDiff(Type *ElemTyA, Value *PtrA, Type *ElemTyB, Value *PtrB, const DataLayout &DL, ScalarEvolution &SE, bool StrictCheck=false, bool CheckType=true)
Returns the distance between the pointers PtrA and PtrB iff they are compatible and it is possible to...
@ Low
Lower the current thread's priority such that it does not affect foreground tasks significantly.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Intrinsic::ID getVectorIntrinsicIDForCall(const CallInst *CI, const TargetLibraryInfo *TLI)
Returns intrinsic ID for call.
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
void initializeLoopAccessLegacyAnalysisPass(PassRegistry &)
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
OutputIt transform(R &&Range, OutputIt d_first, UnaryFunction F)
Wrapper function around std::transform to apply a function to a range and store the result elsewhere.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
std::optional< int64_t > getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr, const Loop *Lp, const DenseMap< Value *, const SCEV * > &StridesMap=DenseMap< Value *, const SCEV * >(), bool Assume=false, bool ShouldCheckWrap=true)
If the pointer has a constant stride return it in units of the access type size.
bool sortPtrAccesses(ArrayRef< Value * > VL, Type *ElemTy, const DataLayout &DL, ScalarEvolution &SE, SmallVectorImpl< unsigned > &SortedIndices)
Attempt to sort the pointers in VL and return the sorted indices in SortedIndices,...
void getUnderlyingObjects(const Value *V, SmallVectorImpl< const Value * > &Objects, LoopInfo *LI=nullptr, unsigned MaxLookup=6)
This method is similar to getUnderlyingObject except that it can look through phi and select instruct...
const SCEV * replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE, const DenseMap< Value *, const SCEV * > &PtrToStride, Value *Ptr)
Return the SCEV corresponding to a pointer with the symbolic stride replaced with constant one,...
bool isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL, ScalarEvolution &SE, bool CheckType=true)
Returns true if the memory operations A and B are consecutive.
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
OutputIt copy(R &&Range, OutputIt Out)
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
gep_type_iterator gep_type_begin(const User *GEP)
Type * getLoadStoreType(Value *I)
A helper function that returns the type of a load or store instruction.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
MDNode * TBAA
The tag for type-based alias analysis.
A special type used by analysis passes to provide an address that identifies that particular analysis...
Dependece between memory access instructions.
DepType Type
The type of the dependence.
bool isPossiblyBackward() const
May be a lexically backward dependence type (includes Unknown).
bool isForward() const
Lexically forward dependence.
bool isBackward() const
Lexically backward dependence.
void print(raw_ostream &OS, unsigned Depth, const SmallVectorImpl< Instruction * > &Instrs) const
Print the dependence.
Instruction * getDestination(const LoopAccessInfo &LAI) const
Return the destination instruction of the dependence.
Instruction * getSource(const LoopAccessInfo &LAI) const
Return the source instruction of the dependence.
DepType
The type of the dependence.
@ BackwardVectorizableButPreventsForwarding
@ ForwardButPreventsForwarding
static const char * DepName[]
String version of the types.
static VectorizationSafetyStatus isSafeForVectorization(DepType Type)
Dependence types that don't prevent vectorization.
unsigned AddressSpace
Address space of the involved pointers.
bool addPointer(unsigned Index, RuntimePointerChecking &RtCheck)
Tries to add the pointer recorded in RtCheck at index Index to this pointer checking group.
bool NeedsFreeze
Whether the pointer needs to be frozen after expansion, e.g.
const SCEV * High
The SCEV expression which represents the upper bound of all the pointers in this group.
SmallVector< unsigned, 2 > Members
Indices of all the pointers that constitute this grouping.
RuntimeCheckingPtrGroup(unsigned Index, RuntimePointerChecking &RtCheck)
Create a new pointer checking group containing a single pointer, with index Index in RtCheck.
const SCEV * Low
The SCEV expression which represents the lower bound of all the pointers in this group.
bool IsWritePtr
Holds the information if this pointer is used for writing to memory.
unsigned DependencySetId
Holds the id of the set of pointers that could be dependent because of a shared underlying object.
unsigned AliasSetId
Holds the id of the disjoint alias set to which this pointer belongs.
static const unsigned MaxVectorWidth
Maximum SIMD width.
static unsigned VectorizationFactor
VF as overridden by the user.
static unsigned RuntimeMemoryCheckThreshold
\When performing memory disambiguation checks at runtime do not make more than this number of compari...
static bool isInterleaveForced()
True if force-vector-interleave was specified by the user.
static unsigned VectorizationInterleave
Interleave factor as overridden by the user.
Function object to check whether the first component of a container supported by std::get (like std::...