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);
1123 assert(EndValue &&
"Must have computed the end value up front");
1128 if (Incoming != WideIV)
1140 auto *Zero = Plan.
getZero(StepTy);
1141 return B.createPtrAdd(EndValue,
B.createSub(Zero, Step),
1146 return B.createNaryOp(
1147 ID.getInductionBinOp()->getOpcode() == Instruction::FAdd
1149 : Instruction::FAdd,
1150 {EndValue, Step}, {ID.getInductionBinOp()->getFastMathFlags()});
1161 VPBuilder VectorPHBuilder(VectorPH, VectorPH->begin());
1171 EndValues[WideIV] = EndValue;
1181 R.getVPSingleValue()->replaceAllUsesWith(EndValue);
1182 R.eraseFromParent();
1191 for (
auto [Idx, PredVPBB] :
enumerate(ExitVPBB->getPredecessors())) {
1193 if (PredVPBB == MiddleVPBB)
1195 Plan, ExitIRI->getOperand(Idx), EndValues, PSE);
1198 Plan, ExitIRI->getOperand(Idx), PSE);
1200 ExitIRI->setOperand(Idx, Escape);
1217 const auto &[V, Inserted] = SCEV2VPV.
try_emplace(ExpR->getSCEV(), ExpR);
1221 ExpR->replaceAllUsesWith(V->second);
1225 ExpR->eraseFromParent();
1234 while (!WorkList.
empty()) {
1236 if (!Seen.
insert(Cur).second)
1244 R->eraseFromParent();
1251static std::optional<std::pair<bool, unsigned>>
1254 return std::make_pair(
true, IID);
1256 std::optional<std::pair<bool, unsigned>>>(R)
1259 [](
auto *
I) {
return std::make_pair(
false,
I->getOpcode()); })
1261 return std::make_pair(
false, Instruction::PHI);
1263 .Case<VPVectorPointerRecipe, VPPredInstPHIRecipe, VPScalarIVStepsRecipe>(
1269 I->getVPRecipeID());
1271 .
Default([](
auto *) {
return std::nullopt; });
1296 VPlan &Plan = *R.getParent()->getPlan();
1297 auto FoldToIRValue = [&]() ->
Value * {
1299 if (OpcodeOrIID->first) {
1305 return Folder.FoldIntrinsic(OpcodeOrIID->second,
Ops, R.getScalarType(),
1306 RFlags ? RFlags->getFastMathFlagsOrNone()
1309 unsigned Opcode = OpcodeOrIID->second;
1315 R.getVPSingleValue()->getScalarType());
1318 return Folder.FoldBinOp(Instruction::BinaryOps::Xor,
Ops[0],
1320 case Instruction::Select:
1321 return Folder.FoldSelect(
Ops[0],
Ops[1],
Ops[2]);
1322 case Instruction::ICmp:
1323 case Instruction::FCmp:
1326 case Instruction::GetElementPtr: {
1329 return Folder.FoldGEP(
GEP->getSourceElementType(),
Ops[0],
1339 case Instruction::ExtractElement:
1346 if (
Value *V = FoldToIRValue())
1353 bool CanCreateNewRecipe) {
1354 VPlan *Plan = Def->getParent()->getPlan();
1364 Def->replaceAllUsesWith(
X);
1365 Def->eraseFromParent();
1377 Def->replaceAllUsesWith(
X);
1389 Def->replaceAllUsesWith(Plan->
getZero(Def->getScalarType()));
1395 Def->replaceAllUsesWith(
X);
1401 Def->replaceAllUsesWith(Plan->
getFalse());
1407 Def->replaceAllUsesWith(
X);
1412 if (CanCreateNewRecipe &&
1417 (!Def->getOperand(0)->hasMoreThanOneUniqueUser() ||
1418 !Def->getOperand(1)->hasMoreThanOneUniqueUser())) {
1419 Def->replaceAllUsesWith(
1420 Builder.createLogicalAnd(
X, Builder.createOr(
Y, Z)));
1427 Def->replaceAllUsesWith(Def->getOperand(1));
1434 Def->replaceAllUsesWith(Builder.createLogicalAnd(
X,
Y));
1440 Def->replaceAllUsesWith(Plan->
getFalse());
1445 Def->replaceAllUsesWith(
X);
1451 if (CanCreateNewRecipe &&
1453 Def->replaceAllUsesWith(Builder.createNot(
C));
1459 Def->setOperand(0,
C);
1460 Def->setOperand(1,
Y);
1461 Def->setOperand(2,
X);
1466 if (CanCreateNewRecipe &&
1470 Y->getScalarType()->isIntegerTy(1)) {
1471 Def->replaceAllUsesWith(
1472 Builder.createOr(
Y, Builder.createLogicalAnd(
X, Z)));
1481 VPlan *Plan = Def->getParent()->getPlan();
1487 return Def->replaceAllUsesWith(V);
1493 PredPHI->replaceAllUsesWith(
Op);
1501 RepR && RepR->isPredicated() && RepR->getOpcode() == Instruction::Store &&
1505 RepR->getUnderlyingInstr(), RepR->operandsWithoutMask(),
1506 RepR->isSingleScalar(),
nullptr, *RepR, *RepR,
1507 RepR->getDebugLoc());
1508 Unmasked->insertBefore(RepR);
1509 RepR->replaceAllUsesWith(Unmasked);
1510 RepR->eraseFromParent();
1524 bool CanCreateNewRecipe =
1529 Type *TruncTy = Def->getScalarType();
1530 Type *ATy =
A->getScalarType();
1531 if (TruncTy == ATy) {
1532 Def->replaceAllUsesWith(
A);
1541 : Instruction::ZExt;
1544 if (
auto *UnderlyingExt = Def->getOperand(0)->getUnderlyingValue()) {
1546 Ext->setUnderlyingValue(UnderlyingExt);
1548 Def->replaceAllUsesWith(Ext);
1550 auto *Trunc = Builder.createWidenCast(Instruction::Trunc,
A, TruncTy);
1551 Def->replaceAllUsesWith(Trunc);
1561 return Def->replaceAllUsesWith(
A);
1564 return Def->replaceAllUsesWith(
A);
1567 return Def->replaceAllUsesWith(Plan->
getZero(Def->getScalarType()));
1573 return Def->replaceAllUsesWith(Builder.createSub(
1574 Plan->
getZero(
A->getScalarType()),
A, Def->getDebugLoc(),
"", NW));
1577 if (CanCreateNewRecipe &&
1585 ->hasNoSignedWrap()};
1586 return Def->replaceAllUsesWith(
1587 Builder.createSub(
X,
Y, Def->getDebugLoc(),
"", NW));
1596 MulR->hasNoSignedWrap() &&
1598 return Def->replaceAllUsesWith(Builder.createNaryOp(
1600 {A, Plan->getConstantInt(APC->getBitWidth(), ShiftAmt)}, NW,
1601 Def->getDebugLoc()));
1606 return Def->replaceAllUsesWith(Builder.createNaryOp(
1608 {A, Plan->getConstantInt(APC->getBitWidth(), APC->exactLogBase2())},
1613 return Def->replaceAllUsesWith(
A);
1628 R->setOperand(1,
Y);
1629 R->setOperand(2,
X);
1633 R->replaceAllUsesWith(Cmp);
1638 if (!Cmp->getDebugLoc() && Def->getDebugLoc())
1639 Cmp->setDebugLoc(Def->getDebugLoc());
1651 if (
Op->getNumUsers() > 1 ||
1655 }
else if (!UnpairedCmp) {
1656 UnpairedCmp =
Op->getDefiningRecipe();
1660 UnpairedCmp =
nullptr;
1667 if (NewOps.
size() < Def->getNumOperands()) {
1669 return Def->replaceAllUsesWith(NewAnyOf);
1676 if (CanCreateNewRecipe &&
1682 return Def->replaceAllUsesWith(NewCmp);
1688 Def->getOperand(1)->getScalarType() == Def->getScalarType())
1689 return Def->replaceAllUsesWith(Def->getOperand(1));
1693 Type *WideStepTy = Def->getScalarType();
1694 if (
X->getScalarType() != WideStepTy)
1695 X = Builder.createWidenCast(Instruction::Trunc,
X, WideStepTy);
1696 Def->replaceAllUsesWith(
X);
1705 Def->getScalarType()->isIntegerTy(1)) {
1706 Def->setOperand(1, Def->getOperand(0));
1707 Def->setOperand(0,
Y);
1714 return Def->replaceAllUsesWith(Def->getOperand(0));
1720 Def->replaceAllUsesWith(
1721 BuildVector->getOperand(BuildVector->getNumOperands() - 1));
1726 return Def->replaceAllUsesWith(
X);
1729 return Def->replaceAllUsesWith(
A);
1732 return Def->replaceAllUsesWith(
A);
1738 Def->replaceAllUsesWith(
1739 BuildVector->getOperand(BuildVector->getNumOperands() - 2));
1746 Def->replaceAllUsesWith(BuildVector->getOperand(Idx));
1751 Def->replaceAllUsesWith(
1759 Def->replaceUsesWithIf(Def->getOperand(0), [Def](
VPUser &U,
unsigned) {
1760 return U.usesFirstLaneOnly(Def);
1769 "broadcast operand must be single-scalar");
1770 Def->setOperand(0,
C);
1775 return Def->replaceUsesWithIf(
1776 X, [Def](
const VPUser &U,
unsigned) {
return U.usesScalars(Def); });
1779 if (Def->getNumOperands() == 1) {
1780 Def->replaceAllUsesWith(Def->getOperand(0));
1785 Phi->replaceAllUsesWith(Phi->getOperand(0));
1791 if (Def->getNumOperands() == 1 &&
1793 return Def->replaceAllUsesWith(IRV);
1806 return Def->replaceAllUsesWith(
A);
1813 return Def->replaceAllUsesWith(WidenIV->getRegion()->getCanonicalIV());
1816 Def->replaceAllUsesWith(Builder.createNaryOp(
1817 Instruction::ExtractElement, {A, LaneToExtract}, Def->getDebugLoc()));
1831 auto *IVInc = Def->getOperand(0);
1832 if (IVInc->getNumUsers() == 2) {
1837 if (Phi->getNumUsers() == 1 || (Phi->getNumUsers() == 2 && Inc)) {
1838 Def->replaceAllUsesWith(IVInc);
1840 Inc->replaceAllUsesWith(Phi);
1841 Phi->setOperand(0,
Y);
1857 Steps->replaceAllUsesWith(Steps->getOperand(0));
1865 Def->replaceUsesWithIf(StartV, [](
const VPUser &U,
unsigned Idx) {
1867 return PhiR && PhiR->isInLoop();
1873 return Def->replaceAllUsesWith(
A);
1889template <
typename Match_t,
typename Builder>
1910 for (
unsigned I = 0;
I < Def->getNumOperands();
I++)
1912 Def->setOperand(
I,
X);
1916 Def->replaceUsesWithIf(
1917 Res, [&Res](
VPUser &U,
unsigned _) {
return &U != Res; });
1935 R.getVPSingleValue()->replaceAllUsesWith(
X);
1951 while (!Worklist.
empty()) {
1960 R->replaceAllUsesWith(
1961 Builder.createLogicalAnd(HeaderMask, Builder.createLogicalAnd(
X,
Y)));
1965static std::optional<Instruction::BinaryOps>
1968 case Intrinsic::masked_udiv:
1969 return Instruction::UDiv;
1970 case Intrinsic::masked_sdiv:
1971 return Instruction::SDiv;
1972 case Intrinsic::masked_urem:
1973 return Instruction::URem;
1974 case Intrinsic::masked_srem:
1975 return Instruction::SRem;
1992 if (RepR && (RepR->isSingleScalar() || RepR->isPredicated()))
1996 if (RepR && RepR->getOpcode() == Instruction::Store &&
1999 RepOrWidenR->getUnderlyingInstr(), RepOrWidenR->operands(),
2000 true ,
nullptr , *RepR ,
2001 *RepR , RepR->getDebugLoc());
2002 Clone->insertBefore(RepOrWidenR);
2004 VPValue *ExtractOp = Clone->getOperand(0);
2010 Clone->setOperand(0, ExtractOp);
2011 RepR->eraseFromParent();
2023 VPValue *SafeDivisor = Builder.createSelect(
2024 IntrR->getOperand(2), IntrR->getOperand(1),
2026 VPValue *Clone = Builder.createNaryOp(
2027 *
Opc, {IntrR->getOperand(0), SafeDivisor},
2030 IntrR->eraseFromParent();
2039 auto IntroducesBCastOf = [](
const VPValue *
Op) {
2048 return !U->usesScalars(
Op);
2052 if (
any_of(RepOrWidenR->users(), IntroducesBCastOf(RepOrWidenR)) &&
2055 make_filter_range(Op->users(), not_equal_to(RepOrWidenR)),
2056 IntroducesBCastOf(Op)))
2060 bool LiveInNeedsBroadcast =
2061 isa<VPIRValue>(Op) && !isa<VPConstant>(Op);
2062 auto *OpR = dyn_cast<VPReplicateRecipe>(Op);
2063 return LiveInNeedsBroadcast || (OpR && OpR->isSingleScalar());
2070 RepOrWidenR->getUnderlyingInstr());
2071 Clone->insertBefore(RepOrWidenR);
2072 RepOrWidenR->replaceAllUsesWith(Clone);
2074 RepOrWidenR->eraseFromParent();
2110 if (Blend->isNormalized() || !
match(Blend->getMask(0),
m_False()))
2111 UniqueValues.
insert(Blend->getIncomingValue(0));
2112 for (
unsigned I = 1;
I != Blend->getNumIncomingValues(); ++
I)
2114 UniqueValues.
insert(Blend->getIncomingValue(
I));
2116 if (UniqueValues.
size() == 1) {
2117 Blend->replaceAllUsesWith(*UniqueValues.
begin());
2118 Blend->eraseFromParent();
2122 if (Blend->isNormalized())
2128 unsigned StartIndex = 0;
2129 for (
unsigned I = 0;
I != Blend->getNumIncomingValues(); ++
I) {
2141 OperandsWithMask.
push_back(Blend->getIncomingValue(StartIndex));
2143 for (
unsigned I = 0;
I != Blend->getNumIncomingValues(); ++
I) {
2144 if (
I == StartIndex)
2146 OperandsWithMask.
push_back(Blend->getIncomingValue(
I));
2147 OperandsWithMask.
push_back(Blend->getMask(
I));
2152 OperandsWithMask, *Blend, Blend->getDebugLoc());
2153 NewBlend->insertBefore(&R);
2155 VPValue *DeadMask = Blend->getMask(StartIndex);
2157 Blend->eraseFromParent();
2162 if (NewBlend->getNumOperands() == 3 &&
2164 VPValue *Inc0 = NewBlend->getOperand(0);
2165 VPValue *Inc1 = NewBlend->getOperand(1);
2166 VPValue *OldMask = NewBlend->getOperand(2);
2167 NewBlend->setOperand(0, Inc1);
2168 NewBlend->setOperand(1, Inc0);
2169 NewBlend->setOperand(2, NewMask);
2196 APInt MaxVal = AlignedTC - 1;
2199 unsigned NewBitWidth =
2205 bool MadeChange =
false;
2230 "canonical IV is not expected to have a truncation");
2235 NewWideIV->insertBefore(WideIV);
2242 Cmp->replaceAllUsesWith(
2243 VPBuilder(Cmp).createICmp(Cmp->getPredicate(), NewWideIV, NewBTC));
2257 return any_of(
Cond->getDefiningRecipe()->operands(), [&Plan, BestVF, BestUF,
2259 return isConditionTrueViaVFAndUF(C, Plan, BestVF, BestUF, PSE);
2273 const SCEV *VectorTripCount =
2278 "Trip count SCEV must be computable");
2299 auto *Term = &ExitingVPBB->
back();
2312 for (
unsigned Part = 0; Part < UF; ++Part) {
2318 Extracts[Part] = Ext;
2330 match(Phi->getBackedgeValue(),
2332 assert(Index &&
"Expected index from ActiveLaneMask instruction");
2349 "Expected one VPActiveLaneMaskPHIRecipe for each unroll part");
2356 "Expected incoming values of Phi to be ActiveLaneMasks");
2361 EntryALM->setOperand(2, ALMMultiplier);
2362 LoopALM->setOperand(2, ALMMultiplier);
2366 ExtractFromALM(EntryALM, EntryExtracts);
2371 ExtractFromALM(LoopALM, LoopExtracts);
2373 Not->setOperand(0, LoopExtracts[0]);
2376 for (
unsigned Part = 0; Part < UF; ++Part) {
2377 Phis[Part]->setStartValue(EntryExtracts[Part]);
2378 Phis[Part]->setBackedgeValue(LoopExtracts[Part]);
2391 auto *Term = &ExitingVPBB->
back();
2403 const SCEV *VectorTripCount =
2409 "Trip count SCEV must be computable");
2428 Term->setOperand(1, Plan.
getTrue());
2433 {}, Term->getDebugLoc());
2435 Term->eraseFromParent();
2468 R.getVPSingleValue()->replaceAllUsesWith(Trunc);
2478 assert(Plan.
hasVF(BestVF) &&
"BestVF is not available in Plan");
2479 assert(Plan.
hasUF(BestUF) &&
"BestUF is not available in Plan");
2497 RecurKind RK = PhiR->getRecurrenceKind();
2504 RecWithFlags->dropPoisonGeneratingFlags();
2510struct VPCSEDenseMapInfo :
public DenseMapInfo<VPSingleDefRecipe *> {
2519 return GEP->getSourceElementType();
2522 .Case<VPVectorPointerRecipe, VPWidenGEPRecipe>(
2523 [](
auto *
I) {
return I->getSourceElementType(); })
2524 .
Default([](
auto *) {
return nullptr; });
2528 static bool canHandle(
const VPSingleDefRecipe *Def) {
2537 if (!
C || (!
C->first && (
C->second == Instruction::InsertValue ||
2538 C->second == Instruction::ExtractValue)))
2542 return !
Def->mayReadOrWriteMemory();
2546 static unsigned getHashValue(
const VPSingleDefRecipe *Def) {
2549 getGEPSourceElementType(Def),
Def->getScalarType(),
2552 if (RFlags->hasPredicate())
2555 return hash_combine(Result, SIVSteps->getInductionOpcode());
2560 static bool isEqual(
const VPSingleDefRecipe *L,
const VPSingleDefRecipe *R) {
2561 if (
L->getVPRecipeID() !=
R->getVPRecipeID() ||
2563 getGEPSourceElementType(L) != getGEPSourceElementType(R) ||
2565 !
equal(
L->operands(),
R->operands()))
2568 "must have valid opcode info for both recipes");
2570 if (LFlags->hasPredicate() &&
2571 LFlags->getPredicate() !=
2575 if (LSIV->getInductionOpcode() !=
2585 const VPRegionBlock *RegionL =
L->getRegion();
2586 const VPRegionBlock *RegionR =
R->getRegion();
2589 L->getParent() !=
R->getParent())
2591 return L->getScalarType() ==
R->getScalarType();
2607 if (!Def || !VPCSEDenseMapInfo::canHandle(Def))
2611 if (!VPDT.
dominates(V->getParent(), VPBB))
2616 Def->replaceAllUsesWith(V);
2629 bool Sinking =
false) {
2658 "Expected vector prehader's successor to be the vector loop region");
2666 return !Op->isDefinedOutsideLoopRegions();
2669 R.moveBefore(*Preheader, Preheader->
end());
2689 assert(!RepR->isPredicated() &&
2690 "Expected prior transformation of predicated replicates to "
2691 "replicate regions");
2696 if (!RepR->isSingleScalar())
2700 if (RepR->getOpcode() == Instruction::Store &&
2701 !RepR->getOperand(1)->isDefinedOutsideLoopRegions())
2706 assert((!R.mayWriteToMemory() ||
2707 (RepR && RepR->getOpcode() == Instruction::Store &&
2708 RepR->getOperand(1)->isDefinedOutsideLoopRegions())) &&
2709 "The only recipes that may write to memory are expected to be "
2710 "stores with invariant pointer-operand");
2720 if (
any_of(Def->users(), [&SinkBB, &LoopRegion](
VPUser *U) {
2721 auto *UserR = cast<VPRecipeBase>(U);
2722 VPBasicBlock *Parent = UserR->getParent();
2724 if (SinkBB && SinkBB != Parent)
2729 return UserR->isPhi() || Parent->getEnclosingLoopRegion() ||
2730 Parent->getSinglePredecessor() != LoopRegion;
2740 "Defining block must dominate sink block");
2765 VPValue *ResultVPV = R.getVPSingleValue();
2767 unsigned NewResSizeInBits = MinBWs.
lookup(UI);
2768 if (!NewResSizeInBits)
2781 (void)OldResSizeInBits;
2789 VPW->dropPoisonGeneratingFlags();
2791 assert((OldResSizeInBits != NewResSizeInBits ||
2793 "Only ICmps should not need extending the result.");
2799 if (OldResSizeInBits != NewResSizeInBits) {
2801 Instruction::ZExt, ResultVPV, OldResTy);
2803 Ext->setOperand(0, ResultVPV);
2813 unsigned OpSizeInBits =
Op->getScalarType()->getScalarSizeInBits();
2814 if (OpSizeInBits == NewResSizeInBits)
2816 assert(OpSizeInBits > NewResSizeInBits &&
"nothing to truncate");
2817 auto [ProcessedIter, Inserted] = ProcessedTruncs.
try_emplace(
Op);
2823 Builder.setInsertPoint(&R);
2824 ProcessedIter->second =
2825 Builder.createWidenCast(Instruction::Trunc,
Op, NewResTy);
2827 Op = ProcessedIter->second;
2831 NWR->insertBefore(&R);
2835 VPValue *Replacement = NWR->getVPSingleValue();
2836 if (OldResSizeInBits != NewResSizeInBits)
2842 R.eraseFromParent();
2848 std::optional<VPDominatorTree> VPDT;
2856 bool SimplifiedPhi =
false;
2866 assert(VPBB->getNumSuccessors() == 2 &&
2867 "Two successors expected for BranchOnCond");
2868 unsigned RemovedIdx;
2879 "There must be a single edge between VPBB and its successor");
2882 auto Phis = RemovedSucc->
phis();
2885 SimplifiedPhi |= !std::empty(Phis);
2889 VPBB->back().eraseFromParent();
2901 if (Reachable.contains(
B))
2912 for (
VPValue *Def : R.definedValues())
2913 Def->replaceAllUsesWith(&Tmp);
2914 R.eraseFromParent();
2918 return SimplifiedPhi;
2973 DebugLoc DL = CanonicalIVIncrement->getDebugLoc();
2984 auto *EntryIncrement =
2986 {StartV, VF}, {},
DL,
"index.part.next");
2992 {EntryIncrement, TC, ALMMultiplier},
DL,
2993 "active.lane.mask.entry");
3000 LaneMaskPhi->insertBefore(*HeaderVPBB, HeaderVPBB->begin());
3005 Builder.setInsertPoint(OriginalTerminator);
3006 auto *InLoopIncrement = Builder.createOverflowingOp(
3008 {CanonicalIVIncrement, &Plan.
getVF()}, {},
DL);
3010 {InLoopIncrement, TC, ALMMultiplier},
DL,
3011 "active.lane.mask.next");
3012 LaneMaskPhi->addBackedgeValue(ALM);
3016 auto *NotMask = Builder.createNot(ALM,
DL);
3023 VPlan &Plan,
bool UseActiveLaneMask,
bool UseActiveLaneMaskForControlFlow) {
3029 if (UseActiveLaneMaskForControlFlow) {
3035 VPBuilder Builder(Header, Header->getFirstNonPhi());
3040 if (UseActiveLaneMask) {
3043 Mask = Builder.createNaryOp(
3045 {WideCanonicalIV, Plan.
getTripCount(), ALMMultiplier},
nullptr,
3046 "active.lane.mask");
3071template <
typename Op0_t,
typename Op1_t>
3079 case Intrinsic::masked_udiv:
3080 return Intrinsic::vp_udiv;
3081 case Intrinsic::masked_sdiv:
3082 return Intrinsic::vp_sdiv;
3083 case Intrinsic::masked_urem:
3084 return Intrinsic::vp_urem;
3085 case Intrinsic::masked_srem:
3086 return Intrinsic::vp_srem;
3088 return std::nullopt;
3103 VPValue *Addr, *Mask, *EndPtr;
3106 auto AdjustEndPtr = [&CurRecipe, &EVL](
VPValue *EndPtr) {
3108 EVLEndPtr->insertBefore(&CurRecipe);
3113 EVLEndPtr->setOperand(1, EVLAsVF);
3117 auto GetVPReverse = [&CurRecipe, &EVL, Plan,
3122 Intrinsic::experimental_vp_reverse, {V, Plan->
getTrue(), &EVL},
3123 V->getScalarType(), {}, {},
DL);
3124 Reverse->insertBefore(&CurRecipe);
3128 if (
match(&CurRecipe,
3133 if (
match(&CurRecipe,
3137 Mask = GetVPReverse(Mask);
3138 Addr = AdjustEndPtr(EndPtr);
3141 LoadR->insertBefore(&CurRecipe);
3145 LoadR->getScalarType(), {}, {},
DL);
3156 NewLoad->setOperand(2, Mask);
3157 NewLoad->setOperand(3, &EVL);
3165 StoredVal, EVL, Mask);
3167 if (
match(&CurRecipe,
3171 Mask = GetVPReverse(Mask);
3172 Addr = AdjustEndPtr(EndPtr);
3175 Intrinsic::vector_splice_right, {StoredVal,
Poison, &EVL},
3179 SpliceR, EVL, Mask);
3183 if (Rdx->isConditional() &&
3188 if (Interleave->getMask() &&
3196 Intrinsic::vp_merge, {Mask ? Mask : Plan->
getTrue(),
LHS,
RHS, &EVL},
3197 LHS->getScalarType(), {}, {},
DL);
3210 if (
match(&CurRecipe,
3215 LHS->getScalarType(), {}, {},
DL);
3221 {IntrR->getOperand(0),
3222 IntrR->getOperand(1),
3223 Mask ? Mask : Plan->
getTrue(), &EVL},
3224 IntrR->getScalarType(), {}, {},
DL);
3233 VPValue *HeaderMask =
nullptr, *EVL =
nullptr;
3238 HeaderMask = R.getVPSingleValue();
3249 NewR->insertBefore(R);
3250 for (
auto [Old, New] :
3251 zip_equal(R->definedValues(), NewR->definedValues()))
3252 Old->replaceAllUsesWith(New);
3265 Mask->getScalarType(), {}, {}, LogicalAnd->getDebugLoc());
3266 Merge->insertBefore(LogicalAnd);
3267 LogicalAnd->replaceAllUsesWith(
Merge);
3277 [&EVL](
const auto &
X) {
3281 [&Plan, &EVL](
auto *
X) {
3283 Intrinsic::vector_splice_left,
3284 {Plan.
getPoison(
X->getScalarType()),
X, EVL},
X->getScalarType(),
3285 {}, {},
X->getDebugLoc());
3296 R->getVPSingleValue()->getNumUsers() == 0) {
3306 R->getVPSingleValue()->replaceAllUsesWith(
X);
3320 Intrinsic::experimental_vp_reverse, {
X, Plan.
getTrue(), EVL},
3321 X->getScalarType(), {}, {}, R->getDebugLoc());
3322 VPReverse->insertBefore(R);
3323 R->getVPSingleValue()->replaceAllUsesWith(VPReverse);
3329 R->eraseFromParent();
3350 auto IsAllowedUser =
3351 IsaPred<VPVectorEndPointerRecipe, VPScalarIVStepsRecipe,
3352 VPWidenIntOrFpInductionRecipe,
3353 VPWidenMemIntrinsicRecipe>;
3354 if (match(U, m_Trunc(m_Specific(&Plan.getVF()))))
3355 return all_of(cast<VPSingleDefRecipe>(U)->users(),
3357 return IsAllowedUser(U);
3359 "User of VF that we can't transform to EVL.");
3369 "Only users of VFxUF should be VPWidenPointerInductionRecipe and the "
3370 "increment of the canonical induction.");
3386 MaxEVL = Builder.createScalarZExtOrTrunc(
3390 Builder.setInsertPoint(Header, Header->getFirstNonPhi());
3391 VPValue *PrevEVL = Builder.createScalarPhi(
3405 Intrinsic::experimental_vp_splice,
3406 {
V1, V2, Imm, Plan.
getTrue(), PrevEVL, &EVL},
3407 R.getVPSingleValue()->getScalarType(), {}, {}, R.getDebugLoc());
3409 R.getVPSingleValue()->replaceAllUsesWith(VPSplice);
3422 if (match(&R, m_ComputeReductionResult(m_Select(m_Specific(HeaderMask),
3423 m_VPValue(), m_VPValue()))))
3424 return R.getOperand(0)->getDefiningRecipe()->getRegion() ==
3425 Plan.getVectorLoopRegion();
3434 VPValue *EVLMask = Builder.createICmp(
3494 VPlan &Plan,
const std::optional<unsigned> &MaxSafeElements) {
3506 auto *CurrentIteration =
3508 CurrentIteration->insertBefore(*Header, Header->begin());
3509 VPBuilder Builder(Header, Header->getFirstNonPhi());
3512 VPPhi *AVLPhi = Builder.createScalarPhi(
3516 if (MaxSafeElements) {
3526 Builder.setInsertPoint(CanonicalIVIncrement);
3530 OpVPEVL = Builder.createScalarZExtOrTrunc(
3531 OpVPEVL, CanIVTy, I32Ty, CanonicalIVIncrement->getDebugLoc());
3533 auto *NextIter = Builder.createAdd(
3534 OpVPEVL, CurrentIteration, CanonicalIVIncrement->getDebugLoc(),
3535 "current.iteration.next", CanonicalIVIncrement->getNoWrapFlags());
3536 CurrentIteration->addBackedgeValue(NextIter);
3540 "avl.next", {
true,
false});
3548 CanonicalIV->replaceUsesWithIf(CurrentIteration,
3549 [CanonicalIVIncrement](
VPUser &U,
unsigned) {
3550 return &U != CanonicalIVIncrement;
3565 assert(!CurrentIteration &&
3566 "Found multiple CurrentIteration. Only one expected");
3567 CurrentIteration = PhiR;
3571 if (!CurrentIteration)
3582 CurrentIteration->
getDebugLoc(),
"current.iteration.iv");
3591 CanIVInc->eraseFromParent();
3600 if (Header->empty())
3609 if (!
match(EVLPhi->getBackedgeValue(),
3622 [[maybe_unused]]
bool FoundAVLNext =
3625 assert(FoundAVLNext &&
"Didn't find AVL backedge?");
3633 [[maybe_unused]]
bool FoundIncrement =
match(
3640 "Expected BranchOnCond with ICmp comparing CanIV + VFxUF with vector "
3645 LatchBr->setOperand(
3657 "expected to run before loop regions are created");
3659 auto CanUseVersionedStride = [&VPDT, Preheader](
VPUser &U,
unsigned) {
3662 return VPDT.
dominates(Preheader, Parent);
3665 for (
const SCEV *Stride : StridesMap.
values()) {
3668 const APInt *StrideConst;
3691 RewriteMap[StrideV] = PSE.
getSCEV(StrideV);
3698 const SCEV *ScevExpr = ExpSCEV->getSCEV();
3701 if (NewSCEV != ScevExpr) {
3703 ExpSCEV->replaceAllUsesWith(NewExp);
3714 auto CollectPoisonGeneratingInstrsInBackwardSlice([&](
VPRecipeBase *Root) {
3719 while (!Worklist.
empty()) {
3722 if (!Visited.
insert(CurRec).second)
3744 RecWithFlags->isDisjoint()) {
3747 Builder.createAdd(
A,
B, RecWithFlags->getDebugLoc());
3748 New->setUnderlyingValue(RecWithFlags->getUnderlyingValue());
3749 RecWithFlags->replaceAllUsesWith(New);
3750 RecWithFlags->eraseFromParent();
3753 RecWithFlags->dropPoisonGeneratingFlags();
3758 assert((!Instr || !Instr->hasPoisonGeneratingFlags()) &&
3759 "found instruction with poison generating flags not covered by "
3760 "VPRecipeWithIRFlags");
3765 if (
VPRecipeBase *OpDef = Operand->getDefiningRecipe())
3776 auto IsNotHeaderMask = [](
VPValue *Mask) {
3789 VPRecipeBase *AddrDef = WidenRec->getAddr()->getDefiningRecipe();
3790 if (AddrDef && WidenRec->isConsecutive() &&
3791 IsNotHeaderMask(WidenRec->getMask()))
3792 CollectPoisonGeneratingInstrsInBackwardSlice(AddrDef);
3794 VPRecipeBase *AddrDef = InterleaveRec->getAddr()->getDefiningRecipe();
3795 if (AddrDef && IsNotHeaderMask(InterleaveRec->getMask()))
3796 CollectPoisonGeneratingInstrsInBackwardSlice(AddrDef);
3806 const bool &EpilogueAllowed) {
3807 if (InterleaveGroups.empty())
3818 IRMemberToRecipe[&MemR->getIngredient()] = MemR;
3825 for (
const auto *IG : InterleaveGroups) {
3828 for (
auto *Member : IG->members())
3830 StartMember = Member;
3838 for (
unsigned I = 0;
I < IG->getFactor(); ++
I) {
3844 StoredValues.
push_back(StoreR->getStoredValue());
3851 bool NeedsMaskForGaps =
3852 (IG->requiresScalarEpilogue() && !EpilogueAllowed) ||
3853 (!StoredValues.
empty() && !IG->isFull());
3856 auto *InsertPos = IRMemberToRecipe.
lookup(IRInsertPos);
3860 "Dead member in non-load group?");
3865 InsertPos->getAsRecipe()))
3866 InsertPos = MemberR;
3867 IRInsertPos = &InsertPos->getIngredient();
3877 VPValue *Addr = Start->getAddr();
3879 if (IG->getIndex(StartMember) != 0 ||
3887 assert(IG->getIndex(IRInsertPos) != 0 &&
3888 "index of insert position shouldn't be zero");
3892 IG->getIndex(IRInsertPos),
3896 Addr =
B.createNoWrapPtrAdd(InsertPos->getAddr(), OffsetVPV, NW);
3902 if (IG->isReverse()) {
3905 -(int64_t)IG->getFactor(), NW, InsertPosR->
getDebugLoc());
3906 ReversePtr->insertBefore(InsertPosR);
3910 IG, Addr, StoredValues, InsertPos->getMask(), NeedsMaskForGaps,
3912 VPIG->insertBefore(InsertPosR);
3915 for (
unsigned i = 0; i < IG->getFactor(); ++i)
3918 if (!Member->getType()->isVoidTy()) {
3979 AddOp = Instruction::Add;
3980 MulOp = Instruction::Mul;
3982 AddOp =
ID.getInductionOpcode();
3983 MulOp = Instruction::FMul;
3991 Step = Builder.createScalarCast(Instruction::Trunc, Step, Ty,
DL);
3992 Start = Builder.createScalarCast(Instruction::Trunc, Start, Ty,
DL);
4001 Init = Builder.createWidenCast(Instruction::UIToFP,
Init, StepTy);
4006 Init = Builder.createNaryOp(MulOp, {
Init, SplatStep}, Flags);
4007 Init = Builder.createNaryOp(AddOp, {SplatStart,
Init}, Flags,
4025 if (R->getParent()->getEnclosingLoopRegion())
4026 Builder.setInsertPoint(R->getParent(), std::next(R->getIterator()));
4031 VF = Builder.createScalarCast(Instruction::CastOps::UIToFP, VF, StepTy,
4034 VF = Builder.createScalarZExtOrTrunc(VF, StepTy, VF->
getScalarType(),
DL);
4036 Inc = Builder.createNaryOp(MulOp, {Step, VF}, Flags);
4043 auto *
Next = Builder.createNaryOp(AddOp, {Prev, Inc}, Flags,
4046 WidePHI->addIncoming(
Next);
4073 VPlan *Plan = R->getParent()->getPlan();
4074 VPValue *Start = R->getStartValue();
4075 VPValue *Step = R->getStepValue();
4076 VPValue *VF = R->getVFValue();
4078 assert(R->getInductionDescriptor().getKind() ==
4080 "Not a pointer induction according to InductionDescriptor!");
4081 assert(R->getScalarType()->isPointerTy() &&
"Unexpected type.");
4083 "Recipe should have been replaced");
4089 VPPhi *ScalarPtrPhi = Builder.createScalarPhi(Start,
DL,
"pointer.phi");
4093 Builder.setInsertPoint(R->getParent(), R->getParent()->getFirstNonPhi());
4096 Offset = Builder.createOverflowingOp(Instruction::Mul, {
Offset, Step});
4098 Builder.createWidePtrAdd(ScalarPtrPhi,
Offset,
DL,
"vector.gep");
4099 R->replaceAllUsesWith(PtrAdd);
4104 VF = Builder.createScalarZExtOrTrunc(VF, StepTy, VF->
getScalarType(),
DL);
4105 VPValue *Inc = Builder.createOverflowingOp(Instruction::Mul, {Step, VF});
4108 Builder.createPtrAdd(ScalarPtrPhi, Inc,
DL,
"ptr.ind");
4115 VPValue *Start = R->getStartValue();
4116 VPValue *Step = R->getStepValue();
4117 VPValue *Index = R->getIndex();
4121 ? Builder.createScalarSExtOrTrunc(
4123 : Builder.createScalarCast(Instruction::SIToFP, Index, StepTy,
4125 switch (R->getInductionKind()) {
4127 assert(Index->getScalarType() == Start->getScalarType() &&
4128 "Index type does not match StartValue type");
4129 return R->replaceAllUsesWith(Builder.createAdd(
4130 Start, Builder.createOverflowingOp(Instruction::Mul, {Index, Step})));
4133 return R->replaceAllUsesWith(Builder.createPtrAdd(
4134 Start, Builder.createOverflowingOp(Instruction::Mul, {Index, Step})));
4139 (FPBinOp->
getOpcode() == Instruction::FAdd ||
4140 FPBinOp->
getOpcode() == Instruction::FSub) &&
4141 "Original BinOp should be defined for FP induction");
4143 VPValue *
FMul = Builder.createNaryOp(Instruction::FMul, {Step, Index}, FMF);
4144 return R->replaceAllUsesWith(
4145 Builder.createNaryOp(FPBinOp->
getOpcode(), {Start, FMul}, FMF));
4158 if (!R->isReplicator())
4162 R->dissolveToCFGLoop();
4183 assert(Br->getNumOperands() == 2 &&
4184 "BranchOnTwoConds must have exactly 2 conditions");
4188 assert(Successors.size() == 3 &&
4189 "BranchOnTwoConds must have exactly 3 successors");
4194 VPValue *Cond0 = Br->getOperand(0);
4195 VPValue *Cond1 = Br->getOperand(1);
4202 if (Succ0 == Succ1) {
4204 VPValue *Combined = Builder.createOr(Cond0, Cond1,
DL);
4208 Br->eraseFromParent();
4213 !BrOnTwoCondsBB->
getParent() &&
"regions must already be dissolved");
4226 Br->eraseFromParent();
4237 WidenIVR->eraseFromParent();
4247 WidenIVR->replaceAllUsesWith(PtrAdd);
4248 WidenIVR->eraseFromParent();
4252 WidenIVR->eraseFromParent();
4258 DerivedIVR->eraseFromParent();
4263 VPValue *CanIV = WideCanIV->getCanonicalIV();
4265 VPValue *Step = WideCanIV->getStepValue();
4268 "Expected unroller to have materialized step for UF != 1");
4273 Step = Builder.createAdd(
4276 Builder.createAdd(CanIV, Step, WideCanIV->getDebugLoc(),
"vec.iv",
4277 WideCanIV->getNoWrapFlags());
4279 WideCanIV->eraseFromParent();
4286 for (
unsigned I = 1;
I != Blend->getNumIncomingValues(); ++
I)
4287 Select = Builder.createSelect(Blend->getMask(
I),
4288 Blend->getIncomingValue(
I),
Select,
4289 R.getDebugLoc(),
"predphi", *Blend);
4290 Blend->replaceAllUsesWith(
Select);
4291 Blend->eraseFromParent();
4296 if (!VEPR->getOffset()) {
4298 "Expected unroller to have materialized offset for UF != 1");
4299 VEPR->materializeOffset();
4306 Expr->eraseFromParent();
4316 for (
VPValue *
Op : LastActiveL->operands()) {
4317 VPValue *NotMask = Builder.createNot(
Op, LastActiveL->getDebugLoc());
4322 VPValue *FirstInactiveLane = Builder.createFirstActiveLane(
4323 NotMasks, LastActiveL->getDebugLoc(),
"first.inactive.lane");
4329 Builder.createSub(FirstInactiveLane, One,
4330 LastActiveL->getDebugLoc(),
"last.active.lane");
4333 LastActiveL->eraseFromParent();
4340 assert(VPI->isMasked() &&
4341 "Unmasked MaskedCond should be simplified earlier");
4342 VPI->replaceAllUsesWith(Builder.createNaryOp(
4344 VPI->eraseFromParent();
4354 Instruction::Add, VPI->operands(), VPI->getNoWrapFlags(),
4355 VPI->getDebugLoc());
4356 VPI->replaceAllUsesWith(
Add);
4357 VPI->eraseFromParent();
4365 DebugLoc DL = BranchOnCountInst->getDebugLoc();
4368 BranchOnCountInst->eraseFromParent();
4383 ? Instruction::UIToFP
4384 : Instruction::Trunc;
4385 VectorStep = Builder.createWidenCast(CastOp, VectorStep, IVTy);
4391 Builder.createWidenCast(Instruction::Trunc, ScalarStep, IVTy);
4397 MulOpc = Instruction::FMul;
4398 Flags = VPI->getFastMathFlagsOrNone();
4400 MulOpc = Instruction::Mul;
4405 MulOpc, {VectorStep, ScalarStep}, Flags, R.getDebugLoc());
4407 VPI->replaceAllUsesWith(VectorStep);
4408 VPI->eraseFromParent();
4418static std::optional<VPValue *>
4471 VPValue *UncountableCondition =
nullptr;
4475 return std::nullopt;
4478 Worklist.
push_back(UncountableCondition);
4479 while (!Worklist.
empty()) {
4483 if (V->isDefinedOutsideLoopRegions())
4489 if (V->getNumUsers() > 1)
4490 return std::nullopt;
4502 return std::nullopt;
4506 return std::nullopt;
4514 return std::nullopt;
4522 return std::nullopt;
4524 return UncountableCondition;
4580 for (
auto &Exit : Exits) {
4581 if (Exit.EarlyExitingVPBB == LatchVPBB)
4585 cast<VPIRPhi>(&R)->removeIncomingValueFor(Exit.EarlyExitingVPBB);
4586 Exit.EarlyExitingVPBB->getTerminator()->eraseFromParent();
4597 std::optional<VPValue *>
Cond =
4613 assert(
Load &&
"Couldn't find exactly one load");
4616 "Uncountable exit condition load is conditional.");
4630 DL.getTypeStoreSize(
Load->getScalarType()).getFixedValue());
4654 while (InsertIt != HeaderVPBB->
end() &&
4656 erase(ConditionRecipes, &*InsertIt);
4659 for (
auto *Recipe :
reverse(ConditionRecipes))
4660 Recipe->moveBefore(*HeaderVPBB, InsertIt);
4664 VPBuilder MaskBuilder(HeaderVPBB, InsertIt);
4666 Type *IVScalarTy =
IV->getScalarType();
4673 {Zero, FirstActive, ALMMultiplier},
4674 DebugLoc(),
"uncountable.exit.mask");
4679 if (R.mayReadOrWriteMemory() && &R !=
Load) {
4681 if (!VPDT.
dominates(R.getParent(), LatchVPBB))
4691 "Expected BranchOnCond terminator for MiddleVPBB");
4702 auto Phis = ScalarPH->
phis();
4712 "Continuing from different IV");
4728 if (Pred == MiddleVPBB)
4733 VPValue *CondOfEarlyExitingVPBB;
4734 [[maybe_unused]]
bool Matched =
4735 match(EarlyExitingVPBB->getTerminator(),
4737 assert(Matched &&
"Terminator must be BranchOnCond");
4741 VPBuilder EarlyExitingBuilder(EarlyExitingVPBB->getTerminator());
4742 auto *CondToEarlyExit = EarlyExitingBuilder.
createNaryOp(
4744 TrueSucc == ExitBlock
4745 ? CondOfEarlyExitingVPBB
4746 : EarlyExitingBuilder.
createNot(CondOfEarlyExitingVPBB));
4752 "exit condition must dominate the latch");
4761 assert(!Exits.
empty() &&
"must have at least one early exit");
4768 for (
const auto &[Num, VPB] :
enumerate(RPOT))
4771 return RPOIdx[
A.EarlyExitingVPBB] < RPOIdx[
B.EarlyExitingVPBB];
4777 for (
unsigned I = 0;
I + 1 < Exits.
size(); ++
I)
4778 for (
unsigned J =
I + 1; J < Exits.
size(); ++J)
4780 Exits[
I].EarlyExitingVPBB) &&
4781 "RPO sort must place dominating exits before dominated ones");
4787 VPValue *Combined = Exits[0].CondToExit;
4800 "Unexpected terminator");
4801 VPValue *IsLatchExitTaken = LatchExitingBranch->getOperand(0);
4802 DebugLoc LatchDL = LatchExitingBranch->getDebugLoc();
4803 LatchExitingBranch->eraseFromParent();
4806 {IsAnyExitTaken, IsLatchExitTaken}, LatchDL);
4812 LatchVPBB->
setSuccessors({MiddleVPBB, MiddleVPBB, HeaderVPBB});
4816 Plan, Exits, HeaderVPBB, LatchVPBB, MiddleVPBB, TheLoop, PSE, DT, AC);
4821 for (
unsigned Idx = 0; Idx != Exits.
size(); ++Idx) {
4825 VectorEarlyExitVPBBs[Idx] = VectorEarlyExitVPBB;
4833 Exits.
size() == 1 ? VectorEarlyExitVPBBs[0]
4836 LatchVPBB->
setSuccessors({DispatchVPBB, MiddleVPBB, HeaderVPBB});
4868 for (
auto [Exit, VectorEarlyExitVPBB] :
4869 zip_equal(Exits, VectorEarlyExitVPBBs)) {
4870 auto &[EarlyExitingVPBB, EarlyExitVPBB,
_] = Exit;
4882 ExitIRI->getIncomingValueForBlock(EarlyExitingVPBB);
4883 VPValue *NewIncoming = IncomingVal;
4885 VPBuilder EarlyExitBuilder(VectorEarlyExitVPBB);
4890 ExitIRI->removeIncomingValueFor(EarlyExitingVPBB);
4891 ExitIRI->addIncoming(NewIncoming);
4894 EarlyExitingVPBB->getTerminator()->eraseFromParent();
4928 bool IsLastDispatch = (
I + 2 == Exits.
size());
4930 IsLastDispatch ? VectorEarlyExitVPBBs.
back()
4936 VectorEarlyExitVPBBs[
I]->setPredecessors({CurrentBB});
4939 CurrentBB = FalseBB;
4954 VPValue *VecOp = Red->getVecOp();
4956 assert(!Red->isPartialReduction() &&
4957 "This path does not support partial reductions");
4960 auto IsExtendedRedValidAndClampRange =
4973 "getExtendedReductionCost only supports integer types");
4974 ExtRedCost = Ctx.TTI.getExtendedReductionCost(
4975 Opcode, ExtOpc == Instruction::CastOps::ZExt, RedTy, SrcVecTy,
4976 Red->getFastMathFlagsOrNone(),
CostKind);
4977 return ExtRedCost.
isValid() && ExtRedCost < ExtCost + RedCost;
4985 IsExtendedRedValidAndClampRange(
5006 if (Opcode != Instruction::Add && Opcode != Instruction::Sub &&
5007 Opcode != Instruction::FAdd)
5010 assert(!Red->isPartialReduction() &&
5011 "This path does not support partial reductions");
5015 auto IsMulAccValidAndClampRange =
5027 (Ext0->getOpcode() != Ext1->getOpcode() ||
5028 Ext0->getOpcode() == Instruction::CastOps::FPExt))
5032 !Ext0 || Ext0->getOpcode() == Instruction::CastOps::ZExt;
5034 MulAccCost = Ctx.TTI.getMulAccReductionCost(IsZExt, Opcode, RedTy,
5041 ExtCost += Ext0->computeCost(VF, Ctx);
5043 ExtCost += Ext1->computeCost(VF, Ctx);
5045 ExtCost += OuterExt->computeCost(VF, Ctx);
5047 return MulAccCost.
isValid() &&
5048 MulAccCost < ExtCost + MulCost + RedCost;
5053 VPValue *VecOp = Red->getVecOp();
5091 Builder.createWidenCast(Instruction::CastOps::Trunc, ValB, NarrowTy);
5093 ValB = ExtB = Builder.createWidenCast(ExtOpc, Trunc, WideTy);
5094 Mul->setOperand(1, ExtB);
5104 ExtendAndReplaceConstantOp(RecipeA, RecipeB,
B,
Mul);
5109 IsMulAccValidAndClampRange(
Mul, RecipeA, RecipeB,
nullptr)) {
5116 if (!
Sub && IsMulAccValidAndClampRange(
Mul,
nullptr,
nullptr,
nullptr))
5133 ExtendAndReplaceConstantOp(Ext0, Ext1,
B,
Mul);
5142 (Ext->getOpcode() == Ext0->getOpcode() || Ext0 == Ext1) &&
5143 Ext0->getOpcode() == Ext1->getOpcode() &&
5144 IsMulAccValidAndClampRange(
Mul, Ext0, Ext1, Ext) &&
Mul->hasOneUse()) {
5146 Ext0->getOpcode(), Ext0->getOperand(0), Ext->getScalarType(),
nullptr,
5147 *Ext0, *Ext0, Ext0->getDebugLoc());
5148 NewExt0->insertBefore(Ext0);
5153 Ext->getScalarType(),
nullptr, *Ext1,
5154 *Ext1, Ext1->getDebugLoc());
5157 auto *NewMul =
Mul->cloneWithOperands({NewExt0, NewExt1});
5158 NewMul->insertBefore(
Mul);
5159 Ext->replaceAllUsesWith(NewMul);
5160 Ext->eraseFromParent();
5161 Mul->eraseFromParent();
5175 assert(!Red->isPartialReduction() &&
5176 "This path does not support partial reductions");
5179 auto IP = std::next(Red->getIterator());
5180 auto *VPBB = Red->getParent();
5190 Red->replaceAllUsesWith(AbstractR);
5220 for (
VPValue *VPV : VPValues) {
5228 if (
User->usesScalars(VPV))
5231 HoistPoint = HoistBlock->
begin();
5235 "All users must be in the vector preheader or dominated by it");
5240 VPV->replaceUsesWithIf(Broadcast,
5241 [VPV, Broadcast](
VPUser &U,
unsigned Idx) {
5242 return Broadcast != &U && !U.usesScalars(VPV);
5253 return CommonMetadata;
5256template <
unsigned Opcode>
5261 static_assert(Opcode == Instruction::Load || Opcode == Instruction::Store,
5262 "Only Load and Store opcodes supported");
5263 [[maybe_unused]]
constexpr bool IsLoad = (Opcode == Instruction::Load);
5270 for (
auto Recipes :
Groups) {
5271 if (Recipes.size() < 2)
5276 "Expected all recipes in group to have the same load-store type");
5283 VPValue *MaskI = RecipeI->getMask();
5289 bool HasComplementaryMask =
false;
5294 VPValue *MaskJ = RecipeJ->getMask();
5303 if (HasComplementaryMask) {
5304 assert(Group.
size() >= 2 &&
"must have at least 2 entries");
5314template <
typename InstType>
5332 for (
auto &Group :
Groups) {
5352 return R->isSingleScalar() == IsSingleScalar;
5354 "all members in group must agree on IsSingleScalar");
5359 LoadWithMinAlign->getUnderlyingInstr(), {EarliestLoad->getOperand(0)},
5360 IsSingleScalar,
nullptr, *EarliestLoad, CommonMetadata);
5362 UnpredicatedLoad->insertBefore(EarliestLoad);
5366 Load->replaceAllUsesWith(UnpredicatedLoad);
5367 Load->eraseFromParent();
5376 if (!StoreLoc || !StoreLoc->AATags.Scope)
5383 SinkStoreInfo SinkInfo(StoresToSink, *StoresToSink[0], PSE, L);
5395 for (
auto &Group :
Groups) {
5408 VPValue *SelectedValue = Group[0]->getOperand(0);
5411 bool IsSingleScalar = Group[0]->isSingleScalar();
5412 for (
unsigned I = 1;
I < Group.size(); ++
I) {
5413 assert(IsSingleScalar == Group[
I]->isSingleScalar() &&
5414 "all members in group must agree on IsSingleScalar");
5415 VPValue *Mask = Group[
I]->getMask();
5417 SelectedValue = Builder.createSelect(Mask,
Value, SelectedValue,
5426 StoreWithMinAlign->getUnderlyingInstr(),
5427 {SelectedValue, LastStore->getOperand(1)}, IsSingleScalar,
5428 nullptr, *LastStore, CommonMetadata);
5429 UnpredicatedStore->insertBefore(*InsertBB, LastStore->
getIterator());
5433 Store->eraseFromParent();
5440 assert(Plan.
hasVF(BestVF) &&
"BestVF is not available in Plan");
5441 assert(Plan.
hasUF(BestUF) &&
"BestUF is not available in Plan");
5504 auto UsesVectorOrInsideReplicateRegion = [DefR, LoopRegion](
VPUser *U) {
5506 return !U->usesScalars(DefR) || ParentRegion != LoopRegion;
5513 none_of(DefR->users(), UsesVectorOrInsideReplicateRegion))
5523 DefR->replaceUsesWithIf(
5524 BuildVector, [BuildVector, &UsesVectorOrInsideReplicateRegion](
5526 return &U != BuildVector && UsesVectorOrInsideReplicateRegion(&U);
5540 for (
VPValue *Def : R.definedValues()) {
5550 unsigned NumFirstLaneUsers =
count_if(Def->users(), [&Def](
VPUser *U) {
5551 return U->usesFirstLaneOnly(Def);
5553 if (!NumFirstLaneUsers || NumFirstLaneUsers == Def->getNumUsers())
5560 Unpack->insertAfter(&R);
5561 Def->replaceUsesWithIf(Unpack, [&Def](
VPUser &U,
unsigned) {
5562 return U.usesFirstLaneOnly(Def);
5571 bool RequiresScalarEpilogue,
VPValue *Step,
5572 std::optional<uint64_t> MaxRuntimeStep) {
5584 "Step VPBB must dominate VectorPHVPBB");
5586 InsertPt = std::next(StepR->getIterator());
5588 VPBuilder Builder(VectorPHVPBB, InsertPt);
5594 if (!RequiresScalarEpilogue &&
match(TC,
m_APInt(TCVal)) && MaxRuntimeStep &&
5595 TCVal->
urem(*MaxRuntimeStep) == 0) {
5606 if (TailByMasking) {
5607 TC = Builder.createAdd(
5618 Builder.createNaryOp(Instruction::URem, {TC, Step},
5627 if (RequiresScalarEpilogue) {
5629 "requiring scalar epilogue is not supported with fail folding");
5632 R = Builder.createSelect(IsZero, Step, R);
5646 "VF and VFxUF must be materialized together");
5658 Builder.createElementCount(TCTy, VFEC * Plan.
getConcreteUF());
5665 VPValue *RuntimeVF = Builder.createElementCount(TCTy, VFEC);
5669 BC, [&VF](
VPUser &U,
unsigned) {
return !U.usesScalars(&VF); });
5673 VPValue *MulByUF = Builder.createOverflowingOp(
5686 auto *AliasMask = Builder.createNaryOp(
5691 Builder =
VPBuilder(Header, Header->getFirstNonPhi());
5694 auto *ClampedHeaderMask = Builder.createAnd(HeaderMask, AliasMask);
5696 return &U != ClampedHeaderMask;
5707 assert(IncomingAliasMask &&
"Expected an alias mask!");
5717 if (
Check.NeedsFreeze) {
5727 Intrinsic::loop_dependence_war_mask,
5731 AliasMask = Builder.createAnd(AliasMask, WARMask);
5733 AliasMask = WARMask;
5738 VPValue *NumActive = Builder.createNaryOp(
5741 VPValue *ClampedVF = Builder.createScalarZExtOrTrunc(
5767 VPValue *DistanceToMax = Builder.createSub(MaxUIntTripCount, TripCount);
5775 VPValue *TripCountCheck = Builder.createICmp(
5778 VPValue *
Cond = Builder.createOr(IsScalar, TripCountCheck,
DL);
5789 "Clamped VF not supported with interleaving");
5797 VPBuilder Builder(Entry, Entry->begin());
5809 if (!ExpSCEV || ExpSCEV->user_empty())
5811 Builder.setInsertPoint(ExpSCEV);
5820 ExpSCEV->eraseFromParent();
5829 BasicBlock *EntryBB = Entry->getIRBasicBlock();
5836 const SCEV *Expr = ExpSCEV->getSCEV();
5839 ExpandedSCEVs[Expr] = Res;
5844 ExpSCEV->eraseFromParent();
5847 "all VPExpandSCEVRecipes must have been expanded");
5850 auto EI = Entry->begin();
5860 return ExpandedSCEVs;
5874 VPValue *OpV,
unsigned Idx,
bool IsScalable) {
5879 if (Member0Op == OpV)
5889 return !IsScalable && !W->getMask() && W->isConsecutive() &&
5892 return IR->getInterleaveGroup()->isFull() &&
IR->getVPValue(Idx) == OpV;
5907 if (R->getScalarType() != WideMember0->getScalarType())
5909 if (R->hasPredicate() && R->getPredicate() != WideMember0->getPredicate())
5913 for (
unsigned Idx = 0; Idx != WideMember0->getNumOperands(); ++Idx) {
5916 OpsI.
push_back(
Op->getDefiningRecipe()->getOperand(Idx));
5921 if (
any_of(
enumerate(OpsI), [WideMember0, Idx, IsScalable](
const auto &
P) {
5922 const auto &[
OpIdx, OpV] =
P;
5934static std::optional<ElementCount>
5938 if (!InterleaveR || InterleaveR->
getMask())
5939 return std::nullopt;
5941 Type *GroupElementTy =
nullptr;
5945 return Op->getScalarType() == GroupElementTy;
5947 return std::nullopt;
5951 return Op->getScalarType() == GroupElementTy;
5953 return std::nullopt;
5957 if (IG->getFactor() != IG->getNumMembers())
5958 return std::nullopt;
5964 assert(
Size.isScalable() == VF.isScalable() &&
5965 "if Size is scalable, VF must be scalable and vice versa");
5966 return Size.getKnownMinValue();
5970 unsigned MinVal = VF.getKnownMinValue();
5972 if (IG->getFactor() == MinVal && GroupSize == GetVectorBitWidthForVF(VF))
5975 return std::nullopt;
5983 return RepR && RepR->isSingleScalar();
5997 if (V->isDefinedOutsideLoopRegions()) {
6000 return M->isDefinedOutsideLoopRegions() &&
6001 M->getScalarType() == V->getScalarType();
6003 "expected distinct loop-invariant values of matching scalar type");
6018 for (
unsigned Idx = 0,
E = WideMember0->getNumOperands(); Idx !=
E; ++Idx) {
6020 for (
VPValue *Member : Members)
6021 OpsI.
push_back(Member->getDefiningRecipe()->getOperand(Idx));
6022 WideMember0->setOperand(
6031 auto *LI =
cast<LoadInst>(LoadGroup->getInterleaveGroup()->getInsertPos());
6033 LoadGroup->getMask(),
true,
6034 *LoadGroup, LoadGroup->getDebugLoc());
6035 L->insertBefore(LoadGroup);
6041 assert(RepR->isSingleScalar() && RepR->getOpcode() == Instruction::Load &&
6042 "must be a single scalar load");
6043 NarrowedOps.
insert(RepR);
6048 VPValue *PtrOp = WideLoad->getAddr();
6050 PtrOp = VecPtr->getOperand(0);
6055 nullptr, {}, *WideLoad);
6056 N->insertBefore(WideLoad);
6061std::unique_ptr<VPlan>
6081 "unexpected branch-on-count");
6084 std::optional<ElementCount> VFToOptimize;
6098 if (R.mayWriteToMemory() && !InterleaveR)
6104 return any_of(V->users(), [&](VPUser *U) {
6105 auto *UR = cast<VPRecipeBase>(U);
6106 return UR->getParent()->getParent() != VectorLoop;
6123 std::optional<ElementCount> NarrowedVF =
6125 if (!NarrowedVF || (VFToOptimize && NarrowedVF != VFToOptimize))
6127 VFToOptimize = NarrowedVF;
6130 if (InterleaveR->getStoredValues().empty())
6135 auto *Member0 = InterleaveR->getStoredValues()[0];
6145 VPRecipeBase *DefR = Op.value()->getDefiningRecipe();
6148 auto *IR = dyn_cast<VPInterleaveRecipe>(DefR);
6149 return IR && IR->getInterleaveGroup()->isFull() &&
6150 IR->getVPValue(Op.index()) == Op.value();
6159 VFToOptimize->isScalable()))
6164 if (StoreGroups.empty())
6168 bool RequiresScalarEpilogue =
6179 std::unique_ptr<VPlan> NewPlan;
6181 NewPlan = std::unique_ptr<VPlan>(Plan.
duplicate());
6182 Plan.
setVF(*VFToOptimize);
6183 NewPlan->removeVF(*VFToOptimize);
6190 for (
auto *StoreGroup : StoreGroups) {
6192 NarrowedOps, Preheader);
6197 StoreGroup->getDebugLoc());
6198 S->insertBefore(StoreGroup);
6199 StoreGroup->eraseFromParent();
6205 Type *CanIVTy = VectorLoop->getCanonicalIVType();
6211 if (VFToOptimize->isScalable()) {
6214 Step = PHBuilder.createOverflowingOp(Instruction::Mul, {VScale,
UF},
6222 materializeVectorTripCount(Plan, VectorPH,
false,
6223 RequiresScalarEpilogue, Step);
6228 removeDeadRecipes(Plan);
6231 "All VPVectorPointerRecipes should have been removed");
6247 "must have a BranchOnCond");
6250 if (VF.
isScalable() && VScaleForTuning.has_value())
6251 VectorStep *= *VScaleForTuning;
6252 assert(VectorStep > 0 &&
"trip count should not be zero");
6256 MiddleTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
6275 "Cannot handle loops with uncountable early exits");
6282 assert(RecurSplice &&
"expected FirstOrderRecurrenceSplice");
6289 if (
any_of(RecurSplice->users(),
6290 [](
VPUser *U) { return !cast<VPRecipeBase>(U)->getRegion(); }) &&
6371 {},
"vector.recur.extract.for.phi");
6374 ExitPhi->replaceUsesOfWith(ExtractR, PenultimateElement);
6388 VPValue *WidenIVCandidate = BinOp->getOperand(0);
6389 VPValue *InvariantCandidate = BinOp->getOperand(1);
6391 std::swap(WidenIVCandidate, InvariantCandidate);
6405 auto *ClonedOp = BinOp->
clone();
6406 if (ClonedOp->getOperand(0) == WidenIV) {
6407 ClonedOp->setOperand(0, ScalarIV);
6409 assert(ClonedOp->getOperand(1) == WidenIV &&
"one operand must be WideIV");
6410 ClonedOp->setOperand(1, ScalarIV);
6425 auto CheckSentinel = [&SE](
const SCEV *IVSCEV,
6426 bool UseMax) -> std::optional<APSInt> {
6428 for (
bool Signed : {
true,
false}) {
6437 return std::nullopt;
6445 PhiR->getRecurrenceKind()))
6454 VPValue *BackedgeVal = PhiR->getBackedgeValue();
6468 !
match(FindLastSelect,
6477 IVOfExpressionToSink ? IVOfExpressionToSink : FindLastExpression, PSE,
6483 "IVOfExpressionToSink not being an AddRec must imply "
6484 "FindLastExpression not being an AddRec.");
6495 std::optional<APSInt> SentinelVal = CheckSentinel(IVSCEV, UseMax);
6496 bool UseSigned = SentinelVal && SentinelVal->isSigned();
6503 if (IVOfExpressionToSink) {
6504 const SCEV *FindLastExpressionSCEV =
6506 if (
match(FindLastExpressionSCEV,
6509 if (
auto NewSentinel =
6510 CheckSentinel(FindLastExpressionSCEV, NewUseMax)) {
6513 SentinelVal = *NewSentinel;
6514 UseSigned = NewSentinel->isSigned();
6516 IVSCEV = FindLastExpressionSCEV;
6517 IVOfExpressionToSink =
nullptr;
6527 if (AR->hasNoSignedWrap())
6529 else if (AR->hasNoUnsignedWrap())
6539 VPValue *NewFindLastSelect = BackedgeVal;
6541 if (!SentinelVal || IVOfExpressionToSink) {
6544 DebugLoc DL = FindLastSelect->getDefiningRecipe()->getDebugLoc();
6545 VPBuilder LoopBuilder(FindLastSelect->getDefiningRecipe());
6546 if (FindLastSelect->getDefiningRecipe()->getOperand(1) == PhiR)
6547 SelectCond = LoopBuilder.
createNot(SelectCond);
6554 if (SelectCond !=
Cond || IVOfExpressionToSink) {
6557 IVOfExpressionToSink ? IVOfExpressionToSink : FindLastExpression,
6566 VPIRFlags Flags(MinMaxKind,
false,
false,
6572 NewFindLastSelect, Flags, ExitDL);
6575 VPValue *VectorRegionExitingVal = ReducedIV;
6576 if (IVOfExpressionToSink)
6577 VectorRegionExitingVal =
6579 ReducedIV, IVOfExpressionToSink);
6582 VPValue *StartVPV = PhiR->getStartValue();
6589 NewRdxResult = MiddleBuilder.
createSelect(Cmp, VectorRegionExitingVal,
6599 AnyOfPhi->insertAfter(PhiR);
6606 OrVal, VectorRegionExitingVal, StartVPV, ExitDL);
6619 PhiR->hasUsesOutsideReductionChain());
6620 NewPhiR->insertBefore(PhiR);
6621 PhiR->replaceAllUsesWith(NewPhiR);
6622 PhiR->eraseFromParent();
6629struct ReductionExtend {
6630 Type *SrcType =
nullptr;
6631 ExtendKind Kind = ExtendKind::PR_None;
6637struct ExtendedReductionOperand {
6641 ReductionExtend ExtendA, ExtendB;
6649struct VPPartialReductionChain {
6652 VPWidenRecipe *ReductionBinOp =
nullptr;
6654 ExtendedReductionOperand ExtendedOp;
6661 unsigned AccumulatorOpIdx;
6662 unsigned ScaleFactor;
6665 VPBlendRecipe *Blend =
nullptr;
6670static std::optional<unsigned>
6674 "Expected a non-normalized blend with two incoming values");
6680 return std::nullopt;
6681 return FirstIncomingHasOneUse ? 0 : 1;
6693 if (!
Op->hasOneUse() ||
6699 auto *Trunc = Builder.createWidenCast(Instruction::CastOps::Trunc,
6700 Op->getOperand(1), NarrowTy);
6702 Op->setOperand(1, Builder.createWidenCast(ExtOpc, Trunc, WideTy));
6711 auto *
Sub =
Op->getOperand(0)->getDefiningRecipe();
6713 assert(Ext->getOpcode() ==
6715 "Expected both the LHS and RHS extends to be the same");
6716 bool IsSigned = Ext->getOpcode() == Instruction::SExt;
6719 auto *FreezeX = Builder.insert(
new VPWidenRecipe(Instruction::Freeze, {
X}));
6720 auto *FreezeY = Builder.insert(
new VPWidenRecipe(Instruction::Freeze, {
Y}));
6721 auto *
Max = Builder.insert(
6723 {FreezeX, FreezeY}, SrcTy));
6724 auto *Min = Builder.insert(
6726 {FreezeX, FreezeY}, SrcTy));
6729 return Builder.createWidenCast(Instruction::CastOps::ZExt, AbsDiff,
6730 Op->getScalarType());
6742 if (!
Mul->hasOneUse() ||
6743 (Ext->getOpcode() != MulLHS->getOpcode() && MulLHS != MulRHS) ||
6744 MulLHS->getOpcode() != MulRHS->getOpcode())
6747 auto *NewLHS = Builder.createWidenCast(
6748 MulLHS->getOpcode(), MulLHS->getOperand(0), Ext->getScalarType());
6749 auto *NewRHS = MulLHS == MulRHS
6751 : Builder.createWidenCast(MulRHS->getOpcode(),
6752 MulRHS->getOperand(0),
6753 Ext->getScalarType());
6754 auto *NewMul =
Mul->cloneWithOperands({NewLHS, NewRHS});
6755 Builder.insert(NewMul);
6756 Op->replaceAllUsesWith(NewMul);
6757 Op->eraseFromParent();
6758 Mul->eraseFromParent();
6767 VPValue *VecOp = Red->getVecOp();
6821static void transformToPartialReduction(
const VPPartialReductionChain &Chain,
6829 WidenRecipe->
getOperand(1 - Chain.AccumulatorOpIdx));
6832 ExtendedOp = optimizeExtendsForPartialReduction(ExtendedOp);
6848 if ((WidenRecipe->
getOpcode() == Instruction::Sub &&
6850 (WidenRecipe->
getOpcode() == Instruction::FSub &&
6855 if (WidenRecipe->
getOpcode() == Instruction::FSub) {
6865 Builder.insert(NegRecipe);
6866 ExtendedOp = NegRecipe;
6881 std::optional<unsigned> BlendReductionIdx =
6882 getBlendReductionUpdateValueIdx(Chain.Blend);
6883 assert(BlendReductionIdx &&
6885 "Expected blend to contain the reduction update");
6896 assert((!ExitValue || IsLastInChain) &&
6897 "if we found ExitValue, it must match RdxPhi's backedge value");
6908 PartialRed->insertBefore(WidenRecipe);
6918 E->insertBefore(WidenRecipe);
6919 PartialRed->replaceAllUsesWith(
E);
6932 auto *NewScaleFactor = Plan.
getConstantInt(32, Chain.ScaleFactor);
6933 StartInst->setOperand(2, NewScaleFactor);
6941 VPValue *OldStartValue = StartInst->getOperand(0);
6942 StartInst->setOperand(0, StartInst->getOperand(1));
6946 assert(RdxResult &&
"Could not find reduction result");
6949 unsigned SubOpc = Chain.RK ==
RecurKind::FSub ? Instruction::BinaryOps::FSub
6950 : Instruction::BinaryOps::Sub;
6956 [&NewResult](
VPUser &U,
unsigned Idx) {
return &
U != NewResult; });
6962 const VPPartialReductionChain &Link,
6965 const ExtendedReductionOperand &ExtendedOp = Link.ExtendedOp;
6966 std::optional<unsigned> BinOpc = std::nullopt;
6968 if (ExtendedOp.ExtendB.Kind != ExtendKind::PR_None)
6969 BinOpc = ExtendedOp.ExtendsUser->
getOpcode();
6971 std::optional<llvm::FastMathFlags>
Flags;
6975 auto GetLinkOpcode = [&Link]() ->
unsigned {
6978 return Instruction::Add;
6980 return Instruction::FAdd;
6982 return Link.ReductionBinOp->
getOpcode();
6987 GetLinkOpcode(), ExtendedOp.ExtendA.SrcType, ExtendedOp.ExtendB.SrcType,
6988 RdxType, VF, ExtendedOp.ExtendA.Kind, ExtendedOp.ExtendB.Kind, BinOpc,
7009static std::optional<ExtendedReductionOperand>
7012 "Op should be operand of UpdateR");
7020 if (
Op->hasOneUse() &&
7029 Type *RHSInputType =
Y->getScalarType();
7030 if (LHSInputType != RHSInputType ||
7031 LHSExt->getOpcode() != RHSExt->getOpcode())
7032 return std::nullopt;
7035 return ExtendedReductionOperand{
7037 {LHSInputType, getPartialReductionExtendKind(LHSExt)},
7041 std::optional<TTI::PartialReductionExtendKind> OuterExtKind;
7044 VPValue *CastSource = CastRecipe->getOperand(0);
7045 OuterExtKind = getPartialReductionExtendKind(CastRecipe);
7055 return ExtendedReductionOperand{
7062 if (!
Op->hasOneUse())
7063 return std::nullopt;
7068 return std::nullopt;
7078 return std::nullopt;
7082 ExtendKind LHSExtendKind = getPartialReductionExtendKind(LHSCast);
7085 const APInt *RHSConst =
nullptr;
7091 return std::nullopt;
7095 if (Cast && OuterExtKind &&
7096 getPartialReductionExtendKind(Cast) != OuterExtKind)
7097 return std::nullopt;
7099 Type *RHSInputType = LHSInputType;
7100 ExtendKind RHSExtendKind = LHSExtendKind;
7103 RHSExtendKind = getPartialReductionExtendKind(RHSCast);
7106 return ExtendedReductionOperand{
7107 MulOp, {LHSInputType, LHSExtendKind}, {RHSInputType, RHSExtendKind}};
7114static std::optional<SmallVector<VPPartialReductionChain>>
7121 return std::nullopt;
7131 VPValue *CurrentValue = ExitValue;
7132 while (CurrentValue != RedPhiR) {
7134 std::optional<unsigned> BlendReductionIdx;
7138 return std::nullopt;
7140 BlendReductionIdx = getBlendReductionUpdateValueIdx(Blend);
7141 if (!BlendReductionIdx)
7142 return std::nullopt;
7149 return std::nullopt;
7156 std::optional<ExtendedReductionOperand> ExtendedOp =
7157 matchExtendedReductionOperand(UpdateR,
Op);
7159 ExtendedOp = matchExtendedReductionOperand(UpdateR, PrevValue);
7161 return std::nullopt;
7169 return std::nullopt;
7171 Type *ExtSrcType = ExtendedOp->ExtendA.SrcType;
7174 return std::nullopt;
7176 VPPartialReductionChain Link(
7177 {UpdateR, *ExtendedOp, RK,
7182 CurrentValue = PrevValue;
7187 std::reverse(Chain.
begin(), Chain.
end());
7206 if (
auto Chains = getScaledReductions(RedPhiR))
7207 ChainsByPhi.
try_emplace(RedPhiR, std::move(*Chains));
7210 if (ChainsByPhi.
empty())
7218 for (
const auto &[
_, Chains] : ChainsByPhi)
7219 for (
const VPPartialReductionChain &Chain : Chains) {
7220 PartialReductionOps.
insert(Chain.ExtendedOp.ExtendsUser);
7222 PartialReductionBlends.
insert(Chain.Blend);
7223 ScaledReductionMap[Chain.ReductionBinOp] = Chain.ScaleFactor;
7229 auto ExtendUsersValid = [&](
VPValue *Ext) {
7231 return PartialReductionOps.contains(cast<VPRecipeBase>(U));
7235 auto IsProfitablePartialReductionChainForVF =
7242 for (
const VPPartialReductionChain &Link : Chain) {
7243 const ExtendedReductionOperand &ExtendedOp = Link.ExtendedOp;
7244 InstructionCost LinkCost = getPartialReductionLinkCost(CostCtx, Link, VF);
7248 PartialCost += LinkCost;
7249 RegularCost += Link.ReductionBinOp->
computeCost(VF, CostCtx);
7251 if (ExtendedOp.ExtendB.Kind != ExtendKind::PR_None)
7252 RegularCost += ExtendedOp.ExtendsUser->
computeCost(VF, CostCtx);
7255 RegularCost += Extend->computeCost(VF, CostCtx);
7257 return PartialCost.
isValid() && PartialCost < RegularCost;
7265 for (
auto &[RedPhiR, Chains] : ChainsByPhi) {
7266 for (
const VPPartialReductionChain &Chain : Chains) {
7267 if (!
all_of(Chain.ExtendedOp.ExtendsUser->operands(), ExtendUsersValid)) {
7271 auto UseIsValid = [&, RedPhiR = RedPhiR](
VPUser *U) {
7273 return PhiR == RedPhiR;
7277 return Blend == Chain.Blend || PartialReductionBlends.
contains(Blend);
7279 return Chain.ScaleFactor == ScaledReductionMap.
lookup_or(R, 0) ||
7285 if (!
all_of(Chain.ReductionBinOp->users(), UseIsValid)) {
7294 auto *RepR = dyn_cast<VPReplicateRecipe>(U);
7295 return RepR && RepR->getOpcode() == Instruction::Store;
7306 return IsProfitablePartialReductionChainForVF(Chains, VF);
7312 for (
auto &[Phi, Chains] : ChainsByPhi)
7313 for (
const VPPartialReductionChain &Chain : Chains)
7314 transformToPartialReduction(Chain, Plan, Phi);
7343 if (VPI && VPI->getUnderlyingValue() &&
7354 auto ProcessSubset = [&](
VPlan &,
auto ProcessVPInst) {
7357 if (!ProcessVPInst(VPI))
7366 New->insertBefore(VPI);
7367 if (VPI->
getOpcode() == Instruction::Load)
7382 "lowerMemoryIdioms", ProcessSubset, Plan, [&](
VPInstruction *VPI) {
7384 VPI, FinalRedStoresBuilder))
7393 return ReplaceWith(VPI, Histogram);
7406 "scalarizeMemOpsWithIrregularTypes", ProcessSubset, Plan,
7410 return Scalarize(VPI);
7417 "makeVPlanMemOpDecision", ProcessSubset, Plan, [&](
VPInstruction *VPI) {
7419 bool IsLoad = VPI->
getOpcode() == Instruction::Load;
7429 const SCEV *PtrSCEV =
7431 bool IsSingleScalarLoad =
7437 I, Ptr, IsSingleScalarLoad,
7445 "widenConsecutiveMemOps", ProcessSubset, Plan, [&](
VPInstruction *VPI) {
7450 bool IsLoad = VPI->
getOpcode() == Instruction::Load;
7463 VectorPtr->insertBefore(VPI);
7474 return ReplaceWith(VPI, WidenedR);
7481 return ReplaceWith(VPI, Recipe);
7483 return Scalarize(VPI);
7506 if (VPI->mayHaveSideEffects())
7510 if (VPI->isMasked() && !VPI->isSafeToSpeculativelyExecute())
7515 if (VPI->getOpcode() == Instruction::Add &&
7524 VPI->getOpcode(), VPI->operandsWithoutMask(),
nullptr, *VPI,
7525 *VPI, VPI->getDebugLoc(),
I);
7526 Recipe->insertBefore(VPI);
7527 VPI->replaceAllUsesWith(Recipe);
7528 VPI->eraseFromParent();
7538 switch (Param.ParamKind) {
7539 case VFParamKind::Vector:
7540 case VFParamKind::GlobalPredicate:
7542 case VFParamKind::OMP_Uniform:
7543 return SE->isSCEVable(Args[Param.ParamPos]->getScalarType()) &&
7544 SE->isLoopInvariant(
7545 vputils::getSCEVExprForVPValue(Args[Param.ParamPos], PSE, L),
7547 case VFParamKind::OMP_Linear:
7548 return match(vputils::getSCEVExprForVPValue(Args[Param.ParamPos], PSE, L),
7549 m_scev_AffineAddRec(
7550 m_SCEV(), m_scev_SpecificSInt(Param.LinearStepOrPos),
7551 m_SpecificLoop(L)));
7568 const auto *It =
find_if(Mappings, [&](
const VFInfo &Info) {
7569 return Info.Shape.VF == VF && (!MaskRequired || Info.isMasked()) &&
7572 if (It == Mappings.end())
7579struct CallWideningDecision {
7580 enum class KindTy { Scalarize,
Intrinsic, VectorVariant };
7581 CallWideningDecision(KindTy Kind, Function *Variant =
nullptr)
7604 return CallWideningDecision::KindTy::Scalarize;
7614 return CallWideningDecision::KindTy::Scalarize;
7618 false, VF, CostCtx);
7633 return CallWideningDecision::KindTy::Intrinsic;
7637 if (VecFunc && ScalarCost >= VecCallCost)
7638 return {CallWideningDecision::KindTy::VectorVariant, VecFunc};
7640 return CallWideningDecision::KindTy::Scalarize;
7650 if (!VPI || !VPI->getUnderlyingValue() ||
7651 VPI->getOpcode() != Instruction::Call)
7656 VPI->op_begin() + CI->arg_size());
7658 CallWideningDecision Decision =
7667 switch (Decision.Kind) {
7668 case CallWideningDecision::KindTy::Intrinsic: {
7672 *VPI, VPI->getDebugLoc());
7675 case CallWideningDecision::KindTy::VectorVariant: {
7679 VPValue *Mask = VPI->isMasked() ? VPI->getMask() : Plan.
getTrue();
7680 Ops.push_back(Mask);
7682 Ops.push_back(VPI->getOperand(VPI->getNumOperandsWithoutMask() - 1));
7684 *VPI, VPI->getDebugLoc());
7687 case CallWideningDecision::KindTy::Scalarize:
7693 VPI->replaceAllUsesWith(Replacement);
7694 VPI->eraseFromParent();
7717 if (!LoadR || LoadR->isConsecutive())
7720 VPValue *Ptr = LoadR->getAddr();
7733 Align Alignment = LoadR->getAlign();
7736 if (!Ctx.TTI.isLegalStridedLoadStore(DataTy, Alignment))
7741 Intrinsic::experimental_vp_strided_load, DataTy,
7742 LoadR->isMasked(), Alignment, Ctx);
7743 return StridedLoadStoreCost < CurrentCost;
7754 Ctx.invalidateWideningDecision(&LoadR->getIngredient(), VF);
7759 I32VF = Builder.createScalarZExtOrTrunc(
7776 "Stride type from SCEV must match the index type");
7777 VPValue *CanIV = Builder.createScalarSExtOrTrunc(
7781 auto *
Offset = Builder.createOverflowingOp(
7782 Instruction::Mul, {CanIV, StrideInBytes},
7783 {AddRecPtr->hasNoUnsignedWrap(),
false});
7787 VPValue *BasePtr = Builder.createNoWrapPtrAdd(StartVPV,
Offset, NWFlags);
7790 VPValue *NewPtr = Builder.createVectorPointer(
7792 LoadR->getDebugLoc());
7794 VPValue *Mask = LoadR->getMask();
7797 auto *StridedLoad = Builder.createWidenMemIntrinsic(
7798 Intrinsic::experimental_vp_strided_load,
7799 {NewPtr, StrideInBytes, Mask, I32VF}, LoadTy, Alignment, *LoadR,
7800 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()
bool hasNoUnsignedWrap() const
GEPNoWrapFlags withoutNoUnsignedWrap() const
static GEPNoWrapFlags none()
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
A struct for saving information about induction variables.
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.
@ Load
The value being inserted comes from a load (InsertElement only).
@ Store
The extracted value is stored (ExtractElement only).
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...