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");
64 cl::desc(
"Disable all vector combine transforms"));
68 cl::desc(
"Disable binop extract to shuffle transforms"));
72 cl::desc(
"Max number of instructions to scan for vector combining."));
74static const unsigned InvalidIndex = std::numeric_limits<unsigned>::max();
82 bool TryEarlyFoldsOnly)
85 SQ(*
DL, nullptr, &DT, &AC),
86 TryEarlyFoldsOnly(TryEarlyFoldsOnly) {}
93 const TargetTransformInfo &TTI;
94 const DominatorTree &DT;
98 const SimplifyQuery SQ;
102 bool TryEarlyFoldsOnly;
104 InstructionWorklist Worklist;
113 bool vectorizeLoadInsert(Instruction &
I);
114 bool widenSubvectorLoad(Instruction &
I);
115 ExtractElementInst *getShuffleExtract(ExtractElementInst *Ext0,
116 ExtractElementInst *Ext1,
117 unsigned PreferredExtractIndex)
const;
118 bool isExtractExtractCheap(ExtractElementInst *Ext0, ExtractElementInst *Ext1,
119 const Instruction &
I,
120 ExtractElementInst *&ConvertToShuffle,
121 unsigned PreferredExtractIndex);
124 bool foldExtractExtract(Instruction &
I);
125 bool foldInsExtFNeg(Instruction &
I);
126 bool foldInsExtBinop(Instruction &
I);
127 bool foldInsExtVectorToShuffle(Instruction &
I);
128 bool foldInsertScalarPartsToShuffle(Instruction &
I);
129 bool foldBitOpOfCastops(Instruction &
I);
130 bool foldBitOpOfCastConstant(Instruction &
I);
131 bool foldBitcastShuffle(Instruction &
I);
132 bool scalarizeOpOrCmp(Instruction &
I);
133 bool foldExtractedCmps(Instruction &
I);
134 bool foldSelectsFromBitcast(Instruction &
I);
135 bool foldBinopOfReductions(Instruction &
I);
136 bool foldInsertElementsToStores(Instruction &
I);
137 bool scalarizeLoad(Instruction &
I);
138 bool scalarizeLoadExtract(LoadInst *LI, VectorType *VecTy,
Value *Ptr);
139 bool scalarizeLoadBitcast(LoadInst *LI, VectorType *VecTy,
Value *Ptr);
140 bool scalarizeExtExtract(Instruction &
I);
141 bool foldConcatOfBoolMasks(Instruction &
I);
142 bool foldPermuteOfBinops(Instruction &
I);
143 bool foldShuffleOfBinops(Instruction &
I);
144 bool foldShuffleOfSelects(Instruction &
I);
145 bool foldShuffleOfCastops(Instruction &
I);
146 bool foldShuffleOfShuffles(Instruction &
I);
147 bool foldPermuteOfIntrinsic(Instruction &
I);
148 bool foldShufflesOfLengthChangingShuffles(Instruction &
I);
149 bool foldShuffleOfIntrinsics(Instruction &
I);
150 bool foldShuffleToIdentity(Instruction &
I);
151 bool foldShuffleFromReductions(Instruction &
I);
152 bool foldShuffleChainsToReduce(Instruction &
I);
153 bool foldCastFromReductions(Instruction &
I);
154 bool foldSignBitReductionCmp(Instruction &
I);
155 bool foldReductionZeroTest(Instruction &
I);
156 bool foldICmpEqZeroVectorReduce(Instruction &
I);
157 bool foldEquivalentReductionCmp(Instruction &
I);
158 bool foldReduceAddCmpZero(Instruction &
I);
159 bool foldSelectShuffle(Instruction &
I,
bool FromReduction =
false);
160 bool foldInterleaveIntrinsics(Instruction &
I);
161 bool foldDeinterleaveIntrinsics(Instruction &
I);
162 bool foldBitcastOfVPLoad(Instruction &
I);
163 bool foldBitOrderReverseAndSwap(Instruction &
I);
164 bool shrinkType(Instruction &
I);
165 bool shrinkLoadForShuffles(Instruction &
I);
166 bool shrinkPhiOfShuffles(Instruction &
I);
167 bool foldInterleaveOfDeinterleaveChains(Instruction &
I);
169 void replaceValue(Instruction &Old,
Value &New,
bool Erase =
true) {
175 Worklist.pushUsersToWorkList(*NewI);
176 Worklist.pushValue(NewI);
193 SmallPtrSet<Value *, 4> Visited;
198 OpI,
nullptr,
nullptr, [&](
Value *V) {
203 NextInst = NextInst->getNextNode();
208 Worklist.pushUsersToWorkList(*OpI);
209 Worklist.pushValue(OpI);
227 return X->getType() ==
Y->getType() &&
236 Load->getFunction()->hasFnAttribute(Attribute::SanitizeMemTag) ||
242 Type *ScalarTy =
Load->getType()->getScalarType();
244 unsigned MinVectorSize =
TTI.getMinVectorRegisterBitWidth();
245 if (!ScalarSize || !MinVectorSize || MinVectorSize % ScalarSize != 0 ||
252bool VectorCombine::vectorizeLoadInsert(
Instruction &
I) {
278 Value *SrcPtr =
Load->getPointerOperand()->stripPointerCasts();
281 unsigned MinVecNumElts = MinVectorSize / ScalarSize;
282 auto *MinVecTy = VectorType::get(ScalarTy, MinVecNumElts,
false);
283 unsigned OffsetEltIndex = 0;
294 unsigned OffsetBitWidth =
DL->getIndexTypeSizeInBits(SrcPtr->
getType());
295 APInt
Offset(OffsetBitWidth, 0);
305 uint64_t ScalarSizeInBytes = ScalarSize / 8;
306 if (
Offset.urem(ScalarSizeInBytes) != 0)
310 APInt OffsetEltIndexAP =
Offset.udiv(ScalarSizeInBytes);
311 if (OffsetEltIndexAP.
uge(MinVecNumElts))
330 unsigned AS =
Load->getPointerAddressSpace();
349 unsigned OutputNumElts = Ty->getNumElements();
351 assert(OffsetEltIndex < MinVecNumElts &&
"Address offset too big");
352 Mask[0] = OffsetEltIndex;
359 if (OldCost < NewCost || !NewCost.
isValid())
370 replaceValue(
I, *VecLd);
378bool VectorCombine::widenSubvectorLoad(Instruction &
I) {
381 if (!Shuf->isIdentityWithPadding())
387 unsigned OpIndex =
any_of(Shuf->getShuffleMask(), [&NumOpElts](
int M) {
388 return M >= (int)(NumOpElts);
411 unsigned AS =
Load->getPointerAddressSpace();
426 if (OldCost < NewCost || !NewCost.
isValid())
433 replaceValue(
I, *VecLd);
440ExtractElementInst *VectorCombine::getShuffleExtract(
441 ExtractElementInst *Ext0, ExtractElementInst *Ext1,
445 assert(Index0C && Index1C &&
"Expected constant extract indexes");
447 unsigned Index0 = Index0C->getZExtValue();
448 unsigned Index1 = Index1C->getZExtValue();
451 if (Index0 == Index1)
475 if (PreferredExtractIndex == Index0)
477 if (PreferredExtractIndex == Index1)
481 return Index0 > Index1 ? Ext0 : Ext1;
489bool VectorCombine::isExtractExtractCheap(ExtractElementInst *Ext0,
490 ExtractElementInst *Ext1,
491 const Instruction &
I,
492 ExtractElementInst *&ConvertToShuffle,
493 unsigned PreferredExtractIndex) {
496 assert(Ext0IndexC && Ext1IndexC &&
"Expected constant extract indexes");
498 unsigned Opcode =
I.getOpcode();
511 assert((Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) &&
512 "Expected a compare");
522 unsigned Ext0Index = Ext0IndexC->getZExtValue();
523 unsigned Ext1Index = Ext1IndexC->getZExtValue();
537 unsigned BestExtIndex = Extract0Cost > Extract1Cost ? Ext0Index : Ext1Index;
538 unsigned BestInsIndex = Extract0Cost > Extract1Cost ? Ext1Index : Ext0Index;
539 InstructionCost CheapExtractCost = std::min(Extract0Cost, Extract1Cost);
544 if (Ext0Src == Ext1Src && Ext0Index == Ext1Index) {
549 bool HasUseTax = Ext0 == Ext1 ? !Ext0->
hasNUses(2)
551 OldCost = CheapExtractCost + ScalarOpCost;
552 NewCost = VectorOpCost + CheapExtractCost + HasUseTax * CheapExtractCost;
556 OldCost = Extract0Cost + Extract1Cost + ScalarOpCost;
557 NewCost = VectorOpCost + CheapExtractCost +
562 ConvertToShuffle = getShuffleExtract(Ext0, Ext1, PreferredExtractIndex);
563 if (ConvertToShuffle) {
575 SmallVector<int> ShuffleMask(FixedVecTy->getNumElements(),
577 ShuffleMask[BestInsIndex] = BestExtIndex;
579 VecTy, VecTy,
CostKind, ShuffleMask, 0,
580 nullptr, {ConvertToShuffle});
583 VecTy, VecTy,
CostKind, {}, 0,
nullptr,
588 LLVM_DEBUG(
dbgs() <<
"Found a binop of extractions: " <<
I <<
"\n OldCost: "
589 << OldCost <<
" vs NewCost: " << NewCost <<
"\n");
594 return OldCost < NewCost;
606 ShufMask[NewIndex] = OldIndex;
607 return Builder.CreateShuffleVector(Vec, ShufMask,
"shift");
659 V1,
"foldExtExtBinop");
664 VecBOInst->copyIRFlags(&
I);
670bool VectorCombine::foldExtractExtract(Instruction &
I) {
686 V0->getType() !=
V1->getType())
691 unsigned NumElts = FixedVecTy->getNumElements();
692 if (C0 >= NumElts || C1 >= NumElts)
708 ExtractElementInst *ExtractToChange;
709 if (isExtractExtractCheap(Ext0, Ext1,
I, ExtractToChange, InsertIndex))
715 if (ExtractToChange) {
716 unsigned CheapExtractIdx = ExtractToChange == Ext0 ? C1 : C0;
721 if (ExtractToChange == Ext0)
730 ? foldExtExtCmp(ExtOp0, ExtOp1, ExtIndex,
I)
731 : foldExtExtBinop(ExtOp0, ExtOp1, ExtIndex,
I);
734 replaceValue(
I, *NewExt);
740bool VectorCombine::foldInsExtFNeg(Instruction &
I) {
758 auto *DstVecScalarTy = DstVecTy->getScalarType();
760 if (!SrcVecTy || DstVecScalarTy != SrcVecTy->getScalarType())
765 unsigned NumDstElts = DstVecTy->getNumElements();
766 unsigned NumSrcElts = SrcVecTy->getNumElements();
767 if (ExtIdx > NumSrcElts || InsIdx >= NumDstElts || NumDstElts == 1)
773 SmallVector<int>
Mask(NumDstElts);
774 std::iota(
Mask.begin(),
Mask.end(), 0);
775 Mask[InsIdx] = (ExtIdx % NumDstElts) + NumDstElts;
791 bool NeedLenChg = SrcVecTy->getNumElements() != NumDstElts;
794 SmallVector<int> SrcMask;
797 SrcMask[ExtIdx % NumDstElts] = ExtIdx;
799 DstVecTy, SrcVecTy,
CostKind, SrcMask);
803 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
805 if (NewCost > OldCost)
808 Value *NewShuf, *LenChgShuf =
nullptr;
822 replaceValue(
I, *NewShuf);
828bool VectorCombine::foldInsExtBinop(Instruction &
I) {
829 BinaryOperator *VecBinOp, *SclBinOp;
861 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
863 if (NewCost > OldCost)
874 NewInst->copyIRFlags(VecBinOp);
875 NewInst->andIRFlags(SclBinOp);
880 replaceValue(
I, *NewBO);
886bool VectorCombine::foldBitOpOfCastops(Instruction &
I) {
889 if (!BinOp || !BinOp->isBitwiseLogicOp())
895 if (!LHSCast || !RHSCast) {
896 LLVM_DEBUG(
dbgs() <<
" One or both operands are not cast instructions\n");
902 if (CastOpcode != RHSCast->getOpcode())
906 switch (CastOpcode) {
907 case Instruction::BitCast:
908 case Instruction::Trunc:
909 case Instruction::SExt:
910 case Instruction::ZExt:
916 Value *LHSSrc = LHSCast->getOperand(0);
917 Value *RHSSrc = RHSCast->getOperand(0);
923 auto *SrcTy = LHSSrc->
getType();
924 auto *DstTy =
I.getType();
927 if (CastOpcode != Instruction::BitCast &&
932 if (!SrcTy->getScalarType()->isIntegerTy() ||
933 !DstTy->getScalarType()->isIntegerTy())
948 LHSCastCost + RHSCastCost;
959 if (!LHSCast->hasOneUse())
960 NewCost += LHSCastCost;
961 if (!RHSCast->hasOneUse())
962 NewCost += RHSCastCost;
965 <<
" NewCost=" << NewCost <<
"\n");
967 if (NewCost > OldCost)
972 BinOp->getName() +
".inner");
974 NewBinOp->copyIRFlags(BinOp);
988 replaceValue(
I, *Result);
997bool VectorCombine::foldBitOpOfCastConstant(Instruction &
I) {
1013 switch (CastOpcode) {
1014 case Instruction::BitCast:
1015 case Instruction::ZExt:
1016 case Instruction::SExt:
1017 case Instruction::Trunc:
1023 Value *LHSSrc = LHSCast->getOperand(0);
1025 auto *SrcTy = LHSSrc->
getType();
1026 auto *DstTy =
I.getType();
1029 if (CastOpcode != Instruction::BitCast &&
1034 if (!SrcTy->getScalarType()->isIntegerTy() ||
1035 !DstTy->getScalarType()->isIntegerTy())
1039 PreservedCastFlags RHSFlags;
1064 if (!LHSCast->hasOneUse())
1065 NewCost += LHSCastCost;
1067 LLVM_DEBUG(
dbgs() <<
"foldBitOpOfCastConstant: OldCost=" << OldCost
1068 <<
" NewCost=" << NewCost <<
"\n");
1070 if (NewCost > OldCost)
1075 LHSSrc, InvC,
I.getName() +
".inner");
1077 NewBinOp->copyIRFlags(&
I);
1097 replaceValue(
I, *Result);
1104bool VectorCombine::foldBitcastShuffle(Instruction &
I) {
1118 if (!DestTy || !SrcTy)
1121 unsigned DestEltSize = DestTy->getScalarSizeInBits();
1122 unsigned SrcEltSize = SrcTy->getScalarSizeInBits();
1123 if (SrcTy->getPrimitiveSizeInBits() % DestEltSize != 0)
1133 if (!(BCTy0 && BCTy0->getElementType() == DestTy->getElementType()) &&
1134 !(BCTy1 && BCTy1->getElementType() == DestTy->getElementType()))
1138 SmallVector<int, 16> NewMask;
1139 if (DestEltSize <= SrcEltSize) {
1142 if (SrcEltSize % DestEltSize != 0)
1144 unsigned ScaleFactor = SrcEltSize / DestEltSize;
1149 if (DestEltSize % SrcEltSize != 0)
1151 unsigned ScaleFactor = DestEltSize / SrcEltSize;
1158 unsigned NumSrcElts = SrcTy->getPrimitiveSizeInBits() / DestEltSize;
1159 auto *NewShuffleTy =
1161 auto *OldShuffleTy =
1163 unsigned NumOps = IsUnary ? 1 : 2;
1173 TargetTransformInfo::CastContextHint::None,
1178 TargetTransformInfo::CastContextHint::None,
1181 LLVM_DEBUG(
dbgs() <<
"Found a bitcasted shuffle: " <<
I <<
"\n OldCost: "
1182 << OldCost <<
" vs NewCost: " << NewCost <<
"\n");
1184 if (NewCost > OldCost || !NewCost.
isValid())
1192 replaceValue(
I, *Shuf);
1199bool VectorCombine::scalarizeOpOrCmp(Instruction &
I) {
1204 if (!UO && !BO && !CI && !
II)
1212 if (Arg->getType() !=
II->getType() &&
1222 for (User *U :
I.users())
1229 std::optional<uint64_t>
Index;
1231 auto Ops =
II ?
II->args() :
I.operands();
1240 if (OpTy->getElementCount().getKnownMinValue() <= InsIdx)
1246 else if (InsIdx != *Index)
1263 if (!
Index.has_value())
1267 Type *ScalarTy = VecTy->getScalarType();
1268 assert(VecTy->isVectorTy() &&
1271 "Unexpected types for insert element into binop or cmp");
1273 unsigned Opcode =
I.getOpcode();
1281 }
else if (UO || BO) {
1285 IntrinsicCostAttributes ScalarICA(
1286 II->getIntrinsicID(), ScalarTy,
1289 IntrinsicCostAttributes VectorICA(
1290 II->getIntrinsicID(), VecTy,
1297 Value *NewVecC =
nullptr;
1299 NewVecC =
simplifyCmpInst(CI->getPredicate(), VecCs[0], VecCs[1], SQ);
1302 simplifyUnOp(UO->getOpcode(), VecCs[0], UO->getFastMathFlags(), SQ);
1304 NewVecC =
simplifyBinOp(BO->getOpcode(), VecCs[0], VecCs[1], SQ);
1318 for (
auto [Idx,
Op, VecC, Scalar] :
enumerate(
Ops, VecCs, ScalarOps)) {
1320 II->getIntrinsicID(), Idx, &
TTI)))
1323 Instruction::InsertElement, VecTy,
CostKind, *Index, VecC, Scalar);
1324 OldCost += InsertCost;
1325 NewCost += !
Op->hasOneUse() * InsertCost;
1329 if (OldCost < NewCost || !NewCost.
isValid())
1339 ++NumScalarIntrinsic;
1342 for (
auto [OpIdx, Scalar, VecC] :
enumerate(ScalarOps, VecCs))
1354 ScalarOps[1], FPMO->getFastMathFlags(),
1355 CI->getName() +
".scalar");
1358 ScalarOps[1], CI->getName() +
".scalar");
1362 UO->getName() +
".scalar");
1364 if (OverflowingBinaryOperator *OBO =
1367 BO->getOpcode(), ScalarOps[0], ScalarOps[1], OBO->hasNoUnsignedWrap(),
1368 OBO->hasNoSignedWrap(), BO->getName() +
".scalar");
1371 BO->getName() +
".scalar", PDI->isDisjoint());
1372 }
else if (PossiblyExactOperator *PEO =
1376 PEO->isExact(), BO->getName() +
".scalar");
1379 ScalarOps[1], FPMO->getFastMathFlags(),
1380 BO->getName() +
".scalar");
1383 BO->getName() +
".scalar");
1388 FMF = FPMO->getFastMathFlags();
1390 FMF,
II->getName() +
".scalar");
1394 replaceValue(
I, *Insert);
1401bool VectorCombine::foldExtractedCmps(Instruction &
I) {
1406 if (!BI || !
I.getType()->isIntegerTy(1))
1411 Value *
B0 =
I.getOperand(0), *
B1 =
I.getOperand(1);
1414 CmpPredicate
P0,
P1;
1433 ExtractElementInst *ConvertToShuf = getShuffleExtract(Ext0, Ext1,
CostKind);
1436 assert((ConvertToShuf == Ext0 || ConvertToShuf == Ext1) &&
1437 "Unknown ExtractElementInst");
1442 unsigned CmpOpcode =
1448 if (Index0 >= VecTy->getNumElements() || Index1 >= VecTy->getNumElements())
1460 Ext0Cost + Ext1Cost + CmpCost * 2 +
1466 int CheapIndex = ConvertToShuf == Ext0 ? Index1 : Index0;
1467 int ExpensiveIndex = ConvertToShuf == Ext0 ? Index0 : Index1;
1472 ShufMask[CheapIndex] = ExpensiveIndex;
1477 NewCost += Ext0->
hasOneUse() ? 0 : Ext0Cost;
1478 NewCost += Ext1->
hasOneUse() ? 0 : Ext1Cost;
1483 if (OldCost < NewCost || !NewCost.
isValid())
1493 Value *
LHS = ConvertToShuf == Ext0 ? Shuf : VCmp;
1494 Value *
RHS = ConvertToShuf == Ext0 ? VCmp : Shuf;
1497 replaceValue(
I, *NewExt);
1524bool VectorCombine::foldSelectsFromBitcast(Instruction &
I) {
1531 if (!SrcVecTy || !DstVecTy)
1541 if (SrcEltBits != 32 && SrcEltBits != 64)
1544 if (!DstEltTy->
isIntegerTy() || DstEltBits >= SrcEltBits)
1561 if (!ScalarSelCost.
isValid() || ScalarSelCost == 0)
1564 unsigned MinSelects = (VecSelCost.
getValue() / ScalarSelCost.
getValue()) + 1;
1567 if (!BC->hasNUsesOrMore(MinSelects))
1572 DenseMap<Value *, SmallVector<SelectInst *, 8>> CondToSelects;
1574 for (User *U : BC->users()) {
1579 for (User *ExtUser : Ext->users()) {
1583 Cond->getType()->isIntegerTy(1))
1588 if (CondToSelects.
empty())
1591 bool MadeChange =
false;
1592 Value *SrcVec = BC->getOperand(0);
1595 for (
auto [
Cond, Selects] : CondToSelects) {
1597 if (Selects.size() < MinSelects) {
1598 LLVM_DEBUG(
dbgs() <<
"VectorCombine: foldSelectsFromBitcast not "
1599 <<
"profitable (VecCost=" << VecSelCost
1600 <<
", ScalarCost=" << ScalarSelCost
1601 <<
", NumSelects=" << Selects.size() <<
")\n");
1606 auto InsertPt = std::next(BC->getIterator());
1610 InsertPt = std::next(CondInst->getIterator());
1618 for (SelectInst *Sel : Selects) {
1620 Value *
Idx = Ext->getIndexOperand();
1624 replaceValue(*Sel, *NewExt);
1629 <<
" selects into vector select\n");
1643 unsigned ReductionOpc =
1649 CostBeforeReduction =
1650 TTI.getCastInstrCost(RedOp->getOpcode(), VecRedTy, ExtType,
1652 CostAfterReduction =
1653 TTI.getExtendedReductionCost(ReductionOpc, IsUnsigned,
II.getType(),
1657 if (RedOp &&
II.getIntrinsicID() == Intrinsic::vector_reduce_add &&
1663 (Op0->
getOpcode() == RedOp->getOpcode() || Op0 == Op1)) {
1670 TTI.getCastInstrCost(Op0->
getOpcode(), MulType, ExtType,
1673 TTI.getArithmeticInstrCost(Instruction::Mul, MulType,
CostKind);
1675 TTI.getCastInstrCost(RedOp->getOpcode(), VecRedTy, MulType,
1678 CostBeforeReduction = ExtCost * 2 + MulCost + Ext2Cost;
1679 CostAfterReduction =
TTI.getMulAccReductionCost(
1680 IsUnsigned, ReductionOpc,
II.getType(), ExtType,
CostKind);
1683 CostAfterReduction =
TTI.getArithmeticReductionCost(ReductionOpc, VecRedTy,
1687bool VectorCombine::foldBinopOfReductions(Instruction &
I) {
1690 if (BinOpOpc == Instruction::Sub)
1691 ReductionIID = Intrinsic::vector_reduce_add;
1695 if (ReductionIID == Intrinsic::vector_reduce_fadd ||
1696 ReductionIID == Intrinsic::vector_reduce_fmul)
1699 auto checkIntrinsicAndGetItsArgument = [](
Value *
V,
1704 if (
II->getIntrinsicID() == IID &&
II->hasOneUse())
1705 return II->getArgOperand(0);
1709 Value *
V0 = checkIntrinsicAndGetItsArgument(
I.getOperand(0), ReductionIID);
1712 Value *
V1 = checkIntrinsicAndGetItsArgument(
I.getOperand(1), ReductionIID);
1717 if (
V1->getType() != VTy)
1721 unsigned ReductionOpc =
1734 CostOfRedOperand0 + CostOfRedOperand1 +
1737 if (NewCost >= OldCost || !NewCost.
isValid())
1741 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
1744 if (BinOpOpc == Instruction::Or)
1751 replaceValue(
I, *Rdx);
1760 unsigned NumScanned = 0;
1775class ScalarizationResult {
1776 enum class StatusTy { Unsafe,
Safe, SafeWithFreeze };
1781 ScalarizationResult(StatusTy Status,
Value *ToFreeze =
nullptr)
1782 : Status(Status), ToFreeze(ToFreeze) {}
1785 ScalarizationResult(
const ScalarizationResult &
Other) =
default;
1786 ~ScalarizationResult() {
1787 assert(!ToFreeze &&
"freeze() not called with ToFreeze being set");
1790 static ScalarizationResult unsafe() {
return {StatusTy::Unsafe}; }
1791 static ScalarizationResult safe() {
return {StatusTy::Safe}; }
1792 static ScalarizationResult safeWithFreeze(
Value *ToFreeze) {
1793 return {StatusTy::SafeWithFreeze, ToFreeze};
1797 bool isSafe()
const {
return Status == StatusTy::Safe; }
1799 bool isUnsafe()
const {
return Status == StatusTy::Unsafe; }
1802 bool isSafeWithFreeze()
const {
return Status == StatusTy::SafeWithFreeze; }
1807 Status = StatusTy::Unsafe;
1811 void freeze(IRBuilderBase &Builder, Instruction &UserI) {
1812 assert(isSafeWithFreeze() &&
1813 "should only be used when freezing is required");
1815 "UserI must be a user of ToFreeze");
1816 IRBuilder<>::InsertPointGuard Guard(Builder);
1821 if (
U.get() == ToFreeze)
1836 uint64_t NumElements = VecTy->getElementCount().getKnownMinValue();
1837 unsigned IntWidth = Idx->getType()->getScalarSizeInBits();
1840 if (
C->getValue().ult(NumElements))
1841 return ScalarizationResult::safe();
1842 return ScalarizationResult::unsafe();
1847 return ScalarizationResult::unsafe();
1849 APInt Zero(IntWidth, 0);
1850 APInt MaxElts(IntWidth, NumElements);
1857 return ScalarizationResult::safe();
1858 return ScalarizationResult::unsafe();
1871 if (ValidIndices.
contains(IdxRange))
1872 return ScalarizationResult::safeWithFreeze(IdxBase);
1873 return ScalarizationResult::unsafe();
1893 unsigned GEPBits = GEPIndexTy->getBitWidth();
1894 uint64_t NumElements = VecTy->getElementCount().getKnownMinValue();
1896 uint64_t MaxLane = NumElements - 1;
1898 if (
C->getValue().uge(NumElements))
1900 MaxLane =
C->getZExtValue();
1904 if (!
DL.typeSizeEqualsStoreSize(
ElemTy))
1924 unsigned WideBits = std::max(GEPBits, 128u);
1925 APInt MaxLaneValue(WideBits, MaxLane);
1926 APInt ByteOffset = MaxLaneValue;
1931 if (ByteOffset.
ugt(MaxGEPOffset))
1942 unsigned SrcBits = Idx->getType()->getIntegerBitWidth();
1944 if (SrcBits >= DstBits)
1947 return Builder.CreateZExt(Idx, GEPIndexTy, Idx->getName() +
".gepidx");
1959 C->getZExtValue() *
DL.getTypeStoreSize(ScalarType));
1996bool VectorCombine::foldInsertElementsToStores(Instruction &
I) {
2011 if (!
Insert->hasOneUse())
2019 if (InsertElements.
empty())
2024 std::reverse(InsertElements.
begin(), InsertElements.
end());
2033 if (InsertElements.
size() == FVT->getNumElements()) {
2034 Value *FirstVal = InsertElements.
front().first;
2035 if (
all_of(InsertElements,
2036 [FirstVal](
const auto &Elt) {
return Elt.first == FirstVal; }))
2040 Value *SrcAddr =
Load->getPointerOperand()->stripPointerCasts();
2045 if (!
Load->isSimple() ||
Load->getParent() !=
SI->getParent() ||
2046 !
DL->typeSizeEqualsStoreSize(
Load->getType()->getScalarType()) ||
2047 SrcAddr !=
SI->getPointerOperand()->stripPointerCasts())
2057 for (
auto [InsertVal, Idx] : InsertElements) {
2058 auto ScalarizableIdx =
2060 if (ScalarizableIdx.isUnsafe())
2066 ScalarizableIdx.discard();
2072 ScalarizableIdx.discard();
2076 Instruction::Store,
SI->getValueOperand()->getType(),
SI->getAlign(),
2079 if (
Load->hasOneUse())
2084 for (
auto [InsertVal, Idx] : InsertElements) {
2087 Index = CIdx->getZExtValue();
2098 for (
auto [InsertVal, Idx] : InsertElements) {
2101 const Value *GEPIndices[] = {ConstantInt::get(
Idx->getType(), 0),
Idx};
2106 for (
auto [InsertVal, Idx] : InsertElements) {
2108 std::max(
SI->getAlign(),
Load->getAlign()), InsertVal->
getType(), Idx,
2116 LLVM_DEBUG(
dbgs() <<
"Found an insert-elements vector store scalarization "
2119 <<
" NumInserts: " << InsertElements.size() <<
"\n"
2120 <<
" OldCost: " << OldCost <<
" vs NewCost: " << NewCost
2123 if (OldCost <= NewCost)
2126 for (
auto [InsertVal, Idx] : InsertElements) {
2127 auto ScalarizableIdx =
2129 assert(!ScalarizableIdx.isUnsafe() &&
"already checked above");
2131 if (ScalarizableIdx.isSafeWithFreeze())
2136 StoreInst *LastStore =
nullptr;
2137 for (
auto [InsertVal, Idx] : InsertElements) {
2138 auto ScalarizableIdx =
2140 if (ScalarizableIdx.isUnsafe())
2143 IntegerType *GEPIndexTy =
2148 SI->getValueOperand()->getType(),
SI->getPointerOperand(),
2149 {ConstantInt::get(GEPIdx->getType(), 0), GEPIdx});
2156 LastStore->
setMetadata(LLVMContext::MD_invariant_group,
nullptr);
2158 std::max(
SI->getAlign(),
Load->getAlign()), InsertVal->
getType(), Idx,
2163 replaceValue(
I, *LastStore);
2170bool VectorCombine::scalarizeLoad(Instruction &
I) {
2180 if (!LI->isSimple() || !
DL->typeSizeEqualsStoreSize(VecTy->getScalarType()))
2183 bool AllExtracts =
true;
2184 bool AllBitcasts =
true;
2186 unsigned NumInstChecked = 0;
2191 for (User *U : LI->users()) {
2193 if (!UI || UI->getParent() != LI->getParent())
2198 if (UI->use_empty())
2202 AllExtracts =
false;
2204 AllBitcasts =
false;
2208 for (Instruction &
I :
2209 make_range(std::next(LI->getIterator()), UI->getIterator())) {
2216 LastCheckedInst = UI;
2221 return scalarizeLoadExtract(LI, VecTy, Ptr);
2223 return scalarizeLoadBitcast(LI, VecTy, Ptr);
2228bool VectorCombine::scalarizeLoadExtract(LoadInst *LI, VectorType *VecTy,
2233 DenseMap<ExtractElementInst *, ScalarizationResult> NeedFreeze;
2234 DenseMap<ExtractElementInst *, IntegerType *> GEPIndexInfos;
2237 for (
auto &Pair : NeedFreeze)
2238 Pair.second.discard();
2246 for (User *U : LI->
users()) {
2251 if (ScalarIdx.isUnsafe())
2257 ScalarIdx.discard();
2263 if (ScalarIdx.isSafeWithFreeze()) {
2264 NeedFreeze.try_emplace(UI, ScalarIdx);
2265 ScalarIdx.discard();
2271 Index ?
Index->getZExtValue() : -1);
2277 if (!Index && UI->getIndexOperand()->getType()->getIntegerBitWidth() <
2280 Instruction::ZExt, GEPIndex, UI->getIndexOperand()->getType(),
2284 LLVM_DEBUG(
dbgs() <<
"Found all extractions of a vector load: " << *LI
2285 <<
"\n LoadExtractCost: " << OriginalCost
2286 <<
" vs ScalarizedCost: " << ScalarizedCost <<
"\n");
2288 if (ScalarizedCost > OriginalCost)
2290 if (ScalarizedCost == OriginalCost && !LI->
hasOneUse())
2297 Type *ElemType = VecTy->getElementType();
2300 for (User *U : LI->
users()) {
2302 Value *
Idx = EI->getIndexOperand();
2305 if (
auto It = NeedFreeze.find(EI); It != NeedFreeze.end())
2309 auto It = GEPIndexInfos.
find(EI);
2311 "Missing scalarized GEP index information");
2314 VecTy, Ptr, {ConstantInt::get(GEPIdx->
getType(), 0), GEPIdx});
2316 Builder.
CreateLoad(ElemType,
GEP, EI->getName() +
".scalar"));
2318 Align ScalarOpAlignment =
2320 NewLoad->setAlignment(ScalarOpAlignment);
2323 size_t Offset = ConstIdx->getZExtValue() *
DL->getTypeStoreSize(ElemType);
2328 replaceValue(*EI, *NewLoad,
false);
2331 FailureGuard.release();
2336bool VectorCombine::scalarizeLoadBitcast(LoadInst *LI, VectorType *VecTy,
2345 Type *TargetScalarType =
nullptr;
2346 unsigned VecBitWidth =
DL->getTypeSizeInBits(VecTy);
2348 for (User *U : LI->
users()) {
2351 Type *DestTy = BC->getDestTy();
2355 unsigned DestBitWidth =
DL->getTypeSizeInBits(DestTy);
2356 if (DestBitWidth != VecBitWidth)
2360 if (!TargetScalarType)
2361 TargetScalarType = DestTy;
2362 else if (TargetScalarType != DestTy)
2370 if (!TargetScalarType)
2378 LLVM_DEBUG(
dbgs() <<
"Found vector load feeding only bitcasts: " << *LI
2379 <<
"\n OriginalCost: " << OriginalCost
2380 <<
" vs ScalarizedCost: " << ScalarizedCost <<
"\n");
2382 if (ScalarizedCost >= OriginalCost)
2393 ScalarLoad->copyMetadata(*LI);
2396 for (User *U : LI->
users()) {
2398 replaceValue(*BC, *ScalarLoad,
false);
2404bool VectorCombine::scalarizeExtExtract(Instruction &
I) {
2419 Type *ScalarDstTy = DstTy->getElementType();
2420 if (
DL->getTypeSizeInBits(SrcTy) !=
DL->getTypeSizeInBits(ScalarDstTy))
2426 unsigned ExtCnt = 0;
2427 bool ExtLane0 =
false;
2428 for (User *U : Ext->users()) {
2434 if (Idx >= SrcTy->getNumElements())
2446 Instruction::And, ScalarDstTy,
CostKind,
2449 (ExtCnt - ExtLane0) *
2451 Instruction::LShr, ScalarDstTy,
CostKind,
2454 if (ScalarCost > VectorCost)
2457 Value *ScalarV = Ext->getOperand(0);
2464 SmallDenseSet<ConstantInt *, 8> ExtractedLanes;
2465 bool AllExtractsTriggerUB =
true;
2466 ExtractElementInst *LastExtract =
nullptr;
2468 for (User *U : Ext->users()) {
2471 AllExtractsTriggerUB =
false;
2475 if (!LastExtract || LastExtract->
comesBefore(Extract))
2476 LastExtract = Extract;
2478 if (ExtractedLanes.
size() != DstTy->getNumElements() ||
2479 !AllExtractsTriggerUB ||
2487 uint64_t SrcEltSizeInBits =
DL->getTypeSizeInBits(SrcTy->getElementType());
2488 uint64_t TotalBits =
DL->getTypeSizeInBits(SrcTy);
2491 Value *
Mask = ConstantInt::get(PackedTy, EltBitMask);
2492 for (User *U : Ext->users()) {
2498 ? (TotalBits - SrcEltSizeInBits -
Idx * SrcEltSizeInBits)
2499 : (
Idx * SrcEltSizeInBits);
2502 U->replaceAllUsesWith(
And);
2510bool VectorCombine::foldConcatOfBoolMasks(Instruction &
I) {
2511 Type *Ty =
I.getType();
2516 if (
DL->isBigEndian())
2543 if (ShAmtX > ShAmtY) {
2551 uint64_t ShAmtDiff = ShAmtY - ShAmtX;
2552 unsigned NumSHL = (ShAmtX > 0) + (ShAmtY > 0);
2557 MaskTy->getNumElements() != ShAmtDiff ||
2558 MaskTy->getNumElements() > (
BitWidth / 2))
2563 Type::getIntNTy(Ty->
getContext(), ConcatTy->getNumElements());
2564 auto *MaskIntTy = Type::getIntNTy(Ty->
getContext(), ShAmtDiff);
2567 std::iota(ConcatMask.begin(), ConcatMask.end(), 0);
2584 if (Ty != ConcatIntTy)
2590 LLVM_DEBUG(
dbgs() <<
"Found a concatenation of bitcasted bool masks: " <<
I
2591 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
2594 if (NewCost > OldCost)
2604 if (Ty != ConcatIntTy) {
2614 replaceValue(
I, *Result);
2620bool VectorCombine::foldPermuteOfBinops(Instruction &
I) {
2621 BinaryOperator *BinOp;
2622 ArrayRef<int> OuterMask;
2630 Value *Op00, *Op01, *Op10, *Op11;
2631 ArrayRef<int> Mask0, Mask1;
2636 if (!Match0 && !Match1)
2649 if (!ShuffleDstTy || !BinOpTy || !Op0Ty || !Op1Ty)
2652 unsigned NumSrcElts = BinOpTy->getNumElements();
2657 any_of(OuterMask, [NumSrcElts](
int M) {
return M >= (int)NumSrcElts; }))
2661 SmallVector<int> NewMask0, NewMask1;
2662 for (
int M : OuterMask) {
2663 if (M < 0 || M >= (
int)NumSrcElts) {
2667 NewMask0.
push_back(Match0 ? Mask0[M] : M);
2668 NewMask1.
push_back(Match1 ? Mask1[M] : M);
2672 unsigned NumOpElts = Op0Ty->getNumElements();
2673 bool IsIdentity0 = ShuffleDstTy == Op0Ty &&
2674 all_of(NewMask0, [NumOpElts](
int M) {
return M < (int)NumOpElts; }) &&
2676 bool IsIdentity1 = ShuffleDstTy == Op1Ty &&
2677 all_of(NewMask1, [NumOpElts](
int M) {
return M < (int)NumOpElts; }) &&
2686 ShuffleDstTy, BinOpTy,
CostKind, OuterMask,
2687 0,
nullptr, {BinOp}, &
I);
2689 NewCost += BinOpCost;
2695 OldCost += Shuf0Cost;
2697 NewCost += Shuf0Cost;
2703 OldCost += Shuf1Cost;
2705 NewCost += Shuf1Cost;
2713 Op0Ty,
CostKind, NewMask0, 0,
nullptr, {Op00, Op01});
2717 Op1Ty,
CostKind, NewMask1, 0,
nullptr, {Op10, Op11});
2719 LLVM_DEBUG(
dbgs() <<
"Found a shuffle feeding a shuffled binop: " <<
I
2720 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
2724 if (NewCost > OldCost)
2735 NewInst->copyIRFlags(BinOp);
2739 replaceValue(
I, *NewBO);
2745bool VectorCombine::foldShuffleOfBinops(Instruction &
I) {
2746 ArrayRef<int> OldMask;
2753 if (
LHS->getOpcode() !=
RHS->getOpcode())
2757 bool IsCommutative =
false;
2766 IsCommutative = BinaryOperator::isCommutative(BO->getOpcode());
2777 if (!ShuffleDstTy || !BinResTy || !BinOpTy ||
X->getType() !=
Z->getType())
2780 bool SameBinOp =
LHS ==
RHS;
2781 unsigned NumSrcElts = BinOpTy->getNumElements();
2784 if (IsCommutative &&
X != Z &&
Y != W && (
X == W ||
Y == Z))
2787 auto ConvertToUnary = [NumSrcElts](
int &
M) {
2788 if (M >= (
int)NumSrcElts)
2792 SmallVector<int> NewMask0(OldMask);
2801 SmallVector<int> NewMask1(OldMask);
2820 ShuffleDstTy, BinResTy,
CostKind, OldMask, 0,
2830 ArrayRef<int> InnerMask;
2832 m_Mask(InnerMask)))) &&
2835 [NumSrcElts](
int M) {
return M < (int)NumSrcElts; })) {
2847 bool ReducedInstCount =
false;
2848 ReducedInstCount |= MergeInner(
X, 0, NewMask0,
CostKind);
2849 ReducedInstCount |= MergeInner(
Y, 0, NewMask1,
CostKind);
2850 ReducedInstCount |= MergeInner(Z, NumSrcElts, NewMask0,
CostKind);
2851 ReducedInstCount |= MergeInner(W, NumSrcElts, NewMask1,
CostKind);
2852 bool SingleSrcBinOp = (
X ==
Y) && (Z == W) && (NewMask0 == NewMask1);
2864 I.getType()->getScalarType()->isIntegerTy(1) &&
2868 auto *ShuffleCmpTy =
2871 SK0, ShuffleCmpTy, BinOpTy,
CostKind, NewMask0, 0,
nullptr, {
X,
Z});
2872 if (!SingleSrcBinOp)
2874 NewMask1, 0,
nullptr, {
Y,
W});
2882 PredLHS,
CostKind, Op0Info, Op1Info);
2892 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
2899 if (ReducedInstCount ? (NewCost > OldCost) : (NewCost >= OldCost))
2908 : Builder.
CreateCmp(PredLHS, Shuf0, Shuf1);
2912 NewInst->copyIRFlags(
LHS);
2913 NewInst->andIRFlags(
RHS);
2918 replaceValue(
I, *NewBO);
2925bool VectorCombine::foldShuffleOfSelects(Instruction &
I) {
2927 Value *C1, *
T1, *F1, *C2, *T2, *F2;
2938 if (!C1VecTy || !C2VecTy || C1VecTy != C2VecTy)
2944 if (((SI0FOp ==
nullptr) != (SI1FOp ==
nullptr)) ||
2945 ((SI0FOp !=
nullptr) &&
2946 (SI0FOp->getFastMathFlags() != SI1FOp->getFastMathFlags())))
2952 auto SelOp = Instruction::Select;
2960 CostSel1 + CostSel2 +
2962 {
I.getOperand(0),
I.getOperand(1)}, &
I);
2966 CostKind, Mask, 0,
nullptr, {C1, C2});
2976 if (!Sel1->hasOneUse())
2977 NewCost += CostSel1;
2978 if (!Sel2->hasOneUse())
2979 NewCost += CostSel2;
2982 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
2984 if (NewCost > OldCost)
2993 NewSel = Builder.
CreateSelectFMF(ShuffleCmp, ShuffleTrue, ShuffleFalse,
2994 SI0FOp->getFastMathFlags());
2996 NewSel = Builder.
CreateSelect(ShuffleCmp, ShuffleTrue, ShuffleFalse);
3001 replaceValue(
I, *NewSel);
3007bool VectorCombine::foldShuffleOfCastops(Instruction &
I) {
3009 ArrayRef<int> OldMask;
3018 if (!C0 || (IsBinaryShuffle && !C1))
3025 if (!IsBinaryShuffle && Opcode == Instruction::BitCast)
3028 if (IsBinaryShuffle) {
3029 if (C0->getSrcTy() != C1->getSrcTy())
3032 if (Opcode != C1->getOpcode()) {
3034 Opcode = Instruction::SExt;
3043 if (!ShuffleDstTy || !CastDstTy || !CastSrcTy)
3046 unsigned NumSrcElts = CastSrcTy->getNumElements();
3047 unsigned NumDstElts = CastDstTy->getNumElements();
3048 assert((NumDstElts == NumSrcElts || Opcode == Instruction::BitCast) &&
3049 "Only bitcasts expected to alter src/dst element counts");
3053 if (NumDstElts != NumSrcElts && (NumSrcElts % NumDstElts) != 0 &&
3054 (NumDstElts % NumSrcElts) != 0)
3057 SmallVector<int, 16> NewMask;
3058 if (NumSrcElts >= NumDstElts) {
3061 assert(NumSrcElts % NumDstElts == 0 &&
"Unexpected shuffle mask");
3062 unsigned ScaleFactor = NumSrcElts / NumDstElts;
3067 assert(NumDstElts % NumSrcElts == 0 &&
"Unexpected shuffle mask");
3068 unsigned ScaleFactor = NumDstElts / NumSrcElts;
3073 auto *NewShuffleDstTy =
3082 if (IsBinaryShuffle)
3089 OldMask, 0,
nullptr, {}, &
I);
3097 if (IsBinaryShuffle) {
3107 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
3109 if (NewCost > OldCost)
3113 if (IsBinaryShuffle)
3123 NewInst->copyIRFlags(C0);
3124 if (IsBinaryShuffle)
3125 NewInst->andIRFlags(C1);
3129 replaceValue(
I, *Cast);
3139bool VectorCombine::foldShuffleOfShuffles(Instruction &
I) {
3140 ArrayRef<int> OuterMask;
3141 Value *OuterV0, *OuterV1;
3146 ArrayRef<int> InnerMask0, InnerMask1;
3147 Value *X0, *X1, *Y0, *Y1;
3152 if (!Match0 && !Match1)
3157 SmallVector<int, 16> PoisonMask1;
3162 InnerMask1 = PoisonMask1;
3166 X0 = Match0 ? X0 : OuterV0;
3167 Y0 = Match0 ? Y0 : OuterV0;
3168 X1 = Match1 ? X1 : OuterV1;
3169 Y1 = Match1 ? Y1 : OuterV1;
3173 if (!ShuffleDstTy || !ShuffleSrcTy || !ShuffleImmTy ||
3177 unsigned NumSrcElts = ShuffleSrcTy->getNumElements();
3178 unsigned NumImmElts = ShuffleImmTy->getNumElements();
3183 SmallVector<int, 16> NewMask(OuterMask);
3184 Value *NewX =
nullptr, *NewY =
nullptr;
3185 for (
int &M : NewMask) {
3186 Value *Src =
nullptr;
3187 if (0 <= M && M < (
int)NumImmElts) {
3191 Src =
M >= (int)NumSrcElts ? Y0 : X0;
3192 M =
M >= (int)NumSrcElts ? (M - NumSrcElts) :
M;
3194 }
else if (M >= (
int)NumImmElts) {
3199 Src =
M >= (int)NumSrcElts ? Y1 : X1;
3200 M =
M >= (int)NumSrcElts ? (M - NumSrcElts) :
M;
3204 assert(0 <= M && M < (
int)NumSrcElts &&
"Unexpected shuffle mask index");
3213 if (!NewX || NewX == Src) {
3217 if (!NewY || NewY == Src) {
3236 replaceValue(
I, *NewX);
3253 bool IsUnary =
all_of(NewMask, [&](
int M) {
return M < (int)NumSrcElts; });
3259 nullptr, {NewX, NewY});
3261 NewCost += InnerCost0;
3263 NewCost += InnerCost1;
3266 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
3268 if (NewCost > OldCost)
3272 replaceValue(
I, *Shuf);
3288bool VectorCombine::foldShufflesOfLengthChangingShuffles(Instruction &
I) {
3293 unsigned ChainLength = 0;
3294 SmallVector<int>
Mask;
3295 SmallVector<int> YMask;
3305 ArrayRef<int> OuterMask;
3306 Value *OuterV0, *OuterV1;
3307 if (ChainLength != 0 && !Trunk->
hasOneUse())
3310 m_Mask(OuterMask))))
3312 if (OuterV0->
getType() != TrunkType) {
3318 ArrayRef<int> InnerMask0, InnerMask1;
3324 bool Match0Leaf = Match0 && A0->
getType() !=
I.getType();
3325 bool Match1Leaf = Match1 && A1->
getType() !=
I.getType();
3326 if (Match0Leaf == Match1Leaf) {
3332 SmallVector<int> CommutedOuterMask;
3339 for (
int &M : CommutedOuterMask) {
3342 if (M < (
int)NumTrunkElts)
3347 OuterMask = CommutedOuterMask;
3366 int NumLeafElts = YType->getNumElements();
3367 SmallVector<int> LocalYMask(InnerMask1);
3368 for (
int &M : LocalYMask) {
3369 if (M >= NumLeafElts)
3379 Mask.assign(OuterMask);
3380 YMask.
assign(LocalYMask);
3381 OldCost = NewCost = LocalOldCost;
3388 SmallVector<int> NewYMask(YMask);
3390 for (
auto [CombinedM, LeafM] :
llvm::zip(NewYMask, LocalYMask)) {
3391 if (LeafM == -1 || CombinedM == LeafM)
3393 if (CombinedM == -1) {
3403 SmallVector<int> NewMask;
3404 NewMask.
reserve(NumTrunkElts);
3405 for (
int M : Mask) {
3406 if (M < 0 || M >=
static_cast<int>(NumTrunkElts))
3421 if (LocalNewCost >= NewCost && LocalOldCost < LocalNewCost - NewCost)
3425 if (ChainLength == 1) {
3426 dbgs() <<
"Found chain of shuffles fed by length-changing shuffles: "
3429 dbgs() <<
" next chain link: " << *Trunk <<
'\n'
3430 <<
" old cost: " << (OldCost + LocalOldCost)
3431 <<
" new cost: " << LocalNewCost <<
'\n';
3436 OldCost += LocalOldCost;
3437 NewCost = LocalNewCost;
3441 if (ChainLength <= 1)
3449 return M < 0 || M >=
static_cast<int>(NumTrunkElts);
3452 for (
int &M : Mask) {
3453 if (M >=
static_cast<int>(NumTrunkElts))
3454 M = YMask[
M - NumTrunkElts];
3458 replaceValue(
I, *Root);
3465 replaceValue(
I, *Root);
3471bool VectorCombine::foldShuffleOfIntrinsics(Instruction &
I) {
3473 ArrayRef<int> OldMask;
3483 if (IID != II1->getIntrinsicID())
3492 if (!ShuffleDstTy || !II0Ty)
3498 for (
unsigned Idx = 0,
E = II0->arg_size(); Idx !=
E; ++Idx) {
3499 Value *Arg0 = II0->getArgOperand(Idx);
3500 Value *Arg1 = II1->getArgOperand(Idx);
3517 II0Ty,
CostKind, OldMask, 0,
nullptr, {II0, II1}, &
I);
3521 SmallDenseSet<std::pair<Value *, Value *>> SeenOperandPairs;
3522 for (
unsigned Idx = 0,
E = II0->arg_size(); Idx !=
E; ++Idx) {
3524 NewArgsTy.
push_back(II0->getArgOperand(Idx)->getType());
3528 ShuffleDstTy->getNumElements());
3530 std::pair<Value *, Value *> OperandPair =
3531 std::make_pair(II0->getArgOperand(Idx), II1->getArgOperand(Idx));
3532 if (!SeenOperandPairs.
insert(OperandPair).second) {
3538 OldMask, 0,
nullptr,
3539 {II0->getArgOperand(Idx), II1->getArgOperand(Idx)});
3542 IntrinsicCostAttributes NewAttr(IID, ShuffleDstTy, NewArgsTy);
3545 if (!II0->hasOneUse())
3547 if (II1 != II0 && !II1->hasOneUse())
3551 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
3554 if (NewCost > OldCost)
3558 SmallDenseMap<std::pair<Value *, Value *>,
Value *> ShuffleCache;
3559 for (
unsigned Idx = 0,
E = II0->arg_size(); Idx !=
E; ++Idx) {
3561 NewArgs.
push_back(II0->getArgOperand(Idx));
3563 std::pair<Value *, Value *> OperandPair =
3564 std::make_pair(II0->getArgOperand(Idx), II1->getArgOperand(Idx));
3565 auto It = ShuffleCache.
find(OperandPair);
3566 if (It != ShuffleCache.
end()) {
3572 II0->getArgOperand(Idx), II1->getArgOperand(Idx), OldMask);
3573 ShuffleCache[OperandPair] = Shuf;
3582 NewInst->copyIRFlags(II0);
3583 NewInst->andIRFlags(II1);
3586 replaceValue(
I, *NewIntrinsic);
3592bool VectorCombine::foldPermuteOfIntrinsic(Instruction &
I) {
3604 if (!ShuffleDstTy || !IntrinsicSrcTy)
3608 unsigned NumSrcElts = IntrinsicSrcTy->getNumElements();
3609 if (
any_of(Mask, [NumSrcElts](
int M) {
return M >= (int)NumSrcElts; }))
3622 IntrinsicSrcTy,
CostKind, Mask, 0,
nullptr, {
V0}, &
I);
3626 for (
unsigned I = 0,
E = II0->arg_size();
I !=
E; ++
I) {
3628 NewArgsTy.
push_back(II0->getArgOperand(
I)->getType());
3632 ShuffleDstTy->getNumElements());
3635 ArgTy, VecTy,
CostKind, Mask, 0,
nullptr,
3636 {II0->getArgOperand(
I)});
3639 IntrinsicCostAttributes NewAttr(IID, ShuffleDstTy, NewArgsTy);
3644 if (!II0->hasOneUse())
3647 LLVM_DEBUG(
dbgs() <<
"Found a permute of intrinsic: " <<
I <<
"\n OldCost: "
3648 << OldCost <<
" vs NewCost: " << NewCost <<
"\n");
3650 if (NewCost > OldCost)
3655 for (
unsigned I = 0,
E = II0->arg_size();
I !=
E; ++
I) {
3668 NewInst->copyIRFlags(II0);
3670 replaceValue(
I, *NewIntrinsic);
3680 int M = SV->getMaskValue(Lane);
3683 if (
static_cast<unsigned>(M) < NumElts) {
3684 V = SV->getOperand(0);
3687 V = SV->getOperand(1);
3698 auto [U, Lane] = IL;
3711 unsigned NumElts = Ty->getNumElements();
3712 if (Item.
size() == NumElts || NumElts == 1 || Item.
size() % NumElts != 0)
3718 std::iota(ConcatMask.
begin(), ConcatMask.
end(), 0);
3724 unsigned NumSlices = Item.
size() / NumElts;
3729 for (
unsigned Slice = 0; Slice < NumSlices; ++Slice) {
3730 Value *SliceV = Item[Slice * NumElts].first;
3731 if (!SliceV || SliceV->
getType() != Ty)
3733 for (
unsigned Elt = 0; Elt < NumElts; ++Elt) {
3734 auto [V, Lane] = Item[Slice * NumElts + Elt];
3735 if (Lane !=
static_cast<int>(Elt) || SliceV != V)
3744 const DenseSet<std::pair<Value *, Use *>> &IdentityLeafs,
3745 const DenseSet<std::pair<Value *, Use *>> &SplatLeafs,
3746 const DenseSet<std::pair<Value *, Use *>> &ConcatLeafs,
3749 auto [FrontV, FrontLane] = Item.
front();
3751 if (IdentityLeafs.contains(std::make_pair(FrontV, From))) {
3754 if (SplatLeafs.contains(std::make_pair(FrontV, From))) {
3756 return Builder.CreateShuffleVector(FrontV, Mask);
3758 if (ConcatLeafs.contains(std::make_pair(FrontV, From))) {
3762 for (
unsigned S = 0; S <
Values.size(); ++S)
3763 Values[S] = Item[S * NumElts].first;
3765 while (
Values.size() > 1) {
3768 std::iota(Mask.begin(), Mask.end(), 0);
3770 for (
unsigned S = 0; S < NewValues.
size(); ++S)
3772 Builder.CreateShuffleVector(
Values[S * 2],
Values[S * 2 + 1], Mask);
3786 if (BCDstTy && BCSrcTy &&
3787 BCDstTy->getElementCount() != BCSrcTy->getElementCount()) {
3788 unsigned DstElts = BCDstTy->getNumElements();
3789 unsigned SrcElts = BCSrcTy->getNumElements();
3791 if (DstElts > SrcElts) {
3793 unsigned R = DstElts / SrcElts;
3794 if (Item.
size() % R != 0)
3796 for (
unsigned Idx = 0,
E = Item.
size(); Idx <
E; Idx += R) {
3797 auto [V, Lane] = Item[Idx];
3807 unsigned R = SrcElts / DstElts;
3808 for (
auto [V, Lane] : Item) {
3814 for (
unsigned J = 0; J < R; ++J)
3819 IdentityLeafs, SplatLeafs, ConcatLeafs,
3820 Builder, WorkList,
TTI);
3822 return Builder.CreateBitCast(
3827 unsigned NumOps =
I->getNumOperands() - (
II ? 1 : 0);
3829 for (
unsigned Idx = 0; Idx <
NumOps; Idx++) {
3832 Ops[Idx] =
II->getOperand(Idx);
3837 IdentityLeafs, SplatLeafs, ConcatLeafs, Builder, WorkList,
TTI);
3847 for (
const auto &Lane : Item)
3860 auto *
Value = Builder.CreateCmp(CI->getPredicate(),
Ops[0],
Ops[1]);
3870 auto *
Value = Builder.CreateCast(CI->getOpcode(),
Ops[0], DstTy);
3875 auto *
Value = Builder.CreateIntrinsic(DstTy,
II->getIntrinsicID(),
Ops);
3889bool VectorCombine::foldShuffleToIdentity(Instruction &
I) {
3891 if (!Ty ||
I.use_empty())
3895 for (
unsigned M = 0,
E = Ty->getNumElements(); M <
E; ++M)
3899 Candidates.
push_back(std::make_pair(Start, &*
I.use_begin()));
3900 DenseSet<std::pair<Value *, Use *>> IdentityLeafs, SplatLeafs, ConcatLeafs;
3901 unsigned NumVisited = 0;
3902 bool TraversedElCountChangingBitcast =
false;
3904 while (!Candidates.
empty()) {
3909 auto Item = ItemFrom.first;
3910 auto From = ItemFrom.second;
3911 auto [FrontV, FrontLane] = Item.front();
3918 if (FrontLane == 0 &&
3922 Value *FrontV = Item.front().first;
3924 E.value().second == (int)
E.index());
3926 IdentityLeafs.
insert(std::make_pair(FrontV, From));
3931 C &&
C->getSplatValue() &&
3933 Value *FrontV = Item.front().first;
3939 SplatLeafs.
insert(std::make_pair(FrontV, From));
3944 auto [FrontV, FrontLane] = Item.front();
3945 auto [
V, Lane] = IL;
3946 return !
V || (
V == FrontV && Lane == FrontLane);
3948 SplatLeafs.
insert(std::make_pair(FrontV, From));
3954 auto CheckLaneIsEquivalentToFirst = [Item](
InstLane IL) {
3955 Value *FrontV = Item.front().first;
3964 if (CI->getPredicate() !=
cast<CmpInst>(FrontV)->getPredicate())
3967 if (CI->getSrcTy()->getScalarType() !=
3972 SI->getOperand(0)->getType() !=
3979 II->getIntrinsicID() ==
3981 !
II->hasOperandBundles());
3988 BO && BO->isIntDivRem())
3995 }
else if (
isa<UnaryOperator, TruncInst, ZExtInst, SExtInst, FPToSIInst,
3996 FPToUIInst, SIToFPInst, UIToFPInst>(FrontV)) {
4003 if (BCDstTy && BCSrcTy) {
4004 ElementCount DstEC = BCDstTy->getElementCount();
4005 ElementCount SrcEC = BCSrcTy->getElementCount();
4006 if (DstEC == SrcEC) {
4009 &BitCast->getOperandUse(0));
4014 if (DstElts > SrcElts && DstElts % SrcElts == 0) {
4018 unsigned R = DstElts / SrcElts;
4020 bool Valid = Item.size() %
R == 0;
4021 for (
unsigned Idx = 0,
E = Item.size(); Valid && Idx <
E;
4023 auto [
V0, L0] = Item[
Idx];
4026 [](
InstLane IL) {
return IL.first !=
nullptr; })) {
4037 for (
unsigned J = 1; J <
R; ++J) {
4038 auto [VJ, LJ] = Item[
Idx + J];
4039 if (!VJ || VJ != V0 || LJ != L0 + (
int)J) {
4050 TraversedElCountChangingBitcast =
true;
4051 Candidates.
emplace_back(NItem, &BitCast->getOperandUse(0));
4054 }
else if (SrcElts > DstElts && SrcElts % DstElts == 0) {
4057 unsigned R = SrcElts / DstElts;
4059 for (
auto [V, Lane] : Item) {
4065 for (
unsigned J = 0; J <
R; ++J)
4068 TraversedElCountChangingBitcast =
true;
4069 Candidates.
emplace_back(NItem, &BitCast->getOperandUse(0));
4075 &Sel->getOperandUse(0));
4077 &Sel->getOperandUse(1));
4079 &Sel->getOperandUse(2));
4083 !
II->hasOperandBundles()) {
4084 for (
unsigned Op = 0,
E =
II->getNumOperands() - 1;
Op <
E;
Op++) {
4088 Value *FrontV = Item.front().first;
4105 ConcatLeafs.
insert(std::make_pair(FrontV, From));
4112 if (NumVisited <= 1)
4118 if (NumVisited == 2 && TraversedElCountChangingBitcast)
4121 LLVM_DEBUG(
dbgs() <<
"Found a superfluous identity shuffle: " <<
I <<
"\n");
4128 ConcatLeafs, Builder, Worklist, &
TTI);
4129 replaceValue(
I, *V);
4136bool VectorCombine::foldShuffleFromReductions(Instruction &
I) {
4140 switch (
II->getIntrinsicID()) {
4141 case Intrinsic::vector_reduce_add:
4142 case Intrinsic::vector_reduce_mul:
4143 case Intrinsic::vector_reduce_and:
4144 case Intrinsic::vector_reduce_or:
4145 case Intrinsic::vector_reduce_xor:
4146 case Intrinsic::vector_reduce_smin:
4147 case Intrinsic::vector_reduce_smax:
4148 case Intrinsic::vector_reduce_umin:
4149 case Intrinsic::vector_reduce_umax:
4158 std::queue<Value *> Worklist;
4159 SmallPtrSet<Value *, 4> Visited;
4160 ShuffleVectorInst *Shuffle =
nullptr;
4164 while (!Worklist.empty()) {
4165 Value *CV = Worklist.front();
4177 if (CI->isBinaryOp()) {
4178 for (
auto *
Op : CI->operand_values())
4182 if (Shuffle && Shuffle != SV)
4199 for (
auto *V : Visited)
4200 for (
auto *U :
V->users())
4201 if (!Visited.contains(U) && U != &
I)
4204 FixedVectorType *VecType =
4208 FixedVectorType *ShuffleInputType =
4210 if (!ShuffleInputType)
4216 SmallVector<int> ConcatMask;
4218 sort(ConcatMask, [](
int X,
int Y) {
return (
unsigned)
X < (unsigned)
Y; });
4219 bool UsesSecondVec =
4220 any_of(ConcatMask, [&](
int M) {
return M >= (int)NumInputElts; });
4227 ShuffleInputType,
CostKind, ConcatMask);
4229 LLVM_DEBUG(
dbgs() <<
"Found a reduction feeding from a shuffle: " << *Shuffle
4231 LLVM_DEBUG(
dbgs() <<
" OldCost: " << OldCost <<
" vs NewCost: " << NewCost
4233 bool MadeChanges =
false;
4234 if (NewCost < OldCost) {
4238 LLVM_DEBUG(
dbgs() <<
"Created new shuffle: " << *NewShuffle <<
"\n");
4239 replaceValue(*Shuffle, *NewShuffle);
4245 MadeChanges |= foldSelectShuffle(*Shuffle,
true);
4266bool VectorCombine::foldShuffleChainsToReduce(Instruction &
I) {
4275 if (FVT->getNumElements() < 2)
4278 std::optional<Instruction::BinaryOps> CommonBinOp;
4279 std::optional<Intrinsic::ID> CommonCallOp;
4284 CommonBinOp = BO->getOpcode();
4286 CommonCallOp = MMI->getIntrinsicID();
4292 FastMathFlags CommonFMF;
4293 bool IsFloatReduction =
false;
4297 auto IsChainNode = [&](
Value *
V) {
4299 return CommonBinOp && BO->getOpcode() == *CommonBinOp;
4301 return CommonCallOp && MMI->getIntrinsicID() == *CommonCallOp;
4309 constexpr unsigned MaxChainNodes = 32;
4310 SmallSetVector<Value *, 16> Nodes;
4311 SmallSetVector<Value *, 4> Sources;
4312 unsigned NumVisited = 0;
4313 auto AddSource = [&](
Value *
V) {
4319 auto Walk = [&](
Value *
V,
auto &&Walk) ->
bool {
4322 if (++NumVisited > MaxChainNodes)
4324 if (!IsChainNode(V))
4325 return AddSource(V);
4330 if (!Walk(
U->getOperand(
I), Walk))
4339 return AddSource(V);
4341 if (!Walk(VecOpEE, Walk) || Nodes.
empty())
4348 for (
Value *V : Nodes) {
4354 if (!IsFloatReduction) {
4356 IsFloatReduction =
true;
4370 DenseMap<Value *, Demand> Demands;
4371 auto DemandOf = [&](
Value *
V) -> Demand & {
4373 Demand &
D = Demands[
V];
4374 if (
D.Lanes.getBitWidth() !=
N)
4378 DemandOf(VecOpEE).Lanes.setBit(0);
4380 Demand DV = Demands.
lookup(V);
4381 if (DV.Lanes.isZero())
4384 ArrayRef<int>
Mask = SVI->getShuffleMask();
4385 Demand &
DS = DemandOf(SVI->getOperand(0));
4386 for (
unsigned I = 0,
E =
Mask.size();
I !=
E; ++
I) {
4388 if (!DV.Lanes[
I] || Mask[
I] < 0 ||
4389 (
unsigned)Mask[
I] >=
DS.Lanes.getBitWidth())
4391 if (
DS.Lanes[Mask[
I]] || DV.Duplicates[
I])
4392 DS.Duplicates.setBit(Mask[
I]);
4393 DS.Lanes.setBit(Mask[
I]);
4397 for (
Value *
Op : {
U->getOperand(0),
U->getOperand(1)}) {
4398 Demand &DOp = DemandOf(
Op);
4400 DOp.Duplicates |= DV.Duplicates | (DOp.Lanes & DV.Lanes);
4401 DOp.Lanes |= DV.Lanes;
4408 auto CoversChain = [&](
Value *
V) {
4409 SmallVector<Value *, 8> Worklist(1, VecOpEE);
4410 SmallPtrSet<Value *, 8> Seen;
4412 while (!Worklist.empty()) {
4415 for (
unsigned I = 0;
I !=
NumOps; ++
I) {
4419 if (!Nodes.contains(
Op))
4421 Worklist.push_back(
Op);
4429 struct ReductionCut {
4433 std::optional<ReductionCut> Cut;
4434 for (
Value *S : Sources) {
4435 auto It = Demands.
find(S);
4436 if (It == Demands.
end() || It->second.Lanes.isZero())
4438 if (!IsIdempotent && !It->second.Duplicates.isZero()) {
4443 Cut = ReductionCut{S, It->second.Lanes};
4450 if (!IsIdempotent && !(Cut->Elts & It->second.Lanes).isZero()) {
4454 Cut->Elts |= It->second.Lanes;
4457 for (
Value *V : Nodes) {
4460 auto It = Demands.
find(V);
4461 if (It == Demands.
end() || !It->second.Lanes.isAllOnes())
4463 if (!IsIdempotent && !It->second.Duplicates.isZero())
4465 if (!CoversChain(V))
4467 Cut = ReductionCut{
V, It->second.Lanes};
4472 if (!Cut || Cut->Elts.popcount() < 2)
4482 for (
Value *V : Nodes)
4486 bool IsPartialReduction = !Cut->Elts.isAllOnes();
4487 FixedVectorType *ReduceVecTy =
4492 SmallVector<int> ExtractMask;
4494 if (IsPartialReduction) {
4495 for (
unsigned I = 0,
E = Cut->Elts.getBitWidth();
I !=
E; ++
I)
4497 ExtractMask.push_back(
I);
4498 unsigned SubIdx = 0, SubLen;
4499 auto SK = Cut->Elts.isShiftedMask(SubIdx, SubLen)
4503 SubIdx, ReduceVecTy);
4506 IntrinsicCostAttributes ICA(
4507 ReducedOp, ReduceVecTy->getElementType(),
4511 IsFloatReduction ? CommonFMF : FastMathFlags());
4514 LLVM_DEBUG(
dbgs() <<
"Found reduction shuffle chain: " <<
I <<
"\n OldCost : "
4515 << OrigCost <<
" vs NewCost: " << NewCost <<
"\n");
4520 if (VecOpEE->
hasOneUse() ? (NewCost > OrigCost) : (NewCost >= OrigCost))
4523 Value *ReduceInput = Cut->Src;
4524 if (IsPartialReduction)
4527 Value *ReducedResult;
4528 if (IsFloatReduction) {
4530 *CommonBinOp, ReduceVecTy->getElementType(),
false,
4533 {Identity, ReduceInput}, CommonFMF);
4538 replaceValue(
I, *ReducedResult);
4547bool VectorCombine::foldCastFromReductions(Instruction &
I) {
4552 bool TruncOnly =
false;
4555 case Intrinsic::vector_reduce_add:
4556 case Intrinsic::vector_reduce_mul:
4559 case Intrinsic::vector_reduce_and:
4560 case Intrinsic::vector_reduce_or:
4561 case Intrinsic::vector_reduce_xor:
4568 Value *ReductionSrc =
I.getOperand(0);
4580 Type *ResultTy =
I.getType();
4583 ReductionOpc, ReductionSrcTy, std::nullopt,
CostKind);
4593 if (OldCost <= NewCost || !NewCost.
isValid())
4597 II->getIntrinsicID(), {Src});
4599 replaceValue(
I, *NewCast);
4627bool VectorCombine::foldSignBitReductionCmp(Instruction &
I) {
4629 IntrinsicInst *ReduceOp;
4630 const APInt *CmpVal;
4637 case Intrinsic::vector_reduce_or:
4638 case Intrinsic::vector_reduce_umax:
4639 case Intrinsic::vector_reduce_and:
4640 case Intrinsic::vector_reduce_umin:
4641 case Intrinsic::vector_reduce_add:
4652 unsigned BitWidth = VecTy->getScalarSizeInBits();
4656 unsigned NumElts = VecTy->getNumElements();
4665 case Intrinsic::vector_reduce_or:
4666 case Intrinsic::vector_reduce_umax:
4667 TreeOpcode = Instruction::Or;
4669 case Intrinsic::vector_reduce_and:
4670 case Intrinsic::vector_reduce_umin:
4671 TreeOpcode = Instruction::And;
4673 case Intrinsic::vector_reduce_add:
4674 TreeOpcode = Instruction::Add;
4682 SmallVector<Value *, 8> Worklist;
4683 SmallVector<Value *, 8> Sources;
4685 std::optional<bool> IsAShr;
4686 constexpr unsigned MaxSources = 8;
4691 while (!Worklist.
empty() && Worklist.
size() <= MaxSources &&
4692 Sources.
size() <= MaxSources) {
4701 bool ThisIsAShr = Shr->getOpcode() == Instruction::AShr;
4703 IsAShr = ThisIsAShr;
4704 else if (*IsAShr != ThisIsAShr)
4730 if (Sources.
empty() || Sources.
size() > MaxSources ||
4731 Worklist.
size() > MaxSources || !IsAShr)
4734 unsigned NumSources = Sources.
size();
4738 if (OrigIID == Intrinsic::vector_reduce_add &&
4746 (OrigIID == Intrinsic::vector_reduce_add) ? NumSources * NumElts : 1;
4749 NegativeVal.negate();
4781 TestsNegative =
false;
4782 }
else if (*CmpVal == NegativeVal) {
4783 TestsNegative =
true;
4787 IsEq = Pred == ICmpInst::ICMP_EQ;
4788 }
else if (Pred == ICmpInst::ICMP_SLT && *CmpVal == RangeHigh) {
4790 TestsNegative = (RangeHigh == NegativeVal);
4791 }
else if (Pred == ICmpInst::ICMP_SGT && *CmpVal == RangeHigh - 1) {
4793 TestsNegative = (RangeHigh == NegativeVal);
4794 }
else if (Pred == ICmpInst::ICMP_SGT && *CmpVal == RangeLow) {
4796 TestsNegative = (RangeLow == NegativeVal);
4797 }
else if (Pred == ICmpInst::ICMP_SLT && *CmpVal == RangeLow + 1) {
4799 TestsNegative = (RangeLow == NegativeVal);
4842 enum CheckKind :
unsigned {
4849 auto RequiresOr = [](CheckKind
C) ->
bool {
return C & 0b100; };
4851 auto IsNegativeCheck = [](CheckKind
C) ->
bool {
return C & 0b010; };
4853 auto Invert = [](CheckKind
C) {
return CheckKind(
C ^ 0b011); };
4857 case Intrinsic::vector_reduce_or:
4858 case Intrinsic::vector_reduce_umax:
4859 Base = TestsNegative ? AnyNeg : AllNonNeg;
4861 case Intrinsic::vector_reduce_and:
4862 case Intrinsic::vector_reduce_umin:
4863 Base = TestsNegative ? AllNeg : AnyNonNeg;
4865 case Intrinsic::vector_reduce_add:
4866 Base = TestsNegative ? AllNeg : AllNonNeg;
4881 return ArithCost <= MinMaxCost ? std::make_pair(Arith, ArithCost)
4882 : std::make_pair(MinMax, MinMaxCost);
4886 auto [NewIID, NewCost] = RequiresOr(
Check)
4887 ? PickCheaper(Intrinsic::vector_reduce_or,
4888 Intrinsic::vector_reduce_umax)
4889 : PickCheaper(
Intrinsic::vector_reduce_and,
4893 if (NumSources > 1) {
4894 unsigned CombineOpc =
4895 RequiresOr(
Check) ? Instruction::Or : Instruction::And;
4900 LLVM_DEBUG(
dbgs() <<
"Found sign-bit reduction cmp: " <<
I <<
"\n OldCost: "
4901 << OldCost <<
" vs NewCost: " << NewCost <<
"\n");
4903 if (NewCost > OldCost)
4908 Type *ScalarTy = VecTy->getScalarType();
4911 if (NumSources == 1) {
4922 replaceValue(
I, *NewCmp);
4953bool VectorCombine::foldReductionZeroTest(Instruction &
I) {
4962 if (!
II || !
II->hasOneUse())
4965 auto ReduceID =
II->getIntrinsicID();
4966 if (ReduceID != Intrinsic::vector_reduce_or &&
4967 ReduceID != Intrinsic::vector_reduce_umax)
4970 Value *Vec =
II->getArgOperand(0);
4972 if (!VecTy || !VecTy->getElementType()->isIntegerTy())
4977 ? Intrinsic::vector_reduce_or
4992 LLVM_DEBUG(
dbgs() <<
"Found a reduction zero test: " <<
I <<
"\n OldCost: "
4993 << OldCost <<
" vs NewCost: " << NewCost <<
"\n");
4995 if (!OldCost.
isValid() || !NewCost.
isValid() || NewCost > OldCost)
5001 replaceValue(
I, *NewReduce);
5026bool VectorCombine::foldICmpEqZeroVectorReduce(Instruction &
I) {
5037 switch (
II->getIntrinsicID()) {
5038 case Intrinsic::vector_reduce_add:
5039 case Intrinsic::vector_reduce_or:
5040 case Intrinsic::vector_reduce_umin:
5041 case Intrinsic::vector_reduce_umax:
5042 case Intrinsic::vector_reduce_smin:
5043 case Intrinsic::vector_reduce_smax:
5049 Value *InnerOp =
II->getArgOperand(0);
5092 switch (
II->getIntrinsicID()) {
5093 case Intrinsic::vector_reduce_add: {
5098 unsigned NumElems = XTy->getNumElements();
5104 if (LeadingZerosX <= LostBits || LeadingZerosFX <= LostBits)
5112 case Intrinsic::vector_reduce_smin:
5113 case Intrinsic::vector_reduce_smax:
5123 LLVM_DEBUG(
dbgs() <<
"Found a reduction to 0 comparison with removable op: "
5139 case Intrinsic::vector_reduce_add:
5140 case Intrinsic::vector_reduce_or:
5146 case Intrinsic::vector_reduce_umin:
5147 case Intrinsic::vector_reduce_umax:
5148 case Intrinsic::vector_reduce_smin:
5149 case Intrinsic::vector_reduce_smax:
5161 NewReduceCost + (InnerOp->
hasOneUse() ? 0 : ExtCost);
5163 LLVM_DEBUG(
dbgs() <<
"Found a removable extension before reduction: "
5164 << *InnerOp <<
"\n OldCost: " << OldCost
5165 <<
" vs NewCost: " << NewCost <<
"\n");
5171 if (NewCost > OldCost)
5180 Builder.
CreateICmp(Pred, NewReduce, ConstantInt::getNullValue(Ty));
5181 replaceValue(
I, *NewCmp);
5212bool VectorCombine::foldEquivalentReductionCmp(Instruction &
I) {
5215 const APInt *CmpVal;
5220 if (!
II || !
II->hasOneUse())
5223 const auto IsValidOrUmaxCmp = [&]() {
5232 bool IsPositive = CmpVal->
isAllOnes() && Pred == ICmpInst::ICMP_SGT;
5234 bool IsNegative = (CmpVal->
isZero() || CmpVal->
isOne() || *CmpVal == 2) &&
5235 Pred == ICmpInst::ICMP_SLT;
5236 return IsEquality || IsPositive || IsNegative;
5239 const auto IsValidAndUminCmp = [&]() {
5244 const auto LeadingOnes = CmpVal->
countl_one();
5251 bool IsNegative = CmpVal->
isZero() && Pred == ICmpInst::ICMP_SLT;
5260 ((*CmpVal)[0] || (*CmpVal)[1]) && Pred == ICmpInst::ICMP_SGT;
5261 return IsEquality || IsNegative || IsPositive;
5269 switch (OriginalIID) {
5270 case Intrinsic::vector_reduce_or:
5271 if (!IsValidOrUmaxCmp())
5273 AlternativeIID = Intrinsic::vector_reduce_umax;
5275 case Intrinsic::vector_reduce_umax:
5276 if (!IsValidOrUmaxCmp())
5278 AlternativeIID = Intrinsic::vector_reduce_or;
5280 case Intrinsic::vector_reduce_and:
5281 if (!IsValidAndUminCmp())
5283 AlternativeIID = Intrinsic::vector_reduce_umin;
5285 case Intrinsic::vector_reduce_umin:
5286 if (!IsValidAndUminCmp())
5288 AlternativeIID = Intrinsic::vector_reduce_and;
5301 if (ReductionOpc != Instruction::ICmp)
5312 <<
"\n OrigCost: " << OrigCost
5313 <<
" vs AltCost: " << AltCost <<
"\n");
5315 if (AltCost >= OrigCost)
5319 Type *ScalarTy = VecTy->getScalarType();
5322 Builder.
CreateICmp(Pred, NewReduce, ConstantInt::get(ScalarTy, *CmpVal));
5324 replaceValue(
I, *NewCmp);
5338 unsigned Depth = 0) {
5339 constexpr unsigned MaxLocalDepth = 2;
5340 if (
Depth > MaxLocalDepth)
5343 auto NumSignBits = [&](
const Value *
X) {
5346 if (NumSignBits(V) == V->getType()->getScalarSizeInBits())
5351 return NumSignBits(
A) >= 2 && NumSignBits(
B) >= 2 &&
5362bool VectorCombine::foldReduceAddCmpZero(Instruction &
I) {
5372 if (!VecTy || VecTy->getNumElements() < 2)
5378 if (!IsNonNegative && !IsNonPositive)
5383 unsigned NumElts = VecTy->getNumElements();
5385 if (
Log2_32(NumElts) >= NumSignBits)
5388 ICmpInst::Predicate NewPred;
5390 case ICmpInst::ICMP_EQ:
5391 case ICmpInst::ICMP_ULE:
5392 case ICmpInst::ICMP_SLE:
5393 case ICmpInst::ICMP_SGE:
5394 NewPred = ICmpInst::ICMP_EQ;
5396 case ICmpInst::ICMP_NE:
5397 case ICmpInst::ICMP_UGT:
5398 case ICmpInst::ICMP_SGT:
5399 case ICmpInst::ICMP_SLT:
5400 NewPred = ICmpInst::ICMP_NE;
5410 if (!IsNonNegative &&
5411 (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLE))
5413 if (!IsNonPositive &&
5414 (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGE))
5416 if ((Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLE ||
5417 Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGE) &&
5418 Log2_32(NumElts) >= NumSignBits - 1)
5422 Instruction::Add, VecTy, std::nullopt,
CostKind);
5424 Instruction::Or, VecTy, std::nullopt,
CostKind);
5426 Intrinsic::umax, VecTy, FastMathFlags(),
CostKind);
5429 bool UseOr = OrCost.
isValid() && (!UmaxCost.
isValid() || OrCost <= UmaxCost);
5431 if (AltCost > OrigCost)
5437 Intrinsic::vector_reduce_umax, {VecTy}, {Vec});
5438 Worklist.pushValue(NewReduce);
5440 NewPred, NewReduce, ConstantInt::getNullValue(VecTy->getScalarType()));
5441 replaceValue(
I, *NewCmp);
5450 constexpr unsigned MaxVisited = 32;
5453 bool FoundReduction =
false;
5456 while (!WorkList.
empty()) {
5458 for (
User *U :
I->users()) {
5460 if (!UI || !Visited.
insert(UI).second)
5462 if (Visited.
size() > MaxVisited)
5468 switch (
II->getIntrinsicID()) {
5469 case Intrinsic::vector_reduce_add:
5470 case Intrinsic::vector_reduce_mul:
5471 case Intrinsic::vector_reduce_and:
5472 case Intrinsic::vector_reduce_or:
5473 case Intrinsic::vector_reduce_xor:
5474 case Intrinsic::vector_reduce_smin:
5475 case Intrinsic::vector_reduce_smax:
5476 case Intrinsic::vector_reduce_umin:
5477 case Intrinsic::vector_reduce_umax:
5478 FoundReduction =
true;
5491 return FoundReduction;
5504bool VectorCombine::foldSelectShuffle(Instruction &
I,
bool FromReduction) {
5509 if (!Op0 || !Op1 || Op0 == Op1 || !Op0->isBinaryOp() || !Op1->isBinaryOp() ||
5510 VT != Op0->getType())
5517 SmallPtrSet<Instruction *, 4> InputShuffles({SVI0A, SVI0B, SVI1A, SVI1B});
5519 if (!
I ||
I->getOperand(0)->getType() != VT)
5521 return any_of(
I->users(), [&](User *U) {
5522 return U != Op0 && U != Op1 &&
5523 !(isa<ShuffleVectorInst>(U) &&
5524 (InputShuffles.contains(cast<Instruction>(U)) ||
5525 isInstructionTriviallyDead(cast<Instruction>(U))));
5528 if (checkSVNonOpUses(SVI0A) || checkSVNonOpUses(SVI0B) ||
5529 checkSVNonOpUses(SVI1A) || checkSVNonOpUses(SVI1B))
5537 for (
auto *U :
I->users()) {
5539 if (!SV ||
SV->getType() != VT)
5541 if ((
SV->getOperand(0) != Op0 &&
SV->getOperand(0) != Op1) ||
5542 (
SV->getOperand(1) != Op0 &&
SV->getOperand(1) != Op1))
5549 if (!collectShuffles(Op0) || !collectShuffles(Op1))
5553 if (FromReduction && Shuffles.
size() > 1)
5558 if (!FromReduction) {
5559 for (
size_t Idx = 0,
E = Shuffles.
size(); Idx !=
E; ++Idx) {
5560 for (
auto *U : Shuffles[Idx]->
users()) {
5575 int MaxV1Elt = 0, MaxV2Elt = 0;
5576 unsigned NumElts = VT->getNumElements();
5577 for (ShuffleVectorInst *SVN : Shuffles) {
5578 SmallVector<int>
Mask;
5579 SVN->getShuffleMask(Mask);
5583 Value *SVOp0 = SVN->getOperand(0);
5584 Value *SVOp1 = SVN->getOperand(1);
5589 for (
int &Elem : Mask) {
5595 if (SVOp0 == Op1 && SVOp1 == Op0) {
5599 if (SVOp0 != Op0 || SVOp1 != Op1)
5605 SmallVector<int> ReconstructMask;
5606 for (
unsigned I = 0;
I <
Mask.size();
I++) {
5609 }
else if (Mask[
I] <
static_cast<int>(NumElts)) {
5610 MaxV1Elt = std::max(MaxV1Elt, Mask[
I]);
5611 auto It =
find_if(
V1, [&](
const std::pair<int, int> &
A) {
5612 return Mask[
I] ==
A.first;
5618 V1.emplace_back(Mask[
I],
V1.size());
5621 MaxV2Elt = std::max<int>(MaxV2Elt, Mask[
I] - NumElts);
5622 auto It =
find_if(V2, [&](
const std::pair<int, int> &
A) {
5623 return Mask[
I] -
static_cast<int>(NumElts) ==
A.first;
5637 sort(ReconstructMask);
5638 OrigReconstructMasks.
push_back(std::move(ReconstructMask));
5645 if (
V1.empty() || V2.
empty() ||
5646 (MaxV1Elt ==
static_cast<int>(
V1.size()) - 1 &&
5647 MaxV2Elt ==
static_cast<int>(V2.
size()) - 1))
5659 if (InputShuffles.contains(SSV))
5661 return SV->getMaskValue(M);
5669 std::pair<int, int>
Y) {
5670 int MXA = GetBaseMaskValue(
A,
X.first);
5671 int MYA = GetBaseMaskValue(
A,
Y.first);
5675 return SortBase(SVI0A,
A,
B);
5677 stable_sort(V2, [&](std::pair<int, int>
A, std::pair<int, int>
B) {
5678 return SortBase(SVI1A,
A,
B);
5683 for (
const auto &Mask : OrigReconstructMasks) {
5684 SmallVector<int> ReconstructMask;
5685 for (
int M : Mask) {
5687 auto It =
find_if(V, [M](
auto A) {
return A.second ==
M; });
5688 assert(It !=
V.end() &&
"Expected all entries in Mask");
5689 return std::distance(
V.begin(), It);
5693 else if (M <
static_cast<int>(NumElts)) {
5696 ReconstructMask.
push_back(NumElts + FindIndex(V2, M));
5699 ReconstructMasks.
push_back(std::move(ReconstructMask));
5704 SmallVector<int> V1A, V1B, V2A, V2B;
5705 for (
unsigned I = 0;
I <
V1.size();
I++) {
5709 for (
unsigned I = 0;
I < V2.
size();
I++) {
5710 V2A.
push_back(GetBaseMaskValue(SVI1A, V2[
I].first));
5711 V2B.
push_back(GetBaseMaskValue(SVI1B, V2[
I].first));
5713 while (V1A.
size() < NumElts) {
5717 while (V2A.
size() < NumElts) {
5736 unsigned ElementSize = VT->getElementType()->getPrimitiveSizeInBits();
5737 unsigned MaxVectorSize =
5739 unsigned MaxElementsInVector = MaxVectorSize / ElementSize;
5740 if (MaxElementsInVector == 0)
5749 std::set<SmallVector<int, 4>> UniqueShuffles;
5754 unsigned NumFullVectors =
Mask.size() / MaxElementsInVector;
5755 if (NumFullVectors < 2)
5756 return C + ShuffleCost;
5757 SmallVector<int, 4> SubShuffle(MaxElementsInVector);
5758 unsigned NumUniqueGroups = 0;
5759 unsigned NumGroups =
Mask.size() / MaxElementsInVector;
5762 for (
unsigned I = 0;
I < NumFullVectors; ++
I) {
5763 for (
unsigned J = 0; J < MaxElementsInVector; ++J)
5764 SubShuffle[J] = Mask[MaxElementsInVector *
I + J];
5765 if (UniqueShuffles.insert(SubShuffle).second)
5766 NumUniqueGroups += 1;
5768 return C + ShuffleCost * NumUniqueGroups / NumGroups;
5774 SmallVector<int, 16>
Mask;
5775 SV->getShuffleMask(Mask);
5776 return AddShuffleMaskAdjustedCost(
C, Mask);
5779 auto AllShufflesHaveSameOperands =
5780 [](SmallPtrSetImpl<Instruction *> &InputShuffles) {
5781 if (InputShuffles.size() < 2)
5783 ShuffleVectorInst *FirstSV =
5790 std::next(InputShuffles.begin()), InputShuffles.end(),
5791 [&](Instruction *
I) {
5792 ShuffleVectorInst *SV = dyn_cast<ShuffleVectorInst>(I);
5793 return SV && SV->getOperand(0) == In0 && SV->getOperand(1) == In1;
5802 CostBefore += std::accumulate(Shuffles.begin(), Shuffles.end(),
5804 if (AllShufflesHaveSameOperands(InputShuffles)) {
5805 UniqueShuffles.clear();
5806 CostBefore += std::accumulate(InputShuffles.begin(), InputShuffles.end(),
5809 CostBefore += std::accumulate(InputShuffles.begin(), InputShuffles.end(),
5815 FixedVectorType *Op0SmallVT =
5817 FixedVectorType *Op1SmallVT =
5822 UniqueShuffles.clear();
5823 CostAfter += std::accumulate(ReconstructMasks.begin(), ReconstructMasks.end(),
5825 std::set<SmallVector<int>> OutputShuffleMasks({V1A, V1B, V2A, V2B});
5827 std::accumulate(OutputShuffleMasks.begin(), OutputShuffleMasks.end(),
5830 LLVM_DEBUG(
dbgs() <<
"Found a binop select shuffle pattern: " <<
I <<
"\n");
5832 <<
" vs CostAfter: " << CostAfter <<
"\n");
5833 if (CostBefore < CostAfter ||
5844 if (InputShuffles.contains(SSV))
5846 return SV->getOperand(
Op);
5850 GetShuffleOperand(SVI0A, 1), V1A);
5853 GetShuffleOperand(SVI0B, 1), V1B);
5856 GetShuffleOperand(SVI1A, 1), V2A);
5859 GetShuffleOperand(SVI1B, 1), V2B);
5864 I->copyIRFlags(Op0,
true);
5869 I->copyIRFlags(Op1,
true);
5871 for (
int S = 0,
E = ReconstructMasks.size(); S !=
E; S++) {
5874 replaceValue(*Shuffles[S], *NSV,
false);
5877 Worklist.pushValue(NSV0A);
5878 Worklist.pushValue(NSV0B);
5879 Worklist.pushValue(NSV1A);
5880 Worklist.pushValue(NSV1B);
5890bool VectorCombine::shrinkType(Instruction &
I) {
5891 Value *ZExted, *OtherOperand;
5897 Value *ZExtOperand =
I.getOperand(
I.getOperand(0) == OtherOperand ? 1 : 0);
5901 unsigned BW = SmallTy->getElementType()->getPrimitiveSizeInBits();
5903 if (
I.getOpcode() == Instruction::LShr) {
5920 Instruction::ZExt, BigTy, SmallTy,
5921 TargetTransformInfo::CastContextHint::None,
CostKind);
5926 for (User *U : ZExtOperand->
users()) {
5933 ShrinkCost += ZExtCost;
5948 ShrinkCost += ZExtCost;
5955 Instruction::Trunc, SmallTy, BigTy,
5956 TargetTransformInfo::CastContextHint::None,
CostKind);
5961 if (ShrinkCost > CurrentCost)
5965 Value *Op0 = ZExted;
5968 if (
I.getOperand(0) == OtherOperand)
5973 NewBinOpI->copyIRFlags(&
I);
5974 NewBinOpI->copyMetadata(
I);
5977 replaceValue(
I, *NewZExtr);
5983bool VectorCombine::foldInsExtVectorToShuffle(Instruction &
I) {
5984 Value *DstVec, *SrcVec;
5995 if (!DstVecTy || !SrcVecTy ||
6001 if (InsIdx >= NumDstElts || ExtIdx >= NumSrcElts || NumDstElts == 1)
6008 bool NeedExpOrNarrow = NumSrcElts != NumDstElts;
6010 if (NeedDstSrcSwap) {
6012 Mask[InsIdx] = ExtIdx % NumDstElts;
6016 std::iota(
Mask.begin(),
Mask.end(), 0);
6017 Mask[InsIdx] = (ExtIdx % NumDstElts) + NumDstElts;
6030 SmallVector<int> ExtToVecMask;
6031 if (!NeedExpOrNarrow) {
6036 nullptr, {DstVec, SrcVec});
6042 ExtToVecMask[ExtIdx % NumDstElts] = ExtIdx;
6045 DstVecTy, SrcVecTy,
CostKind, ExtToVecMask);
6049 if (!Ext->hasOneUse())
6052 LLVM_DEBUG(
dbgs() <<
"Found a insert/extract shuffle-like pair: " <<
I
6053 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
6056 if (OldCost < NewCost)
6059 if (NeedExpOrNarrow) {
6060 if (!NeedDstSrcSwap)
6073 replaceValue(
I, *Shuf);
6082bool VectorCombine::foldInsertScalarPartsToShuffle(Instruction &
I) {
6091 Type *EltTy = VecTy->getElementType();
6093 !
DL->typeSizeEqualsStoreSize(EltTy))
6096 unsigned NumElts = VecTy->getNumElements();
6098 Value *Src =
nullptr;
6099 unsigned NumSrcElts = 0;
6105 if (Ins != &
I && !Ins->hasOneUse())
6110 Vec = Ins->getOperand(0);
6112 if (DemandedElts[Idx])
6114 DemandedElts.
setBit(Idx);
6118 Value *Elt = Ins->getOperand(1);
6125 Value *Shift =
nullptr;
6133 unsigned SrcBits =
X->getType()->getIntegerBitWidth();
6134 if (SrcBits % EltBits)
6137 NumSrcElts = SrcBits / EltBits;
6138 }
else if (
X != Src) {
6142 if (ShAmt % EltBits || Part >= NumSrcElts)
6144 Mask[
Idx] =
DL->isBigEndian() ? NumSrcElts - 1 - Part : Part;
6147 for (
Value *V : {Elt == Trunc ? nullptr : Elt, Trunc, Shift}) {
6150 if (!
V->hasOneUse())
6172 bool IsIdentity = NumSrcElts == NumElts &&
6178 LLVM_DEBUG(
dbgs() <<
"Found an insertelement chain of scalar parts: " <<
I
6179 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
6181 if (!OldCost.
isValid() || !NewCost.
isValid() || NewCost >= OldCost)
6186 replaceValue(
I, *Shuf);
6193 return CB->arg_size();
6205 if (
II->hasOperandBundles() ||
6218 OperandTy->getElementCount() != ResultTy->getElementCount())
6227 auto GetSplatOrScalar = [](
Value *V) {
6231 Value *CommonValue = GetSplatOrScalar(
Values.front());
6235 if (GetSplatOrScalar(V) != CommonValue)
6244 for (
const auto &[Index, Member] :
enumerate(Members)) {
6246 if (!Extract || Extract->getNumIndices() != 1 ||
6247 *Extract->idx_begin() != Index)
6255 unsigned Factor = Members.
size();
6266 unsigned OperandIndex) {
6268 for (
Value *Member : Members)
6276 unsigned &NumScanned) {
6277 unsigned Factor = Members.
size();
6282 NumScanned += Factor;
6286 !FirstInst->getSingleUndroppableUse())
6291 if (!Inst || !Inst->getSingleUndroppableUse() ||
6312 return Builder.CreateNAryOp(NarrowInst->
getOpcode(), NewOperands);
6314 return Builder.CreateCast(Cast->getOpcode(), NewOperands[0], WideResultTy);
6316 return Builder.CreateCmp(Cmp->getPredicate(), NewOperands[0],
6319 return Builder.CreateSelect(
6320 NewOperands[0], NewOperands[1], NewOperands[2],
"",
6323 return Builder.CreateFreeze(NewOperands[0]);
6325 return Builder.CreateIntrinsic(WideResultTy,
II->getIntrinsicID(),
6336 "deinterleave source must have the interleaved element count");
6343 NewOperands.
reserve(NumOperands);
6344 for (
unsigned Op = 0;
Op != NumOperands; ++
Op) {
6346 Value *NewOperand =
nullptr;
6349 Builder.SetCurrentDebugLocation(NarrowInst->getDebugLoc());
6350 NewOperand = Builder.CreateVectorSplat(WideEC, NewOperand);
6360 Builder.SetCurrentDebugLocation(NarrowInst->getDebugLoc());
6361 auto *WideResultTy =
6408bool VectorCombine::foldInterleaveOfDeinterleaveChains(Instruction &
I) {
6414 if (!Factor || Interleave->hasOperandBundles())
6417 SmallVector<Value *, 8> RootMembers(Interleave->args());
6418 unsigned NumScanned = 0;
6426 replaceValue(*Interleave, *WideValue);
6434bool VectorCombine::foldInterleaveIntrinsics(Instruction &
I) {
6435 if (foldInterleaveOfDeinterleaveChains(
I))
6438 const APInt *SplatVal0, *SplatVal1;
6448 auto *ExtVTy = VectorType::getExtendedElementVectorType(VTy);
6449 unsigned Width = VTy->getElementType()->getIntegerBitWidth();
6458 LLVM_DEBUG(
dbgs() <<
"VC: The cost to cast from " << *ExtVTy <<
" to "
6459 << *
I.getType() <<
" is too high.\n");
6463 APInt NewSplatVal = SplatVal1->
zext(Width * 2);
6464 NewSplatVal <<= Width;
6465 NewSplatVal |= SplatVal0->
zext(Width * 2);
6467 ExtVTy->getElementCount(), ConstantInt::get(
F.getContext(), NewSplatVal));
6502bool VectorCombine::foldDeinterleaveIntrinsics(Instruction &
I) {
6504 if (
DL->isBigEndian())
6507 using namespace PatternMatch;
6508 Value *DeinterleavedVal;
6519 unsigned HalfElementWidth = ElementWidth / 2;
6523 std::array<ExtractValueInst *, 2> OrigFields{};
6524 for (User *Usr :
I.users()) {
6527 if (!
E ||
E->getNumIndices() != 1)
6529 unsigned Idx = *
E->idx_begin();
6531 if (Idx >= 2 || OrigFields[Idx] || !
E->hasNUses(2))
6533 OrigFields[
Idx] =
E;
6537 SmallVector<Instruction *, 2> MergeInsts;
6538 for (
auto *FieldUsr : OrigFields[0]->
users()) {
6546 auto MatchMerge = [&](void) ->
bool {
6549 return match(MergeInsts[0],
6553 match(MergeInsts[1],
6558 if (!MatchMerge()) {
6559 std::swap(MergeInsts[0], MergeInsts[1]);
6574 auto *NewFieldTy = VecTy->getWithNewBitWidth(HalfElementWidth);
6584 if (OldCost <= NewCost || !NewCost.
isValid()) {
6586 dbgs() <<
"VC: New deinterleave2 sequence cost (" << NewCost <<
")"
6587 <<
" is higher than that of the old one (" << OldCost <<
")\n");
6595 Intrinsic::vector_deinterleave2, {NewVecTy}, {NewVecCast});
6596 Worklist.pushValue(NewVecCast);
6597 Worklist.pushValue(NewDeinterleave);
6598 for (
auto [Idx, MergeInst] :
enumerate(MergeInsts)) {
6600 Worklist.pushValue(NewField);
6601 NewField = Builder.
CreateBitCast(NewField, MergeInst->getType());
6602 replaceValue(*MergeInst, *NewField);
6608bool VectorCombine::foldBitcastOfVPLoad(Instruction &
I) {
6609 const DataLayout &
DL =
I.getDataLayout();
6624 DL.getValueOrABITypeAlignment(
II->getPointerAlignment(), OrigVecTy);
6625 ElementCount OrigVecCnt = OrigVecTy->getElementCount();
6627 ElementCount NewVecCnt = NewVecTy->getElementCount();
6639 II->getMemoryPointerParam(),
false,
6645 {Intrinsic::vp_load, NewVecTy,
II->getMemoryPointerParam(),
false,
6649 <<
" NewCost=" << NewCost <<
"\n");
6650 if (NewCost > OldCost || !NewCost.
isValid())
6658 NewVecTy, Intrinsic::vp_load,
6659 {
II->getMemoryPointerParam(), NewMask, NewEVL});
6662 0, AttrBuilder(
II->getContext()).addAlignmentAttr(OrigAlign));
6663 replaceValue(*Cast, *NewVP);
6673bool VectorCombine::foldBitOrderReverseAndSwap(Instruction &
I) {
6677 Type *Ty =
X->getType();
6678 Type *VecTy =
I.getOperand(0)->getType();
6692 if (CanUseBswap || CanUseFshl) {
6703 IntrinsicCostAttributes ICABSwap(Intrinsic::bswap, Ty, {Ty});
6704 IntrinsicCostAttributes ICABFshl(Intrinsic::fshl, Ty, {
X,
X, HalfBW},
6706 IntrinsicCostAttributes ICABRev(Intrinsic::bitreverse, Ty, {Ty});
6711 if (!InnerCall->hasOneUse())
6714 else if (!InnerBitCast->hasOneUse())
6717 <<
"\n OldCost: " << OldCost
6718 <<
" vs NewCost: " << NewCost <<
"\n");
6719 if (NewCost.isValid() && NewCost < OldCost) {
6725 Worklist.pushValue(
Swap);
6727 replaceValue(
I, *BRev);
6736 Type *Ty =
I.getType();
6738 TypeSize ElementSize =
DL->getTypeStoreSize(Ty);
6741 Type *NewVecTy = VectorType::get(I8Ty, NewVecCnt);
6754 IntrinsicCostAttributes ICANew(Intrinsic::bitreverse, NewVecTy, {NewVecTy});
6757 InstructionCost NewCost = CastToVecCost + NewIntrinsicCost + CastToOrigCost;
6758 if (!InnerII->hasOneUse())
6761 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
6763 if (!NewCost.
isValid() || NewCost >= OldCost)
6771 replaceValue(
I, *CastToOrig);
6781 unsigned RawNumElements = MaxIdx + 1u;
6785 return RawNumElements;
6789 return RawNumElements;
6794 return RawNumElements;
6799 if (ElemsPerReg == 0 || RawNumElements <= ElemsPerReg)
6800 return RawNumElements;
6802 return alignTo(RawNumElements, ElemsPerReg);
6806bool VectorCombine::shrinkLoadForShuffles(Instruction &
I) {
6808 if (!OldLoad || !OldLoad->isSimple())
6815 unsigned const OldNumElements = OldLoadTy->getNumElements();
6821 using IndexRange = std::pair<int, int>;
6822 auto GetIndexRangeInShuffles = [&]() -> std::optional<IndexRange> {
6823 IndexRange OutputRange = IndexRange(OldNumElements, -1);
6824 for (llvm::Use &Use :
I.uses()) {
6826 User *Shuffle =
Use.getUser();
6831 return std::nullopt;
6838 for (
int Index : Mask) {
6839 if (Index >= 0 && Index <
static_cast<int>(OldNumElements)) {
6840 OutputRange.first = std::min(Index, OutputRange.first);
6841 OutputRange.second = std::max(Index, OutputRange.second);
6846 if (OutputRange.second < OutputRange.first)
6847 return std::nullopt;
6853 if (std::optional<IndexRange> Indices = GetIndexRangeInShuffles()) {
6854 unsigned const NewNumElements =
6859 if (NewNumElements < OldNumElements) {
6864 Type *ElemTy = OldLoadTy->getElementType();
6866 Value *PtrOp = OldLoad->getPointerOperand();
6869 Instruction::Load, OldLoad->getType(), OldLoad->getAlign(),
6870 OldLoad->getPointerAddressSpace(),
CostKind);
6873 OldLoad->getPointerAddressSpace(),
CostKind);
6875 using UseEntry = std::pair<ShuffleVectorInst *, std::vector<int>>;
6877 unsigned const MaxIndex = NewNumElements * 2u;
6879 for (llvm::Use &Use :
I.uses()) {
6886 ArrayRef<int> OldMask = Shuffle->getShuffleMask();
6892 for (
int Index : OldMask) {
6893 if (Index >=
static_cast<int>(MaxIndex))
6907 dbgs() <<
"Found a load used only by shufflevector instructions: "
6908 <<
I <<
"\n OldCost: " << OldCost
6909 <<
" vs NewCost: " << NewCost <<
"\n");
6911 if (OldCost < NewCost || !NewCost.
isValid())
6917 NewLoad->copyMetadata(
I);
6920 for (UseEntry &Use : NewUses) {
6921 ShuffleVectorInst *Shuffle =
Use.first;
6922 std::vector<int> &NewMask =
Use.second;
6929 replaceValue(*Shuffle, *NewShuffle,
false);
6942bool VectorCombine::shrinkPhiOfShuffles(Instruction &
I) {
6944 if (!Phi ||
Phi->getNumIncomingValues() != 2u)
6948 ArrayRef<int> Mask0;
6949 ArrayRef<int> Mask1;
6962 auto const InputNumElements = InputVT->getNumElements();
6964 if (InputNumElements >= ResultVT->getNumElements())
6969 SmallVector<int, 16> NewMask;
6972 for (
auto [
M0,
M1] :
zip(Mask0, Mask1)) {
6973 if (
M0 >= 0 &&
M1 >= 0)
6975 else if (
M0 == -1 &&
M1 == -1)
6988 int MaskOffset = NewMask[0
u];
6989 unsigned Index = (InputNumElements + MaskOffset) % InputNumElements;
6992 for (
unsigned I = 0u;
I < InputNumElements; ++
I) {
7006 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
7009 if (NewCost > OldCost)
7021 auto *NewPhi = Builder.
CreatePHI(NewShuf0->getType(), 2u);
7023 NewPhi->addIncoming(
Op,
Phi->getIncomingBlock(1u));
7029 replaceValue(*Phi, *NewShuf1);
7035bool VectorCombine::run() {
7049 auto Opcode =
I.getOpcode();
7057 if (IsFixedVectorType) {
7059 case Instruction::InsertElement:
7060 if (vectorizeLoadInsert(
I))
7063 case Instruction::ShuffleVector:
7064 if (widenSubvectorLoad(
I))
7075 if (scalarizeOpOrCmp(
I))
7077 if (scalarizeLoad(
I))
7079 if (scalarizeExtExtract(
I))
7081 if (foldInterleaveIntrinsics(
I))
7083 if (foldBitcastOfVPLoad(
I))
7087 if (foldDeinterleaveIntrinsics(
I))
7090 if (Opcode == Instruction::Store)
7091 if (foldInsertElementsToStores(
I))
7095 if (TryEarlyFoldsOnly)
7098 if (Opcode == Instruction::Call)
7099 if (foldBitOrderReverseAndSwap(
I))
7101 if (Opcode == Instruction::BitCast)
7102 if (foldBitOrderReverseAndSwap(
I))
7109 if (IsFixedVectorType) {
7111 case Instruction::InsertElement:
7112 if (foldInsExtFNeg(
I))
7114 if (foldInsExtBinop(
I))
7116 if (foldInsExtVectorToShuffle(
I))
7118 if (foldInsertScalarPartsToShuffle(
I))
7121 case Instruction::ShuffleVector:
7122 if (foldPermuteOfBinops(
I))
7124 if (foldShuffleOfBinops(
I))
7126 if (foldShuffleOfSelects(
I))
7128 if (foldShuffleOfCastops(
I))
7130 if (foldShuffleOfShuffles(
I))
7132 if (foldPermuteOfIntrinsic(
I))
7134 if (foldShufflesOfLengthChangingShuffles(
I))
7136 if (foldShuffleOfIntrinsics(
I))
7138 if (foldSelectShuffle(
I))
7140 if (foldShuffleToIdentity(
I))
7143 case Instruction::Load:
7144 if (shrinkLoadForShuffles(
I))
7147 case Instruction::BitCast:
7148 if (foldBitcastShuffle(
I))
7150 if (foldSelectsFromBitcast(
I))
7153 case Instruction::And:
7154 case Instruction::Or:
7155 case Instruction::Xor:
7156 if (foldBitOpOfCastops(
I))
7158 if (foldBitOpOfCastConstant(
I))
7161 case Instruction::PHI:
7162 if (shrinkPhiOfShuffles(
I))
7172 case Instruction::Call:
7173 if (foldShuffleFromReductions(
I))
7175 if (foldCastFromReductions(
I))
7178 case Instruction::ExtractElement:
7179 if (foldShuffleChainsToReduce(
I))
7182 case Instruction::ICmp:
7183 if (foldSignBitReductionCmp(
I))
7185 if (foldICmpEqZeroVectorReduce(
I))
7187 if (foldReductionZeroTest(
I))
7189 if (foldEquivalentReductionCmp(
I))
7191 if (foldReduceAddCmpZero(
I))
7194 case Instruction::FCmp:
7195 if (foldExtractExtract(
I))
7198 case Instruction::Or:
7199 if (foldConcatOfBoolMasks(
I))
7204 if (foldExtractExtract(
I))
7206 if (foldExtractedCmps(
I))
7208 if (foldBinopOfReductions(
I))
7217 bool MadeChange =
false;
7218 for (BasicBlock &BB :
F) {
7230 if (!
I->isDebugOrPseudoInst())
7231 MadeChange |= FoldInst(*
I);
7238 while (!Worklist.isEmpty()) {
7248 MadeChange |= FoldInst(*
I);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static cl::opt< unsigned > MaxInstrsToScan("aggressive-instcombine-max-scan-instrs", cl::init(64), cl::Hidden, cl::desc("Max number of instructions to scan for aggressive instcombine."))
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")
static cl::opt< OutputCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(OutputCostKind::RecipThroughput), cl::values(clEnumValN(OutputCostKind::RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(OutputCostKind::Latency, "latency", "Instruction latency"), clEnumValN(OutputCostKind::CodeSize, "code-size", "Code size"), clEnumValN(OutputCostKind::SizeAndLatency, "size-latency", "Code size and latency"), clEnumValN(OutputCostKind::All, "all", "Print all cost kinds")))
static cl::opt< IntrinsicCostStrategy > IntrinsicCost("intrinsic-cost-strategy", cl::desc("Costing strategy for intrinsic instructions"), cl::init(IntrinsicCostStrategy::InstructionCost), cl::values(clEnumValN(IntrinsicCostStrategy::InstructionCost, "instruction-cost", "Use TargetTransformInfo::getInstructionCost"), clEnumValN(IntrinsicCostStrategy::IntrinsicCost, "intrinsic-cost", "Use TargetTransformInfo::getIntrinsicInstrCost"), clEnumValN(IntrinsicCostStrategy::TypeBasedIntrinsicCost, "type-based-intrinsic-cost", "Calculate the intrinsic cost based only on argument types")))
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, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU)
uint64_t IntrinsicInst * II
FunctionAnalysisManager FAM
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & 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 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 * widenDeinterleavedOperations(ArrayRef< Value * > Members, ElementCount WideEC, IRBuilder< InstSimplifyFolder > &Builder)
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 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 cl::opt< bool > DisableVectorCombine("disable-vector-combine", cl::init(false), cl::Hidden, cl::desc("Disable all vector combine transforms"))
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 bool canWidenDeinterleavedOperations(ArrayRef< Value * > Members, unsigned &NumScanned)
Check whether the tree of elementwise operations each feeding Members can be rebuilt at the interleav...
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 cl::opt< unsigned > MaxInstrsToScan("vector-combine-max-scan-instrs", cl::init(30), cl::Hidden, cl::desc("Max number of instructions to scan for vector combining."))
static cl::opt< bool > DisableBinopExtractShuffle("disable-binop-extract-shuffle", cl::init(false), cl::Hidden, cl::desc("Disable binop extract to shuffle transforms"))
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(BasicBlock::iterator Begin, BasicBlock::iterator End, const MemoryLocation &Loc, AAResults &AA)
static Value * createWideInstruction(Instruction *NarrowInst, ArrayRef< Value * > NewOperands, VectorType *WideResultTy, IRBuilder< InstSimplifyFolder > &Builder)
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.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
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.
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...
@ 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)
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.
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.
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)
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)
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)
FNeg_match< OpTy > m_FNeg(const OpTy &X)
Match 'fneg X' as 'fsub -0.0, X'.
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.
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
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.
initializer< Ty > init(const Ty &Val)
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).
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.
IRBuilder(LLVMContext &, FolderTy, InserterTy) -> IRBuilder< FolderTy, InserterTy >
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 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...
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