58 if (!VPBB->getParent())
61 auto EndIter = Term ? Term->getIterator() : VPBB->end();
66 VPValue *VPV = Ingredient.getVPSingleValue();
87 *Load, Ingredient.getOperand(0),
nullptr ,
88 false , *VPI, Ingredient.getDebugLoc());
91 *Store, Ingredient.getOperand(1), Ingredient.getOperand(0),
92 nullptr ,
false , *VPI,
93 Ingredient.getDebugLoc());
96 Ingredient.operands(), *VPI,
97 Ingredient.getDebugLoc(),
GEP);
109 if (VectorID == Intrinsic::experimental_noalias_scope_decl)
114 if (VectorID == Intrinsic::assume ||
115 VectorID == Intrinsic::lifetime_end ||
116 VectorID == Intrinsic::lifetime_start ||
117 VectorID == Intrinsic::sideeffect ||
118 VectorID == Intrinsic::pseudoprobe) {
123 const bool IsSingleScalar = VectorID != Intrinsic::assume &&
124 VectorID != Intrinsic::pseudoprobe;
128 Ingredient.getDebugLoc());
131 *CI, VectorID,
drop_end(Ingredient.operands()), CI->getType(),
132 VPIRFlags(*CI), *VPI, CI->getDebugLoc());
136 CI->getOpcode(), Ingredient.getOperand(0), CI->getType(), CI,
140 *VPI, Ingredient.getDebugLoc());
144 "inductions must be created earlier");
153 "Only recpies with zero or one defined values expected");
154 Ingredient.eraseFromParent();
165 const Loop *L =
nullptr;
170 if (
A->getOpcode() != Instruction::Store ||
171 B->getOpcode() != Instruction::Store)
184 const APInt *Distance;
190 Type *TyA =
A->getOperand(0)->getScalarType();
192 Type *TyB =
B->getOperand(0)->getScalarType();
198 uint64_t MaxStoreSize = std::max(SizeA, SizeB);
200 auto VFs =
B->getParent()->getPlan()->vectorFactors();
204 return Distance->
abs().
uge(
212 : ExcludeRecipes(ExcludeRecipes.begin(), ExcludeRecipes.end()),
213 GroupLeader(GroupLeader), PSE(&PSE), L(&L) {}
222 return ExcludeRecipes.contains(Store) ||
223 (Store && isNoAliasViaDistance(Store, &GroupLeader));
236 std::optional<SinkStoreInfo> SinkInfo = {}) {
237 bool CheckReads = SinkInfo.has_value();
241 if (SinkInfo && SinkInfo->shouldSkip(R))
245 if (!
R.mayWriteToMemory() && !(CheckReads &&
R.mayReadFromMemory()))
270template <
unsigned Opcode>
275 static_assert(Opcode == Instruction::Load || Opcode == Instruction::Store,
276 "Only Load and Store opcodes supported");
277 constexpr bool IsLoad = (Opcode == Instruction::Load);
280 RecipesByAddressAndType;
285 if (!RepR || RepR->getOpcode() != Opcode || !FilterFn(RepR))
289 VPValue *Addr = RepR->getOperand(IsLoad ? 0 : 1);
293 RecipesByAddressAndType[{AddrSCEV, LoadStoreTy}].push_back(RepR);
298 for (
auto &Group :
Groups) {
313 auto InsertIfValidSinkCandidate = [ScalarVFOnly, &WorkList](
325 if (Candidate->getParent() == SinkTo ||
330 if (!ScalarVFOnly && RepR->isSingleScalar())
333 WorkList.
insert({SinkTo, Candidate});
345 for (
auto &Recipe : *VPBB)
347 InsertIfValidSinkCandidate(VPBB,
Op);
351 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
354 std::tie(SinkTo, SinkCandidate) = WorkList[
I];
359 auto UsersOutsideSinkTo =
361 return cast<VPRecipeBase>(U)->getParent() != SinkTo;
363 if (
any_of(UsersOutsideSinkTo, [SinkCandidate](
VPUser *U) {
364 return !U->usesFirstLaneOnly(SinkCandidate);
367 bool NeedsDuplicating = !UsersOutsideSinkTo.empty();
369 if (NeedsDuplicating) {
373 if (
auto *SinkCandidateRepR =
378 SinkCandidateRepR->getOpcode(), SinkCandidate->
operands(),
379 nullptr, *SinkCandidateRepR, *SinkCandidateRepR,
383 Clone = SinkCandidate->
clone();
393 InsertIfValidSinkCandidate(SinkTo,
Op);
403 if (!EntryBB || EntryBB->size() != 1 ||
413 if (EntryBB->getNumSuccessors() != 2)
418 if (!Succ0 || !Succ1)
421 if (Succ0->getNumSuccessors() + Succ1->getNumSuccessors() != 1)
423 if (Succ0->getSingleSuccessor() == Succ1)
425 if (Succ1->getSingleSuccessor() == Succ0)
442 if (!Region1->isReplicator())
444 auto *MiddleBasicBlock =
446 if (!MiddleBasicBlock || !MiddleBasicBlock->empty())
451 if (!Region2 || !Region2->isReplicator())
456 if (!Mask1 || Mask1 != Mask2)
459 assert(Mask1 && Mask2 &&
"both region must have conditions");
465 if (TransformedRegions.
contains(Region1))
472 if (!Then1 || !Then2)
492 VPValue *Phi1ToMoveV = Phi1ToMove.getVPSingleValue();
498 if (Phi1ToMove.getVPSingleValue()->user_empty()) {
499 Phi1ToMove.eraseFromParent();
502 Phi1ToMove.moveBefore(*Merge2, Merge2->begin());
516 TransformedRegions.
insert(Region1);
519 return !TransformedRegions.
empty();
527 std::string RegionName = (
Twine(
"pred.") + Instr->getOpcodeName()).str();
528 assert(Instr->getParent() &&
"Predicated instruction not in any basic block");
529 auto *BlockInMask = PredRecipe->
getMask();
550 Region->setParent(ParentRegion);
556 RecipeWithoutMask->getDebugLoc());
557 Exiting->appendRecipe(PHIRecipe);
570 if (RepR->isPredicated())
589 if (ParentRegion && ParentRegion->
getExiting() == CurrentBlock)
601 if (!VPBB->getParent())
605 if (!PredVPBB || PredVPBB->getNumSuccessors() != 1 ||
614 R.moveBefore(*PredVPBB, PredVPBB->
end());
616 auto *ParentRegion = VPBB->getParent();
617 if (ParentRegion && ParentRegion->getExiting() == VPBB)
618 ParentRegion->setExiting(PredVPBB);
622 return !WorkList.
empty();
629 bool ShouldSimplify =
true;
630 while (ShouldSimplify) {
646 if (!
IV ||
IV->getTruncInst())
661 for (
auto *U : FindMyCast->
users()) {
663 if (UserCast && UserCast->getUnderlyingValue() == IRCast) {
664 FoundUserCast = UserCast;
671 FindMyCast = FoundUserCast;
673 if (FindMyCast !=
IV)
688 Builder.createDerivedIV(Kind, FPBinOp, StartV, CanonicalIV, Step);
697 BaseIV = Builder.createScalarCast(Instruction::Trunc, BaseIV, TruncTy,
DL);
703 if (ResultTy != StepTy) {
710 Builder.setInsertPoint(VecPreheader);
711 Step = Builder.createScalarCast(Instruction::Trunc, Step, ResultTy,
DL);
713 return Builder.createScalarIVSteps(InductionOpcode, FPBinOp, BaseIV, Step,
739 WideCanIV->getDebugLoc(), Builder));
740 WideCanIV->eraseFromParent();
757 WideCanIV->replaceAllUsesWith(WidenIV);
758 WideCanIV->eraseFromParent();
767 if (PHICost > BroadcastCost)
776 unsigned RegClass =
TTI.getRegisterClassForType(
true, VecTy);
788 WideCanIV->getNoWrapFlags(), WideCanIV->getDebugLoc());
789 NewWideIV->insertBefore(&*Header->getFirstNonPhi());
790 WideCanIV->replaceAllUsesWith(NewWideIV);
791 WideCanIV->eraseFromParent();
799 bool IsConditionalAssume = RepR && RepR->isPredicated() &&
801 if (IsConditionalAssume)
804 if (R.mayHaveSideEffects())
808 return all_of(R.definedValues(), [](
VPValue *V) { return V->user_empty(); });
828 VPUser *PhiUser = PhiR->getSingleUser();
834 PhiR->replaceAllUsesWith(Start);
835 PhiR->eraseFromParent();
843 for (
unsigned I = 0;
I !=
Users.size(); ++
I) {
846 Users.insert_range(V->users());
848 return Users.takeVector();
862 nullptr, StartV, StepV, PtrIV->
getDebugLoc(), Builder);
899 Def->user_empty() || !Def->getUnderlyingValue() ||
900 (RepR && (RepR->isSingleScalar() || RepR->isPredicated())))
913 Def->getUnderlyingInstr()->getOpcode(), Def->operands(),
915 Def->getUnderlyingInstr());
916 Clone->insertAfter(Def);
917 Def->replaceAllUsesWith(Clone);
928 PtrIV->replaceAllUsesWith(PtrAdd);
935 if (HasOnlyVectorVFs &&
none_of(WideIV->users(), [WideIV](
VPUser *U) {
936 return U->usesScalars(WideIV);
942 Plan,
ID.getKind(),
ID.getInductionOpcode(),
944 WideIV->getTruncInst(), WideIV->getStartValue(), WideIV->getStepValue(),
945 WideIV->getDebugLoc(), Builder);
948 if (!HasOnlyVectorVFs) {
950 "plans containing a scalar VF cannot also include scalable VFs");
951 WideIV->replaceAllUsesWith(Steps);
954 WideIV->replaceUsesWithIf(Steps,
955 [WideIV, HasScalableVF](
VPUser &U,
unsigned) {
957 return U.usesFirstLaneOnly(WideIV);
958 return U.usesScalars(WideIV);
974 return (IntOrFpIV && IntOrFpIV->getTruncInst()) ? nullptr : WideIV;
979 if (!Def || Def->getNumOperands() != 2)
987 auto IsWideIVInc = [&]() {
988 auto &
ID = WideIV->getInductionDescriptor();
991 VPValue *IVStep = WideIV->getStepValue();
992 switch (
ID.getInductionOpcode()) {
993 case Instruction::Add:
995 case Instruction::FAdd:
997 case Instruction::FSub:
1000 case Instruction::Sub: {
1020 return IsWideIVInc() ? WideIV :
nullptr;
1037 if (WideIntOrFp && WideIntOrFp->getTruncInst())
1048 VPValue *FirstActiveLane =
B.createFirstActiveLane(Mask,
DL);
1049 FirstActiveLane =
B.createScalarZExtOrTrunc(
1050 FirstActiveLane, CanonicalIVType, FirstActiveLane->
getScalarType(),
DL);
1051 VPValue *EndValue =
B.createAdd(CanonicalIV, FirstActiveLane,
DL);
1056 if (Incoming != WideIV) {
1058 EndValue =
B.createAdd(EndValue, One,
DL);
1063 VPIRValue *Start = WideIV->getStartValue();
1064 VPValue *Step = WideIV->getStepValue();
1065 EndValue =
B.createDerivedIV(
1067 Start, EndValue, Step);
1081 if (WideIntOrFp && WideIntOrFp->getTruncInst())
1091 Start, VectorTC, Step);
1127 assert(EndValue &&
"Must have computed the end value up front");
1132 if (Incoming != WideIV)
1144 auto *Zero = Plan.
getZero(StepTy);
1145 return B.createPtrAdd(EndValue,
B.createSub(Zero, Step),
1150 return B.createNaryOp(
1151 ID.getInductionBinOp()->getOpcode() == Instruction::FAdd
1153 : Instruction::FAdd,
1154 {EndValue, Step}, {ID.getInductionBinOp()->getFastMathFlags()});
1165 VPBuilder VectorPHBuilder(VectorPH, VectorPH->begin());
1175 EndValues[WideIV] = EndValue;
1185 R.getVPSingleValue()->replaceAllUsesWith(EndValue);
1186 R.eraseFromParent();
1195 for (
auto [Idx, PredVPBB] :
enumerate(ExitVPBB->getPredecessors())) {
1197 if (PredVPBB == MiddleVPBB)
1199 Plan, ExitIRI->getOperand(Idx), EndValues, PSE);
1202 Plan, ExitIRI->getOperand(Idx), PSE);
1204 ExitIRI->setOperand(Idx, Escape);
1221 const auto &[V, Inserted] = SCEV2VPV.
try_emplace(ExpR->getSCEV(), ExpR);
1225 ExpR->replaceAllUsesWith(V->second);
1229 ExpR->eraseFromParent();
1238 while (!WorkList.
empty()) {
1240 if (!Seen.
insert(Cur).second)
1248 R->eraseFromParent();
1255static std::optional<std::pair<bool, unsigned>>
1258 return std::make_pair(
true, IID);
1260 std::optional<std::pair<bool, unsigned>>>(R)
1263 [](
auto *
I) {
return std::make_pair(
false,
I->getOpcode()); })
1265 return std::make_pair(
false, Instruction::PHI);
1267 .Case<VPVectorPointerRecipe, VPPredInstPHIRecipe, VPScalarIVStepsRecipe>(
1273 I->getVPRecipeID());
1275 .
Default([](
auto *) {
return std::nullopt; });
1300 VPlan &Plan = *R.getParent()->getPlan();
1301 auto FoldToIRValue = [&]() ->
Value * {
1303 if (OpcodeOrIID->first) {
1309 return Folder.FoldIntrinsic(OpcodeOrIID->second,
Ops, R.getScalarType(),
1310 RFlags ? RFlags->getFastMathFlagsOrNone()
1313 unsigned Opcode = OpcodeOrIID->second;
1319 R.getVPSingleValue()->getScalarType());
1322 return Folder.FoldBinOp(Instruction::BinaryOps::Xor,
Ops[0],
1324 case Instruction::Select:
1325 return Folder.FoldSelect(
Ops[0],
Ops[1],
Ops[2]);
1326 case Instruction::ICmp:
1327 case Instruction::FCmp:
1330 case Instruction::GetElementPtr: {
1333 return Folder.FoldGEP(
GEP->getSourceElementType(),
Ops[0],
1343 case Instruction::ExtractElement:
1350 if (
Value *V = FoldToIRValue())
1357 bool CanCreateNewRecipe) {
1358 VPlan *Plan = Def->getParent()->getPlan();
1368 Def->replaceAllUsesWith(
X);
1369 Def->eraseFromParent();
1381 Def->replaceAllUsesWith(
X);
1393 Def->replaceAllUsesWith(Plan->
getZero(Def->getScalarType()));
1399 Def->replaceAllUsesWith(
X);
1405 Def->replaceAllUsesWith(Plan->
getFalse());
1411 Def->replaceAllUsesWith(
X);
1416 if (CanCreateNewRecipe &&
1421 (!Def->getOperand(0)->hasMoreThanOneUniqueUser() ||
1422 !Def->getOperand(1)->hasMoreThanOneUniqueUser())) {
1423 Def->replaceAllUsesWith(
1424 Builder.createLogicalAnd(
X, Builder.createOr(
Y, Z)));
1431 Def->replaceAllUsesWith(Def->getOperand(1));
1438 Def->replaceAllUsesWith(Builder.createLogicalAnd(
X,
Y));
1444 Def->replaceAllUsesWith(Plan->
getFalse());
1449 Def->replaceAllUsesWith(
X);
1455 if (CanCreateNewRecipe &&
1457 Def->replaceAllUsesWith(Builder.createNot(
C));
1463 Def->setOperand(0,
C);
1464 Def->setOperand(1,
Y);
1465 Def->setOperand(2,
X);
1470 if (CanCreateNewRecipe &&
1474 Y->getScalarType()->isIntegerTy(1)) {
1475 Def->replaceAllUsesWith(
1476 Builder.createOr(
Y, Builder.createLogicalAnd(
X, Z)));
1485 VPlan *Plan = Def->getParent()->getPlan();
1491 return Def->replaceAllUsesWith(V);
1497 PredPHI->replaceAllUsesWith(
Op);
1505 RepR && RepR->isPredicated() && RepR->getOpcode() == Instruction::Store &&
1509 RepR->getUnderlyingInstr(), RepR->operandsWithoutMask(),
1510 RepR->isSingleScalar(),
nullptr, *RepR, *RepR,
1511 RepR->getDebugLoc());
1512 Unmasked->insertBefore(RepR);
1513 RepR->replaceAllUsesWith(Unmasked);
1514 RepR->eraseFromParent();
1528 bool CanCreateNewRecipe =
1533 Type *TruncTy = Def->getScalarType();
1534 Type *ATy =
A->getScalarType();
1535 if (TruncTy == ATy) {
1536 Def->replaceAllUsesWith(
A);
1545 : Instruction::ZExt;
1548 if (
auto *UnderlyingExt = Def->getOperand(0)->getUnderlyingValue()) {
1550 Ext->setUnderlyingValue(UnderlyingExt);
1552 Def->replaceAllUsesWith(Ext);
1554 auto *Trunc = Builder.createWidenCast(Instruction::Trunc,
A, TruncTy);
1555 Def->replaceAllUsesWith(Trunc);
1565 return Def->replaceAllUsesWith(
A);
1568 return Def->replaceAllUsesWith(
A);
1571 return Def->replaceAllUsesWith(Plan->
getZero(Def->getScalarType()));
1577 return Def->replaceAllUsesWith(Builder.createSub(
1578 Plan->
getZero(
A->getScalarType()),
A, Def->getDebugLoc(),
"", NW));
1581 if (CanCreateNewRecipe &&
1589 ->hasNoSignedWrap()};
1590 return Def->replaceAllUsesWith(
1591 Builder.createSub(
X,
Y, Def->getDebugLoc(),
"", NW));
1600 MulR->hasNoSignedWrap() &&
1602 return Def->replaceAllUsesWith(Builder.createNaryOp(
1604 {A, Plan->getConstantInt(APC->getBitWidth(), ShiftAmt)}, NW,
1605 Def->getDebugLoc()));
1610 return Def->replaceAllUsesWith(Builder.createNaryOp(
1612 {A, Plan->getConstantInt(APC->getBitWidth(), APC->exactLogBase2())},
1617 return Def->replaceAllUsesWith(
A);
1632 R->setOperand(1,
Y);
1633 R->setOperand(2,
X);
1637 R->replaceAllUsesWith(Cmp);
1642 if (!Cmp->getDebugLoc() && Def->getDebugLoc())
1643 Cmp->setDebugLoc(Def->getDebugLoc());
1655 if (
Op->getNumUsers() > 1 ||
1659 }
else if (!UnpairedCmp) {
1660 UnpairedCmp =
Op->getDefiningRecipe();
1664 UnpairedCmp =
nullptr;
1671 if (NewOps.
size() < Def->getNumOperands()) {
1673 return Def->replaceAllUsesWith(NewAnyOf);
1680 if (CanCreateNewRecipe &&
1686 return Def->replaceAllUsesWith(NewCmp);
1692 Def->getOperand(1)->getScalarType() == Def->getScalarType())
1693 return Def->replaceAllUsesWith(Def->getOperand(1));
1697 Type *WideStepTy = Def->getScalarType();
1698 if (
X->getScalarType() != WideStepTy)
1699 X = Builder.createWidenCast(Instruction::Trunc,
X, WideStepTy);
1700 Def->replaceAllUsesWith(
X);
1709 Def->getScalarType()->isIntegerTy(1)) {
1710 Def->setOperand(1, Def->getOperand(0));
1711 Def->setOperand(0,
Y);
1718 return Def->replaceAllUsesWith(Def->getOperand(0));
1724 Def->replaceAllUsesWith(
1725 BuildVector->getOperand(BuildVector->getNumOperands() - 1));
1730 return Def->replaceAllUsesWith(
X);
1733 return Def->replaceAllUsesWith(
A);
1736 return Def->replaceAllUsesWith(
A);
1742 Def->replaceAllUsesWith(
1743 BuildVector->getOperand(BuildVector->getNumOperands() - 2));
1750 Def->replaceAllUsesWith(BuildVector->getOperand(Idx));
1755 Def->replaceAllUsesWith(
1763 Def->replaceUsesWithIf(Def->getOperand(0), [Def](
VPUser &U,
unsigned) {
1764 return U.usesFirstLaneOnly(Def);
1773 "broadcast operand must be single-scalar");
1774 Def->setOperand(0,
C);
1779 return Def->replaceUsesWithIf(
1780 X, [Def](
const VPUser &U,
unsigned) {
return U.usesScalars(Def); });
1783 if (Def->getNumOperands() == 1) {
1784 Def->replaceAllUsesWith(Def->getOperand(0));
1789 Phi->replaceAllUsesWith(Phi->getOperand(0));
1795 if (Def->getNumOperands() == 1 &&
1797 return Def->replaceAllUsesWith(IRV);
1810 return Def->replaceAllUsesWith(
A);
1817 return Def->replaceAllUsesWith(WidenIV->getRegion()->getCanonicalIV());
1820 Def->replaceAllUsesWith(Builder.createNaryOp(
1821 Instruction::ExtractElement, {A, LaneToExtract}, Def->getDebugLoc()));
1835 auto *IVInc = Def->getOperand(0);
1836 if (IVInc->getNumUsers() == 2) {
1841 if (Phi->getNumUsers() == 1 || (Phi->getNumUsers() == 2 && Inc)) {
1842 Def->replaceAllUsesWith(IVInc);
1844 Inc->replaceAllUsesWith(Phi);
1845 Phi->setOperand(0,
Y);
1861 Steps->replaceAllUsesWith(Steps->getOperand(0));
1869 Def->replaceUsesWithIf(StartV, [](
const VPUser &U,
unsigned Idx) {
1871 return PhiR && PhiR->isInLoop();
1877 return Def->replaceAllUsesWith(
A);
1893template <
typename Match_t,
typename Builder>
1914 for (
unsigned I = 0;
I < Def->getNumOperands();
I++)
1916 Def->setOperand(
I,
X);
1920 Def->replaceUsesWithIf(
1921 Res, [&Res](
VPUser &U,
unsigned _) {
return &U != Res; });
1939 R.getVPSingleValue()->replaceAllUsesWith(
X);
1955 while (!Worklist.
empty()) {
1964 R->replaceAllUsesWith(
1965 Builder.createLogicalAnd(HeaderMask, Builder.createLogicalAnd(
X,
Y)));
1969static std::optional<Instruction::BinaryOps>
1972 case Intrinsic::masked_udiv:
1973 return Instruction::UDiv;
1974 case Intrinsic::masked_sdiv:
1975 return Instruction::SDiv;
1976 case Intrinsic::masked_urem:
1977 return Instruction::URem;
1978 case Intrinsic::masked_srem:
1979 return Instruction::SRem;
1996 if (RepR && (RepR->isSingleScalar() || RepR->isPredicated()))
2000 if (RepR && RepR->getOpcode() == Instruction::Store &&
2003 RepOrWidenR->getUnderlyingInstr(), RepOrWidenR->operands(),
2004 true ,
nullptr , *RepR ,
2005 *RepR , RepR->getDebugLoc());
2006 Clone->insertBefore(RepOrWidenR);
2008 VPValue *ExtractOp = Clone->getOperand(0);
2014 Clone->setOperand(0, ExtractOp);
2015 RepR->eraseFromParent();
2027 VPValue *SafeDivisor = Builder.createSelect(
2028 IntrR->getOperand(2), IntrR->getOperand(1),
2030 VPValue *Clone = Builder.createNaryOp(
2031 *
Opc, {IntrR->getOperand(0), SafeDivisor},
2034 IntrR->eraseFromParent();
2043 auto IntroducesBCastOf = [](
const VPValue *
Op) {
2052 return !U->usesScalars(
Op);
2056 if (
any_of(RepOrWidenR->users(), IntroducesBCastOf(RepOrWidenR)) &&
2059 make_filter_range(Op->users(), not_equal_to(RepOrWidenR)),
2060 IntroducesBCastOf(Op)))
2064 bool LiveInNeedsBroadcast =
2065 isa<VPIRValue>(Op) && !isa<VPConstant>(Op);
2066 auto *OpR = dyn_cast<VPReplicateRecipe>(Op);
2067 return LiveInNeedsBroadcast || (OpR && OpR->isSingleScalar());
2074 RepOrWidenR->getUnderlyingInstr());
2075 Clone->insertBefore(RepOrWidenR);
2076 RepOrWidenR->replaceAllUsesWith(Clone);
2078 RepOrWidenR->eraseFromParent();
2114 if (Blend->isNormalized() || !
match(Blend->getMask(0),
m_False()))
2115 UniqueValues.
insert(Blend->getIncomingValue(0));
2116 for (
unsigned I = 1;
I != Blend->getNumIncomingValues(); ++
I)
2118 UniqueValues.
insert(Blend->getIncomingValue(
I));
2120 if (UniqueValues.
size() == 1) {
2121 Blend->replaceAllUsesWith(*UniqueValues.
begin());
2122 Blend->eraseFromParent();
2126 if (Blend->isNormalized())
2132 unsigned StartIndex = 0;
2133 for (
unsigned I = 0;
I != Blend->getNumIncomingValues(); ++
I) {
2145 OperandsWithMask.
push_back(Blend->getIncomingValue(StartIndex));
2147 for (
unsigned I = 0;
I != Blend->getNumIncomingValues(); ++
I) {
2148 if (
I == StartIndex)
2150 OperandsWithMask.
push_back(Blend->getIncomingValue(
I));
2151 OperandsWithMask.
push_back(Blend->getMask(
I));
2156 OperandsWithMask, *Blend, Blend->getDebugLoc());
2157 NewBlend->insertBefore(&R);
2159 VPValue *DeadMask = Blend->getMask(StartIndex);
2161 Blend->eraseFromParent();
2166 if (NewBlend->getNumOperands() == 3 &&
2168 VPValue *Inc0 = NewBlend->getOperand(0);
2169 VPValue *Inc1 = NewBlend->getOperand(1);
2170 VPValue *OldMask = NewBlend->getOperand(2);
2171 NewBlend->setOperand(0, Inc1);
2172 NewBlend->setOperand(1, Inc0);
2173 NewBlend->setOperand(2, NewMask);
2200 APInt MaxVal = AlignedTC - 1;
2203 unsigned NewBitWidth =
2209 bool MadeChange =
false;
2234 "canonical IV is not expected to have a truncation");
2239 NewWideIV->insertBefore(WideIV);
2246 Cmp->replaceAllUsesWith(
2247 VPBuilder(Cmp).createICmp(Cmp->getPredicate(), NewWideIV, NewBTC));
2261 return any_of(
Cond->getDefiningRecipe()->operands(), [&Plan, BestVF, BestUF,
2263 return isConditionTrueViaVFAndUF(C, Plan, BestVF, BestUF, PSE);
2277 const SCEV *VectorTripCount =
2282 "Trip count SCEV must be computable");
2303 auto *Term = &ExitingVPBB->
back();
2316 for (
unsigned Part = 0; Part < UF; ++Part) {
2322 Extracts[Part] = Ext;
2334 match(Phi->getBackedgeValue(),
2336 assert(Index &&
"Expected index from ActiveLaneMask instruction");
2353 "Expected one VPActiveLaneMaskPHIRecipe for each unroll part");
2360 "Expected incoming values of Phi to be ActiveLaneMasks");
2365 EntryALM->setOperand(2, ALMMultiplier);
2366 LoopALM->setOperand(2, ALMMultiplier);
2370 ExtractFromALM(EntryALM, EntryExtracts);
2375 ExtractFromALM(LoopALM, LoopExtracts);
2377 Not->setOperand(0, LoopExtracts[0]);
2380 for (
unsigned Part = 0; Part < UF; ++Part) {
2381 Phis[Part]->setStartValue(EntryExtracts[Part]);
2382 Phis[Part]->setBackedgeValue(LoopExtracts[Part]);
2395 auto *Term = &ExitingVPBB->
back();
2407 const SCEV *VectorTripCount =
2413 "Trip count SCEV must be computable");
2432 Term->setOperand(1, Plan.
getTrue());
2437 {}, Term->getDebugLoc());
2439 Term->eraseFromParent();
2472 R.getVPSingleValue()->replaceAllUsesWith(Trunc);
2482 assert(Plan.
hasVF(BestVF) &&
"BestVF is not available in Plan");
2483 assert(Plan.
hasUF(BestUF) &&
"BestUF is not available in Plan");
2501 RecurKind RK = PhiR->getRecurrenceKind();
2508 RecWithFlags->dropPoisonGeneratingFlags();
2514struct VPCSEDenseMapInfo :
public DenseMapInfo<VPSingleDefRecipe *> {
2523 return GEP->getSourceElementType();
2526 .Case<VPVectorPointerRecipe, VPWidenGEPRecipe>(
2527 [](
auto *
I) {
return I->getSourceElementType(); })
2528 .
Default([](
auto *) {
return nullptr; });
2532 static bool canHandle(
const VPSingleDefRecipe *Def) {
2541 if (!
C || (!
C->first && (
C->second == Instruction::InsertValue ||
2542 C->second == Instruction::ExtractValue)))
2546 return !
Def->mayReadOrWriteMemory();
2550 static unsigned getHashValue(
const VPSingleDefRecipe *Def) {
2553 getGEPSourceElementType(Def),
Def->getScalarType(),
2556 if (RFlags->hasPredicate())
2559 return hash_combine(Result, SIVSteps->getInductionOpcode());
2564 static bool isEqual(
const VPSingleDefRecipe *L,
const VPSingleDefRecipe *R) {
2565 if (
L->getVPRecipeID() !=
R->getVPRecipeID() ||
2567 getGEPSourceElementType(L) != getGEPSourceElementType(R) ||
2569 !
equal(
L->operands(),
R->operands()))
2572 "must have valid opcode info for both recipes");
2574 if (LFlags->hasPredicate() &&
2575 LFlags->getPredicate() !=
2579 if (LSIV->getInductionOpcode() !=
2589 const VPRegionBlock *RegionL =
L->getRegion();
2590 const VPRegionBlock *RegionR =
R->getRegion();
2593 L->getParent() !=
R->getParent())
2595 return L->getScalarType() ==
R->getScalarType();
2611 if (!Def || !VPCSEDenseMapInfo::canHandle(Def))
2615 if (!VPDT.
dominates(V->getParent(), VPBB))
2620 Def->replaceAllUsesWith(V);
2633 bool Sinking =
false) {
2662 "Expected vector prehader's successor to be the vector loop region");
2670 return !Op->isDefinedOutsideLoopRegions();
2673 R.moveBefore(*Preheader, Preheader->
end());
2693 assert(!RepR->isPredicated() &&
2694 "Expected prior transformation of predicated replicates to "
2695 "replicate regions");
2700 if (!RepR->isSingleScalar())
2704 if (RepR->getOpcode() == Instruction::Store &&
2705 !RepR->getOperand(1)->isDefinedOutsideLoopRegions())
2710 assert((!R.mayWriteToMemory() ||
2711 (RepR && RepR->getOpcode() == Instruction::Store &&
2712 RepR->getOperand(1)->isDefinedOutsideLoopRegions())) &&
2713 "The only recipes that may write to memory are expected to be "
2714 "stores with invariant pointer-operand");
2724 if (
any_of(Def->users(), [&SinkBB, &LoopRegion](
VPUser *U) {
2725 auto *UserR = cast<VPRecipeBase>(U);
2726 VPBasicBlock *Parent = UserR->getParent();
2728 if (SinkBB && SinkBB != Parent)
2733 return UserR->isPhi() || Parent->getEnclosingLoopRegion() ||
2734 Parent->getSinglePredecessor() != LoopRegion;
2744 "Defining block must dominate sink block");
2769 VPValue *ResultVPV = R.getVPSingleValue();
2771 unsigned NewResSizeInBits = MinBWs.
lookup(UI);
2772 if (!NewResSizeInBits)
2785 (void)OldResSizeInBits;
2793 VPW->dropPoisonGeneratingFlags();
2795 assert((OldResSizeInBits != NewResSizeInBits ||
2797 "Only ICmps should not need extending the result.");
2803 if (OldResSizeInBits != NewResSizeInBits) {
2805 Instruction::ZExt, ResultVPV, OldResTy);
2807 Ext->setOperand(0, ResultVPV);
2817 unsigned OpSizeInBits =
Op->getScalarType()->getScalarSizeInBits();
2818 if (OpSizeInBits == NewResSizeInBits)
2820 assert(OpSizeInBits > NewResSizeInBits &&
"nothing to truncate");
2821 auto [ProcessedIter, Inserted] = ProcessedTruncs.
try_emplace(
Op);
2827 Builder.setInsertPoint(&R);
2828 ProcessedIter->second =
2829 Builder.createWidenCast(Instruction::Trunc,
Op, NewResTy);
2831 Op = ProcessedIter->second;
2835 NWR->insertBefore(&R);
2839 VPValue *Replacement = NWR->getVPSingleValue();
2840 if (OldResSizeInBits != NewResSizeInBits)
2846 R.eraseFromParent();
2852 std::optional<VPDominatorTree> VPDT;
2860 bool SimplifiedPhi =
false;
2870 assert(VPBB->getNumSuccessors() == 2 &&
2871 "Two successors expected for BranchOnCond");
2872 unsigned RemovedIdx;
2883 "There must be a single edge between VPBB and its successor");
2886 auto Phis = RemovedSucc->
phis();
2889 SimplifiedPhi |= !std::empty(Phis);
2893 VPBB->back().eraseFromParent();
2905 if (Reachable.contains(
B))
2916 for (
VPValue *Def : R.definedValues())
2917 Def->replaceAllUsesWith(&Tmp);
2918 R.eraseFromParent();
2922 return SimplifiedPhi;
2977 DebugLoc DL = CanonicalIVIncrement->getDebugLoc();
2988 auto *EntryIncrement =
2990 {StartV, VF}, {},
DL,
"index.part.next");
2996 {EntryIncrement, TC, ALMMultiplier},
DL,
2997 "active.lane.mask.entry");
3004 LaneMaskPhi->insertBefore(*HeaderVPBB, HeaderVPBB->begin());
3009 Builder.setInsertPoint(OriginalTerminator);
3010 auto *InLoopIncrement = Builder.createOverflowingOp(
3012 {CanonicalIVIncrement, &Plan.
getVF()}, {},
DL);
3014 {InLoopIncrement, TC, ALMMultiplier},
DL,
3015 "active.lane.mask.next");
3016 LaneMaskPhi->addBackedgeValue(ALM);
3020 auto *NotMask = Builder.createNot(ALM,
DL);
3027 VPlan &Plan,
bool UseActiveLaneMask,
bool UseActiveLaneMaskForControlFlow) {
3033 if (UseActiveLaneMaskForControlFlow) {
3039 VPBuilder Builder(Header, Header->getFirstNonPhi());
3044 if (UseActiveLaneMask) {
3047 Mask = Builder.createNaryOp(
3049 {WideCanonicalIV, Plan.
getTripCount(), ALMMultiplier},
nullptr,
3050 "active.lane.mask");
3075template <
typename Op0_t,
typename Op1_t>
3083 case Intrinsic::masked_udiv:
3084 return Intrinsic::vp_udiv;
3085 case Intrinsic::masked_sdiv:
3086 return Intrinsic::vp_sdiv;
3087 case Intrinsic::masked_urem:
3088 return Intrinsic::vp_urem;
3089 case Intrinsic::masked_srem:
3090 return Intrinsic::vp_srem;
3092 return std::nullopt;
3107 VPValue *Addr, *Mask, *EndPtr;
3110 auto AdjustEndPtr = [&CurRecipe, &EVL](
VPValue *EndPtr) {
3112 EVLEndPtr->insertBefore(&CurRecipe);
3117 EVLEndPtr->setOperand(1, EVLAsVF);
3121 auto GetVPReverse = [&CurRecipe, &EVL, Plan,
3126 Intrinsic::experimental_vp_reverse, {V, Plan->
getTrue(), &EVL},
3127 V->getScalarType(), {}, {},
DL);
3128 Reverse->insertBefore(&CurRecipe);
3132 if (
match(&CurRecipe,
3137 if (
match(&CurRecipe,
3141 Mask = GetVPReverse(Mask);
3142 Addr = AdjustEndPtr(EndPtr);
3145 LoadR->insertBefore(&CurRecipe);
3149 LoadR->getScalarType(), {}, {},
DL);
3160 NewLoad->setOperand(2, Mask);
3161 NewLoad->setOperand(3, &EVL);
3169 StoredVal, EVL, Mask);
3171 if (
match(&CurRecipe,
3175 Mask = GetVPReverse(Mask);
3176 Addr = AdjustEndPtr(EndPtr);
3179 Intrinsic::vector_splice_right, {StoredVal,
Poison, &EVL},
3183 SpliceR, EVL, Mask);
3187 if (Rdx->isConditional() &&
3192 if (Interleave->getMask() &&
3200 Intrinsic::vp_merge, {Mask ? Mask : Plan->
getTrue(),
LHS,
RHS, &EVL},
3201 LHS->getScalarType(), {}, {},
DL);
3214 if (
match(&CurRecipe,
3219 LHS->getScalarType(), {}, {},
DL);
3225 {IntrR->getOperand(0),
3226 IntrR->getOperand(1),
3227 Mask ? Mask : Plan->
getTrue(), &EVL},
3228 IntrR->getScalarType(), {}, {},
DL);
3237 VPValue *HeaderMask =
nullptr, *EVL =
nullptr;
3242 HeaderMask = R.getVPSingleValue();
3253 NewR->insertBefore(R);
3254 for (
auto [Old, New] :
3255 zip_equal(R->definedValues(), NewR->definedValues()))
3256 Old->replaceAllUsesWith(New);
3269 Mask->getScalarType(), {}, {}, LogicalAnd->getDebugLoc());
3270 Merge->insertBefore(LogicalAnd);
3271 LogicalAnd->replaceAllUsesWith(
Merge);
3281 [&EVL](
const auto &
X) {
3285 [&Plan, &EVL](
auto *
X) {
3287 Intrinsic::vector_splice_left,
3288 {Plan.
getPoison(
X->getScalarType()),
X, EVL},
X->getScalarType(),
3289 {}, {},
X->getDebugLoc());
3300 R->getVPSingleValue()->getNumUsers() == 0) {
3310 R->getVPSingleValue()->replaceAllUsesWith(
X);
3324 Intrinsic::experimental_vp_reverse, {
X, Plan.
getTrue(), EVL},
3325 X->getScalarType(), {}, {}, R->getDebugLoc());
3326 VPReverse->insertBefore(R);
3327 R->getVPSingleValue()->replaceAllUsesWith(VPReverse);
3333 R->eraseFromParent();
3354 auto IsAllowedUser =
3355 IsaPred<VPVectorEndPointerRecipe, VPScalarIVStepsRecipe,
3356 VPWidenIntOrFpInductionRecipe,
3357 VPWidenMemIntrinsicRecipe>;
3358 if (match(U, m_Trunc(m_Specific(&Plan.getVF()))))
3359 return all_of(cast<VPSingleDefRecipe>(U)->users(),
3361 return IsAllowedUser(U);
3363 "User of VF that we can't transform to EVL.");
3373 "Only users of VFxUF should be VPWidenPointerInductionRecipe and the "
3374 "increment of the canonical induction.");
3390 MaxEVL = Builder.createScalarZExtOrTrunc(
3394 Builder.setInsertPoint(Header, Header->getFirstNonPhi());
3395 VPValue *PrevEVL = Builder.createScalarPhi(
3409 Intrinsic::experimental_vp_splice,
3410 {
V1, V2, Imm, Plan.
getTrue(), PrevEVL, &EVL},
3411 R.getVPSingleValue()->getScalarType(), {}, {}, R.getDebugLoc());
3413 R.getVPSingleValue()->replaceAllUsesWith(VPSplice);
3426 if (match(&R, m_ComputeReductionResult(m_Select(m_Specific(HeaderMask),
3427 m_VPValue(), m_VPValue()))))
3428 return R.getOperand(0)->getDefiningRecipe()->getRegion() ==
3429 Plan.getVectorLoopRegion();
3438 VPValue *EVLMask = Builder.createICmp(
3498 VPlan &Plan,
const std::optional<unsigned> &MaxSafeElements) {
3510 auto *CurrentIteration =
3512 CurrentIteration->insertBefore(*Header, Header->begin());
3513 VPBuilder Builder(Header, Header->getFirstNonPhi());
3516 VPPhi *AVLPhi = Builder.createScalarPhi(
3520 if (MaxSafeElements) {
3530 Builder.setInsertPoint(CanonicalIVIncrement);
3534 OpVPEVL = Builder.createScalarZExtOrTrunc(
3535 OpVPEVL, CanIVTy, I32Ty, CanonicalIVIncrement->getDebugLoc());
3537 auto *NextIter = Builder.createAdd(
3538 OpVPEVL, CurrentIteration, CanonicalIVIncrement->getDebugLoc(),
3539 "current.iteration.next", CanonicalIVIncrement->getNoWrapFlags());
3540 CurrentIteration->addBackedgeValue(NextIter);
3544 "avl.next", {
true,
false});
3552 CanonicalIV->replaceUsesWithIf(CurrentIteration,
3553 [CanonicalIVIncrement](
VPUser &U,
unsigned) {
3554 return &U != CanonicalIVIncrement;
3569 assert(!CurrentIteration &&
3570 "Found multiple CurrentIteration. Only one expected");
3571 CurrentIteration = PhiR;
3575 if (!CurrentIteration)
3586 CurrentIteration->
getDebugLoc(),
"current.iteration.iv");
3595 CanIVInc->eraseFromParent();
3604 if (Header->empty())
3613 if (!
match(EVLPhi->getBackedgeValue(),
3626 [[maybe_unused]]
bool FoundAVLNext =
3629 assert(FoundAVLNext &&
"Didn't find AVL backedge?");
3637 [[maybe_unused]]
bool FoundIncrement =
match(
3644 "Expected BranchOnCond with ICmp comparing CanIV + VFxUF with vector "
3649 LatchBr->setOperand(
3661 "expected to run before loop regions are created");
3663 auto CanUseVersionedStride = [&VPDT, Preheader](
VPUser &U,
unsigned) {
3666 return VPDT.
dominates(Preheader, Parent);
3669 for (
const SCEV *Stride : StridesMap.
values()) {
3672 const APInt *StrideConst;
3695 RewriteMap[StrideV] = PSE.
getSCEV(StrideV);
3702 const SCEV *ScevExpr = ExpSCEV->getSCEV();
3705 if (NewSCEV != ScevExpr) {
3707 ExpSCEV->replaceAllUsesWith(NewExp);
3718 auto CollectPoisonGeneratingInstrsInBackwardSlice([&](
VPRecipeBase *Root) {
3723 while (!Worklist.
empty()) {
3726 if (!Visited.
insert(CurRec).second)
3748 RecWithFlags->isDisjoint()) {
3751 Builder.createAdd(
A,
B, RecWithFlags->getDebugLoc());
3752 New->setUnderlyingValue(RecWithFlags->getUnderlyingValue());
3753 RecWithFlags->replaceAllUsesWith(New);
3754 RecWithFlags->eraseFromParent();
3757 RecWithFlags->dropPoisonGeneratingFlags();
3762 assert((!Instr || !Instr->hasPoisonGeneratingFlags()) &&
3763 "found instruction with poison generating flags not covered by "
3764 "VPRecipeWithIRFlags");
3769 if (
VPRecipeBase *OpDef = Operand->getDefiningRecipe())
3780 auto IsNotHeaderMask = [](
VPValue *Mask) {
3793 VPRecipeBase *AddrDef = WidenRec->getAddr()->getDefiningRecipe();
3794 if (AddrDef && WidenRec->isConsecutive() &&
3795 IsNotHeaderMask(WidenRec->getMask()))
3796 CollectPoisonGeneratingInstrsInBackwardSlice(AddrDef);
3798 VPRecipeBase *AddrDef = InterleaveRec->getAddr()->getDefiningRecipe();
3799 if (AddrDef && IsNotHeaderMask(InterleaveRec->getMask()))
3800 CollectPoisonGeneratingInstrsInBackwardSlice(AddrDef);
3810 const bool &EpilogueAllowed) {
3811 if (InterleaveGroups.empty())
3822 IRMemberToRecipe[&MemR->getIngredient()] = MemR;
3829 for (
const auto *IG : InterleaveGroups) {
3832 for (
auto *Member : IG->members())
3834 StartMember = Member;
3842 for (
unsigned I = 0;
I < IG->getFactor(); ++
I) {
3848 StoredValues.
push_back(StoreR->getStoredValue());
3855 bool NeedsMaskForGaps =
3856 (IG->requiresScalarEpilogue() && !EpilogueAllowed) ||
3857 (!StoredValues.
empty() && !IG->isFull());
3860 auto *InsertPos = IRMemberToRecipe.
lookup(IRInsertPos);
3864 "Dead member in non-load group?");
3869 InsertPos->getAsRecipe()))
3870 InsertPos = MemberR;
3871 IRInsertPos = &InsertPos->getIngredient();
3881 VPValue *Addr = Start->getAddr();
3883 if (IG->getIndex(StartMember) != 0 ||
3891 assert(IG->getIndex(IRInsertPos) != 0 &&
3892 "index of insert position shouldn't be zero");
3896 IG->getIndex(IRInsertPos),
3900 Addr =
B.createNoWrapPtrAdd(InsertPos->getAddr(), OffsetVPV, NW);
3906 if (IG->isReverse()) {
3909 -(int64_t)IG->getFactor(), NW, InsertPosR->
getDebugLoc());
3910 ReversePtr->insertBefore(InsertPosR);
3914 IG, Addr, StoredValues, InsertPos->getMask(), NeedsMaskForGaps,
3916 VPIG->insertBefore(InsertPosR);
3919 for (
unsigned i = 0; i < IG->getFactor(); ++i)
3922 if (!Member->getType()->isVoidTy()) {
3983 AddOp = Instruction::Add;
3984 MulOp = Instruction::Mul;
3986 AddOp =
ID.getInductionOpcode();
3987 MulOp = Instruction::FMul;
3995 Step = Builder.createScalarCast(Instruction::Trunc, Step, Ty,
DL);
3996 Start = Builder.createScalarCast(Instruction::Trunc, Start, Ty,
DL);
4005 Init = Builder.createWidenCast(Instruction::UIToFP,
Init, StepTy);
4010 Init = Builder.createNaryOp(MulOp, {
Init, SplatStep}, Flags);
4011 Init = Builder.createNaryOp(AddOp, {SplatStart,
Init}, Flags,
4029 if (R->getParent()->getEnclosingLoopRegion())
4030 Builder.setInsertPoint(R->getParent(), std::next(R->getIterator()));
4035 VF = Builder.createScalarCast(Instruction::CastOps::UIToFP, VF, StepTy,
4038 VF = Builder.createScalarZExtOrTrunc(VF, StepTy, VF->
getScalarType(),
DL);
4040 Inc = Builder.createNaryOp(MulOp, {Step, VF}, Flags);
4047 auto *
Next = Builder.createNaryOp(AddOp, {Prev, Inc}, Flags,
4050 WidePHI->addIncoming(
Next);
4077 VPlan *Plan = R->getParent()->getPlan();
4078 VPValue *Start = R->getStartValue();
4079 VPValue *Step = R->getStepValue();
4080 VPValue *VF = R->getVFValue();
4082 assert(R->getInductionDescriptor().getKind() ==
4084 "Not a pointer induction according to InductionDescriptor!");
4085 assert(R->getScalarType()->isPointerTy() &&
"Unexpected type.");
4087 "Recipe should have been replaced");
4093 VPPhi *ScalarPtrPhi = Builder.createScalarPhi(Start,
DL,
"pointer.phi");
4097 Builder.setInsertPoint(R->getParent(), R->getParent()->getFirstNonPhi());
4100 Offset = Builder.createOverflowingOp(Instruction::Mul, {
Offset, Step});
4102 Builder.createWidePtrAdd(ScalarPtrPhi,
Offset,
DL,
"vector.gep");
4103 R->replaceAllUsesWith(PtrAdd);
4108 VF = Builder.createScalarZExtOrTrunc(VF, StepTy, VF->
getScalarType(),
DL);
4109 VPValue *Inc = Builder.createOverflowingOp(Instruction::Mul, {Step, VF});
4112 Builder.createPtrAdd(ScalarPtrPhi, Inc,
DL,
"ptr.ind");
4119 VPValue *Start = R->getStartValue();
4120 VPValue *Step = R->getStepValue();
4121 VPValue *Index = R->getIndex();
4125 ? Builder.createScalarSExtOrTrunc(
4127 : Builder.createScalarCast(Instruction::SIToFP, Index, StepTy,
4129 switch (R->getInductionKind()) {
4131 assert(Index->getScalarType() == Start->getScalarType() &&
4132 "Index type does not match StartValue type");
4133 return R->replaceAllUsesWith(Builder.createAdd(
4134 Start, Builder.createOverflowingOp(Instruction::Mul, {Index, Step})));
4137 return R->replaceAllUsesWith(Builder.createPtrAdd(
4138 Start, Builder.createOverflowingOp(Instruction::Mul, {Index, Step})));
4143 (FPBinOp->
getOpcode() == Instruction::FAdd ||
4144 FPBinOp->
getOpcode() == Instruction::FSub) &&
4145 "Original BinOp should be defined for FP induction");
4147 VPValue *
FMul = Builder.createNaryOp(Instruction::FMul, {Step, Index}, FMF);
4148 return R->replaceAllUsesWith(
4149 Builder.createNaryOp(FPBinOp->
getOpcode(), {Start, FMul}, FMF));
4162 if (!R->isReplicator())
4166 R->dissolveToCFGLoop();
4187 assert(Br->getNumOperands() == 2 &&
4188 "BranchOnTwoConds must have exactly 2 conditions");
4192 assert(Successors.size() == 3 &&
4193 "BranchOnTwoConds must have exactly 3 successors");
4198 VPValue *Cond0 = Br->getOperand(0);
4199 VPValue *Cond1 = Br->getOperand(1);
4206 if (Succ0 == Succ1) {
4208 VPValue *Combined = Builder.createOr(Cond0, Cond1,
DL);
4212 Br->eraseFromParent();
4217 !BrOnTwoCondsBB->
getParent() &&
"regions must already be dissolved");
4230 Br->eraseFromParent();
4241 WidenIVR->eraseFromParent();
4251 WidenIVR->replaceAllUsesWith(PtrAdd);
4252 WidenIVR->eraseFromParent();
4256 WidenIVR->eraseFromParent();
4262 DerivedIVR->eraseFromParent();
4267 VPValue *CanIV = WideCanIV->getCanonicalIV();
4269 VPValue *Step = WideCanIV->getStepValue();
4272 "Expected unroller to have materialized step for UF != 1");
4277 Step = Builder.createAdd(
4280 Builder.createAdd(CanIV, Step, WideCanIV->getDebugLoc(),
"vec.iv",
4281 WideCanIV->getNoWrapFlags());
4283 WideCanIV->eraseFromParent();
4290 for (
unsigned I = 1;
I != Blend->getNumIncomingValues(); ++
I)
4291 Select = Builder.createSelect(Blend->getMask(
I),
4292 Blend->getIncomingValue(
I),
Select,
4293 R.getDebugLoc(),
"predphi", *Blend);
4294 Blend->replaceAllUsesWith(
Select);
4295 Blend->eraseFromParent();
4300 if (!VEPR->getOffset()) {
4302 "Expected unroller to have materialized offset for UF != 1");
4303 VEPR->materializeOffset();
4310 Expr->eraseFromParent();
4320 for (
VPValue *
Op : LastActiveL->operands()) {
4321 VPValue *NotMask = Builder.createNot(
Op, LastActiveL->getDebugLoc());
4326 VPValue *FirstInactiveLane = Builder.createFirstActiveLane(
4327 NotMasks, LastActiveL->getDebugLoc(),
"first.inactive.lane");
4333 Builder.createSub(FirstInactiveLane, One,
4334 LastActiveL->getDebugLoc(),
"last.active.lane");
4337 LastActiveL->eraseFromParent();
4344 assert(VPI->isMasked() &&
4345 "Unmasked MaskedCond should be simplified earlier");
4346 VPI->replaceAllUsesWith(Builder.createNaryOp(
4348 VPI->eraseFromParent();
4358 Instruction::Add, VPI->operands(), VPI->getNoWrapFlags(),
4359 VPI->getDebugLoc());
4360 VPI->replaceAllUsesWith(
Add);
4361 VPI->eraseFromParent();
4369 DebugLoc DL = BranchOnCountInst->getDebugLoc();
4372 BranchOnCountInst->eraseFromParent();
4387 ? Instruction::UIToFP
4388 : Instruction::Trunc;
4389 VectorStep = Builder.createWidenCast(CastOp, VectorStep, IVTy);
4395 Builder.createWidenCast(Instruction::Trunc, ScalarStep, IVTy);
4401 MulOpc = Instruction::FMul;
4402 Flags = VPI->getFastMathFlagsOrNone();
4404 MulOpc = Instruction::Mul;
4409 MulOpc, {VectorStep, ScalarStep}, Flags, R.getDebugLoc());
4411 VPI->replaceAllUsesWith(VectorStep);
4412 VPI->eraseFromParent();
4422static std::optional<VPValue *>
4475 VPValue *UncountableCondition =
nullptr;
4479 return std::nullopt;
4482 Worklist.
push_back(UncountableCondition);
4483 while (!Worklist.
empty()) {
4487 if (V->isDefinedOutsideLoopRegions())
4493 if (V->getNumUsers() > 1)
4494 return std::nullopt;
4506 return std::nullopt;
4510 return std::nullopt;
4518 return std::nullopt;
4526 return std::nullopt;
4528 return UncountableCondition;
4584 for (
auto &Exit : Exits) {
4585 if (Exit.EarlyExitingVPBB == LatchVPBB)
4589 cast<VPIRPhi>(&R)->removeIncomingValueFor(Exit.EarlyExitingVPBB);
4590 Exit.EarlyExitingVPBB->getTerminator()->eraseFromParent();
4601 std::optional<VPValue *>
Cond =
4617 assert(Load &&
"Couldn't find exactly one load");
4620 "Uncountable exit condition load is conditional.");
4634 DL.getTypeStoreSize(Load->getScalarType()).getFixedValue());
4658 while (InsertIt != HeaderVPBB->
end() &&
4660 erase(ConditionRecipes, &*InsertIt);
4663 for (
auto *Recipe :
reverse(ConditionRecipes))
4664 Recipe->moveBefore(*HeaderVPBB, InsertIt);
4668 VPBuilder MaskBuilder(HeaderVPBB, InsertIt);
4670 Type *IVScalarTy =
IV->getScalarType();
4677 {Zero, FirstActive, ALMMultiplier},
4678 DebugLoc(),
"uncountable.exit.mask");
4683 if (R.mayReadOrWriteMemory() && &R != Load) {
4685 if (!VPDT.
dominates(R.getParent(), LatchVPBB))
4695 "Expected BranchOnCond terminator for MiddleVPBB");
4706 auto Phis = ScalarPH->
phis();
4716 "Continuing from different IV");
4732 if (Pred == MiddleVPBB)
4737 VPValue *CondOfEarlyExitingVPBB;
4738 [[maybe_unused]]
bool Matched =
4739 match(EarlyExitingVPBB->getTerminator(),
4741 assert(Matched &&
"Terminator must be BranchOnCond");
4745 VPBuilder EarlyExitingBuilder(EarlyExitingVPBB->getTerminator());
4746 auto *CondToEarlyExit = EarlyExitingBuilder.
createNaryOp(
4748 TrueSucc == ExitBlock
4749 ? CondOfEarlyExitingVPBB
4750 : EarlyExitingBuilder.
createNot(CondOfEarlyExitingVPBB));
4756 "exit condition must dominate the latch");
4765 assert(!Exits.
empty() &&
"must have at least one early exit");
4772 for (
const auto &[Num, VPB] :
enumerate(RPOT))
4775 return RPOIdx[
A.EarlyExitingVPBB] < RPOIdx[
B.EarlyExitingVPBB];
4781 for (
unsigned I = 0;
I + 1 < Exits.
size(); ++
I)
4782 for (
unsigned J =
I + 1; J < Exits.
size(); ++J)
4784 Exits[
I].EarlyExitingVPBB) &&
4785 "RPO sort must place dominating exits before dominated ones");
4791 VPValue *Combined = Exits[0].CondToExit;
4804 "Unexpected terminator");
4805 VPValue *IsLatchExitTaken = LatchExitingBranch->getOperand(0);
4806 DebugLoc LatchDL = LatchExitingBranch->getDebugLoc();
4807 LatchExitingBranch->eraseFromParent();
4810 {IsAnyExitTaken, IsLatchExitTaken}, LatchDL);
4816 LatchVPBB->
setSuccessors({MiddleVPBB, MiddleVPBB, HeaderVPBB});
4820 Plan, Exits, HeaderVPBB, LatchVPBB, MiddleVPBB, TheLoop, PSE, DT, AC);
4825 for (
unsigned Idx = 0; Idx != Exits.
size(); ++Idx) {
4829 VectorEarlyExitVPBBs[Idx] = VectorEarlyExitVPBB;
4837 Exits.
size() == 1 ? VectorEarlyExitVPBBs[0]
4840 LatchVPBB->
setSuccessors({DispatchVPBB, MiddleVPBB, HeaderVPBB});
4872 for (
auto [Exit, VectorEarlyExitVPBB] :
4873 zip_equal(Exits, VectorEarlyExitVPBBs)) {
4874 auto &[EarlyExitingVPBB, EarlyExitVPBB,
_] = Exit;
4886 ExitIRI->getIncomingValueForBlock(EarlyExitingVPBB);
4887 VPValue *NewIncoming = IncomingVal;
4889 VPBuilder EarlyExitBuilder(VectorEarlyExitVPBB);
4894 ExitIRI->removeIncomingValueFor(EarlyExitingVPBB);
4895 ExitIRI->addIncoming(NewIncoming);
4898 EarlyExitingVPBB->getTerminator()->eraseFromParent();
4932 bool IsLastDispatch = (
I + 2 == Exits.
size());
4934 IsLastDispatch ? VectorEarlyExitVPBBs.
back()
4940 VectorEarlyExitVPBBs[
I]->setPredecessors({CurrentBB});
4943 CurrentBB = FalseBB;
4958 VPValue *VecOp = Red->getVecOp();
4960 assert(!Red->isPartialReduction() &&
4961 "This path does not support partial reductions");
4964 auto IsExtendedRedValidAndClampRange =
4977 "getExtendedReductionCost only supports integer types");
4978 ExtRedCost = Ctx.TTI.getExtendedReductionCost(
4979 Opcode, ExtOpc == Instruction::CastOps::ZExt, RedTy, SrcVecTy,
4980 Red->getFastMathFlagsOrNone(),
CostKind);
4981 return ExtRedCost.
isValid() && ExtRedCost < ExtCost + RedCost;
4989 IsExtendedRedValidAndClampRange(
5010 if (Opcode != Instruction::Add && Opcode != Instruction::Sub &&
5011 Opcode != Instruction::FAdd)
5014 assert(!Red->isPartialReduction() &&
5015 "This path does not support partial reductions");
5019 auto IsMulAccValidAndClampRange =
5031 (Ext0->getOpcode() != Ext1->getOpcode() ||
5032 Ext0->getOpcode() == Instruction::CastOps::FPExt))
5036 !Ext0 || Ext0->getOpcode() == Instruction::CastOps::ZExt;
5038 MulAccCost = Ctx.TTI.getMulAccReductionCost(IsZExt, Opcode, RedTy,
5045 ExtCost += Ext0->computeCost(VF, Ctx);
5047 ExtCost += Ext1->computeCost(VF, Ctx);
5049 ExtCost += OuterExt->computeCost(VF, Ctx);
5051 return MulAccCost.
isValid() &&
5052 MulAccCost < ExtCost + MulCost + RedCost;
5057 VPValue *VecOp = Red->getVecOp();
5095 Builder.createWidenCast(Instruction::CastOps::Trunc, ValB, NarrowTy);
5097 ValB = ExtB = Builder.createWidenCast(ExtOpc, Trunc, WideTy);
5098 Mul->setOperand(1, ExtB);
5108 ExtendAndReplaceConstantOp(RecipeA, RecipeB,
B,
Mul);
5113 IsMulAccValidAndClampRange(
Mul, RecipeA, RecipeB,
nullptr)) {
5120 if (!
Sub && IsMulAccValidAndClampRange(
Mul,
nullptr,
nullptr,
nullptr))
5137 ExtendAndReplaceConstantOp(Ext0, Ext1,
B,
Mul);
5146 (Ext->getOpcode() == Ext0->getOpcode() || Ext0 == Ext1) &&
5147 Ext0->getOpcode() == Ext1->getOpcode() &&
5148 IsMulAccValidAndClampRange(
Mul, Ext0, Ext1, Ext) &&
Mul->hasOneUse()) {
5150 Ext0->getOpcode(), Ext0->getOperand(0), Ext->getScalarType(),
nullptr,
5151 *Ext0, *Ext0, Ext0->getDebugLoc());
5152 NewExt0->insertBefore(Ext0);
5157 Ext->getScalarType(),
nullptr, *Ext1,
5158 *Ext1, Ext1->getDebugLoc());
5161 auto *NewMul =
Mul->cloneWithOperands({NewExt0, NewExt1});
5162 NewMul->insertBefore(
Mul);
5163 Ext->replaceAllUsesWith(NewMul);
5164 Ext->eraseFromParent();
5165 Mul->eraseFromParent();
5179 assert(!Red->isPartialReduction() &&
5180 "This path does not support partial reductions");
5183 auto IP = std::next(Red->getIterator());
5184 auto *VPBB = Red->getParent();
5194 Red->replaceAllUsesWith(AbstractR);
5224 for (
VPValue *VPV : VPValues) {
5232 if (
User->usesScalars(VPV))
5235 HoistPoint = HoistBlock->
begin();
5239 "All users must be in the vector preheader or dominated by it");
5244 VPV->replaceUsesWithIf(Broadcast,
5245 [VPV, Broadcast](
VPUser &U,
unsigned Idx) {
5246 return Broadcast != &U && !U.usesScalars(VPV);
5257 return CommonMetadata;
5260template <
unsigned Opcode>
5265 static_assert(Opcode == Instruction::Load || Opcode == Instruction::Store,
5266 "Only Load and Store opcodes supported");
5267 [[maybe_unused]]
constexpr bool IsLoad = (Opcode == Instruction::Load);
5274 for (
auto Recipes :
Groups) {
5275 if (Recipes.size() < 2)
5280 "Expected all recipes in group to have the same load-store type");
5287 VPValue *MaskI = RecipeI->getMask();
5293 bool HasComplementaryMask =
false;
5298 VPValue *MaskJ = RecipeJ->getMask();
5307 if (HasComplementaryMask) {
5308 assert(Group.
size() >= 2 &&
"must have at least 2 entries");
5318template <
typename InstType>
5336 for (
auto &Group :
Groups) {
5356 return R->isSingleScalar() == IsSingleScalar;
5358 "all members in group must agree on IsSingleScalar");
5363 LoadWithMinAlign->getUnderlyingInstr(), {EarliestLoad->getOperand(0)},
5364 IsSingleScalar,
nullptr, *EarliestLoad, CommonMetadata);
5366 UnpredicatedLoad->insertBefore(EarliestLoad);
5370 Load->replaceAllUsesWith(UnpredicatedLoad);
5371 Load->eraseFromParent();
5380 if (!StoreLoc || !StoreLoc->AATags.Scope)
5387 SinkStoreInfo SinkInfo(StoresToSink, *StoresToSink[0], PSE, L);
5399 for (
auto &Group :
Groups) {
5412 VPValue *SelectedValue = Group[0]->getOperand(0);
5415 bool IsSingleScalar = Group[0]->isSingleScalar();
5416 for (
unsigned I = 1;
I < Group.size(); ++
I) {
5417 assert(IsSingleScalar == Group[
I]->isSingleScalar() &&
5418 "all members in group must agree on IsSingleScalar");
5419 VPValue *Mask = Group[
I]->getMask();
5421 SelectedValue = Builder.createSelect(Mask,
Value, SelectedValue,
5430 StoreWithMinAlign->getUnderlyingInstr(),
5431 {SelectedValue, LastStore->getOperand(1)}, IsSingleScalar,
5432 nullptr, *LastStore, CommonMetadata);
5433 UnpredicatedStore->insertBefore(*InsertBB, LastStore->
getIterator());
5437 Store->eraseFromParent();
5444 assert(Plan.
hasVF(BestVF) &&
"BestVF is not available in Plan");
5445 assert(Plan.
hasUF(BestUF) &&
"BestUF is not available in Plan");
5508 auto UsesVectorOrInsideReplicateRegion = [DefR, LoopRegion](
VPUser *U) {
5510 return !U->usesScalars(DefR) || ParentRegion != LoopRegion;
5517 none_of(DefR->users(), UsesVectorOrInsideReplicateRegion))
5527 DefR->replaceUsesWithIf(
5528 BuildVector, [BuildVector, &UsesVectorOrInsideReplicateRegion](
5530 return &U != BuildVector && UsesVectorOrInsideReplicateRegion(&U);
5544 for (
VPValue *Def : R.definedValues()) {
5554 unsigned NumFirstLaneUsers =
count_if(Def->users(), [&Def](
VPUser *U) {
5555 return U->usesFirstLaneOnly(Def);
5557 if (!NumFirstLaneUsers || NumFirstLaneUsers == Def->getNumUsers())
5564 Unpack->insertAfter(&R);
5565 Def->replaceUsesWithIf(Unpack, [&Def](
VPUser &U,
unsigned) {
5566 return U.usesFirstLaneOnly(Def);
5575 bool RequiresScalarEpilogue,
VPValue *Step,
5576 std::optional<uint64_t> MaxRuntimeStep) {
5588 "Step VPBB must dominate VectorPHVPBB");
5590 InsertPt = std::next(StepR->getIterator());
5592 VPBuilder Builder(VectorPHVPBB, InsertPt);
5598 if (!RequiresScalarEpilogue &&
match(TC,
m_APInt(TCVal)) && MaxRuntimeStep &&
5599 TCVal->
urem(*MaxRuntimeStep) == 0) {
5610 if (TailByMasking) {
5611 TC = Builder.createAdd(
5622 Builder.createNaryOp(Instruction::URem, {TC, Step},
5631 if (RequiresScalarEpilogue) {
5633 "requiring scalar epilogue is not supported with fail folding");
5636 R = Builder.createSelect(IsZero, Step, R);
5650 "VF and VFxUF must be materialized together");
5662 Builder.createElementCount(TCTy, VFEC * Plan.
getConcreteUF());
5669 VPValue *RuntimeVF = Builder.createElementCount(TCTy, VFEC);
5673 BC, [&VF](
VPUser &U,
unsigned) {
return !U.usesScalars(&VF); });
5677 VPValue *MulByUF = Builder.createOverflowingOp(
5690 auto *AliasMask = Builder.createNaryOp(
5695 Builder =
VPBuilder(Header, Header->getFirstNonPhi());
5698 auto *ClampedHeaderMask = Builder.createAnd(HeaderMask, AliasMask);
5700 return &U != ClampedHeaderMask;
5711 assert(IncomingAliasMask &&
"Expected an alias mask!");
5721 if (
Check.NeedsFreeze) {
5731 Intrinsic::loop_dependence_war_mask,
5735 AliasMask = Builder.createAnd(AliasMask, WARMask);
5737 AliasMask = WARMask;
5742 VPValue *NumActive = Builder.createNaryOp(
5745 VPValue *ClampedVF = Builder.createScalarZExtOrTrunc(
5771 VPValue *DistanceToMax = Builder.createSub(MaxUIntTripCount, TripCount);
5779 VPValue *TripCountCheck = Builder.createICmp(
5782 VPValue *
Cond = Builder.createOr(IsScalar, TripCountCheck,
DL);
5793 "Clamped VF not supported with interleaving");
5801 VPBuilder Builder(Entry, Entry->begin());
5813 if (!ExpSCEV || ExpSCEV->user_empty())
5815 Builder.setInsertPoint(ExpSCEV);
5824 ExpSCEV->eraseFromParent();
5833 BasicBlock *EntryBB = Entry->getIRBasicBlock();
5840 const SCEV *Expr = ExpSCEV->getSCEV();
5843 ExpandedSCEVs[Expr] = Res;
5848 ExpSCEV->eraseFromParent();
5851 "all VPExpandSCEVRecipes must have been expanded");
5854 auto EI = Entry->begin();
5864 return ExpandedSCEVs;
5878 VPValue *OpV,
unsigned Idx,
bool IsScalable) {
5883 if (Member0Op == OpV)
5893 return !IsScalable && !W->getMask() && W->isConsecutive() &&
5896 return IR->getInterleaveGroup()->isFull() &&
IR->getVPValue(Idx) == OpV;
5911 if (R->getScalarType() != WideMember0->getScalarType())
5913 if (R->hasPredicate() && R->getPredicate() != WideMember0->getPredicate())
5917 for (
unsigned Idx = 0; Idx != WideMember0->getNumOperands(); ++Idx) {
5920 OpsI.
push_back(
Op->getDefiningRecipe()->getOperand(Idx));
5925 if (
any_of(
enumerate(OpsI), [WideMember0, Idx, IsScalable](
const auto &
P) {
5926 const auto &[
OpIdx, OpV] =
P;
5938static std::optional<ElementCount>
5942 if (!InterleaveR || InterleaveR->
getMask())
5943 return std::nullopt;
5945 Type *GroupElementTy =
nullptr;
5949 return Op->getScalarType() == GroupElementTy;
5951 return std::nullopt;
5955 return Op->getScalarType() == GroupElementTy;
5957 return std::nullopt;
5961 if (IG->getFactor() != IG->getNumMembers())
5962 return std::nullopt;
5968 assert(
Size.isScalable() == VF.isScalable() &&
5969 "if Size is scalable, VF must be scalable and vice versa");
5970 return Size.getKnownMinValue();
5974 unsigned MinVal = VF.getKnownMinValue();
5976 if (IG->getFactor() == MinVal && GroupSize == GetVectorBitWidthForVF(VF))
5979 return std::nullopt;
5987 return RepR && RepR->isSingleScalar();
6001 if (V->isDefinedOutsideLoopRegions()) {
6004 return M->isDefinedOutsideLoopRegions() &&
6005 M->getScalarType() == V->getScalarType();
6007 "expected distinct loop-invariant values of matching scalar type");
6022 for (
unsigned Idx = 0,
E = WideMember0->getNumOperands(); Idx !=
E; ++Idx) {
6024 for (
VPValue *Member : Members)
6025 OpsI.
push_back(Member->getDefiningRecipe()->getOperand(Idx));
6026 WideMember0->setOperand(
6035 auto *LI =
cast<LoadInst>(LoadGroup->getInterleaveGroup()->getInsertPos());
6037 LoadGroup->getMask(),
true,
6038 *LoadGroup, LoadGroup->getDebugLoc());
6039 L->insertBefore(LoadGroup);
6045 assert(RepR->isSingleScalar() && RepR->getOpcode() == Instruction::Load &&
6046 "must be a single scalar load");
6047 NarrowedOps.
insert(RepR);
6052 VPValue *PtrOp = WideLoad->getAddr();
6054 PtrOp = VecPtr->getOperand(0);
6059 nullptr, {}, *WideLoad);
6060 N->insertBefore(WideLoad);
6065std::unique_ptr<VPlan>
6085 "unexpected branch-on-count");
6088 std::optional<ElementCount> VFToOptimize;
6102 if (R.mayWriteToMemory() && !InterleaveR)
6108 return any_of(V->users(), [&](VPUser *U) {
6109 auto *UR = cast<VPRecipeBase>(U);
6110 return UR->getParent()->getParent() != VectorLoop;
6127 std::optional<ElementCount> NarrowedVF =
6129 if (!NarrowedVF || (VFToOptimize && NarrowedVF != VFToOptimize))
6131 VFToOptimize = NarrowedVF;
6134 if (InterleaveR->getStoredValues().empty())
6139 auto *Member0 = InterleaveR->getStoredValues()[0];
6149 VPRecipeBase *DefR = Op.value()->getDefiningRecipe();
6152 auto *IR = dyn_cast<VPInterleaveRecipe>(DefR);
6153 return IR && IR->getInterleaveGroup()->isFull() &&
6154 IR->getVPValue(Op.index()) == Op.value();
6163 VFToOptimize->isScalable()))
6168 if (StoreGroups.empty())
6172 bool RequiresScalarEpilogue =
6183 std::unique_ptr<VPlan> NewPlan;
6185 NewPlan = std::unique_ptr<VPlan>(Plan.
duplicate());
6186 Plan.
setVF(*VFToOptimize);
6187 NewPlan->removeVF(*VFToOptimize);
6194 for (
auto *StoreGroup : StoreGroups) {
6196 NarrowedOps, Preheader);
6201 StoreGroup->getDebugLoc());
6202 S->insertBefore(StoreGroup);
6203 StoreGroup->eraseFromParent();
6209 Type *CanIVTy = VectorLoop->getCanonicalIVType();
6215 if (VFToOptimize->isScalable()) {
6218 Step = PHBuilder.createOverflowingOp(Instruction::Mul, {VScale,
UF},
6226 materializeVectorTripCount(Plan, VectorPH,
false,
6227 RequiresScalarEpilogue, Step);
6232 removeDeadRecipes(Plan);
6235 "All VPVectorPointerRecipes should have been removed");
6251 "must have a BranchOnCond");
6254 if (VF.
isScalable() && VScaleForTuning.has_value())
6255 VectorStep *= *VScaleForTuning;
6256 assert(VectorStep > 0 &&
"trip count should not be zero");
6260 MiddleTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
6279 "Cannot handle loops with uncountable early exits");
6286 assert(RecurSplice &&
"expected FirstOrderRecurrenceSplice");
6293 if (
any_of(RecurSplice->users(),
6294 [](
VPUser *U) { return !cast<VPRecipeBase>(U)->getRegion(); }) &&
6375 {},
"vector.recur.extract.for.phi");
6378 ExitPhi->replaceUsesOfWith(ExtractR, PenultimateElement);
6392 VPValue *WidenIVCandidate = BinOp->getOperand(0);
6393 VPValue *InvariantCandidate = BinOp->getOperand(1);
6395 std::swap(WidenIVCandidate, InvariantCandidate);
6409 auto *ClonedOp = BinOp->
clone();
6410 if (ClonedOp->getOperand(0) == WidenIV) {
6411 ClonedOp->setOperand(0, ScalarIV);
6413 assert(ClonedOp->getOperand(1) == WidenIV &&
"one operand must be WideIV");
6414 ClonedOp->setOperand(1, ScalarIV);
6429 auto CheckSentinel = [&SE](
const SCEV *IVSCEV,
6430 bool UseMax) -> std::optional<APSInt> {
6432 for (
bool Signed : {
true,
false}) {
6441 return std::nullopt;
6449 PhiR->getRecurrenceKind()))
6458 VPValue *BackedgeVal = PhiR->getBackedgeValue();
6472 !
match(FindLastSelect,
6481 IVOfExpressionToSink ? IVOfExpressionToSink : FindLastExpression, PSE,
6487 "IVOfExpressionToSink not being an AddRec must imply "
6488 "FindLastExpression not being an AddRec.");
6499 std::optional<APSInt> SentinelVal = CheckSentinel(IVSCEV, UseMax);
6500 bool UseSigned = SentinelVal && SentinelVal->isSigned();
6507 if (IVOfExpressionToSink) {
6508 const SCEV *FindLastExpressionSCEV =
6510 if (
match(FindLastExpressionSCEV,
6513 if (
auto NewSentinel =
6514 CheckSentinel(FindLastExpressionSCEV, NewUseMax)) {
6517 SentinelVal = *NewSentinel;
6518 UseSigned = NewSentinel->isSigned();
6520 IVSCEV = FindLastExpressionSCEV;
6521 IVOfExpressionToSink =
nullptr;
6531 if (AR->hasNoSignedWrap())
6533 else if (AR->hasNoUnsignedWrap())
6543 VPValue *NewFindLastSelect = BackedgeVal;
6545 if (!SentinelVal || IVOfExpressionToSink) {
6548 DebugLoc DL = FindLastSelect->getDefiningRecipe()->getDebugLoc();
6549 VPBuilder LoopBuilder(FindLastSelect->getDefiningRecipe());
6550 if (FindLastSelect->getDefiningRecipe()->getOperand(1) == PhiR)
6551 SelectCond = LoopBuilder.
createNot(SelectCond);
6558 if (SelectCond !=
Cond || IVOfExpressionToSink) {
6561 IVOfExpressionToSink ? IVOfExpressionToSink : FindLastExpression,
6570 VPIRFlags Flags(MinMaxKind,
false,
false,
6576 NewFindLastSelect, Flags, ExitDL);
6579 VPValue *VectorRegionExitingVal = ReducedIV;
6580 if (IVOfExpressionToSink)
6581 VectorRegionExitingVal =
6583 ReducedIV, IVOfExpressionToSink);
6586 VPValue *StartVPV = PhiR->getStartValue();
6593 NewRdxResult = MiddleBuilder.
createSelect(Cmp, VectorRegionExitingVal,
6603 AnyOfPhi->insertAfter(PhiR);
6610 OrVal, VectorRegionExitingVal, StartVPV, ExitDL);
6623 PhiR->hasUsesOutsideReductionChain());
6624 NewPhiR->insertBefore(PhiR);
6625 PhiR->replaceAllUsesWith(NewPhiR);
6626 PhiR->eraseFromParent();
6633struct ReductionExtend {
6634 Type *SrcType =
nullptr;
6635 ExtendKind Kind = ExtendKind::PR_None;
6641struct ExtendedReductionOperand {
6645 ReductionExtend ExtendA, ExtendB;
6653struct VPPartialReductionChain {
6656 VPWidenRecipe *ReductionBinOp =
nullptr;
6658 ExtendedReductionOperand ExtendedOp;
6665 unsigned AccumulatorOpIdx;
6666 unsigned ScaleFactor;
6669 VPBlendRecipe *Blend =
nullptr;
6674static std::optional<unsigned>
6678 "Expected a non-normalized blend with two incoming values");
6684 return std::nullopt;
6685 return FirstIncomingHasOneUse ? 0 : 1;
6697 if (!
Op->hasOneUse() ||
6703 auto *Trunc = Builder.createWidenCast(Instruction::CastOps::Trunc,
6704 Op->getOperand(1), NarrowTy);
6706 Op->setOperand(1, Builder.createWidenCast(ExtOpc, Trunc, WideTy));
6715 auto *
Sub =
Op->getOperand(0)->getDefiningRecipe();
6717 assert(Ext->getOpcode() ==
6719 "Expected both the LHS and RHS extends to be the same");
6720 bool IsSigned = Ext->getOpcode() == Instruction::SExt;
6723 auto *FreezeX = Builder.insert(
new VPWidenRecipe(Instruction::Freeze, {
X}));
6724 auto *FreezeY = Builder.insert(
new VPWidenRecipe(Instruction::Freeze, {
Y}));
6725 auto *
Max = Builder.insert(
6727 {FreezeX, FreezeY}, SrcTy));
6728 auto *Min = Builder.insert(
6730 {FreezeX, FreezeY}, SrcTy));
6733 return Builder.createWidenCast(Instruction::CastOps::ZExt, AbsDiff,
6734 Op->getScalarType());
6746 if (!
Mul->hasOneUse() ||
6747 (Ext->getOpcode() != MulLHS->getOpcode() && MulLHS != MulRHS) ||
6748 MulLHS->getOpcode() != MulRHS->getOpcode())
6751 auto *NewLHS = Builder.createWidenCast(
6752 MulLHS->getOpcode(), MulLHS->getOperand(0), Ext->getScalarType());
6753 auto *NewRHS = MulLHS == MulRHS
6755 : Builder.createWidenCast(MulRHS->getOpcode(),
6756 MulRHS->getOperand(0),
6757 Ext->getScalarType());
6758 auto *NewMul =
Mul->cloneWithOperands({NewLHS, NewRHS});
6759 Builder.insert(NewMul);
6760 Op->replaceAllUsesWith(NewMul);
6761 Op->eraseFromParent();
6762 Mul->eraseFromParent();
6771 VPValue *VecOp = Red->getVecOp();
6825static void transformToPartialReduction(
const VPPartialReductionChain &Chain,
6833 WidenRecipe->
getOperand(1 - Chain.AccumulatorOpIdx));
6836 ExtendedOp = optimizeExtendsForPartialReduction(ExtendedOp);
6852 if ((WidenRecipe->
getOpcode() == Instruction::Sub &&
6854 (WidenRecipe->
getOpcode() == Instruction::FSub &&
6859 if (WidenRecipe->
getOpcode() == Instruction::FSub) {
6869 Builder.insert(NegRecipe);
6870 ExtendedOp = NegRecipe;
6885 std::optional<unsigned> BlendReductionIdx =
6886 getBlendReductionUpdateValueIdx(Chain.Blend);
6887 assert(BlendReductionIdx &&
6889 "Expected blend to contain the reduction update");
6900 assert((!ExitValue || IsLastInChain) &&
6901 "if we found ExitValue, it must match RdxPhi's backedge value");
6912 PartialRed->insertBefore(WidenRecipe);
6922 E->insertBefore(WidenRecipe);
6923 PartialRed->replaceAllUsesWith(
E);
6936 auto *NewScaleFactor = Plan.
getConstantInt(32, Chain.ScaleFactor);
6937 StartInst->setOperand(2, NewScaleFactor);
6945 VPValue *OldStartValue = StartInst->getOperand(0);
6946 StartInst->setOperand(0, StartInst->getOperand(1));
6950 assert(RdxResult &&
"Could not find reduction result");
6953 unsigned SubOpc = Chain.RK ==
RecurKind::FSub ? Instruction::BinaryOps::FSub
6954 : Instruction::BinaryOps::Sub;
6960 [&NewResult](
VPUser &U,
unsigned Idx) {
return &
U != NewResult; });
6966 const VPPartialReductionChain &Link,
6969 const ExtendedReductionOperand &ExtendedOp = Link.ExtendedOp;
6970 std::optional<unsigned> BinOpc = std::nullopt;
6972 if (ExtendedOp.ExtendB.Kind != ExtendKind::PR_None)
6973 BinOpc = ExtendedOp.ExtendsUser->
getOpcode();
6975 std::optional<llvm::FastMathFlags>
Flags;
6979 auto GetLinkOpcode = [&Link]() ->
unsigned {
6982 return Instruction::Add;
6984 return Instruction::FAdd;
6986 return Link.ReductionBinOp->
getOpcode();
6991 GetLinkOpcode(), ExtendedOp.ExtendA.SrcType, ExtendedOp.ExtendB.SrcType,
6992 RdxType, VF, ExtendedOp.ExtendA.Kind, ExtendedOp.ExtendB.Kind, BinOpc,
7013static std::optional<ExtendedReductionOperand>
7016 "Op should be operand of UpdateR");
7024 if (
Op->hasOneUse() &&
7033 Type *RHSInputType =
Y->getScalarType();
7034 if (LHSInputType != RHSInputType ||
7035 LHSExt->getOpcode() != RHSExt->getOpcode())
7036 return std::nullopt;
7039 return ExtendedReductionOperand{
7041 {LHSInputType, getPartialReductionExtendKind(LHSExt)},
7045 std::optional<TTI::PartialReductionExtendKind> OuterExtKind;
7048 VPValue *CastSource = CastRecipe->getOperand(0);
7049 OuterExtKind = getPartialReductionExtendKind(CastRecipe);
7059 return ExtendedReductionOperand{
7066 if (!
Op->hasOneUse())
7067 return std::nullopt;
7072 return std::nullopt;
7082 return std::nullopt;
7086 ExtendKind LHSExtendKind = getPartialReductionExtendKind(LHSCast);
7089 const APInt *RHSConst =
nullptr;
7095 return std::nullopt;
7099 if (Cast && OuterExtKind &&
7100 getPartialReductionExtendKind(Cast) != OuterExtKind)
7101 return std::nullopt;
7103 Type *RHSInputType = LHSInputType;
7104 ExtendKind RHSExtendKind = LHSExtendKind;
7107 RHSExtendKind = getPartialReductionExtendKind(RHSCast);
7110 return ExtendedReductionOperand{
7111 MulOp, {LHSInputType, LHSExtendKind}, {RHSInputType, RHSExtendKind}};
7118static std::optional<SmallVector<VPPartialReductionChain>>
7125 return std::nullopt;
7135 VPValue *CurrentValue = ExitValue;
7136 while (CurrentValue != RedPhiR) {
7138 std::optional<unsigned> BlendReductionIdx;
7142 return std::nullopt;
7144 BlendReductionIdx = getBlendReductionUpdateValueIdx(Blend);
7145 if (!BlendReductionIdx)
7146 return std::nullopt;
7153 return std::nullopt;
7160 std::optional<ExtendedReductionOperand> ExtendedOp =
7161 matchExtendedReductionOperand(UpdateR,
Op);
7163 ExtendedOp = matchExtendedReductionOperand(UpdateR, PrevValue);
7165 return std::nullopt;
7173 return std::nullopt;
7175 Type *ExtSrcType = ExtendedOp->ExtendA.SrcType;
7178 return std::nullopt;
7180 VPPartialReductionChain Link(
7181 {UpdateR, *ExtendedOp, RK,
7186 CurrentValue = PrevValue;
7191 std::reverse(Chain.
begin(), Chain.
end());
7210 if (
auto Chains = getScaledReductions(RedPhiR))
7211 ChainsByPhi.
try_emplace(RedPhiR, std::move(*Chains));
7214 if (ChainsByPhi.
empty())
7222 for (
const auto &[
_, Chains] : ChainsByPhi)
7223 for (
const VPPartialReductionChain &Chain : Chains) {
7224 PartialReductionOps.
insert(Chain.ExtendedOp.ExtendsUser);
7226 PartialReductionBlends.
insert(Chain.Blend);
7227 ScaledReductionMap[Chain.ReductionBinOp] = Chain.ScaleFactor;
7233 auto ExtendUsersValid = [&](
VPValue *Ext) {
7235 return PartialReductionOps.contains(cast<VPRecipeBase>(U));
7239 auto IsProfitablePartialReductionChainForVF =
7246 for (
const VPPartialReductionChain &Link : Chain) {
7247 const ExtendedReductionOperand &ExtendedOp = Link.ExtendedOp;
7248 InstructionCost LinkCost = getPartialReductionLinkCost(CostCtx, Link, VF);
7252 PartialCost += LinkCost;
7253 RegularCost += Link.ReductionBinOp->
computeCost(VF, CostCtx);
7255 if (ExtendedOp.ExtendB.Kind != ExtendKind::PR_None)
7256 RegularCost += ExtendedOp.ExtendsUser->
computeCost(VF, CostCtx);
7259 RegularCost += Extend->computeCost(VF, CostCtx);
7261 return PartialCost.
isValid() && PartialCost < RegularCost;
7269 for (
auto &[RedPhiR, Chains] : ChainsByPhi) {
7270 for (
const VPPartialReductionChain &Chain : Chains) {
7271 if (!
all_of(Chain.ExtendedOp.ExtendsUser->operands(), ExtendUsersValid)) {
7275 auto UseIsValid = [&, RedPhiR = RedPhiR](
VPUser *U) {
7277 return PhiR == RedPhiR;
7281 return Blend == Chain.Blend || PartialReductionBlends.
contains(Blend);
7283 return Chain.ScaleFactor == ScaledReductionMap.
lookup_or(R, 0) ||
7289 if (!
all_of(Chain.ReductionBinOp->users(), UseIsValid)) {
7298 auto *RepR = dyn_cast<VPReplicateRecipe>(U);
7299 return RepR && RepR->getOpcode() == Instruction::Store;
7310 return IsProfitablePartialReductionChainForVF(Chains, VF);
7316 for (
auto &[Phi, Chains] : ChainsByPhi)
7317 for (
const VPPartialReductionChain &Chain : Chains)
7318 transformToPartialReduction(Chain, Plan, Phi);
7347 if (VPI && VPI->getUnderlyingValue() &&
7358 auto ProcessSubset = [&](
VPlan &,
auto ProcessVPInst) {
7361 if (!ProcessVPInst(VPI))
7370 New->insertBefore(VPI);
7371 if (VPI->
getOpcode() == Instruction::Load)
7386 "lowerMemoryIdioms", ProcessSubset, Plan, [&](
VPInstruction *VPI) {
7388 VPI, FinalRedStoresBuilder))
7397 return ReplaceWith(VPI, Histogram);
7410 "scalarizeMemOpsWithIrregularTypes", ProcessSubset, Plan,
7414 return Scalarize(VPI);
7421 "makeVPlanMemOpDecision", ProcessSubset, Plan, [&](
VPInstruction *VPI) {
7423 bool IsLoad = VPI->
getOpcode() == Instruction::Load;
7433 const SCEV *PtrSCEV =
7435 bool IsSingleScalarLoad =
7441 I, Ptr, IsSingleScalarLoad,
7449 "widenConsecutiveMemOps", ProcessSubset, Plan, [&](
VPInstruction *VPI) {
7454 bool IsLoad = VPI->
getOpcode() == Instruction::Load;
7467 VectorPtr->insertBefore(VPI);
7478 return ReplaceWith(VPI, WidenedR);
7485 return ReplaceWith(VPI, Recipe);
7487 return Scalarize(VPI);
7510 if (VPI->mayHaveSideEffects())
7514 if (VPI->isMasked() && !VPI->isSafeToSpeculativelyExecute())
7519 if (VPI->getOpcode() == Instruction::Add &&
7528 VPI->getOpcode(), VPI->operandsWithoutMask(),
nullptr, *VPI,
7529 *VPI, VPI->getDebugLoc(),
I);
7530 Recipe->insertBefore(VPI);
7531 VPI->replaceAllUsesWith(Recipe);
7532 VPI->eraseFromParent();
7542 switch (Param.ParamKind) {
7543 case VFParamKind::Vector:
7544 case VFParamKind::GlobalPredicate:
7546 case VFParamKind::OMP_Uniform:
7547 return SE->isSCEVable(Args[Param.ParamPos]->getScalarType()) &&
7548 SE->isLoopInvariant(
7549 vputils::getSCEVExprForVPValue(Args[Param.ParamPos], PSE, L),
7551 case VFParamKind::OMP_Linear:
7552 return match(vputils::getSCEVExprForVPValue(Args[Param.ParamPos], PSE, L),
7553 m_scev_AffineAddRec(
7554 m_SCEV(), m_scev_SpecificSInt(Param.LinearStepOrPos),
7555 m_SpecificLoop(L)));
7572 const auto *It =
find_if(Mappings, [&](
const VFInfo &Info) {
7573 return Info.Shape.VF == VF && (!MaskRequired || Info.isMasked()) &&
7576 if (It == Mappings.end())
7583struct CallWideningDecision {
7584 enum class KindTy { Scalarize,
Intrinsic, VectorVariant };
7585 CallWideningDecision(KindTy Kind, Function *Variant =
nullptr)
7608 return CallWideningDecision::KindTy::Scalarize;
7618 return CallWideningDecision::KindTy::Scalarize;
7622 false, VF, CostCtx);
7637 return CallWideningDecision::KindTy::Intrinsic;
7641 if (VecFunc && ScalarCost >= VecCallCost)
7642 return {CallWideningDecision::KindTy::VectorVariant, VecFunc};
7644 return CallWideningDecision::KindTy::Scalarize;
7654 if (!VPI || !VPI->getUnderlyingValue() ||
7655 VPI->getOpcode() != Instruction::Call)
7660 VPI->op_begin() + CI->arg_size());
7662 CallWideningDecision Decision =
7671 switch (Decision.Kind) {
7672 case CallWideningDecision::KindTy::Intrinsic: {
7676 *VPI, VPI->getDebugLoc());
7679 case CallWideningDecision::KindTy::VectorVariant: {
7683 VPValue *Mask = VPI->isMasked() ? VPI->getMask() : Plan.
getTrue();
7684 Ops.push_back(Mask);
7686 Ops.push_back(VPI->getOperand(VPI->getNumOperandsWithoutMask() - 1));
7688 *VPI, VPI->getDebugLoc());
7691 case CallWideningDecision::KindTy::Scalarize:
7697 VPI->replaceAllUsesWith(Replacement);
7698 VPI->eraseFromParent();
7721 if (!LoadR || LoadR->isConsecutive())
7740 Align Alignment = LoadR->getAlign();
7743 if (!Ctx.TTI.isLegalStridedLoadStore(DataTy, Alignment))
7748 Intrinsic::experimental_vp_strided_load, DataTy,
7749 LoadR->isMasked(), Alignment, Ctx);
7750 return StridedLoadStoreCost < CurrentCost;
7761 Ctx.invalidateWideningDecision(&LoadR->getIngredient(), VF);
7766 I32VF = Builder.createScalarZExtOrTrunc(
7783 "Stride type from SCEV must match the index type");
7784 VPValue *CanIV = Builder.createScalarSExtOrTrunc(
7788 auto *
Offset = Builder.createOverflowingOp(
7789 Instruction::Mul, {CanIV, StrideInBytes},
7790 {AddRecPtr->hasNoUnsignedWrap(), AddRecPtr->hasNoSignedWrap()});
7791 auto *BasePtr = Builder.createNoWrapPtrAdd(
7797 VPValue *NewPtr = Builder.createVectorPointer(
7799 Ptr->getGEPNoWrapFlags(), Ptr->getDebugLoc());
7801 VPValue *Mask = LoadR->getMask();
7804 auto *StridedLoad = Builder.createWidenMemIntrinsic(
7805 Intrinsic::experimental_vp_strided_load,
7806 {NewPtr, StrideInBytes, Mask, I32VF}, LoadTy, Alignment, *LoadR,
7807 LoadR->getDebugLoc());
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static bool isEqual(const Function &Caller, const Function &Callee)
static const Function * getParent(const Value *V)
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")
static cl::opt< OutputCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(OutputCostKind::RecipThroughput), cl::values(clEnumValN(OutputCostKind::RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(OutputCostKind::Latency, "latency", "Instruction latency"), clEnumValN(OutputCostKind::CodeSize, "code-size", "Code size"), clEnumValN(OutputCostKind::SizeAndLatency, "size-latency", "Code size and latency"), clEnumValN(OutputCostKind::All, "all", "Print all cost kinds")))
static cl::opt< IntrinsicCostStrategy > IntrinsicCost("intrinsic-cost-strategy", cl::desc("Costing strategy for intrinsic instructions"), cl::init(IntrinsicCostStrategy::InstructionCost), cl::values(clEnumValN(IntrinsicCostStrategy::InstructionCost, "instruction-cost", "Use TargetTransformInfo::getInstructionCost"), clEnumValN(IntrinsicCostStrategy::IntrinsicCost, "intrinsic-cost", "Use TargetTransformInfo::getIntrinsicInstrCost"), clEnumValN(IntrinsicCostStrategy::TypeBasedIntrinsicCost, "type-based-intrinsic-cost", "Calculate the intrinsic cost based only on argument types")))
iv Induction Variable Users
static std::pair< Value *, APInt > getMask(Value *WideMask, unsigned Factor, ElementCount LeafValueEC)
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.
MachineInstr unsigned OpIdx
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
const SmallVectorImpl< MachineOperand > & Cond
static bool dominates(InstrPosIndexes &PosIndexes, const MachineInstr &A, const MachineInstr &B)
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")
static SymbolRef::Type getType(const Symbol *Sym)
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 declares the class VPlanVerifier, which contains utility functions to check the consistency...
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.
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
unsigned getActiveBits() const
Compute the number of active bits in the value.
APInt abs() const
Get the absolute value.
LLVM_ABI APInt urem(const APInt &RHS) const
Unsigned remainder operation.
unsigned getBitWidth() const
Return the number of bits in the APInt.
int32_t exactLogBase2() const
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.
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.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
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)
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...
static ConstantInt * getSigned(IntegerType *Ty, int64_t V, bool ImplicitTrunc=false)
Return a ConstantInt with the specified value for the specified type.
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.
static LLVM_ABI Constant * getAllOnesValue(Type *Ty)
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 getCompilerGenerated()
static DebugLoc getUnknown()
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)
ValueT lookup_or(const_arg_type_t< KeyT > Val, U &&Default) const
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.
constexpr bool isVector() const
One or more elements.
static constexpr ElementCount getScalable(ScalarTy MinVal)
constexpr bool isScalar() const
Exactly one element.
Utility class for floating point operations which can have information about relaxed accuracy require...
FastMathFlags getFastMathFlags() const
Convenience function for getting all the fast-math flags.
Convenience struct for specifying and reasoning about fast-math flags.
Represents flags for the getelementptr instruction/expression.
static GEPNoWrapFlags noUnsignedWrap()
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.
static LLVM_ABI InductionDescriptor getCanonicalIntInduction(Type *Ty, ScalarEvolution &SE)
Returns the canonical integer induction for type Ty with start = 0 and step = 1.
InductionKind
This enum represents the kinds of inductions that we support.
@ IK_NoInduction
Not an induction variable.
@ IK_FpInduction
Floating point induction variable.
@ IK_PtrInduction
Pointer induction var. Step = C.
@ IK_IntInduction
Integer induction variable. Step = C.
InstSimplifyFolder - Use InstructionSimplify to fold operations to existing values.
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.
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.
unsigned getOpcode() const
Return the opcode for this Instruction or ConstantExpr.
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,...
RegionT * getParent() const
Get the parent of the Region.
This class represents a constant integer value.
ConstantInt * getValue() const
This class uses information about analyze scalars to rewrite expressions in canonical form.
LLVM_ABI Value * expandCodeFor(SCEVUse SH, Type *Ty, BasicBlock::iterator I)
Insert code to directly compute the specified SCEV expression into the program.
static const SCEV * rewrite(const SCEV *Scev, ScalarEvolution &SE, ValueToSCEVMapTy &Map)
This class represents an analyzed expression in the program.
LLVM_ABI Type * getType() const
Return the LLVM type of this SCEV expression.
The main scalar evolution driver.
LLVM_ABI const SCEV * getUDivExpr(SCEVUse LHS, SCEVUse RHS)
Get a canonical unsigned division expression, or something simpler if possible.
const DataLayout & getDataLayout() const
Return the DataLayout associated with the module this SCEV instance is operating on.
LLVM_ABI const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
LLVM_ABI bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
LLVM_ABI const SCEV * getConstant(ConstantInt *V)
LLVM_ABI const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
LLVM_ABI const SCEV * getMinusSCEV(SCEVUse LHS, SCEVUse RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
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.
LLVM_ABI const SCEV * getElementCount(Type *Ty, ElementCount EC, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
LLVM_ABI const SCEV * getMulExpr(SmallVectorImpl< SCEVUse > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
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,...
static LLVM_ABI AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
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.
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...
This class implements a switch-like dispatch statement for a value of 'T' using dyn_cast functionalit...
TypeSwitch< T, ResultT > & Case(CallableT &&caseFn)
Add a case on the given type.
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 IntegerType * getInt8Ty(LLVMContext &C)
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
bool isStructTy() const
True if this is an instance of StructType.
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
LLVM_ABI unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
bool isFloatingPointTy() const
Return true if this is one of the floating-point types.
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.
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
const std::string & getName() const
void clearSuccessors()
Remove all the successors of this block.
VPBlockBase * getSinglePredecessor() const
void clearPredecessors()
Remove all the predecessor of this block.
const VPBasicBlock * getEntryBasicBlock() const
VPBlockBase * getSingleHierarchicalPredecessor()
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 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 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.
RAII object that stores the current insertion point and restores it when the object is destroyed.
VPlan-based builder utility analogous to IRBuilder.
VPDerivedIVRecipe * createDerivedIV(InductionDescriptor::InductionKind Kind, FPMathOperator *FPBinOp, VPValue *Start, VPValue *Current, VPValue *Step)
Convert the input value Current to the corresponding value of an induction with Start and Step values...
VPInstruction * createFirstActiveLane(ArrayRef< VPValue * > Masks, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="")
VPInstruction * createAdd(VPValue *LHS, VPValue *RHS, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="", VPRecipeWithIRFlags::WrapFlagsTy WrapFlags={false, false})
VPInstruction * createOr(VPValue *LHS, VPValue *RHS, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="")
VPValue * createScalarZExtOrTrunc(VPValue *Op, Type *ResultTy, Type *SrcTy, DebugLoc DL)
VPInstruction * createLogicalOr(VPValue *LHS, VPValue *RHS, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="")
VPInstruction * createNot(VPValue *Operand, 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 ...
VPInstruction * createLogicalAnd(VPValue *LHS, VPValue *RHS, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="")
VPInstruction * createScalarCast(Instruction::CastOps Opcode, VPValue *Op, Type *ResultTy, DebugLoc DL, const VPIRMetadata &Metadata={})
VPWidenPHIRecipe * createWidenPhi(ArrayRef< VPValue * > IncomingValues, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="")
static VPBuilder getToInsertAfter(VPRecipeBase *R)
Create a VPBuilder to insert after R.
VPWidenCastRecipe * createWidenCast(Instruction::CastOps Opcode, VPValue *Op, Type *ResultTy)
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.
VPPhi * createScalarPhi(ArrayRef< VPValue * > IncomingValues, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="", const VPIRFlags &Flags={}, Type *ResultTy=nullptr)
VPInstruction * createSelect(VPValue *Cond, VPValue *TrueVal, VPValue *FalseVal, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="", const VPIRFlags &Flags={})
VPExpandSCEVRecipe * createExpandSCEV(const SCEV *Expr)
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)
Create an N-ary operation with Opcode, Operands and set Inst as its underlying Instruction.
static VPSingleDefRecipe * createSingleScalarOp(unsigned Opcode, ArrayRef< VPValue * > Operands, VPValue *Mask, const VPIRFlags &Flags, const VPIRMetadata &Metadata, DebugLoc DL, Instruction *UV)
Create a single-scalar recipe with Opcode and Operands without inserting it.
void setInsertPoint(VPBasicBlock *TheBB)
This specifies that created VPInstructions should be appended to the end of the specified block.
A recipe for generating the phi node tracking the current scalar iteration index.
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.
A recipe for converting the input value IV value to the corresponding value of an IV with different s...
Template specialization of the standard LLVM dominator tree utility for VPBlockBases.
bool properlyDominates(const VPRecipeBase *A, const VPRecipeBase *B) const
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.
A special type of VPBasicBlock that wraps an existing IR basic block.
Class to record and manage LLVM IR flags.
static VPIRFlags getDefaultFlags(unsigned Opcode)
Returns default flags for Opcode for opcodes that support it, asserts otherwise.
LLVM_ABI_FOR_TEST FastMathFlags getFastMathFlagsOrNone() const
void dropPoisonGeneratingFlags()
Drop all poison-generating flags.
static LLVM_ABI_FOR_TEST VPIRInstruction * create(Instruction &I)
Create a new VPIRPhi for \I , if it is a PHINode, otherwise create a VPIRInstruction.
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
@ Unpack
Extracts all lanes from its (non-scalable) vector operand.
@ 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.
@ BuildStructVector
Given operands of (the same) struct type, creates a struct of fixed- width vectors each containing a ...
@ CanonicalIVIncrementForPart
@ ComputeReductionResult
Reduce the operands to the final reduction result using the operation specified via the operation's V...
unsigned getOpcode() const
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.
A recipe for interleaved memory operations with vector-predication intrinsics.
VPInterleaveRecipe is a recipe for transforming an interleave group of load or stores into one wide l...
void addIncoming(VPValue *IncomingV)
Append IncomingV as an incoming value to the phi-like recipe.
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.
VPBasicBlock * getParent()
DebugLoc getDebugLoc() const
Returns the debug location of the recipe.
void moveBefore(VPBasicBlock &BB, iplist< VPRecipeBase >::iterator I)
Unlink this recipe and insert into BB before I.
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.
iplist< VPRecipeBase >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
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...
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.
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 to represent inloop reduction operations with vector-predication intrinsics,...
A recipe for handling reduction phis.
void setVFScaleFactor(unsigned ScaleFactor)
Set the VFScaleFactor for this reduction phi.
unsigned getVFScaleFactor() const
Get the factor that the VF of this recipe's output should be scaled by, or 1 if it isn't scaled.
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...
VPRegionValue * getUsedHeaderMask() const
Return the header mask if it exists and is used, or null otherwise.
VPInstruction * getOrCreateCanonicalIVIncrement()
Get the canonical IV increment instruction if it exists.
void setExiting(VPBlockBase *ExitingBlock)
Set ExitingBlock as the exiting VPBlockBase of this VPRegionBlock.
Type * getCanonicalIVType() const
Return the type of the canonical IV for loop regions.
void clearCanonicalIVNUW(VPInstruction *Increment)
Unsets NUW for the canonical IV increment Increment, for loop regions.
VPRegionValue * getCanonicalIV()
Return the canonical induction variable of the region, null for replicating regions.
const VPBlockBase * getExiting() const
VPBasicBlock * getPreheaderVPBB()
Returns the pre-header VPBasicBlock of the loop region.
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
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 * tryToExpand(const SCEV *S)
Try to 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.
bool isMaterialized() const
Returns true if this value has been materialized.
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 setUnderlyingValue(Value *Val)
VPUser * getSingleUser()
Return the single user of this value, or nullptr if there is not exactly one user.
void replaceAllUsesWith(VPValue *New)
unsigned getNumUsers() const
void replaceUsesWithIf(VPValue *New, llvm::function_ref< bool(VPUser &U, unsigned Idx)> ShouldReplace)
Go through the uses list for this VPValue and make each use point to New if the callback ShouldReplac...
A recipe to compute a pointer to the last element of each part of a widened memory access for widened...
A recipe to compute the pointers for widened memory accesses of SourceElementTy, with the Stride expr...
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.
A Recipe for widening the canonical induction variable of the vector loop.
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),...
VPIRValue * getStartValue() const
Returns the start value of the induction.
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...
VPValue * getSplatVFValue() const
If the recipe has been unrolled, return the VPValue for the induction increment, otherwise return nul...
TruncInst * getTruncInst()
Returns the first defined value as TruncInst, if it is one or nullptr otherwise.
VPValue * getLastUnrolledPartOperand()
Returns the VPValue representing the value of this induction at the last unrolled part,...
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.
VPValue * getOrCreateBackedgeTakenCount()
The backedge taken 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
VPIRValue * getPoison(Type *Ty)
Return a VPIRValue wrapping a poison value of type Ty.
ArrayRef< VPIRBasicBlock * > getExitBlocks() const
Return an ArrayRef containing VPIRBasicBlocks wrapping the exit blocks of the original scalar loop.
VPSymbolicValue & getVectorTripCount()
The vector trip count.
VPValue * getBackedgeTakenCount() const
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.
bool hasScalarTail() const
Returns true if the scalar tail may execute after the vector loop, i.e.
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.
Type * getType() const
All values are typed, get the type of this value.
iterator_range< user_iterator > users()
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
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.multiplyCoefficientBy(X) will result in a value whos...
constexpr ScalarTy getFixedValue() const
constexpr ScalarTy getKnownScalarFactor(const FixedOrScalableQuantity &RHS) const
Returns a value X where RHS.multiplyCoefficientBy(X) will result in a value whose quantity matches ou...
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 LeafTy multiplyCoefficientBy(ScalarTy RHS) const
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.
self_iterator getIterator()
#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.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
std::variant< std::monostate, Loc::Single, Loc::Multi, Loc::MMI, Loc::EntryValue > Variant
Alias for the std::variant specialization base class of DbgVariable.
SpecificConstantMatch m_ZeroInt()
Convenience matchers for specific integer values.
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_isa< To... > m_Isa()
match_combine_or< Ty... > m_CombineOr(const Ty &...Ps)
Combine pattern matchers matching any of Ps patterns.
cst_pred_ty< is_all_ones > m_AllOnes()
Match an integer or vector with all bits set.
auto m_Cmp()
Matches any compare instruction and ignore it.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
match_combine_or< CastInst_match< OpTy, TruncInst >, OpTy > m_TruncOrSelf(const OpTy &Op)
auto m_Poison()
Match an arbitrary poison constant.
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)
match_combine_or< CastInst_match< OpTy, ZExtInst >, OpTy > m_ZExtOrSelf(const OpTy &Op)
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.
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)
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.
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.
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)
FNeg_match< OpTy > m_FNeg(const OpTy &X)
Match 'fneg X' as 'fsub -0.0, X'.
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.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
CastInst_match< OpTy, SExtInst > m_SExt(const OpTy &Op)
Matches SExt.
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.
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()
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.
VPInstruction_match< VPInstruction::StepVector > m_StepVector()
auto m_VPPhi(const Op0_t &Op0, const Op1_t &Op1)
VPInstruction_match< VPInstruction::BranchOnTwoConds > m_BranchOnTwoConds()
AllRecipe_match< Opcode, Op0_t, Op1_t > m_Binary(const Op0_t &Op0, const Op1_t &Op1)
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)
specific_intval< 1 > m_False()
VPInstruction_match< VPInstruction::ExtractLastLane, Op0_t > m_ExtractLastLane(const Op0_t &Op0)
VPInstruction_match< VPInstruction::ActiveLaneMask, Op0_t, Op1_t, Op2_t > m_ActiveLaneMask(const Op0_t &Op0, const Op1_t &Op1, const Op2_t &Op2)
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)
specific_intval< 1 > m_True()
auto m_VPValue()
Match an arbitrary VPValue and ignore it.
VectorEndPointerRecipe_match< Op0_t, Op1_t > m_VecEndPtr(const Op0_t &Op0, const Op1_t &Op1)
VPInstruction_match< VPInstruction::ExtractLastPart, Op0_t > m_ExtractLastPart(const Op0_t &Op0)
VPRecipeBase * findUserOf(VPValue *V, const MatchT &P)
If V is used by a recipe matching pattern P, return it.
VPInstruction_match< VPInstruction::Broadcast, Op0_t > m_Broadcast(const Op0_t &Op0)
header_mask_match m_HeaderMask()
VPInstruction_match< VPInstruction::ExplicitVectorLength, Op0_t > m_EVL(const Op0_t &Op0)
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)
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...
VPValue * getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr)
Get or create a VPValue that corresponds to the expansion of Expr.
bool cannotHoistOrSinkRecipe(const VPRecipeBase &R, bool Sinking=false)
Return true if we do not know how to (mechanically) hoist or sink R.
Intrinsic::ID getIntrinsicID(const Ty *R)
Return the intrinsic ID underlying a call.
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.
VPValue * findIncomingAliasMask(const VPlan &Plan)
Finds the incoming alias-mask within the vector preheader.
VPRecipeBase * findRecipe(VPValue *Start, PredT Pred)
Search Start's users for a recipe satisfying Pred, looking through recipes with definitions.
bool isElementwise(const VPValue *V)
Return true if V is elementwise, i.e. none of the lanes are permuted.
bool onlyScalarValuesUsed(const VPValue *Def)
Returns true if only scalar values of Def are used by all users.
bool isUniformAcrossVFsAndUFs(const VPValue *V)
Checks if V is uniform across all VF lanes and UF parts.
bool isUsedByLoadStoreAddress(const VPValue *V)
Returns true if V is used as part of the address of another load or store.
GEPNoWrapFlags getGEPFlagsForPtr(VPValue *Ptr)
Returns the GEP nowrap flags for Ptr, looking through pointer casts mirroring Value::stripPointerCast...
const SCEV * getSCEVExprForVPValue(const VPValue *V, PredicatedScalarEvolution &PSE, const Loop *L=nullptr)
Return the SCEV expression for V.
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.
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.
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.
constexpr from_range_t from_range
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)
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.
constexpr auto bind_back(FnT &&Fn, BindArgsT &&...BindArgs)
C++23 bind_back.
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)
SmallVector< VPRegisterUsage, 8 > calculateRegisterUsageForPlan(VPlan &Plan, ArrayRef< ElementCount > VFs, const TargetTransformInfo &TTI, const SmallPtrSetImpl< const Value * > &ValuesToIgnore)
Estimate the register usage for Plan and vectorization factors in VFs by calculating the highest numb...
auto map_range(ContainerTy &&C, FuncTy F)
Return a range that applies F to the elements of C.
detail::concat_range< ValueT, RangeTs... > concat(RangeTs &&...Ranges)
Returns a concatenated range across two or more ranges.
uint64_t PowerOf2Ceil(uint64_t A)
Returns the power of two which is greater than or equal to the given value.
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)
bool hasIrregularType(Type *Ty, const DataLayout &DL)
A helper function that returns true if the given type is irregular.
LLVM_ABI_FOR_TEST cl::opt< bool > EnableWideActiveLaneMask
UncountableExitStyle
Different methods of handling early exits.
@ MaskedHandleExitInScalarLoop
All memory operations other than the load(s) required to determine whether an uncountable exit occurr...
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
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 >
auto make_second_range(ContainerTy &&c)
Given a container of pairs, return a range over the second elements.
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
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.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Next
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.
LLVM_ABI std::optional< int64_t > getStrideFromAddRec(const SCEVAddRecExpr *AR, const Loop *Lp, Type *AccessTy, Value *Ptr, PredicatedScalarEvolution &PSE)
If AR is an affine AddRec for Lp with a constant step, return the step in units of AccessTy's allocat...
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...
@ Default
The result value is uniform if and only if all operands are uniform.
constexpr detail::IsaCheckPredicate< Types... > IsaPred
Function object wrapper for the llvm::isa type check.
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
RemoveMask_match(const Op0_t &In, Op1_t &Out)
bool match(OpTy *V) const
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.
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
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 struct that represents some properties of the register usage of a loop.
SmallMapVector< unsigned, unsigned, 4 > MaxLocalUsers
Holds the maximum number of concurrent live intervals in the loop.
InstructionCost spillCost(const TargetTransformInfo &TTI, TargetTransformInfo::TargetCostKind CostKind, unsigned OverrideMaxNumRegs=0) const
Calculate the estimated cost of any spills due to using more registers than the number available for ...
A recipe for widening load operations with vector-predication intrinsics, using the address to load f...
A recipe for widening load operations, using the address to load from and an optional mask.
A recipe for widening store operations with vector-predication intrinsics, using the value to store,...
A recipe for widening store operations, using the stored value, the address to store to and an option...