60 return Opts.vplan_print_before_all || Opts.vplan_print_after_all ||
61 !Opts.vplan_print_before.empty() || !Opts.vplan_print_after.empty();
67 bool All = After ? Opts.vplan_print_after_all : Opts.vplan_print_before_all;
69 After ? Opts.vplan_print_after : Opts.vplan_print_before;
74 dbgs() <<
"VPlan for loop in '" << Fn->
getName() <<
"' "
75 << (After ?
"after" :
"before") <<
" " << NumberedPassName <<
'\n';
79 dbgs() << Plan <<
'\n';
97 auto IsConsecutiveAccess = [&](
VPValue *Addr,
Type *AccessTy) {
106 if (!VPBB->getParent())
109 auto EndIter = Term ? Term->getIterator() : VPBB->end();
114 VPValue *VPV = Ingredient.getVPSingleValue();
130 IsConsecutiveAccess(VPI->getOperand(0), VPI->getScalarType());
132 *
Load, Ingredient.getOperand(0),
nullptr , IsConsecutive,
133 Load->getAlign(), *VPI, Ingredient.getDebugLoc());
135 bool IsConsecutive = IsConsecutiveAccess(
136 VPI->getOperand(1), VPI->getOperand(0)->getScalarType());
138 *
Store, Ingredient.getOperand(1), Ingredient.getOperand(0),
139 nullptr , IsConsecutive,
Store->getAlign(), *VPI,
140 Ingredient.getDebugLoc());
143 Ingredient.operands(), *VPI,
144 Ingredient.getDebugLoc(),
GEP);
156 if (VectorID == Intrinsic::experimental_noalias_scope_decl)
161 if (VectorID == Intrinsic::assume ||
162 VectorID == Intrinsic::lifetime_end ||
163 VectorID == Intrinsic::lifetime_start ||
164 VectorID == Intrinsic::sideeffect ||
165 VectorID == Intrinsic::pseudoprobe) {
170 const bool IsSingleScalar = VectorID != Intrinsic::assume &&
171 VectorID != Intrinsic::pseudoprobe;
175 Ingredient.getDebugLoc());
177 assert(!CI->hasOperandBundles() &&
178 "calls with operand bundles must not be widened");
180 *CI, VectorID,
drop_end(Ingredient.operands()), CI->getType(),
181 VPIRFlags(*CI), *VPI, CI->getDebugLoc());
185 CI->getOpcode(), Ingredient.getOperand(0), CI->getType(), CI,
189 *VPI, Ingredient.getDebugLoc());
193 "inductions must be created earlier");
202 "Only recpies with zero or one defined values expected");
203 Ingredient.eraseFromParent();
214 const Loop *L =
nullptr;
219 if (
A->getOpcode() != Instruction::Store ||
220 B->getOpcode() != Instruction::Store)
233 const APInt *Distance;
239 Type *TyA =
A->getOperand(0)->getScalarType();
240 uint64_t SizeA =
DL.getTypeStoreSize(TyA);
241 Type *TyB =
B->getOperand(0)->getScalarType();
242 uint64_t SizeB =
DL.getTypeStoreSize(TyB);
247 uint64_t MaxStoreSize = std::max(SizeA, SizeB);
249 auto VFs =
B->getParent()->getPlan()->vectorFactors();
260 : ExcludeRecipes(ExcludeRecipes.begin(), ExcludeRecipes.end()),
261 GroupLeader(GroupLeader), PSE(&PSE), L(&L) {}
270 return ExcludeRecipes.contains(
Store) ||
271 (
Store && isNoAliasViaDistance(
Store, &GroupLeader));
284 std::optional<SinkStoreInfo> SinkInfo = {}) {
285 bool CheckReads = SinkInfo.has_value();
290 if (SinkInfo && SinkInfo->shouldSkip(R))
294 if (!
R.mayWriteToMemory() && !(CheckReads &&
R.mayReadFromMemory()))
313template <
unsigned Opcode>
318 static_assert(Opcode == Instruction::Load || Opcode == Instruction::Store,
319 "Only Load and Store opcodes supported");
320 constexpr bool IsLoad = (Opcode == Instruction::Load);
323 RecipesByAddressAndType;
327 if (RepR.getOpcode() != Opcode || !FilterFn(&RepR))
331 VPValue *Addr = RepR.getOperand(IsLoad ? 0 : 1);
335 RecipesByAddressAndType[{AddrSCEV, LoadStoreTy}].push_back(&RepR);
340 for (
auto &Group :
Groups) {
355 auto InsertIfValidSinkCandidate = [ScalarVFOnly, &WorkList](
362 if (Candidate->getParent() == SinkTo ||
363 all_of(Candidate->operands(),
364 [](
VPValue *
Op) { return Op->isDefinedOutsideLoopRegions(); }) ||
376 WorkList.
insert({SinkTo, Candidate});
388 for (
auto &Recipe : *VPBB)
390 InsertIfValidSinkCandidate(VPBB,
Op);
394 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
397 std::tie(SinkTo, SinkCandidate) = WorkList[
I];
402 auto UsersOutsideSinkTo =
404 return cast<VPRecipeBase>(U)->getParent() != SinkTo;
406 if (
any_of(UsersOutsideSinkTo, [SinkCandidate](
VPUser *U) {
407 return !U->usesFirstLaneOnly(SinkCandidate);
410 bool NeedsDuplicating = !UsersOutsideSinkTo.empty();
412 if (NeedsDuplicating) {
416 if (
auto *SinkCandidateRepR =
421 SinkCandidateRepR->getOpcode(), SinkCandidate->
operands(),
422 nullptr, *SinkCandidateRepR, *SinkCandidateRepR,
427 Clone = SinkCandidate->
clone();
437 InsertIfValidSinkCandidate(SinkTo,
Op);
446 if (EntryBB->getNumSuccessors() != 2)
451 if (!Succ0 || !Succ1)
454 if (Succ0->getNumSuccessors() + Succ1->getNumSuccessors() != 1)
456 if (Succ0->getSingleSuccessor() == Succ1)
458 if (Succ1->getSingleSuccessor() == Succ0)
475 if (!Region1->isReplicator())
477 auto *MiddleBasicBlock =
479 if (!MiddleBasicBlock || !MiddleBasicBlock->empty())
484 if (!Region2 || !Region2->isReplicator())
487 VPValue *Mask1 = Region1->getEntryBranchOnMask()->getOperand(0);
488 VPValue *Mask2 = Region2->getEntryBranchOnMask()->getOperand(0);
489 if (!Mask1 || Mask1 != Mask2)
492 assert(Mask1 && Mask2 &&
"both region must have conditions");
498 if (TransformedRegions.
contains(Region1))
505 if (!Then1 || !Then2)
513 std::optional<VPExecutionFrequency> Freq1 =
516 if (Freq1 && Freq2) {
517 if (Freq2->Freq < Freq1->Freq) {
520 Freq1.emplace(Freq1->Freq, Freq1->IsEstimated || Freq2->IsEstimated);
544 VPValue *Phi1ToMoveV = Phi1ToMove.getVPSingleValue();
550 if (Phi1ToMove.getVPSingleValue()->user_empty()) {
551 Phi1ToMove.eraseFromParent();
554 Phi1ToMove.moveBefore(Merge2->begin());
568 TransformedRegions.
insert(Region1);
571 return !TransformedRegions.
empty();
579 std::string RegionName = (
Twine(
"pred.") + Instr->getOpcodeName()).str();
580 assert(Instr->getParent() &&
"Predicated instruction not in any basic block");
581 auto *BlockInMask = PredRecipe->
getMask();
596 BOMRecipe->setExecutionFrequency(RecipeWithoutMask->getExecutionFrequency(),
598 RecipeWithoutMask->clearExecutionFrequency();
607 Region->setParent(ParentRegion);
615 if (RecipeWithoutMask->getScalarType()->isStructTy())
616 Defs =
to_vector(RecipeWithoutMask->users());
619 assert((Def == RecipeWithoutMask ||
620 Def->getOpcode() == Instruction::ExtractValue) &&
621 "only extracts can use a predicated struct");
622 Def->moveBefore(
Pred->end());
623 if (Def->user_empty())
626 Exiting->appendRecipe(PHIRecipe);
627 Def->replaceAllUsesWith(PHIRecipe);
628 PHIRecipe->setOperand(0, Def);
639 if (RepR.isPredicated())
657 if (ParentRegion && ParentRegion->
getExiting() == CurrentBlock)
669 if (!VPBB->getParent())
681 R.moveBefore(PredVPBB->
end());
683 auto *ParentRegion = VPBB->getParent();
684 if (ParentRegion && ParentRegion->getExiting() == VPBB)
685 ParentRegion->setExiting(PredVPBB);
689 return !WorkList.
empty();
696 bool ShouldSimplify =
true;
697 while (ShouldSimplify) {
714 if (
IV.isTruncated())
729 for (
auto *U : FindMyCast->
users()) {
731 if (UserCast && UserCast->getUnderlyingValue() == IRCast) {
732 FoundUserCast = UserCast;
739 FindMyCast = FoundUserCast;
741 if (FindMyCast != &
IV)
766 PhiR->replaceAllUsesWith(PhiR->getOperand(0));
768 PhiR->eraseFromParent();
834 Def->user_empty() || !Def->getUnderlyingValue() ||
835 (RepR && (RepR->isSingleScalar() || RepR->isPredicated())))
848 Def->getUnderlyingInstr()->getOpcode(), Def->operands(),
850 Def->getScalarType(), Def->getUnderlyingInstr());
851 Clone->insertAfter(Def);
852 Def->replaceAllUsesWith(Clone);
853 Def->eraseFromParent();
868 PtrIV->replaceAllUsesWith(PtrAdd);
875 if (HasOnlyVectorVFs &&
none_of(WideIV->users(), [WideIV](
VPUser *U) {
876 return U->usesScalars(WideIV);
887 Plan, ID.getKind(), ID.getInductionOpcode(),
889 WideIV->getScalarType(), WideIV->getStartValue(),
890 WideIV->getStepValue(), WideIV->getDebugLoc(), Builder, WrapFlags);
893 if (!HasOnlyVectorVFs) {
895 "plans containing a scalar VF cannot also include scalable VFs");
896 WideIV->replaceAllUsesWith(Steps);
899 WideIV->replaceUsesWithIf(Steps, [WideIV, HasScalableVF](
VPUser *U) {
901 return U->usesFirstLaneOnly(WideIV);
902 return U->usesScalars(WideIV);
918 return (IntOrFpIV && IntOrFpIV->isTruncated()) ? nullptr : WideIV;
923 if (!Def || Def->getNumOperands() != 2)
931 auto IsWideIVInc = [&]() {
932 auto &ID = WideIV->getInductionDescriptor();
935 VPValue *IVStep = WideIV->getStepValue();
936 switch (ID.getInductionOpcode()) {
937 case Instruction::Add:
939 case Instruction::FAdd:
941 case Instruction::FSub:
944 case Instruction::Sub: {
964 return IsWideIVInc() ? WideIV :
nullptr;
988 VPValue *FirstActiveLane =
B.createFirstActiveLane(Mask,
DL);
990 B.createScalarZExtOrTrunc(FirstActiveLane, CanonicalIVType,
DL);
991 VPValue *EndValue =
B.createAdd(CanonicalIV, FirstActiveLane,
DL);
996 if (Incoming != WideIV) {
998 EndValue =
B.createAdd(EndValue, One,
DL);
1003 VPValue *Start = WideIV->getStartValue();
1004 VPValue *Step = WideIV->getStepValue();
1005 EndValue =
B.createDerivedIV(
1007 Start, EndValue, Step);
1021 if (WideIntOrFp && WideIntOrFp->isTruncated())
1031 Start, VectorTC, Step);
1063 assert(EndValue &&
"Must have computed the end value up front");
1068 if (Incoming != WideIV)
1081 return B.createPtrAdd(EndValue,
B.createSub(
Zero, Step),
1086 return B.createNaryOp(
1087 ID.getInductionBinOp()->getOpcode() == Instruction::FAdd
1089 : Instruction::FAdd,
1090 {EndValue, Step}, {ID.getInductionBinOp()->getFastMathFlags()});
1107 const SCEV *Start, *Step;
1125 VPValue *ExitCount = Builder.createOverflowingOp(
1128 return Builder.createDerivedIV(Kind,
nullptr, StartVPV, ExitCount,
1137 VPBuilder VectorPHBuilder(VectorPH->getFirstNonPhi());
1144 &WideIV, VectorPHBuilder, ResumeTC))
1145 EndValues[&WideIV] = EndValue;
1155 R.getVPSingleValue()->replaceAllUsesWith(EndValue);
1156 R.eraseFromParent();
1165 for (
auto [Idx, PredVPBB] :
enumerate(ExitVPBB->getPredecessors())) {
1167 if (PredVPBB == MiddleVPBB) {
1169 Plan, ExitIRI->getOperand(Idx), EndValues, PSE);
1172 Plan, ExitIRI->getOperand(Idx), PSE, ResumeTC, L);
1175 Plan, ExitIRI->getOperand(Idx), PSE);
1178 ExitIRI->setOperand(Idx, Escape);
1202 return Plan.
getZero(Def->getScalarType());
1219 return Def->getOperand(1);
1230 assert(
X->getScalarType()->isIntegerTy(1) &&
"must have boolean operands");
1246 assert(Weights.
size() == 2 &&
"unexpected branch weights");
1248 LLVMContext::MD_prof,
1285 return Plan.
getZero(Def->getScalarType());
1289 Def->getScalarType() ==
A->getScalarType())
1299 if (Def->getScalarType() ==
A->getScalarType())
1309 A->getScalarType() == Def->getScalarType())
1316 return BuildVector->getLastOperand();
1333 return BuildVector->getOperand(BuildVector->getNumOperands() - 2);
1339 return BuildVector->getOperand(Idx);
1343 if (Def->getNumOperands() == 1) {
1344 return Def->getOperand(0);
1348 return Phi->getOperand(0);
1354 if (Def->getNumOperands() == 1 &&
1360 A->getScalarType() == Def->getScalarType())
1372 return Def->getOperand(1);
1384 return VPR->getOperand(0);
1390 return Steps->getOperand(0);
1408struct VPCombineInserter {
1409 SmallVectorImpl<VPSingleDefRecipe *> &Worklist;
1412 R->insertBefore(It);
1424 VPCombineBuilder &Builder) {
1426 Def->replaceAllUsesWith(
V);
1435 RepR && RepR->isPredicated() && RepR->getOpcode() == Instruction::Store &&
1439 RepR->getUnderlyingInstr(), RepR->operandsWithoutMask(),
1440 RepR->isSingleScalar(),
nullptr, *RepR, *RepR,
1441 RepR->getDebugLoc());
1442 Builder.insert(Unmasked);
1454 bool CanCreateNewRecipe =
1460 if (CanCreateNewRecipe &&
1463 return Builder.createLogicalAnd(
X,
Y);
1466 if (CanCreateNewRecipe &&
1471 (!Def->getOperand(0)->hasMoreThanOneUniqueUser() ||
1472 !Def->getOperand(1)->hasMoreThanOneUniqueUser()))
1473 return Builder.createLogicalAnd(
X, Builder.createOr(
Y, Z));
1476 if (CanCreateNewRecipe &&
1480 return Builder.createLogicalOr(Z,
Y);
1484 if (CanCreateNewRecipe &&
1486 return Builder.createNot(
C);
1490 Def->setOperand(0,
C);
1491 Def->setOperand(1,
Y);
1492 Def->setOperand(2,
X);
1498 if (CanCreateNewRecipe &&
1502 Y->getScalarType()->isIntegerTy(1))
1503 return Builder.createOr(
Y, Builder.createLogicalAnd(
X, Z));
1507 if (CanCreateNewRecipe &&
1513 return Builder.createSelect(Builder.createLogicalAnd(Mask0, Mask1),
X,
Y,
1514 Def->getDebugLoc());
1520 Type *TruncTy = Def->getScalarType();
1521 Type *XTy =
X->getScalarType();
1524 unsigned ExtOpcode =
1528 if (
auto *UnderlyingExt =
Y->getUnderlyingValue()) {
1530 Ext->setUnderlyingValue(UnderlyingExt);
1534 auto *Trunc = Builder.createWidenCast(Instruction::Trunc,
X, TruncTy);
1543 return Builder.createSub(Plan.
getZero(
X->getScalarType()),
X,
1544 Def->getDebugLoc(),
"", NW);
1547 if (CanCreateNewRecipe &&
1555 return Builder.createSub(
X,
Y, Def->getDebugLoc(),
"", NW);
1562 Def->getDebugLoc());
1569 MulR->hasNoSignedWrap() &&
1571 return Builder.createNaryOp(
1574 Def->getDebugLoc());
1579 return Builder.createNaryOp(
1585 if (CanCreateNewRecipe &&
1588 return Builder.createAnd(
1590 Def->getDebugLoc());
1600 return match(U, m_Not(m_Specific(Cmp))) ||
1601 (match(U, m_Select(m_Specific(Cmp), m_VPValue(),
1603 U->getOperand(1) != Cmp && U->getOperand(2) != Cmp);
1610 R->setOperand(1,
Y);
1611 R->setOperand(2,
X);
1616 R->replaceAllUsesWith(Cmp);
1621 if (!Cmp->getDebugLoc() && Def->getDebugLoc())
1622 Cmp->setDebugLoc(Def->getDebugLoc());
1635 if (
Op->getNumUsers() > 1 ||
1639 }
else if (!UnpairedCmp) {
1640 UnpairedCmp =
Op->getDefiningRecipe();
1644 UnpairedCmp =
nullptr;
1651 if (NewOps.
size() < Def->getNumOperands())
1658 if (CanCreateNewRecipe &&
1663 X->getScalarType() ==
Y->getScalarType())
1668 X->getScalarType() != Def->getScalarType())
1669 return Builder.createWidenCast(Instruction::Trunc,
X, Def->getScalarType());
1676 Def->getScalarType()->isIntegerTy(1)) {
1677 Def->setOperand(1, Plan.
getTrue());
1678 Def->setOperand(0,
Y);
1688 Def->replaceUsesWithIf(Def->getOperand(0), [Def](
VPUser *U) {
1689 return U->usesFirstLaneOnly(Def);
1699 "broadcast operand must be single-scalar");
1700 Def->setOperand(0, Z);
1705 Def->replaceUsesWithIf(
1706 X, [Def](
const VPUser *U) {
return U->usesScalars(Def); });
1718 return Builder.createNaryOp(Instruction::ExtractElement, {
X, LaneToExtract},
1719 Def->getDebugLoc());
1731 IVInc->getNumUsers() == 2) {
1737 if ((Phi->getNumUsers() == 1 || (Phi->getNumUsers() == 2 && Inc)) &&
1739 Def->replaceAllUsesWith(IVInc);
1741 Inc->replaceAllUsesWith(Phi);
1742 Phi->setOperand(0,
Y);
1751 Def->replaceUsesWithIf(StartV, [](
const VPUser *U) {
1753 return PhiR && PhiR->isInLoop();
1770 [[maybe_unused]]
unsigned InitWorklistSize = Worklist.
size();
1772 VPCombineBuilder Builder({Worklist});
1773 while (!Worklist.
empty()) {
1774 assert(Worklist.
size() < InitWorklistSize * 2 &&
1775 "Worklist is growing large, possible cycle?");
1777 Builder.setInsertPoint(Def);
1783 Def->replaceAllUsesWith(New);
1784 Def->eraseFromParent();
1788 Def->eraseFromParent();
1806 R.getVPSingleValue()->replaceAllUsesWith(
X);
1822 while (!Worklist.
empty()) {
1831 R->replaceAllUsesWith(
1832 Builder.createLogicalAnd(HeaderMask, Builder.createLogicalAnd(
X,
Y)));
1836static std::optional<Instruction::BinaryOps>
1839 case Intrinsic::masked_udiv:
1840 return Instruction::UDiv;
1841 case Intrinsic::masked_sdiv:
1842 return Instruction::SDiv;
1843 case Intrinsic::masked_urem:
1844 return Instruction::URem;
1845 case Intrinsic::masked_srem:
1846 return Instruction::SRem;
1863 if (RepR && (RepR->isSingleScalar() || RepR->isPredicated()))
1867 if (RepR && RepR->getOpcode() == Instruction::Store &&
1870 RepOrWidenR->getUnderlyingInstr(), RepOrWidenR->operands(),
1871 true ,
nullptr , *RepR ,
1872 *RepR , RepR->getDebugLoc());
1873 Clone->insertBefore(RepOrWidenR);
1875 VPValue *ExtractOp = Clone->getOperand(0);
1881 Clone->setOperand(0, ExtractOp);
1882 RepR->eraseFromParent();
1894 VPValue *SafeDivisor = Builder.createSelect(
1895 IntrR->getOperand(2), IntrR->getOperand(1),
1897 VPValue *Clone = Builder.createNaryOp(
1898 *
Opc, {IntrR->getOperand(0), SafeDivisor},
1901 IntrR->eraseFromParent();
1907 if (!RepOrWidenR->getUnderlyingValue() ||
1912 auto IntroducesBCastOf = [](
const VPValue *
Op) {
1921 return !U->usesScalars(
Op);
1925 if (
any_of(RepOrWidenR->users(), IntroducesBCastOf(RepOrWidenR)) &&
1928 make_filter_range(Op->users(), not_equal_to(RepOrWidenR)),
1929 IntroducesBCastOf(Op)))
1933 bool LiveInNeedsBroadcast =
1934 isa<VPIRValue>(Op) && !isa<VPConstant>(Op);
1935 auto *OpR = dyn_cast<VPReplicateRecipe>(Op);
1936 return LiveInNeedsBroadcast || (OpR && OpR->isSingleScalar());
1944 RepOrWidenR->getUnderlyingInstr());
1945 Clone->insertBefore(RepOrWidenR);
1946 RepOrWidenR->replaceAllUsesWith(Clone);
1948 RepOrWidenR->eraseFromParent();
1981 if (Blend.isNormalized() || !
match(Blend.getMask(0),
m_False()))
1982 UniqueValues.
insert(Blend.getIncomingValue(0));
1983 for (
unsigned I = 1;
I != Blend.getNumIncomingValues(); ++
I)
1985 UniqueValues.
insert(Blend.getIncomingValue(
I));
1987 if (UniqueValues.
size() == 1) {
1988 Blend.replaceAllUsesWith(*UniqueValues.
begin());
1989 Blend.eraseFromParent();
1993 if (Blend.isNormalized())
1999 unsigned StartIndex = 0;
2000 for (
unsigned I = 0;
I != Blend.getNumIncomingValues(); ++
I) {
2012 OperandsWithMask.
push_back(Blend.getIncomingValue(StartIndex));
2014 for (
unsigned I = 0;
I != Blend.getNumIncomingValues(); ++
I) {
2015 if (
I == StartIndex)
2017 OperandsWithMask.
push_back(Blend.getIncomingValue(
I));
2018 OperandsWithMask.
push_back(Blend.getMask(
I));
2023 OperandsWithMask, Blend, Blend.getDebugLoc());
2024 NewBlend->insertBefore(&Blend);
2026 VPValue *DeadMask = Blend.getMask(StartIndex);
2028 Blend.eraseFromParent();
2033 if (NewBlend->getNumOperands() == 3 &&
2035 VPValue *Inc0 = NewBlend->getOperand(0);
2036 VPValue *Inc1 = NewBlend->getOperand(1);
2037 VPValue *OldMask = NewBlend->getOperand(2);
2038 NewBlend->setOperand(0, Inc1);
2039 NewBlend->setOperand(1, Inc0);
2040 NewBlend->setOperand(2, NewMask);
2067 APInt MaxVal = AlignedTC - 1;
2070 unsigned NewBitWidth =
2076 bool MadeChange =
false;
2104 "canonical IV is not expected to have a truncation");
2109 NewWideIV->insertBefore(WideIV);
2116 Cmp->replaceAllUsesWith(
2117 VPBuilder(Cmp).createICmp(Cmp->getPredicate(), NewWideIV, NewBTC));
2131 return any_of(
Cond->getDefiningRecipe()->operands(), [&Plan, BestVF, BestUF,
2133 return isConditionTrueViaVFAndUF(C, Plan, BestVF, BestUF, PSE);
2147 const SCEV *VectorTripCount =
2152 "Trip count SCEV must be computable");
2167 bool MadeChange =
false;
2175 for (
VPBasicBlock *VPBB : {PreheaderVPBB, ExitingVPBB}) {
2184 Builder.setInsertPoint(Extract);
2187 Start = Builder.createAdd(
2192 Extract->eraseFromParent();
2211 return !
Offset ||
Offset->isDefinedOutsideLoopRegions();
2230 auto *Term = &ExitingVPBB->
back();
2241 const SCEV *VectorTripCount =
2247 "Trip count SCEV must be computable");
2261 Term->setOperand(1, Plan.
getTrue());
2266 {}, Term->getDebugLoc());
2268 Term->eraseFromParent();
2276 assert(Plan.
hasVF(BestVF) &&
"BestVF is not available in Plan");
2277 assert(Plan.
hasUF(BestUF) &&
"BestUF is not available in Plan");
2293 RecurKind RK = PhiR.getRecurrenceKind();
2300 RecWithFlags->dropPoisonGeneratingFlags();
2307 return MemR->getAlign();
2312struct VPCSEDenseMapInfo :
public DenseMapInfo<VPSingleDefRecipe *> {
2315 static Type *getGEPSourceElementType(
const VPSingleDefRecipe *R) {
2318 return TypeSwitch<const VPSingleDefRecipe *, Type *>(R)
2319 .Case([](
const VPReplicateRecipe *
I) ->
Type * {
2321 return GEP->getSourceElementType();
2324 .Case<VPVectorPointerRecipe, VPWidenGEPRecipe>(
2325 [](
auto *
I) {
return I->getSourceElementType(); })
2326 .
Default([](
auto *) {
return nullptr; });
2330 static bool canHandle(
const VPSingleDefRecipe *Def) {
2337 if (!
C || (!
C->first &&
C->second == Instruction::Alloca))
2342 if (
Def->mayWriteToMemory())
2344 return !
Def->mayReadFromMemory() ||
2345 (!
C->first &&
C->second == Instruction::Load);
2349 static unsigned getHashValue(
const VPSingleDefRecipe *Def) {
2352 getGEPSourceElementType(Def),
Def->getScalarType(),
2355 if (RFlags->hasPredicate())
2358 return hash_combine(Result, SIVSteps->getInductionOpcode());
2360 return hash_combine(Result, DIV->getInductionKind(), DIV->getFPBinOp());
2371 static bool isEqual(
const VPSingleDefRecipe *L,
const VPSingleDefRecipe *R) {
2372 if (
L->getVPRecipeID() !=
R->getVPRecipeID() ||
2375 getGEPSourceElementType(L) != getGEPSourceElementType(R) ||
2377 !
equal(
L->operands(),
R->operands()))
2381 "must have valid opcode info for both recipes");
2383 if (LFlags->hasPredicate() &&
2384 LFlags->getPredicate() !=
2388 if (LSIV->getInductionOpcode() !=
2393 if (LDIV->getInductionKind() != RDIV->getInductionKind() ||
2394 LDIV->getFPBinOp() != RDIV->getFPBinOp())
2413 const VPRegionBlock *RegionL =
L->getRegion();
2414 const VPRegionBlock *RegionR =
R->getRegion();
2417 L->getParent() !=
R->getParent())
2419 return L->getScalarType() ==
R->getScalarType();
2437 if (R.mayWriteToMemory())
2440 if (!Def || !VPCSEDenseMapInfo::canHandle(Def))
2443 auto [It, Inserted] =
2444 (IsLoad ? LoadCSEMap : CSEMap).try_emplace(Def, Def);
2449 if (!VPDT.
dominates(V->getParent(), VPBB))
2463 if (DefExp && DefExp->expandInIR() &&
2474 Def->replaceAllUsesWith(V);
2488 bool Sinking =
false) {
2517 "Expected vector prehader's successor to be the vector loop region");
2525 return !Op->isDefinedOutsideLoopRegions();
2531 R.moveBefore(Preheader->
end());
2549 assert(!RepR->isPredicated() &&
2550 "Expected prior transformation of predicated replicates to "
2551 "replicate regions");
2556 if (!RepR->isSingleScalar())
2560 if (RepR->getOpcode() == Instruction::Store &&
2561 !RepR->getOperand(1)->isDefinedOutsideLoopRegions())
2569 if (
any_of(Def->users(), [&SinkBB, &LoopRegion](
VPUser *U) {
2570 auto *UserR = cast<VPRecipeBase>(U);
2571 VPBasicBlock *Parent = UserR->getParent();
2573 if (SinkBB && SinkBB != Parent)
2578 return UserR->isPhi() || Parent->getEnclosingLoopRegion() ||
2579 Parent->getSinglePredecessor() != LoopRegion;
2589 assert((!R.mayWriteToMemory() ||
2590 (RepR && RepR->getOpcode() == Instruction::Store &&
2591 RepR->getOperand(1)->isDefinedOutsideLoopRegions())) &&
2592 "The only recipes that may write to memory are expected to be "
2593 "stores with invariant pointer-operand");
2601 "Defining block must dominate sink block");
2628 VPValue *ResultVPV = R.getVPSingleValue();
2630 unsigned NewResSizeInBits = MinBWs.
lookup(UI);
2631 if (!NewResSizeInBits)
2644 (void)OldResSizeInBits;
2652 VPW->dropPoisonGeneratingFlags();
2654 assert((OldResSizeInBits != NewResSizeInBits ||
2656 "Only ICmps should not need extending the result.");
2669 unsigned OpSizeInBits =
Op->getScalarType()->getScalarSizeInBits();
2670 if (OpSizeInBits == NewResSizeInBits)
2672 assert(OpSizeInBits > NewResSizeInBits &&
"nothing to truncate");
2673 auto [ProcessedIter, Inserted] =
2678 Builder.setInsertPoint(PH);
2680 Builder.setInsertPoint(&R);
2681 ProcessedIter->second =
2682 Builder.createWidenCast(Instruction::Trunc,
Op, NewResTy);
2684 Op = ProcessedIter->second;
2688 NWR->insertBefore(&R);
2693 VPValue *Replacement = NWR->getVPSingleValue();
2700 R.eraseFromParent();
2706 std::optional<VPDominatorTree> VPDT;
2714 bool SimplifiedPhi =
false;
2724 assert(VPBB->getNumSuccessors() == 2 &&
2725 "Two successors expected for BranchOnCond");
2726 unsigned RemovedIdx;
2737 "There must be a single edge between VPBB and its successor");
2742 SimplifiedPhi =
true;
2746 if (!PhiR || PhiR->getNumIncoming() != 1)
2748 PhiR->replaceAllUsesWith(PhiR->getOperand(0));
2749 PhiR->eraseFromParent();
2754 VPBB->back().eraseFromParent();
2766 if (Reachable.contains(
B))
2777 for (
VPValue *Def : R.definedValues())
2778 Def->replaceAllUsesWith(&Tmp);
2779 R.eraseFromParent();
2783 return SimplifiedPhi;
2811 auto GetSimplifiedLiveInViaSCEV = [&](
VPValue *VPV) ->
VPValue * {
2820 if (
VPValue *SimplifiedLiveIn = GetSimplifiedLiveInViaSCEV(LiveIn))
2821 LiveIn->replaceAllUsesWith(SimplifiedLiveIn);
2832 "expected to run before loop regions are created");
2834 auto CanUseVersionedStride = [&VPDT, Header = Header, &Plan](
VPUser *U) {
2840 return VPDT.
dominates(Header, R->getParent());
2844 Value *StrideV = Stride->getValue();
2845 const APInt *StrideConst;
2852 CanUseVersionedStride);
2866 CanUseVersionedStride);
2868 RewriteMap[StrideV] = StrideExpr;
2874 const SCEV *ScevExpr = ExpSCEV.getSCEV();
2875 const SCEV *NewSCEV =
2880 ExpSCEV.replaceAllUsesWith(NewExp);
2890 auto CollectPoisonGeneratingInstrsInBackwardSlice([&](
VPRecipeBase *Root) {
2895 while (!Worklist.
empty()) {
2898 if (!Visited.
insert(CurRec).second)
2920 RecWithFlags->isDisjoint()) {
2923 Builder.createAdd(
A,
B, RecWithFlags->getDebugLoc());
2924 New->setUnderlyingValue(RecWithFlags->getUnderlyingValue());
2925 RecWithFlags->replaceAllUsesWith(New);
2926 RecWithFlags->eraseFromParent();
2929 RecWithFlags->dropPoisonGeneratingFlags();
2934 assert((!Instr || !Instr->hasPoisonGeneratingFlags()) &&
2935 "found instruction with poison generating flags not covered by "
2936 "VPRecipeWithIRFlags");
2941 if (
VPRecipeBase *OpDef = Operand->getDefiningRecipe())
2963 VPRecipeBase *AddrDef = WidenRec->getAddr()->getDefiningRecipe();
2964 if (AddrDef && WidenRec->isConsecutive() && WidenRec->getMask() &&
2965 match(WidenRec->getMask(), m_UnlessHdrMask))
2966 CollectPoisonGeneratingInstrsInBackwardSlice(AddrDef);
2968 VPRecipeBase *AddrDef = InterleaveRec->getAddr()->getDefiningRecipe();
2969 if (AddrDef && InterleaveRec->getMask() &&
2970 match(InterleaveRec->getMask(), m_UnlessHdrMask))
2971 CollectPoisonGeneratingInstrsInBackwardSlice(AddrDef);
2981 const bool &EpilogueAllowed) {
2982 if (InterleaveGroups.empty())
2993 IRMemberToRecipe[&MemR->getIngredient()] = MemR;
3000 for (
const auto *IG : InterleaveGroups) {
3003 for (
auto *Member : IG->members())
3005 StartMember = Member;
3013 for (
unsigned I = 0;
I < IG->getFactor(); ++
I) {
3019 StoredValues.
push_back(StoreR->getStoredValue());
3026 bool NeedsMaskForGaps =
3027 (IG->requiresScalarEpilogue() && !EpilogueAllowed) ||
3028 (!StoredValues.
empty() && !IG->isFull());
3031 auto *InsertPos = IRMemberToRecipe.
lookup(IRInsertPos);
3035 "Dead member in non-load group?");
3040 InsertPos->getAsRecipe()))
3041 InsertPos = MemberR;
3042 IRInsertPos = &InsertPos->getIngredient();
3052 VPValue *Addr = Start->getAddr();
3054 if (IG->getIndex(StartMember) != 0 ||
3062 assert(IG->getIndex(IRInsertPos) != 0 &&
3063 "index of insert position shouldn't be zero");
3067 IG->getIndex(IRInsertPos),
3071 Addr =
B.createNoWrapPtrAdd(InsertPos->getAddr(), OffsetVPV, NW);
3077 if (IG->isReverse()) {
3080 -(int64_t)IG->getFactor(), NW, InsertPosR->
getDebugLoc());
3081 ReversePtr->insertBefore(InsertPosR);
3085 IG, Addr, StoredValues, InsertPos->getMask(), NeedsMaskForGaps,
3087 VPIG->insertBefore(InsertPosR);
3090 for (
unsigned i = 0; i < IG->getFactor(); ++i)
3093 if (!Member->getType()->isVoidTy()) {
3115struct CountableConditionMatch {
3117 PredicatedScalarEvolution &PSE;
3120 CountableConditionMatch(VPValue *&Cmp, PredicatedScalarEvolution &PSE,
3124 template <
typename ITy>
bool match(ITy *
V)
const {
3144 return CountableConditionMatch(Cmp, PSE, L);
3163 VPValue *Uncountable =
nullptr;
3180 if (ExitBlocks.
size() != 1)
3187 if (!ExitBlocks.
front()->phis().empty())
3203 LatchVPBB->clearSuccessors();
3213 Term->setOperand(0, Countable);
3277 VPValue *UncountableCondition =
nullptr;
3284 Worklist.
push_back(UncountableCondition);
3285 while (!Worklist.
empty()) {
3289 if (
V->isDefinedOutsideLoopRegions())
3322 if (Recipes.
empty() ||
3326 return UncountableCondition;
3381 for (
auto &Exit : Exits) {
3382 if (Exit.EarlyExitingVPBB == LatchVPBB)
3386 cast<VPIRPhi>(&R)->removeIncomingValueFor(Exit.EarlyExitingVPBB);
3387 Exit.EarlyExitingVPBB->getTerminator()->eraseFromParent();
3401 "loop with side effects",
3402 "EarlyExitSideEffectsCond", ORE, TheLoop);
3417 assert(
Load &&
"Couldn't find exactly one load");
3420 "Uncountable exit condition load is conditional.");
3434 DL.getTypeStoreSize(
Load->getScalarType()).getFixedValue());
3440 "load used by the exit condition that may "
3442 "EarlyExitSideEffectsFaultingLoad", ORE,
3455 "load used by the exit condition with an "
3456 "unsupported memory access pattern",
3457 "EarlyExitSideEffectsBadLoadAccessPattern", ORE,
3465 "load used by the exit condition with an "
3466 "unsupported memory access pattern",
3467 "EarlyExitSideEffectsBadLoadAccessPattern", ORE,
3477 while (InsertIt != HeaderVPBB->
end() &&
3479 erase(ConditionRecipes, &*InsertIt);
3482 for (
auto *Recipe :
reverse(ConditionRecipes))
3483 Recipe->moveBefore(InsertIt);
3494 if (R.mayReadOrWriteMemory() && &R !=
Load) {
3496 if (!VPDT.
dominates(R.getParent(), LatchVPBB)) {
3498 "Early exit loop with side effects contains unsupported "
3499 "conditional memory operations",
3500 "EarlyExitSideEffectsUnsupportedConditionalMemOps", ORE, TheLoop);
3511 "Expected BranchOnCond terminator for MiddleVPBB");
3513 Type *IVScalarTy =
IV->getScalarType();
3526 auto Phis = ScalarPH->
phis();
3531 "Early exit loop with side effects contains "
3532 "unsupported reductions, inductions or recurrences",
3533 "EarlyExitSideEffectsReductions", ORE, TheLoop);
3541 "Continuing from different IV");
3554 if (!R.mayWriteToMemory()) {
3556 R.isSafeToSpeculativelyExecute()) &&
3557 "legality only accepts recipes with side effects that are "
3558 "safe to speculate");
3562 "legality only accepts stores as writes in early-exit loops");
3588 "Auto-vectorization of early exit loops with potentially "
3589 "faulting loads is not supported",
3590 "EarlyExitFaultingLoads", ORE, TheLoop);
3594 VPBuilder LatchBuilder(LatchVPBB->getTerminator());
3596 for (
auto [EarlyExitingVPBB, ExitBlock] :
3603 cast<VPIRPhi>(&R)->getIncomingValueForBlock(EarlyExitingVPBB);
3606 if (ExitV != PhiR.getBackedgeValue())
3609 "Found reduction used on an early exit",
3610 "Cannot vectorize early exit loop with reduction used on an "
3612 "ReductionUsedOnEarlyExit", ORE, TheLoop);
3619 VPValue *CondOfEarlyExitingVPBB;
3620 [[maybe_unused]]
bool Matched =
3621 match(EarlyExitingVPBB->getTerminator(),
3623 assert(Matched &&
"Terminator must be BranchOnCond");
3627 VPBuilder EarlyExitingBuilder(EarlyExitingVPBB->getTerminator());
3628 auto *CondToEarlyExit = EarlyExitingBuilder.
createNaryOp(
3630 TrueSucc == ExitBlock
3631 ? CondOfEarlyExitingVPBB
3632 : EarlyExitingBuilder.
createNot(CondOfEarlyExitingVPBB));
3638 "exit condition must dominate the latch");
3646 assert(!Exits.
empty() &&
"must have at least one early exit");
3653 for (
const auto &[Num, VPB] :
enumerate(RPOT))
3656 return RPOIdx[
A.EarlyExitingVPBB] < RPOIdx[
B.EarlyExitingVPBB];
3662 for (
unsigned I = 0;
I + 1 < Exits.
size(); ++
I)
3663 for (
unsigned J =
I + 1; J < Exits.
size(); ++J)
3665 Exits[
I].EarlyExitingVPBB) &&
3666 "RPO sort must place dominating exits before dominated ones");
3672 VPValue *Combined = Exits[0].CondToExit;
3694 "Unexpected terminator");
3695 VPValue *IsLatchExitTaken = LatchExitingBranch->getOperand(0);
3696 DebugLoc LatchDL = LatchExitingBranch->getDebugLoc();
3697 LatchExitingBranch->eraseFromParent();
3700 {IsAnyExitTaken, IsLatchExitTaken}, LatchDL);
3701 LatchVPBB->clearSuccessors();
3706 LatchVPBB->setSuccessors({MiddleVPBB, MiddleVPBB, HeaderVPBB});
3707 MiddleVPBB->clearPredecessors();
3708 MiddleVPBB->setPredecessors({LatchVPBB, LatchVPBB});
3710 LatchVPBB, MiddleVPBB, ORE,
3711 TheLoop, PSE, DT, AC);
3716 for (
unsigned Idx = 0; Idx != Exits.
size(); ++Idx) {
3720 VectorEarlyExitVPBBs[Idx] = VectorEarlyExitVPBB;
3728 Exits.
size() == 1 ? VectorEarlyExitVPBBs[0]
3731 LatchVPBB->setSuccessors({DispatchVPBB, MiddleVPBB, HeaderVPBB});
3763 for (
auto [Exit, VectorEarlyExitVPBB] :
3764 zip_equal(Exits, VectorEarlyExitVPBBs)) {
3765 auto &[EarlyExitingVPBB, EarlyExitVPBB,
_] = Exit;
3777 ExitIRI->getIncomingValueForBlock(EarlyExitingVPBB);
3778 VPValue *NewIncoming = IncomingVal;
3780 VPBuilder EarlyExitBuilder(VectorEarlyExitVPBB);
3785 ExitIRI->removeIncomingValueFor(EarlyExitingVPBB);
3786 ExitIRI->addIncoming(NewIncoming);
3789 EarlyExitingVPBB->getTerminator()->eraseFromParent();
3824 bool IsLastDispatch = (
I + 2 == Exits.
size());
3826 IsLastDispatch ? VectorEarlyExitVPBBs.
back()
3832 VectorEarlyExitVPBBs[
I]->setPredecessors({CurrentBB});
3835 CurrentBB = FalseBB;
3850 VPValue *VecOp = Red->getVecOp();
3853 if (Red->isPartialReduction())
3857 auto IsExtendedRedValidAndClampRange =
3870 "getExtendedReductionCost only supports integer types");
3871 ExtRedCost = Ctx.TTI.getExtendedReductionCost(
3872 Opcode, ExtOpc == Instruction::CastOps::ZExt, RedTy, SrcVecTy,
3873 Red->getFastMathFlagsOrNone(), CostKind);
3874 return ExtRedCost.
isValid() && ExtRedCost < ExtCost + RedCost;
3882 IsExtendedRedValidAndClampRange(
3902 Type *LHSSrcTy =
LHS->getOperand(0)->getScalarType();
3904 Type *RHSSrcTy =
RHS ?
RHS->getOperand(0)->getScalarType() : LHSSrcTy;
3906 if (
Mul->getScalarType()->getScalarSizeInBits() >=
3909 if (ExtKind == ExtendKind::PR_ZeroExtend)
3910 return Mul->hasNoUnsignedWrap();
3911 return ExtKind == ExtendKind::PR_SignExtend &&
Mul->hasNoSignedWrap();
3927 if (Opcode != Instruction::Add && Opcode != Instruction::Sub &&
3928 Opcode != Instruction::FAdd)
3932 if (Red->isPartialReduction())
3938 auto IsMulAccValidAndClampRange =
3950 (Ext0->getOpcode() != Ext1->getOpcode() ||
3951 Ext0->getOpcode() == Instruction::CastOps::FPExt))
3955 !Ext0 || Ext0->getOpcode() == Instruction::CastOps::ZExt;
3957 MulAccCost = Ctx.TTI.getMulAccReductionCost(IsZExt, Opcode, RedTy,
3958 SrcVecTy, CostKind);
3964 ExtCost += Ext0->computeCost(VF, Ctx);
3966 ExtCost += Ext1->computeCost(VF, Ctx);
3968 ExtCost += OuterExt->computeCost(VF, Ctx);
3970 return MulAccCost.
isValid() &&
3971 MulAccCost < ExtCost + MulCost + RedCost;
3976 VPValue *VecOp = Red->getVecOp();
4014 Builder.createWidenCast(Instruction::CastOps::Trunc, ValB, NarrowTy);
4016 ValB = ExtB = Builder.createWidenCast(ExtOpc, Trunc, WideTy);
4017 Mul->setOperand(1, ExtB);
4027 ExtendAndReplaceConstantOp(RecipeA, RecipeB,
B,
Mul);
4032 IsMulAccValidAndClampRange(
Mul, RecipeA, RecipeB,
nullptr)) {
4039 if (!
Sub && IsMulAccValidAndClampRange(
Mul,
nullptr,
nullptr,
nullptr))
4056 ExtendAndReplaceConstantOp(Ext0, Ext1,
B,
Mul);
4065 (Ext->getOpcode() == Ext0->getOpcode() ||
4066 (Ext0 == Ext1 && Ext0->getOpcode() == Instruction::SExt)) &&
4067 Ext0->getOpcode() == Ext1->getOpcode() &&
Mul->hasOneUse() &&
4069 IsMulAccValidAndClampRange(
Mul, Ext0, Ext1, Ext)) {
4071 Ext0->getOpcode(), Ext0->getOperand(0), Ext->getScalarType(),
nullptr,
4072 *Ext0, *Ext0, Ext0->getDebugLoc());
4073 NewExt0->insertBefore(Ext0);
4078 Ext->getScalarType(),
nullptr, *Ext1,
4079 *Ext1, Ext1->getDebugLoc());
4082 auto *NewMul =
Mul->cloneWithOperands({NewExt0, NewExt1});
4083 NewMul->insertBefore(
Mul);
4084 Ext->replaceAllUsesWith(NewMul);
4085 Ext->eraseFromParent();
4086 Mul->eraseFromParent();
4100 if (Red->isPartialReduction())
4104 auto IP = std::next(Red->getIterator());
4114 Red->replaceAllUsesWith(AbstractR);
4136 return CommonMetadata;
4139template <
unsigned Opcode>
4144 static_assert(Opcode == Instruction::Load || Opcode == Instruction::Store,
4145 "Only Load and Store opcodes supported");
4152 for (
auto Recipes :
Groups) {
4153 if (Recipes.size() < 2)
4157 "Expected all recipes in group to have the same load-store type");
4164 VPValue *MaskI = RecipeI->getMask();
4170 bool HasComplementaryMask =
false;
4175 VPValue *MaskJ = RecipeJ->getMask();
4184 if (HasComplementaryMask) {
4185 assert(Group.
size() >= 2 &&
"must have at least 2 entries");
4195template <
typename InstType>
4213 for (
auto &Group :
Groups) {
4233 return R->isSingleScalar() == IsSingleScalar;
4235 "all members in group must agree on IsSingleScalar");
4240 LoadWithMinAlign->getUnderlyingInstr(), {EarliestLoad->getOperand(0)},
4241 IsSingleScalar,
nullptr, *EarliestLoad, CommonMetadata);
4243 UnpredicatedLoad->insertBefore(EarliestLoad);
4247 Load->replaceAllUsesWith(UnpredicatedLoad);
4248 Load->eraseFromParent();
4257 if (!StoreLoc || !StoreLoc->AATags.Scope)
4264 SinkStoreInfo SinkInfo(StoresToSink, *StoresToSink[0], PSE, L);
4276 for (
auto &Group :
Groups) {
4288 VPValue *SelectedValue = Group[0]->getOperand(0);
4291 bool IsSingleScalar = Group[0]->isSingleScalar();
4292 for (
unsigned I = 1;
I < Group.size(); ++
I) {
4293 assert(IsSingleScalar == Group[
I]->isSingleScalar() &&
4294 "all members in group must agree on IsSingleScalar");
4295 VPValue *Mask = Group[
I]->getMask();
4297 SelectedValue = Builder.createSelect(
4300 Value->getScalarType()));
4308 StoreWithMinAlign->getUnderlyingInstr(),
4309 {SelectedValue, LastStore->getOperand(1)}, IsSingleScalar,
4310 nullptr, *LastStore, CommonMetadata);
4311 UnpredicatedStore->insertBefore(LastStore);
4315 Store->eraseFromParent();
4322 assert(UF > 1 &&
"Expected plan to have an UF > 1");
4332 VPValue *StoredValue =
nullptr;
4343 assert(
MemOp->isConsecutive() &&
"Expected consecutive load/store");
4350 auto MaskSource =
MemOp->isMasked()
4355 : R.getVPSingleValue()->getScalarType();
4357 std::optional<Instruction::CastOps> CastHint;
4359 : R.getVPSingleValue()->getSingleUser();
4361 CastHint = Cast->getOpcode();
4364 if (!
TTI.hasMultiVectorLoadStore(UF, MaskSource,
4365 VectorAccessType, IsStore, CastHint))
4375 VPValue *WideStoredValue = Builder.createNaryOp(
4377 NewMemOp = Builder.createNaryOp(
4379 {Multiplier, Ptr,
Align, WideStoredValue},
nullptr, {}, *
MemOp,
DL);
4381 VPValue *OldLoad = R.getVPSingleValue();
4382 NewMemOp = Builder.createNaryOp(
4391 R.eraseFromParent();
4393 assert((!MaskPhi || Mask == MaskPhi) &&
"Expected a single mask phi");
4414 "Expected incoming values of Phi to be WideActiveLaneMask");
4429 "Expected entry/loop extract-vector-for-part ops");
4430 EntryMask->replaceAllUsesWith(EntryALM);
4431 LoopMask->replaceAllUsesWith(LoopALM);
4450 if (Member0Op == OpV)
4460 return !
IsScalable && !W->getMask() && W->isConsecutive() &&
4463 return IR->getInterleaveGroup()->isFull() &&
IR->getVPValue(Idx) == OpV;
4482 if (R->getScalarType() != WideMember0->getScalarType())
4484 if (R->hasPredicate() && R->getPredicate() != WideMember0->getPredicate())
4492 if (
V->isDefinedOutsideLoopRegions())
4494 auto [It, Inserted] = FirstMembersOf.try_emplace(
V,
Ops);
4495 if (!Inserted && (It->second.front() ==
V ||
V == WideMember0) &&
4500 for (
unsigned Idx = 0; Idx != WideMember0->getNumOperands(); ++Idx) {
4503 OpsI.
push_back(
Op->getDefiningRecipe()->getOperand(Idx));
4509 const auto &[OpIdx, OpV] =
P;
4521static std::optional<ElementCount>
4525 if (!InterleaveR || InterleaveR->
getMask())
4526 return std::nullopt;
4528 Type *GroupElementTy =
nullptr;
4532 return Op->getScalarType() == GroupElementTy;
4534 return std::nullopt;
4538 return Op->getScalarType() == GroupElementTy;
4540 return std::nullopt;
4544 if (IG->getFactor() != IG->getNumMembers() || IG->isReverse())
4545 return std::nullopt;
4551 assert(
Size.isScalable() == VF.isScalable() &&
4552 "if Size is scalable, VF must be scalable and vice versa");
4553 return Size.getKnownMinValue();
4557 unsigned MinVal = VF.getKnownMinValue();
4559 if (IG->getFactor() == MinVal && GroupSize == GetVectorBitWidthForVF(VF))
4562 return std::nullopt;
4570 return RepR && RepR->isSingleScalar();
4584 if (
V->isDefinedOutsideLoopRegions()) {
4587 return M->isDefinedOutsideLoopRegions() &&
4588 M->getScalarType() ==
V->getScalarType();
4590 "expected distinct loop-invariant values of matching scalar type");
4605 for (
unsigned Idx = 0,
E = WideMember0->getNumOperands(); Idx !=
E; ++Idx) {
4607 for (
VPValue *Member : Members)
4608 OpsI.
push_back(Member->getDefiningRecipe()->getOperand(Idx));
4609 WideMember0->setOperand(
4621 *LI, LoadGroup->getAddr(), LoadGroup->getMask(),
true,
4622 IG->
getAlign(), *LoadGroup, LoadGroup->getDebugLoc());
4628 VPValue *PtrOp = WideLoad->getAddr();
4630 PtrOp = VecPtr->getOperand(0);
4635 nullptr, {}, *WideLoad);
4636 N->insertBefore(WideLoad);
4641std::unique_ptr<VPlan>
4661 "unexpected branch-on-count");
4665 std::optional<ElementCount> VFToOptimize;
4679 if (R.mayWriteToMemory() && !InterleaveR)
4685 return any_of(V->users(), [&](VPUser *U) {
4686 auto *UR = cast<VPRecipeBase>(U);
4687 return UR->getParent()->getParent() != VectorLoop;
4704 std::optional<ElementCount> NarrowedVF =
4706 if (!NarrowedVF || (VFToOptimize && NarrowedVF != VFToOptimize))
4708 VFToOptimize = NarrowedVF;
4711 if (InterleaveR->getStoredValues().empty())
4716 auto *Member0 = InterleaveR->getStoredValues()[0];
4726 VPRecipeBase *DefR = Op.value()->getDefiningRecipe();
4729 auto *IR = dyn_cast<VPInterleaveRecipe>(DefR);
4730 return IR && IR->getInterleaveGroup()->isFull() &&
4731 IR->getVPValue(Op.index()) == Op.value();
4740 VFToOptimize->isScalable(), FirstMembersOf))
4745 if (StoreGroups.empty())
4749 bool RequiresScalarEpilogue =
4760 std::unique_ptr<VPlan> NewPlan;
4762 NewPlan = std::unique_ptr<VPlan>(Plan.
duplicate());
4763 Plan.
setVF(*VFToOptimize);
4764 NewPlan->removeVF(*VFToOptimize);
4771 for (
auto *StoreGroup : StoreGroups) {
4773 NarrowedOps, Preheader);
4779 StoreGroup->getDebugLoc());
4786 Type *CanIVTy = VectorLoop->getCanonicalIVType();
4792 if (VFToOptimize->isScalable()) {
4795 Step = PHBuilder.createOverflowingOp(Instruction::Mul, {VScale,
UF},
4803 materializeVectorTripCount(Plan, VectorPH,
false,
4804 RequiresScalarEpilogue, Step);
4809 removeDeadRecipes(Plan);
4812 "All VPVectorPointerRecipes should have been removed");
4830 "Cannot handle loops with uncountable early exits");
4837 assert(RecurSplice &&
"expected FirstOrderRecurrenceSplice");
4844 if (
any_of(RecurSplice->users(),
4845 [](
VPUser *U) { return !cast<VPRecipeBase>(U)->getRegion(); }) &&
4926 {},
"vector.recur.extract.for.phi");
4929 ExitPhi->replaceUsesOfWith(ExtractR, PenultimateElement);
4943 VPValue *WidenIVCandidate = BinOp->getOperand(0);
4944 VPValue *InvariantCandidate = BinOp->getOperand(1);
4946 std::swap(WidenIVCandidate, InvariantCandidate);
4960 auto *ClonedOp = BinOp->
clone();
4961 if (ClonedOp->getOperand(0) == WidenIV) {
4962 ClonedOp->setOperand(0, ScalarIV);
4964 assert(ClonedOp->getOperand(1) == WidenIV &&
"one operand must be WideIV");
4965 ClonedOp->setOperand(1, ScalarIV);
4979 return std::nullopt;
4984 return std::nullopt;
4996 auto CheckSentinel = [&SE](
const SCEV *IVSCEV,
4997 bool UseMax) -> std::optional<APSInt> {
4999 for (
bool Signed : {
true,
false}) {
5008 return std::nullopt;
5016 PhiR->getRecurrenceKind()))
5025 VPValue *BackedgeVal = PhiR->getBackedgeValue();
5039 !
match(FindLastSelect,
5048 IVOfExpressionToSink ? IVOfExpressionToSink : FindLastExpression, PSE,
5053 "IVOfExpressionToSink not being an AddRec must imply "
5054 "FindLastExpression not being an AddRec.");
5063 bool UseMax = *StepDirection;
5064 std::optional<APSInt> SentinelVal = CheckSentinel(IVSCEV, UseMax);
5065 bool UseSigned = SentinelVal && SentinelVal->isSigned();
5072 if (IVOfExpressionToSink) {
5073 const SCEV *FindLastExpressionSCEV =
5075 if (std::optional<bool> NewUseMax =
5077 if (
auto NewSentinel =
5078 CheckSentinel(FindLastExpressionSCEV, *NewUseMax)) {
5081 SentinelVal = *NewSentinel;
5082 UseSigned = NewSentinel->isSigned();
5083 UseMax = *NewUseMax;
5084 IVSCEV = FindLastExpressionSCEV;
5085 IVOfExpressionToSink =
nullptr;
5095 if (AR->hasNoSignedWrap())
5097 else if (AR->hasNoUnsignedWrap())
5107 VPValue *NewFindLastSelect = BackedgeVal;
5109 if (!SentinelVal || IVOfExpressionToSink) {
5112 DebugLoc DL = FindLastSelect->getDefiningRecipe()->getDebugLoc();
5113 VPBuilder LoopBuilder(FindLastSelect->getDefiningRecipe());
5114 if (
match(FindLastSelect,
5116 SelectCond = LoopBuilder.
createNot(SelectCond);
5123 if (SelectCond !=
Cond || IVOfExpressionToSink) {
5126 IVOfExpressionToSink ? IVOfExpressionToSink : FindLastExpression,
5135 VPIRFlags Flags(MinMaxKind,
false,
false,
5141 NewFindLastSelect, Flags, ExitDL);
5144 VPValue *VectorRegionExitingVal = ReducedIV;
5145 bool SunkExpression =
false;
5146 if (IVOfExpressionToSink) {
5147 VectorRegionExitingVal =
5149 ReducedIV, IVOfExpressionToSink);
5150 SunkExpression =
true;
5154 VPValue *StartVPV = PhiR->getStartValue();
5161 NewRdxResult = MiddleBuilder.
createSelect(Cmp, VectorRegionExitingVal,
5171 AnyOfPhi->insertAfter(PhiR);
5178 OrVal, VectorRegionExitingVal, StartVPV, ExitDL);
5191 PhiR->hasUsesOutsideReductionChain());
5193 NewPhiR->setExpressionSunk();
5194 NewPhiR->insertBefore(PhiR);
5195 PhiR->replaceAllUsesWith(NewPhiR);
5196 PhiR->eraseFromParent();
5202struct ReductionExtend {
5203 Type *SrcType =
nullptr;
5210struct ExtendedReductionOperand {
5214 ReductionExtend ExtendA, ExtendB;
5222struct PartialReductionDescriptor {
5225 VPWidenRecipe *ReductionBinOp =
nullptr;
5227 ExtendedReductionOperand ExtendedOp;
5234 unsigned AccumulatorOpIdx;
5235 unsigned ScaleFactor;
5238 VPBlendRecipe *Blend =
nullptr;
5243static std::optional<unsigned>
5247 "Expected a non-normalized blend with two incoming values");
5253 return std::nullopt;
5254 return FirstIncomingHasOneUse ? 0 : 1;
5266 if (!
Op->hasOneUse() ||
5272 auto *Trunc = Builder.createWidenCast(Instruction::CastOps::Trunc,
5273 Op->getOperand(1), NarrowTy);
5275 Op->setOperand(1, Builder.createWidenCast(ExtOpc, Trunc, WideTy));
5284 auto *
Sub =
Op->getOperand(0)->getDefiningRecipe();
5286 assert(Ext->getOpcode() ==
5288 "Expected both the LHS and RHS extends to be the same");
5289 bool IsSigned = Ext->getOpcode() == Instruction::SExt;
5292 auto *FreezeX = Builder.insert(
new VPWidenRecipe(Instruction::Freeze, {
X}));
5293 auto *FreezeY = Builder.insert(
new VPWidenRecipe(Instruction::Freeze, {
Y}));
5294 auto *
Max = Builder.insert(
5296 {FreezeX, FreezeY}, SrcTy));
5297 auto *Min = Builder.insert(
5299 {FreezeX, FreezeY}, SrcTy));
5300 auto *AbsDiff = Builder.insert(
5303 return Builder.createWidenCast(Instruction::CastOps::ZExt, AbsDiff,
5304 Op->getScalarType());
5316 assert(
Mul->hasOneUse() && Ext->getOpcode() == MulLHS->getOpcode() &&
5317 MulLHS->getOpcode() == MulRHS->getOpcode() &&
5319 "Expected the outer extend to be foldable");
5321 auto *NewLHS = Builder.createWidenCast(
5322 MulLHS->getOpcode(), MulLHS->getOperand(0), Ext->getScalarType());
5323 auto *NewRHS = MulLHS == MulRHS
5325 : Builder.createWidenCast(MulRHS->getOpcode(),
5326 MulRHS->getOperand(0),
5327 Ext->getScalarType());
5328 auto *NewMul =
Mul->cloneWithOperands({NewLHS, NewRHS});
5329 Builder.insert(NewMul);
5330 Op->replaceAllUsesWith(NewMul);
5331 Op->eraseFromParent();
5332 Mul->eraseFromParent();
5341 VPValue *VecOp = Red->getVecOp();
5394static void transformToPartialReduction(
const PartialReductionDescriptor &Link,
5402 WidenRecipe->
getOperand(1 - Link.AccumulatorOpIdx));
5405 ExtendedOp = optimizeExtendsForPartialReduction(ExtendedOp);
5421 if ((WidenRecipe->
getOpcode() == Instruction::Sub &&
5423 (WidenRecipe->
getOpcode() == Instruction::FSub &&
5428 if (WidenRecipe->
getOpcode() == Instruction::FSub) {
5440 Builder.insert(NegRecipe);
5441 ExtendedOp = NegRecipe;
5456 std::optional<unsigned> BlendReductionIdx =
5457 getBlendReductionUpdateValueIdx(Link.Blend);
5458 assert(BlendReductionIdx &&
5460 "Expected blend to contain the reduction update");
5474 [[maybe_unused]]
bool IsLastInChain =
5478 assert((!ExitValue || IsLastInChain) &&
5479 "if we found ExitValue, it must match RdxPhi's backedge value");
5490 PartialRed->insertBefore(WidenRecipe);
5500 E->insertBefore(WidenRecipe);
5501 PartialRed->replaceAllUsesWith(
E);
5507 const PartialReductionDescriptor &Link,
5510 const ExtendedReductionOperand &ExtendedOp = Link.ExtendedOp;
5511 std::optional<unsigned> BinOpc = std::nullopt;
5513 if (ExtendedOp.ExtendB.Kind != ExtendKind::PR_None)
5514 BinOpc = ExtendedOp.ExtendsUser->
getOpcode();
5516 std::optional<llvm::FastMathFlags>
Flags;
5520 auto GetLinkOpcode = [&Link]() ->
unsigned {
5523 return Instruction::Add;
5525 return Instruction::FAdd;
5527 return Link.ReductionBinOp->
getOpcode();
5532 GetLinkOpcode(), ExtendedOp.ExtendA.SrcType, ExtendedOp.ExtendB.SrcType,
5533 RdxType, VF, ExtendedOp.ExtendA.Kind, ExtendedOp.ExtendB.Kind, BinOpc,
5550static std::optional<ExtendedReductionOperand>
5553 "Op should be operand of UpdateR");
5561 if (
Op->hasOneUse() &&
5570 Type *RHSInputType =
Y->getScalarType();
5571 if (LHSInputType != RHSInputType ||
5572 LHSExt->getOpcode() != RHSExt->getOpcode())
5573 return std::nullopt;
5576 return ExtendedReductionOperand{
5582 std::optional<TTI::PartialReductionExtendKind> OuterExtKind;
5585 VPValue *CastSource = CastRecipe->getOperand(0);
5596 return ExtendedReductionOperand{
5603 if (!
Op->hasOneUse())
5604 return std::nullopt;
5609 return std::nullopt;
5619 return std::nullopt;
5626 const APInt *RHSConst =
nullptr;
5632 return std::nullopt;
5636 if (Cast && OuterExtKind &&
5638 return std::nullopt;
5640 Type *RHSInputType = LHSInputType;
5649 if (OuterExtKind && MulOp->
getOpcode() == Instruction::Mul &&
5651 return std::nullopt;
5653 return ExtendedReductionOperand{
5654 MulOp, {LHSInputType, LHSExtendKind}, {RHSInputType, RHSExtendKind}};
5661static std::optional<SmallVector<PartialReductionDescriptor>>
5668 return std::nullopt;
5669 VPValue *ExitValue = RdxResult->getOperand(0);
5678 VPValue *CurrentValue = ExitValue;
5679 while (CurrentValue != RedPhiR) {
5681 std::optional<unsigned> BlendReductionIdx;
5685 return std::nullopt;
5687 BlendReductionIdx = getBlendReductionUpdateValueIdx(Blend);
5688 if (!BlendReductionIdx)
5689 return std::nullopt;
5696 return std::nullopt;
5703 std::optional<ExtendedReductionOperand> ExtendedOp =
5704 matchExtendedReductionOperand(UpdateR,
Op);
5706 ExtendedOp = matchExtendedReductionOperand(UpdateR, PrevValue);
5708 return std::nullopt;
5716 return std::nullopt;
5718 Type *ExtSrcType = ExtendedOp->ExtendA.SrcType;
5721 return std::nullopt;
5723 PartialReductionDescriptor Link(
5724 {UpdateR, *ExtendedOp, RK,
5729 CurrentValue = PrevValue;
5734 std::reverse(Chain.
begin(), Chain.
end());
5744 assert(Phi->getVFScaleFactor() == 1 &&
"scale factor must not be set");
5745 Phi->setVFScaleFactor(Factor);
5750 StartInst->setOperand(2, NewScaleFactor);
5757 VPValue *OldStartValue = StartInst->getOperand(0);
5758 StartInst->setOperand(0, StartInst->getOperand(1));
5762 assert(RdxResult &&
"Could not find reduction result");
5765 unsigned SubOpc = RK ==
RecurKind::FSub ? Instruction::BinaryOps::FSub
5766 : Instruction::BinaryOps::Sub;
5769 Phi->getDebugLoc());
5785 if (
auto Chain = getScaledReductionChain(&RedPhiR))
5786 PhiToChain.
try_emplace(&RedPhiR, std::move(*Chain));
5787 else if (CostCtx.
Opts.use_partial_reductions_by_default &&
5791 UnorderedReductions.
push_back(&RedPhiR);
5797 for (
auto *Rdx : UnorderedReductions) {
5813 ? std::make_optional(Rdx->getFastMathFlagsOrNone())
5817 Backedge->getOpcode(), ScalarTy,
nullptr,
5819 std::nullopt, CostCtx.
CostKind, FMF);
5820 return PRCost <= CurrentCost;
5826 Rdx->getRecurrenceKind(), Rdx->getFastMathFlagsOrNone(),
5827 Backedge->getUnderlyingInstr(), Rdx, OtherOp,
nullptr,
5830 Partial->insertBefore(Backedge);
5831 Backedge->replaceAllUsesWith(Partial);
5832 Backedge->eraseFromParent();
5835 if (PhiToChain.
empty())
5843 for (
auto &[
_, Chain] : PhiToChain)
5844 for (
const PartialReductionDescriptor &Link : Chain) {
5845 PartialReductionOps.
insert(Link.ExtendedOp.ExtendsUser);
5847 PartialReductionBlends.
insert(Link.Blend);
5848 ScaledReductionMap[Link.ReductionBinOp] = Link.ScaleFactor;
5854 auto ExtendUsersValid = [&](
VPValue *Ext) {
5856 return PartialReductionOps.contains(cast<VPRecipeBase>(U));
5860 auto IsProfitablePartialReductionChainForVF =
5867 for (
const PartialReductionDescriptor &Link : Chain) {
5868 const ExtendedReductionOperand &ExtendedOp = Link.ExtendedOp;
5869 InstructionCost LinkCost = getPartialReductionLinkCost(CostCtx, Link, VF);
5873 PartialCost += LinkCost;
5874 RegularCost += Link.ReductionBinOp->
computeCost(VF, CostCtx);
5876 if (ExtendedOp.ExtendB.Kind != ExtendKind::PR_None)
5877 RegularCost += ExtendedOp.ExtendsUser->
computeCost(VF, CostCtx);
5880 RegularCost += Extend->computeCost(VF, CostCtx);
5882 return PartialCost.
isValid() && PartialCost < RegularCost;
5890 for (
auto &[RedPhiR, Chain] : PhiToChain) {
5891 for (
const PartialReductionDescriptor &Link : Chain) {
5892 if (!
all_of(Link.ExtendedOp.ExtendsUser->
operands(), ExtendUsersValid)) {
5896 auto UseIsValid = [&, RedPhiR = RedPhiR](
VPUser *U) {
5898 return PhiR == RedPhiR;
5902 return Blend == Link.Blend || PartialReductionBlends.
contains(Blend);
5904 return Link.ScaleFactor == ScaledReductionMap.
lookup_or(R, 0) ||
5910 if (!
all_of(Link.ReductionBinOp->
users(), UseIsValid)) {
5919 auto *RepR = dyn_cast<VPReplicateRecipe>(U);
5920 return RepR && RepR->getOpcode() == Instruction::Store;
5931 return IsProfitablePartialReductionChainForVF(Chain, VF);
5937 for (
auto &[Phi, Chain] : PhiToChain) {
5941 for (
const PartialReductionDescriptor &Link : Chain)
5942 transformToPartialReduction(Link, Plan, Phi);
5947 const PartialReductionDescriptor &Link = Chain[0];
5963 if (VPI.getUnderlyingValue() &&
5974 auto ProcessSubset = [&](
VPlan &,
auto ProcessVPInst) {
5977 if (!ProcessVPInst(VPI))
5986 assert(New->getParent() &&
"New recipe must have been inserted");
5987 if (VPI->
getOpcode() == Instruction::Load)
5996 return ReplaceWith(VPI,
VPBuilder(VPI).insert(
6003 "lowerMemoryIdioms", ProcessSubset, Plan, [&](
VPInstruction *VPI) {
6005 VPI, FinalRedStoresBuilder))
6014 return ReplaceWith(VPI,
VPBuilder(VPI).insert(Histogram));
6027 "scalarizeMemOpsWithIrregularTypes", ProcessSubset, Plan,
6031 return Scalarize(VPI);
6038 "makeVPlanMemOpDecision", ProcessSubset, Plan, [&](
VPInstruction *VPI) {
6040 bool IsLoad = VPI->
getOpcode() == Instruction::Load;
6050 const SCEV *PtrSCEV =
6052 bool IsSingleScalarLoad =
6058 I, Ptr, IsSingleScalarLoad,
6067 "widenConsecutiveMemOps", ProcessSubset, Plan, [&](
VPInstruction *VPI) {
6069 bool IsLoad = VPI->
getOpcode() == Instruction::Load;
6073 std::optional<int64_t> Stride =
6075 if (Stride != 1 && Stride != -1)
6107 return ReplaceWith(VPI,
Load);
6116 auto *StoreR = Builder.createWidenStore(
6119 return ReplaceWith(VPI, StoreR);
6126 return ReplaceWith(VPI, Recipe);
6128 return Scalarize(VPI);
6148 if (VPI.mayHaveSideEffects())
6153 if (VPI.getOpcode() == Instruction::ExtractValue)
6157 if (VPI.isMasked() && !VPI.isSafeToSpeculativelyExecute())
6165 VPI.getOpcode(), VPI.operandsWithoutMask(),
nullptr, VPI,
6166 VPI, VPI.getDebugLoc(), VPI.getScalarType(),
I);
6167 Recipe->insertBefore(&VPI);
6168 VPI.replaceAllUsesWith(Recipe);
6169 VPI.eraseFromParent();
6179 switch (Param.ParamKind) {
6180 case VFParamKind::Vector:
6181 case VFParamKind::GlobalPredicate:
6183 case VFParamKind::OMP_Uniform:
6184 return SE->isSCEVable(Args[Param.ParamPos]->getScalarType()) &&
6185 SE->isLoopInvariant(
6186 vputils::getSCEVExprForVPValue(Args[Param.ParamPos], PSE, L),
6188 case VFParamKind::OMP_Linear:
6189 return match(vputils::getSCEVExprForVPValue(Args[Param.ParamPos], PSE, L),
6190 m_scev_AffineAddRec(
6191 m_SCEV(), m_scev_SpecificSInt(Param.LinearStepOrPos),
6192 m_SpecificLoop(L)));
6209 const auto *It =
find_if(Mappings, [&](
const VFInfo &Info) {
6210 return Info.Shape.VF == VF && (!MaskRequired || Info.isMasked()) &&
6213 if (It == Mappings.end())
6220struct CallWideningDecision {
6221 enum class KindTy { Scalarize,
Intrinsic, VectorVariant };
6222 CallWideningDecision(KindTy Kind,
Function *Variant =
nullptr)
6245 return CallWideningDecision::KindTy::Scalarize;
6255 return CallWideningDecision::KindTy::Scalarize;
6259 false, VF, CostCtx);
6274 return CallWideningDecision::KindTy::Intrinsic;
6278 if (VecFunc && ScalarCost >= VecCallCost)
6279 return {CallWideningDecision::KindTy::VectorVariant, VecFunc};
6281 return CallWideningDecision::KindTy::Scalarize;
6287 bool Widened =
false;
6292 if (!VPI.getUnderlyingValue() || VPI.getOpcode() != Instruction::Call)
6297 VPI.op_begin() + CI->arg_size());
6299 CallWideningDecision Decision =
6307 assert((Decision.Kind == CallWideningDecision::KindTy::Scalarize ||
6308 !CI->hasOperandBundles()) &&
6309 "calls with operand bundles must not be widened");
6311 switch (Decision.Kind) {
6312 case CallWideningDecision::KindTy::Intrinsic: {
6316 VPI, VPI.getDebugLoc());
6320 case CallWideningDecision::KindTy::VectorVariant: {
6325 Ops.push_back(Mask);
6327 Ops.push_back(VPI.getOperand(VPI.getNumOperandsWithoutMask() - 1));
6330 Attrs, VPI.getDebugLoc());
6334 case CallWideningDecision::KindTy::Scalarize:
6340 VPI.replaceAllUsesWith(Replacement);
6341 VPI.eraseFromParent();
6358 if (VPI.getOpcode() != Instruction::Trunc)
6382 !
TTI.isTruncateFree(
6383 toVectorTy(VPI.getOperand(0)->getScalarType(), VF),
6387 IsNarrowingProfitable,
Range))
6393 WideIV->getPHINode(), WideIV->getStartValue(), WideIV->getStepValue(),
6394 WideIV->getVFValue(), WideIV->getInductionDescriptor(),
6398 VPI.replaceAllUsesWith(NarrowIV);
6399 VPI.eraseFromParent();
6421 if (!MemR || MemR->isConsecutive())
6424 VPValue *Ptr = MemR->getAddr();
6436 VPValue *StoredValue =
nullptr;
6440 StoredValue = StoreR->getStoredValue();
6442 IntrinID = Intrinsic::experimental_vp_strided_store;
6446 IntrinID = Intrinsic::experimental_vp_strided_load;
6449 Align Alignment = MemR->getAlign();
6452 if (!Ctx.TTI.isLegalStridedLoadStore(VectorTy, Alignment))
6457 IntrinID, VectorTy, MemR->isMasked(), Alignment, Ctx);
6458 return StridedLoadStoreCost < CurrentCost;
6469 Ctx.invalidateWideningDecision(&MemR->getIngredient(), VF);
6474 I32VF = Builder.createScalarZExtOrTrunc(
6488 "Stride type from SCEV must match the index type");
6489 VPValue *CanIV = Builder.createScalarZExtOrTrunc(
6492 auto *
Offset = Builder.createOverflowingOp(
6493 Instruction::Mul, {CanIV, StrideInBytes},
6494 {AddRecPtr->hasNoUnsignedWrap(),
false});
6498 VPValue *BasePtr = Builder.createNoWrapPtrAdd(StartVPV,
Offset, NWFlags);
6501 VPValue *NewPtr = Builder.createVectorPointer(
6505 VPValue *Mask = MemR->getMask();
6510 Ops.push_back(StoredValue);
6511 Ops.append({NewPtr, StrideInBytes, Mask, I32VF});
6513 auto *StridedR = Builder.createWidenMemIntrinsic(
6516 *MemR, R.getDebugLoc());
6519 R.eraseFromParent();
6526 if (
Range.Start.isScalar())
6542 Intrinsic::experimental_cttz_elts, IdxTy,
6546 return BeforeFirst->computeCost(VF, Ctx) <
6547 Ctx.TTI.getIntrinsicInstrCost(CttzElts, Ctx.CostKind) +
6548 Ctx.TTI.getIntrinsicInstrCost(ActiveLaneMask, Ctx.CostKind);
6555 VPValue *FirstActive = Builder.createScalarZExtOrTrunc(
6556 Builder.createFirstActiveLane(
X,
DL), Ty,
DL);
6557 VPValue *PartStart = Builder.createOverflowingOp(
6562 BeforeFirst->eraseFromParent();
6575 if (std::optional<CompressedPtrInfo> Info =
6577 CondIndToMemOps[Info->ConditionalInductionPHI].push_back(&VPI);
6582 for (
auto &CondIndPhi :
6587 assert(!BlendR->isNormalized() &&
"Expected to run before simpifyBlends");
6588 for (
unsigned ValIdx :
seq(BlendR->getNumIncomingValues()))
6589 if (
VPValue *IncomingValue = BlendR->getIncomingValue(ValIdx);
6590 IncomingValue != &CondIndPhi) {
6591 Mask = BlendR->getMask(ValIdx);
6594 assert(Mask &&
"Expected mask for conditional induction update");
6598 for (
VPInstruction *VPI : CondIndToMemOps[CondIndPhi.getPHINode()]) {
6601 if (VPI->getMask() != Mask)
6604 Builder.setInsertPoint(VPI);
6605 auto *CompressedMemOp =
6608 VPI->replaceAllUsesWith(CompressedMemOp);
6609 VPI->eraseFromParent();
6615 if (UpdateType->isPointerTy())
6619 const SCEV *StepSCEV = CondIndPhi.getStepSCEV();
6621 Builder.setInsertPoint(BlendR);
6624 {},
DL,
"handled.lanes");
6627 Step = Builder.createFreeze(Step);
6630 Instruction::Mul, {Step, HandledLanes}, {
false,
false},
DL);
6633 ? Builder.createPtrAdd(&CondIndPhi,
Offset,
DL,
"conditional.step")
6634 : Builder.createAdd(&CondIndPhi,
Offset,
DL,
"conditional.step");
6635 CondIndPhi.getBackedgeValue()->replaceAllUsesWith(Update);
const TargetLowering & TLI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static bool isEqual(AttributeSet CallerAttrs, AttributeSet CalleeAttrs)
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
iv Induction Variable Users
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
Legalize the Machine IR a function s Machine IR
This file provides utility analysis objects describing memory locations.
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
Function const char * Passes
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
This file contains the declarations for profiling metadata utility functions.
SmallVector< MachineOperand, 4 > Cond
This is the interface for a metadata-based scoped no-alias analysis.
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")
This file implements the TypeSwitch template, which mimics a switch() statement whose cases are type ...
This file implements dominator tree analysis for a single level of a VPlan's H-CFG.
This file contains the declarations of different VPlan-related auxiliary helpers.
This file contains the declarations of the Vectorization Plan base classes:
static const X86InstrFMA3Group Groups[]
static const uint32_t IV[8]
Helper for extra no-alias checks via known-safe recipe and SCEV.
SinkStoreInfo(ArrayRef< VPReplicateRecipe * > ExcludeRecipes, VPReplicateRecipe &GroupLeader, PredicatedScalarEvolution &PSE, const Loop &L)
SinkStoreInfo(VPReplicateRecipe &GroupLeader)
bool shouldSkip(VPRecipeBase &R) const
Return true if R should be skipped during alias checking, either because it's in the exclude set or b...
Class for arbitrary precision integers.
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
LLVM_ABI APInt zextOrTrunc(unsigned width) const
Zero extend or truncate to width.
unsigned getActiveBits() const
Compute the number of active bits in the value.
APInt abs() const
Get the absolute value.
unsigned getBitWidth() const
Return the number of bits in the APInt.
int32_t exactLogBase2() const
bool isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
LLVM_ABI APInt sext(unsigned width) const
Sign extend to a new width.
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
An arbitrary precision integer that knows its signedness.
static APSInt getMinValue(uint32_t numBits, bool Unsigned)
Return the APSInt representing the minimum integer value with the given bit width and signedness.
static APSInt getMaxValue(uint32_t numBits, bool Unsigned)
Return the APSInt representing the maximum integer value with the given bit width and signedness.
@ NoAlias
The two locations do not alias at all.
Represent a constant reference to an array (0 or more elements consecutively in memory),...
const T & back() const
Get the last element.
ArrayRef< T > drop_front(size_t N=1) const
Drop the first N elements of the array.
const T & front() const
Get the first element.
size_t size() const
Get the array size.
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.
bool isNoBuiltin() const
Return true if the call should not be treated as a call to a builtin.
This class represents a function call, abstracting a target machine's calling convention.
@ ICMP_ULT
unsigned less than
@ ICMP_ULE
unsigned less or equal
@ FCMP_UNO
1 0 0 0 True if unordered: isnan(X) | isnan(Y)
bool isTrueWhenEqual() const
This is just a convenience.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
This class represents a range of values.
LLVM_ABI bool contains(const APInt &Val) const
Return true if the specified value is in the set.
A parsed version of the target data layout string in and methods for querying it.
LLVM_ABI IntegerType * getIndexType(LLVMContext &C, unsigned AddressSpace) const
Returns the type of a GEP index in AddressSpace.
static DebugLoc getUnknown()
ValueT lookup_or(const_arg_type_t< KeyT > Val, U &&Default) const
ValueT lookup(const_arg_type_t< KeyT > Val) const
Return the entry for the specified key, or a default constructed value if no such entry exists.
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
bool dominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
dominates - Returns true iff A dominates B.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
static constexpr ElementCount getScalable(ScalarTy MinVal)
constexpr bool isScalar() const
Exactly one element.
Convenience struct for specifying and reasoning about fast-math flags.
FunctionType * getFunctionType() const
Returns the FunctionType for me.
Represents flags for the getelementptr instruction/expression.
static GEPNoWrapFlags noUnsignedWrap()
bool hasNoUnsignedWrap() const
GEPNoWrapFlags withoutNoUnsignedWrap() const
static GEPNoWrapFlags none()
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
A struct for saving information about induction variables.
InductionKind
This enum represents the kinds of inductions that we support.
@ IK_PtrInduction
Pointer induction var. Step = C.
@ IK_IntInduction
Integer induction variable. Step = C.
static InstructionCost getInvalid(CostType Val=0)
LLVM_ABI const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this instruction belongs to.
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
The group of interleaved loads/stores sharing the same stride and close to each other.
InstTy * getInsertPos() const
This is an important class for using LLVM in a threaded context.
An instruction for reading from memory.
static bool getDecisionAndClampRange(const std::function< bool(ElementCount)> &Predicate, VFRange &Range)
Test a Predicate on a Range of VF's.
Represents a single loop in the control flow graph.
LLVM_ABI MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight, bool IsExpected=false)
Return metadata containing two branch weights.
This class implements a map that also provides access to all stored values in a deterministic order.
ValueT lookup(const KeyT &Key) const
std::pair< iterator, bool > try_emplace(const KeyT &Key, Ts &&...Args)
Representation for a specific memory location.
Function * getFunction(StringRef Name) const
Look up the specified function in the module symbol table.
Post-order traversal of a graph.
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
LLVM_ABI const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
static LLVM_ABI unsigned getOpcode(RecurKind Kind)
Returns the opcode corresponding to the RecurrenceKind.
unsigned getOpcode() const
static bool isFindLastRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...
LLVM_ABI bool match(StringRef String, SmallVectorImpl< StringRef > *Matches=nullptr, std::string *Error=nullptr) const
matches - Match the regex against a given String.
RegionT * getParent() const
Get the parent of the Region.
This class represents a constant integer value.
ConstantInt * getValue() const
static const SCEV * rewrite(const SCEV *Scev, ScalarEvolution &SE, ValueToSCEVMapTy &Map)
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.
The main scalar evolution driver.
const DataLayout & getDataLayout() const
Return the DataLayout associated with the module this SCEV instance is operating on.
LLVM_ABI const SCEV * getElementCount(Type *Ty, ElementCount EC, SCEVFlags Flags=SCEV::FlagNone)
LLVM_ABI bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
LLVM_ABI const SCEV * getMinusSCEV(SCEVUse LHS, SCEVUse RHS, SCEVFlags Flags=SCEV::FlagNone, unsigned Depth=0)
Return LHS-RHS.
LLVM_ABI const SCEV * getConstant(ConstantInt *V)
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
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.
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
LLVM_ABI bool isKnownPredicate(CmpPredicate Pred, SCEVUse LHS, SCEVUse RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
LLVM_ABI bool isGuaranteedNotToCauseUB(const SCEV *Op)
Returns true if Op is guaranteed not to cause immediate UB.
LLVM_ABI const SCEV * getNegativeSCEV(const SCEV *V, SCEVFlags Flags=SCEV::FlagNone)
Return the SCEV object corresponding to -V.
A simple AA result which uses scoped-noalias metadata to answer queries.
A vector that has set insertion semantics.
size_type size() const
Determine the number of elements in the SetVector.
bool insert(const value_type &X)
Insert a new element into the SetVector.
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.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
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.
Represent a constant reference to a string, i.e.
Provides information about what library functions are available for the current target.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
static LLVM_ABI IntegerType * getInt32Ty(LLVMContext &C)
bool isPointerTy() const
True if this is an instance of PointerType.
static LLVM_ABI Type * getVoidTy(LLVMContext &C)
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
static LLVM_ABI IntegerType * getInt8Ty(LLVMContext &C)
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
bool isFloatingPointTy() const
Return true if this is one of the floating-point types.
bool isIntOrPtrTy() const
Return true if this is an integer type or a pointer type.
bool isIntegerTy() const
True if this is an instance of IntegerType.
static SmallVector< VFInfo, 8 > getMappings(const CallInst &CI)
Retrieve all the VFInfo instances associated to the CallInst CI.
bool isLegalMaskedLoadOrStore(bool IsLoad, Type *ScalarTy, Align Alignment, unsigned AddressSpace) const
Returns true if the target machine supports a masked load (if IsLoad) or masked store of scalar type ...
A recipe for generating the active lane mask for the vector loop that is used to predicate the vector...
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
void appendRecipe(VPRecipeBase *Recipe)
Augment the existing recipes of a VPBasicBlock with an additional Recipe as the last recipe.
RecipeListTy::iterator iterator
Instruction iterators...
iterator begin()
Recipe iterator methods.
iterator_range< iterator > phis()
Returns an iterator range over the PHI-like recipes in the block.
iterator getFirstNonPhi()
Return the position of the first non-phi node recipe in the block.
VPBasicBlock * splitAt(iterator SplitAt)
Split current block at SplitAt by inserting a new block between the current block and its successors ...
const VPRecipeBase & front() const
VPRecipeBase * getTerminator()
If the block has multiple successors, return the branch recipe terminating the block.
const VPRecipeBase & back() const
A recipe for vectorizing a phi-node as a sequence of mask-based select instructions.
VPValue * getIncomingValue(unsigned Idx) const
Return incoming value number Idx.
VPValue * getMask(unsigned Idx) const
Return mask number Idx.
unsigned getNumIncomingValues() const
Return the number of incoming values, taking into account when normalized the first incoming value wi...
void setMask(unsigned Idx, VPValue *V)
Set mask number Idx to V.
bool isNormalized() const
A normalized blend is one that has an odd number of operands, whereby the first operand does not have...
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
void setSuccessors(ArrayRef< VPBlockBase * > NewSuccs)
Set each VPBasicBlock in NewSuccss as successor of this VPBlockBase.
VPRegionBlock * getParent()
const VPBasicBlock * getExitingBasicBlock() const
size_t getNumSuccessors() const
void setPredecessors(ArrayRef< VPBlockBase * > NewPreds)
Set each VPBasicBlock in NewPreds as predecessor of this VPBlockBase.
const VPBlocksTy & getPredecessors() const
VPBlockBase * getSinglePredecessor() const
void clearPredecessors()
Remove all the predecessor of this block.
const VPBasicBlock * getEntryBasicBlock() const
VPBlockBase * getSingleSuccessor() const
const VPBlocksTy & getSuccessors() const
static auto blocksAs(T &&Range)
Return an iterator range over Range with each block cast to BlockTy.
static void insertOnEdge(VPBlockBase *From, VPBlockBase *To, VPBlockBase *BlockPtr)
Inserts BlockPtr on the edge between From and To.
static bool isLatch(const VPBlockBase *VPB, const VPDominatorTree &VPDT)
Returns true if VPB is a loop latch, using isHeader().
static VPBasicBlock * getPlainCFGMiddleBlock(const VPlan &Plan)
Returns the middle block of Plan in plain CFG form (before regions are formed).
static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse, VPBlockBase *BlockPtr)
Insert disconnected VPBlockBases IfTrue and IfFalse after BlockPtr.
static void connectBlocks(VPBlockBase *From, VPBlockBase *To, unsigned PredIdx=-1u, unsigned SuccIdx=-1u)
Connect VPBlockBases From and To bi-directionally.
static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To)
Disconnect VPBlockBases From and To bi-directionally.
static auto blocksOnly(T &&Range)
Return an iterator range over Range which only includes BlockTy blocks.
static std::pair< VPBasicBlock *, VPBasicBlock * > getPlainCFGHeaderAndLatch(const VPlan &Plan)
Returns the header and latch of the outermost loop of Plan in plain CFG form (before regions are form...
static void transferSuccessors(VPBlockBase *Old, VPBlockBase *New)
Transfer successors from Old to New. New must have no successors.
static SmallVector< VPBasicBlock * > blocksInSingleSuccessorChainBetween(VPBasicBlock *FirstBB, VPBasicBlock *LastBB)
Returns the blocks between FirstBB and LastBB, where FirstBB to LastBB forms a single-sucessor chain.
A recipe for generating conditional branches on the bits of a mask.
VPlan-based builder utility similar to IRBuilder.
VPInstruction * createFreeze(VPValue *Op, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="")
VPWidenIntrinsicRecipe * createWidenIntrinsic(Intrinsic::ID VectorIntrinsicID, ArrayRef< VPValue * > CallArguments, Type *Ty, const VPIRFlags &Flags={}, const VPIRMetadata &MD={}, DebugLoc DL=DebugLoc::getUnknown())
static VPBuilderBase getToInsertAfter(VPRecipeBase *R)
VPInstruction * createLogicalAnd(VPValue *LHS, VPValue *RHS, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="")
VPInstruction * createAnyOfReduction(VPValue *ChainOp, VPValue *TrueVal, VPValue *FalseVal, DebugLoc DL=DebugLoc::getUnknown())
Create an AnyOf reduction pattern: or-reduce ChainOp, freeze the result, then select between TrueVal ...
VPDerivedIVRecipe * createDerivedIV(InductionDescriptor::InductionKind Kind, FPMathOperator *FPBinOp, VPValue *Start, VPValue *Current, VPValue *Step, const VPIRFlags::WrapFlagsTy &Flags={})
Convert Current to Start + Current * Step.
VPWidenCastRecipe * createWidenCast(Instruction::CastOps Opcode, VPValue *Op, Type *ResultTy)
VPInstruction * createAdd(VPValue *LHS, VPValue *RHS, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="", VPRecipeWithIRFlags::WrapFlagsTy WrapFlags={false, false})
VPInstruction * createSelect(VPValue *Cond, VPValue *TrueVal, VPValue *FalseVal, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="", std::optional< VPIRFlags > Flags=std::nullopt)
Create a select of TrueVal and FalseVal based on Cond, using the default flags for the result type,...
VPValue * createScalarZExtOrTrunc(VPValue *Op, Type *ResultTy, DebugLoc DL)
static VPSingleDefRecipe * createSingleScalarOp(unsigned Opcode, ArrayRef< VPValue * > Operands, VPValue *Mask, const VPIRFlags &Flags, const VPIRMetadata &Metadata, DebugLoc DL, Type *ResultTy, Instruction *UV)
VPWidenLoadRecipe * createWidenLoad(LoadInst &Load, VPValue *Addr, VPValue *Mask, bool Consecutive, Align Alignment, const VPIRMetadata &Metadata, DebugLoc DL)
Create a recipe widening Load, loading from Addr with Mask (may be null).
VPInstruction * createLogicalOr(VPValue *LHS, VPValue *RHS, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="")
VPInstruction * createScalarCast(Instruction::CastOps Opcode, VPValue *Op, Type *ResultTy, DebugLoc DL, std::optional< VPIRFlags > Flags=std::nullopt, const VPIRMetadata &Metadata={})
VPInstruction * createNot(VPValue *Operand, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="")
void setInsertPoint(const VPInsertPoint &IP)
Set the current insert point.
VPInstruction * createNaryOp(unsigned Opcode, ArrayRef< VPValue * > Operands, Instruction *Inst=nullptr, const VPIRFlags &Flags={}, const VPIRMetadata &MD={}, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="", Type *ResultTy=nullptr, const VPIRAttributes &Attrs={})
Create an N-ary operation with Opcode, Operands and set Inst as its underlying Instruction.
VPInstruction * createFirstActiveLane(ArrayRef< VPValue * > Masks, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="")
VPWidenStoreRecipe * createWidenStore(StoreInst &Store, VPValue *Addr, VPValue *StoredVal, VPValue *Mask, bool Consecutive, Align Alignment, const VPIRMetadata &Metadata, DebugLoc DL)
Create a recipe widening Store, storing StoredVal to Addr with Mask (may be null).
VPInstruction * createOr(VPValue *LHS, VPValue *RHS, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="")
VPInstruction * createICmp(CmpInst::Predicate Pred, VPValue *A, VPValue *B, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="")
Create a new ICmp VPInstruction with predicate Pred and operands A and B.
unsigned getNumDefinedValues() const
Returns the number of values defined by the VPDef.
VPValue * getVPSingleValue()
Returns the only VPValue defined by the VPDef.
VPValue * getVPValue(unsigned I)
Returns the VPValue with index I defined by the VPDef.
ArrayRef< VPRecipeValue * > definedValues()
Returns an ArrayRef of the values defined by the VPDef.
Template specialization of the standard LLVM dominator tree utility for VPBlockBases.
LLVM_ABI_FOR_TEST bool properlyDominates(const VPRecipeBase *A, const VPRecipeBase *B) const
Recipe to expand a SCEV expression.
A recipe to combine multiple recipes into a single 'expression' recipe, which should be considered a ...
A recipe representing a sequence of load -> update -> store as part of a histogram operation.
Manage IR attributes for call recipes.
A special type of VPBasicBlock that wraps an existing IR basic block.
Class to record and manage LLVM IR flags.
static LLVM_ABI_FOR_TEST VPIRFlags getDefaultFlags(unsigned Opcode, Type *ResultTy=nullptr)
Returns default flags for Opcode and scalar ResultTy for opcodes that support it, asserts otherwise.
LLVM_ABI_FOR_TEST FastMathFlags getFastMathFlagsOrNone() const
This is a concrete Recipe that models a single VPlan-level instruction.
unsigned getNumOperandsWithoutMask() const
Returns the number of operands, excluding the mask if the VPInstruction is masked.
@ ExtractLane
Extracts a single lane (first operand) from a set of vector operands.
@ ExtractPenultimateElement
@ ReductionStartVector
Start vector for reductions with 3 operands: the original start value, the identity value for the red...
@ BuildVector
Creates a fixed-width vector containing all operands.
@ CanonicalIVIncrementForPart
@ ComputeReductionResult
Reduce the operands to the final reduction result using the operation specified via the operation's V...
void addMask(VPValue *Mask)
Add mask Mask to an unmasked VPInstruction, if it needs masking.
unsigned getOpcode() const
VPValue * getMask() const
Returns the mask for the VPInstruction.
const InterleaveGroup< Instruction > * getInterleaveGroup() const
VPValue * getMask() const
Return the mask used by this recipe.
ArrayRef< VPValue * > getStoredValues() const
Return the VPValues stored by this interleave group.
VPInterleaveRecipe is a recipe for transforming an interleave group of load or stores into one wide l...
VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when control converges back from ...
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
void moveBefore(RecipeListTy::iterator I)
Unlink this recipe and insert it before I.
VPRegionBlock * getRegion()
RecipeListTy::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
DebugLoc getDebugLoc() const
Returns the debug location of the recipe.
void insertBefore(VPRecipeBase *InsertPos)
Insert an unlinked recipe into a basic block immediately before the specified recipe.
void insertAfter(VPRecipeBase *InsertPos)
Insert an unlinked Recipe into a basic block immediately after the specified Recipe.
Helper class to create VPRecipies from IR instructions.
VPHistogramRecipe * widenIfHistogram(VPInstruction *VPI)
If VPI represents a histogram operation (as determined by LoopVectorizationLegality) make that safe f...
std::optional< CompressedPtrInfo > getCompressedPtrInfo(VPInstruction *VPI)
Returns the CompressedPtrInfo for VPI if it is a compressed load or store (as determined by LoopVecto...
bool prefersVectorizedAddressing() const
Returns true if the target prefers vectorized addressing.
VPRecipeBase * tryToWidenMemory(VPInstruction *VPI, VFRange &Range)
Check if the load or store instruction VPI should widened for Range.Start and potentially masked.
bool replaceWithFinalIfReductionStore(VPInstruction *VPI, VPBuilder &FinalRedStoresBuilder)
If VPI is a store of a reduction into an invariant address, delete it.
VPSingleDefRecipe * handleReplication(VPInstruction *VPI, VFRange &Range)
Build a replicating or single-scalar recipe for VPI.
VPWidenMemIntrinsicRecipe * widenCompressedLoadOrStore(VPInstruction *VPI)
Build a llvm.masked.expandload or llvm.masked.compressstore intrinsic for VPI.
bool isPredicatedInst(Instruction *I) const
Returns true if I needs to be predicated (i.e.
Type * getScalarType() const
Returns the scalar type of this VPRecipeValue.
A recipe for handling reduction phis.
bool isOrdered() const
Returns true, if the phi is part of an ordered reduction.
bool isInLoop() const
Returns true if the phi is part of an in-loop reduction.
RecurKind getRecurrenceKind() const
Returns the recurrence kind of the reduction.
A recipe to represent inloop, ordered or partial reduction operations.
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
const VPBlockBase * getEntry() const
bool isReplicator() const
An indicator whether this region is to generate multiple replicated instances of output IR correspond...
void setExiting(VPBlockBase *ExitingBlock)
Set ExitingBlock as the exiting VPBlockBase of this VPRegionBlock.
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print this VPRegionBlock to O (recursively), prefixing all lines with Indent.
Type * getCanonicalIVType() const
Return the type of the canonical IV for loop regions.
VPRegionValue * getCanonicalIV()
Return the canonical induction variable of the region, null for replicating regions.
const VPBlockBase * getExiting() const
VPRegionValue * getHeaderMask() const
Return the header mask of the region, or null if not set.
VPReplicateRecipe replicates a given instruction producing multiple scalar copies of the original sca...
bool isSingleScalar() const
Returns true if the recipe produces a single scalar value.
static InstructionCost computeCallCost(Function *CalledFn, Type *ResultTy, ArrayRef< const VPValue * > ArgOps, bool IsSingleScalar, ElementCount VF, VPCostContext &Ctx)
Return the cost of scalarizing a call to CalledFn with argument operands ArgOps for a given VF.
operand_range operandsWithoutMask()
Return the recipe's operands, excluding the mask of a predicated recipe.
bool isPredicated() const
VPValue * getMask()
Return the mask of a predicated VPReplicateRecipe.
Lightweight SCEV-to-VPlan expander.
VPValue * expand(const SCEV *S)
Expand S into recipes and live-ins using the builder.
A recipe for handling phi nodes of integer and floating-point inductions, producing their scalar valu...
VPSingleDefRecipe is a base class for recipes that model a sequence of one or more output IR that def...
Instruction * getUnderlyingInstr()
Returns the underlying instruction.
VPSingleDefRecipe * clone() override=0
Clone the current recipe.
A symbolic live-in VPValue, used for values like vector trip count, VF, and VFxUF.
This class augments VPValue with operands which provide the inverse def-use edges from VPValue's user...
void setOperand(unsigned I, VPValue *New)
unsigned getNumOperands() const
VPValue * getOperand(unsigned N) const
This is the base class of the VPlan Def/Use graph, used for modeling the data flow into,...
Type * getScalarType() const
Returns the scalar type of this VPValue, dispatching based on the concrete subclass.
Value * getLiveInIRValue() const
Return the underlying IR value for a VPIRValue.
bool isDefinedOutsideLoopRegions() const
Returns true if the VPValue is defined outside any loop.
VPRecipeBase * getDefiningRecipe()
Returns the recipe defining this VPValue or nullptr if it is not defined by a recipe,...
bool hasMoreThanOneUniqueUser() const
Returns true if the value has more than one unique user.
Value * getUnderlyingValue() const
Return the underlying Value attached to this VPValue.
void replaceUsesWithIf(VPValue *New, llvm::function_ref< bool(VPUser *U)> ShouldReplace)
Go through the uses list for this VPValue and make each use point to New if the callback ShouldReplac...
VPUser * getSingleUser()
Return the single user of this value, or nullptr if there is not exactly one user.
void replaceAllUsesWith(VPValue *New)
A recipe to compute a pointer to the last element of each part of a widened memory access for widened...
A recipe for widening Call instructions using library calls.
static InstructionCost computeCallCost(Function *Variant, VPCostContext &Ctx)
Return the cost of widening a call using the vector function Variant.
VPWidenCastRecipe is a recipe to create vector cast instructions.
Instruction::CastOps getOpcode() const
A recipe for handling GEP instructions.
Base class for widened induction (VPWidenIntOrFpInductionRecipe and VPWidenPointerInductionRecipe),...
PHINode * getPHINode() const
Returns the underlying PHINode if one exists, or null otherwise.
VPValue * getStepValue()
Returns the step value of the induction.
const InductionDescriptor & getInductionDescriptor() const
Returns the induction descriptor for the recipe.
A recipe for handling phi nodes of integer and floating-point inductions, producing their vector valu...
bool isTruncated() const
Returns true if this induction is evaluated in a narrower type than the start value.
A recipe for widening vector intrinsics.
static InstructionCost computeCallCost(Intrinsic::ID ID, ArrayRef< const VPValue * > Operands, const VPRecipeWithIRFlags &R, ElementCount VF, VPCostContext &Ctx)
Compute the cost of a vector intrinsic with ID and Operands.
static InstructionCost computeMemIntrinsicCost(Intrinsic::ID IID, Type *Ty, bool IsMasked, Align Alignment, VPCostContext &Ctx)
Helper function for computing the cost of vector memory intrinsic.
A common mixin class for widening memory operations.
virtual VPRecipeBase * getAsRecipe()=0
Return a VPRecipeBase* to the current object.
A recipe for widened phis.
VPWidenRecipe is a recipe for producing a widened instruction using the opcode and operands of the re...
InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const override
Return the cost of this VPWidenRecipe.
VPWidenRecipe * clone() override
Clone the current recipe.
unsigned getOpcode() const
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
VPIRValue * getLiveIn(Value *V) const
Return the live-in VPIRValue for V, if there is one or nullptr otherwise.
bool hasVF(ElementCount VF) const
const DataLayout & getDataLayout() const
LLVMContext & getContext() const
VPBasicBlock * getEntry()
bool hasScalableVF() const
VPValue * getTripCount() const
The trip count of the original loop.
iterator_range< SmallSetVector< ElementCount, 2 >::iterator > vectorFactors() const
Returns an iterator range over all VFs of the plan.
VPIRValue * getFalse()
Return a VPIRValue wrapping i1 false.
VPSymbolicValue & getVFxUF()
Returns VF * UF of the vector loop region.
VPIRValue * getAllOnesValue(Type *Ty)
Return a VPIRValue wrapping the AllOnes value of type Ty.
VPRegionBlock * createReplicateRegion(VPBlockBase *Entry, VPBlockBase *Exiting, const std::string &Name="")
Create a new replicate region with Entry, Exiting and Name.
auto getLiveIns() const
Return the list of live-in VPValues available in the VPlan.
bool hasUF(unsigned UF) const
ArrayRef< VPIRBasicBlock * > getExitBlocks() const
Return an ArrayRef containing VPIRBasicBlocks wrapping the exit blocks of the original scalar loop.
VPSymbolicValue & getVectorTripCount()
The vector trip count.
VPIRValue * getOrAddLiveIn(Value *V)
Gets the live-in VPIRValue for V or adds a new live-in (if none exists yet) for V.
VPIRValue * getZero(Type *Ty)
Return a VPIRValue wrapping the null value of type Ty.
void setVF(ElementCount VF)
bool isUnrolled() const
Returns true if the VPlan already has been unrolled, i.e.
LLVM_ABI_FOR_TEST VPRegionBlock * getVectorLoopRegion()
Returns the VPRegionBlock of the vector loop.
unsigned getConcreteUF() const
Returns the concrete UF of the plan, after unrolling.
void resetTripCount(VPValue *NewTripCount)
Resets the trip count for the VPlan.
VPBasicBlock * getMiddleBlock()
Returns the 'middle' block of the plan, that is the block that selects whether to execute the scalar ...
VPBasicBlock * createVPBasicBlock(const Twine &Name, VPRecipeBase *Recipe=nullptr)
Create a new VPBasicBlock with Name and containing Recipe if present.
VPIRValue * getTrue()
Return a VPIRValue wrapping i1 true.
VPBasicBlock * getVectorPreheader() const
Returns the preheader of the vector loop region, if one exists, or null otherwise.
VPSymbolicValue & getUF()
Returns the UF of the vector loop region.
bool hasScalarVFOnly() const
VPBasicBlock * getScalarPreheader() const
Return the VPBasicBlock for the preheader of the scalar loop.
bool hasTailFolded() const
Returns true if the vector loop region is tail-folded.
VPSymbolicValue & getVF()
Returns the VF of the vector loop region.
LLVM_ABI_FOR_TEST VPlan * duplicate()
Clone the current VPlan, update all VPValues of the new VPlan and cloned recipes to refer to the clon...
VPIRValue * getConstantInt(Type *Ty, uint64_t Val, bool IsSigned=false)
Return a VPIRValue wrapping a ConstantInt with the given type and value.
LLVM Value Representation.
iterator_range< user_iterator > users()
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
Base class of all SIMD vector types.
static LLVM_ABI VectorType * get(Type *ElementType, ElementCount EC)
This static method is the primary way to construct an VectorType.
constexpr bool hasKnownScalarFactor(const FixedOrScalableQuantity &RHS) const
Returns true if there exists a value X where RHS*X will result in a value whose quantity matches our ...
constexpr ScalarTy getFixedValue() const
constexpr ScalarTy getKnownScalarFactor(const FixedOrScalableQuantity &RHS) const
Returns a value X where RHS*X will result in a value whose quantity matches our own.
static constexpr bool isKnownLT(const FixedOrScalableQuantity &LHS, const FixedOrScalableQuantity &RHS)
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
constexpr bool isFixed() const
Returns true if the quantity is not scaled by vscale.
constexpr ScalarTy getKnownMinValue() const
Returns the minimum value this quantity can represent.
An efficient, type-erasing, non-owning reference to a callable.
const ParentTy * getParent() const
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
LLVM_ABI APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM)
Return A unsign-divided by B, rounded by the given rounding mode.
std::variant< std::monostate, Loc::Single, Loc::Multi, Loc::MMI, Loc::EntryValue > Variant
Alias for the std::variant specialization base class of DbgVariable.
void reportVectorizationFailure(const StringRef DebugMsg, const StringRef OREMsg, const StringRef ORETag, OptimizationRemarkEmitter *ORE, const Loop *TheLoop, Instruction *I=nullptr)
Reports a vectorization failure: print DebugMsg for debugging purposes along with the corresponding o...
SpecificConstantMatch m_ZeroInt()
Convenience matchers for specific integer values.
AllOnesConstantMatch m_AllOnes()
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
OneUse_match< SubPat > m_OneUse(const SubPat &SP)
match_unless< Pattern > m_Unless(const Pattern &P)
Match if the inner matcher does NOT match.
match_isa< To... > m_Isa()
match_combine_or< Ty... > m_CombineOr(const Ty &...Ps)
Combine pattern matchers matching any of Ps patterns.
auto m_Cmp()
Matches any compare instruction and ignore it.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
FNeg_match< OpTy, false > m_FNeg(const OpTy &X)
Match fneg X only.
BinaryOp_match< LHS, RHS, Instruction::URem > m_URem(const LHS &L, const RHS &R)
OneOps_match< OpTy, Instruction::Freeze > m_Freeze(const OpTy &Op)
Matches FreezeInst.
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
CastInst_match< OpTy, TruncInst > m_Trunc(const OpTy &Op)
Matches Trunc.
LogicalOp_match< LHS, RHS, Instruction::And > m_LogicalAnd(const LHS &L, const RHS &R)
Matches L && R either in the form of L & R or L ?
specific_intval< false > m_SpecificInt(const APInt &V)
Match a specific integer value or vector with all elements equal to the value.
BinaryOp_match< LHS, RHS, Instruction::FMul > m_FMul(const LHS &L, const RHS &R)
bool match(Val *V, const Pattern &P)
match_deferred< Value > m_Deferred(Value *const &V)
Like m_Specific(), but works if the specific value to match is determined as part of the same match()...
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
CmpClass_match< LHS, RHS, CmpInst, true > m_c_Cmp(const LHS &L, const RHS &R)
CmpClass_match< LHS, RHS, ICmpInst, true > m_c_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
Matches an ICmp with a predicate over LHS and RHS in either order.
auto match_fn(const Pattern &P)
A match functor that can be used as a UnaryPredicate in functional algorithms like all_of.
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
SpecificCmpClass_match< LHS, RHS, CmpInst > m_SpecificCmp(CmpPredicate MatchPred, const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
CastInst_match< OpTy, FPExtInst > m_FPExt(const OpTy &Op)
SpecificCmpClass_match< LHS, RHS, ICmpInst > m_SpecificICmp(CmpPredicate MatchPred, const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::UDiv > m_UDiv(const LHS &L, const RHS &R)
SelectLike_match< CondTy, LTy, RTy > m_SelectLike(const CondTy &C, const LTy &TrueC, const RTy &FalseC)
Matches a value that behaves like a boolean-controlled select, i.e.
BinaryOp_match< LHS, RHS, Instruction::Add, true > m_c_Add(const LHS &L, const RHS &R)
Matches a Add with LHS and RHS in either order.
CastOperator_match< OpTy, Instruction::BitCast > m_BitCast(const OpTy &Op)
Matches BitCast.
auto m_Intrinsic(const Ts &...Ops)
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
auto m_MaskedStore(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2)
Matches MaskedStore Intrinsic.
auto m_MaskedLoad(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2)
Matches MaskedLoad Intrinsic.
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
match_combine_or< CastInst_match< OpTy, ZExtInst >, CastInst_match< OpTy, SExtInst > > m_ZExtOrSExt(const OpTy &Op)
BinaryOp_match< LHS, RHS, Instruction::FAdd, true > m_c_FAdd(const LHS &L, const RHS &R)
Matches FAdd with LHS and RHS in either order.
LogicalOp_match< LHS, RHS, Instruction::And, true > m_c_LogicalAnd(const LHS &L, const RHS &R)
Matches L && R with LHS and RHS in either order.
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
CastInst_match< OpTy, SExtInst > m_SExt(const OpTy &Op)
Matches SExt.
LogicalOp_match< LHS, RHS, Instruction::Or, true > m_c_LogicalOr(const LHS &L, const RHS &R)
Matches L || R with LHS and RHS in either order.
BinaryOp_match< LHS, RHS, Instruction::Mul, true > m_c_Mul(const LHS &L, const RHS &R)
Matches a Mul with LHS and RHS in either order.
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
auto m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
bind_cst_ty m_scev_APInt(const APInt *&C)
Match an SCEV constant and bind it to an APInt.
cst_pred_ty< is_one > m_scev_One()
Match an integer 1.
specificloop_ty m_SpecificLoop(const Loop *L)
bool match(const SCEV *S, const Pattern &P)
SCEVAffineAddRec_match< Op0_t, Op1_t, match_isa< const Loop > > m_scev_AffineAddRec(const Op0_t &Op0, const Op1_t &Op1)
VPInstruction_match< VPInstruction::ExtractLastLane, VPInstruction_match< VPInstruction::ExtractLastPart, Op0_t > > m_ExtractLastLaneOfLastPart(const Op0_t &Op0)
AllRecipe_commutative_match< Instruction::And, Op0_t, Op1_t > m_c_BinaryAnd(const Op0_t &Op0, const Op1_t &Op1)
Match a binary AND operation.
AllRecipe_match< Instruction::Or, Op0_t, Op1_t > m_BinaryOr(const Op0_t &Op0, const Op1_t &Op1)
Match a binary OR operation.
VPInstruction_match< VPInstruction::AnyOf > m_AnyOf()
RecipeTy * findSingleUser(VPValue *V, const MatchT &P)
Return the sole user of V matching pattern P, casting it to RecipeTy, or nullptr.
AllRecipe_commutative_match< Instruction::Or, Op0_t, Op1_t > m_c_BinaryOr(const Op0_t &Op0, const Op1_t &Op1)
VPInstruction_match< VPInstruction::ComputeReductionResult, Op0_t > m_ComputeReductionResult(const Op0_t &Op0)
auto m_WidenAnyExtend(const Op0_t &Op0)
match_bind< VPIRValue > m_VPIRValue(VPIRValue *&V)
Match a VPIRValue.
auto m_VPPhi(const Op0_t &Op0, const Op1_t &Op1)
VPInstruction_match< VPInstruction::BranchOnTwoConds > m_BranchOnTwoConds()
VPWidenStoreRecipe_match< Op0_t, Op1_t > m_WidenStore(const Op0_t &Op0, const Op1_t &Op1)
AllRecipe_match< Opcode, Op0_t, Op1_t > m_Binary(const Op0_t &Op0, const Op1_t &Op1)
VPWidenLoadRecipe_match< Op0_t > m_WidenLoad(const Op0_t &Op0)
VPInstruction_match< VPInstruction::LastActiveLane, Op0_t > m_LastActiveLane(const Op0_t &Op0)
auto m_WidenIntrinsic(const T &...Ops)
canonical_widen_iv_match m_CanonicalWidenIV()
VPInstruction_match< VPInstruction::ExitingIVValue, Op0_t > m_ExitingIVValue(const Op0_t &Op0)
VPInstruction_match< Instruction::ExtractElement, Op0_t, Op1_t > m_ExtractElement(const Op0_t &Op0, const Op1_t &Op1)
ActiveLaneMaskPHIRecipe_match< Op0_t, Op1_t > m_ActiveLaneMaskPhi(const Op0_t &Op0, const Op1_t &Op1)
VectorPointerRecipe_match< Op0_t, Op1_t > m_VecPtr(const Op0_t &Op0, const Op1_t &Op1)
VPInstruction_match< VPInstruction::ExtractLastLane, Op0_t > m_ExtractLastLane(const Op0_t &Op0)
int_pred_ty< is_zero_int, 1 > m_False()
match_bind< VPSingleDefRecipe > m_VPSingleDefRecipe(VPSingleDefRecipe *&V)
Match a VPSingleDefRecipe, capturing if we match.
VPInstruction_match< VPInstruction::BranchOnCount > m_BranchOnCount()
auto m_GetElementPtr(const Op0_t &Op0, const Op1_t &Op1)
auto m_VPValue()
Match an arbitrary VPValue and ignore it.
VPInstruction_match< VPInstruction::ExtractLastPart, Op0_t > m_ExtractLastPart(const Op0_t &Op0)
VPInstruction_match< VPInstruction::Broadcast, Op0_t > m_Broadcast(const Op0_t &Op0)
bool match(Val *V, const Pattern &P)
header_mask_match m_HeaderMask()
VPInstruction_match< VPInstruction::BuildVector > m_BuildVector()
BuildVector is matches only its opcode, w/o matching its operands as the number of operands is not fi...
VPInstruction_match< VPInstruction::ExtractPenultimateElement, Op0_t > m_ExtractPenultimateElement(const Op0_t &Op0)
match_bind< VPInstruction > m_VPInstruction(VPInstruction *&V)
Match a VPInstruction, capturing if we match.
VPInstruction_match< VPInstruction::FirstActiveLane, Op0_t > m_FirstActiveLane(const Op0_t &Op0)
int_pred_ty< is_one, 1 > m_True()
VPInstruction_match< VPInstruction::WideActiveLaneMask, Op_t... > m_WideActiveLaneMask(const Op_t &...Op)
VPInstruction_match< VPInstruction::ExtractVectorForPart, Op_t... > m_ExtractVectorForPart(const Op_t &...Op)
auto m_DerivedIV(const Op0_t &Op0, const Op1_t &Op1, const Op2_t &Op2)
VPInstruction_match< VPInstruction::BranchOnCond > m_BranchOnCond()
VPInstruction_match< VPInstruction::ExtractLane, Op0_t, Op1_t > m_ExtractLane(const Op0_t &Op0, const Op1_t &Op1)
auto m_AnyNeg(const Op0_t &Op0)
VPInstruction_match< VPInstruction::Reverse, Op0_t > m_Reverse(const Op0_t &Op0)
NodeAddr< DefNode * > Def
bool isSingleScalar(const VPValue *VPV)
Returns true if VPV is a single scalar, either because it produces the same value for all lanes or on...
bool cannotHoistOrSinkRecipe(const VPRecipeBase &R, bool Sinking=false)
Return true if we do not know how to (mechanically) hoist or sink R.
unsigned getOpcode(const VPValue *V)
Return the instruction opcode for the recipe defining V or 0 for unsupported recipes and VPValues not...
std::optional< int64_t > getConstantStride(VPValue *Addr, Type *AccessTy, PredicatedScalarEvolution &PSE, const Loop *L)
If the pointer operand Addr of a memory access is an affine AddRec w.r.t.
VPInstruction * findComputeReductionResult(VPReductionPHIRecipe *PhiR)
Find the ComputeReductionResult recipe for PhiR, looking through selects inserted for predicated redu...
VPInstruction * findCanonicalIVIncrement(VPlan &Plan)
Find the canonical IV increment of Plan's vector loop region.
std::optional< MemoryLocation > getMemoryLocation(const VPRecipeBase &R)
Return a MemoryLocation for R with noalias metadata populated from R, if the recipe is supported and ...
bool onlyFirstLaneUsed(const VPValue *Def)
Returns true if only the first lane of Def is used by all users.
VPIRValue * tryToFoldLiveIns(VPSingleDefRecipe &R, ArrayRef< VPValue * > Operands, const DataLayout &DL)
Try to fold R using InstSimplifyFolder.
SmallVector< std::pair< VPBasicBlock *, VPIRBasicBlock * > > getEarlyExits(const VPlan &Plan, const VPBlockBase *MiddleVPBB)
Returns the (early exiting block, exit block) pairs of Plan, i.e.
Type * getLoadStoreValueType(VPSingleDefRecipe *R)
Get the value type of a VPInstruction or VPReplicateRecipe load or store.
VPScalarIVStepsRecipe * createScalarIVSteps(VPlan &Plan, InductionDescriptor::InductionKind Kind, Instruction::BinaryOps InductionOpcode, FPMathOperator *FPBinOp, Type *ResultTy, VPValue *StartV, VPValue *Step, DebugLoc DL, VPBuilder &Builder, const VPIRFlags::WrapFlagsTy &Flags={})
Create a scalar-iv-steps recipe over Plan's canonical IV for an induction of Kind with InductionOpcod...
void recursivelyDeleteDeadRecipes(VPValue *V)
Recursively delete V and any of its operands that become dead.
bool doesGeneratePerAllLanes(const VPRecipeBase *R)
Returns true if R produces scalar values for all VF lanes.
bool isDeadRecipe(VPRecipeBase &R)
Returns true if R is dead, i.e.
VPRecipeBase * findRecipe(VPValue *Start, PredT Pred)
Search Start's users for a recipe satisfying Pred, looking through recipes with definitions.
LLVM_ABI_FOR_TEST bool isUniformAcrossVFsAndUFs(const VPValue *V)
Checks if V is uniform across all VF lanes and UF parts.
VPValue * getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr, bool ExpandInIR=false)
Get or create a VPValue that corresponds to the expansion of Expr.
bool isUsedByLoadStoreAddress(const VPValue *V)
Returns true if V is used as part of the address of another load or store.
std::optional< std::pair< bool, unsigned > > getOpcodeOrIntrinsicID(const VPValue *V)
Get the instruction opcode or intrinsic ID for the recipe defining V.
VPValue * scalarizeVPWidenPointerInduction(VPWidenPointerInductionRecipe *PtrIV, VPlan &Plan, VPBuilder &Builder)
Scalarize a VPWidenPointerInductionRecipe by replacing it with a PtrAdd (IndStart,...
LLVM_ABI_FOR_TEST const SCEV * getSCEVExprForVPValue(const VPValue *V, PredicatedScalarEvolution &PSE, const Loop *L=nullptr)
Return the SCEV expression for V.
void pullOutPermutations(VPlan &Plan, Match_t Perm, Builder Build)
Removes the permutation pattern Perm from any elementwise operations in the plan, by constructing a n...
SmallVector< VPUser * > collectUsersRecursively(VPValue *V)
Collect all users of V, looking through recipes that define other values.
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.
SmallVector< VPBasicBlock * > vp_rpo_plain_cfg_loop_body(VPBasicBlock *Header)
Returns the VPBasicBlocks forming the loop body of a plain (pre-region) VPlan in reverse post-order s...
constexpr auto not_equal_to(T &&Arg)
Functor variant of std::not_equal_to that can be used as a UnaryPredicate in functional algorithms li...
void stable_sort(R &&Range)
auto min_element(R &&Range)
Provide wrappers to std::min_element which take ranges instead of having to pass begin/end explicitly...
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
unsigned getLoadStoreAddressSpace(const Value *I)
A helper function that returns the address space of the pointer operand of load or store instruction.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
LLVM_ABI Intrinsic::ID getVectorIntrinsicIDForCall(const CallInst *CI, const TargetLibraryInfo *TLI)
Returns intrinsic ID for call.
detail::zippy< detail::zip_first, T, U, Args... > zip_equal(T &&t, U &&u, Args &&...args)
zip iterator that assumes that all iteratees have the same length.
ReductionStyle getReductionStyle(bool InLoop, bool Ordered, unsigned ScaleFactor)
DenseMap< const Value *, const SCEV * > ValueToSCEVMapTy
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are tuples (A, B,...
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
@ Load
The value being inserted comes from a load (InsertElement only).
@ Store
The extracted value is stored (ExtractElement only).
VPBuilderBase<> VPBuilder
constexpr from_range_t from_range
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 ...
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
auto cast_or_null(const Y &Val)
Align getLoadStoreAlignment(const Value *I)
A helper function that returns the alignment of load or store instruction.
iterator_range< df_iterator< VPBlockShallowTraversalWrapper< VPBlockBase * > > > vp_depth_first_shallow(VPBlockBase *G)
Returns an iterator range to traverse the graph starting at G in depth-first order.
bool isa_and_nonnull(const Y &Val)
iterator_range< df_iterator< VPBlockDeepTraversalWrapper< VPBlockBase * > > > vp_depth_first_deep(VPBlockBase *G)
Returns an iterator range to traverse the graph starting at G in depth-first order while traversing t...
constexpr auto equal_to(T &&Arg)
Functor variant of std::equal_to that can be used as a UnaryPredicate in functional algorithms like a...
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
auto map_range(ContainerTy &&C, FuncTy F)
Return a range that applies F to the elements of C.
uint64_t PowerOf2Ceil(uint64_t A)
Returns the power of two which is greater than or equal to the given value.
auto make_isa_range(RangeT &&Range)
Return a range over Range containing only elements for which isa<T> holds, casting each of them to T.
auto dyn_cast_or_null(const Y &Val)
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
auto reverse(ContainerTy &&C)
constexpr size_t range_size(R &&Range)
Returns the size of the Range, i.e., the number of elements.
void sort(IteratorTy Start, IteratorTy End)
DenseMap< Value *, const SCEVUnknown * > SymbolicStrideMap
Maps a pointer to its symbolic (non-constant) stride.
bool hasIrregularType(Type *Ty, const DataLayout &DL)
A helper function that returns true if the given type is irregular.
UncountableExitStyle
Different methods of handling early exits.
@ ReadOnly
No side effects to worry about, so we can process any uncountable exits in the loop and branch either...
@ MaskedHandleExitInScalarLoop
All memory operations other than the load(s) required to determine whether an uncountable exit occurr...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI void report_fatal_error(Error Err, bool gen_crash_diag=true)
SmallVector< ValueTypeFromRangeType< R >, Size > to_vector(R &&Range)
Given a range of type R, iterate the entire range and return a SmallVector with elements of the vecto...
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
bool canConstantBeExtended(const APInt *C, Type *NarrowType, TTI::PartialReductionExtendKind ExtKind)
Check if a constant CI can be safely treated as having been extended from a narrower type with the gi...
T * find_singleton(R &&Range, Predicate P, bool AllowRepeats=false)
Return the single value in Range that satisfies P(<member of Range> *, AllowRepeats)->T * returning n...
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...
auto drop_end(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the last N elements excluded.
RecurKind
These are the kinds of recurrences that we support.
@ UMin
Unsigned integer min implemented in terms of select(cmp()).
@ FindIV
FindIV reduction with select(icmp(),x,y) where one of (x,y) is a loop induction variable (increasing ...
@ Or
Bitwise or logical OR of integers.
@ Mul
Product of integers.
@ FSub
Subtraction of floats.
@ SMax
Signed integer max implemented in terms of select(cmp()).
@ SMin
Signed integer min implemented in terms of select(cmp()).
@ Sub
Subtraction of integers.
@ AddChainWithSubs
A chain of adds and subs.
@ UMax
Unsigned integer max implemented in terms of select(cmp()).
LLVM_ABI Value * getRecurrenceIdentity(RecurKind K, Type *Tp, FastMathFlags FMF)
Given information about an recurrence kind, return the identity for the @llvm.vector....
LLVM_ABI BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the specified block at the specified instruction.
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
DWARFExpression::Operation Op
auto max_element(R &&Range)
Provide wrappers to std::max_element which take ranges instead of having to pass begin/end explicitly...
ArrayRef(const T &OneElt) -> ArrayRef< T >
LLVM_ABI bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
const VectorizeOptions & getVectorizeOptions(const LLVMContext &C)
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.
constexpr auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Type * getLoadStoreType(const Value *I)
A helper function that returns the type of a load or store instruction.
bool all_equal(std::initializer_list< T > Values)
Returns true if all Values in the initializer lists are equal or the list.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
Type * toVectorTy(Type *Scalar, ElementCount EC)
A helper function for converting Scalar types to vector types.
LLVM_ABI bool isDereferenceableAndAlignedInLoop(LoadInst *LI, Loop *L, ScalarEvolution &SE, DominatorTree &DT, AssumptionCache *AC=nullptr, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Return true if we can prove that the given load (which is assumed to be within the specified loop) wo...
constexpr detail::IsaCheckPredicate< Types... > IsaPred
Function object wrapper for the llvm::isa type check.
LLVM_ABI_FOR_TEST bool verifyVPlanIsValid(const VPlan &Plan)
Verify invariants for general VPlans.
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
VPBasicBlock * EarlyExitingVPBB
VPIRBasicBlock * EarlyExitVPBB
This struct is a compact representation of a valid (non-zero power of two) alignment.
An information struct used to provide DenseMap with the various necessary components for a given valu...
This reduction is unordered with the partial result scaled down by some factor.
Holds the VFShape for a specific scalar to vector function mapping.
Encapsulates information needed to describe a parameter.
A range of powers-of-2 vectorization factors with fixed start and adjustable end.
Struct to hold various analysis needed for cost computations.
const VFSelectionContext & Config
static bool isFreeScalarIntrinsic(Intrinsic::ID ID)
Returns true if ID is a pseudo intrinsic that is dropped via scalarization rather than widened.
bool isMaskRequired(Instruction *I) const
Forwards to LoopVectorizationCostModel::isMaskRequired.
PredicatedScalarEvolution & PSE
bool willBeScalarized(Instruction *I, ElementCount VF) const
Returns true if I is known to be scalarized at VF.
TargetTransformInfo::TargetCostKind CostKind
const TargetLibraryInfo & TLI
const TargetTransformInfo & TTI
const VectorizeOptions & Opts
A recipe for handling first-order recurrence phis.
WrapFlagsTy withoutNoSignedWrap()
A VPValue representing a live-in from the input IR or a constant.
Type * getType() const
Returns the type of the underlying IR value.
A recipe for widening load operations, using the address to load from and an optional mask.
A recipe for widening store operations, using the stored value, the address to store to and an option...