47#define DEBUG_TYPE "vector-combine"
53STATISTIC(NumVecLoad,
"Number of vector loads formed");
54STATISTIC(NumVecCmp,
"Number of vector compares formed");
55STATISTIC(NumVecBO,
"Number of vector binops formed");
56STATISTIC(NumVecCmpBO,
"Number of vector compare + binop formed");
57STATISTIC(NumShufOfBitcast,
"Number of shuffles moved after bitcast");
58STATISTIC(NumScalarOps,
"Number of scalar unary + binary ops formed");
59STATISTIC(NumScalarCmp,
"Number of scalar compares formed");
60STATISTIC(NumScalarIntrinsic,
"Number of scalar intrinsic calls formed");
62static const unsigned InvalidIndex = std::numeric_limits<unsigned>::max();
67 VectorCombine(
const VectorizeOptions &Opts,
Function &
F,
78 TTI(TTI), DT(DT), AA(AA),
DL(DL), CostKind(CostKind),
79 SQ(*DL,
nullptr, &DT, &AC),
80 TryEarlyFoldsOnly(TryEarlyFoldsOnly) {}
85 const VectorizeOptions &Opts;
87 IRBuilder<InstSimplifyFolder, IRBuilderCallbackInserter> Builder;
88 const TargetTransformInfo &TTI;
89 const DominatorTree &DT;
93 const SimplifyQuery SQ;
97 bool TryEarlyFoldsOnly;
99 InstructionWorklist Worklist;
108 bool vectorizeLoadInsert(Instruction &
I);
109 bool widenSubvectorLoad(Instruction &
I);
110 ExtractElementInst *getShuffleExtract(ExtractElementInst *Ext0,
111 ExtractElementInst *Ext1,
112 unsigned PreferredExtractIndex)
const;
113 bool isExtractExtractCheap(ExtractElementInst *Ext0, ExtractElementInst *Ext1,
114 const Instruction &
I,
115 ExtractElementInst *&ConvertToShuffle,
116 unsigned PreferredExtractIndex);
119 bool foldExtractExtract(Instruction &
I);
120 bool foldInsExtFNeg(Instruction &
I);
121 bool foldInsExtBinop(Instruction &
I);
122 bool foldInsExtVectorToShuffle(Instruction &
I);
123 bool foldInsertScalarPartsToShuffle(Instruction &
I);
124 bool foldBitOpOfCastops(Instruction &
I);
125 bool foldBitOpOfCastConstant(Instruction &
I);
126 bool foldBitcastShuffle(Instruction &
I);
127 bool scalarizeOpOrCmp(Instruction &
I);
128 bool foldExtractedCmps(Instruction &
I);
129 bool foldSelectsFromBitcast(Instruction &
I);
130 bool foldBinopOfReductions(Instruction &
I);
131 bool foldInsertElementsToStores(Instruction &
I);
132 bool scalarizeLoad(Instruction &
I);
133 bool scalarizeLoadExtract(LoadInst *LI, VectorType *VecTy,
Value *Ptr);
134 bool scalarizeLoadBitcast(LoadInst *LI, VectorType *VecTy,
Value *Ptr);
135 bool scalarizeExtExtract(Instruction &
I);
136 bool foldConcatOfBoolMasks(Instruction &
I);
137 bool foldPermuteOfBinops(Instruction &
I);
138 bool foldShuffleOfBinops(Instruction &
I);
139 bool foldShuffleOfSelects(Instruction &
I);
140 bool foldShuffleOfCastops(Instruction &
I);
141 bool foldShuffleOfShuffles(Instruction &
I);
142 bool foldShuffleOfAdjacentLoads(Instruction &
I);
143 bool foldPermuteOfIntrinsic(Instruction &
I);
144 bool foldShufflesOfLengthChangingShuffles(Instruction &
I);
145 bool foldShuffleOfIntrinsics(Instruction &
I);
146 bool foldShuffleToIdentity(Instruction &
I);
147 bool foldShuffleFromReductions(Instruction &
I);
148 bool foldShuffleChainsToReduce(Instruction &
I);
149 bool foldCastFromReductions(Instruction &
I);
150 bool foldSignBitReductionCmp(Instruction &
I);
151 bool foldReductionZeroTest(Instruction &
I);
152 bool foldICmpEqZeroVectorReduce(Instruction &
I);
153 bool foldEquivalentReductionCmp(Instruction &
I);
154 bool foldReduceAddCmpZero(Instruction &
I);
155 bool foldSelectShuffle(Instruction &
I,
bool FromReduction =
false);
156 bool foldInterleaveIntrinsics(Instruction &
I);
157 bool foldDeinterleaveIntrinsics(Instruction &
I);
158 bool foldBitcastOfVPLoad(Instruction &
I);
159 bool foldBitOrderReverseAndSwap(Instruction &
I);
160 bool shrinkType(Instruction &
I);
161 bool shrinkLoadForShuffles(Instruction &
I);
162 bool shrinkPhiOfShuffles(Instruction &
I);
163 bool foldInterleaveOfDeinterleaveChains(Instruction &
I);
165 void replaceValue(Instruction &Old,
Value &New,
bool Erase =
true) {
171 Worklist.pushUsersToWorkList(*NewI);
172 Worklist.pushValue(NewI);
189 SmallPtrSet<Value *, 4> Visited;
194 OpI,
nullptr,
nullptr, [&](
Value *V) {
199 NextInst = NextInst->getNextNode();
204 Worklist.pushUsersToWorkList(*OpI);
205 Worklist.pushValue(OpI);
223 return X->getType() ==
Y->getType() &&
232 Load->getFunction()->hasFnAttribute(Attribute::SanitizeMemTag) ||
238 Type *ScalarTy =
Load->getType()->getScalarType();
240 unsigned MinVectorSize =
TTI.getMinVectorRegisterBitWidth();
241 if (!ScalarSize || !MinVectorSize || MinVectorSize % ScalarSize != 0 ||
248bool VectorCombine::vectorizeLoadInsert(
Instruction &
I) {
274 Value *SrcPtr =
Load->getPointerOperand()->stripPointerCasts();
277 unsigned MinVecNumElts = MinVectorSize / ScalarSize;
278 auto *MinVecTy = VectorType::get(ScalarTy, MinVecNumElts,
false);
279 unsigned OffsetEltIndex = 0;
290 unsigned OffsetBitWidth =
DL->getIndexTypeSizeInBits(SrcPtr->
getType());
291 APInt
Offset(OffsetBitWidth, 0);
301 uint64_t ScalarSizeInBytes = ScalarSize / 8;
302 if (
Offset.urem(ScalarSizeInBytes) != 0)
306 APInt OffsetEltIndexAP =
Offset.udiv(ScalarSizeInBytes);
307 if (OffsetEltIndexAP.
uge(MinVecNumElts))
326 unsigned AS =
Load->getPointerAddressSpace();
332 true, HasExtract, CostKind);
345 unsigned OutputNumElts = Ty->getNumElements();
347 assert(OffsetEltIndex < MinVecNumElts &&
"Address offset too big");
348 Mask[0] = OffsetEltIndex;
355 if (OldCost < NewCost || !NewCost.
isValid())
366 replaceValue(
I, *VecLd);
374bool VectorCombine::widenSubvectorLoad(Instruction &
I) {
377 if (!Shuf->isIdentityWithPadding())
383 unsigned OpIndex =
any_of(Shuf->getShuffleMask(), [&NumOpElts](
int M) {
384 return M >= (int)(NumOpElts);
407 unsigned AS =
Load->getPointerAddressSpace();
422 if (OldCost < NewCost || !NewCost.
isValid())
429 replaceValue(
I, *VecLd);
436ExtractElementInst *VectorCombine::getShuffleExtract(
437 ExtractElementInst *Ext0, ExtractElementInst *Ext1,
441 assert(Index0C && Index1C &&
"Expected constant extract indexes");
443 unsigned Index0 = Index0C->getZExtValue();
444 unsigned Index1 = Index1C->getZExtValue();
447 if (Index0 == Index1)
471 if (PreferredExtractIndex == Index0)
473 if (PreferredExtractIndex == Index1)
477 return Index0 > Index1 ? Ext0 : Ext1;
485bool VectorCombine::isExtractExtractCheap(ExtractElementInst *Ext0,
486 ExtractElementInst *Ext1,
487 const Instruction &
I,
488 ExtractElementInst *&ConvertToShuffle,
489 unsigned PreferredExtractIndex) {
492 assert(Ext0IndexC && Ext1IndexC &&
"Expected constant extract indexes");
494 unsigned Opcode =
I.getOpcode();
507 assert((Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) &&
508 "Expected a compare");
518 unsigned Ext0Index = Ext0IndexC->getZExtValue();
519 unsigned Ext1Index = Ext1IndexC->getZExtValue();
533 unsigned BestExtIndex = Extract0Cost > Extract1Cost ? Ext0Index : Ext1Index;
534 unsigned BestInsIndex = Extract0Cost > Extract1Cost ? Ext1Index : Ext0Index;
535 InstructionCost CheapExtractCost = std::min(Extract0Cost, Extract1Cost);
540 if (Ext0Src == Ext1Src && Ext0Index == Ext1Index) {
545 bool HasUseTax = Ext0 == Ext1 ? !Ext0->
hasNUses(2)
547 OldCost = CheapExtractCost + ScalarOpCost;
548 NewCost = VectorOpCost + CheapExtractCost + HasUseTax * CheapExtractCost;
552 OldCost = Extract0Cost + Extract1Cost + ScalarOpCost;
553 NewCost = VectorOpCost + CheapExtractCost +
558 ConvertToShuffle = getShuffleExtract(Ext0, Ext1, PreferredExtractIndex);
559 if (ConvertToShuffle) {
560 if (IsBinOp && Opts.disable_binop_extract_shuffle)
571 SmallVector<int> ShuffleMask(FixedVecTy->getNumElements(),
573 ShuffleMask[BestInsIndex] = BestExtIndex;
575 VecTy, VecTy, CostKind, ShuffleMask, 0,
576 nullptr, {ConvertToShuffle});
579 VecTy, VecTy, CostKind, {}, 0,
nullptr,
584 LLVM_DEBUG(
dbgs() <<
"Found a binop of extractions: " <<
I <<
"\n OldCost: "
585 << OldCost <<
" vs NewCost: " << NewCost <<
"\n");
590 return OldCost < NewCost;
602 ShufMask[NewIndex] = OldIndex;
603 return Builder.CreateShuffleVector(Vec, ShufMask,
"shift");
655 V1,
"foldExtExtBinop");
660 VecBOInst->copyIRFlags(&
I);
666bool VectorCombine::foldExtractExtract(Instruction &
I) {
682 V0->getType() !=
V1->getType())
687 unsigned NumElts = FixedVecTy->getNumElements();
688 if (
C0 >= NumElts ||
C1 >= NumElts)
704 ExtractElementInst *ExtractToChange;
705 if (isExtractExtractCheap(Ext0, Ext1,
I, ExtractToChange, InsertIndex))
711 if (ExtractToChange) {
712 unsigned CheapExtractIdx = ExtractToChange == Ext0 ?
C1 :
C0;
717 if (ExtractToChange == Ext0)
726 ? foldExtExtCmp(ExtOp0, ExtOp1, ExtIndex,
I)
727 : foldExtExtBinop(ExtOp0, ExtOp1, ExtIndex,
I);
728 replaceValue(
I, *NewExt);
734bool VectorCombine::foldInsExtFNeg(Instruction &
I) {
753 auto *DstVecScalarTy = DstVecTy->getScalarType();
755 if (!SrcVecTy || DstVecScalarTy != SrcVecTy->getScalarType())
760 unsigned NumDstElts = DstVecTy->getNumElements();
761 unsigned NumSrcElts = SrcVecTy->getNumElements();
762 if (ExtIdx > NumSrcElts || InsIdx >= NumDstElts || NumDstElts == 1)
768 SmallVector<int>
Mask(NumDstElts);
769 std::iota(
Mask.begin(),
Mask.end(), 0);
770 Mask[InsIdx] = (ExtIdx % NumDstElts) + NumDstElts;
784 DstVecTy, CostKind, Mask);
786 bool NeedLenChg = SrcVecTy->getNumElements() != NumDstElts;
789 SmallVector<int> SrcMask;
792 SrcMask[ExtIdx % NumDstElts] = ExtIdx;
794 DstVecTy, SrcVecTy, CostKind, SrcMask);
798 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
800 if (NewCost > OldCost)
803 Value *NewShuf, *LenChgShuf =
nullptr;
815 replaceValue(
I, *NewShuf);
821bool VectorCombine::foldInsExtBinop(Instruction &
I) {
822 BinaryOperator *VecBinOp, *SclBinOp;
854 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
856 if (NewCost > OldCost)
867 NewInst->copyIRFlags(VecBinOp);
868 NewInst->andIRFlags(SclBinOp);
871 replaceValue(
I, *NewBO);
877bool VectorCombine::foldBitOpOfCastops(Instruction &
I) {
880 if (!BinOp || !BinOp->isBitwiseLogicOp())
886 if (!LHSCast || !RHSCast) {
887 LLVM_DEBUG(
dbgs() <<
" One or both operands are not cast instructions\n");
893 if (CastOpcode != RHSCast->getOpcode())
897 switch (CastOpcode) {
898 case Instruction::BitCast:
899 case Instruction::Trunc:
900 case Instruction::SExt:
901 case Instruction::ZExt:
907 Value *LHSSrc = LHSCast->getOperand(0);
908 Value *RHSSrc = RHSCast->getOperand(0);
914 auto *SrcTy = LHSSrc->
getType();
915 auto *DstTy =
I.getType();
918 if (CastOpcode != Instruction::BitCast &&
923 if (!SrcTy->getScalarType()->isIntegerTy() ||
924 !DstTy->getScalarType()->isIntegerTy())
939 LHSCastCost + RHSCastCost;
950 if (!LHSCast->hasOneUse())
951 NewCost += LHSCastCost;
952 if (!RHSCast->hasOneUse())
953 NewCost += RHSCastCost;
956 <<
" NewCost=" << NewCost <<
"\n");
958 if (NewCost > OldCost)
963 BinOp->getName() +
".inner");
965 NewBinOp->copyIRFlags(BinOp);
977 replaceValue(
I, *Result);
986bool VectorCombine::foldBitOpOfCastConstant(Instruction &
I) {
1002 switch (CastOpcode) {
1003 case Instruction::BitCast:
1004 case Instruction::ZExt:
1005 case Instruction::SExt:
1006 case Instruction::Trunc:
1012 Value *LHSSrc = LHSCast->getOperand(0);
1014 auto *SrcTy = LHSSrc->
getType();
1015 auto *DstTy =
I.getType();
1018 if (CastOpcode != Instruction::BitCast &&
1023 if (!SrcTy->getScalarType()->isIntegerTy() ||
1024 !DstTy->getScalarType()->isIntegerTy())
1028 PreservedCastFlags RHSFlags;
1053 if (!LHSCast->hasOneUse())
1054 NewCost += LHSCastCost;
1056 LLVM_DEBUG(
dbgs() <<
"foldBitOpOfCastConstant: OldCost=" << OldCost
1057 <<
" NewCost=" << NewCost <<
"\n");
1059 if (NewCost > OldCost)
1064 LHSSrc, InvC,
I.getName() +
".inner");
1066 NewBinOp->copyIRFlags(&
I);
1084 replaceValue(
I, *Result);
1091bool VectorCombine::foldBitcastShuffle(Instruction &
I) {
1105 if (!DestTy || !SrcTy)
1108 unsigned DestEltSize = DestTy->getScalarSizeInBits();
1109 unsigned SrcEltSize = SrcTy->getScalarSizeInBits();
1110 if (SrcTy->getPrimitiveSizeInBits() % DestEltSize != 0)
1120 if (!(BCTy0 && BCTy0->getElementType() == DestTy->getElementType()) &&
1121 !(BCTy1 && BCTy1->getElementType() == DestTy->getElementType()))
1125 SmallVector<int, 16> NewMask;
1126 if (DestEltSize <= SrcEltSize) {
1129 if (SrcEltSize % DestEltSize != 0)
1131 unsigned ScaleFactor = SrcEltSize / DestEltSize;
1136 if (DestEltSize % SrcEltSize != 0)
1138 unsigned ScaleFactor = DestEltSize / SrcEltSize;
1145 unsigned NumSrcElts = SrcTy->getPrimitiveSizeInBits() / DestEltSize;
1146 auto *NewShuffleTy =
1148 auto *OldShuffleTy =
1150 unsigned NumOps = IsUnary ? 1 : 2;
1160 TargetTransformInfo::CastContextHint::None,
1165 TargetTransformInfo::CastContextHint::None,
1168 LLVM_DEBUG(
dbgs() <<
"Found a bitcasted shuffle: " <<
I <<
"\n OldCost: "
1169 << OldCost <<
" vs NewCost: " << NewCost <<
"\n");
1171 if (NewCost > OldCost || !NewCost.
isValid())
1179 replaceValue(
I, *Shuf);
1186bool VectorCombine::scalarizeOpOrCmp(Instruction &
I) {
1191 if (!UO && !BO && !CI && !
II)
1199 if (Arg->getType() !=
II->getType() &&
1209 for (User *U :
I.users())
1216 std::optional<uint64_t>
Index;
1218 auto Ops =
II ?
II->args() :
I.operands();
1227 if (OpTy->getElementCount().getKnownMinValue() <= InsIdx)
1233 else if (InsIdx != *Index)
1250 if (!
Index.has_value())
1254 Type *ScalarTy = VecTy->getScalarType();
1255 assert(VecTy->isVectorTy() &&
1258 "Unexpected types for insert element into binop or cmp");
1260 unsigned Opcode =
I.getOpcode();
1268 }
else if (UO || BO) {
1272 IntrinsicCostAttributes ScalarICA(
1273 II->getIntrinsicID(), ScalarTy,
1276 IntrinsicCostAttributes VectorICA(
1277 II->getIntrinsicID(), VecTy,
1284 Value *NewVecC =
nullptr;
1286 NewVecC =
simplifyCmpInst(CI->getPredicate(), VecCs[0], VecCs[1], SQ);
1289 simplifyUnOp(UO->getOpcode(), VecCs[0], UO->getFastMathFlags(), SQ);
1291 NewVecC =
simplifyBinOp(BO->getOpcode(), VecCs[0], VecCs[1], SQ);
1303 CostKind, *Index, NewVecC);
1305 for (
auto [Idx,
Op, VecC, Scalar] :
enumerate(
Ops, VecCs, ScalarOps)) {
1307 II->getIntrinsicID(), Idx, &
TTI)))
1310 Instruction::InsertElement, VecTy, CostKind, *Index, VecC, Scalar);
1311 OldCost += InsertCost;
1312 NewCost += !
Op->hasOneUse() * InsertCost;
1316 if (OldCost < NewCost || !NewCost.
isValid())
1326 ++NumScalarIntrinsic;
1329 for (
auto [OpIdx, Scalar, VecC] :
enumerate(ScalarOps, VecCs))
1341 ScalarOps[1], FPMO->getFastMathFlags(),
1342 CI->getName() +
".scalar");
1345 ScalarOps[1], CI->getName() +
".scalar");
1349 UO->getName() +
".scalar");
1351 if (OverflowingBinaryOperator *OBO =
1354 BO->getOpcode(), ScalarOps[0], ScalarOps[1], OBO->hasNoUnsignedWrap(),
1355 OBO->hasNoSignedWrap(), BO->getName() +
".scalar");
1358 BO->getName() +
".scalar", PDI->isDisjoint());
1359 }
else if (PossiblyExactOperator *PEO =
1363 PEO->isExact(), BO->getName() +
".scalar");
1366 ScalarOps[1], FPMO->getFastMathFlags(),
1367 BO->getName() +
".scalar");
1370 BO->getName() +
".scalar");
1375 FMF = FPMO->getFastMathFlags();
1377 FMF,
II->getName() +
".scalar");
1381 replaceValue(
I, *Insert);
1388bool VectorCombine::foldExtractedCmps(Instruction &
I) {
1393 if (!BI || !
I.getType()->isIntegerTy(1))
1398 Value *
B0 =
I.getOperand(0), *
B1 =
I.getOperand(1);
1401 CmpPredicate
P0,
P1;
1420 ExtractElementInst *ConvertToShuf = getShuffleExtract(Ext0, Ext1, CostKind);
1423 assert((ConvertToShuf == Ext0 || ConvertToShuf == Ext1) &&
1424 "Unknown ExtractElementInst");
1429 unsigned CmpOpcode =
1435 if (Index0 >= VecTy->getNumElements() || Index1 >= VecTy->getNumElements())
1447 Ext0Cost + Ext1Cost + CmpCost * 2 +
1453 int CheapIndex = ConvertToShuf == Ext0 ? Index1 : Index0;
1454 int ExpensiveIndex = ConvertToShuf == Ext0 ? Index0 : Index1;
1459 ShufMask[CheapIndex] = ExpensiveIndex;
1461 CmpTy, CostKind, ShufMask);
1464 NewCost += Ext0->
hasOneUse() ? 0 : Ext0Cost;
1465 NewCost += Ext1->
hasOneUse() ? 0 : Ext1Cost;
1470 if (OldCost < NewCost || !NewCost.
isValid())
1480 Value *
LHS = ConvertToShuf == Ext0 ? Shuf : VCmp;
1481 Value *
RHS = ConvertToShuf == Ext0 ? VCmp : Shuf;
1484 replaceValue(
I, *NewExt);
1511bool VectorCombine::foldSelectsFromBitcast(Instruction &
I) {
1518 if (!SrcVecTy || !DstVecTy)
1528 if (SrcEltBits != 32 && SrcEltBits != 64)
1531 if (!DstEltTy->
isIntegerTy() || DstEltBits >= SrcEltBits)
1548 if (!ScalarSelCost.
isValid() || ScalarSelCost == 0)
1551 unsigned MinSelects = (VecSelCost.
getValue() / ScalarSelCost.
getValue()) + 1;
1554 if (!BC->hasNUsesOrMore(MinSelects))
1559 DenseMap<Value *, SmallVector<SelectInst *, 8>> CondToSelects;
1561 for (User *U : BC->users()) {
1566 for (User *ExtUser : Ext->users()) {
1570 Cond->getType()->isIntegerTy(1))
1575 if (CondToSelects.
empty())
1578 bool MadeChange =
false;
1579 Value *SrcVec = BC->getOperand(0);
1582 for (
auto [
Cond, Selects] : CondToSelects) {
1584 if (Selects.size() < MinSelects) {
1585 LLVM_DEBUG(
dbgs() <<
"VectorCombine: foldSelectsFromBitcast not "
1586 <<
"profitable (VecCost=" << VecSelCost
1587 <<
", ScalarCost=" << ScalarSelCost
1588 <<
", NumSelects=" << Selects.size() <<
")\n");
1593 auto InsertPt = std::next(BC->getIterator());
1597 InsertPt = std::next(CondInst->getIterator());
1605 for (SelectInst *Sel : Selects) {
1607 Value *
Idx = Ext->getIndexOperand();
1611 replaceValue(*Sel, *NewExt);
1616 <<
" selects into vector select\n");
1630 unsigned ReductionOpc =
1636 CostBeforeReduction =
1637 TTI.getCastInstrCost(RedOp->getOpcode(), VecRedTy, ExtType,
1639 CostAfterReduction =
1640 TTI.getExtendedReductionCost(ReductionOpc, IsUnsigned,
II.getType(),
1644 if (RedOp &&
II.getIntrinsicID() == Intrinsic::vector_reduce_add &&
1650 (Op0->
getOpcode() == RedOp->getOpcode() || Op0 == Op1)) {
1657 TTI.getCastInstrCost(Op0->
getOpcode(), MulType, ExtType,
1660 TTI.getArithmeticInstrCost(Instruction::Mul, MulType, CostKind);
1662 TTI.getCastInstrCost(RedOp->getOpcode(), VecRedTy, MulType,
1665 CostBeforeReduction = ExtCost * 2 + MulCost + Ext2Cost;
1666 CostAfterReduction =
TTI.getMulAccReductionCost(
1667 IsUnsigned, ReductionOpc,
II.getType(), ExtType, CostKind);
1670 CostAfterReduction =
TTI.getArithmeticReductionCost(ReductionOpc, VecRedTy,
1671 std::nullopt, CostKind);
1674bool VectorCombine::foldBinopOfReductions(Instruction &
I) {
1677 if (BinOpOpc == Instruction::Sub)
1678 ReductionIID = Intrinsic::vector_reduce_add;
1682 if (ReductionIID == Intrinsic::vector_reduce_fadd ||
1683 ReductionIID == Intrinsic::vector_reduce_fmul)
1686 auto checkIntrinsicAndGetItsArgument = [](
Value *
V,
1691 if (
II->getIntrinsicID() == IID &&
II->hasOneUse())
1692 return II->getArgOperand(0);
1696 Value *
V0 = checkIntrinsicAndGetItsArgument(
I.getOperand(0), ReductionIID);
1699 Value *
V1 = checkIntrinsicAndGetItsArgument(
I.getOperand(1), ReductionIID);
1704 if (
V1->getType() != VTy)
1708 unsigned ReductionOpc =
1721 CostOfRedOperand0 + CostOfRedOperand1 +
1724 if (NewCost >= OldCost || !NewCost.
isValid())
1728 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
1731 if (BinOpOpc == Instruction::Or)
1738 replaceValue(
I, *Rdx);
1748 unsigned NumScanned = 0;
1751 ++NumScanned > Opts.vector_combine_max_scan_instrs;
1763class ScalarizationResult {
1764 enum class StatusTy { Unsafe,
Safe, SafeWithFreeze };
1769 ScalarizationResult(StatusTy Status,
Value *ToFreeze =
nullptr)
1770 : Status(Status), ToFreeze(ToFreeze) {}
1773 ScalarizationResult(
const ScalarizationResult &
Other) =
default;
1774 ~ScalarizationResult() {
1775 assert(!ToFreeze &&
"freeze() not called with ToFreeze being set");
1778 static ScalarizationResult unsafe() {
return {StatusTy::Unsafe}; }
1779 static ScalarizationResult safe() {
return {StatusTy::Safe}; }
1780 static ScalarizationResult safeWithFreeze(
Value *ToFreeze) {
1781 return {StatusTy::SafeWithFreeze, ToFreeze};
1785 bool isSafe()
const {
return Status == StatusTy::Safe; }
1787 bool isUnsafe()
const {
return Status == StatusTy::Unsafe; }
1790 bool isSafeWithFreeze()
const {
return Status == StatusTy::SafeWithFreeze; }
1795 Status = StatusTy::Unsafe;
1799 void freeze(IRBuilderBase &Builder, Instruction &UserI) {
1800 assert(isSafeWithFreeze() &&
1801 "should only be used when freezing is required");
1803 "UserI must be a user of ToFreeze");
1804 IRBuilder<>::InsertPointGuard Guard(Builder);
1809 if (
U.get() == ToFreeze)
1824 uint64_t NumElements = VecTy->getElementCount().getKnownMinValue();
1825 unsigned IntWidth = Idx->getType()->getScalarSizeInBits();
1828 if (
C->getValue().ult(NumElements))
1829 return ScalarizationResult::safe();
1830 return ScalarizationResult::unsafe();
1835 return ScalarizationResult::unsafe();
1837 APInt Zero(IntWidth, 0);
1838 APInt MaxElts(IntWidth, NumElements);
1845 return ScalarizationResult::safe();
1846 return ScalarizationResult::unsafe();
1859 if (ValidIndices.
contains(IdxRange))
1860 return ScalarizationResult::safeWithFreeze(IdxBase);
1861 return ScalarizationResult::unsafe();
1881 unsigned GEPBits = GEPIndexTy->getBitWidth();
1882 uint64_t NumElements = VecTy->getElementCount().getKnownMinValue();
1884 uint64_t MaxLane = NumElements - 1;
1886 if (
C->getValue().uge(NumElements))
1888 MaxLane =
C->getZExtValue();
1892 if (!
DL.typeSizeEqualsStoreSize(
ElemTy))
1912 unsigned WideBits = std::max(GEPBits, 128u);
1913 APInt MaxLaneValue(WideBits, MaxLane);
1914 APInt ByteOffset = MaxLaneValue;
1919 if (ByteOffset.
ugt(MaxGEPOffset))
1930 unsigned SrcBits = Idx->getType()->getIntegerBitWidth();
1932 if (SrcBits >= DstBits)
1935 return Builder.CreateZExt(Idx, GEPIndexTy, Idx->getName() +
".gepidx");
1947 C->getZExtValue() *
DL.getTypeStoreSize(ScalarType));
1984bool VectorCombine::foldInsertElementsToStores(Instruction &
I) {
1999 if (!
Insert->hasOneUse())
2007 if (InsertElements.
empty())
2012 std::reverse(InsertElements.
begin(), InsertElements.
end());
2021 if (InsertElements.
size() == FVT->getNumElements()) {
2022 Value *FirstVal = InsertElements.
front().first;
2023 if (
all_of(InsertElements,
2024 [FirstVal](
const auto &Elt) {
return Elt.first == FirstVal; }))
2028 Value *SrcAddr =
Load->getPointerOperand()->stripPointerCasts();
2033 if (!
Load->isSimple() ||
Load->getParent() !=
SI->getParent() ||
2034 !
DL->typeSizeEqualsStoreSize(
Load->getType()->getScalarType()) ||
2035 SrcAddr !=
SI->getPointerOperand()->stripPointerCasts())
2045 for (
auto [InsertVal, Idx] : InsertElements) {
2046 auto ScalarizableIdx =
2048 if (ScalarizableIdx.isUnsafe())
2054 ScalarizableIdx.discard();
2060 ScalarizableIdx.discard();
2064 Instruction::Store,
SI->getValueOperand()->getType(),
SI->getAlign(),
2065 SI->getPointerAddressSpace(), CostKind);
2067 if (
Load->hasOneUse())
2070 Load->getPointerAddressSpace(), CostKind);
2072 for (
auto [InsertVal, Idx] : InsertElements) {
2075 Index = CIdx->getZExtValue();
2086 for (
auto [InsertVal, Idx] : InsertElements) {
2089 const Value *GEPIndices[] = {ConstantInt::get(
Idx->getType(), 0),
Idx};
2091 CostKind, InsertVal->
getType());
2094 for (
auto [InsertVal, Idx] : InsertElements) {
2096 std::max(
SI->getAlign(),
Load->getAlign()), InsertVal->
getType(), Idx,
2101 SI->getPointerAddressSpace(), CostKind);
2104 LLVM_DEBUG(
dbgs() <<
"Found an insert-elements vector store scalarization "
2107 <<
" NumInserts: " << InsertElements.size() <<
"\n"
2108 <<
" OldCost: " << OldCost <<
" vs NewCost: " << NewCost
2111 if (OldCost <= NewCost)
2114 for (
auto [InsertVal, Idx] : InsertElements) {
2115 auto ScalarizableIdx =
2117 assert(!ScalarizableIdx.isUnsafe() &&
"already checked above");
2119 if (ScalarizableIdx.isSafeWithFreeze())
2124 StoreInst *LastStore =
nullptr;
2125 for (
auto [InsertVal, Idx] : InsertElements) {
2126 auto ScalarizableIdx =
2128 if (ScalarizableIdx.isUnsafe())
2131 IntegerType *GEPIndexTy =
2136 SI->getValueOperand()->getType(),
SI->getPointerOperand(),
2137 {ConstantInt::get(GEPIdx->getType(), 0), GEPIdx});
2144 LastStore->
setMetadata(LLVMContext::MD_invariant_group,
nullptr);
2146 std::max(
SI->getAlign(),
Load->getAlign()), InsertVal->
getType(), Idx,
2151 replaceValue(
I, *LastStore);
2158bool VectorCombine::scalarizeLoad(Instruction &
I) {
2168 if (!LI->isSimple() || !
DL->typeSizeEqualsStoreSize(VecTy->getScalarType()))
2171 bool AllExtracts =
true;
2172 bool AllBitcasts =
true;
2174 unsigned NumInstChecked = 0;
2179 for (User *U : LI->users()) {
2181 if (!UI || UI->getParent() != LI->getParent())
2186 if (UI->use_empty())
2190 AllExtracts =
false;
2192 AllBitcasts =
false;
2196 for (Instruction &
I :
2197 make_range(std::next(LI->getIterator()), UI->getIterator())) {
2200 if (NumInstChecked == Opts.vector_combine_max_scan_instrs ||
2201 I.mayWriteToMemory())
2205 LastCheckedInst = UI;
2210 return scalarizeLoadExtract(LI, VecTy, Ptr);
2212 return scalarizeLoadBitcast(LI, VecTy, Ptr);
2217bool VectorCombine::scalarizeLoadExtract(LoadInst *LI, VectorType *VecTy,
2222 DenseMap<ExtractElementInst *, ScalarizationResult> NeedFreeze;
2223 DenseMap<ExtractElementInst *, IntegerType *> GEPIndexInfos;
2226 for (
auto &Pair : NeedFreeze)
2227 Pair.second.discard();
2235 for (User *U : LI->
users()) {
2240 if (ScalarIdx.isUnsafe())
2246 ScalarIdx.discard();
2252 if (ScalarIdx.isSafeWithFreeze()) {
2253 NeedFreeze.try_emplace(UI, ScalarIdx);
2254 ScalarIdx.discard();
2260 Index ?
Index->getZExtValue() : -1);
2265 nullptr,
nullptr, CostKind);
2266 if (!Index && UI->getIndexOperand()->getType()->getIntegerBitWidth() <
2269 Instruction::ZExt, GEPIndex, UI->getIndexOperand()->getType(),
2273 LLVM_DEBUG(
dbgs() <<
"Found all extractions of a vector load: " << *LI
2274 <<
"\n LoadExtractCost: " << OriginalCost
2275 <<
" vs ScalarizedCost: " << ScalarizedCost <<
"\n");
2277 if (ScalarizedCost > OriginalCost)
2279 if (ScalarizedCost == OriginalCost && !LI->
hasOneUse())
2286 Type *ElemType = VecTy->getElementType();
2289 for (User *U : LI->
users()) {
2291 Value *
Idx = EI->getIndexOperand();
2294 if (
auto It = NeedFreeze.find(EI); It != NeedFreeze.end())
2298 auto It = GEPIndexInfos.
find(EI);
2300 "Missing scalarized GEP index information");
2303 VecTy, Ptr, {ConstantInt::get(GEPIdx->
getType(), 0), GEPIdx});
2305 Builder.
CreateLoad(ElemType,
GEP, EI->getName() +
".scalar"));
2307 Align ScalarOpAlignment =
2309 NewLoad->setAlignment(ScalarOpAlignment);
2312 size_t Offset = ConstIdx->getZExtValue() *
DL->getTypeStoreSize(ElemType);
2317 replaceValue(*EI, *NewLoad,
false);
2320 FailureGuard.release();
2325bool VectorCombine::scalarizeLoadBitcast(LoadInst *LI, VectorType *VecTy,
2334 Type *TargetScalarType =
nullptr;
2335 unsigned VecBitWidth =
DL->getTypeSizeInBits(VecTy);
2337 for (User *U : LI->
users()) {
2340 Type *DestTy = BC->getDestTy();
2344 unsigned DestBitWidth =
DL->getTypeSizeInBits(DestTy);
2345 if (DestBitWidth != VecBitWidth)
2349 if (!TargetScalarType)
2350 TargetScalarType = DestTy;
2351 else if (TargetScalarType != DestTy)
2359 if (!TargetScalarType)
2367 LLVM_DEBUG(
dbgs() <<
"Found vector load feeding only bitcasts: " << *LI
2368 <<
"\n OriginalCost: " << OriginalCost
2369 <<
" vs ScalarizedCost: " << ScalarizedCost <<
"\n");
2371 if (ScalarizedCost >= OriginalCost)
2382 ScalarLoad->copyMetadata(*LI);
2385 for (User *U : LI->
users()) {
2387 replaceValue(*BC, *ScalarLoad,
false);
2393bool VectorCombine::scalarizeExtExtract(Instruction &
I) {
2408 Type *ScalarDstTy = DstTy->getElementType();
2409 if (
DL->getTypeSizeInBits(SrcTy) !=
DL->getTypeSizeInBits(ScalarDstTy))
2415 unsigned ExtCnt = 0;
2416 bool ExtLane0 =
false;
2417 for (User *U : Ext->users()) {
2423 if (Idx >= SrcTy->getNumElements())
2435 Instruction::And, ScalarDstTy, CostKind,
2438 (ExtCnt - ExtLane0) *
2440 Instruction::LShr, ScalarDstTy, CostKind,
2443 if (ScalarCost > VectorCost)
2446 Value *ScalarV = Ext->getOperand(0);
2453 SmallDenseSet<ConstantInt *, 8> ExtractedLanes;
2454 bool AllExtractsTriggerUB =
true;
2455 ExtractElementInst *LastExtract =
nullptr;
2457 for (User *U : Ext->users()) {
2460 AllExtractsTriggerUB =
false;
2464 if (!LastExtract || LastExtract->
comesBefore(Extract))
2465 LastExtract = Extract;
2467 if (ExtractedLanes.
size() != DstTy->getNumElements() ||
2468 !AllExtractsTriggerUB ||
2476 uint64_t SrcEltSizeInBits =
DL->getTypeSizeInBits(SrcTy->getElementType());
2477 uint64_t TotalBits =
DL->getTypeSizeInBits(SrcTy);
2480 Value *
Mask = ConstantInt::get(PackedTy, EltBitMask);
2481 for (User *U : Ext->users()) {
2487 ? (TotalBits - SrcEltSizeInBits -
Idx * SrcEltSizeInBits)
2488 : (
Idx * SrcEltSizeInBits);
2491 U->replaceAllUsesWith(
And);
2499bool VectorCombine::foldConcatOfBoolMasks(Instruction &
I) {
2500 Type *Ty =
I.getType();
2505 if (
DL->isBigEndian())
2532 if (ShAmtX > ShAmtY) {
2540 uint64_t ShAmtDiff = ShAmtY - ShAmtX;
2541 unsigned NumSHL = (ShAmtX > 0) + (ShAmtY > 0);
2546 MaskTy->getNumElements() != ShAmtDiff ||
2547 MaskTy->getNumElements() > (
BitWidth / 2))
2552 Type::getIntNTy(Ty->
getContext(), ConcatTy->getNumElements());
2553 auto *MaskIntTy = Type::getIntNTy(Ty->
getContext(), ShAmtDiff);
2556 std::iota(ConcatMask.begin(), ConcatMask.end(), 0);
2570 MaskTy, CostKind, ConcatMask);
2573 if (Ty != ConcatIntTy)
2579 LLVM_DEBUG(
dbgs() <<
"Found a concatenation of bitcasted bool masks: " <<
I
2580 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
2583 if (NewCost > OldCost)
2592 if (Ty != ConcatIntTy) {
2600 replaceValue(
I, *Result);
2606bool VectorCombine::foldPermuteOfBinops(Instruction &
I) {
2607 BinaryOperator *BinOp;
2608 ArrayRef<int> OuterMask;
2616 Value *Op00, *Op01, *Op10, *Op11;
2617 ArrayRef<int> Mask0, Mask1;
2622 if (!Match0 && !Match1)
2635 if (!ShuffleDstTy || !BinOpTy || !Op0Ty || !Op1Ty)
2638 unsigned NumSrcElts = BinOpTy->getNumElements();
2643 any_of(OuterMask, [NumSrcElts](
int M) {
return M >= (int)NumSrcElts; }))
2647 SmallVector<int> NewMask0, NewMask1;
2648 for (
int M : OuterMask) {
2649 if (M < 0 || M >= (
int)NumSrcElts) {
2653 NewMask0.
push_back(Match0 ? Mask0[M] : M);
2654 NewMask1.
push_back(Match1 ? Mask1[M] : M);
2658 unsigned NumOpElts = Op0Ty->getNumElements();
2659 bool IsIdentity0 = ShuffleDstTy == Op0Ty &&
2660 all_of(NewMask0, [NumOpElts](
int M) {
return M < (int)NumOpElts; }) &&
2662 bool IsIdentity1 = ShuffleDstTy == Op1Ty &&
2663 all_of(NewMask1, [NumOpElts](
int M) {
return M < (int)NumOpElts; }) &&
2672 ShuffleDstTy, BinOpTy, CostKind, OuterMask,
2673 0,
nullptr, {BinOp}, &
I);
2675 NewCost += BinOpCost;
2681 OldCost += Shuf0Cost;
2683 NewCost += Shuf0Cost;
2689 OldCost += Shuf1Cost;
2691 NewCost += Shuf1Cost;
2699 Op0Ty, CostKind, NewMask0, 0,
nullptr, {Op00, Op01});
2703 Op1Ty, CostKind, NewMask1, 0,
nullptr, {Op10, Op11});
2705 LLVM_DEBUG(
dbgs() <<
"Found a shuffle feeding a shuffled binop: " <<
I
2706 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
2710 if (NewCost > OldCost)
2721 NewInst->copyIRFlags(BinOp);
2723 replaceValue(
I, *NewBO);
2729bool VectorCombine::foldShuffleOfBinops(Instruction &
I) {
2730 ArrayRef<int> OldMask;
2737 if (
LHS->getOpcode() !=
RHS->getOpcode())
2741 bool IsCommutative =
false;
2750 IsCommutative = BinaryOperator::isCommutative(BO->getOpcode());
2761 if (!ShuffleDstTy || !BinResTy || !BinOpTy ||
X->getType() !=
Z->getType())
2764 bool SameBinOp =
LHS ==
RHS;
2765 unsigned NumSrcElts = BinOpTy->getNumElements();
2768 if (IsCommutative &&
X != Z &&
Y != W && (
X == W ||
Y == Z))
2771 auto ConvertToUnary = [NumSrcElts](
int &
M) {
2772 if (M >= (
int)NumSrcElts)
2776 SmallVector<int> NewMask0(OldMask);
2785 SmallVector<int> NewMask1(OldMask);
2804 ShuffleDstTy, BinResTy, CostKind, OldMask, 0,
2815 ArrayRef<int> InnerMask;
2817 m_Mask(InnerMask)))) &&
2820 [NumSrcElts](
int M) {
return M < (int)NumSrcElts; })) {
2835 bool ReducedInstCount =
false;
2836 ReducedInstCount |= MergeInner(
X, 0, NewMask0, CostKind,
LHS);
2837 ReducedInstCount |= MergeInner(
Y, 0, NewMask1, CostKind,
LHS);
2838 ReducedInstCount |= MergeInner(Z, NumSrcElts, NewMask0, CostKind,
RHS);
2839 ReducedInstCount |= MergeInner(W, NumSrcElts, NewMask1, CostKind,
RHS);
2840 bool SingleSrcBinOp = (
X ==
Y) && (Z == W) && (NewMask0 == NewMask1);
2852 I.getType()->getScalarType()->isIntegerTy(1) &&
2856 auto *ShuffleCmpTy =
2859 SK0, ShuffleCmpTy, BinOpTy, CostKind, NewMask0, 0,
nullptr, {
X,
Z});
2860 if (!SingleSrcBinOp)
2862 NewMask1, 0,
nullptr, {
Y,
W});
2866 CostKind, Op0Info, Op1Info);
2870 PredLHS, CostKind, Op0Info, Op1Info);
2880 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
2887 if (ReducedInstCount ? (NewCost > OldCost) : (NewCost >= OldCost))
2896 : Builder.
CreateCmp(PredLHS, Shuf0, Shuf1);
2900 NewInst->copyIRFlags(
LHS);
2901 NewInst->andIRFlags(
RHS);
2904 replaceValue(
I, *NewBO);
2911bool VectorCombine::foldShuffleOfSelects(Instruction &
I) {
2924 if (!C1VecTy || !C2VecTy || C1VecTy != C2VecTy)
2930 if (((SI0FOp ==
nullptr) != (SI1FOp ==
nullptr)) ||
2931 ((SI0FOp !=
nullptr) &&
2932 (SI0FOp->getFastMathFlags() != SI1FOp->getFastMathFlags())))
2938 auto SelOp = Instruction::Select;
2946 CostSel1 + CostSel2 +
2948 {
I.getOperand(0),
I.getOperand(1)}, &
I);
2952 CostKind, Mask, 0,
nullptr, {C1, C2});
2962 if (!Sel1->hasOneUse())
2963 NewCost += CostSel1;
2964 if (!Sel2->hasOneUse())
2965 NewCost += CostSel2;
2968 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
2970 if (NewCost > OldCost)
2979 NewSel = Builder.
CreateSelectFMF(ShuffleCmp, ShuffleTrue, ShuffleFalse,
2980 SI0FOp->getFastMathFlags());
2982 NewSel = Builder.
CreateSelect(ShuffleCmp, ShuffleTrue, ShuffleFalse);
2984 replaceValue(
I, *NewSel);
2990bool VectorCombine::foldShuffleOfCastops(Instruction &
I) {
2992 ArrayRef<int> OldMask;
3001 if (!
C0 || (IsBinaryShuffle && !
C1))
3008 if (!IsBinaryShuffle && Opcode == Instruction::BitCast)
3011 if (IsBinaryShuffle) {
3012 if (
C0->getSrcTy() !=
C1->getSrcTy())
3015 if (Opcode !=
C1->getOpcode()) {
3017 Opcode = Instruction::SExt;
3026 if (!ShuffleDstTy || !CastDstTy || !CastSrcTy)
3029 unsigned NumSrcElts = CastSrcTy->getNumElements();
3030 unsigned NumDstElts = CastDstTy->getNumElements();
3031 assert((NumDstElts == NumSrcElts || Opcode == Instruction::BitCast) &&
3032 "Only bitcasts expected to alter src/dst element counts");
3036 if (NumDstElts != NumSrcElts && (NumSrcElts % NumDstElts) != 0 &&
3037 (NumDstElts % NumSrcElts) != 0)
3040 SmallVector<int, 16> NewMask;
3041 if (NumSrcElts >= NumDstElts) {
3044 assert(NumSrcElts % NumDstElts == 0 &&
"Unexpected shuffle mask");
3045 unsigned ScaleFactor = NumSrcElts / NumDstElts;
3050 assert(NumDstElts % NumSrcElts == 0 &&
"Unexpected shuffle mask");
3051 unsigned ScaleFactor = NumDstElts / NumSrcElts;
3056 auto *NewShuffleDstTy =
3065 if (IsBinaryShuffle)
3072 OldMask, 0,
nullptr, {}, &
I);
3075 CastSrcTy, CostKind, NewMask);
3078 if (!
C0->hasOneUse())
3080 if (IsBinaryShuffle) {
3085 if (!
C1->hasOneUse())
3090 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
3092 if (NewCost > OldCost)
3096 if (IsBinaryShuffle)
3106 NewInst->copyIRFlags(
C0);
3107 if (IsBinaryShuffle)
3108 NewInst->andIRFlags(
C1);
3111 replaceValue(
I, *Cast);
3121bool VectorCombine::foldShuffleOfShuffles(Instruction &
I) {
3122 ArrayRef<int> OuterMask;
3123 Value *OuterV0, *OuterV1;
3128 ArrayRef<int> InnerMask0, InnerMask1;
3129 Value *X0, *X1, *Y0, *Y1;
3134 if (!Match0 && !Match1)
3139 SmallVector<int, 16> PoisonMask1;
3144 InnerMask1 = PoisonMask1;
3148 X0 = Match0 ? X0 : OuterV0;
3149 Y0 = Match0 ? Y0 : OuterV0;
3150 X1 = Match1 ? X1 : OuterV1;
3151 Y1 = Match1 ? Y1 : OuterV1;
3155 if (!ShuffleDstTy || !ShuffleSrcTy || !ShuffleImmTy ||
3159 unsigned NumSrcElts = ShuffleSrcTy->getNumElements();
3160 unsigned NumImmElts = ShuffleImmTy->getNumElements();
3165 SmallVector<int, 16> NewMask(OuterMask);
3166 Value *NewX =
nullptr, *NewY =
nullptr;
3167 for (
int &M : NewMask) {
3168 Value *Src =
nullptr;
3169 if (0 <= M && M < (
int)NumImmElts) {
3173 Src =
M >= (int)NumSrcElts ? Y0 : X0;
3174 M =
M >= (int)NumSrcElts ? (M - NumSrcElts) :
M;
3176 }
else if (M >= (
int)NumImmElts) {
3181 Src =
M >= (int)NumSrcElts ? Y1 : X1;
3182 M =
M >= (int)NumSrcElts ? (M - NumSrcElts) :
M;
3186 assert(0 <= M && M < (
int)NumSrcElts &&
"Unexpected shuffle mask index");
3195 if (!NewX || NewX == Src) {
3199 if (!NewY || NewY == Src) {
3218 replaceValue(
I, *NewX);
3235 bool IsUnary =
all_of(NewMask, [&](
int M) {
return M < (int)NumSrcElts; });
3241 nullptr, {NewX, NewY});
3243 NewCost += InnerCost0;
3245 NewCost += InnerCost1;
3248 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
3250 if (NewCost > OldCost)
3254 replaceValue(
I, *Shuf);
3270bool VectorCombine::foldShufflesOfLengthChangingShuffles(Instruction &
I) {
3275 unsigned ChainLength = 0;
3276 SmallVector<int>
Mask;
3277 SmallVector<int> YMask;
3287 ArrayRef<int> OuterMask;
3288 Value *OuterV0, *OuterV1;
3289 if (ChainLength != 0 && !Trunk->
hasOneUse())
3292 m_Mask(OuterMask))))
3294 if (OuterV0->
getType() != TrunkType) {
3300 ArrayRef<int> InnerMask0, InnerMask1;
3306 bool Match0Leaf = Match0 && A0->
getType() !=
I.getType();
3307 bool Match1Leaf = Match1 && A1->
getType() !=
I.getType();
3308 if (Match0Leaf == Match1Leaf) {
3314 SmallVector<int> CommutedOuterMask;
3321 for (
int &M : CommutedOuterMask) {
3324 if (M < (
int)NumTrunkElts)
3329 OuterMask = CommutedOuterMask;
3348 int NumLeafElts = YType->getNumElements();
3349 SmallVector<int> LocalYMask(InnerMask1);
3350 for (
int &M : LocalYMask) {
3351 if (M >= NumLeafElts)
3361 Mask.assign(OuterMask);
3362 YMask.
assign(LocalYMask);
3363 OldCost = NewCost = LocalOldCost;
3370 SmallVector<int> NewYMask(YMask);
3372 for (
auto [CombinedM, LeafM] :
llvm::zip(NewYMask, LocalYMask)) {
3373 if (LeafM == -1 || CombinedM == LeafM)
3375 if (CombinedM == -1) {
3385 SmallVector<int> NewMask;
3386 NewMask.
reserve(NumTrunkElts);
3387 for (
int M : Mask) {
3388 if (M < 0 || M >=
static_cast<int>(NumTrunkElts))
3399 YType, CostKind, NewYMask) +
3401 TrunkType, CostKind, NewMask);
3403 if (LocalNewCost >= NewCost && LocalOldCost < LocalNewCost - NewCost)
3407 if (ChainLength == 1) {
3408 dbgs() <<
"Found chain of shuffles fed by length-changing shuffles: "
3411 dbgs() <<
" next chain link: " << *Trunk <<
'\n'
3412 <<
" old cost: " << (OldCost + LocalOldCost)
3413 <<
" new cost: " << LocalNewCost <<
'\n';
3418 OldCost += LocalOldCost;
3419 NewCost = LocalNewCost;
3423 if (ChainLength <= 1)
3431 return M < 0 || M >=
static_cast<int>(NumTrunkElts);
3434 for (
int &M : Mask) {
3435 if (M >=
static_cast<int>(NumTrunkElts))
3436 M = YMask[
M - NumTrunkElts];
3440 replaceValue(
I, *Root);
3447 replaceValue(
I, *Root);
3453bool VectorCombine::foldShuffleOfIntrinsics(Instruction &
I) {
3455 ArrayRef<int> OldMask;
3465 if (IID != II1->getIntrinsicID())
3474 if (!ShuffleDstTy || !II0Ty)
3480 for (
unsigned Idx = 0,
E = II0->arg_size(); Idx !=
E; ++Idx) {
3481 Value *Arg0 = II0->getArgOperand(Idx);
3482 Value *Arg1 = II1->getArgOperand(Idx);
3499 II0Ty, CostKind, OldMask, 0,
nullptr, {II0, II1}, &
I);
3503 SmallDenseSet<std::pair<Value *, Value *>> SeenOperandPairs;
3504 for (
unsigned Idx = 0,
E = II0->arg_size(); Idx !=
E; ++Idx) {
3506 NewArgsTy.
push_back(II0->getArgOperand(Idx)->getType());
3510 ShuffleDstTy->getNumElements());
3512 std::pair<Value *, Value *> OperandPair =
3513 std::make_pair(II0->getArgOperand(Idx), II1->getArgOperand(Idx));
3514 if (!SeenOperandPairs.
insert(OperandPair).second) {
3520 OldMask, 0,
nullptr,
3521 {II0->getArgOperand(Idx), II1->getArgOperand(Idx)});
3524 IntrinsicCostAttributes NewAttr(IID, ShuffleDstTy, NewArgsTy);
3527 if (!II0->hasOneUse())
3529 if (II1 != II0 && !II1->hasOneUse())
3533 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
3536 if (NewCost > OldCost)
3540 SmallDenseMap<std::pair<Value *, Value *>,
Value *> ShuffleCache;
3541 for (
unsigned Idx = 0,
E = II0->arg_size(); Idx !=
E; ++Idx) {
3543 NewArgs.
push_back(II0->getArgOperand(Idx));
3545 std::pair<Value *, Value *> OperandPair =
3546 std::make_pair(II0->getArgOperand(Idx), II1->getArgOperand(Idx));
3547 auto It = ShuffleCache.
find(OperandPair);
3548 if (It != ShuffleCache.
end()) {
3554 II0->getArgOperand(Idx), II1->getArgOperand(Idx), OldMask);
3555 ShuffleCache[OperandPair] = Shuf;
3563 NewInst->copyIRFlags(II0);
3564 NewInst->andIRFlags(II1);
3567 replaceValue(
I, *NewIntrinsic);
3573bool VectorCombine::foldPermuteOfIntrinsic(Instruction &
I) {
3585 if (!ShuffleDstTy || !IntrinsicSrcTy)
3589 unsigned NumSrcElts = IntrinsicSrcTy->getNumElements();
3590 if (
any_of(Mask, [NumSrcElts](
int M) {
return M >= (int)NumSrcElts; }))
3603 IntrinsicSrcTy, CostKind, Mask, 0,
nullptr, {
V0}, &
I);
3607 for (
unsigned I = 0,
E = II0->arg_size();
I !=
E; ++
I) {
3609 NewArgsTy.
push_back(II0->getArgOperand(
I)->getType());
3613 ShuffleDstTy->getNumElements());
3616 ArgTy, VecTy, CostKind, Mask, 0,
nullptr,
3617 {II0->getArgOperand(
I)});
3620 IntrinsicCostAttributes NewAttr(IID, ShuffleDstTy, NewArgsTy);
3625 if (!II0->hasOneUse())
3628 LLVM_DEBUG(
dbgs() <<
"Found a permute of intrinsic: " <<
I <<
"\n OldCost: "
3629 << OldCost <<
" vs NewCost: " << NewCost <<
"\n");
3631 if (NewCost > OldCost)
3636 for (
unsigned I = 0,
E = II0->arg_size();
I !=
E; ++
I) {
3648 NewInst->copyIRFlags(II0);
3650 replaceValue(
I, *NewIntrinsic);
3660 int M = SV->getMaskValue(Lane);
3663 if (
static_cast<unsigned>(M) < NumElts) {
3664 V = SV->getOperand(0);
3667 V = SV->getOperand(1);
3678 auto [U, Lane] = IL;
3691 unsigned NumElts = Ty->getNumElements();
3692 if (Item.
size() == NumElts || NumElts == 1 || Item.
size() % NumElts != 0)
3698 std::iota(ConcatMask.
begin(), ConcatMask.
end(), 0);
3701 Ty, CostKind, ConcatMask) != 0)
3704 unsigned NumSlices = Item.
size() / NumElts;
3709 for (
unsigned Slice = 0; Slice < NumSlices; ++Slice) {
3710 Value *SliceV = Item[Slice * NumElts].first;
3711 if (!SliceV || SliceV->
getType() != Ty)
3713 for (
unsigned Elt = 0; Elt < NumElts; ++Elt) {
3714 auto [V, Lane] = Item[Slice * NumElts + Elt];
3715 if (Lane !=
static_cast<int>(Elt) || SliceV != V)
3724 const DenseSet<std::pair<Value *, Use *>> &IdentityLeafs,
3725 const DenseSet<std::pair<Value *, Use *>> &SplatLeafs,
3726 const DenseSet<std::pair<Value *, Use *>> &ConcatLeafs,
3729 auto [FrontV, FrontLane] = Item.
front();
3731 if (IdentityLeafs.contains(std::make_pair(FrontV, From))) {
3734 if (SplatLeafs.contains(std::make_pair(FrontV, From))) {
3736 return Builder.CreateShuffleVector(FrontV, Mask);
3738 if (ConcatLeafs.contains(std::make_pair(FrontV, From))) {
3742 for (
unsigned S = 0; S <
Values.size(); ++S)
3743 Values[S] = Item[S * NumElts].first;
3745 while (
Values.size() > 1) {
3748 std::iota(Mask.begin(), Mask.end(), 0);
3750 for (
unsigned S = 0; S < NewValues.
size(); ++S)
3752 Builder.CreateShuffleVector(
Values[S * 2],
Values[S * 2 + 1], Mask);
3766 if (BCDstTy && BCSrcTy &&
3767 BCDstTy->getElementCount() != BCSrcTy->getElementCount()) {
3768 unsigned DstElts = BCDstTy->getNumElements();
3769 unsigned SrcElts = BCSrcTy->getNumElements();
3771 if (DstElts > SrcElts) {
3773 unsigned R = DstElts / SrcElts;
3774 if (Item.
size() % R != 0)
3776 for (
unsigned Idx = 0,
E = Item.
size(); Idx <
E; Idx += R) {
3777 auto [V, Lane] = Item[Idx];
3787 unsigned R = SrcElts / DstElts;
3788 for (
auto [V, Lane] : Item) {
3794 for (
unsigned J = 0; J < R; ++J)
3799 IdentityLeafs, SplatLeafs, ConcatLeafs,
3800 Builder, WorkList,
TTI);
3801 return Builder.CreateBitCast(
3806 unsigned NumOps =
I->getNumOperands() - (
II ? 1 : 0);
3808 for (
unsigned Idx = 0; Idx <
NumOps; Idx++) {
3811 Ops[Idx] =
II->getOperand(Idx);
3816 IdentityLeafs, SplatLeafs, ConcatLeafs, Builder, WorkList,
TTI);
3828 for (
const auto &Lane : Item)
3841 auto *
Value = Builder.CreateCmp(CI->getPredicate(),
Ops[0],
Ops[1]);
3851 auto *
Value = Builder.CreateCast(CI->getOpcode(),
Ops[0], DstTy);
3856 auto *
Value = Builder.CreateIntrinsic(DstTy,
II->getIntrinsicID(),
Ops);
3870bool VectorCombine::foldShuffleToIdentity(Instruction &
I) {
3872 if (!Ty ||
I.use_empty())
3876 for (
unsigned M = 0,
E = Ty->getNumElements(); M <
E; ++M)
3880 Candidates.
push_back(std::make_pair(Start, &*
I.use_begin()));
3881 DenseSet<std::pair<Value *, Use *>> IdentityLeafs, SplatLeafs, ConcatLeafs;
3882 unsigned NumVisited = 0;
3883 bool TraversedElCountChangingBitcast =
false;
3885 while (!Candidates.
empty()) {
3886 if (++NumVisited > Opts.vector_combine_max_scan_instrs)
3890 auto Item = ItemFrom.first;
3891 auto From = ItemFrom.second;
3892 auto [FrontV, FrontLane] = Item.front();
3899 if (FrontLane == 0 &&
3903 Value *FrontV = Item.front().first;
3905 E.value().second == (int)
E.index());
3907 IdentityLeafs.
insert(std::make_pair(FrontV, From));
3912 C &&
C->getSplatValue() &&
3914 Value *FrontV = Item.front().first;
3920 SplatLeafs.
insert(std::make_pair(FrontV, From));
3925 auto [FrontV, FrontLane] = Item.front();
3926 auto [
V, Lane] = IL;
3927 return !
V || (
V == FrontV && Lane == FrontLane);
3929 SplatLeafs.
insert(std::make_pair(FrontV, From));
3935 auto CheckLaneIsEquivalentToFirst = [Item](
InstLane IL) {
3936 Value *FrontV = Item.front().first;
3945 if (CI->getPredicate() !=
cast<CmpInst>(FrontV)->getPredicate())
3948 if (CI->getSrcTy()->getScalarType() !=
3953 SI->getOperand(0)->getType() !=
3960 II->getIntrinsicID() ==
3962 !
II->hasOperandBundles());
3969 BO && BO->isIntDivRem())
3976 }
else if (
isa<UnaryOperator, TruncInst, ZExtInst, SExtInst, FPToSIInst,
3977 FPToUIInst, SIToFPInst, UIToFPInst>(FrontV)) {
3984 if (BCDstTy && BCSrcTy) {
3985 ElementCount DstEC = BCDstTy->getElementCount();
3986 ElementCount SrcEC = BCSrcTy->getElementCount();
3987 if (DstEC == SrcEC) {
3990 &BitCast->getOperandUse(0));
3995 if (DstElts > SrcElts && DstElts % SrcElts == 0) {
3999 unsigned R = DstElts / SrcElts;
4001 bool Valid = Item.size() %
R == 0;
4002 for (
unsigned Idx = 0,
E = Item.size(); Valid && Idx <
E;
4004 auto [
V0, L0] = Item[
Idx];
4007 [](
InstLane IL) {
return IL.first !=
nullptr; })) {
4018 for (
unsigned J = 1; J <
R; ++J) {
4019 auto [VJ, LJ] = Item[
Idx + J];
4020 if (!VJ || VJ != V0 || LJ != L0 + (
int)J) {
4031 TraversedElCountChangingBitcast =
true;
4032 Candidates.
emplace_back(NItem, &BitCast->getOperandUse(0));
4035 }
else if (SrcElts > DstElts && SrcElts % DstElts == 0) {
4038 unsigned R = SrcElts / DstElts;
4040 for (
auto [V, Lane] : Item) {
4046 for (
unsigned J = 0; J <
R; ++J)
4049 TraversedElCountChangingBitcast =
true;
4050 Candidates.
emplace_back(NItem, &BitCast->getOperandUse(0));
4056 &Sel->getOperandUse(0));
4058 &Sel->getOperandUse(1));
4060 &Sel->getOperandUse(2));
4064 !
II->hasOperandBundles()) {
4065 for (
unsigned Op = 0,
E =
II->getNumOperands() - 1;
Op <
E;
Op++) {
4069 Value *FrontV = Item.front().first;
4086 ConcatLeafs.
insert(std::make_pair(FrontV, From));
4093 if (NumVisited <= 1)
4099 if (NumVisited == 2 && TraversedElCountChangingBitcast)
4102 LLVM_DEBUG(
dbgs() <<
"Found a superfluous identity shuffle: " <<
I <<
"\n");
4109 ConcatLeafs, Builder, Worklist, &
TTI);
4110 replaceValue(
I, *V);
4117bool VectorCombine::foldShuffleFromReductions(Instruction &
I) {
4121 switch (
II->getIntrinsicID()) {
4122 case Intrinsic::vector_reduce_add:
4123 case Intrinsic::vector_reduce_mul:
4124 case Intrinsic::vector_reduce_and:
4125 case Intrinsic::vector_reduce_or:
4126 case Intrinsic::vector_reduce_xor:
4127 case Intrinsic::vector_reduce_smin:
4128 case Intrinsic::vector_reduce_smax:
4129 case Intrinsic::vector_reduce_umin:
4130 case Intrinsic::vector_reduce_umax:
4139 std::queue<Value *> Worklist;
4140 SmallPtrSet<Value *, 4> Visited;
4141 ShuffleVectorInst *Shuffle =
nullptr;
4145 while (!Worklist.empty()) {
4146 Value *CV = Worklist.front();
4158 if (CI->isBinaryOp()) {
4159 for (
auto *
Op : CI->operand_values())
4163 if (Shuffle && Shuffle != SV)
4180 for (
auto *V : Visited)
4181 for (
auto *U :
V->users())
4182 if (!Visited.contains(U) && U != &
I)
4185 FixedVectorType *VecType =
4189 FixedVectorType *ShuffleInputType =
4191 if (!ShuffleInputType)
4197 SmallVector<int> ConcatMask;
4199 sort(ConcatMask, [](
int X,
int Y) {
return (
unsigned)
X < (unsigned)
Y; });
4200 bool UsesSecondVec =
4201 any_of(ConcatMask, [&](
int M) {
return M >= (int)NumInputElts; });
4208 ShuffleInputType, CostKind, ConcatMask);
4210 LLVM_DEBUG(
dbgs() <<
"Found a reduction feeding from a shuffle: " << *Shuffle
4212 LLVM_DEBUG(
dbgs() <<
" OldCost: " << OldCost <<
" vs NewCost: " << NewCost
4214 bool MadeChanges =
false;
4215 if (NewCost < OldCost) {
4219 LLVM_DEBUG(
dbgs() <<
"Created new shuffle: " << *NewShuffle <<
"\n");
4220 replaceValue(*Shuffle, *NewShuffle);
4226 MadeChanges |= foldSelectShuffle(*Shuffle,
true);
4247bool VectorCombine::foldShuffleChainsToReduce(Instruction &
I) {
4256 if (FVT->getNumElements() < 2)
4259 std::optional<Instruction::BinaryOps> CommonBinOp;
4260 std::optional<Intrinsic::ID> CommonCallOp;
4265 CommonBinOp = BO->getOpcode();
4267 CommonCallOp = MMI->getIntrinsicID();
4273 FastMathFlags CommonFMF;
4274 bool IsFloatReduction =
false;
4278 auto IsChainNode = [&](
Value *
V) {
4280 return CommonBinOp && BO->getOpcode() == *CommonBinOp;
4282 return CommonCallOp && MMI->getIntrinsicID() == *CommonCallOp;
4290 constexpr unsigned MaxChainNodes = 32;
4291 SmallSetVector<Value *, 16> Nodes;
4292 SmallSetVector<Value *, 4> Sources;
4293 unsigned NumVisited = 0;
4294 auto AddSource = [&](
Value *
V) {
4300 auto Walk = [&](
Value *
V,
auto &&Walk) ->
bool {
4303 if (++NumVisited > MaxChainNodes)
4305 if (!IsChainNode(V))
4306 return AddSource(V);
4311 if (!Walk(
U->getOperand(
I), Walk))
4320 return AddSource(V);
4322 if (!Walk(VecOpEE, Walk) || Nodes.
empty())
4329 for (
Value *V : Nodes) {
4335 if (!IsFloatReduction) {
4337 IsFloatReduction =
true;
4351 DenseMap<Value *, Demand> Demands;
4352 auto DemandOf = [&](
Value *
V) -> Demand & {
4354 Demand &
D = Demands[
V];
4355 if (
D.Lanes.getBitWidth() !=
N)
4359 DemandOf(VecOpEE).Lanes.setBit(0);
4361 Demand DV = Demands.
lookup(V);
4362 if (DV.Lanes.isZero())
4365 ArrayRef<int>
Mask = SVI->getShuffleMask();
4366 Demand &
DS = DemandOf(SVI->getOperand(0));
4367 for (
unsigned I = 0,
E =
Mask.size();
I !=
E; ++
I) {
4369 if (!DV.Lanes[
I] || Mask[
I] < 0 ||
4370 (
unsigned)Mask[
I] >=
DS.Lanes.getBitWidth())
4372 if (
DS.Lanes[Mask[
I]] || DV.Duplicates[
I])
4373 DS.Duplicates.setBit(Mask[
I]);
4374 DS.Lanes.setBit(Mask[
I]);
4378 for (
Value *
Op : {
U->getOperand(0),
U->getOperand(1)}) {
4379 Demand &DOp = DemandOf(
Op);
4381 DOp.Duplicates |= DV.Duplicates | (DOp.Lanes & DV.Lanes);
4382 DOp.Lanes |= DV.Lanes;
4389 auto CoversChain = [&](
Value *
V) {
4390 SmallVector<Value *, 8> Worklist(1, VecOpEE);
4391 SmallPtrSet<Value *, 8> Seen;
4393 while (!Worklist.empty()) {
4396 for (
unsigned I = 0;
I !=
NumOps; ++
I) {
4400 if (!Nodes.contains(
Op))
4402 Worklist.push_back(
Op);
4410 struct ReductionCut {
4414 std::optional<ReductionCut> Cut;
4415 for (
Value *S : Sources) {
4416 auto It = Demands.
find(S);
4417 if (It == Demands.
end() || It->second.Lanes.isZero())
4419 if (!IsIdempotent && !It->second.Duplicates.isZero()) {
4424 Cut = ReductionCut{S, It->second.Lanes};
4431 if (!IsIdempotent && !(Cut->Elts & It->second.Lanes).isZero()) {
4435 Cut->Elts |= It->second.Lanes;
4438 for (
Value *V : Nodes) {
4441 auto It = Demands.
find(V);
4442 if (It == Demands.
end() || !It->second.Lanes.isAllOnes())
4444 if (!IsIdempotent && !It->second.Duplicates.isZero())
4446 if (!CoversChain(V))
4448 Cut = ReductionCut{
V, It->second.Lanes};
4453 if (!Cut || Cut->Elts.popcount() < 2)
4463 for (
Value *V : Nodes)
4467 bool IsPartialReduction = !Cut->Elts.isAllOnes();
4468 FixedVectorType *ReduceVecTy =
4473 SmallVector<int> ExtractMask;
4475 if (IsPartialReduction) {
4476 for (
unsigned I = 0,
E = Cut->Elts.getBitWidth();
I !=
E; ++
I)
4478 ExtractMask.push_back(
I);
4479 unsigned SubIdx = 0, SubLen;
4480 auto SK = Cut->Elts.isShiftedMask(SubIdx, SubLen)
4484 SubIdx, ReduceVecTy);
4487 IntrinsicCostAttributes ICA(
4488 ReducedOp, ReduceVecTy->getElementType(),
4492 IsFloatReduction ? CommonFMF : FastMathFlags());
4495 LLVM_DEBUG(
dbgs() <<
"Found reduction shuffle chain: " <<
I <<
"\n OldCost : "
4496 << OrigCost <<
" vs NewCost: " << NewCost <<
"\n");
4501 if (VecOpEE->
hasOneUse() ? (NewCost > OrigCost) : (NewCost >= OrigCost))
4504 Value *ReduceInput = Cut->Src;
4505 if (IsPartialReduction)
4508 Value *ReducedResult;
4509 if (IsFloatReduction) {
4511 *CommonBinOp, ReduceVecTy->getElementType(),
false,
4514 {Identity, ReduceInput}, CommonFMF);
4519 replaceValue(
I, *ReducedResult);
4528bool VectorCombine::foldCastFromReductions(Instruction &
I) {
4533 bool TruncOnly =
false;
4536 case Intrinsic::vector_reduce_add:
4537 case Intrinsic::vector_reduce_mul:
4540 case Intrinsic::vector_reduce_and:
4541 case Intrinsic::vector_reduce_or:
4542 case Intrinsic::vector_reduce_xor:
4549 Value *ReductionSrc =
I.getOperand(0);
4561 Type *ResultTy =
I.getType();
4564 ReductionOpc, ReductionSrcTy, std::nullopt, CostKind);
4574 if (OldCost <= NewCost || !NewCost.
isValid())
4578 II->getIntrinsicID(), {Src});
4580 replaceValue(
I, *NewCast);
4608bool VectorCombine::foldSignBitReductionCmp(Instruction &
I) {
4610 IntrinsicInst *ReduceOp;
4611 const APInt *CmpVal;
4618 case Intrinsic::vector_reduce_or:
4619 case Intrinsic::vector_reduce_umax:
4620 case Intrinsic::vector_reduce_and:
4621 case Intrinsic::vector_reduce_umin:
4622 case Intrinsic::vector_reduce_add:
4633 unsigned BitWidth = VecTy->getScalarSizeInBits();
4637 unsigned NumElts = VecTy->getNumElements();
4646 case Intrinsic::vector_reduce_or:
4647 case Intrinsic::vector_reduce_umax:
4648 TreeOpcode = Instruction::Or;
4650 case Intrinsic::vector_reduce_and:
4651 case Intrinsic::vector_reduce_umin:
4652 TreeOpcode = Instruction::And;
4654 case Intrinsic::vector_reduce_add:
4655 TreeOpcode = Instruction::Add;
4663 SmallVector<Value *, 8> Worklist;
4664 SmallVector<Value *, 8> Sources;
4666 std::optional<bool> IsAShr;
4667 constexpr unsigned MaxSources = 8;
4672 while (!Worklist.
empty() && Worklist.
size() <= MaxSources &&
4673 Sources.
size() <= MaxSources) {
4682 bool ThisIsAShr = Shr->getOpcode() == Instruction::AShr;
4684 IsAShr = ThisIsAShr;
4685 else if (*IsAShr != ThisIsAShr)
4711 if (Sources.
empty() || Sources.
size() > MaxSources ||
4712 Worklist.
size() > MaxSources || !IsAShr)
4715 unsigned NumSources = Sources.
size();
4719 if (OrigIID == Intrinsic::vector_reduce_add &&
4727 (OrigIID == Intrinsic::vector_reduce_add) ? NumSources * NumElts : 1;
4730 NegativeVal.negate();
4762 TestsNegative =
false;
4763 }
else if (*CmpVal == NegativeVal) {
4764 TestsNegative =
true;
4768 IsEq = Pred == ICmpInst::ICMP_EQ;
4769 }
else if (Pred == ICmpInst::ICMP_SLT && *CmpVal == RangeHigh) {
4771 TestsNegative = (RangeHigh == NegativeVal);
4772 }
else if (Pred == ICmpInst::ICMP_SGT && *CmpVal == RangeHigh - 1) {
4774 TestsNegative = (RangeHigh == NegativeVal);
4775 }
else if (Pred == ICmpInst::ICMP_SGT && *CmpVal == RangeLow) {
4777 TestsNegative = (RangeLow == NegativeVal);
4778 }
else if (Pred == ICmpInst::ICMP_SLT && *CmpVal == RangeLow + 1) {
4780 TestsNegative = (RangeLow == NegativeVal);
4823 enum CheckKind :
unsigned {
4830 auto RequiresOr = [](CheckKind
C) ->
bool {
return C & 0b100; };
4832 auto IsNegativeCheck = [](CheckKind
C) ->
bool {
return C & 0b010; };
4834 auto Invert = [](CheckKind
C) {
return CheckKind(
C ^ 0b011); };
4838 case Intrinsic::vector_reduce_or:
4839 case Intrinsic::vector_reduce_umax:
4840 Base = TestsNegative ? AnyNeg : AllNonNeg;
4842 case Intrinsic::vector_reduce_and:
4843 case Intrinsic::vector_reduce_umin:
4844 Base = TestsNegative ? AllNeg : AnyNonNeg;
4846 case Intrinsic::vector_reduce_add:
4847 Base = TestsNegative ? AllNeg : AllNonNeg;
4858 VecTy, std::nullopt, CostKind);
4861 FastMathFlags(), CostKind);
4862 return ArithCost <= MinMaxCost ? std::make_pair(Arith, ArithCost)
4863 : std::make_pair(MinMax, MinMaxCost);
4867 auto [NewIID, NewCost] = RequiresOr(
Check)
4868 ? PickCheaper(Intrinsic::vector_reduce_or,
4869 Intrinsic::vector_reduce_umax)
4870 : PickCheaper(
Intrinsic::vector_reduce_and,
4874 if (NumSources > 1) {
4875 unsigned CombineOpc =
4876 RequiresOr(
Check) ? Instruction::Or : Instruction::And;
4881 LLVM_DEBUG(
dbgs() <<
"Found sign-bit reduction cmp: " <<
I <<
"\n OldCost: "
4882 << OldCost <<
" vs NewCost: " << NewCost <<
"\n");
4884 if (NewCost > OldCost)
4889 Type *ScalarTy = VecTy->getScalarType();
4892 if (NumSources == 1) {
4903 replaceValue(
I, *NewCmp);
4934bool VectorCombine::foldReductionZeroTest(Instruction &
I) {
4943 if (!
II || !
II->hasOneUse())
4946 auto ReduceID =
II->getIntrinsicID();
4947 if (ReduceID != Intrinsic::vector_reduce_or &&
4948 ReduceID != Intrinsic::vector_reduce_umax)
4951 Value *Vec =
II->getArgOperand(0);
4953 if (!VecTy || !VecTy->getElementType()->isIntegerTy())
4958 ? Intrinsic::vector_reduce_or
4973 LLVM_DEBUG(
dbgs() <<
"Found a reduction zero test: " <<
I <<
"\n OldCost: "
4974 << OldCost <<
" vs NewCost: " << NewCost <<
"\n");
4976 if (!OldCost.
isValid() || !NewCost.
isValid() || NewCost > OldCost)
4982 replaceValue(
I, *NewReduce);
5007bool VectorCombine::foldICmpEqZeroVectorReduce(Instruction &
I) {
5018 switch (
II->getIntrinsicID()) {
5019 case Intrinsic::vector_reduce_add:
5020 case Intrinsic::vector_reduce_or:
5021 case Intrinsic::vector_reduce_umin:
5022 case Intrinsic::vector_reduce_umax:
5023 case Intrinsic::vector_reduce_smin:
5024 case Intrinsic::vector_reduce_smax:
5030 Value *InnerOp =
II->getArgOperand(0);
5073 switch (
II->getIntrinsicID()) {
5074 case Intrinsic::vector_reduce_add: {
5079 unsigned NumElems = XTy->getNumElements();
5085 if (LeadingZerosX <= LostBits || LeadingZerosFX <= LostBits)
5093 case Intrinsic::vector_reduce_smin:
5094 case Intrinsic::vector_reduce_smax:
5104 LLVM_DEBUG(
dbgs() <<
"Found a reduction to 0 comparison with removable op: "
5120 case Intrinsic::vector_reduce_add:
5121 case Intrinsic::vector_reduce_or:
5127 case Intrinsic::vector_reduce_umin:
5128 case Intrinsic::vector_reduce_umax:
5129 case Intrinsic::vector_reduce_smin:
5130 case Intrinsic::vector_reduce_smax:
5142 NewReduceCost + (InnerOp->
hasOneUse() ? 0 : ExtCost);
5144 LLVM_DEBUG(
dbgs() <<
"Found a removable extension before reduction: "
5145 << *InnerOp <<
"\n OldCost: " << OldCost
5146 <<
" vs NewCost: " << NewCost <<
"\n");
5152 if (NewCost > OldCost)
5161 Builder.
CreateICmp(Pred, NewReduce, ConstantInt::getNullValue(Ty));
5162 replaceValue(
I, *NewCmp);
5193bool VectorCombine::foldEquivalentReductionCmp(Instruction &
I) {
5196 const APInt *CmpVal;
5201 if (!
II || !
II->hasOneUse())
5204 const auto IsValidOrUmaxCmp = [&]() {
5213 bool IsPositive = CmpVal->
isAllOnes() && Pred == ICmpInst::ICMP_SGT;
5215 bool IsNegative = (CmpVal->
isZero() || CmpVal->
isOne() || *CmpVal == 2) &&
5216 Pred == ICmpInst::ICMP_SLT;
5217 return IsEquality || IsPositive || IsNegative;
5220 const auto IsValidAndUminCmp = [&]() {
5225 const auto LeadingOnes = CmpVal->
countl_one();
5232 bool IsNegative = CmpVal->
isZero() && Pred == ICmpInst::ICMP_SLT;
5241 ((*CmpVal)[0] || (*CmpVal)[1]) && Pred == ICmpInst::ICMP_SGT;
5242 return IsEquality || IsNegative || IsPositive;
5250 switch (OriginalIID) {
5251 case Intrinsic::vector_reduce_or:
5252 if (!IsValidOrUmaxCmp())
5254 AlternativeIID = Intrinsic::vector_reduce_umax;
5256 case Intrinsic::vector_reduce_umax:
5257 if (!IsValidOrUmaxCmp())
5259 AlternativeIID = Intrinsic::vector_reduce_or;
5261 case Intrinsic::vector_reduce_and:
5262 if (!IsValidAndUminCmp())
5264 AlternativeIID = Intrinsic::vector_reduce_umin;
5266 case Intrinsic::vector_reduce_umin:
5267 if (!IsValidAndUminCmp())
5269 AlternativeIID = Intrinsic::vector_reduce_and;
5282 if (ReductionOpc != Instruction::ICmp)
5286 FastMathFlags(), CostKind);
5293 <<
"\n OrigCost: " << OrigCost
5294 <<
" vs AltCost: " << AltCost <<
"\n");
5296 if (AltCost >= OrigCost)
5300 Type *ScalarTy = VecTy->getScalarType();
5303 Builder.
CreateICmp(Pred, NewReduce, ConstantInt::get(ScalarTy, *CmpVal));
5305 replaceValue(
I, *NewCmp);
5319 unsigned Depth = 0) {
5320 constexpr unsigned MaxLocalDepth = 2;
5321 if (
Depth > MaxLocalDepth)
5324 auto NumSignBits = [&](
const Value *
X) {
5327 if (NumSignBits(V) == V->getType()->getScalarSizeInBits())
5332 return NumSignBits(
A) >= 2 && NumSignBits(
B) >= 2 &&
5343bool VectorCombine::foldReduceAddCmpZero(Instruction &
I) {
5353 if (!VecTy || VecTy->getNumElements() < 2)
5359 if (!IsNonNegative && !IsNonPositive)
5364 unsigned NumElts = VecTy->getNumElements();
5366 if (
Log2_32(NumElts) >= NumSignBits)
5369 ICmpInst::Predicate NewPred;
5371 case ICmpInst::ICMP_EQ:
5372 case ICmpInst::ICMP_ULE:
5373 case ICmpInst::ICMP_SLE:
5374 case ICmpInst::ICMP_SGE:
5375 NewPred = ICmpInst::ICMP_EQ;
5377 case ICmpInst::ICMP_NE:
5378 case ICmpInst::ICMP_UGT:
5379 case ICmpInst::ICMP_SGT:
5380 case ICmpInst::ICMP_SLT:
5381 NewPred = ICmpInst::ICMP_NE;
5391 if (!IsNonNegative &&
5392 (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLE))
5394 if (!IsNonPositive &&
5395 (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGE))
5397 if ((Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLE ||
5398 Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGE) &&
5399 Log2_32(NumElts) >= NumSignBits - 1)
5403 Instruction::Add, VecTy, std::nullopt, CostKind);
5405 Instruction::Or, VecTy, std::nullopt, CostKind);
5407 Intrinsic::umax, VecTy, FastMathFlags(), CostKind);
5410 bool UseOr = OrCost.
isValid() && (!UmaxCost.
isValid() || OrCost <= UmaxCost);
5412 if (AltCost > OrigCost)
5418 Intrinsic::vector_reduce_umax, {VecTy}, {Vec});
5420 NewPred, NewReduce, ConstantInt::getNullValue(VecTy->getScalarType()));
5421 replaceValue(
I, *NewCmp);
5430 constexpr unsigned MaxVisited = 32;
5433 bool FoundReduction =
false;
5436 while (!WorkList.
empty()) {
5438 for (
User *U :
I->users()) {
5440 if (!UI || !Visited.
insert(UI).second)
5442 if (Visited.
size() > MaxVisited)
5448 switch (
II->getIntrinsicID()) {
5449 case Intrinsic::vector_reduce_add:
5450 case Intrinsic::vector_reduce_mul:
5451 case Intrinsic::vector_reduce_and:
5452 case Intrinsic::vector_reduce_or:
5453 case Intrinsic::vector_reduce_xor:
5454 case Intrinsic::vector_reduce_smin:
5455 case Intrinsic::vector_reduce_smax:
5456 case Intrinsic::vector_reduce_umin:
5457 case Intrinsic::vector_reduce_umax:
5458 FoundReduction =
true;
5471 return FoundReduction;
5484bool VectorCombine::foldSelectShuffle(Instruction &
I,
bool FromReduction) {
5489 if (!Op0 || !Op1 || Op0 == Op1 || !Op0->isBinaryOp() || !Op1->isBinaryOp() ||
5490 VT != Op0->getType())
5497 SmallPtrSet<Instruction *, 4> InputShuffles({SVI0A, SVI0B, SVI1A, SVI1B});
5499 if (!
I ||
I->getOperand(0)->getType() != VT)
5501 return any_of(
I->users(), [&](User *U) {
5502 return U != Op0 && U != Op1 &&
5503 !(isa<ShuffleVectorInst>(U) &&
5504 (InputShuffles.contains(cast<Instruction>(U)) ||
5505 isInstructionTriviallyDead(cast<Instruction>(U))));
5508 if (checkSVNonOpUses(SVI0A) || checkSVNonOpUses(SVI0B) ||
5509 checkSVNonOpUses(SVI1A) || checkSVNonOpUses(SVI1B))
5517 for (
auto *U :
I->users()) {
5519 if (!SV ||
SV->getType() != VT)
5521 if ((
SV->getOperand(0) != Op0 &&
SV->getOperand(0) != Op1) ||
5522 (
SV->getOperand(1) != Op0 &&
SV->getOperand(1) != Op1))
5529 if (!collectShuffles(Op0) || !collectShuffles(Op1))
5533 if (FromReduction && Shuffles.
size() > 1)
5538 if (!FromReduction) {
5539 for (
size_t Idx = 0,
E = Shuffles.
size(); Idx !=
E; ++Idx) {
5540 for (
auto *U : Shuffles[Idx]->
users()) {
5555 int MaxV1Elt = 0, MaxV2Elt = 0;
5556 unsigned NumElts = VT->getNumElements();
5557 for (ShuffleVectorInst *SVN : Shuffles) {
5558 SmallVector<int>
Mask;
5559 SVN->getShuffleMask(Mask);
5563 Value *SVOp0 = SVN->getOperand(0);
5564 Value *SVOp1 = SVN->getOperand(1);
5569 for (
int &Elem : Mask) {
5575 if (SVOp0 == Op1 && SVOp1 == Op0) {
5579 if (SVOp0 != Op0 || SVOp1 != Op1)
5585 SmallVector<int> ReconstructMask;
5586 for (
unsigned I = 0;
I <
Mask.size();
I++) {
5589 }
else if (Mask[
I] <
static_cast<int>(NumElts)) {
5590 MaxV1Elt = std::max(MaxV1Elt, Mask[
I]);
5591 auto It =
find_if(
V1, [&](
const std::pair<int, int> &
A) {
5592 return Mask[
I] ==
A.first;
5598 V1.emplace_back(Mask[
I],
V1.size());
5601 MaxV2Elt = std::max<int>(MaxV2Elt, Mask[
I] - NumElts);
5602 auto It =
find_if(V2, [&](
const std::pair<int, int> &
A) {
5603 return Mask[
I] -
static_cast<int>(NumElts) ==
A.first;
5617 sort(ReconstructMask);
5618 OrigReconstructMasks.
push_back(std::move(ReconstructMask));
5625 if (
V1.empty() || V2.
empty() ||
5626 (MaxV1Elt ==
static_cast<int>(
V1.size()) - 1 &&
5627 MaxV2Elt ==
static_cast<int>(V2.
size()) - 1))
5639 if (InputShuffles.contains(SSV))
5641 return SV->getMaskValue(M);
5649 std::pair<int, int>
Y) {
5650 int MXA = GetBaseMaskValue(
A,
X.first);
5651 int MYA = GetBaseMaskValue(
A,
Y.first);
5655 return SortBase(SVI0A,
A,
B);
5657 stable_sort(V2, [&](std::pair<int, int>
A, std::pair<int, int>
B) {
5658 return SortBase(SVI1A,
A,
B);
5663 for (
const auto &Mask : OrigReconstructMasks) {
5664 SmallVector<int> ReconstructMask;
5665 for (
int M : Mask) {
5667 auto It =
find_if(V, [M](
auto A) {
return A.second ==
M; });
5668 assert(It !=
V.end() &&
"Expected all entries in Mask");
5669 return std::distance(
V.begin(), It);
5673 else if (M <
static_cast<int>(NumElts)) {
5676 ReconstructMask.
push_back(NumElts + FindIndex(V2, M));
5679 ReconstructMasks.
push_back(std::move(ReconstructMask));
5684 SmallVector<int> V1A, V1B, V2A, V2B;
5685 for (
unsigned I = 0;
I <
V1.size();
I++) {
5689 for (
unsigned I = 0;
I < V2.
size();
I++) {
5690 V2A.
push_back(GetBaseMaskValue(SVI1A, V2[
I].first));
5691 V2B.
push_back(GetBaseMaskValue(SVI1B, V2[
I].first));
5693 while (V1A.
size() < NumElts) {
5697 while (V2A.
size() < NumElts) {
5709 VT, VT, CostKind,
SV->getShuffleMask());
5716 unsigned ElementSize = VT->getElementType()->getPrimitiveSizeInBits();
5717 unsigned MaxVectorSize =
5719 unsigned MaxElementsInVector = MaxVectorSize / ElementSize;
5720 if (MaxElementsInVector == 0)
5729 std::set<SmallVector<int, 4>> UniqueShuffles;
5734 unsigned NumFullVectors =
Mask.size() / MaxElementsInVector;
5735 if (NumFullVectors < 2)
5736 return C + ShuffleCost;
5737 SmallVector<int, 4> SubShuffle(MaxElementsInVector);
5738 unsigned NumUniqueGroups = 0;
5739 unsigned NumGroups =
Mask.size() / MaxElementsInVector;
5742 for (
unsigned I = 0;
I < NumFullVectors; ++
I) {
5743 for (
unsigned J = 0; J < MaxElementsInVector; ++J)
5744 SubShuffle[J] = Mask[MaxElementsInVector *
I + J];
5745 if (UniqueShuffles.insert(SubShuffle).second)
5746 NumUniqueGroups += 1;
5748 return C + ShuffleCost * NumUniqueGroups / NumGroups;
5754 SmallVector<int, 16>
Mask;
5755 SV->getShuffleMask(Mask);
5756 return AddShuffleMaskAdjustedCost(
C, Mask);
5759 auto AllShufflesHaveSameOperands =
5760 [](SmallPtrSetImpl<Instruction *> &InputShuffles) {
5761 if (InputShuffles.size() < 2)
5763 ShuffleVectorInst *FirstSV =
5770 std::next(InputShuffles.begin()), InputShuffles.end(),
5771 [&](Instruction *
I) {
5772 ShuffleVectorInst *SV = dyn_cast<ShuffleVectorInst>(I);
5773 return SV && SV->getOperand(0) == In0 && SV->getOperand(1) == In1;
5782 CostBefore += std::accumulate(Shuffles.begin(), Shuffles.end(),
5784 if (AllShufflesHaveSameOperands(InputShuffles)) {
5785 UniqueShuffles.clear();
5786 CostBefore += std::accumulate(InputShuffles.begin(), InputShuffles.end(),
5789 CostBefore += std::accumulate(InputShuffles.begin(), InputShuffles.end(),
5795 FixedVectorType *Op0SmallVT =
5797 FixedVectorType *Op1SmallVT =
5802 UniqueShuffles.clear();
5803 CostAfter += std::accumulate(ReconstructMasks.begin(), ReconstructMasks.end(),
5805 std::set<SmallVector<int>> OutputShuffleMasks({V1A, V1B, V2A, V2B});
5807 std::accumulate(OutputShuffleMasks.begin(), OutputShuffleMasks.end(),
5810 LLVM_DEBUG(
dbgs() <<
"Found a binop select shuffle pattern: " <<
I <<
"\n");
5812 <<
" vs CostAfter: " << CostAfter <<
"\n");
5813 if (CostBefore < CostAfter ||
5824 if (InputShuffles.contains(SSV))
5826 return SV->getOperand(
Op);
5830 GetShuffleOperand(SVI0A, 1), V1A);
5833 GetShuffleOperand(SVI0B, 1), V1B);
5836 GetShuffleOperand(SVI1A, 1), V2A);
5839 GetShuffleOperand(SVI1B, 1), V2B);
5844 I->copyIRFlags(Op0,
true);
5849 I->copyIRFlags(Op1,
true);
5851 for (
int S = 0,
E = ReconstructMasks.size(); S !=
E; S++) {
5854 replaceValue(*Shuffles[S], *NSV,
false);
5866bool VectorCombine::shrinkType(Instruction &
I) {
5867 Value *ZExted, *OtherOperand;
5873 Value *ZExtOperand =
I.getOperand(
I.getOperand(0) == OtherOperand ? 1 : 0);
5877 unsigned BW = SmallTy->getElementType()->getPrimitiveSizeInBits();
5879 if (
I.getOpcode() == Instruction::LShr) {
5896 Instruction::ZExt, BigTy, SmallTy,
5897 TargetTransformInfo::CastContextHint::None, CostKind);
5902 for (User *U : ZExtOperand->
users()) {
5909 ShrinkCost += ZExtCost;
5924 ShrinkCost += ZExtCost;
5931 Instruction::Trunc, SmallTy, BigTy,
5932 TargetTransformInfo::CastContextHint::None, CostKind);
5937 if (ShrinkCost > CurrentCost)
5941 Value *Op0 = ZExted;
5944 if (
I.getOperand(0) == OtherOperand)
5949 NewBinOpI->copyIRFlags(&
I);
5950 NewBinOpI->copyMetadata(
I);
5953 replaceValue(
I, *NewZExtr);
5959bool VectorCombine::foldInsExtVectorToShuffle(Instruction &
I) {
5960 Value *DstVec, *SrcVec;
5971 if (!DstVecTy || !SrcVecTy ||
5977 if (InsIdx >= NumDstElts || ExtIdx >= NumSrcElts || NumDstElts == 1)
5984 bool NeedExpOrNarrow = NumSrcElts != NumDstElts;
5986 if (NeedDstSrcSwap) {
5988 Mask[InsIdx] = ExtIdx % NumDstElts;
5992 std::iota(
Mask.begin(),
Mask.end(), 0);
5993 Mask[InsIdx] = (ExtIdx % NumDstElts) + NumDstElts;
6006 SmallVector<int> ExtToVecMask;
6007 if (!NeedExpOrNarrow) {
6012 nullptr, {DstVec, SrcVec});
6018 ExtToVecMask[ExtIdx % NumDstElts] = ExtIdx;
6021 DstVecTy, SrcVecTy, CostKind, ExtToVecMask);
6025 if (!Ext->hasOneUse())
6028 LLVM_DEBUG(
dbgs() <<
"Found a insert/extract shuffle-like pair: " <<
I
6029 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
6032 if (OldCost < NewCost)
6035 if (NeedExpOrNarrow) {
6036 if (!NeedDstSrcSwap)
6049 replaceValue(
I, *Shuf);
6058bool VectorCombine::foldInsertScalarPartsToShuffle(Instruction &
I) {
6067 Type *EltTy = VecTy->getElementType();
6069 !
DL->typeSizeEqualsStoreSize(EltTy))
6072 unsigned NumElts = VecTy->getNumElements();
6074 Value *Src =
nullptr;
6075 unsigned NumSrcElts = 0;
6081 if (Ins != &
I && !Ins->hasOneUse())
6086 Vec = Ins->getOperand(0);
6088 if (DemandedElts[Idx])
6090 DemandedElts.
setBit(Idx);
6094 Value *Elt = Ins->getOperand(1);
6101 Value *Shift =
nullptr;
6109 unsigned SrcBits =
X->getType()->getIntegerBitWidth();
6110 if (SrcBits % EltBits)
6113 NumSrcElts = SrcBits / EltBits;
6114 }
else if (
X != Src) {
6118 if (ShAmt % EltBits || Part >= NumSrcElts)
6120 Mask[
Idx] =
DL->isBigEndian() ? NumSrcElts - 1 - Part : Part;
6123 for (
Value *V : {Elt == Trunc ? nullptr : Elt, Trunc, Shift}) {
6126 if (!
V->hasOneUse())
6148 bool IsIdentity = NumSrcElts == NumElts &&
6154 LLVM_DEBUG(
dbgs() <<
"Found an insertelement chain of scalar parts: " <<
I
6155 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
6157 if (!OldCost.
isValid() || !NewCost.
isValid() || NewCost >= OldCost)
6162 replaceValue(
I, *Shuf);
6169 return CB->arg_size();
6181 if (
II->hasOperandBundles() ||
6194 OperandTy->getElementCount() != ResultTy->getElementCount())
6203 auto GetSplatOrScalar = [](
Value *V) {
6207 Value *CommonValue = GetSplatOrScalar(
Values.front());
6211 if (GetSplatOrScalar(V) != CommonValue)
6220 for (
const auto &[Index, Member] :
enumerate(Members)) {
6222 if (!Extract || Extract->getNumIndices() != 1 ||
6223 *Extract->idx_begin() != Index)
6231 unsigned Factor = Members.
size();
6242 unsigned OperandIndex) {
6244 for (
Value *Member : Members)
6253 unsigned &NumScanned) {
6254 unsigned Factor = Members.
size();
6257 if (NumScanned + Factor > Opts.vector_combine_max_scan_instrs)
6259 NumScanned += Factor;
6263 !FirstInst->getSingleUndroppableUse())
6268 if (!Inst || !Inst->getSingleUndroppableUse() ||
6289 return Builder.CreateNAryOp(NarrowInst->
getOpcode(), NewOperands);
6291 return Builder.CreateCast(Cast->getOpcode(), NewOperands[0], WideResultTy);
6293 return Builder.CreateCmp(Cmp->getPredicate(), NewOperands[0],
6296 return Builder.CreateSelect(
6297 NewOperands[0], NewOperands[1], NewOperands[2],
"",
6300 return Builder.CreateFreeze(NewOperands[0]);
6302 return Builder.CreateIntrinsic(WideResultTy,
II->getIntrinsicID(),
6313 "deinterleave source must have the interleaved element count");
6320 NewOperands.
reserve(NumOperands);
6321 for (
unsigned Op = 0;
Op != NumOperands; ++
Op) {
6323 Value *NewOperand =
nullptr;
6326 Builder.SetCurrentDebugLocation(NarrowInst->getDebugLoc());
6327 NewOperand = Builder.CreateVectorSplat(WideEC, NewOperand);
6337 Builder.SetCurrentDebugLocation(NarrowInst->getDebugLoc());
6338 auto *WideResultTy =
6385bool VectorCombine::foldInterleaveOfDeinterleaveChains(Instruction &
I) {
6391 if (!Factor || Interleave->hasOperandBundles())
6394 SmallVector<Value *, 8> RootMembers(Interleave->args());
6395 unsigned NumScanned = 0;
6403 replaceValue(*Interleave, *WideValue);
6411bool VectorCombine::foldInterleaveIntrinsics(Instruction &
I) {
6412 if (foldInterleaveOfDeinterleaveChains(
I))
6415 const APInt *SplatVal0, *SplatVal1;
6425 auto *ExtVTy = VectorType::getExtendedElementVectorType(VTy);
6426 unsigned Width = VTy->getElementType()->getIntegerBitWidth();
6435 LLVM_DEBUG(
dbgs() <<
"VC: The cost to cast from " << *ExtVTy <<
" to "
6436 << *
I.getType() <<
" is too high.\n");
6440 APInt NewSplatVal = SplatVal1->
zext(Width * 2);
6441 NewSplatVal <<= Width;
6442 NewSplatVal |= SplatVal0->
zext(Width * 2);
6444 ExtVTy->getElementCount(), ConstantInt::get(
F.getContext(), NewSplatVal));
6479bool VectorCombine::foldDeinterleaveIntrinsics(Instruction &
I) {
6481 if (
DL->isBigEndian())
6484 using namespace PatternMatch;
6485 Value *DeinterleavedVal;
6496 unsigned HalfElementWidth = ElementWidth / 2;
6500 std::array<ExtractValueInst *, 2> OrigFields{};
6501 for (User *Usr :
I.users()) {
6504 if (!
E ||
E->getNumIndices() != 1)
6506 unsigned Idx = *
E->idx_begin();
6508 if (Idx >= 2 || OrigFields[Idx] || !
E->hasNUses(2))
6510 OrigFields[
Idx] =
E;
6514 SmallVector<Instruction *, 2> MergeInsts;
6515 for (
auto *FieldUsr : OrigFields[0]->
users()) {
6523 auto MatchMerge = [&](void) ->
bool {
6526 return match(MergeInsts[0],
6530 match(MergeInsts[1],
6535 if (!MatchMerge()) {
6536 std::swap(MergeInsts[0], MergeInsts[1]);
6551 auto *NewFieldTy = VecTy->getWithNewBitWidth(HalfElementWidth);
6561 if (OldCost <= NewCost || !NewCost.
isValid()) {
6563 dbgs() <<
"VC: New deinterleave2 sequence cost (" << NewCost <<
")"
6564 <<
" is higher than that of the old one (" << OldCost <<
")\n");
6572 Intrinsic::vector_deinterleave2, {NewVecTy}, {NewVecCast});
6573 for (
auto [Idx, MergeInst] :
enumerate(MergeInsts)) {
6575 NewField = Builder.
CreateBitCast(NewField, MergeInst->getType());
6576 replaceValue(*MergeInst, *NewField);
6582bool VectorCombine::foldBitcastOfVPLoad(Instruction &
I) {
6583 const DataLayout &
DL =
I.getDataLayout();
6598 DL.getValueOrABITypeAlignment(
II->getPointerAlignment(), OrigVecTy);
6599 ElementCount OrigVecCnt = OrigVecTy->getElementCount();
6601 ElementCount NewVecCnt = NewVecTy->getElementCount();
6613 II->getMemoryPointerParam(),
false,
6619 {Intrinsic::vp_load, NewVecTy,
II->getMemoryPointerParam(),
false,
6623 <<
" NewCost=" << NewCost <<
"\n");
6624 if (NewCost > OldCost || !NewCost.
isValid())
6632 NewVecTy, Intrinsic::vp_load,
6633 {
II->getMemoryPointerParam(), NewMask, NewEVL});
6636 0, AttrBuilder(
II->getContext()).addAlignmentAttr(OrigAlign));
6637 replaceValue(*Cast, *NewVP);
6647bool VectorCombine::foldBitOrderReverseAndSwap(Instruction &
I) {
6651 Type *Ty =
X->getType();
6652 Type *VecTy =
I.getOperand(0)->getType();
6666 if (CanUseBswap || CanUseFshl) {
6677 IntrinsicCostAttributes ICABSwap(Intrinsic::bswap, Ty, {Ty});
6678 IntrinsicCostAttributes ICABFshl(Intrinsic::fshl, Ty, {
X,
X, HalfBW},
6680 IntrinsicCostAttributes ICABRev(Intrinsic::bitreverse, Ty, {Ty});
6685 if (!InnerCall->hasOneUse())
6688 else if (!InnerBitCast->hasOneUse())
6691 <<
"\n OldCost: " << OldCost
6692 <<
" vs NewCost: " << NewCost <<
"\n");
6693 if (NewCost.isValid() && NewCost < OldCost) {
6700 replaceValue(
I, *BRev);
6709 Type *Ty =
I.getType();
6711 TypeSize ElementSize =
DL->getTypeStoreSize(Ty);
6714 Type *NewVecTy = VectorType::get(I8Ty, NewVecCnt);
6727 IntrinsicCostAttributes ICANew(Intrinsic::bitreverse, NewVecTy, {NewVecTy});
6730 InstructionCost NewCost = CastToVecCost + NewIntrinsicCost + CastToOrigCost;
6731 if (!InnerII->hasOneUse())
6734 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
6736 if (!NewCost.
isValid() || NewCost >= OldCost)
6744 replaceValue(
I, *CastToOrig);
6754 unsigned RawNumElements = MaxIdx + 1u;
6758 return RawNumElements;
6762 return RawNumElements;
6767 return RawNumElements;
6772 if (ElemsPerReg == 0 || RawNumElements <= ElemsPerReg)
6773 return RawNumElements;
6775 return alignTo(RawNumElements, ElemsPerReg);
6779bool VectorCombine::shrinkLoadForShuffles(Instruction &
I) {
6781 if (!OldLoad || !OldLoad->isSimple())
6788 unsigned const OldNumElements = OldLoadTy->getNumElements();
6794 using IndexRange = std::pair<int, int>;
6795 auto GetIndexRangeInShuffles = [&]() -> std::optional<IndexRange> {
6796 IndexRange OutputRange = IndexRange(OldNumElements, -1);
6797 for (llvm::Use &Use :
I.uses()) {
6799 User *Shuffle =
Use.getUser();
6804 return std::nullopt;
6811 for (
int Index : Mask) {
6812 if (Index >= 0 && Index <
static_cast<int>(OldNumElements)) {
6813 OutputRange.first = std::min(Index, OutputRange.first);
6814 OutputRange.second = std::max(Index, OutputRange.second);
6819 if (OutputRange.second < OutputRange.first)
6820 return std::nullopt;
6826 if (std::optional<IndexRange> Indices = GetIndexRangeInShuffles()) {
6827 unsigned const NewNumElements =
6832 if (NewNumElements < OldNumElements) {
6837 Type *ElemTy = OldLoadTy->getElementType();
6839 Value *PtrOp = OldLoad->getPointerOperand();
6842 Instruction::Load, OldLoad->getType(), OldLoad->getAlign(),
6843 OldLoad->getPointerAddressSpace(), CostKind);
6846 OldLoad->getPointerAddressSpace(), CostKind);
6848 using UseEntry = std::pair<ShuffleVectorInst *, std::vector<int>>;
6850 unsigned const MaxIndex = NewNumElements * 2u;
6852 for (llvm::Use &Use :
I.uses()) {
6859 ArrayRef<int> OldMask = Shuffle->getShuffleMask();
6865 for (
int Index : OldMask) {
6866 if (Index >=
static_cast<int>(MaxIndex))
6873 OldLoadTy, CostKind, OldMask);
6876 NewLoadTy, CostKind, OldMask);
6880 dbgs() <<
"Found a load used only by shufflevector instructions: "
6881 <<
I <<
"\n OldCost: " << OldCost
6882 <<
" vs NewCost: " << NewCost <<
"\n");
6884 if (OldCost < NewCost || !NewCost.
isValid())
6890 NewLoad->copyMetadata(
I);
6893 for (UseEntry &Use : NewUses) {
6894 ShuffleVectorInst *Shuffle =
Use.first;
6895 std::vector<int> &NewMask =
Use.second;
6902 replaceValue(*Shuffle, *NewShuffle,
false);
6934bool VectorCombine::foldShuffleOfAdjacentLoads(Instruction &
I) {
6940 if (!Load0 || !Load1 || Load0 == Load1 || !Load0->isSimple() ||
6950 if (Load0->getParent() != Load1->getParent())
6953 if (Load0->getPointerAddressSpace() != Load1->getPointerAddressSpace())
6958 if (
DL->getTypeSizeInBits(LoadTy) != 8 *
DL->getTypeStoreSize(LoadTy))
6961 const unsigned NumElts = LoadTy->getNumElements();
6963 if (NumElts > INT_MAX / 2)
6969 unsigned AS = Load0->getPointerAddressSpace();
6970 unsigned IdxWidth =
DL->getIndexSizeInBits(AS);
6971 APInt Offset0(IdxWidth, 0), Offset1(IdxWidth, 0);
6972 const Value *Base0 =
6973 Load0->getPointerOperand()->stripAndAccumulateConstantOffsets(
6974 *
DL, Offset0,
true);
6975 const Value *Base1 =
6976 Load1->getPointerOperand()->stripAndAccumulateConstantOffsets(
6977 *
DL, Offset1,
true);
6982 int64_t LoadSize =
DL->getTypeStoreSize(LoadTy).getFixedValue();
6983 std::optional<int64_t> Dist = (Offset1 - Offset0).trySExtValue();
6984 LoadInst *LowLoad, *HighLoad;
6985 if (Dist == LoadSize) {
6988 }
else if (Dist == -LoadSize) {
6997 SmallPtrSet<ShuffleVectorInst *, 4> Shuffles;
7001 if (auto *SVI = dyn_cast<ShuffleVectorInst>(U)) {
7002 Shuffles.insert(SVI);
7011 LoadInst *FirstLoad = LowLoad, *LastLoad = HighLoad;
7016 LastLoad->getIterator(), FirstLoc, AA))
7027 auto RemapMask = [&](ShuffleVectorInst *
SV, SmallVectorImpl<int> &NewMask) {
7028 Value *SVOp0 =
SV->getOperand(0);
7029 assert(((SVOp0 == LowLoad &&
SV->getOperand(1) == HighLoad) ||
7030 (SVOp0 == HighLoad &&
SV->getOperand(1) == LowLoad)) &&
7031 "Shuffle operands must be exactly {LowLoad, HighLoad} or {HighLoad, "
7033 SV->getShuffleMask(NewMask);
7034 if (SVOp0 == HighLoad)
7049 for (ShuffleVectorInst *SV : Shuffles) {
7051 CostKind,
SV->getShuffleMask());
7053 RemapMask(SV, NewMask);
7061 WideTy, CostKind, NewMask);
7064 LLVM_DEBUG(
dbgs() <<
"Found adjacent loads feeding shuffles: " << *LowLoad
7065 <<
", " << *HighLoad <<
"\n OldCost: " << OldCost
7066 <<
" vs NewCost: " << NewCost <<
"\n");
7068 if (!NewCost.
isValid() || NewCost > OldCost)
7073 LoadInst *InsertPt = LastLoad;
7090 for (ShuffleVectorInst *SV : Shuffles) {
7092 RemapMask(SV, NewMask);
7099 replaceValue(*SV, *NewShuf,
false);
7108bool VectorCombine::shrinkPhiOfShuffles(Instruction &
I) {
7110 if (!Phi ||
Phi->getNumIncomingValues() != 2u)
7114 ArrayRef<int> Mask0;
7115 ArrayRef<int> Mask1;
7128 auto const InputNumElements = InputVT->getNumElements();
7130 if (InputNumElements >= ResultVT->getNumElements())
7135 SmallVector<int, 16> NewMask;
7138 for (
auto [
M0,
M1] :
zip(Mask0, Mask1)) {
7139 if (
M0 >= 0 &&
M1 >= 0)
7141 else if (
M0 == -1 &&
M1 == -1)
7154 int MaskOffset = NewMask[0
u];
7155 unsigned Index = (InputNumElements + MaskOffset) % InputNumElements;
7158 for (
unsigned I = 0u;
I < InputNumElements; ++
I) {
7172 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
7175 if (NewCost > OldCost)
7186 auto *NewPhi = Builder.
CreatePHI(NewShuf0->getType(), 2u);
7188 NewPhi->addIncoming(
Op,
Phi->getIncomingBlock(1u));
7194 replaceValue(*Phi, *NewShuf1);
7200bool VectorCombine::run() {
7201 if (Opts.disable_vector_combine)
7214 auto Opcode =
I.getOpcode();
7222 if (IsFixedVectorType) {
7224 case Instruction::InsertElement:
7225 if (vectorizeLoadInsert(
I))
7228 case Instruction::ShuffleVector:
7229 if (widenSubvectorLoad(
I))
7240 if (scalarizeOpOrCmp(
I))
7242 if (scalarizeLoad(
I))
7244 if (scalarizeExtExtract(
I))
7246 if (foldInterleaveIntrinsics(
I))
7248 if (foldBitcastOfVPLoad(
I))
7252 if (foldDeinterleaveIntrinsics(
I))
7255 if (Opcode == Instruction::Store)
7256 if (foldInsertElementsToStores(
I))
7260 if (TryEarlyFoldsOnly)
7263 if (Opcode == Instruction::Call)
7264 if (foldBitOrderReverseAndSwap(
I))
7266 if (Opcode == Instruction::BitCast)
7267 if (foldBitOrderReverseAndSwap(
I))
7274 if (IsFixedVectorType) {
7276 case Instruction::InsertElement:
7277 if (foldInsExtFNeg(
I))
7279 if (foldInsExtBinop(
I))
7281 if (foldInsExtVectorToShuffle(
I))
7283 if (foldInsertScalarPartsToShuffle(
I))
7286 case Instruction::ShuffleVector:
7287 if (foldPermuteOfBinops(
I))
7289 if (foldShuffleOfBinops(
I))
7291 if (foldShuffleOfSelects(
I))
7293 if (foldShuffleOfCastops(
I))
7295 if (foldShuffleOfShuffles(
I))
7297 if (foldShuffleOfAdjacentLoads(
I))
7299 if (foldPermuteOfIntrinsic(
I))
7301 if (foldShufflesOfLengthChangingShuffles(
I))
7303 if (foldShuffleOfIntrinsics(
I))
7305 if (foldSelectShuffle(
I))
7307 if (foldShuffleToIdentity(
I))
7310 case Instruction::Load:
7311 if (shrinkLoadForShuffles(
I))
7314 case Instruction::BitCast:
7315 if (foldBitcastShuffle(
I))
7317 if (foldSelectsFromBitcast(
I))
7320 case Instruction::And:
7321 case Instruction::Or:
7322 case Instruction::Xor:
7323 if (foldBitOpOfCastops(
I))
7325 if (foldBitOpOfCastConstant(
I))
7328 case Instruction::PHI:
7329 if (shrinkPhiOfShuffles(
I))
7339 case Instruction::Call:
7340 if (foldShuffleFromReductions(
I))
7342 if (foldCastFromReductions(
I))
7345 case Instruction::ExtractElement:
7346 if (foldShuffleChainsToReduce(
I))
7349 case Instruction::ICmp:
7350 if (foldSignBitReductionCmp(
I))
7352 if (foldICmpEqZeroVectorReduce(
I))
7354 if (foldReductionZeroTest(
I))
7356 if (foldEquivalentReductionCmp(
I))
7358 if (foldReduceAddCmpZero(
I))
7361 case Instruction::FCmp:
7362 if (foldExtractExtract(
I))
7365 case Instruction::Or:
7366 if (foldConcatOfBoolMasks(
I))
7371 if (foldExtractExtract(
I))
7373 if (foldExtractedCmps(
I))
7375 if (foldBinopOfReductions(
I))
7384 bool MadeChange =
false;
7385 for (BasicBlock &BB :
F) {
7397 MadeChange |= FoldInst(*
I);
7404 while (!Worklist.isEmpty()) {
7407 while (Instruction *
I = Worklist.popDeferred()) {
7425 MadeChange |= FoldInst(*
I);
7441 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.
const SDValue & getOperand(unsigned Num) const
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