46#define DEBUG_TYPE "vector-combine"
52STATISTIC(NumVecLoad,
"Number of vector loads formed");
53STATISTIC(NumVecCmp,
"Number of vector compares formed");
54STATISTIC(NumVecBO,
"Number of vector binops formed");
55STATISTIC(NumVecCmpBO,
"Number of vector compare + binop formed");
56STATISTIC(NumShufOfBitcast,
"Number of shuffles moved after bitcast");
57STATISTIC(NumScalarOps,
"Number of scalar unary + binary ops formed");
58STATISTIC(NumScalarCmp,
"Number of scalar compares formed");
59STATISTIC(NumScalarIntrinsic,
"Number of scalar intrinsic calls formed");
61static const unsigned InvalidIndex = std::numeric_limits<unsigned>::max();
66 VectorCombine(
const VectorizeOptions &Opts,
Function &
F,
77 TTI(TTI), DT(DT), AA(AA),
DL(DL), CostKind(CostKind),
78 SQ(*DL,
nullptr, &DT, &AC),
79 TryEarlyFoldsOnly(TryEarlyFoldsOnly) {}
84 const VectorizeOptions &Opts;
86 IRBuilder<InstSimplifyFolder, IRBuilderCallbackInserter> Builder;
87 const TargetTransformInfo &TTI;
88 const DominatorTree &DT;
92 const SimplifyQuery SQ;
96 bool TryEarlyFoldsOnly;
98 InstructionWorklist Worklist;
107 bool vectorizeLoadInsert(Instruction &
I);
108 bool widenSubvectorLoad(Instruction &
I);
109 ExtractElementInst *getShuffleExtract(ExtractElementInst *Ext0,
110 ExtractElementInst *Ext1,
111 unsigned PreferredExtractIndex)
const;
112 bool isExtractExtractCheap(ExtractElementInst *Ext0, ExtractElementInst *Ext1,
113 const Instruction &
I,
114 ExtractElementInst *&ConvertToShuffle,
115 unsigned PreferredExtractIndex);
118 bool foldExtractExtract(Instruction &
I);
119 bool foldInsExtFNeg(Instruction &
I);
120 bool foldInsExtBinop(Instruction &
I);
121 bool foldInsExtVectorToShuffle(Instruction &
I);
122 bool foldInsertScalarPartsToShuffle(Instruction &
I);
123 bool foldBitOpOfCastops(Instruction &
I);
124 bool foldBitOpOfCastConstant(Instruction &
I);
125 bool foldBitcastShuffle(Instruction &
I);
126 bool scalarizeOpOrCmp(Instruction &
I);
127 bool foldExtractedCmps(Instruction &
I);
128 bool foldSelectsFromBitcast(Instruction &
I);
129 bool foldBinopOfReductions(Instruction &
I);
130 bool foldInsertElementsToStores(Instruction &
I);
131 bool scalarizeLoad(Instruction &
I);
132 bool scalarizeLoadExtract(LoadInst *LI, VectorType *VecTy,
Value *Ptr);
133 bool scalarizeLoadBitcast(LoadInst *LI, VectorType *VecTy,
Value *Ptr);
134 bool scalarizeExtExtract(Instruction &
I);
135 bool foldConcatOfBoolMasks(Instruction &
I);
136 bool foldPermuteOfBinops(Instruction &
I);
137 bool foldShuffleOfBinops(Instruction &
I);
138 bool foldShuffleOfSelects(Instruction &
I);
139 bool foldShuffleOfCastops(Instruction &
I);
140 bool foldShuffleOfShuffles(Instruction &
I);
141 bool foldShuffleOfAdjacentLoads(Instruction &
I);
142 bool foldPermuteOfIntrinsic(Instruction &
I);
143 bool foldShufflesOfLengthChangingShuffles(Instruction &
I);
144 bool foldShuffleOfIntrinsics(Instruction &
I);
145 bool foldShuffleToIdentity(Instruction &
I);
146 bool foldShuffleFromReductions(Instruction &
I);
147 bool foldShuffleChainsToReduce(Instruction &
I);
148 bool foldCastFromReductions(Instruction &
I);
149 bool foldSignBitReductionCmp(Instruction &
I);
150 bool foldReductionZeroTest(Instruction &
I);
151 bool foldICmpEqZeroVectorReduce(Instruction &
I);
152 bool foldEquivalentReductionCmp(Instruction &
I);
153 bool foldReduceAddCmpZero(Instruction &
I);
154 bool foldSelectShuffle(Instruction &
I,
bool FromReduction =
false);
155 bool foldInterleaveIntrinsics(Instruction &
I);
156 bool foldDeinterleaveIntrinsics(Instruction &
I);
157 bool foldBitcastOfVPLoad(Instruction &
I);
158 bool foldBitOrderReverseAndSwap(Instruction &
I);
159 bool shrinkType(Instruction &
I);
160 bool shrinkLoadForShuffles(Instruction &
I);
161 bool shrinkPhiOfShuffles(Instruction &
I);
162 bool foldInterleaveOfDeinterleaveChains(Instruction &
I);
164 void replaceValue(Instruction &Old,
Value &New,
bool Erase =
true) {
170 Worklist.pushUsersToWorkList(*NewI);
171 Worklist.pushValue(NewI);
188 SmallPtrSet<Value *, 4> Visited;
193 OpI,
nullptr,
nullptr, [&](
Value *
V) {
198 NextInst = NextInst->getNextNode();
203 Worklist.pushUsersToWorkList(*OpI);
204 Worklist.pushValue(OpI);
216 V = BitCast->getOperand(0);
222 return X->getType() ==
Y->getType() &&
231 Load->getFunction()->hasFnAttribute(Attribute::SanitizeMemTag) ||
237 Type *ScalarTy =
Load->getType()->getScalarType();
239 unsigned MinVectorSize =
TTI.getMinVectorRegisterBitWidth();
240 if (!ScalarSize || !MinVectorSize || MinVectorSize % ScalarSize != 0 ||
247bool VectorCombine::vectorizeLoadInsert(
Instruction &
I) {
273 Value *SrcPtr =
Load->getPointerOperand()->stripPointerCasts();
276 unsigned MinVecNumElts = MinVectorSize / ScalarSize;
277 auto *MinVecTy = VectorType::get(ScalarTy, MinVecNumElts,
false);
278 unsigned OffsetEltIndex = 0;
289 unsigned OffsetBitWidth =
DL->getIndexTypeSizeInBits(SrcPtr->
getType());
290 APInt
Offset(OffsetBitWidth, 0);
300 uint64_t ScalarSizeInBytes = ScalarSize / 8;
301 if (
Offset.urem(ScalarSizeInBytes) != 0)
305 APInt OffsetEltIndexAP =
Offset.udiv(ScalarSizeInBytes);
306 if (OffsetEltIndexAP.
uge(MinVecNumElts))
325 unsigned AS =
Load->getPointerAddressSpace();
331 true, HasExtract, CostKind);
344 unsigned OutputNumElts = Ty->getNumElements();
346 assert(OffsetEltIndex < MinVecNumElts &&
"Address offset too big");
347 Mask[0] = OffsetEltIndex;
354 if (OldCost < NewCost || !NewCost.
isValid())
365 replaceValue(
I, *VecLd);
373bool VectorCombine::widenSubvectorLoad(Instruction &
I) {
376 if (!Shuf->isIdentityWithPadding())
382 unsigned OpIndex =
any_of(Shuf->getShuffleMask(), [&NumOpElts](
int M) {
383 return M >= (int)(NumOpElts);
406 unsigned AS =
Load->getPointerAddressSpace();
421 if (OldCost < NewCost || !NewCost.
isValid())
428 replaceValue(
I, *VecLd);
435ExtractElementInst *VectorCombine::getShuffleExtract(
436 ExtractElementInst *Ext0, ExtractElementInst *Ext1,
440 assert(Index0C && Index1C &&
"Expected constant extract indexes");
442 unsigned Index0 = Index0C->getZExtValue();
443 unsigned Index1 = Index1C->getZExtValue();
446 if (Index0 == Index1)
470 if (PreferredExtractIndex == Index0)
472 if (PreferredExtractIndex == Index1)
476 return Index0 > Index1 ? Ext0 : Ext1;
484bool VectorCombine::isExtractExtractCheap(ExtractElementInst *Ext0,
485 ExtractElementInst *Ext1,
486 const Instruction &
I,
487 ExtractElementInst *&ConvertToShuffle,
488 unsigned PreferredExtractIndex) {
491 assert(Ext0IndexC && Ext1IndexC &&
"Expected constant extract indexes");
493 unsigned Opcode =
I.getOpcode();
506 assert((Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) &&
507 "Expected a compare");
517 unsigned Ext0Index = Ext0IndexC->getZExtValue();
518 unsigned Ext1Index = Ext1IndexC->getZExtValue();
532 unsigned BestExtIndex = Extract0Cost > Extract1Cost ? Ext0Index : Ext1Index;
533 unsigned BestInsIndex = Extract0Cost > Extract1Cost ? Ext1Index : Ext0Index;
534 InstructionCost CheapExtractCost = std::min(Extract0Cost, Extract1Cost);
539 if (Ext0Src == Ext1Src && Ext0Index == Ext1Index) {
544 bool HasUseTax = Ext0 == Ext1 ? !Ext0->
hasNUses(2)
546 OldCost = CheapExtractCost + ScalarOpCost;
547 NewCost = VectorOpCost + CheapExtractCost + HasUseTax * CheapExtractCost;
551 OldCost = Extract0Cost + Extract1Cost + ScalarOpCost;
552 NewCost = VectorOpCost + CheapExtractCost +
557 ConvertToShuffle = getShuffleExtract(Ext0, Ext1, PreferredExtractIndex);
558 if (ConvertToShuffle) {
559 if (IsBinOp && Opts.disable_binop_extract_shuffle)
570 SmallVector<int> ShuffleMask(FixedVecTy->getNumElements(),
572 ShuffleMask[BestInsIndex] = BestExtIndex;
574 VecTy, VecTy, CostKind, ShuffleMask, 0,
575 nullptr, {ConvertToShuffle});
578 VecTy, VecTy, CostKind, {}, 0,
nullptr,
583 LLVM_DEBUG(
dbgs() <<
"Found a binop of extractions: " <<
I <<
"\n OldCost: "
584 << OldCost <<
" vs NewCost: " << NewCost <<
"\n");
589 return OldCost < NewCost;
601 ShufMask[NewIndex] = OldIndex;
602 return Builder.CreateShuffleVector(Vec, ShufMask,
"shift");
654 V1,
"foldExtExtBinop");
659 VecBOInst->copyIRFlags(&
I);
665bool VectorCombine::foldExtractExtract(Instruction &
I) {
681 V0->getType() !=
V1->getType())
686 unsigned NumElts = FixedVecTy->getNumElements();
687 if (
C0 >= NumElts ||
C1 >= NumElts)
703 ExtractElementInst *ExtractToChange;
704 if (isExtractExtractCheap(Ext0, Ext1,
I, ExtractToChange, InsertIndex))
710 if (ExtractToChange) {
711 unsigned CheapExtractIdx = ExtractToChange == Ext0 ?
C1 :
C0;
716 if (ExtractToChange == Ext0)
725 ? foldExtExtCmp(ExtOp0, ExtOp1, ExtIndex,
I)
726 : foldExtExtBinop(ExtOp0, ExtOp1, ExtIndex,
I);
727 replaceValue(
I, *NewExt);
733bool VectorCombine::foldInsExtFNeg(Instruction &
I) {
752 auto *DstVecScalarTy = DstVecTy->getScalarType();
754 if (!SrcVecTy || DstVecScalarTy != SrcVecTy->getScalarType())
759 unsigned NumDstElts = DstVecTy->getNumElements();
760 unsigned NumSrcElts = SrcVecTy->getNumElements();
761 if (ExtIdx > NumSrcElts || InsIdx >= NumDstElts || NumDstElts == 1)
767 SmallVector<int>
Mask(NumDstElts);
768 std::iota(
Mask.begin(),
Mask.end(), 0);
769 Mask[InsIdx] = (ExtIdx % NumDstElts) + NumDstElts;
783 DstVecTy, CostKind, Mask);
785 bool NeedLenChg = SrcVecTy->getNumElements() != NumDstElts;
788 SmallVector<int> SrcMask;
791 SrcMask[ExtIdx % NumDstElts] = ExtIdx;
793 DstVecTy, SrcVecTy, CostKind, SrcMask);
797 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
799 if (NewCost > OldCost)
802 Value *NewShuf, *LenChgShuf =
nullptr;
814 replaceValue(
I, *NewShuf);
820bool VectorCombine::foldInsExtBinop(Instruction &
I) {
821 BinaryOperator *VecBinOp, *SclBinOp;
853 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
855 if (NewCost > OldCost)
866 NewInst->copyIRFlags(VecBinOp);
867 NewInst->andIRFlags(SclBinOp);
870 replaceValue(
I, *NewBO);
876bool VectorCombine::foldBitOpOfCastops(Instruction &
I) {
879 if (!BinOp || !BinOp->isBitwiseLogicOp())
885 if (!LHSCast || !RHSCast) {
886 LLVM_DEBUG(
dbgs() <<
" One or both operands are not cast instructions\n");
892 if (CastOpcode != RHSCast->getOpcode())
896 switch (CastOpcode) {
897 case Instruction::BitCast:
898 case Instruction::Trunc:
899 case Instruction::SExt:
900 case Instruction::ZExt:
906 Value *LHSSrc = LHSCast->getOperand(0);
907 Value *RHSSrc = RHSCast->getOperand(0);
913 auto *SrcTy = LHSSrc->
getType();
914 auto *DstTy =
I.getType();
917 if (CastOpcode != Instruction::BitCast &&
922 if (!SrcTy->getScalarType()->isIntegerTy() ||
923 !DstTy->getScalarType()->isIntegerTy())
938 LHSCastCost + RHSCastCost;
949 if (!LHSCast->hasOneUse())
950 NewCost += LHSCastCost;
951 if (!RHSCast->hasOneUse())
952 NewCost += RHSCastCost;
955 <<
" NewCost=" << NewCost <<
"\n");
957 if (NewCost > OldCost)
962 BinOp->getName() +
".inner");
964 NewBinOp->copyIRFlags(BinOp);
976 replaceValue(
I, *Result);
985bool VectorCombine::foldBitOpOfCastConstant(Instruction &
I) {
1001 switch (CastOpcode) {
1002 case Instruction::BitCast:
1003 case Instruction::ZExt:
1004 case Instruction::SExt:
1005 case Instruction::Trunc:
1011 Value *LHSSrc = LHSCast->getOperand(0);
1013 auto *SrcTy = LHSSrc->
getType();
1014 auto *DstTy =
I.getType();
1017 if (CastOpcode != Instruction::BitCast &&
1022 if (!SrcTy->getScalarType()->isIntegerTy() ||
1023 !DstTy->getScalarType()->isIntegerTy())
1027 PreservedCastFlags RHSFlags;
1052 if (!LHSCast->hasOneUse())
1053 NewCost += LHSCastCost;
1055 LLVM_DEBUG(
dbgs() <<
"foldBitOpOfCastConstant: OldCost=" << OldCost
1056 <<
" NewCost=" << NewCost <<
"\n");
1058 if (NewCost > OldCost)
1063 LHSSrc, InvC,
I.getName() +
".inner");
1065 NewBinOp->copyIRFlags(&
I);
1083 replaceValue(
I, *Result);
1090bool VectorCombine::foldBitcastShuffle(Instruction &
I) {
1104 if (!DestTy || !SrcTy)
1107 unsigned DestEltSize = DestTy->getScalarSizeInBits();
1108 unsigned SrcEltSize = SrcTy->getScalarSizeInBits();
1109 if (SrcTy->getPrimitiveSizeInBits() % DestEltSize != 0)
1119 if (!(BCTy0 && BCTy0->getElementType() == DestTy->getElementType()) &&
1120 !(BCTy1 && BCTy1->getElementType() == DestTy->getElementType()))
1124 SmallVector<int, 16> NewMask;
1125 if (DestEltSize <= SrcEltSize) {
1128 if (SrcEltSize % DestEltSize != 0)
1130 unsigned ScaleFactor = SrcEltSize / DestEltSize;
1135 if (DestEltSize % SrcEltSize != 0)
1137 unsigned ScaleFactor = DestEltSize / SrcEltSize;
1144 unsigned NumSrcElts = SrcTy->getPrimitiveSizeInBits() / DestEltSize;
1145 auto *NewShuffleTy =
1147 auto *OldShuffleTy =
1149 unsigned NumOps = IsUnary ? 1 : 2;
1159 TargetTransformInfo::CastContextHint::None,
1164 TargetTransformInfo::CastContextHint::None,
1167 LLVM_DEBUG(
dbgs() <<
"Found a bitcasted shuffle: " <<
I <<
"\n OldCost: "
1168 << OldCost <<
" vs NewCost: " << NewCost <<
"\n");
1170 if (NewCost > OldCost || !NewCost.
isValid())
1178 replaceValue(
I, *Shuf);
1185bool VectorCombine::scalarizeOpOrCmp(Instruction &
I) {
1190 if (!UO && !BO && !CI && !
II)
1198 if (Arg->getType() !=
II->getType() &&
1208 for (User *U :
I.users())
1215 std::optional<uint64_t>
Index;
1217 auto Ops =
II ?
II->args() :
I.operands();
1226 if (OpTy->getElementCount().getKnownMinValue() <= InsIdx)
1232 else if (InsIdx != *Index)
1249 if (!
Index.has_value())
1253 Type *ScalarTy = VecTy->getScalarType();
1254 assert(VecTy->isVectorTy() &&
1257 "Unexpected types for insert element into binop or cmp");
1259 unsigned Opcode =
I.getOpcode();
1267 }
else if (UO || BO) {
1271 IntrinsicCostAttributes ScalarICA(
1272 II->getIntrinsicID(), ScalarTy,
1275 IntrinsicCostAttributes VectorICA(
1276 II->getIntrinsicID(), VecTy,
1283 Value *NewVecC =
nullptr;
1285 NewVecC =
simplifyCmpInst(CI->getPredicate(), VecCs[0], VecCs[1], SQ);
1288 simplifyUnOp(UO->getOpcode(), VecCs[0], UO->getFastMathFlags(), SQ);
1290 NewVecC =
simplifyBinOp(BO->getOpcode(), VecCs[0], VecCs[1], SQ);
1302 CostKind, *Index, NewVecC);
1304 for (
auto [Idx,
Op, VecC, Scalar] :
enumerate(
Ops, VecCs, ScalarOps)) {
1306 II->getIntrinsicID(), Idx, &
TTI)))
1309 Instruction::InsertElement, VecTy, CostKind, *Index, VecC, Scalar);
1310 OldCost += InsertCost;
1311 NewCost += !
Op->hasOneUse() * InsertCost;
1315 if (OldCost < NewCost || !NewCost.
isValid())
1325 ++NumScalarIntrinsic;
1328 for (
auto [OpIdx, Scalar, VecC] :
enumerate(ScalarOps, VecCs))
1340 ScalarOps[1], FPMO->getFastMathFlags(),
1341 CI->getName() +
".scalar");
1344 ScalarOps[1], CI->getName() +
".scalar");
1348 UO->getName() +
".scalar");
1350 if (OverflowingBinaryOperator *OBO =
1353 BO->getOpcode(), ScalarOps[0], ScalarOps[1], OBO->hasNoUnsignedWrap(),
1354 OBO->hasNoSignedWrap(), BO->getName() +
".scalar");
1357 BO->getName() +
".scalar", PDI->isDisjoint());
1358 }
else if (PossiblyExactOperator *PEO =
1362 PEO->isExact(), BO->getName() +
".scalar");
1365 ScalarOps[1], FPMO->getFastMathFlags(),
1366 BO->getName() +
".scalar");
1369 BO->getName() +
".scalar");
1374 FMF = FPMO->getFastMathFlags();
1376 FMF,
II->getName() +
".scalar");
1380 replaceValue(
I, *Insert);
1387bool VectorCombine::foldExtractedCmps(Instruction &
I) {
1392 if (!BI || !
I.getType()->isIntegerTy(1))
1397 Value *
B0 =
I.getOperand(0), *
B1 =
I.getOperand(1);
1400 CmpPredicate
P0,
P1;
1419 ExtractElementInst *ConvertToShuf = getShuffleExtract(Ext0, Ext1, CostKind);
1422 assert((ConvertToShuf == Ext0 || ConvertToShuf == Ext1) &&
1423 "Unknown ExtractElementInst");
1428 unsigned CmpOpcode =
1434 if (Index0 >= VecTy->getNumElements() || Index1 >= VecTy->getNumElements())
1446 Ext0Cost + Ext1Cost + CmpCost * 2 +
1452 int CheapIndex = ConvertToShuf == Ext0 ? Index1 : Index0;
1453 int ExpensiveIndex = ConvertToShuf == Ext0 ? Index0 : Index1;
1458 ShufMask[CheapIndex] = ExpensiveIndex;
1460 CmpTy, CostKind, ShufMask);
1463 NewCost += Ext0->
hasOneUse() ? 0 : Ext0Cost;
1464 NewCost += Ext1->
hasOneUse() ? 0 : Ext1Cost;
1469 if (OldCost < NewCost || !NewCost.
isValid())
1479 Value *
LHS = ConvertToShuf == Ext0 ? Shuf : VCmp;
1480 Value *
RHS = ConvertToShuf == Ext0 ? VCmp : Shuf;
1483 replaceValue(
I, *NewExt);
1510bool VectorCombine::foldSelectsFromBitcast(Instruction &
I) {
1517 if (!SrcVecTy || !DstVecTy)
1527 if (SrcEltBits != 32 && SrcEltBits != 64)
1530 if (!DstEltTy->
isIntegerTy() || DstEltBits >= SrcEltBits)
1547 if (!ScalarSelCost.
isValid() || ScalarSelCost == 0)
1550 unsigned MinSelects = (VecSelCost.
getValue() / ScalarSelCost.
getValue()) + 1;
1553 if (!BC->hasNUsesOrMore(MinSelects))
1558 DenseMap<Value *, SmallVector<SelectInst *, 8>> CondToSelects;
1560 for (User *U : BC->users()) {
1565 for (User *ExtUser : Ext->users()) {
1569 Cond->getType()->isIntegerTy(1))
1574 if (CondToSelects.
empty())
1577 bool MadeChange =
false;
1578 Value *SrcVec = BC->getOperand(0);
1581 for (
auto [
Cond, Selects] : CondToSelects) {
1583 if (Selects.size() < MinSelects) {
1584 LLVM_DEBUG(
dbgs() <<
"VectorCombine: foldSelectsFromBitcast not "
1585 <<
"profitable (VecCost=" << VecSelCost
1586 <<
", ScalarCost=" << ScalarSelCost
1587 <<
", NumSelects=" << Selects.size() <<
")\n");
1592 auto InsertPt = std::next(BC->getIterator());
1596 InsertPt = std::next(CondInst->getIterator());
1604 for (SelectInst *Sel : Selects) {
1606 Value *
Idx = Ext->getIndexOperand();
1610 replaceValue(*Sel, *NewExt);
1615 <<
" selects into vector select\n");
1629 unsigned ReductionOpc =
1635 CostBeforeReduction =
1636 TTI.getCastInstrCost(RedOp->getOpcode(), VecRedTy, ExtType,
1638 CostAfterReduction =
1639 TTI.getExtendedReductionCost(ReductionOpc, IsUnsigned,
II.getType(),
1643 if (RedOp &&
II.getIntrinsicID() == Intrinsic::vector_reduce_add &&
1649 (Op0->
getOpcode() == RedOp->getOpcode() || Op0 == Op1)) {
1656 TTI.getCastInstrCost(Op0->
getOpcode(), MulType, ExtType,
1659 TTI.getArithmeticInstrCost(Instruction::Mul, MulType, CostKind);
1661 TTI.getCastInstrCost(RedOp->getOpcode(), VecRedTy, MulType,
1664 CostBeforeReduction = ExtCost * 2 + MulCost + Ext2Cost;
1665 CostAfterReduction =
TTI.getMulAccReductionCost(
1666 IsUnsigned, ReductionOpc,
II.getType(), ExtType, CostKind);
1669 CostAfterReduction =
TTI.getArithmeticReductionCost(ReductionOpc, VecRedTy,
1670 std::nullopt, CostKind);
1673bool VectorCombine::foldBinopOfReductions(Instruction &
I) {
1676 if (BinOpOpc == Instruction::Sub)
1677 ReductionIID = Intrinsic::vector_reduce_add;
1681 if (ReductionIID == Intrinsic::vector_reduce_fadd ||
1682 ReductionIID == Intrinsic::vector_reduce_fmul)
1685 auto checkIntrinsicAndGetItsArgument = [](
Value *
V,
1690 if (
II->getIntrinsicID() == IID &&
II->hasOneUse())
1691 return II->getArgOperand(0);
1695 Value *
V0 = checkIntrinsicAndGetItsArgument(
I.getOperand(0), ReductionIID);
1698 Value *
V1 = checkIntrinsicAndGetItsArgument(
I.getOperand(1), ReductionIID);
1703 if (
V1->getType() != VTy)
1707 unsigned ReductionOpc =
1720 CostOfRedOperand0 + CostOfRedOperand1 +
1723 if (NewCost >= OldCost || !NewCost.
isValid())
1727 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
1730 if (BinOpOpc == Instruction::Or)
1737 replaceValue(
I, *Rdx);
1747 unsigned NumScanned = 0;
1750 ++NumScanned > Opts.vector_combine_max_scan_instrs;
1762class ScalarizationResult {
1763 enum class StatusTy { Unsafe,
Safe, SafeWithFreeze };
1768 ScalarizationResult(StatusTy Status,
Value *ToFreeze =
nullptr)
1769 : Status(Status), ToFreeze(ToFreeze) {}
1772 ScalarizationResult(
const ScalarizationResult &
Other) =
default;
1773 ~ScalarizationResult() {
1774 assert(!ToFreeze &&
"freeze() not called with ToFreeze being set");
1777 static ScalarizationResult unsafe() {
return {StatusTy::Unsafe}; }
1778 static ScalarizationResult safe() {
return {StatusTy::Safe}; }
1779 static ScalarizationResult safeWithFreeze(
Value *ToFreeze) {
1780 return {StatusTy::SafeWithFreeze, ToFreeze};
1784 bool isSafe()
const {
return Status == StatusTy::Safe; }
1786 bool isUnsafe()
const {
return Status == StatusTy::Unsafe; }
1789 bool isSafeWithFreeze()
const {
return Status == StatusTy::SafeWithFreeze; }
1794 Status = StatusTy::Unsafe;
1798 void freeze(IRBuilderBase &Builder, Instruction &UserI) {
1799 assert(isSafeWithFreeze() &&
1800 "should only be used when freezing is required");
1802 "UserI must be a user of ToFreeze");
1803 IRBuilder<>::InsertPointGuard Guard(Builder);
1808 if (
U.get() == ToFreeze)
1823 uint64_t NumElements = VecTy->getElementCount().getKnownMinValue();
1824 unsigned IntWidth = Idx->getType()->getScalarSizeInBits();
1827 if (
C->getValue().ult(NumElements))
1828 return ScalarizationResult::safe();
1829 return ScalarizationResult::unsafe();
1834 return ScalarizationResult::unsafe();
1837 APInt MaxElts(IntWidth, NumElements);
1844 return ScalarizationResult::safe();
1845 return ScalarizationResult::unsafe();
1858 if (ValidIndices.
contains(IdxRange))
1859 return ScalarizationResult::safeWithFreeze(IdxBase);
1860 return ScalarizationResult::unsafe();
1880 unsigned GEPBits = GEPIndexTy->getBitWidth();
1881 uint64_t NumElements = VecTy->getElementCount().getKnownMinValue();
1883 uint64_t MaxLane = NumElements - 1;
1885 if (
C->getValue().uge(NumElements))
1887 MaxLane =
C->getZExtValue();
1891 if (!
DL.typeSizeEqualsStoreSize(
ElemTy))
1911 unsigned WideBits = std::max(GEPBits, 128u);
1912 APInt MaxLaneValue(WideBits, MaxLane);
1913 APInt ByteOffset = MaxLaneValue;
1918 if (ByteOffset.
ugt(MaxGEPOffset))
1929 unsigned SrcBits = Idx->getType()->getIntegerBitWidth();
1931 if (SrcBits >= DstBits)
1934 return Builder.CreateZExt(Idx, GEPIndexTy, Idx->getName() +
".gepidx");
1946 C->getZExtValue() *
DL.getTypeStoreSize(ScalarType));
1983bool VectorCombine::foldInsertElementsToStores(Instruction &
I) {
1998 if (!
Insert->hasOneUse())
2006 if (InsertElements.
empty())
2011 std::reverse(InsertElements.
begin(), InsertElements.
end());
2020 if (InsertElements.
size() == FVT->getNumElements()) {
2021 Value *FirstVal = InsertElements.
front().first;
2022 if (
all_of(InsertElements,
2023 [FirstVal](
const auto &Elt) {
return Elt.first == FirstVal; }))
2027 Value *SrcAddr =
Load->getPointerOperand()->stripPointerCasts();
2032 if (!
Load->isSimple() ||
Load->getParent() !=
SI->getParent() ||
2033 !
DL->typeSizeEqualsStoreSize(
Load->getType()->getScalarType()) ||
2034 SrcAddr !=
SI->getPointerOperand()->stripPointerCasts())
2044 for (
auto [InsertVal, Idx] : InsertElements) {
2045 auto ScalarizableIdx =
2047 if (ScalarizableIdx.isUnsafe())
2053 ScalarizableIdx.discard();
2059 ScalarizableIdx.discard();
2063 Instruction::Store,
SI->getValueOperand()->getType(),
SI->getAlign(),
2064 SI->getPointerAddressSpace(), CostKind);
2066 if (
Load->hasOneUse())
2069 Load->getPointerAddressSpace(), CostKind);
2071 for (
auto [InsertVal, Idx] : InsertElements) {
2074 Index = CIdx->getZExtValue();
2085 for (
auto [InsertVal, Idx] : InsertElements) {
2088 const Value *GEPIndices[] = {ConstantInt::get(
Idx->getType(), 0),
Idx};
2090 CostKind, InsertVal->
getType());
2093 for (
auto [InsertVal, Idx] : InsertElements) {
2095 std::max(
SI->getAlign(),
Load->getAlign()), InsertVal->
getType(), Idx,
2100 SI->getPointerAddressSpace(), CostKind);
2103 LLVM_DEBUG(
dbgs() <<
"Found an insert-elements vector store scalarization "
2106 <<
" NumInserts: " << InsertElements.size() <<
"\n"
2107 <<
" OldCost: " << OldCost <<
" vs NewCost: " << NewCost
2110 if (OldCost <= NewCost)
2113 for (
auto [InsertVal, Idx] : InsertElements) {
2114 auto ScalarizableIdx =
2116 assert(!ScalarizableIdx.isUnsafe() &&
"already checked above");
2118 if (ScalarizableIdx.isSafeWithFreeze())
2123 StoreInst *LastStore =
nullptr;
2124 for (
auto [InsertVal, Idx] : InsertElements) {
2125 auto ScalarizableIdx =
2127 if (ScalarizableIdx.isUnsafe())
2130 IntegerType *GEPIndexTy =
2135 SI->getValueOperand()->getType(),
SI->getPointerOperand(),
2136 {ConstantInt::get(GEPIdx->getType(), 0), GEPIdx});
2143 LastStore->
setMetadata(LLVMContext::MD_invariant_group,
nullptr);
2145 std::max(
SI->getAlign(),
Load->getAlign()), InsertVal->
getType(), Idx,
2150 replaceValue(
I, *LastStore);
2157bool VectorCombine::scalarizeLoad(Instruction &
I) {
2167 if (!LI->isSimple() || !
DL->typeSizeEqualsStoreSize(VecTy->getScalarType()))
2170 bool AllExtracts =
true;
2171 bool AllBitcasts =
true;
2173 unsigned NumInstChecked = 0;
2178 for (User *U : LI->users()) {
2180 if (!UI || UI->getParent() != LI->getParent())
2185 if (UI->use_empty())
2189 AllExtracts =
false;
2191 AllBitcasts =
false;
2195 for (Instruction &
I :
2196 make_range(std::next(LI->getIterator()), UI->getIterator())) {
2199 if (NumInstChecked == Opts.vector_combine_max_scan_instrs ||
2200 I.mayWriteToMemory())
2204 LastCheckedInst = UI;
2209 return scalarizeLoadExtract(LI, VecTy, Ptr);
2211 return scalarizeLoadBitcast(LI, VecTy, Ptr);
2216bool VectorCombine::scalarizeLoadExtract(LoadInst *LI, VectorType *VecTy,
2221 DenseMap<ExtractElementInst *, ScalarizationResult> NeedFreeze;
2222 DenseMap<ExtractElementInst *, IntegerType *> GEPIndexInfos;
2225 for (
auto &Pair : NeedFreeze)
2226 Pair.second.discard();
2234 for (User *U : LI->
users()) {
2239 if (ScalarIdx.isUnsafe())
2245 ScalarIdx.discard();
2251 if (ScalarIdx.isSafeWithFreeze()) {
2252 NeedFreeze.try_emplace(UI, ScalarIdx);
2253 ScalarIdx.discard();
2259 Index ?
Index->getZExtValue() : -1);
2264 nullptr,
nullptr, CostKind);
2265 if (!Index && UI->getIndexOperand()->getType()->getIntegerBitWidth() <
2268 Instruction::ZExt, GEPIndex, UI->getIndexOperand()->getType(),
2272 LLVM_DEBUG(
dbgs() <<
"Found all extractions of a vector load: " << *LI
2273 <<
"\n LoadExtractCost: " << OriginalCost
2274 <<
" vs ScalarizedCost: " << ScalarizedCost <<
"\n");
2276 if (ScalarizedCost > OriginalCost)
2278 if (ScalarizedCost == OriginalCost && !LI->
hasOneUse())
2285 Type *ElemType = VecTy->getElementType();
2288 for (User *U : LI->
users()) {
2290 Value *
Idx = EI->getIndexOperand();
2293 if (
auto It = NeedFreeze.find(EI); It != NeedFreeze.end())
2297 auto It = GEPIndexInfos.
find(EI);
2299 "Missing scalarized GEP index information");
2302 VecTy, Ptr, {ConstantInt::get(GEPIdx->
getType(), 0), GEPIdx});
2304 Builder.
CreateLoad(ElemType,
GEP, EI->getName() +
".scalar"));
2306 Align ScalarOpAlignment =
2308 NewLoad->setAlignment(ScalarOpAlignment);
2311 size_t Offset = ConstIdx->getZExtValue() *
DL->getTypeStoreSize(ElemType);
2316 replaceValue(*EI, *NewLoad,
false);
2319 FailureGuard.release();
2324bool VectorCombine::scalarizeLoadBitcast(LoadInst *LI, VectorType *VecTy,
2333 Type *TargetScalarType =
nullptr;
2334 unsigned VecBitWidth =
DL->getTypeSizeInBits(VecTy);
2336 for (User *U : LI->
users()) {
2339 Type *DestTy = BC->getDestTy();
2343 unsigned DestBitWidth =
DL->getTypeSizeInBits(DestTy);
2344 if (DestBitWidth != VecBitWidth)
2348 if (!TargetScalarType)
2349 TargetScalarType = DestTy;
2350 else if (TargetScalarType != DestTy)
2358 if (!TargetScalarType)
2366 LLVM_DEBUG(
dbgs() <<
"Found vector load feeding only bitcasts: " << *LI
2367 <<
"\n OriginalCost: " << OriginalCost
2368 <<
" vs ScalarizedCost: " << ScalarizedCost <<
"\n");
2370 if (ScalarizedCost >= OriginalCost)
2381 ScalarLoad->copyMetadata(*LI);
2384 for (User *U : LI->
users()) {
2386 replaceValue(*BC, *ScalarLoad,
false);
2392bool VectorCombine::scalarizeExtExtract(Instruction &
I) {
2407 Type *ScalarDstTy = DstTy->getElementType();
2408 if (
DL->getTypeSizeInBits(SrcTy) !=
DL->getTypeSizeInBits(ScalarDstTy))
2414 unsigned ExtCnt = 0;
2415 bool ExtLane0 =
false;
2416 for (User *U : Ext->users()) {
2422 if (Idx >= SrcTy->getNumElements())
2434 Instruction::And, ScalarDstTy, CostKind,
2437 (ExtCnt - ExtLane0) *
2439 Instruction::LShr, ScalarDstTy, CostKind,
2442 if (ScalarCost > VectorCost)
2445 Value *ScalarV = Ext->getOperand(0);
2452 SmallDenseSet<ConstantInt *, 8> ExtractedLanes;
2453 bool AllExtractsTriggerUB =
true;
2454 ExtractElementInst *LastExtract =
nullptr;
2456 for (User *U : Ext->users()) {
2459 AllExtractsTriggerUB =
false;
2463 if (!LastExtract || LastExtract->
comesBefore(Extract))
2464 LastExtract = Extract;
2466 if (ExtractedLanes.
size() != DstTy->getNumElements() ||
2467 !AllExtractsTriggerUB ||
2475 uint64_t SrcEltSizeInBits =
DL->getTypeSizeInBits(SrcTy->getElementType());
2476 uint64_t TotalBits =
DL->getTypeSizeInBits(SrcTy);
2479 Value *
Mask = ConstantInt::get(PackedTy, EltBitMask);
2480 for (User *U : Ext->users()) {
2486 ? (TotalBits - SrcEltSizeInBits -
Idx * SrcEltSizeInBits)
2487 : (
Idx * SrcEltSizeInBits);
2490 U->replaceAllUsesWith(
And);
2498bool VectorCombine::foldConcatOfBoolMasks(Instruction &
I) {
2499 Type *Ty =
I.getType();
2504 if (
DL->isBigEndian())
2531 if (ShAmtX > ShAmtY) {
2539 uint64_t ShAmtDiff = ShAmtY - ShAmtX;
2540 unsigned NumSHL = (ShAmtX > 0) + (ShAmtY > 0);
2545 MaskTy->getNumElements() != ShAmtDiff ||
2546 MaskTy->getNumElements() > (
BitWidth / 2))
2551 Type::getIntNTy(Ty->
getContext(), ConcatTy->getNumElements());
2552 auto *MaskIntTy = Type::getIntNTy(Ty->
getContext(), ShAmtDiff);
2555 std::iota(ConcatMask.begin(), ConcatMask.end(), 0);
2569 MaskTy, CostKind, ConcatMask);
2572 if (Ty != ConcatIntTy)
2578 LLVM_DEBUG(
dbgs() <<
"Found a concatenation of bitcasted bool masks: " <<
I
2579 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
2582 if (NewCost > OldCost)
2591 if (Ty != ConcatIntTy) {
2599 replaceValue(
I, *Result);
2605bool VectorCombine::foldPermuteOfBinops(Instruction &
I) {
2606 BinaryOperator *BinOp;
2607 ArrayRef<int> OuterMask;
2615 Value *Op00, *Op01, *Op10, *Op11;
2616 ArrayRef<int> Mask0, Mask1;
2621 if (!Match0 && !Match1)
2634 if (!ShuffleDstTy || !BinOpTy || !Op0Ty || !Op1Ty)
2637 unsigned NumSrcElts = BinOpTy->getNumElements();
2642 any_of(OuterMask, [NumSrcElts](
int M) {
return M >= (int)NumSrcElts; }))
2646 SmallVector<int> NewMask0, NewMask1;
2647 for (
int M : OuterMask) {
2648 if (M < 0 || M >= (
int)NumSrcElts) {
2652 NewMask0.
push_back(Match0 ? Mask0[M] : M);
2653 NewMask1.
push_back(Match1 ? Mask1[M] : M);
2657 unsigned NumOpElts = Op0Ty->getNumElements();
2658 bool IsIdentity0 = ShuffleDstTy == Op0Ty &&
2659 all_of(NewMask0, [NumOpElts](
int M) {
return M < (int)NumOpElts; }) &&
2661 bool IsIdentity1 = ShuffleDstTy == Op1Ty &&
2662 all_of(NewMask1, [NumOpElts](
int M) {
return M < (int)NumOpElts; }) &&
2671 ShuffleDstTy, BinOpTy, CostKind, OuterMask,
2672 0,
nullptr, {BinOp}, &
I);
2674 NewCost += BinOpCost;
2680 OldCost += Shuf0Cost;
2682 NewCost += Shuf0Cost;
2688 OldCost += Shuf1Cost;
2690 NewCost += Shuf1Cost;
2698 Op0Ty, CostKind, NewMask0, 0,
nullptr, {Op00, Op01});
2702 Op1Ty, CostKind, NewMask1, 0,
nullptr, {Op10, Op11});
2704 LLVM_DEBUG(
dbgs() <<
"Found a shuffle feeding a shuffled binop: " <<
I
2705 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
2709 if (NewCost > OldCost)
2720 NewInst->copyIRFlags(BinOp);
2722 replaceValue(
I, *NewBO);
2728bool VectorCombine::foldShuffleOfBinops(Instruction &
I) {
2729 ArrayRef<int> OldMask;
2736 if (
LHS->getOpcode() !=
RHS->getOpcode())
2740 bool IsCommutative =
false;
2749 IsCommutative = BinaryOperator::isCommutative(BO->getOpcode());
2760 if (!ShuffleDstTy || !BinResTy || !BinOpTy ||
X->getType() !=
Z->getType())
2763 bool SameBinOp =
LHS ==
RHS;
2764 unsigned NumSrcElts = BinOpTy->getNumElements();
2767 if (IsCommutative &&
X != Z &&
Y != W && (
X == W ||
Y == Z))
2770 auto ConvertToUnary = [NumSrcElts](
int &
M) {
2771 if (M >= (
int)NumSrcElts)
2775 SmallVector<int> NewMask0(OldMask);
2784 SmallVector<int> NewMask1(OldMask);
2803 ShuffleDstTy, BinResTy, CostKind, OldMask, 0,
2814 ArrayRef<int> InnerMask;
2816 m_Mask(InnerMask)))) &&
2819 [NumSrcElts](
int M) {
return M < (int)NumSrcElts; })) {
2834 bool ReducedInstCount =
false;
2835 ReducedInstCount |= MergeInner(
X, 0, NewMask0, CostKind,
LHS);
2836 ReducedInstCount |= MergeInner(
Y, 0, NewMask1, CostKind,
LHS);
2837 ReducedInstCount |= MergeInner(Z, NumSrcElts, NewMask0, CostKind,
RHS);
2838 ReducedInstCount |= MergeInner(W, NumSrcElts, NewMask1, CostKind,
RHS);
2839 bool SingleSrcBinOp = (
X ==
Y) && (Z == W) && (NewMask0 == NewMask1);
2851 I.getType()->getScalarType()->isIntegerTy(1) &&
2855 auto *ShuffleCmpTy =
2858 SK0, ShuffleCmpTy, BinOpTy, CostKind, NewMask0, 0,
nullptr, {
X,
Z});
2859 if (!SingleSrcBinOp)
2861 NewMask1, 0,
nullptr, {
Y,
W});
2865 CostKind, Op0Info, Op1Info);
2869 PredLHS, CostKind, Op0Info, Op1Info);
2879 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
2886 if (ReducedInstCount ? (NewCost > OldCost) : (NewCost >= OldCost))
2895 : Builder.
CreateCmp(PredLHS, Shuf0, Shuf1);
2899 NewInst->copyIRFlags(
LHS);
2900 NewInst->andIRFlags(
RHS);
2903 replaceValue(
I, *NewBO);
2910bool VectorCombine::foldShuffleOfSelects(Instruction &
I) {
2923 if (!C1VecTy || !C2VecTy || C1VecTy != C2VecTy)
2929 if (((SI0FOp ==
nullptr) != (SI1FOp ==
nullptr)) ||
2930 ((SI0FOp !=
nullptr) &&
2931 (SI0FOp->getFastMathFlags() != SI1FOp->getFastMathFlags())))
2937 auto SelOp = Instruction::Select;
2945 CostSel1 + CostSel2 +
2947 {
I.getOperand(0),
I.getOperand(1)}, &
I);
2951 CostKind, Mask, 0,
nullptr, {C1, C2});
2961 if (!Sel1->hasOneUse())
2962 NewCost += CostSel1;
2963 if (!Sel2->hasOneUse())
2964 NewCost += CostSel2;
2967 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
2969 if (NewCost > OldCost)
2978 NewSel = Builder.
CreateSelectFMF(ShuffleCmp, ShuffleTrue, ShuffleFalse,
2979 SI0FOp->getFastMathFlags());
2981 NewSel = Builder.
CreateSelect(ShuffleCmp, ShuffleTrue, ShuffleFalse);
2983 replaceValue(
I, *NewSel);
2989bool VectorCombine::foldShuffleOfCastops(Instruction &
I) {
2991 ArrayRef<int> OldMask;
3000 if (!
C0 || (IsBinaryShuffle && !
C1))
3007 if (!IsBinaryShuffle && Opcode == Instruction::BitCast)
3010 if (IsBinaryShuffle) {
3011 if (
C0->getSrcTy() !=
C1->getSrcTy())
3014 if (Opcode !=
C1->getOpcode()) {
3016 Opcode = Instruction::SExt;
3025 if (!ShuffleDstTy || !CastDstTy || !CastSrcTy)
3028 unsigned NumSrcElts = CastSrcTy->getNumElements();
3029 unsigned NumDstElts = CastDstTy->getNumElements();
3030 assert((NumDstElts == NumSrcElts || Opcode == Instruction::BitCast) &&
3031 "Only bitcasts expected to alter src/dst element counts");
3035 if (NumDstElts != NumSrcElts && (NumSrcElts % NumDstElts) != 0 &&
3036 (NumDstElts % NumSrcElts) != 0)
3039 SmallVector<int, 16> NewMask;
3040 if (NumSrcElts >= NumDstElts) {
3043 assert(NumSrcElts % NumDstElts == 0 &&
"Unexpected shuffle mask");
3044 unsigned ScaleFactor = NumSrcElts / NumDstElts;
3049 assert(NumDstElts % NumSrcElts == 0 &&
"Unexpected shuffle mask");
3050 unsigned ScaleFactor = NumDstElts / NumSrcElts;
3055 auto *NewShuffleDstTy =
3064 if (IsBinaryShuffle)
3071 OldMask, 0,
nullptr, {}, &
I);
3074 CastSrcTy, CostKind, NewMask);
3077 if (!
C0->hasOneUse())
3079 if (IsBinaryShuffle) {
3084 if (!
C1->hasOneUse())
3089 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
3091 if (NewCost > OldCost)
3095 if (IsBinaryShuffle)
3105 NewInst->copyIRFlags(
C0);
3106 if (IsBinaryShuffle)
3107 NewInst->andIRFlags(
C1);
3110 replaceValue(
I, *Cast);
3120bool VectorCombine::foldShuffleOfShuffles(Instruction &
I) {
3121 ArrayRef<int> OuterMask;
3122 Value *OuterV0, *OuterV1;
3127 ArrayRef<int> InnerMask0, InnerMask1;
3128 Value *X0, *X1, *Y0, *Y1;
3133 if (!Match0 && !Match1)
3138 SmallVector<int, 16> PoisonMask1;
3143 InnerMask1 = PoisonMask1;
3147 X0 = Match0 ? X0 : OuterV0;
3148 Y0 = Match0 ? Y0 : OuterV0;
3149 X1 = Match1 ? X1 : OuterV1;
3150 Y1 = Match1 ? Y1 : OuterV1;
3154 if (!ShuffleDstTy || !ShuffleSrcTy || !ShuffleImmTy ||
3158 unsigned NumSrcElts = ShuffleSrcTy->getNumElements();
3159 unsigned NumImmElts = ShuffleImmTy->getNumElements();
3164 SmallVector<int, 16> NewMask(OuterMask);
3165 Value *NewX =
nullptr, *NewY =
nullptr;
3166 for (
int &M : NewMask) {
3167 Value *Src =
nullptr;
3168 if (0 <= M && M < (
int)NumImmElts) {
3172 Src =
M >= (int)NumSrcElts ? Y0 : X0;
3173 M =
M >= (int)NumSrcElts ? (M - NumSrcElts) :
M;
3175 }
else if (M >= (
int)NumImmElts) {
3180 Src =
M >= (int)NumSrcElts ? Y1 : X1;
3181 M =
M >= (int)NumSrcElts ? (M - NumSrcElts) :
M;
3185 assert(0 <= M && M < (
int)NumSrcElts &&
"Unexpected shuffle mask index");
3194 if (!NewX || NewX == Src) {
3198 if (!NewY || NewY == Src) {
3217 replaceValue(
I, *NewX);
3234 bool IsUnary =
all_of(NewMask, [&](
int M) {
return M < (int)NumSrcElts; });
3240 nullptr, {NewX, NewY});
3242 NewCost += InnerCost0;
3244 NewCost += InnerCost1;
3247 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
3249 if (NewCost > OldCost)
3253 replaceValue(
I, *Shuf);
3269bool VectorCombine::foldShufflesOfLengthChangingShuffles(Instruction &
I) {
3274 unsigned ChainLength = 0;
3275 SmallVector<int>
Mask;
3276 SmallVector<int> YMask;
3286 ArrayRef<int> OuterMask;
3287 Value *OuterV0, *OuterV1;
3288 if (ChainLength != 0 && !Trunk->
hasOneUse())
3291 m_Mask(OuterMask))))
3293 if (OuterV0->
getType() != TrunkType) {
3299 ArrayRef<int> InnerMask0, InnerMask1;
3305 bool Match0Leaf = Match0 && A0->
getType() !=
I.getType();
3306 bool Match1Leaf = Match1 && A1->
getType() !=
I.getType();
3307 if (Match0Leaf == Match1Leaf) {
3313 SmallVector<int> CommutedOuterMask;
3320 for (
int &M : CommutedOuterMask) {
3323 if (M < (
int)NumTrunkElts)
3328 OuterMask = CommutedOuterMask;
3347 int NumLeafElts = YType->getNumElements();
3348 SmallVector<int> LocalYMask(InnerMask1);
3349 for (
int &M : LocalYMask) {
3350 if (M >= NumLeafElts)
3360 Mask.assign(OuterMask);
3361 YMask.
assign(LocalYMask);
3362 OldCost = NewCost = LocalOldCost;
3369 SmallVector<int> NewYMask(YMask);
3371 for (
auto [CombinedM, LeafM] :
llvm::zip(NewYMask, LocalYMask)) {
3372 if (LeafM == -1 || CombinedM == LeafM)
3374 if (CombinedM == -1) {
3384 SmallVector<int> NewMask;
3385 NewMask.
reserve(NumTrunkElts);
3386 for (
int M : Mask) {
3387 if (M < 0 || M >=
static_cast<int>(NumTrunkElts))
3398 YType, CostKind, NewYMask) +
3400 TrunkType, CostKind, NewMask);
3402 if (LocalNewCost >= NewCost && LocalOldCost < LocalNewCost - NewCost)
3406 if (ChainLength == 1) {
3407 dbgs() <<
"Found chain of shuffles fed by length-changing shuffles: "
3410 dbgs() <<
" next chain link: " << *Trunk <<
'\n'
3411 <<
" old cost: " << (OldCost + LocalOldCost)
3412 <<
" new cost: " << LocalNewCost <<
'\n';
3417 OldCost += LocalOldCost;
3418 NewCost = LocalNewCost;
3422 if (ChainLength <= 1)
3430 return M < 0 || M >=
static_cast<int>(NumTrunkElts);
3433 for (
int &M : Mask) {
3434 if (M >=
static_cast<int>(NumTrunkElts))
3435 M = YMask[
M - NumTrunkElts];
3439 replaceValue(
I, *Root);
3446 replaceValue(
I, *Root);
3452bool VectorCombine::foldShuffleOfIntrinsics(Instruction &
I) {
3454 ArrayRef<int> OldMask;
3464 if (IID != II1->getIntrinsicID())
3473 if (!ShuffleDstTy || !II0Ty)
3479 for (
unsigned Idx = 0,
E = II0->arg_size(); Idx !=
E; ++Idx) {
3480 Value *Arg0 = II0->getArgOperand(Idx);
3481 Value *Arg1 = II1->getArgOperand(Idx);
3498 II0Ty, CostKind, OldMask, 0,
nullptr, {II0, II1}, &
I);
3502 SmallDenseSet<std::pair<Value *, Value *>> SeenOperandPairs;
3503 for (
unsigned Idx = 0,
E = II0->arg_size(); Idx !=
E; ++Idx) {
3505 NewArgsTy.
push_back(II0->getArgOperand(Idx)->getType());
3509 ShuffleDstTy->getNumElements());
3511 std::pair<Value *, Value *> OperandPair =
3512 std::make_pair(II0->getArgOperand(Idx), II1->getArgOperand(Idx));
3513 if (!SeenOperandPairs.
insert(OperandPair).second) {
3519 OldMask, 0,
nullptr,
3520 {II0->getArgOperand(Idx), II1->getArgOperand(Idx)});
3523 IntrinsicCostAttributes NewAttr(IID, ShuffleDstTy, NewArgsTy);
3526 if (!II0->hasOneUse())
3528 if (II1 != II0 && !II1->hasOneUse())
3532 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
3535 if (NewCost > OldCost)
3539 SmallDenseMap<std::pair<Value *, Value *>,
Value *> ShuffleCache;
3540 for (
unsigned Idx = 0,
E = II0->arg_size(); Idx !=
E; ++Idx) {
3542 NewArgs.
push_back(II0->getArgOperand(Idx));
3544 std::pair<Value *, Value *> OperandPair =
3545 std::make_pair(II0->getArgOperand(Idx), II1->getArgOperand(Idx));
3546 auto It = ShuffleCache.
find(OperandPair);
3547 if (It != ShuffleCache.
end()) {
3553 II0->getArgOperand(Idx), II1->getArgOperand(Idx), OldMask);
3554 ShuffleCache[OperandPair] = Shuf;
3562 NewInst->copyIRFlags(II0);
3563 NewInst->andIRFlags(II1);
3566 replaceValue(
I, *NewIntrinsic);
3572bool VectorCombine::foldPermuteOfIntrinsic(Instruction &
I) {
3584 if (!ShuffleDstTy || !IntrinsicSrcTy)
3588 unsigned NumSrcElts = IntrinsicSrcTy->getNumElements();
3589 if (
any_of(Mask, [NumSrcElts](
int M) {
return M >= (int)NumSrcElts; }))
3602 IntrinsicSrcTy, CostKind, Mask, 0,
nullptr, {
V0}, &
I);
3606 for (
unsigned I = 0,
E = II0->arg_size();
I !=
E; ++
I) {
3608 NewArgsTy.
push_back(II0->getArgOperand(
I)->getType());
3612 ShuffleDstTy->getNumElements());
3615 ArgTy, VecTy, CostKind, Mask, 0,
nullptr,
3616 {II0->getArgOperand(
I)});
3619 IntrinsicCostAttributes NewAttr(IID, ShuffleDstTy, NewArgsTy);
3624 if (!II0->hasOneUse())
3627 LLVM_DEBUG(
dbgs() <<
"Found a permute of intrinsic: " <<
I <<
"\n OldCost: "
3628 << OldCost <<
" vs NewCost: " << NewCost <<
"\n");
3630 if (NewCost > OldCost)
3635 for (
unsigned I = 0,
E = II0->arg_size();
I !=
E; ++
I) {
3647 NewInst->copyIRFlags(II0);
3649 replaceValue(
I, *NewIntrinsic);
3659 int M = SV->getMaskValue(Lane);
3662 if (
static_cast<unsigned>(M) < NumElts) {
3663 V = SV->getOperand(0);
3666 V = SV->getOperand(1);
3677 auto [U, Lane] = IL;
3690 unsigned NumElts = Ty->getNumElements();
3691 if (Item.
size() == NumElts || NumElts == 1 || Item.
size() % NumElts != 0)
3697 std::iota(ConcatMask.
begin(), ConcatMask.
end(), 0);
3700 Ty, CostKind, ConcatMask) != 0)
3703 unsigned NumSlices = Item.
size() / NumElts;
3708 for (
unsigned Slice = 0; Slice < NumSlices; ++Slice) {
3709 Value *SliceV = Item[Slice * NumElts].first;
3710 if (!SliceV || SliceV->
getType() != Ty)
3712 for (
unsigned Elt = 0; Elt < NumElts; ++Elt) {
3713 auto [
V, Lane] = Item[Slice * NumElts + Elt];
3714 if (Lane !=
static_cast<int>(Elt) || SliceV !=
V)
3723 const DenseSet<std::pair<Value *, Use *>> &IdentityLeafs,
3724 const DenseSet<std::pair<Value *, Use *>> &SplatLeafs,
3725 const DenseSet<std::pair<Value *, Use *>> &ConcatLeafs,
3728 auto [FrontV, FrontLane] = Item.
front();
3730 if (IdentityLeafs.contains(std::make_pair(FrontV, From))) {
3733 if (SplatLeafs.contains(std::make_pair(FrontV, From))) {
3735 return Builder.CreateShuffleVector(FrontV, Mask);
3737 if (ConcatLeafs.contains(std::make_pair(FrontV, From))) {
3741 for (
unsigned S = 0; S <
Values.size(); ++S)
3742 Values[S] = Item[S * NumElts].first;
3744 while (
Values.size() > 1) {
3747 std::iota(Mask.begin(), Mask.end(), 0);
3749 for (
unsigned S = 0; S < NewValues.
size(); ++S)
3751 Builder.CreateShuffleVector(
Values[S * 2],
Values[S * 2 + 1], Mask);
3765 if (BCDstTy && BCSrcTy &&
3766 BCDstTy->getElementCount() != BCSrcTy->getElementCount()) {
3767 unsigned DstElts = BCDstTy->getNumElements();
3768 unsigned SrcElts = BCSrcTy->getNumElements();
3770 if (DstElts > SrcElts) {
3772 unsigned R = DstElts / SrcElts;
3773 if (Item.
size() % R != 0)
3775 for (
unsigned Idx = 0,
E = Item.
size(); Idx <
E; Idx += R) {
3776 auto [
V, Lane] = Item[Idx];
3786 unsigned R = SrcElts / DstElts;
3787 for (
auto [
V, Lane] : Item) {
3793 for (
unsigned J = 0; J < R; ++J)
3798 IdentityLeafs, SplatLeafs, ConcatLeafs,
3799 Builder, WorkList,
TTI);
3800 return Builder.CreateBitCast(
3805 unsigned NumOps =
I->getNumOperands() - (
II ? 1 : 0);
3807 for (
unsigned Idx = 0; Idx <
NumOps; Idx++) {
3810 Ops[Idx] =
II->getOperand(Idx);
3815 IdentityLeafs, SplatLeafs, ConcatLeafs, Builder, WorkList,
TTI);
3827 for (
const auto &Lane : Item)
3840 auto *
Value = Builder.CreateCmp(CI->getPredicate(),
Ops[0],
Ops[1]);
3850 auto *
Value = Builder.CreateCast(CI->getOpcode(),
Ops[0], DstTy);
3855 auto *
Value = Builder.CreateIntrinsic(DstTy,
II->getIntrinsicID(),
Ops);
3869bool VectorCombine::foldShuffleToIdentity(Instruction &
I) {
3871 if (!Ty ||
I.use_empty())
3875 for (
unsigned M = 0,
E = Ty->getNumElements(); M <
E; ++M)
3879 Candidates.
push_back(std::make_pair(Start, &*
I.use_begin()));
3880 DenseSet<std::pair<Value *, Use *>> IdentityLeafs, SplatLeafs, ConcatLeafs;
3881 unsigned NumVisited = 0;
3882 bool TraversedElCountChangingBitcast =
false;
3884 while (!Candidates.
empty()) {
3885 if (++NumVisited > Opts.vector_combine_max_scan_instrs)
3889 auto Item = ItemFrom.first;
3890 auto From = ItemFrom.second;
3891 auto [FrontV, FrontLane] = Item.front();
3898 if (FrontLane == 0 &&
3902 Value *FrontV = Item.front().first;
3904 E.value().second == (int)
E.index());
3906 IdentityLeafs.
insert(std::make_pair(FrontV, From));
3911 C &&
C->getSplatValue() &&
3913 Value *FrontV = Item.front().first;
3919 SplatLeafs.
insert(std::make_pair(FrontV, From));
3924 auto [FrontV, FrontLane] = Item.front();
3925 auto [
V, Lane] = IL;
3926 return !
V || (
V == FrontV && Lane == FrontLane);
3928 SplatLeafs.
insert(std::make_pair(FrontV, From));
3934 auto CheckLaneIsEquivalentToFirst = [Item](
InstLane IL) {
3935 Value *FrontV = Item.front().first;
3944 if (CI->getPredicate() !=
cast<CmpInst>(FrontV)->getPredicate())
3947 if (CI->getSrcTy()->getScalarType() !=
3952 SI->getOperand(0)->getType() !=
3959 II->getIntrinsicID() ==
3961 !
II->hasOperandBundles());
3968 BO && BO->isIntDivRem())
3975 }
else if (
isa<UnaryOperator, TruncInst, ZExtInst, SExtInst, FPToSIInst,
3976 FPToUIInst, SIToFPInst, UIToFPInst>(FrontV)) {
3983 if (BCDstTy && BCSrcTy) {
3984 ElementCount DstEC = BCDstTy->getElementCount();
3985 ElementCount SrcEC = BCSrcTy->getElementCount();
3986 if (DstEC == SrcEC) {
3989 &BitCast->getOperandUse(0));
3994 if (DstElts > SrcElts && DstElts % SrcElts == 0) {
3998 unsigned R = DstElts / SrcElts;
4000 bool Valid = Item.size() %
R == 0;
4001 for (
unsigned Idx = 0,
E = Item.size(); Valid && Idx <
E;
4003 auto [
V0, L0] = Item[
Idx];
4006 [](
InstLane IL) {
return IL.first !=
nullptr; })) {
4017 for (
unsigned J = 1; J <
R; ++J) {
4018 auto [VJ, LJ] = Item[
Idx + J];
4019 if (!VJ || VJ != V0 || LJ != L0 + (
int)J) {
4030 TraversedElCountChangingBitcast =
true;
4031 Candidates.
emplace_back(NItem, &BitCast->getOperandUse(0));
4034 }
else if (SrcElts > DstElts && SrcElts % DstElts == 0) {
4037 unsigned R = SrcElts / DstElts;
4039 for (
auto [
V, Lane] : Item) {
4045 for (
unsigned J = 0; J <
R; ++J)
4048 TraversedElCountChangingBitcast =
true;
4049 Candidates.
emplace_back(NItem, &BitCast->getOperandUse(0));
4055 &Sel->getOperandUse(0));
4057 &Sel->getOperandUse(1));
4059 &Sel->getOperandUse(2));
4063 !
II->hasOperandBundles()) {
4064 for (
unsigned Op = 0,
E =
II->getNumOperands() - 1;
Op <
E;
Op++) {
4068 Value *FrontV = Item.front().first;
4085 ConcatLeafs.
insert(std::make_pair(FrontV, From));
4092 if (NumVisited <= 1)
4098 if (NumVisited == 2 && TraversedElCountChangingBitcast)
4101 LLVM_DEBUG(
dbgs() <<
"Found a superfluous identity shuffle: " <<
I <<
"\n");
4108 ConcatLeafs, Builder, Worklist, &
TTI);
4109 replaceValue(
I, *
V);
4116bool VectorCombine::foldShuffleFromReductions(Instruction &
I) {
4120 switch (
II->getIntrinsicID()) {
4121 case Intrinsic::vector_reduce_add:
4122 case Intrinsic::vector_reduce_mul:
4123 case Intrinsic::vector_reduce_and:
4124 case Intrinsic::vector_reduce_or:
4125 case Intrinsic::vector_reduce_xor:
4126 case Intrinsic::vector_reduce_smin:
4127 case Intrinsic::vector_reduce_smax:
4128 case Intrinsic::vector_reduce_umin:
4129 case Intrinsic::vector_reduce_umax:
4138 std::queue<Value *> Worklist;
4139 SmallPtrSet<Value *, 4> Visited;
4140 ShuffleVectorInst *Shuffle =
nullptr;
4144 while (!Worklist.empty()) {
4145 Value *CV = Worklist.front();
4157 if (CI->isBinaryOp()) {
4158 for (
auto *
Op : CI->operand_values())
4162 if (Shuffle && Shuffle != SV)
4179 for (
auto *
V : Visited)
4180 for (
auto *U :
V->users())
4181 if (!Visited.contains(U) && U != &
I)
4184 FixedVectorType *VecType =
4188 FixedVectorType *ShuffleInputType =
4190 if (!ShuffleInputType)
4196 SmallVector<int> ConcatMask;
4198 sort(ConcatMask, [](
int X,
int Y) {
return (
unsigned)
X < (unsigned)
Y; });
4199 bool UsesSecondVec =
4200 any_of(ConcatMask, [&](
int M) {
return M >= (int)NumInputElts; });
4207 ShuffleInputType, CostKind, ConcatMask);
4209 LLVM_DEBUG(
dbgs() <<
"Found a reduction feeding from a shuffle: " << *Shuffle
4211 LLVM_DEBUG(
dbgs() <<
" OldCost: " << OldCost <<
" vs NewCost: " << NewCost
4213 bool MadeChanges =
false;
4214 if (NewCost < OldCost) {
4218 LLVM_DEBUG(
dbgs() <<
"Created new shuffle: " << *NewShuffle <<
"\n");
4219 replaceValue(*Shuffle, *NewShuffle);
4225 MadeChanges |= foldSelectShuffle(*Shuffle,
true);
4246bool VectorCombine::foldShuffleChainsToReduce(Instruction &
I) {
4255 if (FVT->getNumElements() < 2)
4258 std::optional<Instruction::BinaryOps> CommonBinOp;
4259 std::optional<Intrinsic::ID> CommonCallOp;
4264 CommonBinOp = BO->getOpcode();
4266 CommonCallOp = MMI->getIntrinsicID();
4272 FastMathFlags CommonFMF;
4273 bool IsFloatReduction =
false;
4277 auto IsChainNode = [&](
Value *
V) {
4279 return CommonBinOp && BO->getOpcode() == *CommonBinOp;
4281 return CommonCallOp && MMI->getIntrinsicID() == *CommonCallOp;
4289 constexpr unsigned MaxChainNodes = 32;
4290 SmallSetVector<Value *, 16> Nodes;
4291 SmallSetVector<Value *, 4> Sources;
4292 unsigned NumVisited = 0;
4293 auto AddSource = [&](
Value *
V) {
4299 auto Walk = [&](
Value *
V,
auto &&Walk) ->
bool {
4302 if (++NumVisited > MaxChainNodes)
4304 if (!IsChainNode(
V))
4305 return AddSource(
V);
4310 if (!Walk(
U->getOperand(
I), Walk))
4319 return AddSource(
V);
4321 if (!Walk(VecOpEE, Walk) || Nodes.
empty())
4334 if (!IsFloatReduction) {
4336 IsFloatReduction =
true;
4350 DenseMap<Value *, Demand> Demands;
4351 auto DemandOf = [&](
Value *
V) -> Demand & {
4353 Demand &
D = Demands[
V];
4354 if (
D.Lanes.getBitWidth() !=
N)
4358 DemandOf(VecOpEE).Lanes.setBit(0);
4360 Demand DV = Demands.
lookup(
V);
4361 if (DV.Lanes.isZero())
4364 ArrayRef<int>
Mask = SVI->getShuffleMask();
4365 Demand &
DS = DemandOf(SVI->getOperand(0));
4366 for (
unsigned I = 0,
E =
Mask.size();
I !=
E; ++
I) {
4368 if (!DV.Lanes[
I] || Mask[
I] < 0 ||
4369 (
unsigned)Mask[
I] >=
DS.Lanes.getBitWidth())
4371 if (
DS.Lanes[Mask[
I]] || DV.Duplicates[
I])
4372 DS.Duplicates.setBit(Mask[
I]);
4373 DS.Lanes.setBit(Mask[
I]);
4377 for (
Value *
Op : {
U->getOperand(0),
U->getOperand(1)}) {
4378 Demand &DOp = DemandOf(
Op);
4380 DOp.Duplicates |= DV.Duplicates | (DOp.Lanes & DV.Lanes);
4381 DOp.Lanes |= DV.Lanes;
4388 auto CoversChain = [&](
Value *
V) {
4389 SmallVector<Value *, 8> Worklist(1, VecOpEE);
4390 SmallPtrSet<Value *, 8> Seen;
4392 while (!Worklist.empty()) {
4395 for (
unsigned I = 0;
I !=
NumOps; ++
I) {
4399 if (!Nodes.contains(
Op))
4401 Worklist.push_back(
Op);
4409 struct ReductionCut {
4413 std::optional<ReductionCut> Cut;
4414 for (
Value *S : Sources) {
4415 auto It = Demands.
find(S);
4416 if (It == Demands.
end() || It->second.Lanes.isZero())
4418 if (!IsIdempotent && !It->second.Duplicates.isZero()) {
4423 Cut = ReductionCut{S, It->second.Lanes};
4430 if (!IsIdempotent && !(Cut->Elts & It->second.Lanes).isZero()) {
4434 Cut->Elts |= It->second.Lanes;
4440 auto It = Demands.
find(
V);
4441 if (It == Demands.
end() || !It->second.Lanes.isAllOnes())
4443 if (!IsIdempotent && !It->second.Duplicates.isZero())
4445 if (!CoversChain(
V))
4447 Cut = ReductionCut{
V, It->second.Lanes};
4452 if (!Cut || Cut->Elts.popcount() < 2)
4466 bool IsPartialReduction = !Cut->Elts.isAllOnes();
4467 FixedVectorType *ReduceVecTy =
4472 SmallVector<int> ExtractMask;
4474 if (IsPartialReduction) {
4475 for (
unsigned I = 0,
E = Cut->Elts.getBitWidth();
I !=
E; ++
I)
4477 ExtractMask.push_back(
I);
4478 unsigned SubIdx = 0, SubLen;
4479 auto SK = Cut->Elts.isShiftedMask(SubIdx, SubLen)
4483 SubIdx, ReduceVecTy);
4486 IntrinsicCostAttributes ICA(
4487 ReducedOp, ReduceVecTy->getElementType(),
4491 IsFloatReduction ? CommonFMF : FastMathFlags());
4494 LLVM_DEBUG(
dbgs() <<
"Found reduction shuffle chain: " <<
I <<
"\n OldCost : "
4495 << OrigCost <<
" vs NewCost: " << NewCost <<
"\n");
4500 if (VecOpEE->
hasOneUse() ? (NewCost > OrigCost) : (NewCost >= OrigCost))
4503 Value *ReduceInput = Cut->Src;
4504 if (IsPartialReduction)
4507 Value *ReducedResult;
4508 if (IsFloatReduction) {
4510 *CommonBinOp, ReduceVecTy->getElementType(),
false,
4513 {Identity, ReduceInput}, CommonFMF);
4518 replaceValue(
I, *ReducedResult);
4527bool VectorCombine::foldCastFromReductions(Instruction &
I) {
4532 bool TruncOnly =
false;
4535 case Intrinsic::vector_reduce_add:
4536 case Intrinsic::vector_reduce_mul:
4539 case Intrinsic::vector_reduce_and:
4540 case Intrinsic::vector_reduce_or:
4541 case Intrinsic::vector_reduce_xor:
4548 Value *ReductionSrc =
I.getOperand(0);
4560 Type *ResultTy =
I.getType();
4563 ReductionOpc, ReductionSrcTy, std::nullopt, CostKind);
4573 if (OldCost <= NewCost || !NewCost.
isValid())
4577 II->getIntrinsicID(), {Src});
4579 replaceValue(
I, *NewCast);
4607bool VectorCombine::foldSignBitReductionCmp(Instruction &
I) {
4609 IntrinsicInst *ReduceOp;
4610 const APInt *CmpVal;
4617 case Intrinsic::vector_reduce_or:
4618 case Intrinsic::vector_reduce_umax:
4619 case Intrinsic::vector_reduce_and:
4620 case Intrinsic::vector_reduce_umin:
4621 case Intrinsic::vector_reduce_add:
4632 unsigned BitWidth = VecTy->getScalarSizeInBits();
4636 unsigned NumElts = VecTy->getNumElements();
4645 case Intrinsic::vector_reduce_or:
4646 case Intrinsic::vector_reduce_umax:
4647 TreeOpcode = Instruction::Or;
4649 case Intrinsic::vector_reduce_and:
4650 case Intrinsic::vector_reduce_umin:
4651 TreeOpcode = Instruction::And;
4653 case Intrinsic::vector_reduce_add:
4654 TreeOpcode = Instruction::Add;
4662 SmallVector<Value *, 8> Worklist;
4663 SmallVector<Value *, 8> Sources;
4665 std::optional<bool> IsAShr;
4666 constexpr unsigned MaxSources = 8;
4671 while (!Worklist.
empty() && Worklist.
size() <= MaxSources &&
4672 Sources.
size() <= MaxSources) {
4681 bool ThisIsAShr = Shr->getOpcode() == Instruction::AShr;
4683 IsAShr = ThisIsAShr;
4684 else if (*IsAShr != ThisIsAShr)
4710 if (Sources.
empty() || Sources.
size() > MaxSources ||
4711 Worklist.
size() > MaxSources || !IsAShr)
4714 unsigned NumSources = Sources.
size();
4718 if (OrigIID == Intrinsic::vector_reduce_add &&
4726 (OrigIID == Intrinsic::vector_reduce_add) ? NumSources * NumElts : 1;
4729 NegativeVal.negate();
4761 TestsNegative =
false;
4762 }
else if (*CmpVal == NegativeVal) {
4763 TestsNegative =
true;
4767 IsEq =
Pred == ICmpInst::ICMP_EQ;
4768 }
else if (
Pred == ICmpInst::ICMP_SLT && *CmpVal == RangeHigh) {
4770 TestsNegative = (RangeHigh == NegativeVal);
4771 }
else if (
Pred == ICmpInst::ICMP_SGT && *CmpVal == RangeHigh - 1) {
4773 TestsNegative = (RangeHigh == NegativeVal);
4774 }
else if (
Pred == ICmpInst::ICMP_SGT && *CmpVal == RangeLow) {
4776 TestsNegative = (RangeLow == NegativeVal);
4777 }
else if (
Pred == ICmpInst::ICMP_SLT && *CmpVal == RangeLow + 1) {
4779 TestsNegative = (RangeLow == NegativeVal);
4822 enum CheckKind :
unsigned {
4829 auto RequiresOr = [](CheckKind
C) ->
bool {
return C & 0b100; };
4831 auto IsNegativeCheck = [](CheckKind
C) ->
bool {
return C & 0b010; };
4833 auto Invert = [](CheckKind
C) {
return CheckKind(
C ^ 0b011); };
4837 case Intrinsic::vector_reduce_or:
4838 case Intrinsic::vector_reduce_umax:
4839 Base = TestsNegative ? AnyNeg : AllNonNeg;
4841 case Intrinsic::vector_reduce_and:
4842 case Intrinsic::vector_reduce_umin:
4843 Base = TestsNegative ? AllNeg : AnyNonNeg;
4845 case Intrinsic::vector_reduce_add:
4846 Base = TestsNegative ? AllNeg : AllNonNeg;
4857 VecTy, std::nullopt, CostKind);
4860 FastMathFlags(), CostKind);
4861 return ArithCost <= MinMaxCost ? std::make_pair(Arith, ArithCost)
4862 : std::make_pair(MinMax, MinMaxCost);
4866 auto [NewIID, NewCost] = RequiresOr(
Check)
4867 ? PickCheaper(Intrinsic::vector_reduce_or,
4868 Intrinsic::vector_reduce_umax)
4869 : PickCheaper(
Intrinsic::vector_reduce_and,
4873 if (NumSources > 1) {
4874 unsigned CombineOpc =
4875 RequiresOr(
Check) ? Instruction::Or : Instruction::And;
4880 LLVM_DEBUG(
dbgs() <<
"Found sign-bit reduction cmp: " <<
I <<
"\n OldCost: "
4881 << OldCost <<
" vs NewCost: " << NewCost <<
"\n");
4883 if (NewCost > OldCost)
4888 Type *ScalarTy = VecTy->getScalarType();
4891 if (NumSources == 1) {
4902 replaceValue(
I, *NewCmp);
4933bool VectorCombine::foldReductionZeroTest(Instruction &
I) {
4942 if (!
II || !
II->hasOneUse())
4945 auto ReduceID =
II->getIntrinsicID();
4946 if (ReduceID != Intrinsic::vector_reduce_or &&
4947 ReduceID != Intrinsic::vector_reduce_umax)
4950 Value *Vec =
II->getArgOperand(0);
4952 if (!VecTy || !VecTy->getElementType()->isIntegerTy())
4957 ? Intrinsic::vector_reduce_or
4972 LLVM_DEBUG(
dbgs() <<
"Found a reduction zero test: " <<
I <<
"\n OldCost: "
4973 << OldCost <<
" vs NewCost: " << NewCost <<
"\n");
4975 if (!OldCost.
isValid() || !NewCost.
isValid() || NewCost > OldCost)
4981 replaceValue(
I, *NewReduce);
5006bool VectorCombine::foldICmpEqZeroVectorReduce(Instruction &
I) {
5017 switch (
II->getIntrinsicID()) {
5018 case Intrinsic::vector_reduce_add:
5019 case Intrinsic::vector_reduce_or:
5020 case Intrinsic::vector_reduce_umin:
5021 case Intrinsic::vector_reduce_umax:
5022 case Intrinsic::vector_reduce_smin:
5023 case Intrinsic::vector_reduce_smax:
5029 Value *InnerOp =
II->getArgOperand(0);
5072 switch (
II->getIntrinsicID()) {
5073 case Intrinsic::vector_reduce_add: {
5078 unsigned NumElems = XTy->getNumElements();
5084 if (LeadingZerosX <= LostBits || LeadingZerosFX <= LostBits)
5092 case Intrinsic::vector_reduce_smin:
5093 case Intrinsic::vector_reduce_smax:
5103 LLVM_DEBUG(
dbgs() <<
"Found a reduction to 0 comparison with removable op: "
5119 case Intrinsic::vector_reduce_add:
5120 case Intrinsic::vector_reduce_or:
5126 case Intrinsic::vector_reduce_umin:
5127 case Intrinsic::vector_reduce_umax:
5128 case Intrinsic::vector_reduce_smin:
5129 case Intrinsic::vector_reduce_smax:
5141 NewReduceCost + (InnerOp->
hasOneUse() ? 0 : ExtCost);
5143 LLVM_DEBUG(
dbgs() <<
"Found a removable extension before reduction: "
5144 << *InnerOp <<
"\n OldCost: " << OldCost
5145 <<
" vs NewCost: " << NewCost <<
"\n");
5151 if (NewCost > OldCost)
5160 Builder.
CreateICmp(
Pred, NewReduce, ConstantInt::getNullValue(Ty));
5161 replaceValue(
I, *NewCmp);
5192bool VectorCombine::foldEquivalentReductionCmp(Instruction &
I) {
5195 const APInt *CmpVal;
5200 if (!
II || !
II->hasOneUse())
5203 const auto IsValidOrUmaxCmp = [&]() {
5212 bool IsPositive = CmpVal->
isAllOnes() &&
Pred == ICmpInst::ICMP_SGT;
5214 bool IsNegative = (CmpVal->
isZero() || CmpVal->
isOne() || *CmpVal == 2) &&
5215 Pred == ICmpInst::ICMP_SLT;
5216 return IsEquality || IsPositive || IsNegative;
5219 const auto IsValidAndUminCmp = [&]() {
5224 const auto LeadingOnes = CmpVal->
countl_one();
5231 bool IsNegative = CmpVal->
isZero() &&
Pred == ICmpInst::ICMP_SLT;
5240 ((*CmpVal)[0] || (*CmpVal)[1]) &&
Pred == ICmpInst::ICMP_SGT;
5241 return IsEquality || IsNegative || IsPositive;
5249 switch (OriginalIID) {
5250 case Intrinsic::vector_reduce_or:
5251 if (!IsValidOrUmaxCmp())
5253 AlternativeIID = Intrinsic::vector_reduce_umax;
5255 case Intrinsic::vector_reduce_umax:
5256 if (!IsValidOrUmaxCmp())
5258 AlternativeIID = Intrinsic::vector_reduce_or;
5260 case Intrinsic::vector_reduce_and:
5261 if (!IsValidAndUminCmp())
5263 AlternativeIID = Intrinsic::vector_reduce_umin;
5265 case Intrinsic::vector_reduce_umin:
5266 if (!IsValidAndUminCmp())
5268 AlternativeIID = Intrinsic::vector_reduce_and;
5281 if (ReductionOpc != Instruction::ICmp)
5285 FastMathFlags(), CostKind);
5292 <<
"\n OrigCost: " << OrigCost
5293 <<
" vs AltCost: " << AltCost <<
"\n");
5295 if (AltCost >= OrigCost)
5299 Type *ScalarTy = VecTy->getScalarType();
5302 Builder.
CreateICmp(
Pred, NewReduce, ConstantInt::get(ScalarTy, *CmpVal));
5304 replaceValue(
I, *NewCmp);
5318 unsigned Depth = 0) {
5319 constexpr unsigned MaxLocalDepth = 2;
5320 if (
Depth > MaxLocalDepth)
5323 auto NumSignBits = [&](
const Value *
X) {
5326 if (NumSignBits(
V) ==
V->getType()->getScalarSizeInBits())
5331 return NumSignBits(
A) >= 2 && NumSignBits(
B) >= 2 &&
5342bool VectorCombine::foldReduceAddCmpZero(Instruction &
I) {
5352 if (!VecTy || VecTy->getNumElements() < 2)
5358 if (!IsNonNegative && !IsNonPositive)
5363 unsigned NumElts = VecTy->getNumElements();
5365 if (
Log2_32(NumElts) >= NumSignBits)
5368 ICmpInst::Predicate NewPred;
5370 case ICmpInst::ICMP_EQ:
5371 case ICmpInst::ICMP_ULE:
5372 case ICmpInst::ICMP_SLE:
5373 case ICmpInst::ICMP_SGE:
5374 NewPred = ICmpInst::ICMP_EQ;
5376 case ICmpInst::ICMP_NE:
5377 case ICmpInst::ICMP_UGT:
5378 case ICmpInst::ICMP_SGT:
5379 case ICmpInst::ICMP_SLT:
5380 NewPred = ICmpInst::ICMP_NE;
5390 if (!IsNonNegative &&
5391 (
Pred == ICmpInst::ICMP_SGT ||
Pred == ICmpInst::ICMP_SLE))
5393 if (!IsNonPositive &&
5394 (
Pred == ICmpInst::ICMP_SLT ||
Pred == ICmpInst::ICMP_SGE))
5396 if ((
Pred == ICmpInst::ICMP_SGT ||
Pred == ICmpInst::ICMP_SLE ||
5397 Pred == ICmpInst::ICMP_SLT ||
Pred == ICmpInst::ICMP_SGE) &&
5398 Log2_32(NumElts) >= NumSignBits - 1)
5402 Instruction::Add, VecTy, std::nullopt, CostKind);
5404 Instruction::Or, VecTy, std::nullopt, CostKind);
5406 Intrinsic::umax, VecTy, FastMathFlags(), CostKind);
5409 bool UseOr = OrCost.
isValid() && (!UmaxCost.
isValid() || OrCost <= UmaxCost);
5411 if (AltCost > OrigCost)
5417 Intrinsic::vector_reduce_umax, {VecTy}, {Vec});
5419 NewPred, NewReduce, ConstantInt::getNullValue(VecTy->getScalarType()));
5420 replaceValue(
I, *NewCmp);
5429 constexpr unsigned MaxVisited = 32;
5432 bool FoundReduction =
false;
5435 while (!WorkList.
empty()) {
5437 for (
User *U :
I->users()) {
5439 if (!UI || !Visited.
insert(UI).second)
5441 if (Visited.
size() > MaxVisited)
5447 switch (
II->getIntrinsicID()) {
5448 case Intrinsic::vector_reduce_add:
5449 case Intrinsic::vector_reduce_mul:
5450 case Intrinsic::vector_reduce_and:
5451 case Intrinsic::vector_reduce_or:
5452 case Intrinsic::vector_reduce_xor:
5453 case Intrinsic::vector_reduce_smin:
5454 case Intrinsic::vector_reduce_smax:
5455 case Intrinsic::vector_reduce_umin:
5456 case Intrinsic::vector_reduce_umax:
5457 FoundReduction =
true;
5470 return FoundReduction;
5483bool VectorCombine::foldSelectShuffle(Instruction &
I,
bool FromReduction) {
5488 if (!Op0 || !Op1 || Op0 == Op1 || !Op0->isBinaryOp() || !Op1->isBinaryOp() ||
5489 VT != Op0->getType())
5496 SmallPtrSet<Instruction *, 4> InputShuffles({SVI0A, SVI0B, SVI1A, SVI1B});
5498 if (!
I ||
I->getOperand(0)->getType() != VT)
5500 return any_of(
I->users(), [&](User *U) {
5501 return U != Op0 && U != Op1 &&
5502 !(isa<ShuffleVectorInst>(U) &&
5503 (InputShuffles.contains(cast<Instruction>(U)) ||
5504 isInstructionTriviallyDead(cast<Instruction>(U))));
5507 if (checkSVNonOpUses(SVI0A) || checkSVNonOpUses(SVI0B) ||
5508 checkSVNonOpUses(SVI1A) || checkSVNonOpUses(SVI1B))
5516 for (
auto *U :
I->users()) {
5518 if (!SV ||
SV->getType() != VT)
5520 if ((
SV->getOperand(0) != Op0 &&
SV->getOperand(0) != Op1) ||
5521 (
SV->getOperand(1) != Op0 &&
SV->getOperand(1) != Op1))
5528 if (!collectShuffles(Op0) || !collectShuffles(Op1))
5532 if (FromReduction && Shuffles.
size() > 1)
5537 if (!FromReduction) {
5538 for (
size_t Idx = 0,
E = Shuffles.
size(); Idx !=
E; ++Idx) {
5539 for (
auto *U : Shuffles[Idx]->
users()) {
5554 int MaxV1Elt = 0, MaxV2Elt = 0;
5555 unsigned NumElts = VT->getNumElements();
5556 for (ShuffleVectorInst *SVN : Shuffles) {
5557 SmallVector<int>
Mask;
5558 SVN->getShuffleMask(Mask);
5562 Value *SVOp0 = SVN->getOperand(0);
5563 Value *SVOp1 = SVN->getOperand(1);
5568 for (
int &Elem : Mask) {
5574 if (SVOp0 == Op1 && SVOp1 == Op0) {
5578 if (SVOp0 != Op0 || SVOp1 != Op1)
5584 SmallVector<int> ReconstructMask;
5585 for (
unsigned I = 0;
I <
Mask.size();
I++) {
5588 }
else if (Mask[
I] <
static_cast<int>(NumElts)) {
5589 MaxV1Elt = std::max(MaxV1Elt, Mask[
I]);
5590 auto It =
find_if(
V1, [&](
const std::pair<int, int> &
A) {
5591 return Mask[
I] ==
A.first;
5597 V1.emplace_back(Mask[
I],
V1.size());
5600 MaxV2Elt = std::max<int>(MaxV2Elt, Mask[
I] - NumElts);
5601 auto It =
find_if(V2, [&](
const std::pair<int, int> &
A) {
5602 return Mask[
I] -
static_cast<int>(NumElts) ==
A.first;
5616 sort(ReconstructMask);
5617 OrigReconstructMasks.
push_back(std::move(ReconstructMask));
5624 if (
V1.empty() || V2.
empty() ||
5625 (MaxV1Elt ==
static_cast<int>(
V1.size()) - 1 &&
5626 MaxV2Elt ==
static_cast<int>(V2.
size()) - 1))
5638 if (InputShuffles.contains(SSV))
5640 return SV->getMaskValue(M);
5648 std::pair<int, int>
Y) {
5649 int MXA = GetBaseMaskValue(
A,
X.first);
5650 int MYA = GetBaseMaskValue(
A,
Y.first);
5654 return SortBase(SVI0A,
A,
B);
5656 stable_sort(V2, [&](std::pair<int, int>
A, std::pair<int, int>
B) {
5657 return SortBase(SVI1A,
A,
B);
5662 for (
const auto &Mask : OrigReconstructMasks) {
5663 SmallVector<int> ReconstructMask;
5664 for (
int M : Mask) {
5666 auto It =
find_if(
V, [M](
auto A) {
return A.second ==
M; });
5667 assert(It !=
V.end() &&
"Expected all entries in Mask");
5668 return std::distance(
V.begin(), It);
5672 else if (M <
static_cast<int>(NumElts)) {
5675 ReconstructMask.
push_back(NumElts + FindIndex(V2, M));
5678 ReconstructMasks.
push_back(std::move(ReconstructMask));
5683 SmallVector<int> V1A, V1B, V2A, V2B;
5684 for (
unsigned I = 0;
I <
V1.size();
I++) {
5688 for (
unsigned I = 0;
I < V2.
size();
I++) {
5689 V2A.
push_back(GetBaseMaskValue(SVI1A, V2[
I].first));
5690 V2B.
push_back(GetBaseMaskValue(SVI1B, V2[
I].first));
5692 while (V1A.
size() < NumElts) {
5696 while (V2A.
size() < NumElts) {
5708 VT, VT, CostKind,
SV->getShuffleMask());
5715 unsigned ElementSize = VT->getElementType()->getPrimitiveSizeInBits();
5716 unsigned MaxVectorSize =
5718 unsigned MaxElementsInVector = MaxVectorSize / ElementSize;
5719 if (MaxElementsInVector == 0)
5728 std::set<SmallVector<int, 4>> UniqueShuffles;
5733 unsigned NumFullVectors =
Mask.size() / MaxElementsInVector;
5734 if (NumFullVectors < 2)
5735 return C + ShuffleCost;
5736 SmallVector<int, 4> SubShuffle(MaxElementsInVector);
5737 unsigned NumUniqueGroups = 0;
5738 unsigned NumGroups =
Mask.size() / MaxElementsInVector;
5741 for (
unsigned I = 0;
I < NumFullVectors; ++
I) {
5742 for (
unsigned J = 0; J < MaxElementsInVector; ++J)
5743 SubShuffle[J] = Mask[MaxElementsInVector *
I + J];
5744 if (UniqueShuffles.insert(SubShuffle).second)
5745 NumUniqueGroups += 1;
5747 return C + ShuffleCost * NumUniqueGroups / NumGroups;
5753 SmallVector<int, 16>
Mask;
5754 SV->getShuffleMask(Mask);
5755 return AddShuffleMaskAdjustedCost(
C, Mask);
5758 auto AllShufflesHaveSameOperands =
5759 [](SmallPtrSetImpl<Instruction *> &InputShuffles) {
5760 if (InputShuffles.size() < 2)
5762 ShuffleVectorInst *FirstSV =
5769 std::next(InputShuffles.begin()), InputShuffles.end(),
5770 [&](Instruction *
I) {
5771 ShuffleVectorInst *SV = dyn_cast<ShuffleVectorInst>(I);
5772 return SV && SV->getOperand(0) == In0 && SV->getOperand(1) == In1;
5781 CostBefore += std::accumulate(Shuffles.begin(), Shuffles.end(),
5783 if (AllShufflesHaveSameOperands(InputShuffles)) {
5784 UniqueShuffles.clear();
5785 CostBefore += std::accumulate(InputShuffles.begin(), InputShuffles.end(),
5788 CostBefore += std::accumulate(InputShuffles.begin(), InputShuffles.end(),
5794 FixedVectorType *Op0SmallVT =
5796 FixedVectorType *Op1SmallVT =
5801 UniqueShuffles.clear();
5802 CostAfter += std::accumulate(ReconstructMasks.begin(), ReconstructMasks.end(),
5804 std::set<SmallVector<int>> OutputShuffleMasks({V1A, V1B, V2A, V2B});
5806 std::accumulate(OutputShuffleMasks.begin(), OutputShuffleMasks.end(),
5809 LLVM_DEBUG(
dbgs() <<
"Found a binop select shuffle pattern: " <<
I <<
"\n");
5811 <<
" vs CostAfter: " << CostAfter <<
"\n");
5812 if (CostBefore < CostAfter ||
5823 if (InputShuffles.contains(SSV))
5825 return SV->getOperand(
Op);
5829 GetShuffleOperand(SVI0A, 1), V1A);
5832 GetShuffleOperand(SVI0B, 1), V1B);
5835 GetShuffleOperand(SVI1A, 1), V2A);
5838 GetShuffleOperand(SVI1B, 1), V2B);
5843 I->copyIRFlags(Op0,
true);
5848 I->copyIRFlags(Op1,
true);
5850 for (
int S = 0,
E = ReconstructMasks.size(); S !=
E; S++) {
5853 replaceValue(*Shuffles[S], *NSV,
false);
5865bool VectorCombine::shrinkType(Instruction &
I) {
5866 Value *ZExted, *OtherOperand;
5872 Value *ZExtOperand =
I.getOperand(
I.getOperand(0) == OtherOperand ? 1 : 0);
5876 unsigned BW = SmallTy->getElementType()->getPrimitiveSizeInBits();
5878 if (
I.getOpcode() == Instruction::LShr) {
5895 Instruction::ZExt, BigTy, SmallTy,
5896 TargetTransformInfo::CastContextHint::None, CostKind);
5901 for (User *U : ZExtOperand->
users()) {
5908 ShrinkCost += ZExtCost;
5923 ShrinkCost += ZExtCost;
5930 Instruction::Trunc, SmallTy, BigTy,
5931 TargetTransformInfo::CastContextHint::None, CostKind);
5936 if (ShrinkCost > CurrentCost)
5940 Value *Op0 = ZExted;
5943 if (
I.getOperand(0) == OtherOperand)
5948 NewBinOpI->copyIRFlags(&
I);
5949 NewBinOpI->copyMetadata(
I);
5952 replaceValue(
I, *NewZExtr);
5958bool VectorCombine::foldInsExtVectorToShuffle(Instruction &
I) {
5959 Value *DstVec, *SrcVec;
5970 if (!DstVecTy || !SrcVecTy ||
5976 if (InsIdx >= NumDstElts || ExtIdx >= NumSrcElts || NumDstElts == 1)
5983 bool NeedExpOrNarrow = NumSrcElts != NumDstElts;
5985 if (NeedDstSrcSwap) {
5987 Mask[InsIdx] = ExtIdx % NumDstElts;
5991 std::iota(
Mask.begin(),
Mask.end(), 0);
5992 Mask[InsIdx] = (ExtIdx % NumDstElts) + NumDstElts;
6005 SmallVector<int> ExtToVecMask;
6006 if (!NeedExpOrNarrow) {
6011 nullptr, {DstVec, SrcVec});
6017 ExtToVecMask[ExtIdx % NumDstElts] = ExtIdx;
6020 DstVecTy, SrcVecTy, CostKind, ExtToVecMask);
6024 if (!Ext->hasOneUse())
6027 LLVM_DEBUG(
dbgs() <<
"Found a insert/extract shuffle-like pair: " <<
I
6028 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
6031 if (OldCost < NewCost)
6034 if (NeedExpOrNarrow) {
6035 if (!NeedDstSrcSwap)
6048 replaceValue(
I, *Shuf);
6057bool VectorCombine::foldInsertScalarPartsToShuffle(Instruction &
I) {
6066 Type *EltTy = VecTy->getElementType();
6068 !
DL->typeSizeEqualsStoreSize(EltTy))
6071 unsigned NumElts = VecTy->getNumElements();
6073 Value *Src =
nullptr;
6074 unsigned NumSrcElts = 0;
6080 if (Ins != &
I && !Ins->hasOneUse())
6085 Vec = Ins->getOperand(0);
6087 if (DemandedElts[Idx])
6089 DemandedElts.
setBit(Idx);
6093 Value *Elt = Ins->getOperand(1);
6100 Value *Shift =
nullptr;
6108 unsigned SrcBits =
X->getType()->getIntegerBitWidth();
6109 if (SrcBits % EltBits)
6112 NumSrcElts = SrcBits / EltBits;
6113 }
else if (
X != Src) {
6117 if (ShAmt % EltBits || Part >= NumSrcElts)
6119 Mask[
Idx] =
DL->isBigEndian() ? NumSrcElts - 1 - Part : Part;
6122 for (
Value *
V : {Elt == Trunc ? nullptr : Elt, Trunc, Shift}) {
6125 if (!
V->hasOneUse())
6147 bool IsIdentity = NumSrcElts == NumElts &&
6153 LLVM_DEBUG(
dbgs() <<
"Found an insertelement chain of scalar parts: " <<
I
6154 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
6156 if (!OldCost.
isValid() || !NewCost.
isValid() || NewCost >= OldCost)
6161 replaceValue(
I, *Shuf);
6168 return CB->arg_size();
6180 if (
II->hasOperandBundles() ||
6193 OperandTy->getElementCount() != ResultTy->getElementCount())
6202 auto GetSplatOrScalar = [](
Value *
V) {
6206 Value *CommonValue = GetSplatOrScalar(
Values.front());
6210 if (GetSplatOrScalar(
V) != CommonValue)
6219 for (
const auto &[Index, Member] :
enumerate(Members)) {
6221 if (!Extract || Extract->getNumIndices() != 1 ||
6222 *Extract->idx_begin() != Index)
6230 unsigned Factor = Members.
size();
6241 unsigned OperandIndex) {
6243 for (
Value *Member : Members)
6252 unsigned &NumScanned) {
6253 unsigned Factor = Members.
size();
6256 if (NumScanned + Factor > Opts.vector_combine_max_scan_instrs)
6258 NumScanned += Factor;
6262 !FirstInst->getSingleUndroppableUse())
6267 if (!Inst || !Inst->getSingleUndroppableUse() ||
6288 return Builder.CreateNAryOp(NarrowInst->
getOpcode(), NewOperands);
6290 return Builder.CreateCast(Cast->getOpcode(), NewOperands[0], WideResultTy);
6292 return Builder.CreateCmp(Cmp->getPredicate(), NewOperands[0],
6295 return Builder.CreateSelect(
6296 NewOperands[0], NewOperands[1], NewOperands[2],
"",
6299 return Builder.CreateFreeze(NewOperands[0]);
6301 return Builder.CreateIntrinsic(WideResultTy,
II->getIntrinsicID(),
6312 "deinterleave source must have the interleaved element count");
6319 NewOperands.
reserve(NumOperands);
6320 for (
unsigned Op = 0;
Op != NumOperands; ++
Op) {
6322 Value *NewOperand =
nullptr;
6325 Builder.SetCurrentDebugLocation(NarrowInst->getDebugLoc());
6326 NewOperand = Builder.CreateVectorSplat(WideEC, NewOperand);
6336 Builder.SetCurrentDebugLocation(NarrowInst->getDebugLoc());
6337 auto *WideResultTy =
6384bool VectorCombine::foldInterleaveOfDeinterleaveChains(Instruction &
I) {
6390 if (!Factor || Interleave->hasOperandBundles())
6393 SmallVector<Value *, 8> RootMembers(Interleave->args());
6394 unsigned NumScanned = 0;
6402 replaceValue(*Interleave, *WideValue);
6410bool VectorCombine::foldInterleaveIntrinsics(Instruction &
I) {
6411 if (foldInterleaveOfDeinterleaveChains(
I))
6414 const APInt *SplatVal0, *SplatVal1;
6424 auto *ExtVTy = VectorType::getExtendedElementVectorType(VTy);
6425 unsigned Width = VTy->getElementType()->getIntegerBitWidth();
6434 LLVM_DEBUG(
dbgs() <<
"VC: The cost to cast from " << *ExtVTy <<
" to "
6435 << *
I.getType() <<
" is too high.\n");
6439 APInt NewSplatVal = SplatVal1->
zext(Width * 2);
6440 NewSplatVal <<= Width;
6441 NewSplatVal |= SplatVal0->
zext(Width * 2);
6443 ExtVTy->getElementCount(), ConstantInt::get(
F.getContext(), NewSplatVal));
6478bool VectorCombine::foldDeinterleaveIntrinsics(Instruction &
I) {
6480 if (
DL->isBigEndian())
6483 using namespace PatternMatch;
6484 Value *DeinterleavedVal;
6495 unsigned HalfElementWidth = ElementWidth / 2;
6499 std::array<ExtractValueInst *, 2> OrigFields{};
6500 for (User *Usr :
I.users()) {
6503 if (!
E ||
E->getNumIndices() != 1)
6505 unsigned Idx = *
E->idx_begin();
6507 if (Idx >= 2 || OrigFields[Idx] || !
E->hasNUses(2))
6509 OrigFields[
Idx] =
E;
6513 SmallVector<Instruction *, 2> MergeInsts;
6514 for (
auto *FieldUsr : OrigFields[0]->
users()) {
6522 auto MatchMerge = [&](void) ->
bool {
6525 return match(MergeInsts[0],
6529 match(MergeInsts[1],
6534 if (!MatchMerge()) {
6535 std::swap(MergeInsts[0], MergeInsts[1]);
6550 auto *NewFieldTy = VecTy->getWithNewBitWidth(HalfElementWidth);
6560 if (OldCost <= NewCost || !NewCost.
isValid()) {
6562 dbgs() <<
"VC: New deinterleave2 sequence cost (" << NewCost <<
")"
6563 <<
" is higher than that of the old one (" << OldCost <<
")\n");
6571 Intrinsic::vector_deinterleave2, {NewVecTy}, {NewVecCast});
6572 for (
auto [Idx, MergeInst] :
enumerate(MergeInsts)) {
6574 NewField = Builder.
CreateBitCast(NewField, MergeInst->getType());
6575 replaceValue(*MergeInst, *NewField);
6581bool VectorCombine::foldBitcastOfVPLoad(Instruction &
I) {
6582 const DataLayout &
DL =
I.getDataLayout();
6597 DL.getValueOrABITypeAlignment(
II->getPointerAlignment(), OrigVecTy);
6598 ElementCount OrigVecCnt = OrigVecTy->getElementCount();
6600 ElementCount NewVecCnt = NewVecTy->getElementCount();
6612 II->getMemoryPointerParam(),
false,
6618 {Intrinsic::vp_load, NewVecTy,
II->getMemoryPointerParam(),
false,
6622 <<
" NewCost=" << NewCost <<
"\n");
6623 if (NewCost > OldCost || !NewCost.
isValid())
6631 NewVecTy, Intrinsic::vp_load,
6632 {
II->getMemoryPointerParam(), NewMask, NewEVL});
6635 0, AttrBuilder(
II->getContext()).addAlignmentAttr(OrigAlign));
6636 replaceValue(*Cast, *NewVP);
6646bool VectorCombine::foldBitOrderReverseAndSwap(Instruction &
I) {
6650 Type *Ty =
X->getType();
6651 Type *VecTy =
I.getOperand(0)->getType();
6665 if (CanUseBswap || CanUseFshl) {
6676 IntrinsicCostAttributes ICABSwap(Intrinsic::bswap, Ty, {Ty});
6677 IntrinsicCostAttributes ICABFshl(Intrinsic::fshl, Ty, {
X,
X, HalfBW},
6679 IntrinsicCostAttributes ICABRev(Intrinsic::bitreverse, Ty, {Ty});
6684 if (!InnerCall->hasOneUse())
6687 else if (!InnerBitCast->hasOneUse())
6690 <<
"\n OldCost: " << OldCost
6691 <<
" vs NewCost: " << NewCost <<
"\n");
6692 if (NewCost.isValid() && NewCost < OldCost) {
6699 replaceValue(
I, *BRev);
6708 Type *Ty =
I.getType();
6710 TypeSize ElementSize =
DL->getTypeStoreSize(Ty);
6713 Type *NewVecTy = VectorType::get(I8Ty, NewVecCnt);
6726 IntrinsicCostAttributes ICANew(Intrinsic::bitreverse, NewVecTy, {NewVecTy});
6729 InstructionCost NewCost = CastToVecCost + NewIntrinsicCost + CastToOrigCost;
6730 if (!InnerII->hasOneUse())
6733 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
6735 if (!NewCost.
isValid() || NewCost >= OldCost)
6743 replaceValue(
I, *CastToOrig);
6753 unsigned RawNumElements = MaxIdx + 1u;
6757 return RawNumElements;
6761 return RawNumElements;
6766 return RawNumElements;
6771 if (ElemsPerReg == 0 || RawNumElements <= ElemsPerReg)
6772 return RawNumElements;
6774 return alignTo(RawNumElements, ElemsPerReg);
6778bool VectorCombine::shrinkLoadForShuffles(Instruction &
I) {
6780 if (!OldLoad || !OldLoad->isSimple())
6787 unsigned const OldNumElements = OldLoadTy->getNumElements();
6793 using IndexRange = std::pair<int, int>;
6794 auto GetIndexRangeInShuffles = [&]() -> std::optional<IndexRange> {
6795 IndexRange OutputRange = IndexRange(OldNumElements, -1);
6796 for (llvm::Use &Use :
I.uses()) {
6798 User *Shuffle =
Use.getUser();
6803 return std::nullopt;
6810 for (
int Index : Mask) {
6811 if (Index >= 0 && Index <
static_cast<int>(OldNumElements)) {
6812 OutputRange.first = std::min(Index, OutputRange.first);
6813 OutputRange.second = std::max(Index, OutputRange.second);
6818 if (OutputRange.second < OutputRange.first)
6819 return std::nullopt;
6825 if (std::optional<IndexRange> Indices = GetIndexRangeInShuffles()) {
6826 unsigned const NewNumElements =
6831 if (NewNumElements < OldNumElements) {
6836 Type *ElemTy = OldLoadTy->getElementType();
6838 Value *PtrOp = OldLoad->getPointerOperand();
6841 Instruction::Load, OldLoad->getType(), OldLoad->getAlign(),
6842 OldLoad->getPointerAddressSpace(), CostKind);
6845 OldLoad->getPointerAddressSpace(), CostKind);
6847 using UseEntry = std::pair<ShuffleVectorInst *, std::vector<int>>;
6849 unsigned const MaxIndex = NewNumElements * 2u;
6851 for (llvm::Use &Use :
I.uses()) {
6858 ArrayRef<int> OldMask = Shuffle->getShuffleMask();
6864 for (
int Index : OldMask) {
6865 if (Index >=
static_cast<int>(MaxIndex))
6872 OldLoadTy, CostKind, OldMask);
6875 NewLoadTy, CostKind, OldMask);
6879 dbgs() <<
"Found a load used only by shufflevector instructions: "
6880 <<
I <<
"\n OldCost: " << OldCost
6881 <<
" vs NewCost: " << NewCost <<
"\n");
6883 if (OldCost < NewCost || !NewCost.
isValid())
6889 NewLoad->copyMetadata(
I);
6892 for (UseEntry &Use : NewUses) {
6893 ShuffleVectorInst *Shuffle =
Use.first;
6894 std::vector<int> &NewMask =
Use.second;
6901 replaceValue(*Shuffle, *NewShuffle,
false);
6933bool VectorCombine::foldShuffleOfAdjacentLoads(Instruction &
I) {
6939 if (!Load0 || !Load1 || Load0 == Load1 || !Load0->isSimple() ||
6949 if (Load0->getParent() != Load1->getParent())
6952 if (Load0->getPointerAddressSpace() != Load1->getPointerAddressSpace())
6957 if (
DL->getTypeSizeInBits(LoadTy) != 8 *
DL->getTypeStoreSize(LoadTy))
6960 const unsigned NumElts = LoadTy->getNumElements();
6962 if (NumElts > INT_MAX / 2)
6968 unsigned AS = Load0->getPointerAddressSpace();
6969 unsigned IdxWidth =
DL->getIndexSizeInBits(AS);
6970 APInt Offset0(IdxWidth, 0), Offset1(IdxWidth, 0);
6971 const Value *Base0 =
6972 Load0->getPointerOperand()->stripAndAccumulateConstantOffsets(
6973 *
DL, Offset0,
true);
6974 const Value *Base1 =
6975 Load1->getPointerOperand()->stripAndAccumulateConstantOffsets(
6976 *
DL, Offset1,
true);
6981 int64_t LoadSize =
DL->getTypeStoreSize(LoadTy).getFixedValue();
6982 std::optional<int64_t> Dist = (Offset1 - Offset0).trySExtValue();
6983 LoadInst *LowLoad, *HighLoad;
6984 if (Dist == LoadSize) {
6987 }
else if (Dist == -LoadSize) {
6996 SmallPtrSet<ShuffleVectorInst *, 4> Shuffles;
7000 if (auto *SVI = dyn_cast<ShuffleVectorInst>(U)) {
7001 Shuffles.insert(SVI);
7010 LoadInst *FirstLoad = LowLoad, *LastLoad = HighLoad;
7015 LastLoad->getIterator(), FirstLoc, AA))
7026 auto RemapMask = [&](ShuffleVectorInst *
SV, SmallVectorImpl<int> &NewMask) {
7027 Value *SVOp0 =
SV->getOperand(0);
7028 assert(((SVOp0 == LowLoad &&
SV->getOperand(1) == HighLoad) ||
7029 (SVOp0 == HighLoad &&
SV->getOperand(1) == LowLoad)) &&
7030 "Shuffle operands must be exactly {LowLoad, HighLoad} or {HighLoad, "
7032 SV->getShuffleMask(NewMask);
7033 if (SVOp0 == HighLoad)
7048 for (ShuffleVectorInst *SV : Shuffles) {
7050 CostKind,
SV->getShuffleMask());
7052 RemapMask(SV, NewMask);
7060 WideTy, CostKind, NewMask);
7063 LLVM_DEBUG(
dbgs() <<
"Found adjacent loads feeding shuffles: " << *LowLoad
7064 <<
", " << *HighLoad <<
"\n OldCost: " << OldCost
7065 <<
" vs NewCost: " << NewCost <<
"\n");
7067 if (!NewCost.
isValid() || NewCost > OldCost)
7072 LoadInst *InsertPt = LastLoad;
7089 for (ShuffleVectorInst *SV : Shuffles) {
7091 RemapMask(SV, NewMask);
7098 replaceValue(*SV, *NewShuf,
false);
7107bool VectorCombine::shrinkPhiOfShuffles(Instruction &
I) {
7109 if (!Phi ||
Phi->getNumIncomingValues() != 2u)
7113 ArrayRef<int> Mask0;
7114 ArrayRef<int> Mask1;
7127 auto const InputNumElements = InputVT->getNumElements();
7129 if (InputNumElements >= ResultVT->getNumElements())
7134 SmallVector<int, 16> NewMask;
7137 auto IsPoison = [InputNumElements](
int M) {
7138 return M < 0 || (unsigned)M >= InputNumElements;
7141 for (
auto [
M0,
M1] :
zip(Mask0, Mask1)) {
7142 bool P0 = IsPoison(
M0);
7143 bool P1 = IsPoison(
M1);
7159 int MaskOffset = NewMask[0
u];
7160 unsigned Index = (InputNumElements + MaskOffset) % InputNumElements;
7163 for (
unsigned I = 0u;
I < InputNumElements; ++
I) {
7177 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
7180 if (NewCost > OldCost)
7191 auto *NewPhi = Builder.
CreatePHI(NewShuf0->getType(), 2u);
7193 NewPhi->addIncoming(
Op,
Phi->getIncomingBlock(1u));
7199 replaceValue(*Phi, *NewShuf1);
7205bool VectorCombine::run() {
7206 if (Opts.disable_vector_combine)
7219 auto Opcode =
I.getOpcode();
7227 if (IsFixedVectorType) {
7229 case Instruction::InsertElement:
7230 if (vectorizeLoadInsert(
I))
7233 case Instruction::ShuffleVector:
7234 if (widenSubvectorLoad(
I))
7245 if (scalarizeOpOrCmp(
I))
7247 if (scalarizeLoad(
I))
7249 if (scalarizeExtExtract(
I))
7251 if (foldInterleaveIntrinsics(
I))
7253 if (foldBitcastOfVPLoad(
I))
7257 if (foldDeinterleaveIntrinsics(
I))
7260 if (Opcode == Instruction::Store)
7261 if (foldInsertElementsToStores(
I))
7265 if (TryEarlyFoldsOnly)
7268 if (Opcode == Instruction::Call)
7269 if (foldBitOrderReverseAndSwap(
I))
7271 if (Opcode == Instruction::BitCast)
7272 if (foldBitOrderReverseAndSwap(
I))
7279 if (IsFixedVectorType) {
7281 case Instruction::InsertElement:
7282 if (foldInsExtFNeg(
I))
7284 if (foldInsExtBinop(
I))
7286 if (foldInsExtVectorToShuffle(
I))
7288 if (foldInsertScalarPartsToShuffle(
I))
7291 case Instruction::ShuffleVector:
7292 if (foldPermuteOfBinops(
I))
7294 if (foldShuffleOfBinops(
I))
7296 if (foldShuffleOfSelects(
I))
7298 if (foldShuffleOfCastops(
I))
7300 if (foldShuffleOfShuffles(
I))
7302 if (foldShuffleOfAdjacentLoads(
I))
7304 if (foldPermuteOfIntrinsic(
I))
7306 if (foldShufflesOfLengthChangingShuffles(
I))
7308 if (foldShuffleOfIntrinsics(
I))
7310 if (foldSelectShuffle(
I))
7312 if (foldShuffleToIdentity(
I))
7315 case Instruction::Load:
7316 if (shrinkLoadForShuffles(
I))
7319 case Instruction::BitCast:
7320 if (foldBitcastShuffle(
I))
7322 if (foldSelectsFromBitcast(
I))
7325 case Instruction::And:
7326 case Instruction::Or:
7327 case Instruction::Xor:
7328 if (foldBitOpOfCastops(
I))
7330 if (foldBitOpOfCastConstant(
I))
7333 case Instruction::PHI:
7334 if (shrinkPhiOfShuffles(
I))
7344 case Instruction::Call:
7345 if (foldShuffleFromReductions(
I))
7347 if (foldCastFromReductions(
I))
7350 case Instruction::ExtractElement:
7351 if (foldShuffleChainsToReduce(
I))
7354 case Instruction::ICmp:
7355 if (foldSignBitReductionCmp(
I))
7357 if (foldICmpEqZeroVectorReduce(
I))
7359 if (foldReductionZeroTest(
I))
7361 if (foldEquivalentReductionCmp(
I))
7363 if (foldReduceAddCmpZero(
I))
7366 case Instruction::FCmp:
7367 if (foldExtractExtract(
I))
7370 case Instruction::Or:
7371 if (foldConcatOfBoolMasks(
I))
7376 if (foldExtractExtract(
I))
7378 if (foldExtractedCmps(
I))
7380 if (foldBinopOfReductions(
I))
7389 bool MadeChange =
false;
7390 for (BasicBlock &BB :
F) {
7402 MadeChange |= FoldInst(*
I);
7409 while (!Worklist.isEmpty()) {
7412 while (Instruction *
I = Worklist.popDeferred()) {
7430 MadeChange |= FoldInst(*
I);
7446 CostKind, TryEarlyFoldsOnly);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static const Function * getParent(const Value *V)
This is the interface for LLVM's primary stateless and local alias analysis.
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file defines the DenseMap class.
This is the interface for a simple mod/ref and alias analysis over globals.
const size_t AbstractManglingParser< Derived, Alloc >::NumOps
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
static void eraseInstruction(Instruction &I, const LICMDependencies &Deps)
uint64_t IntrinsicInst * II
FunctionAnalysisManager FAM
This file contains the declarations for profiling metadata utility functions.
SmallVector< MachineOperand, 4 > Cond
This file defines the scope_exit class, which executes user-defined cleanup logic at scope exit.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")
static SymbolRef::Type getType(const Symbol *Sym)
static Value * widenDeinterleavedOperations(ArrayRef< Value * > Members, ElementCount WideEC, IRBuilderBase &Builder)
static bool isEquivBitcast(Value *X, Value *Y)
Helper to peek through bitcasts to the same value.
static SmallVector< Value *, 8 > getInstrOperandsAtIdx(ArrayRef< Value * > Members, unsigned OperandIndex)
Return the operand at OperandIndex of each Members.
static bool isFreeConcat(ArrayRef< InstLane > Item, TTI::TargetCostKind CostKind, const TargetTransformInfo &TTI)
Detect concat of multiple values into a vector.
static void analyzeCostOfVecReduction(const IntrinsicInst &II, TTI::TargetCostKind CostKind, const TargetTransformInfo &TTI, InstructionCost &CostBeforeReduction, InstructionCost &CostAfterReduction)
static Value * generateNewInstTree(ArrayRef< InstLane > Item, Use *From, const DenseSet< std::pair< Value *, Use * > > &IdentityLeafs, const DenseSet< std::pair< Value *, Use * > > &SplatLeafs, const DenseSet< std::pair< Value *, Use * > > &ConcatLeafs, IRBuilderBase &Builder, InstructionWorklist &WorkList, const TargetTransformInfo *TTI)
static SmallVector< InstLane > generateInstLaneVectorFromOperand(ArrayRef< InstLane > Item, int Op)
static Value * createShiftShuffle(Value *Vec, unsigned OldIndex, unsigned NewIndex, IRBuilderBase &Builder)
Create a shuffle that translates (shifts) 1 element from the input vector to a new element location.
std::pair< Value *, int > InstLane
static Value * createWideInstruction(Instruction *NarrowInst, ArrayRef< Value * > NewOperands, VectorType *WideResultTy, IRBuilderBase &Builder)
static unsigned getNumDataOperands(const Instruction *Inst)
Return the number of data operands of Inst.
static bool isKnownNonPositive(const Value *V, const SimplifyQuery &SQ, unsigned Depth=0)
Used by foldReduceAddCmpZero to check if we can prove that a value is non-positive.
static bool isSupportedElementwise(Instruction *Inst)
Return true if Inst is an elementwise operation that can be rebuilt at a wider element count.
static Value * materializeScalarizedGEPIndex(Value *Idx, IntegerType *GEPIndexTy, IRBuilderBase &Builder)
Materialize an index for a scalarized GEP after profitability is known.
static Align computeAlignmentAfterScalarization(Align VectorAlignment, Type *ScalarType, Value *Idx, const DataLayout &DL)
The memory operation on a vector of ScalarType had alignment of VectorAlignment.
static bool feedsIntoVectorReduction(ShuffleVectorInst *SVI)
Returns true if this ShuffleVectorInst eventually feeds into a vector reduction intrinsic (e....
static bool canWidenDeinterleavedOperations(const VectorizeOptions &Opts, ArrayRef< Value * > Members, unsigned &NumScanned)
Check whether the tree of elementwise operations each feeding Members can be rebuilt at the interleav...
static bool canWidenLoad(LoadInst *Load, const TargetTransformInfo &TTI)
static const unsigned InvalidIndex
static Value * getCommonSplatValue(ArrayRef< Value * > Values)
Return the common splat value of Values.
static IntegerType * getScalarizedGEPIndexInfo(VectorType *VecTy, Value *Idx, Type *PtrTy, const DataLayout &DL)
Return the GEP index type if the unsigned vector index Idx can be represented by an inbounds GEP.
static Value * translateExtract(ExtractElementInst *ExtElt, unsigned NewIndex, IRBuilderBase &Builder)
Given an extract element instruction with constant index operand, shuffle the source vector (shift th...
static ScalarizationResult canScalarizeAccess(VectorType *VecTy, Value *Idx, const SimplifyQuery &SQ)
Check if it is legal to scalarize a memory access to VecTy at index Idx.
static unsigned getAlignedNumElements(unsigned MaxIdx, FixedVectorType *LoadTy, const TargetTransformInfo &TTI, const DataLayout &DL)
Given the maximum shuffle index and load vector type, compute the number of elements for the shrunk l...
static InstLane lookThroughShuffles(Value *V, int Lane)
static IntrinsicInst * getCommonDeinterleavedSource(ArrayRef< Value * > Members)
Return the common deinterleave intrinsic if Members are its extracts in field order.
static bool isMemModifiedBetween(const VectorizeOptions &Opts, BasicBlock::iterator Begin, BasicBlock::iterator End, const MemoryLocation &Loc, AAResults &AA)
static constexpr int Concat[]
A manager for alias analyses.
Class for arbitrary precision integers.
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
uint64_t getZExtValue() const
Get zero extended value.
void setBit(unsigned BitPosition)
Set the given bit to 1 whose position is given as "bitPosition".
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
unsigned getBitWidth() const
Return the number of bits in the APInt.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
bool isNegative() const
Determine sign of this APInt.
unsigned countl_one() const
Count the number of leading one bits.
LLVM_ABI APInt sext(unsigned width) const
Sign extend to a new width.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Constructs an APInt value that has the top hiBitsSet bits set.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
bool isOne() const
Determine if this is a value of 1.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Represent a constant reference to an array (0 or more elements consecutively in memory),...
ArrayRef< T > drop_front(size_t N=1) const
Drop the first N elements of the array.
const T & front() const
Get the first element.
size_t size() const
Get the array size.
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
InstListType::iterator iterator
Instruction iterators...
BinaryOps getOpcode() const
Represents analyses that only rely on functions' control flow.
Value * getArgOperand(unsigned i) const
void addParamAttrs(unsigned ArgNo, const AttrBuilder &B)
Adds attributes to the indicated argument.
This is the base class for all instructions that perform data casts.
static LLVM_ABI CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass's ...
This class is the base class for the comparison instructions.
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
bool isFPPredicate() const
static LLVM_ABI std::optional< CmpPredicate > getMatching(CmpPredicate A, CmpPredicate B)
Compares two CmpPredicates taking samesign into account and returns the canonicalized CmpPredicate if...
static LLVM_ABI Constant * getExtractElement(Constant *Vec, Constant *Idx, Type *OnlyIfReducedTy=nullptr)
static LLVM_ABI Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false, bool NSZ=false)
Return the identity constant for a binary opcode.
This is the shared class of boolean and integer constants.
const APInt & getValue() const
Return the constant as an APInt value reference.
This class represents a range of values.
LLVM_ABI ConstantRange urem(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned remainder operation of...
LLVM_ABI ConstantRange binaryAnd(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a binary-and of a value in this ra...
LLVM_ABI bool contains(const APInt &Val) const
Return true if the specified value is in the set.
static LLVM_ABI Constant * getSplat(ElementCount EC, Constant *Elt)
Return a ConstantVector with the specified constant in each element.
static LLVM_ABI Constant * get(ArrayRef< Constant * > V)
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
A parsed version of the target data layout string in and methods for querying it.
iterator find(const_arg_type_t< KeyT > Val)
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)
Implements a dense probed hash-table based set.
Analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
LLVM_ABI bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
static constexpr ElementCount get(ScalarTy MinVal, bool Scalable)
Convenience struct for specifying and reasoning about fast-math flags.
bool noSignedZeros() const
Class to represent fixed width SIMD vectors.
unsigned getNumElements() const
static FixedVectorType * getDoubleElementsVectorType(FixedVectorType *VTy)
static LLVM_ABI FixedVectorType * get(Type *ElementType, unsigned NumElts)
This class represents a freeze function that returns random concrete value if an operand is either a ...
Predicate getSignedPredicate() const
For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.
bool isEquality() const
Return true if this predicate is either EQ or NE.
Common base class shared among various IRBuilders.
LLVM_ABI CallInst * CreateIntrinsicWithoutFolding(Intrinsic::ID ID, ArrayRef< Type * > OverloadTypes, ArrayRef< Value * > Args, FMFSource FMFSource={}, const Twine &Name="", ArrayRef< OperandBundleDef > OpBundles={})
Create a call to intrinsic ID with Args, mangled using OverloadTypes.
Value * CreateNUWMul(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateInsertElement(Type *VecTy, Value *NewElt, Value *Idx, const Twine &Name="")
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
LoadInst * CreateAlignedLoad(Type *Ty, Value *Ptr, MaybeAlign Align, const char *Name)
Value * CreateNoWrapBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, bool IsNUW, bool IsNSW, const Twine &Name="")
LLVM_ABI Value * CreateSelectFMF(Value *C, Value *True, Value *False, FMFSource FMFSource, const Twine &Name="", Instruction *MDFrom=nullptr)
LLVM_ABI Value * CreateVectorSplat(unsigned NumElts, Value *V, const Twine &Name="")
Return a vector value that contains.
Value * CreateExtractValue(Value *Agg, ArrayRef< unsigned > Idxs, const Twine &Name="")
ConstantInt * getTrue()
Get the constant value for i1 true.
LLVM_ABI Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Value * CreateFreeze(Value *V, const Twine &Name="")
void SetCurrentDebugLocation(const DebugLoc &L)
Set location information used by debugging information.
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Value * CreateCast(Instruction::CastOps Op, Value *V, Type *DestTy, const Twine &Name="", MDNode *FPMathTag=nullptr, FMFSource FMFSource={})
Value * CreateIsNotNeg(Value *Arg, const Twine &Name="")
Return a boolean value testing if Arg > -1.
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
Value * CreatePointerBitCastOrAddrSpaceCast(Value *V, Type *DestTy, const Twine &Name="")
Value * CreateFCmpFMF(CmpInst::Predicate P, Value *LHS, Value *RHS, FMFSource FMFSource, const Twine &Name="", MDNode *FPMathTag=nullptr)
ConstantInt * getInt64(uint64_t C)
Get a constant 64-bit value.
LLVM_ABI Value * CreateOrReduce(Value *Src)
Create a vector int OR reduction intrinsic of the source vector.
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Value * CreateCmp(CmpInst::Predicate Pred, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
PHINode * CreatePHI(Type *Ty, unsigned NumReservedValues, const Twine &Name="")
InstTy * Insert(InstTy *I, const Twine &Name="") const
Insert and return the specified instruction.
Value * CreateBinOpFMF(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, FMFSource FMFSource, const Twine &Name="", MDNode *FPMathTag=nullptr)
Value * CreateIsNeg(Value *Arg, const Twine &Name="")
Return a boolean value testing if Arg < 0.
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
LoadInst * CreateLoad(Type *Ty, Value *Ptr, const char *Name)
Provided to resolve 'CreateLoad(Ty, Ptr, "...")' correctly, instead of converting the string to 'bool...
Value * CreateUnOpFMF(Instruction::UnaryOps Opc, Value *V, FMFSource FMFSource, const Twine &Name="", MDNode *FPMathTag=nullptr)
Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
Value * CreateShuffleVector(Value *V1, Value *V2, Value *Mask, const Twine &Name="")
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
LLVM_ABI Value * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > OverloadTypes, ArrayRef< Value * > Args, FMFSource FMFSource={}, const Twine &Name="", ArrayRef< OperandBundleDef > OpBundles={}, function_ref< void(CallInst *)> SetFn=[](CallInst *) {})
Variant to create a possibly constant-folded intrinsic.
StoreInst * CreateStore(Value *Val, Value *Ptr, bool isVolatile=false)
Value * CreateExactBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, bool IsExact, const Twine &Name="")
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
PointerType * getPtrTy(unsigned AddrSpace=0)
Fetch the type representing a pointer.
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateFNegFMF(Value *V, FMFSource FMFSource, const Twine &Name="", MDNode *FPMathTag=nullptr)
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="", bool IsDisjoint=false)
IntegerType * getInt8Ty()
Fetch the type representing an 8-bit integer.
LLVM_ABI Value * CreateUnaryIntrinsic(Intrinsic::ID ID, Value *Op, FMFSource FMFSource={}, const Twine &Name="")
Create a call to intrinsic ID with 1 operand which is mangled on its type.
Provides an 'InsertHelper' that calls a user-provided callback after performing the default insertion...
InstSimplifyFolder - Use InstructionSimplify to fold operations to existing values.
CostType getValue() const
This function is intended to be used as sparingly as possible, since the class provides the full rang...
InstructionWorklist - This is the worklist management logic for InstCombine and other simplification ...
void push(Instruction *I)
Push the instruction onto the worklist stack.
void remove(Instruction *I)
Remove I from the worklist if it exists.
LLVM_ABI void setHasNoUnsignedWrap(bool b=true)
Set or clear the nuw flag on this instruction, which must be an operator which supports this flag.
LLVM_ABI void copyIRFlags(const Value *V, bool IncludeWrapFlags=true)
Convenience method to copy supported exact, fast-math, and (optionally) wrapping flags from V to this...
LLVM_ABI void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
LLVM_ABI void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
LLVM_ABI void setNonNeg(bool b=true)
Set or clear the nneg flag on this instruction, which must be a zext instruction.
LLVM_ABI bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
iterator_range< user_iterator > users()
LLVM_ABI void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
LLVM_ABI FastMathFlags getFastMathFlags() const LLVM_READONLY
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
user_iterator user_begin()
@ CompareCallTargets
Check for equivalence by comparing call targets.
LLVM_ABI AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
bool isIdempotent() const
Return true if the instruction is idempotent:
LLVM_ABI void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
LLVM_ABI bool hasAllowReassoc() const LLVM_READONLY
Determine whether the allow-reassociation flag is set.
Class to represent integer types.
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
A wrapper class for inspecting calls to intrinsic functions.
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
An instruction for reading from memory.
unsigned getPointerAddressSpace() const
Returns the address space of the pointer operand.
void setAlignment(Align Align)
Value * getPointerOperand()
Type * getPointerOperandType() const
Align getAlign() const
Return the alignment of the access that is being performed.
Representation for a specific memory location.
static LLVM_ABI MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
PreservedAnalyses & preserveSet()
Mark an analysis set as preserved.
This class represents the LLVM 'select' instruction.
bool contains(const_arg_type key) const
Check if the SetVector contains the given key.
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
This instruction constructs a fixed permutation of two input vectors.
int getMaskValue(unsigned Elt) const
Return the shuffle mask value of this instruction for the given element index.
static LLVM_ABI bool isValidOperands(const Value *V1, const Value *V2, const Value *Mask)
Return true if a shufflevector instruction can be formed with the specified operands.
VectorType * getType() const
Overload to return most specific vector type.
static LLVM_ABI void getShuffleMask(const Constant *Mask, SmallVectorImpl< int > &Result)
Convert the input shuffle mask operand to a vector of integers.
static LLVM_ABI bool isIdentityMask(ArrayRef< int > Mask, int NumSrcElts)
Return true if this shuffle mask chooses elements from exactly one source vector without lane crossin...
static void commuteShuffleMask(MutableArrayRef< int > Mask, unsigned InVecNumElts)
Change values in a shuffle permute mask assuming the two vector operands of length InVecNumElts have ...
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.
void assign(size_type NumElts, ValueParamT Elt)
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
void setAlignment(Align Align)
Analysis pass providing the TargetTransformInfo.
The instances of the Type class are immutable: once they are created, they are never changed.
LLVM_ABI unsigned getIntegerBitWidth() const
bool isPointerTy() const
True if this is an instance of PointerType.
LLVM_ABI unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
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.
bool isFPOrFPVectorTy() const
Return true if this is a FP type or a vector of FP.
bool isIEEELikeFPTy() const
Return true if this is a well-behaved IEEE-like type, which has a IEEE compatible layout,...
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
const Value * stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL, APInt &Offset) const
This is a wrapper around stripAndAccumulateConstantOffsets with the in-bounds requirement set to fals...
LLVM_ABI bool hasOneUser() const
Return true if there is exactly one user of this value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
LLVM_ABI Align getPointerAlignment(const DataLayout &DL) const
Returns an alignment of the pointer value.
unsigned getValueID() const
Return an ID for the concrete type of this object.
LLVM_ABI bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
LLVM_ABI const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
static LLVM_ABI VectorType * get(Type *ElementType, ElementCount EC)
This static method is the primary way to construct an VectorType.
Type * getElementType() const
std::pair< iterator, bool > insert(const ValueT &V)
constexpr bool hasKnownScalarFactor(const FixedOrScalableQuantity &RHS) const
Returns true if there exists a value X where RHS*X will result in a value whose quantity matches our ...
constexpr ScalarTy getFixedValue() const
constexpr ScalarTy getKnownScalarFactor(const FixedOrScalableQuantity &RHS) const
Returns a value X where RHS*X will result in a value whose quantity matches our own.
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
constexpr ScalarTy getKnownMinValue() const
Returns the minimum value this quantity can represent.
constexpr bool isZero() const
const ParentTy * getParent() const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Abstract Attribute helper functions.
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ BasicBlock
Various leaf nodes.
SpecificConstantMatch m_ZeroInt()
Convenience matchers for specific integer values.
BinaryOp_match< SpecificConstantMatch, SrcTy, TargetOpcode::G_SUB > m_Neg(const SrcTy &&Src)
Matches a register negated by a G_SUB.
AllOnesConstantMatch m_AllOnes()
OneUse_match< SubPat > m_OneUse(const SubPat &SP)
match_combine_and< Ty... > m_CombineAnd(const Ty &...Ps)
Combine pattern matchers matching all of Ps patterns.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
auto m_BSwap(const Opnd0 &Op0)
auto m_Cmp()
Matches any compare instruction and ignore it.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
auto m_BitReverse(const Opnd0 &Op0)
BinaryOp_match< LHS, RHS, Instruction::URem > m_URem(const LHS &L, const RHS &R)
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.
specific_intval< false > m_SpecificInt(const APInt &V)
Match a specific integer value or vector with all elements equal to the value.
bool match(Val *V, const Pattern &P)
match_bind< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
DisjointOr_match< LHS, RHS > m_DisjointOr(const LHS &L, const RHS &R)
BinOpPred_match< LHS, RHS, is_right_shift_op > m_Shr(const LHS &L, const RHS &R)
Matches logical shift operations.
CmpClass_match< LHS, RHS, ICmpInst, true > m_c_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
Matches an ICmp with a predicate over LHS and RHS in either order.
TwoOps_match< Val_t, Idx_t, Instruction::ExtractElement > m_ExtractElt(const Val_t &Val, const Idx_t &Idx)
Matches ExtractElementInst.
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
auto m_BinOp()
Match an arbitrary binary operation and ignore it.
auto m_Value()
Match an arbitrary value and ignore it.
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
auto m_Constant()
Match an arbitrary Constant and ignore it.
TwoOps_match< V1_t, V2_t, Instruction::ShuffleVector > m_Shuffle(const V1_t &v1, const V2_t &v2)
Matches ShuffleVectorInst independently of mask value.
cst_pred_ty< is_non_zero_int > m_NonZeroInt()
Match a non-zero integer or a vector with all non-zero elements.
OneOps_match< OpTy, Instruction::Load > m_Load(const OpTy &Op)
Matches LoadInst.
CastInst_match< OpTy, ZExtInst > m_ZExt(const OpTy &Op)
Matches ZExt.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWShl(const LHS &L, const RHS &R)
auto m_AnyIntrinsic()
Matches any intrinsic call and ignore it.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWMul(const LHS &L, const RHS &R)
is_zero< true > m_Zero()
Match any null constant or a vector with all elements equal to 0.
BinOpPred_match< LHS, RHS, is_bitwiselogic_op, true > m_c_BitwiseLogic(const LHS &L, const RHS &R)
Matches bitwise logic operations in either order.
CastOperator_match< OpTy, Instruction::BitCast > m_BitCast(const OpTy &Op)
Matches BitCast.
match_combine_or< CastInst_match< OpTy, SExtInst >, NNegZExt_match< OpTy > > m_SExtLike(const OpTy &Op)
Match either "sext" or "zext nneg".
auto m_Intrinsic(const Ts &...Ops)
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
auto m_Deinterleave2(const Opnd &Op)
FNeg_match< OpTy, true > m_FNegOrFSubNegZero(const OpTy &X)
Match fneg X or fsub -0.0, X.
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
match_combine_or< CastInst_match< OpTy, ZExtInst >, CastInst_match< OpTy, SExtInst > > m_ZExtOrSExt(const OpTy &Op)
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
auto m_Undef()
Match an arbitrary undef constant.
CastInst_match< OpTy, SExtInst > m_SExt(const OpTy &Op)
Matches SExt.
BinaryOp_match< LHS, RHS, Instruction::Or, true > m_c_Or(const LHS &L, const RHS &R)
Matches an Or with LHS and RHS in either order.
ThreeOps_match< Val_t, Elt_t, Idx_t, Instruction::InsertElement > m_InsertElt(const Val_t &Val, const Elt_t &Elt, const Idx_t &Idx)
Matches InsertElementInst.
auto m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
@ Valid
The data is already valid.
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
@ User
could "use" a pointer
NodeAddr< PhiNode * > Phi
NodeAddr< UseNode * > Use
friend class Instruction
Iterator for Instructions in a `BasicBlock.
unsigned getOpcode(const VPValue *V)
Return the instruction opcode for the recipe defining V or 0 for unsupported recipes and VPValues not...
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.
unsigned Log2_32_Ceil(uint32_t Value)
Return the ceil log base 2 of the specified value, 32 if the value is zero.
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
void stable_sort(R &&Range)
LLVM_ABI cl::opt< bool > ProfcheckDisableMetadataFixes
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each 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.
LLVM_ABI Intrinsic::ID getMinMaxReductionIntrinsicOp(Intrinsic::ID RdxID)
Returns the min/max intrinsic used when expanding a min/max reduction.
LLVM_ABI bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
RelativeUniformCounterPtr Values
LLVM_ABI SDValue peekThroughBitcasts(SDValue V)
Return the non-bitcasted source operand of V if it exists.
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.
LLVM_ABI Value * simplifyUnOp(unsigned Opcode, Value *Op, const SimplifyQuery &Q)
Given operand for a UnaryOperator, fold the result or return null.
scope_exit(Callable) -> scope_exit< Callable >
@ Load
The value being inserted comes from a load (InsertElement only).
LLVM_ABI void copyMetadataForLoad(LoadInst &Dest, const LoadInst &Source)
Copy the metadata from the source instruction to the destination (the replacement for the source inst...
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
LLVM_ABI unsigned getArithmeticReductionInstruction(Intrinsic::ID RdxID)
Returns the arithmetic instruction opcode used when expanding a reduction.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
constexpr bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
LLVM_ABI Value * simplifyCall(CallBase *Call, Value *Callee, ArrayRef< Value * > Args, const SimplifyQuery &Q)
Given a callsite, callee, and arguments, fold the result or return null.
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...
LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
LLVM_ABI bool mustSuppressSpeculation(const LoadInst &LI)
Return true if speculation of the given load must be suppressed to avoid ordering or interfering with...
LLVM_ABI bool widenShuffleMaskElts(int Scale, ArrayRef< int > Mask, SmallVectorImpl< int > &ScaledMask)
Try to transform a shuffle mask by replacing elements with the scaled index for an equivalent mask of...
LLVM_ABI bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true, bool IgnoreUBImplyingAttrs=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
LLVM_ABI Instruction * propagateMetadata(Instruction *I, ArrayRef< Value * > VL)
Specifically, let Kinds = [MD_tbaa, MD_alias_scope, MD_noalias, MD_fpmath, MD_nontemporal,...
LLVM_ABI Value * getSplatValue(const Value *V)
Get splat value if the input is a splat vector or return nullptr.
LLVM_ABI unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Return the number of times the sign bit of the register is replicated into the other bits.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
unsigned M1(unsigned Val)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
LLVM_ABI bool isSplatValue(const Value *V, int Index=-1, unsigned Depth=0)
Return true if each element of the vector value V is poisoned or equal to every other non-poisoned el...
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
auto reverse(ContainerTy &&C)
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
bool isModSet(const ModRefInfo MRI)
void sort(IteratorTy Start, IteratorTy End)
LLVM_ABI bool programUndefinedIfPoison(const Instruction *Inst)
LLVM_ABI unsigned getDeinterleaveIntrinsicFactor(Intrinsic::ID ID)
Returns the corresponding factor of llvm.vector.deinterleaveN intrinsics.
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
constexpr uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
LLVM_ABI unsigned getInterleaveIntrinsicFactor(Intrinsic::ID ID)
Returns the corresponding factor of llvm.vector.interleaveN intrinsics.
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...
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ABI void propagateIRFlags(Value *I, ArrayRef< Value * > VL, Value *OpValue=nullptr, bool IncludeWrapFlags=true)
Get the intersection (logical and) of all of the potential IR flags of each scalar operation (VL) tha...
MutableArrayRef(T &OneElt) -> MutableArrayRef< T >
constexpr int PoisonMaskElem
LLVM_ABI void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
LLVM_ABI bool isSafeToLoadUnconditionally(Value *V, Align Alignment, const APInt &Size, const SimplifyQuery &SQ, bool IgnoreFree=false)
Return true if we know that executing a load from this value cannot trap.
LLVM_ABI Value * simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
LLVM_ABI void narrowShuffleMaskElts(int Scale, ArrayRef< int > Mask, SmallVectorImpl< int > &ScaledMask)
Replace each shuffle mask index with the scaled sequential indices for an equivalent mask of narrowed...
LLVM_ABI Intrinsic::ID getReductionForBinop(Instruction::BinaryOps Opc)
Returns the reduction intrinsic id corresponding to the binary operation.
@ And
Bitwise or logical AND of integers.
LLVM_ABI bool isVectorIntrinsicWithScalarOpAtArg(Intrinsic::ID ID, unsigned ScalarOpdIdx, const TargetTransformInfo *TTI)
Identifies if the vector form of the intrinsic has a scalar operand.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
DWARFExpression::Operation Op
unsigned M0(unsigned Val)
ArrayRef(const T &OneElt) -> ArrayRef< T >
LLVM_ABI bool willNotFreeBetween(const Instruction *Assume, const Instruction *CtxI, const DominatorTree *DT=nullptr)
Returns true, if no instruction between Assume and CtxI may free (including through synchronization).
constexpr unsigned BitWidth
LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
LLVM_ABI Constant * getLosslessInvCast(Constant *C, Type *InvCastTo, unsigned CastOp, const DataLayout &DL, PreservedCastFlags *Flags=nullptr)
Try to cast C to InvC losslessly, satisfying CastOp(InvC) equals C, or CastOp(InvC) is a refined valu...
const VectorizeOptions & getVectorizeOptions(const LLVMContext &C)
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
constexpr bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Align commonAlignment(Align A, uint64_t Offset)
Returns the alignment that satisfies both alignments.
bool all_equal(std::initializer_list< T > Values)
Returns true if all Values in the initializer lists are equal or the list.
LLVM_ABI Value * simplifyCmpInst(CmpPredicate Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a CmpInst, fold the result or return null.
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Returns true if V cannot be poison, but may be undef.
@ End
Run the machine verifier once, at the end of the pipeline.
LLVM_ABI bool isKnownNonNegative(const Value *V, const SimplifyQuery &SQ, unsigned Depth=0)
Returns true if the give value is known to be non-negative.
LLVM_ABI bool isTriviallyVectorizable(Intrinsic::ID ID)
Identify if the intrinsic is trivially vectorizable.
LLVM_ABI Intrinsic::ID getMinMaxReductionIntrinsicID(Intrinsic::ID IID)
Returns the llvm.vector.reduce min/max intrinsic that corresponds to the intrinsic op.
LLVM_ABI ConstantRange computeConstantRange(const Value *V, bool ForSigned, const SimplifyQuery &SQ, unsigned Depth=0)
Determine the possible constant range of an integer or vector of integer value.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
LLVM_ABI AAMDNodes adjustForAccess(unsigned AccessSize)
Create a new AAMDNode for accessing AccessSize bytes of this AAMDNode.
This struct is a compact representation of a valid (non-zero power of two) alignment.
unsigned countMaxActiveBits() const
Returns the maximum number of bits needed to represent all possible unsigned values with these known ...
unsigned countMinLeadingZeros() const
Returns the minimum number of leading zero bits.
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
SimplifyQuery getWithInstruction(const Instruction *I) const