47#define DEBUG_TYPE "vector-combine"
53STATISTIC(NumVecLoad,
"Number of vector loads formed");
54STATISTIC(NumVecCmp,
"Number of vector compares formed");
55STATISTIC(NumVecBO,
"Number of vector binops formed");
56STATISTIC(NumVecCmpBO,
"Number of vector compare + binop formed");
57STATISTIC(NumShufOfBitcast,
"Number of shuffles moved after bitcast");
58STATISTIC(NumScalarOps,
"Number of scalar unary + binary ops formed");
59STATISTIC(NumScalarCmp,
"Number of scalar compares formed");
60STATISTIC(NumScalarIntrinsic,
"Number of scalar intrinsic calls formed");
62static const unsigned InvalidIndex = std::numeric_limits<unsigned>::max();
67 VectorCombine(
const VectorizeOptions &Opts,
Function &
F,
79 SQ(*DL,
nullptr, &DT, &AC),
80 TryEarlyFoldsOnly(TryEarlyFoldsOnly) {}
85 const VectorizeOptions &Opts;
87 IRBuilder<InstSimplifyFolder, IRBuilderCallbackInserter> Builder;
88 const TargetTransformInfo &TTI;
89 const DominatorTree &DT;
93 const SimplifyQuery SQ;
97 bool TryEarlyFoldsOnly;
99 InstructionWorklist Worklist;
108 bool vectorizeLoadInsert(Instruction &
I);
109 bool widenSubvectorLoad(Instruction &
I);
110 ExtractElementInst *getShuffleExtract(ExtractElementInst *Ext0,
111 ExtractElementInst *Ext1,
112 unsigned PreferredExtractIndex)
const;
113 bool isExtractExtractCheap(ExtractElementInst *Ext0, ExtractElementInst *Ext1,
114 const Instruction &
I,
115 ExtractElementInst *&ConvertToShuffle,
116 unsigned PreferredExtractIndex);
119 bool foldExtractExtract(Instruction &
I);
120 bool foldInsExtFNeg(Instruction &
I);
121 bool foldInsExtBinop(Instruction &
I);
122 bool foldInsExtVectorToShuffle(Instruction &
I);
123 bool foldInsertScalarPartsToShuffle(Instruction &
I);
124 bool foldBitOpOfCastops(Instruction &
I);
125 bool foldBitOpOfCastConstant(Instruction &
I);
126 bool foldBitcastShuffle(Instruction &
I);
127 bool scalarizeOpOrCmp(Instruction &
I);
128 bool foldExtractedCmps(Instruction &
I);
129 bool foldSelectsFromBitcast(Instruction &
I);
130 bool foldBinopOfReductions(Instruction &
I);
131 bool foldInsertElementsToStores(Instruction &
I);
132 bool scalarizeLoad(Instruction &
I);
133 bool scalarizeLoadExtract(LoadInst *LI, VectorType *VecTy,
Value *Ptr);
134 bool scalarizeLoadBitcast(LoadInst *LI, VectorType *VecTy,
Value *Ptr);
135 bool scalarizeExtExtract(Instruction &
I);
136 bool foldConcatOfBoolMasks(Instruction &
I);
137 bool foldPermuteOfBinops(Instruction &
I);
138 bool foldShuffleOfBinops(Instruction &
I);
139 bool foldShuffleOfSelects(Instruction &
I);
140 bool foldShuffleOfCastops(Instruction &
I);
141 bool foldShuffleOfShuffles(Instruction &
I);
142 bool foldPermuteOfIntrinsic(Instruction &
I);
143 bool foldShufflesOfLengthChangingShuffles(Instruction &
I);
144 bool foldShuffleOfIntrinsics(Instruction &
I);
145 bool foldShuffleToIdentity(Instruction &
I);
146 bool foldShuffleFromReductions(Instruction &
I);
147 bool foldShuffleChainsToReduce(Instruction &
I);
148 bool foldCastFromReductions(Instruction &
I);
149 bool foldSignBitReductionCmp(Instruction &
I);
150 bool foldReductionZeroTest(Instruction &
I);
151 bool foldICmpEqZeroVectorReduce(Instruction &
I);
152 bool foldEquivalentReductionCmp(Instruction &
I);
153 bool foldReduceAddCmpZero(Instruction &
I);
154 bool foldSelectShuffle(Instruction &
I,
bool FromReduction =
false);
155 bool foldInterleaveIntrinsics(Instruction &
I);
156 bool foldDeinterleaveIntrinsics(Instruction &
I);
157 bool foldBitcastOfVPLoad(Instruction &
I);
158 bool foldBitOrderReverseAndSwap(Instruction &
I);
159 bool shrinkType(Instruction &
I);
160 bool shrinkLoadForShuffles(Instruction &
I);
161 bool shrinkPhiOfShuffles(Instruction &
I);
162 bool foldInterleaveOfDeinterleaveChains(Instruction &
I);
164 void replaceValue(Instruction &Old,
Value &New,
bool Erase =
true) {
170 Worklist.pushUsersToWorkList(*NewI);
171 Worklist.pushValue(NewI);
188 SmallPtrSet<Value *, 4> Visited;
193 OpI,
nullptr,
nullptr, [&](
Value *V) {
198 NextInst = NextInst->getNextNode();
203 Worklist.pushUsersToWorkList(*OpI);
204 Worklist.pushValue(OpI);
222 return X->getType() ==
Y->getType() &&
231 Load->getFunction()->hasFnAttribute(Attribute::SanitizeMemTag) ||
237 Type *ScalarTy =
Load->getType()->getScalarType();
239 unsigned MinVectorSize =
TTI.getMinVectorRegisterBitWidth();
240 if (!ScalarSize || !MinVectorSize || MinVectorSize % ScalarSize != 0 ||
247bool VectorCombine::vectorizeLoadInsert(
Instruction &
I) {
273 Value *SrcPtr =
Load->getPointerOperand()->stripPointerCasts();
276 unsigned MinVecNumElts = MinVectorSize / ScalarSize;
277 auto *MinVecTy = VectorType::get(ScalarTy, MinVecNumElts,
false);
278 unsigned OffsetEltIndex = 0;
289 unsigned OffsetBitWidth =
DL->getIndexTypeSizeInBits(SrcPtr->
getType());
290 APInt
Offset(OffsetBitWidth, 0);
300 uint64_t ScalarSizeInBytes = ScalarSize / 8;
301 if (
Offset.urem(ScalarSizeInBytes) != 0)
305 APInt OffsetEltIndexAP =
Offset.udiv(ScalarSizeInBytes);
306 if (OffsetEltIndexAP.
uge(MinVecNumElts))
325 unsigned AS =
Load->getPointerAddressSpace();
344 unsigned OutputNumElts = Ty->getNumElements();
346 assert(OffsetEltIndex < MinVecNumElts &&
"Address offset too big");
347 Mask[0] = OffsetEltIndex;
354 if (OldCost < NewCost || !NewCost.
isValid())
365 replaceValue(
I, *VecLd);
373bool VectorCombine::widenSubvectorLoad(Instruction &
I) {
376 if (!Shuf->isIdentityWithPadding())
382 unsigned OpIndex =
any_of(Shuf->getShuffleMask(), [&NumOpElts](
int M) {
383 return M >= (int)(NumOpElts);
406 unsigned AS =
Load->getPointerAddressSpace();
421 if (OldCost < NewCost || !NewCost.
isValid())
428 replaceValue(
I, *VecLd);
435ExtractElementInst *VectorCombine::getShuffleExtract(
436 ExtractElementInst *Ext0, ExtractElementInst *Ext1,
440 assert(Index0C && Index1C &&
"Expected constant extract indexes");
442 unsigned Index0 = Index0C->getZExtValue();
443 unsigned Index1 = Index1C->getZExtValue();
446 if (Index0 == Index1)
470 if (PreferredExtractIndex == Index0)
472 if (PreferredExtractIndex == Index1)
476 return Index0 > Index1 ? Ext0 : Ext1;
484bool VectorCombine::isExtractExtractCheap(ExtractElementInst *Ext0,
485 ExtractElementInst *Ext1,
486 const Instruction &
I,
487 ExtractElementInst *&ConvertToShuffle,
488 unsigned PreferredExtractIndex) {
491 assert(Ext0IndexC && Ext1IndexC &&
"Expected constant extract indexes");
493 unsigned Opcode =
I.getOpcode();
506 assert((Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) &&
507 "Expected a compare");
517 unsigned Ext0Index = Ext0IndexC->getZExtValue();
518 unsigned Ext1Index = Ext1IndexC->getZExtValue();
532 unsigned BestExtIndex = Extract0Cost > Extract1Cost ? Ext0Index : Ext1Index;
533 unsigned BestInsIndex = Extract0Cost > Extract1Cost ? Ext1Index : Ext0Index;
534 InstructionCost CheapExtractCost = std::min(Extract0Cost, Extract1Cost);
539 if (Ext0Src == Ext1Src && Ext0Index == Ext1Index) {
544 bool HasUseTax = Ext0 == Ext1 ? !Ext0->
hasNUses(2)
546 OldCost = CheapExtractCost + ScalarOpCost;
547 NewCost = VectorOpCost + CheapExtractCost + HasUseTax * CheapExtractCost;
551 OldCost = Extract0Cost + Extract1Cost + ScalarOpCost;
552 NewCost = VectorOpCost + CheapExtractCost +
557 ConvertToShuffle = getShuffleExtract(Ext0, Ext1, PreferredExtractIndex);
558 if (ConvertToShuffle) {
559 if (IsBinOp && Opts.disable_binop_extract_shuffle)
570 SmallVector<int> ShuffleMask(FixedVecTy->getNumElements(),
572 ShuffleMask[BestInsIndex] = BestExtIndex;
574 VecTy, VecTy,
CostKind, ShuffleMask, 0,
575 nullptr, {ConvertToShuffle});
578 VecTy, VecTy,
CostKind, {}, 0,
nullptr,
583 LLVM_DEBUG(
dbgs() <<
"Found a binop of extractions: " <<
I <<
"\n OldCost: "
584 << OldCost <<
" vs NewCost: " << NewCost <<
"\n");
589 return OldCost < NewCost;
601 ShufMask[NewIndex] = OldIndex;
602 return Builder.CreateShuffleVector(Vec, ShufMask,
"shift");
654 V1,
"foldExtExtBinop");
659 VecBOInst->copyIRFlags(&
I);
665bool VectorCombine::foldExtractExtract(Instruction &
I) {
681 V0->getType() !=
V1->getType())
686 unsigned NumElts = FixedVecTy->getNumElements();
687 if (C0 >= NumElts || C1 >= NumElts)
703 ExtractElementInst *ExtractToChange;
704 if (isExtractExtractCheap(Ext0, Ext1,
I, ExtractToChange, InsertIndex))
710 if (ExtractToChange) {
711 unsigned CheapExtractIdx = ExtractToChange == Ext0 ? C1 : C0;
716 if (ExtractToChange == Ext0)
725 ? foldExtExtCmp(ExtOp0, ExtOp1, ExtIndex,
I)
726 : foldExtExtBinop(ExtOp0, ExtOp1, ExtIndex,
I);
727 replaceValue(
I, *NewExt);
733bool VectorCombine::foldInsExtFNeg(Instruction &
I) {
751 auto *DstVecScalarTy = DstVecTy->getScalarType();
753 if (!SrcVecTy || DstVecScalarTy != SrcVecTy->getScalarType())
758 unsigned NumDstElts = DstVecTy->getNumElements();
759 unsigned NumSrcElts = SrcVecTy->getNumElements();
760 if (ExtIdx > NumSrcElts || InsIdx >= NumDstElts || NumDstElts == 1)
766 SmallVector<int>
Mask(NumDstElts);
767 std::iota(
Mask.begin(),
Mask.end(), 0);
768 Mask[InsIdx] = (ExtIdx % NumDstElts) + NumDstElts;
784 bool NeedLenChg = SrcVecTy->getNumElements() != NumDstElts;
787 SmallVector<int> SrcMask;
790 SrcMask[ExtIdx % NumDstElts] = ExtIdx;
792 DstVecTy, SrcVecTy,
CostKind, SrcMask);
796 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
798 if (NewCost > OldCost)
801 Value *NewShuf, *LenChgShuf =
nullptr;
813 replaceValue(
I, *NewShuf);
819bool VectorCombine::foldInsExtBinop(Instruction &
I) {
820 BinaryOperator *VecBinOp, *SclBinOp;
852 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
854 if (NewCost > OldCost)
865 NewInst->copyIRFlags(VecBinOp);
866 NewInst->andIRFlags(SclBinOp);
869 replaceValue(
I, *NewBO);
875bool VectorCombine::foldBitOpOfCastops(Instruction &
I) {
878 if (!BinOp || !BinOp->isBitwiseLogicOp())
884 if (!LHSCast || !RHSCast) {
885 LLVM_DEBUG(
dbgs() <<
" One or both operands are not cast instructions\n");
891 if (CastOpcode != RHSCast->getOpcode())
895 switch (CastOpcode) {
896 case Instruction::BitCast:
897 case Instruction::Trunc:
898 case Instruction::SExt:
899 case Instruction::ZExt:
905 Value *LHSSrc = LHSCast->getOperand(0);
906 Value *RHSSrc = RHSCast->getOperand(0);
912 auto *SrcTy = LHSSrc->
getType();
913 auto *DstTy =
I.getType();
916 if (CastOpcode != Instruction::BitCast &&
921 if (!SrcTy->getScalarType()->isIntegerTy() ||
922 !DstTy->getScalarType()->isIntegerTy())
937 LHSCastCost + RHSCastCost;
948 if (!LHSCast->hasOneUse())
949 NewCost += LHSCastCost;
950 if (!RHSCast->hasOneUse())
951 NewCost += RHSCastCost;
954 <<
" NewCost=" << NewCost <<
"\n");
956 if (NewCost > OldCost)
961 BinOp->getName() +
".inner");
963 NewBinOp->copyIRFlags(BinOp);
975 replaceValue(
I, *Result);
984bool VectorCombine::foldBitOpOfCastConstant(Instruction &
I) {
1000 switch (CastOpcode) {
1001 case Instruction::BitCast:
1002 case Instruction::ZExt:
1003 case Instruction::SExt:
1004 case Instruction::Trunc:
1010 Value *LHSSrc = LHSCast->getOperand(0);
1012 auto *SrcTy = LHSSrc->
getType();
1013 auto *DstTy =
I.getType();
1016 if (CastOpcode != Instruction::BitCast &&
1021 if (!SrcTy->getScalarType()->isIntegerTy() ||
1022 !DstTy->getScalarType()->isIntegerTy())
1026 PreservedCastFlags RHSFlags;
1051 if (!LHSCast->hasOneUse())
1052 NewCost += LHSCastCost;
1054 LLVM_DEBUG(
dbgs() <<
"foldBitOpOfCastConstant: OldCost=" << OldCost
1055 <<
" NewCost=" << NewCost <<
"\n");
1057 if (NewCost > OldCost)
1062 LHSSrc, InvC,
I.getName() +
".inner");
1064 NewBinOp->copyIRFlags(&
I);
1082 replaceValue(
I, *Result);
1089bool VectorCombine::foldBitcastShuffle(Instruction &
I) {
1103 if (!DestTy || !SrcTy)
1106 unsigned DestEltSize = DestTy->getScalarSizeInBits();
1107 unsigned SrcEltSize = SrcTy->getScalarSizeInBits();
1108 if (SrcTy->getPrimitiveSizeInBits() % DestEltSize != 0)
1118 if (!(BCTy0 && BCTy0->getElementType() == DestTy->getElementType()) &&
1119 !(BCTy1 && BCTy1->getElementType() == DestTy->getElementType()))
1123 SmallVector<int, 16> NewMask;
1124 if (DestEltSize <= SrcEltSize) {
1127 if (SrcEltSize % DestEltSize != 0)
1129 unsigned ScaleFactor = SrcEltSize / DestEltSize;
1134 if (DestEltSize % SrcEltSize != 0)
1136 unsigned ScaleFactor = DestEltSize / SrcEltSize;
1143 unsigned NumSrcElts = SrcTy->getPrimitiveSizeInBits() / DestEltSize;
1144 auto *NewShuffleTy =
1146 auto *OldShuffleTy =
1148 unsigned NumOps = IsUnary ? 1 : 2;
1158 TargetTransformInfo::CastContextHint::None,
1163 TargetTransformInfo::CastContextHint::None,
1166 LLVM_DEBUG(
dbgs() <<
"Found a bitcasted shuffle: " <<
I <<
"\n OldCost: "
1167 << OldCost <<
" vs NewCost: " << NewCost <<
"\n");
1169 if (NewCost > OldCost || !NewCost.
isValid())
1177 replaceValue(
I, *Shuf);
1184bool VectorCombine::scalarizeOpOrCmp(Instruction &
I) {
1189 if (!UO && !BO && !CI && !
II)
1197 if (Arg->getType() !=
II->getType() &&
1207 for (User *U :
I.users())
1214 std::optional<uint64_t>
Index;
1216 auto Ops =
II ?
II->args() :
I.operands();
1225 if (OpTy->getElementCount().getKnownMinValue() <= InsIdx)
1231 else if (InsIdx != *Index)
1248 if (!
Index.has_value())
1252 Type *ScalarTy = VecTy->getScalarType();
1253 assert(VecTy->isVectorTy() &&
1256 "Unexpected types for insert element into binop or cmp");
1258 unsigned Opcode =
I.getOpcode();
1266 }
else if (UO || BO) {
1270 IntrinsicCostAttributes ScalarICA(
1271 II->getIntrinsicID(), ScalarTy,
1274 IntrinsicCostAttributes VectorICA(
1275 II->getIntrinsicID(), VecTy,
1282 Value *NewVecC =
nullptr;
1284 NewVecC =
simplifyCmpInst(CI->getPredicate(), VecCs[0], VecCs[1], SQ);
1287 simplifyUnOp(UO->getOpcode(), VecCs[0], UO->getFastMathFlags(), SQ);
1289 NewVecC =
simplifyBinOp(BO->getOpcode(), VecCs[0], VecCs[1], SQ);
1303 for (
auto [Idx,
Op, VecC, Scalar] :
enumerate(
Ops, VecCs, ScalarOps)) {
1305 II->getIntrinsicID(), Idx, &
TTI)))
1308 Instruction::InsertElement, VecTy,
CostKind, *Index, VecC, Scalar);
1309 OldCost += InsertCost;
1310 NewCost += !
Op->hasOneUse() * InsertCost;
1314 if (OldCost < NewCost || !NewCost.
isValid())
1324 ++NumScalarIntrinsic;
1327 for (
auto [OpIdx, Scalar, VecC] :
enumerate(ScalarOps, VecCs))
1339 ScalarOps[1], FPMO->getFastMathFlags(),
1340 CI->getName() +
".scalar");
1343 ScalarOps[1], CI->getName() +
".scalar");
1347 UO->getName() +
".scalar");
1349 if (OverflowingBinaryOperator *OBO =
1352 BO->getOpcode(), ScalarOps[0], ScalarOps[1], OBO->hasNoUnsignedWrap(),
1353 OBO->hasNoSignedWrap(), BO->getName() +
".scalar");
1356 BO->getName() +
".scalar", PDI->isDisjoint());
1357 }
else if (PossiblyExactOperator *PEO =
1361 PEO->isExact(), BO->getName() +
".scalar");
1364 ScalarOps[1], FPMO->getFastMathFlags(),
1365 BO->getName() +
".scalar");
1368 BO->getName() +
".scalar");
1373 FMF = FPMO->getFastMathFlags();
1375 FMF,
II->getName() +
".scalar");
1379 replaceValue(
I, *Insert);
1386bool VectorCombine::foldExtractedCmps(Instruction &
I) {
1391 if (!BI || !
I.getType()->isIntegerTy(1))
1396 Value *
B0 =
I.getOperand(0), *
B1 =
I.getOperand(1);
1399 CmpPredicate
P0,
P1;
1418 ExtractElementInst *ConvertToShuf = getShuffleExtract(Ext0, Ext1,
CostKind);
1421 assert((ConvertToShuf == Ext0 || ConvertToShuf == Ext1) &&
1422 "Unknown ExtractElementInst");
1427 unsigned CmpOpcode =
1433 if (Index0 >= VecTy->getNumElements() || Index1 >= VecTy->getNumElements())
1445 Ext0Cost + Ext1Cost + CmpCost * 2 +
1451 int CheapIndex = ConvertToShuf == Ext0 ? Index1 : Index0;
1452 int ExpensiveIndex = ConvertToShuf == Ext0 ? Index0 : Index1;
1457 ShufMask[CheapIndex] = ExpensiveIndex;
1462 NewCost += Ext0->
hasOneUse() ? 0 : Ext0Cost;
1463 NewCost += Ext1->
hasOneUse() ? 0 : Ext1Cost;
1468 if (OldCost < NewCost || !NewCost.
isValid())
1478 Value *
LHS = ConvertToShuf == Ext0 ? Shuf : VCmp;
1479 Value *
RHS = ConvertToShuf == Ext0 ? VCmp : Shuf;
1482 replaceValue(
I, *NewExt);
1509bool VectorCombine::foldSelectsFromBitcast(Instruction &
I) {
1516 if (!SrcVecTy || !DstVecTy)
1526 if (SrcEltBits != 32 && SrcEltBits != 64)
1529 if (!DstEltTy->
isIntegerTy() || DstEltBits >= SrcEltBits)
1546 if (!ScalarSelCost.
isValid() || ScalarSelCost == 0)
1549 unsigned MinSelects = (VecSelCost.
getValue() / ScalarSelCost.
getValue()) + 1;
1552 if (!BC->hasNUsesOrMore(MinSelects))
1557 DenseMap<Value *, SmallVector<SelectInst *, 8>> CondToSelects;
1559 for (User *U : BC->users()) {
1564 for (User *ExtUser : Ext->users()) {
1568 Cond->getType()->isIntegerTy(1))
1573 if (CondToSelects.
empty())
1576 bool MadeChange =
false;
1577 Value *SrcVec = BC->getOperand(0);
1580 for (
auto [
Cond, Selects] : CondToSelects) {
1582 if (Selects.size() < MinSelects) {
1583 LLVM_DEBUG(
dbgs() <<
"VectorCombine: foldSelectsFromBitcast not "
1584 <<
"profitable (VecCost=" << VecSelCost
1585 <<
", ScalarCost=" << ScalarSelCost
1586 <<
", NumSelects=" << Selects.size() <<
")\n");
1591 auto InsertPt = std::next(BC->getIterator());
1595 InsertPt = std::next(CondInst->getIterator());
1603 for (SelectInst *Sel : Selects) {
1605 Value *
Idx = Ext->getIndexOperand();
1609 replaceValue(*Sel, *NewExt);
1614 <<
" selects into vector select\n");
1628 unsigned ReductionOpc =
1634 CostBeforeReduction =
1635 TTI.getCastInstrCost(RedOp->getOpcode(), VecRedTy, ExtType,
1637 CostAfterReduction =
1638 TTI.getExtendedReductionCost(ReductionOpc, IsUnsigned,
II.getType(),
1642 if (RedOp &&
II.getIntrinsicID() == Intrinsic::vector_reduce_add &&
1648 (Op0->
getOpcode() == RedOp->getOpcode() || Op0 == Op1)) {
1655 TTI.getCastInstrCost(Op0->
getOpcode(), MulType, ExtType,
1658 TTI.getArithmeticInstrCost(Instruction::Mul, MulType,
CostKind);
1660 TTI.getCastInstrCost(RedOp->getOpcode(), VecRedTy, MulType,
1663 CostBeforeReduction = ExtCost * 2 + MulCost + Ext2Cost;
1664 CostAfterReduction =
TTI.getMulAccReductionCost(
1665 IsUnsigned, ReductionOpc,
II.getType(), ExtType,
CostKind);
1668 CostAfterReduction =
TTI.getArithmeticReductionCost(ReductionOpc, VecRedTy,
1672bool VectorCombine::foldBinopOfReductions(Instruction &
I) {
1675 if (BinOpOpc == Instruction::Sub)
1676 ReductionIID = Intrinsic::vector_reduce_add;
1680 if (ReductionIID == Intrinsic::vector_reduce_fadd ||
1681 ReductionIID == Intrinsic::vector_reduce_fmul)
1684 auto checkIntrinsicAndGetItsArgument = [](
Value *
V,
1689 if (
II->getIntrinsicID() == IID &&
II->hasOneUse())
1690 return II->getArgOperand(0);
1694 Value *
V0 = checkIntrinsicAndGetItsArgument(
I.getOperand(0), ReductionIID);
1697 Value *
V1 = checkIntrinsicAndGetItsArgument(
I.getOperand(1), ReductionIID);
1702 if (
V1->getType() != VTy)
1706 unsigned ReductionOpc =
1719 CostOfRedOperand0 + CostOfRedOperand1 +
1722 if (NewCost >= OldCost || !NewCost.
isValid())
1726 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
1729 if (BinOpOpc == Instruction::Or)
1736 replaceValue(
I, *Rdx);
1746 unsigned NumScanned = 0;
1749 ++NumScanned > Opts.vector_combine_max_scan_instrs;
1761class ScalarizationResult {
1762 enum class StatusTy { Unsafe,
Safe, SafeWithFreeze };
1767 ScalarizationResult(StatusTy Status,
Value *ToFreeze =
nullptr)
1768 : Status(Status), ToFreeze(ToFreeze) {}
1771 ScalarizationResult(
const ScalarizationResult &
Other) =
default;
1772 ~ScalarizationResult() {
1773 assert(!ToFreeze &&
"freeze() not called with ToFreeze being set");
1776 static ScalarizationResult unsafe() {
return {StatusTy::Unsafe}; }
1777 static ScalarizationResult safe() {
return {StatusTy::Safe}; }
1778 static ScalarizationResult safeWithFreeze(
Value *ToFreeze) {
1779 return {StatusTy::SafeWithFreeze, ToFreeze};
1783 bool isSafe()
const {
return Status == StatusTy::Safe; }
1785 bool isUnsafe()
const {
return Status == StatusTy::Unsafe; }
1788 bool isSafeWithFreeze()
const {
return Status == StatusTy::SafeWithFreeze; }
1793 Status = StatusTy::Unsafe;
1797 void freeze(IRBuilderBase &Builder, Instruction &UserI) {
1798 assert(isSafeWithFreeze() &&
1799 "should only be used when freezing is required");
1801 "UserI must be a user of ToFreeze");
1802 IRBuilder<>::InsertPointGuard Guard(Builder);
1807 if (
U.get() == ToFreeze)
1822 uint64_t NumElements = VecTy->getElementCount().getKnownMinValue();
1823 unsigned IntWidth = Idx->getType()->getScalarSizeInBits();
1826 if (
C->getValue().ult(NumElements))
1827 return ScalarizationResult::safe();
1828 return ScalarizationResult::unsafe();
1833 return ScalarizationResult::unsafe();
1835 APInt Zero(IntWidth, 0);
1836 APInt MaxElts(IntWidth, NumElements);
1843 return ScalarizationResult::safe();
1844 return ScalarizationResult::unsafe();
1857 if (ValidIndices.
contains(IdxRange))
1858 return ScalarizationResult::safeWithFreeze(IdxBase);
1859 return ScalarizationResult::unsafe();
1879 unsigned GEPBits = GEPIndexTy->getBitWidth();
1880 uint64_t NumElements = VecTy->getElementCount().getKnownMinValue();
1882 uint64_t MaxLane = NumElements - 1;
1884 if (
C->getValue().uge(NumElements))
1886 MaxLane =
C->getZExtValue();
1890 if (!
DL.typeSizeEqualsStoreSize(
ElemTy))
1910 unsigned WideBits = std::max(GEPBits, 128u);
1911 APInt MaxLaneValue(WideBits, MaxLane);
1912 APInt ByteOffset = MaxLaneValue;
1917 if (ByteOffset.
ugt(MaxGEPOffset))
1928 unsigned SrcBits = Idx->getType()->getIntegerBitWidth();
1930 if (SrcBits >= DstBits)
1933 return Builder.CreateZExt(Idx, GEPIndexTy, Idx->getName() +
".gepidx");
1945 C->getZExtValue() *
DL.getTypeStoreSize(ScalarType));
1982bool VectorCombine::foldInsertElementsToStores(Instruction &
I) {
1997 if (!
Insert->hasOneUse())
2005 if (InsertElements.
empty())
2010 std::reverse(InsertElements.
begin(), InsertElements.
end());
2019 if (InsertElements.
size() == FVT->getNumElements()) {
2020 Value *FirstVal = InsertElements.
front().first;
2021 if (
all_of(InsertElements,
2022 [FirstVal](
const auto &Elt) {
return Elt.first == FirstVal; }))
2026 Value *SrcAddr =
Load->getPointerOperand()->stripPointerCasts();
2031 if (!
Load->isSimple() ||
Load->getParent() !=
SI->getParent() ||
2032 !
DL->typeSizeEqualsStoreSize(
Load->getType()->getScalarType()) ||
2033 SrcAddr !=
SI->getPointerOperand()->stripPointerCasts())
2043 for (
auto [InsertVal, Idx] : InsertElements) {
2044 auto ScalarizableIdx =
2046 if (ScalarizableIdx.isUnsafe())
2052 ScalarizableIdx.discard();
2058 ScalarizableIdx.discard();
2062 Instruction::Store,
SI->getValueOperand()->getType(),
SI->getAlign(),
2065 if (
Load->hasOneUse())
2070 for (
auto [InsertVal, Idx] : InsertElements) {
2073 Index = CIdx->getZExtValue();
2084 for (
auto [InsertVal, Idx] : InsertElements) {
2087 const Value *GEPIndices[] = {ConstantInt::get(
Idx->getType(), 0),
Idx};
2092 for (
auto [InsertVal, Idx] : InsertElements) {
2094 std::max(
SI->getAlign(),
Load->getAlign()), InsertVal->
getType(), Idx,
2102 LLVM_DEBUG(
dbgs() <<
"Found an insert-elements vector store scalarization "
2105 <<
" NumInserts: " << InsertElements.size() <<
"\n"
2106 <<
" OldCost: " << OldCost <<
" vs NewCost: " << NewCost
2109 if (OldCost <= NewCost)
2112 for (
auto [InsertVal, Idx] : InsertElements) {
2113 auto ScalarizableIdx =
2115 assert(!ScalarizableIdx.isUnsafe() &&
"already checked above");
2117 if (ScalarizableIdx.isSafeWithFreeze())
2122 StoreInst *LastStore =
nullptr;
2123 for (
auto [InsertVal, Idx] : InsertElements) {
2124 auto ScalarizableIdx =
2126 if (ScalarizableIdx.isUnsafe())
2129 IntegerType *GEPIndexTy =
2134 SI->getValueOperand()->getType(),
SI->getPointerOperand(),
2135 {ConstantInt::get(GEPIdx->getType(), 0), GEPIdx});
2142 LastStore->
setMetadata(LLVMContext::MD_invariant_group,
nullptr);
2144 std::max(
SI->getAlign(),
Load->getAlign()), InsertVal->
getType(), Idx,
2149 replaceValue(
I, *LastStore);
2156bool VectorCombine::scalarizeLoad(Instruction &
I) {
2166 if (!LI->isSimple() || !
DL->typeSizeEqualsStoreSize(VecTy->getScalarType()))
2169 bool AllExtracts =
true;
2170 bool AllBitcasts =
true;
2172 unsigned NumInstChecked = 0;
2177 for (User *U : LI->users()) {
2179 if (!UI || UI->getParent() != LI->getParent())
2184 if (UI->use_empty())
2188 AllExtracts =
false;
2190 AllBitcasts =
false;
2194 for (Instruction &
I :
2195 make_range(std::next(LI->getIterator()), UI->getIterator())) {
2198 if (NumInstChecked == Opts.vector_combine_max_scan_instrs ||
2199 I.mayWriteToMemory())
2203 LastCheckedInst = UI;
2208 return scalarizeLoadExtract(LI, VecTy, Ptr);
2210 return scalarizeLoadBitcast(LI, VecTy, Ptr);
2215bool VectorCombine::scalarizeLoadExtract(LoadInst *LI, VectorType *VecTy,
2220 DenseMap<ExtractElementInst *, ScalarizationResult> NeedFreeze;
2221 DenseMap<ExtractElementInst *, IntegerType *> GEPIndexInfos;
2224 for (
auto &Pair : NeedFreeze)
2225 Pair.second.discard();
2233 for (User *U : LI->
users()) {
2238 if (ScalarIdx.isUnsafe())
2244 ScalarIdx.discard();
2250 if (ScalarIdx.isSafeWithFreeze()) {
2251 NeedFreeze.try_emplace(UI, ScalarIdx);
2252 ScalarIdx.discard();
2258 Index ?
Index->getZExtValue() : -1);
2264 if (!Index && UI->getIndexOperand()->getType()->getIntegerBitWidth() <
2267 Instruction::ZExt, GEPIndex, UI->getIndexOperand()->getType(),
2271 LLVM_DEBUG(
dbgs() <<
"Found all extractions of a vector load: " << *LI
2272 <<
"\n LoadExtractCost: " << OriginalCost
2273 <<
" vs ScalarizedCost: " << ScalarizedCost <<
"\n");
2275 if (ScalarizedCost > OriginalCost)
2277 if (ScalarizedCost == OriginalCost && !LI->
hasOneUse())
2284 Type *ElemType = VecTy->getElementType();
2287 for (User *U : LI->
users()) {
2289 Value *
Idx = EI->getIndexOperand();
2292 if (
auto It = NeedFreeze.find(EI); It != NeedFreeze.end())
2296 auto It = GEPIndexInfos.
find(EI);
2298 "Missing scalarized GEP index information");
2301 VecTy, Ptr, {ConstantInt::get(GEPIdx->
getType(), 0), GEPIdx});
2303 Builder.
CreateLoad(ElemType,
GEP, EI->getName() +
".scalar"));
2305 Align ScalarOpAlignment =
2307 NewLoad->setAlignment(ScalarOpAlignment);
2310 size_t Offset = ConstIdx->getZExtValue() *
DL->getTypeStoreSize(ElemType);
2315 replaceValue(*EI, *NewLoad,
false);
2318 FailureGuard.release();
2323bool VectorCombine::scalarizeLoadBitcast(LoadInst *LI, VectorType *VecTy,
2332 Type *TargetScalarType =
nullptr;
2333 unsigned VecBitWidth =
DL->getTypeSizeInBits(VecTy);
2335 for (User *U : LI->
users()) {
2338 Type *DestTy = BC->getDestTy();
2342 unsigned DestBitWidth =
DL->getTypeSizeInBits(DestTy);
2343 if (DestBitWidth != VecBitWidth)
2347 if (!TargetScalarType)
2348 TargetScalarType = DestTy;
2349 else if (TargetScalarType != DestTy)
2357 if (!TargetScalarType)
2365 LLVM_DEBUG(
dbgs() <<
"Found vector load feeding only bitcasts: " << *LI
2366 <<
"\n OriginalCost: " << OriginalCost
2367 <<
" vs ScalarizedCost: " << ScalarizedCost <<
"\n");
2369 if (ScalarizedCost >= OriginalCost)
2380 ScalarLoad->copyMetadata(*LI);
2383 for (User *U : LI->
users()) {
2385 replaceValue(*BC, *ScalarLoad,
false);
2391bool VectorCombine::scalarizeExtExtract(Instruction &
I) {
2406 Type *ScalarDstTy = DstTy->getElementType();
2407 if (
DL->getTypeSizeInBits(SrcTy) !=
DL->getTypeSizeInBits(ScalarDstTy))
2413 unsigned ExtCnt = 0;
2414 bool ExtLane0 =
false;
2415 for (User *U : Ext->users()) {
2421 if (Idx >= SrcTy->getNumElements())
2433 Instruction::And, ScalarDstTy,
CostKind,
2436 (ExtCnt - ExtLane0) *
2438 Instruction::LShr, ScalarDstTy,
CostKind,
2441 if (ScalarCost > VectorCost)
2444 Value *ScalarV = Ext->getOperand(0);
2451 SmallDenseSet<ConstantInt *, 8> ExtractedLanes;
2452 bool AllExtractsTriggerUB =
true;
2453 ExtractElementInst *LastExtract =
nullptr;
2455 for (User *U : Ext->users()) {
2458 AllExtractsTriggerUB =
false;
2462 if (!LastExtract || LastExtract->
comesBefore(Extract))
2463 LastExtract = Extract;
2465 if (ExtractedLanes.
size() != DstTy->getNumElements() ||
2466 !AllExtractsTriggerUB ||
2474 uint64_t SrcEltSizeInBits =
DL->getTypeSizeInBits(SrcTy->getElementType());
2475 uint64_t TotalBits =
DL->getTypeSizeInBits(SrcTy);
2478 Value *
Mask = ConstantInt::get(PackedTy, EltBitMask);
2479 for (User *U : Ext->users()) {
2485 ? (TotalBits - SrcEltSizeInBits -
Idx * SrcEltSizeInBits)
2486 : (
Idx * SrcEltSizeInBits);
2489 U->replaceAllUsesWith(
And);
2497bool VectorCombine::foldConcatOfBoolMasks(Instruction &
I) {
2498 Type *Ty =
I.getType();
2503 if (
DL->isBigEndian())
2530 if (ShAmtX > ShAmtY) {
2538 uint64_t ShAmtDiff = ShAmtY - ShAmtX;
2539 unsigned NumSHL = (ShAmtX > 0) + (ShAmtY > 0);
2544 MaskTy->getNumElements() != ShAmtDiff ||
2545 MaskTy->getNumElements() > (
BitWidth / 2))
2550 Type::getIntNTy(Ty->
getContext(), ConcatTy->getNumElements());
2551 auto *MaskIntTy = Type::getIntNTy(Ty->
getContext(), ShAmtDiff);
2554 std::iota(ConcatMask.begin(), ConcatMask.end(), 0);
2571 if (Ty != ConcatIntTy)
2577 LLVM_DEBUG(
dbgs() <<
"Found a concatenation of bitcasted bool masks: " <<
I
2578 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
2581 if (NewCost > OldCost)
2590 if (Ty != ConcatIntTy) {
2598 replaceValue(
I, *Result);
2604bool VectorCombine::foldPermuteOfBinops(Instruction &
I) {
2605 BinaryOperator *BinOp;
2606 ArrayRef<int> OuterMask;
2614 Value *Op00, *Op01, *Op10, *Op11;
2615 ArrayRef<int> Mask0, Mask1;
2620 if (!Match0 && !Match1)
2633 if (!ShuffleDstTy || !BinOpTy || !Op0Ty || !Op1Ty)
2636 unsigned NumSrcElts = BinOpTy->getNumElements();
2641 any_of(OuterMask, [NumSrcElts](
int M) {
return M >= (int)NumSrcElts; }))
2645 SmallVector<int> NewMask0, NewMask1;
2646 for (
int M : OuterMask) {
2647 if (M < 0 || M >= (
int)NumSrcElts) {
2651 NewMask0.
push_back(Match0 ? Mask0[M] : M);
2652 NewMask1.
push_back(Match1 ? Mask1[M] : M);
2656 unsigned NumOpElts = Op0Ty->getNumElements();
2657 bool IsIdentity0 = ShuffleDstTy == Op0Ty &&
2658 all_of(NewMask0, [NumOpElts](
int M) {
return M < (int)NumOpElts; }) &&
2660 bool IsIdentity1 = ShuffleDstTy == Op1Ty &&
2661 all_of(NewMask1, [NumOpElts](
int M) {
return M < (int)NumOpElts; }) &&
2670 ShuffleDstTy, BinOpTy,
CostKind, OuterMask,
2671 0,
nullptr, {BinOp}, &
I);
2673 NewCost += BinOpCost;
2679 OldCost += Shuf0Cost;
2681 NewCost += Shuf0Cost;
2687 OldCost += Shuf1Cost;
2689 NewCost += Shuf1Cost;
2697 Op0Ty,
CostKind, NewMask0, 0,
nullptr, {Op00, Op01});
2701 Op1Ty,
CostKind, NewMask1, 0,
nullptr, {Op10, Op11});
2703 LLVM_DEBUG(
dbgs() <<
"Found a shuffle feeding a shuffled binop: " <<
I
2704 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
2708 if (NewCost > OldCost)
2719 NewInst->copyIRFlags(BinOp);
2721 replaceValue(
I, *NewBO);
2727bool VectorCombine::foldShuffleOfBinops(Instruction &
I) {
2728 ArrayRef<int> OldMask;
2735 if (
LHS->getOpcode() !=
RHS->getOpcode())
2739 bool IsCommutative =
false;
2748 IsCommutative = BinaryOperator::isCommutative(BO->getOpcode());
2759 if (!ShuffleDstTy || !BinResTy || !BinOpTy ||
X->getType() !=
Z->getType())
2762 bool SameBinOp =
LHS ==
RHS;
2763 unsigned NumSrcElts = BinOpTy->getNumElements();
2766 if (IsCommutative &&
X != Z &&
Y != W && (
X == W ||
Y == Z))
2769 auto ConvertToUnary = [NumSrcElts](
int &
M) {
2770 if (M >= (
int)NumSrcElts)
2774 SmallVector<int> NewMask0(OldMask);
2783 SmallVector<int> NewMask1(OldMask);
2802 ShuffleDstTy, BinResTy,
CostKind, OldMask, 0,
2812 ArrayRef<int> InnerMask;
2814 m_Mask(InnerMask)))) &&
2817 [NumSrcElts](
int M) {
return M < (int)NumSrcElts; })) {
2829 bool ReducedInstCount =
false;
2830 ReducedInstCount |= MergeInner(
X, 0, NewMask0,
CostKind);
2831 ReducedInstCount |= MergeInner(
Y, 0, NewMask1,
CostKind);
2832 ReducedInstCount |= MergeInner(Z, NumSrcElts, NewMask0,
CostKind);
2833 ReducedInstCount |= MergeInner(W, NumSrcElts, NewMask1,
CostKind);
2834 bool SingleSrcBinOp = (
X ==
Y) && (Z == W) && (NewMask0 == NewMask1);
2846 I.getType()->getScalarType()->isIntegerTy(1) &&
2850 auto *ShuffleCmpTy =
2853 SK0, ShuffleCmpTy, BinOpTy,
CostKind, NewMask0, 0,
nullptr, {
X,
Z});
2854 if (!SingleSrcBinOp)
2856 NewMask1, 0,
nullptr, {
Y,
W});
2864 PredLHS,
CostKind, Op0Info, Op1Info);
2874 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
2881 if (ReducedInstCount ? (NewCost > OldCost) : (NewCost >= OldCost))
2890 : Builder.
CreateCmp(PredLHS, Shuf0, Shuf1);
2894 NewInst->copyIRFlags(
LHS);
2895 NewInst->andIRFlags(
RHS);
2898 replaceValue(
I, *NewBO);
2905bool VectorCombine::foldShuffleOfSelects(Instruction &
I) {
2907 Value *C1, *
T1, *F1, *C2, *T2, *F2;
2918 if (!C1VecTy || !C2VecTy || C1VecTy != C2VecTy)
2924 if (((SI0FOp ==
nullptr) != (SI1FOp ==
nullptr)) ||
2925 ((SI0FOp !=
nullptr) &&
2926 (SI0FOp->getFastMathFlags() != SI1FOp->getFastMathFlags())))
2932 auto SelOp = Instruction::Select;
2940 CostSel1 + CostSel2 +
2942 {
I.getOperand(0),
I.getOperand(1)}, &
I);
2946 CostKind, Mask, 0,
nullptr, {C1, C2});
2956 if (!Sel1->hasOneUse())
2957 NewCost += CostSel1;
2958 if (!Sel2->hasOneUse())
2959 NewCost += CostSel2;
2962 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
2964 if (NewCost > OldCost)
2973 NewSel = Builder.
CreateSelectFMF(ShuffleCmp, ShuffleTrue, ShuffleFalse,
2974 SI0FOp->getFastMathFlags());
2976 NewSel = Builder.
CreateSelect(ShuffleCmp, ShuffleTrue, ShuffleFalse);
2978 replaceValue(
I, *NewSel);
2984bool VectorCombine::foldShuffleOfCastops(Instruction &
I) {
2986 ArrayRef<int> OldMask;
2995 if (!C0 || (IsBinaryShuffle && !C1))
3002 if (!IsBinaryShuffle && Opcode == Instruction::BitCast)
3005 if (IsBinaryShuffle) {
3006 if (C0->getSrcTy() != C1->getSrcTy())
3009 if (Opcode != C1->getOpcode()) {
3011 Opcode = Instruction::SExt;
3020 if (!ShuffleDstTy || !CastDstTy || !CastSrcTy)
3023 unsigned NumSrcElts = CastSrcTy->getNumElements();
3024 unsigned NumDstElts = CastDstTy->getNumElements();
3025 assert((NumDstElts == NumSrcElts || Opcode == Instruction::BitCast) &&
3026 "Only bitcasts expected to alter src/dst element counts");
3030 if (NumDstElts != NumSrcElts && (NumSrcElts % NumDstElts) != 0 &&
3031 (NumDstElts % NumSrcElts) != 0)
3034 SmallVector<int, 16> NewMask;
3035 if (NumSrcElts >= NumDstElts) {
3038 assert(NumSrcElts % NumDstElts == 0 &&
"Unexpected shuffle mask");
3039 unsigned ScaleFactor = NumSrcElts / NumDstElts;
3044 assert(NumDstElts % NumSrcElts == 0 &&
"Unexpected shuffle mask");
3045 unsigned ScaleFactor = NumDstElts / NumSrcElts;
3050 auto *NewShuffleDstTy =
3059 if (IsBinaryShuffle)
3066 OldMask, 0,
nullptr, {}, &
I);
3074 if (IsBinaryShuffle) {
3084 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
3086 if (NewCost > OldCost)
3090 if (IsBinaryShuffle)
3100 NewInst->copyIRFlags(C0);
3101 if (IsBinaryShuffle)
3102 NewInst->andIRFlags(C1);
3105 replaceValue(
I, *Cast);
3115bool VectorCombine::foldShuffleOfShuffles(Instruction &
I) {
3116 ArrayRef<int> OuterMask;
3117 Value *OuterV0, *OuterV1;
3122 ArrayRef<int> InnerMask0, InnerMask1;
3123 Value *X0, *X1, *Y0, *Y1;
3128 if (!Match0 && !Match1)
3133 SmallVector<int, 16> PoisonMask1;
3138 InnerMask1 = PoisonMask1;
3142 X0 = Match0 ? X0 : OuterV0;
3143 Y0 = Match0 ? Y0 : OuterV0;
3144 X1 = Match1 ? X1 : OuterV1;
3145 Y1 = Match1 ? Y1 : OuterV1;
3149 if (!ShuffleDstTy || !ShuffleSrcTy || !ShuffleImmTy ||
3153 unsigned NumSrcElts = ShuffleSrcTy->getNumElements();
3154 unsigned NumImmElts = ShuffleImmTy->getNumElements();
3159 SmallVector<int, 16> NewMask(OuterMask);
3160 Value *NewX =
nullptr, *NewY =
nullptr;
3161 for (
int &M : NewMask) {
3162 Value *Src =
nullptr;
3163 if (0 <= M && M < (
int)NumImmElts) {
3167 Src =
M >= (int)NumSrcElts ? Y0 : X0;
3168 M =
M >= (int)NumSrcElts ? (M - NumSrcElts) :
M;
3170 }
else if (M >= (
int)NumImmElts) {
3175 Src =
M >= (int)NumSrcElts ? Y1 : X1;
3176 M =
M >= (int)NumSrcElts ? (M - NumSrcElts) :
M;
3180 assert(0 <= M && M < (
int)NumSrcElts &&
"Unexpected shuffle mask index");
3189 if (!NewX || NewX == Src) {
3193 if (!NewY || NewY == Src) {
3212 replaceValue(
I, *NewX);
3229 bool IsUnary =
all_of(NewMask, [&](
int M) {
return M < (int)NumSrcElts; });
3235 nullptr, {NewX, NewY});
3237 NewCost += InnerCost0;
3239 NewCost += InnerCost1;
3242 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
3244 if (NewCost > OldCost)
3248 replaceValue(
I, *Shuf);
3264bool VectorCombine::foldShufflesOfLengthChangingShuffles(Instruction &
I) {
3269 unsigned ChainLength = 0;
3270 SmallVector<int>
Mask;
3271 SmallVector<int> YMask;
3281 ArrayRef<int> OuterMask;
3282 Value *OuterV0, *OuterV1;
3283 if (ChainLength != 0 && !Trunk->
hasOneUse())
3286 m_Mask(OuterMask))))
3288 if (OuterV0->
getType() != TrunkType) {
3294 ArrayRef<int> InnerMask0, InnerMask1;
3300 bool Match0Leaf = Match0 && A0->
getType() !=
I.getType();
3301 bool Match1Leaf = Match1 && A1->
getType() !=
I.getType();
3302 if (Match0Leaf == Match1Leaf) {
3308 SmallVector<int> CommutedOuterMask;
3315 for (
int &M : CommutedOuterMask) {
3318 if (M < (
int)NumTrunkElts)
3323 OuterMask = CommutedOuterMask;
3342 int NumLeafElts = YType->getNumElements();
3343 SmallVector<int> LocalYMask(InnerMask1);
3344 for (
int &M : LocalYMask) {
3345 if (M >= NumLeafElts)
3355 Mask.assign(OuterMask);
3356 YMask.
assign(LocalYMask);
3357 OldCost = NewCost = LocalOldCost;
3364 SmallVector<int> NewYMask(YMask);
3366 for (
auto [CombinedM, LeafM] :
llvm::zip(NewYMask, LocalYMask)) {
3367 if (LeafM == -1 || CombinedM == LeafM)
3369 if (CombinedM == -1) {
3379 SmallVector<int> NewMask;
3380 NewMask.
reserve(NumTrunkElts);
3381 for (
int M : Mask) {
3382 if (M < 0 || M >=
static_cast<int>(NumTrunkElts))
3397 if (LocalNewCost >= NewCost && LocalOldCost < LocalNewCost - NewCost)
3401 if (ChainLength == 1) {
3402 dbgs() <<
"Found chain of shuffles fed by length-changing shuffles: "
3405 dbgs() <<
" next chain link: " << *Trunk <<
'\n'
3406 <<
" old cost: " << (OldCost + LocalOldCost)
3407 <<
" new cost: " << LocalNewCost <<
'\n';
3412 OldCost += LocalOldCost;
3413 NewCost = LocalNewCost;
3417 if (ChainLength <= 1)
3425 return M < 0 || M >=
static_cast<int>(NumTrunkElts);
3428 for (
int &M : Mask) {
3429 if (M >=
static_cast<int>(NumTrunkElts))
3430 M = YMask[
M - NumTrunkElts];
3434 replaceValue(
I, *Root);
3441 replaceValue(
I, *Root);
3447bool VectorCombine::foldShuffleOfIntrinsics(Instruction &
I) {
3449 ArrayRef<int> OldMask;
3459 if (IID != II1->getIntrinsicID())
3468 if (!ShuffleDstTy || !II0Ty)
3474 for (
unsigned Idx = 0,
E = II0->arg_size(); Idx !=
E; ++Idx) {
3475 Value *Arg0 = II0->getArgOperand(Idx);
3476 Value *Arg1 = II1->getArgOperand(Idx);
3493 II0Ty,
CostKind, OldMask, 0,
nullptr, {II0, II1}, &
I);
3497 SmallDenseSet<std::pair<Value *, Value *>> SeenOperandPairs;
3498 for (
unsigned Idx = 0,
E = II0->arg_size(); Idx !=
E; ++Idx) {
3500 NewArgsTy.
push_back(II0->getArgOperand(Idx)->getType());
3504 ShuffleDstTy->getNumElements());
3506 std::pair<Value *, Value *> OperandPair =
3507 std::make_pair(II0->getArgOperand(Idx), II1->getArgOperand(Idx));
3508 if (!SeenOperandPairs.
insert(OperandPair).second) {
3514 OldMask, 0,
nullptr,
3515 {II0->getArgOperand(Idx), II1->getArgOperand(Idx)});
3518 IntrinsicCostAttributes NewAttr(IID, ShuffleDstTy, NewArgsTy);
3521 if (!II0->hasOneUse())
3523 if (II1 != II0 && !II1->hasOneUse())
3527 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
3530 if (NewCost > OldCost)
3534 SmallDenseMap<std::pair<Value *, Value *>,
Value *> ShuffleCache;
3535 for (
unsigned Idx = 0,
E = II0->arg_size(); Idx !=
E; ++Idx) {
3537 NewArgs.
push_back(II0->getArgOperand(Idx));
3539 std::pair<Value *, Value *> OperandPair =
3540 std::make_pair(II0->getArgOperand(Idx), II1->getArgOperand(Idx));
3541 auto It = ShuffleCache.
find(OperandPair);
3542 if (It != ShuffleCache.
end()) {
3548 II0->getArgOperand(Idx), II1->getArgOperand(Idx), OldMask);
3549 ShuffleCache[OperandPair] = Shuf;
3557 NewInst->copyIRFlags(II0);
3558 NewInst->andIRFlags(II1);
3561 replaceValue(
I, *NewIntrinsic);
3567bool VectorCombine::foldPermuteOfIntrinsic(Instruction &
I) {
3579 if (!ShuffleDstTy || !IntrinsicSrcTy)
3583 unsigned NumSrcElts = IntrinsicSrcTy->getNumElements();
3584 if (
any_of(Mask, [NumSrcElts](
int M) {
return M >= (int)NumSrcElts; }))
3597 IntrinsicSrcTy,
CostKind, Mask, 0,
nullptr, {
V0}, &
I);
3601 for (
unsigned I = 0,
E = II0->arg_size();
I !=
E; ++
I) {
3603 NewArgsTy.
push_back(II0->getArgOperand(
I)->getType());
3607 ShuffleDstTy->getNumElements());
3610 ArgTy, VecTy,
CostKind, Mask, 0,
nullptr,
3611 {II0->getArgOperand(
I)});
3614 IntrinsicCostAttributes NewAttr(IID, ShuffleDstTy, NewArgsTy);
3619 if (!II0->hasOneUse())
3622 LLVM_DEBUG(
dbgs() <<
"Found a permute of intrinsic: " <<
I <<
"\n OldCost: "
3623 << OldCost <<
" vs NewCost: " << NewCost <<
"\n");
3625 if (NewCost > OldCost)
3630 for (
unsigned I = 0,
E = II0->arg_size();
I !=
E; ++
I) {
3642 NewInst->copyIRFlags(II0);
3644 replaceValue(
I, *NewIntrinsic);
3654 int M = SV->getMaskValue(Lane);
3657 if (
static_cast<unsigned>(M) < NumElts) {
3658 V = SV->getOperand(0);
3661 V = SV->getOperand(1);
3672 auto [U, Lane] = IL;
3685 unsigned NumElts = Ty->getNumElements();
3686 if (Item.
size() == NumElts || NumElts == 1 || Item.
size() % NumElts != 0)
3692 std::iota(ConcatMask.
begin(), ConcatMask.
end(), 0);
3698 unsigned NumSlices = Item.
size() / NumElts;
3703 for (
unsigned Slice = 0; Slice < NumSlices; ++Slice) {
3704 Value *SliceV = Item[Slice * NumElts].first;
3705 if (!SliceV || SliceV->
getType() != Ty)
3707 for (
unsigned Elt = 0; Elt < NumElts; ++Elt) {
3708 auto [V, Lane] = Item[Slice * NumElts + Elt];
3709 if (Lane !=
static_cast<int>(Elt) || SliceV != V)
3718 const DenseSet<std::pair<Value *, Use *>> &IdentityLeafs,
3719 const DenseSet<std::pair<Value *, Use *>> &SplatLeafs,
3720 const DenseSet<std::pair<Value *, Use *>> &ConcatLeafs,
3723 auto [FrontV, FrontLane] = Item.
front();
3725 if (IdentityLeafs.contains(std::make_pair(FrontV, From))) {
3728 if (SplatLeafs.contains(std::make_pair(FrontV, From))) {
3730 return Builder.CreateShuffleVector(FrontV, Mask);
3732 if (ConcatLeafs.contains(std::make_pair(FrontV, From))) {
3736 for (
unsigned S = 0; S <
Values.size(); ++S)
3737 Values[S] = Item[S * NumElts].first;
3739 while (
Values.size() > 1) {
3742 std::iota(Mask.begin(), Mask.end(), 0);
3744 for (
unsigned S = 0; S < NewValues.
size(); ++S)
3746 Builder.CreateShuffleVector(
Values[S * 2],
Values[S * 2 + 1], Mask);
3760 if (BCDstTy && BCSrcTy &&
3761 BCDstTy->getElementCount() != BCSrcTy->getElementCount()) {
3762 unsigned DstElts = BCDstTy->getNumElements();
3763 unsigned SrcElts = BCSrcTy->getNumElements();
3765 if (DstElts > SrcElts) {
3767 unsigned R = DstElts / SrcElts;
3768 if (Item.
size() % R != 0)
3770 for (
unsigned Idx = 0,
E = Item.
size(); Idx <
E; Idx += R) {
3771 auto [V, Lane] = Item[Idx];
3781 unsigned R = SrcElts / DstElts;
3782 for (
auto [V, Lane] : Item) {
3788 for (
unsigned J = 0; J < R; ++J)
3793 IdentityLeafs, SplatLeafs, ConcatLeafs,
3794 Builder, WorkList,
TTI);
3795 return Builder.CreateBitCast(
3800 unsigned NumOps =
I->getNumOperands() - (
II ? 1 : 0);
3802 for (
unsigned Idx = 0; Idx <
NumOps; Idx++) {
3805 Ops[Idx] =
II->getOperand(Idx);
3810 IdentityLeafs, SplatLeafs, ConcatLeafs, Builder, WorkList,
TTI);
3822 for (
const auto &Lane : Item)
3835 auto *
Value = Builder.CreateCmp(CI->getPredicate(),
Ops[0],
Ops[1]);
3845 auto *
Value = Builder.CreateCast(CI->getOpcode(),
Ops[0], DstTy);
3850 auto *
Value = Builder.CreateIntrinsic(DstTy,
II->getIntrinsicID(),
Ops);
3864bool VectorCombine::foldShuffleToIdentity(Instruction &
I) {
3866 if (!Ty ||
I.use_empty())
3870 for (
unsigned M = 0,
E = Ty->getNumElements(); M <
E; ++M)
3874 Candidates.
push_back(std::make_pair(Start, &*
I.use_begin()));
3875 DenseSet<std::pair<Value *, Use *>> IdentityLeafs, SplatLeafs, ConcatLeafs;
3876 unsigned NumVisited = 0;
3877 bool TraversedElCountChangingBitcast =
false;
3879 while (!Candidates.
empty()) {
3880 if (++NumVisited > Opts.vector_combine_max_scan_instrs)
3884 auto Item = ItemFrom.first;
3885 auto From = ItemFrom.second;
3886 auto [FrontV, FrontLane] = Item.front();
3893 if (FrontLane == 0 &&
3897 Value *FrontV = Item.front().first;
3899 E.value().second == (int)
E.index());
3901 IdentityLeafs.
insert(std::make_pair(FrontV, From));
3906 C &&
C->getSplatValue() &&
3908 Value *FrontV = Item.front().first;
3914 SplatLeafs.
insert(std::make_pair(FrontV, From));
3919 auto [FrontV, FrontLane] = Item.front();
3920 auto [
V, Lane] = IL;
3921 return !
V || (
V == FrontV && Lane == FrontLane);
3923 SplatLeafs.
insert(std::make_pair(FrontV, From));
3929 auto CheckLaneIsEquivalentToFirst = [Item](
InstLane IL) {
3930 Value *FrontV = Item.front().first;
3939 if (CI->getPredicate() !=
cast<CmpInst>(FrontV)->getPredicate())
3942 if (CI->getSrcTy()->getScalarType() !=
3947 SI->getOperand(0)->getType() !=
3954 II->getIntrinsicID() ==
3956 !
II->hasOperandBundles());
3963 BO && BO->isIntDivRem())
3970 }
else if (
isa<UnaryOperator, TruncInst, ZExtInst, SExtInst, FPToSIInst,
3971 FPToUIInst, SIToFPInst, UIToFPInst>(FrontV)) {
3978 if (BCDstTy && BCSrcTy) {
3979 ElementCount DstEC = BCDstTy->getElementCount();
3980 ElementCount SrcEC = BCSrcTy->getElementCount();
3981 if (DstEC == SrcEC) {
3984 &BitCast->getOperandUse(0));
3989 if (DstElts > SrcElts && DstElts % SrcElts == 0) {
3993 unsigned R = DstElts / SrcElts;
3995 bool Valid = Item.size() %
R == 0;
3996 for (
unsigned Idx = 0,
E = Item.size(); Valid && Idx <
E;
3998 auto [
V0, L0] = Item[
Idx];
4001 [](
InstLane IL) {
return IL.first !=
nullptr; })) {
4012 for (
unsigned J = 1; J <
R; ++J) {
4013 auto [VJ, LJ] = Item[
Idx + J];
4014 if (!VJ || VJ != V0 || LJ != L0 + (
int)J) {
4025 TraversedElCountChangingBitcast =
true;
4026 Candidates.
emplace_back(NItem, &BitCast->getOperandUse(0));
4029 }
else if (SrcElts > DstElts && SrcElts % DstElts == 0) {
4032 unsigned R = SrcElts / DstElts;
4034 for (
auto [V, Lane] : Item) {
4040 for (
unsigned J = 0; J <
R; ++J)
4043 TraversedElCountChangingBitcast =
true;
4044 Candidates.
emplace_back(NItem, &BitCast->getOperandUse(0));
4050 &Sel->getOperandUse(0));
4052 &Sel->getOperandUse(1));
4054 &Sel->getOperandUse(2));
4058 !
II->hasOperandBundles()) {
4059 for (
unsigned Op = 0,
E =
II->getNumOperands() - 1;
Op <
E;
Op++) {
4063 Value *FrontV = Item.front().first;
4080 ConcatLeafs.
insert(std::make_pair(FrontV, From));
4087 if (NumVisited <= 1)
4093 if (NumVisited == 2 && TraversedElCountChangingBitcast)
4096 LLVM_DEBUG(
dbgs() <<
"Found a superfluous identity shuffle: " <<
I <<
"\n");
4103 ConcatLeafs, Builder, Worklist, &
TTI);
4104 replaceValue(
I, *V);
4111bool VectorCombine::foldShuffleFromReductions(Instruction &
I) {
4115 switch (
II->getIntrinsicID()) {
4116 case Intrinsic::vector_reduce_add:
4117 case Intrinsic::vector_reduce_mul:
4118 case Intrinsic::vector_reduce_and:
4119 case Intrinsic::vector_reduce_or:
4120 case Intrinsic::vector_reduce_xor:
4121 case Intrinsic::vector_reduce_smin:
4122 case Intrinsic::vector_reduce_smax:
4123 case Intrinsic::vector_reduce_umin:
4124 case Intrinsic::vector_reduce_umax:
4133 std::queue<Value *> Worklist;
4134 SmallPtrSet<Value *, 4> Visited;
4135 ShuffleVectorInst *Shuffle =
nullptr;
4139 while (!Worklist.empty()) {
4140 Value *CV = Worklist.front();
4152 if (CI->isBinaryOp()) {
4153 for (
auto *
Op : CI->operand_values())
4157 if (Shuffle && Shuffle != SV)
4174 for (
auto *V : Visited)
4175 for (
auto *U :
V->users())
4176 if (!Visited.contains(U) && U != &
I)
4179 FixedVectorType *VecType =
4183 FixedVectorType *ShuffleInputType =
4185 if (!ShuffleInputType)
4191 SmallVector<int> ConcatMask;
4193 sort(ConcatMask, [](
int X,
int Y) {
return (
unsigned)
X < (unsigned)
Y; });
4194 bool UsesSecondVec =
4195 any_of(ConcatMask, [&](
int M) {
return M >= (int)NumInputElts; });
4202 ShuffleInputType,
CostKind, ConcatMask);
4204 LLVM_DEBUG(
dbgs() <<
"Found a reduction feeding from a shuffle: " << *Shuffle
4206 LLVM_DEBUG(
dbgs() <<
" OldCost: " << OldCost <<
" vs NewCost: " << NewCost
4208 bool MadeChanges =
false;
4209 if (NewCost < OldCost) {
4213 LLVM_DEBUG(
dbgs() <<
"Created new shuffle: " << *NewShuffle <<
"\n");
4214 replaceValue(*Shuffle, *NewShuffle);
4220 MadeChanges |= foldSelectShuffle(*Shuffle,
true);
4241bool VectorCombine::foldShuffleChainsToReduce(Instruction &
I) {
4250 if (FVT->getNumElements() < 2)
4253 std::optional<Instruction::BinaryOps> CommonBinOp;
4254 std::optional<Intrinsic::ID> CommonCallOp;
4259 CommonBinOp = BO->getOpcode();
4261 CommonCallOp = MMI->getIntrinsicID();
4267 FastMathFlags CommonFMF;
4268 bool IsFloatReduction =
false;
4272 auto IsChainNode = [&](
Value *
V) {
4274 return CommonBinOp && BO->getOpcode() == *CommonBinOp;
4276 return CommonCallOp && MMI->getIntrinsicID() == *CommonCallOp;
4284 constexpr unsigned MaxChainNodes = 32;
4285 SmallSetVector<Value *, 16> Nodes;
4286 SmallSetVector<Value *, 4> Sources;
4287 unsigned NumVisited = 0;
4288 auto AddSource = [&](
Value *
V) {
4294 auto Walk = [&](
Value *
V,
auto &&Walk) ->
bool {
4297 if (++NumVisited > MaxChainNodes)
4299 if (!IsChainNode(V))
4300 return AddSource(V);
4305 if (!Walk(
U->getOperand(
I), Walk))
4314 return AddSource(V);
4316 if (!Walk(VecOpEE, Walk) || Nodes.
empty())
4323 for (
Value *V : Nodes) {
4329 if (!IsFloatReduction) {
4331 IsFloatReduction =
true;
4345 DenseMap<Value *, Demand> Demands;
4346 auto DemandOf = [&](
Value *
V) -> Demand & {
4348 Demand &
D = Demands[
V];
4349 if (
D.Lanes.getBitWidth() !=
N)
4353 DemandOf(VecOpEE).Lanes.setBit(0);
4355 Demand DV = Demands.
lookup(V);
4356 if (DV.Lanes.isZero())
4359 ArrayRef<int>
Mask = SVI->getShuffleMask();
4360 Demand &
DS = DemandOf(SVI->getOperand(0));
4361 for (
unsigned I = 0,
E =
Mask.size();
I !=
E; ++
I) {
4363 if (!DV.Lanes[
I] || Mask[
I] < 0 ||
4364 (
unsigned)Mask[
I] >=
DS.Lanes.getBitWidth())
4366 if (
DS.Lanes[Mask[
I]] || DV.Duplicates[
I])
4367 DS.Duplicates.setBit(Mask[
I]);
4368 DS.Lanes.setBit(Mask[
I]);
4372 for (
Value *
Op : {
U->getOperand(0),
U->getOperand(1)}) {
4373 Demand &DOp = DemandOf(
Op);
4375 DOp.Duplicates |= DV.Duplicates | (DOp.Lanes & DV.Lanes);
4376 DOp.Lanes |= DV.Lanes;
4383 auto CoversChain = [&](
Value *
V) {
4384 SmallVector<Value *, 8> Worklist(1, VecOpEE);
4385 SmallPtrSet<Value *, 8> Seen;
4387 while (!Worklist.empty()) {
4390 for (
unsigned I = 0;
I !=
NumOps; ++
I) {
4394 if (!Nodes.contains(
Op))
4396 Worklist.push_back(
Op);
4404 struct ReductionCut {
4408 std::optional<ReductionCut> Cut;
4409 for (
Value *S : Sources) {
4410 auto It = Demands.
find(S);
4411 if (It == Demands.
end() || It->second.Lanes.isZero())
4413 if (!IsIdempotent && !It->second.Duplicates.isZero()) {
4418 Cut = ReductionCut{S, It->second.Lanes};
4425 if (!IsIdempotent && !(Cut->Elts & It->second.Lanes).isZero()) {
4429 Cut->Elts |= It->second.Lanes;
4432 for (
Value *V : Nodes) {
4435 auto It = Demands.
find(V);
4436 if (It == Demands.
end() || !It->second.Lanes.isAllOnes())
4438 if (!IsIdempotent && !It->second.Duplicates.isZero())
4440 if (!CoversChain(V))
4442 Cut = ReductionCut{
V, It->second.Lanes};
4447 if (!Cut || Cut->Elts.popcount() < 2)
4457 for (
Value *V : Nodes)
4461 bool IsPartialReduction = !Cut->Elts.isAllOnes();
4462 FixedVectorType *ReduceVecTy =
4467 SmallVector<int> ExtractMask;
4469 if (IsPartialReduction) {
4470 for (
unsigned I = 0,
E = Cut->Elts.getBitWidth();
I !=
E; ++
I)
4472 ExtractMask.push_back(
I);
4473 unsigned SubIdx = 0, SubLen;
4474 auto SK = Cut->Elts.isShiftedMask(SubIdx, SubLen)
4478 SubIdx, ReduceVecTy);
4481 IntrinsicCostAttributes ICA(
4482 ReducedOp, ReduceVecTy->getElementType(),
4486 IsFloatReduction ? CommonFMF : FastMathFlags());
4489 LLVM_DEBUG(
dbgs() <<
"Found reduction shuffle chain: " <<
I <<
"\n OldCost : "
4490 << OrigCost <<
" vs NewCost: " << NewCost <<
"\n");
4495 if (VecOpEE->
hasOneUse() ? (NewCost > OrigCost) : (NewCost >= OrigCost))
4498 Value *ReduceInput = Cut->Src;
4499 if (IsPartialReduction)
4502 Value *ReducedResult;
4503 if (IsFloatReduction) {
4505 *CommonBinOp, ReduceVecTy->getElementType(),
false,
4508 {Identity, ReduceInput}, CommonFMF);
4513 replaceValue(
I, *ReducedResult);
4522bool VectorCombine::foldCastFromReductions(Instruction &
I) {
4527 bool TruncOnly =
false;
4530 case Intrinsic::vector_reduce_add:
4531 case Intrinsic::vector_reduce_mul:
4534 case Intrinsic::vector_reduce_and:
4535 case Intrinsic::vector_reduce_or:
4536 case Intrinsic::vector_reduce_xor:
4543 Value *ReductionSrc =
I.getOperand(0);
4555 Type *ResultTy =
I.getType();
4558 ReductionOpc, ReductionSrcTy, std::nullopt,
CostKind);
4568 if (OldCost <= NewCost || !NewCost.
isValid())
4572 II->getIntrinsicID(), {Src});
4574 replaceValue(
I, *NewCast);
4602bool VectorCombine::foldSignBitReductionCmp(Instruction &
I) {
4604 IntrinsicInst *ReduceOp;
4605 const APInt *CmpVal;
4612 case Intrinsic::vector_reduce_or:
4613 case Intrinsic::vector_reduce_umax:
4614 case Intrinsic::vector_reduce_and:
4615 case Intrinsic::vector_reduce_umin:
4616 case Intrinsic::vector_reduce_add:
4627 unsigned BitWidth = VecTy->getScalarSizeInBits();
4631 unsigned NumElts = VecTy->getNumElements();
4640 case Intrinsic::vector_reduce_or:
4641 case Intrinsic::vector_reduce_umax:
4642 TreeOpcode = Instruction::Or;
4644 case Intrinsic::vector_reduce_and:
4645 case Intrinsic::vector_reduce_umin:
4646 TreeOpcode = Instruction::And;
4648 case Intrinsic::vector_reduce_add:
4649 TreeOpcode = Instruction::Add;
4657 SmallVector<Value *, 8> Worklist;
4658 SmallVector<Value *, 8> Sources;
4660 std::optional<bool> IsAShr;
4661 constexpr unsigned MaxSources = 8;
4666 while (!Worklist.
empty() && Worklist.
size() <= MaxSources &&
4667 Sources.
size() <= MaxSources) {
4676 bool ThisIsAShr = Shr->getOpcode() == Instruction::AShr;
4678 IsAShr = ThisIsAShr;
4679 else if (*IsAShr != ThisIsAShr)
4705 if (Sources.
empty() || Sources.
size() > MaxSources ||
4706 Worklist.
size() > MaxSources || !IsAShr)
4709 unsigned NumSources = Sources.
size();
4713 if (OrigIID == Intrinsic::vector_reduce_add &&
4721 (OrigIID == Intrinsic::vector_reduce_add) ? NumSources * NumElts : 1;
4724 NegativeVal.negate();
4756 TestsNegative =
false;
4757 }
else if (*CmpVal == NegativeVal) {
4758 TestsNegative =
true;
4762 IsEq = Pred == ICmpInst::ICMP_EQ;
4763 }
else if (Pred == ICmpInst::ICMP_SLT && *CmpVal == RangeHigh) {
4765 TestsNegative = (RangeHigh == NegativeVal);
4766 }
else if (Pred == ICmpInst::ICMP_SGT && *CmpVal == RangeHigh - 1) {
4768 TestsNegative = (RangeHigh == NegativeVal);
4769 }
else if (Pred == ICmpInst::ICMP_SGT && *CmpVal == RangeLow) {
4771 TestsNegative = (RangeLow == NegativeVal);
4772 }
else if (Pred == ICmpInst::ICMP_SLT && *CmpVal == RangeLow + 1) {
4774 TestsNegative = (RangeLow == NegativeVal);
4817 enum CheckKind :
unsigned {
4824 auto RequiresOr = [](CheckKind
C) ->
bool {
return C & 0b100; };
4826 auto IsNegativeCheck = [](CheckKind
C) ->
bool {
return C & 0b010; };
4828 auto Invert = [](CheckKind
C) {
return CheckKind(
C ^ 0b011); };
4832 case Intrinsic::vector_reduce_or:
4833 case Intrinsic::vector_reduce_umax:
4834 Base = TestsNegative ? AnyNeg : AllNonNeg;
4836 case Intrinsic::vector_reduce_and:
4837 case Intrinsic::vector_reduce_umin:
4838 Base = TestsNegative ? AllNeg : AnyNonNeg;
4840 case Intrinsic::vector_reduce_add:
4841 Base = TestsNegative ? AllNeg : AllNonNeg;
4856 return ArithCost <= MinMaxCost ? std::make_pair(Arith, ArithCost)
4857 : std::make_pair(MinMax, MinMaxCost);
4861 auto [NewIID, NewCost] = RequiresOr(
Check)
4862 ? PickCheaper(Intrinsic::vector_reduce_or,
4863 Intrinsic::vector_reduce_umax)
4864 : PickCheaper(
Intrinsic::vector_reduce_and,
4868 if (NumSources > 1) {
4869 unsigned CombineOpc =
4870 RequiresOr(
Check) ? Instruction::Or : Instruction::And;
4875 LLVM_DEBUG(
dbgs() <<
"Found sign-bit reduction cmp: " <<
I <<
"\n OldCost: "
4876 << OldCost <<
" vs NewCost: " << NewCost <<
"\n");
4878 if (NewCost > OldCost)
4883 Type *ScalarTy = VecTy->getScalarType();
4886 if (NumSources == 1) {
4897 replaceValue(
I, *NewCmp);
4928bool VectorCombine::foldReductionZeroTest(Instruction &
I) {
4937 if (!
II || !
II->hasOneUse())
4940 auto ReduceID =
II->getIntrinsicID();
4941 if (ReduceID != Intrinsic::vector_reduce_or &&
4942 ReduceID != Intrinsic::vector_reduce_umax)
4945 Value *Vec =
II->getArgOperand(0);
4947 if (!VecTy || !VecTy->getElementType()->isIntegerTy())
4952 ? Intrinsic::vector_reduce_or
4967 LLVM_DEBUG(
dbgs() <<
"Found a reduction zero test: " <<
I <<
"\n OldCost: "
4968 << OldCost <<
" vs NewCost: " << NewCost <<
"\n");
4970 if (!OldCost.
isValid() || !NewCost.
isValid() || NewCost > OldCost)
4976 replaceValue(
I, *NewReduce);
5001bool VectorCombine::foldICmpEqZeroVectorReduce(Instruction &
I) {
5012 switch (
II->getIntrinsicID()) {
5013 case Intrinsic::vector_reduce_add:
5014 case Intrinsic::vector_reduce_or:
5015 case Intrinsic::vector_reduce_umin:
5016 case Intrinsic::vector_reduce_umax:
5017 case Intrinsic::vector_reduce_smin:
5018 case Intrinsic::vector_reduce_smax:
5024 Value *InnerOp =
II->getArgOperand(0);
5067 switch (
II->getIntrinsicID()) {
5068 case Intrinsic::vector_reduce_add: {
5073 unsigned NumElems = XTy->getNumElements();
5079 if (LeadingZerosX <= LostBits || LeadingZerosFX <= LostBits)
5087 case Intrinsic::vector_reduce_smin:
5088 case Intrinsic::vector_reduce_smax:
5098 LLVM_DEBUG(
dbgs() <<
"Found a reduction to 0 comparison with removable op: "
5114 case Intrinsic::vector_reduce_add:
5115 case Intrinsic::vector_reduce_or:
5121 case Intrinsic::vector_reduce_umin:
5122 case Intrinsic::vector_reduce_umax:
5123 case Intrinsic::vector_reduce_smin:
5124 case Intrinsic::vector_reduce_smax:
5136 NewReduceCost + (InnerOp->
hasOneUse() ? 0 : ExtCost);
5138 LLVM_DEBUG(
dbgs() <<
"Found a removable extension before reduction: "
5139 << *InnerOp <<
"\n OldCost: " << OldCost
5140 <<
" vs NewCost: " << NewCost <<
"\n");
5146 if (NewCost > OldCost)
5155 Builder.
CreateICmp(Pred, NewReduce, ConstantInt::getNullValue(Ty));
5156 replaceValue(
I, *NewCmp);
5187bool VectorCombine::foldEquivalentReductionCmp(Instruction &
I) {
5190 const APInt *CmpVal;
5195 if (!
II || !
II->hasOneUse())
5198 const auto IsValidOrUmaxCmp = [&]() {
5207 bool IsPositive = CmpVal->
isAllOnes() && Pred == ICmpInst::ICMP_SGT;
5209 bool IsNegative = (CmpVal->
isZero() || CmpVal->
isOne() || *CmpVal == 2) &&
5210 Pred == ICmpInst::ICMP_SLT;
5211 return IsEquality || IsPositive || IsNegative;
5214 const auto IsValidAndUminCmp = [&]() {
5219 const auto LeadingOnes = CmpVal->
countl_one();
5226 bool IsNegative = CmpVal->
isZero() && Pred == ICmpInst::ICMP_SLT;
5235 ((*CmpVal)[0] || (*CmpVal)[1]) && Pred == ICmpInst::ICMP_SGT;
5236 return IsEquality || IsNegative || IsPositive;
5244 switch (OriginalIID) {
5245 case Intrinsic::vector_reduce_or:
5246 if (!IsValidOrUmaxCmp())
5248 AlternativeIID = Intrinsic::vector_reduce_umax;
5250 case Intrinsic::vector_reduce_umax:
5251 if (!IsValidOrUmaxCmp())
5253 AlternativeIID = Intrinsic::vector_reduce_or;
5255 case Intrinsic::vector_reduce_and:
5256 if (!IsValidAndUminCmp())
5258 AlternativeIID = Intrinsic::vector_reduce_umin;
5260 case Intrinsic::vector_reduce_umin:
5261 if (!IsValidAndUminCmp())
5263 AlternativeIID = Intrinsic::vector_reduce_and;
5276 if (ReductionOpc != Instruction::ICmp)
5287 <<
"\n OrigCost: " << OrigCost
5288 <<
" vs AltCost: " << AltCost <<
"\n");
5290 if (AltCost >= OrigCost)
5294 Type *ScalarTy = VecTy->getScalarType();
5297 Builder.
CreateICmp(Pred, NewReduce, ConstantInt::get(ScalarTy, *CmpVal));
5299 replaceValue(
I, *NewCmp);
5313 unsigned Depth = 0) {
5314 constexpr unsigned MaxLocalDepth = 2;
5315 if (
Depth > MaxLocalDepth)
5318 auto NumSignBits = [&](
const Value *
X) {
5321 if (NumSignBits(V) == V->getType()->getScalarSizeInBits())
5326 return NumSignBits(
A) >= 2 && NumSignBits(
B) >= 2 &&
5337bool VectorCombine::foldReduceAddCmpZero(Instruction &
I) {
5347 if (!VecTy || VecTy->getNumElements() < 2)
5353 if (!IsNonNegative && !IsNonPositive)
5358 unsigned NumElts = VecTy->getNumElements();
5360 if (
Log2_32(NumElts) >= NumSignBits)
5363 ICmpInst::Predicate NewPred;
5365 case ICmpInst::ICMP_EQ:
5366 case ICmpInst::ICMP_ULE:
5367 case ICmpInst::ICMP_SLE:
5368 case ICmpInst::ICMP_SGE:
5369 NewPred = ICmpInst::ICMP_EQ;
5371 case ICmpInst::ICMP_NE:
5372 case ICmpInst::ICMP_UGT:
5373 case ICmpInst::ICMP_SGT:
5374 case ICmpInst::ICMP_SLT:
5375 NewPred = ICmpInst::ICMP_NE;
5385 if (!IsNonNegative &&
5386 (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLE))
5388 if (!IsNonPositive &&
5389 (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGE))
5391 if ((Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLE ||
5392 Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGE) &&
5393 Log2_32(NumElts) >= NumSignBits - 1)
5397 Instruction::Add, VecTy, std::nullopt,
CostKind);
5399 Instruction::Or, VecTy, std::nullopt,
CostKind);
5401 Intrinsic::umax, VecTy, FastMathFlags(),
CostKind);
5404 bool UseOr = OrCost.
isValid() && (!UmaxCost.
isValid() || OrCost <= UmaxCost);
5406 if (AltCost > OrigCost)
5412 Intrinsic::vector_reduce_umax, {VecTy}, {Vec});
5414 NewPred, NewReduce, ConstantInt::getNullValue(VecTy->getScalarType()));
5415 replaceValue(
I, *NewCmp);
5424 constexpr unsigned MaxVisited = 32;
5427 bool FoundReduction =
false;
5430 while (!WorkList.
empty()) {
5432 for (
User *U :
I->users()) {
5434 if (!UI || !Visited.
insert(UI).second)
5436 if (Visited.
size() > MaxVisited)
5442 switch (
II->getIntrinsicID()) {
5443 case Intrinsic::vector_reduce_add:
5444 case Intrinsic::vector_reduce_mul:
5445 case Intrinsic::vector_reduce_and:
5446 case Intrinsic::vector_reduce_or:
5447 case Intrinsic::vector_reduce_xor:
5448 case Intrinsic::vector_reduce_smin:
5449 case Intrinsic::vector_reduce_smax:
5450 case Intrinsic::vector_reduce_umin:
5451 case Intrinsic::vector_reduce_umax:
5452 FoundReduction =
true;
5465 return FoundReduction;
5478bool VectorCombine::foldSelectShuffle(Instruction &
I,
bool FromReduction) {
5483 if (!Op0 || !Op1 || Op0 == Op1 || !Op0->isBinaryOp() || !Op1->isBinaryOp() ||
5484 VT != Op0->getType())
5491 SmallPtrSet<Instruction *, 4> InputShuffles({SVI0A, SVI0B, SVI1A, SVI1B});
5493 if (!
I ||
I->getOperand(0)->getType() != VT)
5495 return any_of(
I->users(), [&](User *U) {
5496 return U != Op0 && U != Op1 &&
5497 !(isa<ShuffleVectorInst>(U) &&
5498 (InputShuffles.contains(cast<Instruction>(U)) ||
5499 isInstructionTriviallyDead(cast<Instruction>(U))));
5502 if (checkSVNonOpUses(SVI0A) || checkSVNonOpUses(SVI0B) ||
5503 checkSVNonOpUses(SVI1A) || checkSVNonOpUses(SVI1B))
5511 for (
auto *U :
I->users()) {
5513 if (!SV ||
SV->getType() != VT)
5515 if ((
SV->getOperand(0) != Op0 &&
SV->getOperand(0) != Op1) ||
5516 (
SV->getOperand(1) != Op0 &&
SV->getOperand(1) != Op1))
5523 if (!collectShuffles(Op0) || !collectShuffles(Op1))
5527 if (FromReduction && Shuffles.
size() > 1)
5532 if (!FromReduction) {
5533 for (
size_t Idx = 0,
E = Shuffles.
size(); Idx !=
E; ++Idx) {
5534 for (
auto *U : Shuffles[Idx]->
users()) {
5549 int MaxV1Elt = 0, MaxV2Elt = 0;
5550 unsigned NumElts = VT->getNumElements();
5551 for (ShuffleVectorInst *SVN : Shuffles) {
5552 SmallVector<int>
Mask;
5553 SVN->getShuffleMask(Mask);
5557 Value *SVOp0 = SVN->getOperand(0);
5558 Value *SVOp1 = SVN->getOperand(1);
5563 for (
int &Elem : Mask) {
5569 if (SVOp0 == Op1 && SVOp1 == Op0) {
5573 if (SVOp0 != Op0 || SVOp1 != Op1)
5579 SmallVector<int> ReconstructMask;
5580 for (
unsigned I = 0;
I <
Mask.size();
I++) {
5583 }
else if (Mask[
I] <
static_cast<int>(NumElts)) {
5584 MaxV1Elt = std::max(MaxV1Elt, Mask[
I]);
5585 auto It =
find_if(
V1, [&](
const std::pair<int, int> &
A) {
5586 return Mask[
I] ==
A.first;
5592 V1.emplace_back(Mask[
I],
V1.size());
5595 MaxV2Elt = std::max<int>(MaxV2Elt, Mask[
I] - NumElts);
5596 auto It =
find_if(V2, [&](
const std::pair<int, int> &
A) {
5597 return Mask[
I] -
static_cast<int>(NumElts) ==
A.first;
5611 sort(ReconstructMask);
5612 OrigReconstructMasks.
push_back(std::move(ReconstructMask));
5619 if (
V1.empty() || V2.
empty() ||
5620 (MaxV1Elt ==
static_cast<int>(
V1.size()) - 1 &&
5621 MaxV2Elt ==
static_cast<int>(V2.
size()) - 1))
5633 if (InputShuffles.contains(SSV))
5635 return SV->getMaskValue(M);
5643 std::pair<int, int>
Y) {
5644 int MXA = GetBaseMaskValue(
A,
X.first);
5645 int MYA = GetBaseMaskValue(
A,
Y.first);
5649 return SortBase(SVI0A,
A,
B);
5651 stable_sort(V2, [&](std::pair<int, int>
A, std::pair<int, int>
B) {
5652 return SortBase(SVI1A,
A,
B);
5657 for (
const auto &Mask : OrigReconstructMasks) {
5658 SmallVector<int> ReconstructMask;
5659 for (
int M : Mask) {
5661 auto It =
find_if(V, [M](
auto A) {
return A.second ==
M; });
5662 assert(It !=
V.end() &&
"Expected all entries in Mask");
5663 return std::distance(
V.begin(), It);
5667 else if (M <
static_cast<int>(NumElts)) {
5670 ReconstructMask.
push_back(NumElts + FindIndex(V2, M));
5673 ReconstructMasks.
push_back(std::move(ReconstructMask));
5678 SmallVector<int> V1A, V1B, V2A, V2B;
5679 for (
unsigned I = 0;
I <
V1.size();
I++) {
5683 for (
unsigned I = 0;
I < V2.
size();
I++) {
5684 V2A.
push_back(GetBaseMaskValue(SVI1A, V2[
I].first));
5685 V2B.
push_back(GetBaseMaskValue(SVI1B, V2[
I].first));
5687 while (V1A.
size() < NumElts) {
5691 while (V2A.
size() < NumElts) {
5710 unsigned ElementSize = VT->getElementType()->getPrimitiveSizeInBits();
5711 unsigned MaxVectorSize =
5713 unsigned MaxElementsInVector = MaxVectorSize / ElementSize;
5714 if (MaxElementsInVector == 0)
5723 std::set<SmallVector<int, 4>> UniqueShuffles;
5728 unsigned NumFullVectors =
Mask.size() / MaxElementsInVector;
5729 if (NumFullVectors < 2)
5730 return C + ShuffleCost;
5731 SmallVector<int, 4> SubShuffle(MaxElementsInVector);
5732 unsigned NumUniqueGroups = 0;
5733 unsigned NumGroups =
Mask.size() / MaxElementsInVector;
5736 for (
unsigned I = 0;
I < NumFullVectors; ++
I) {
5737 for (
unsigned J = 0; J < MaxElementsInVector; ++J)
5738 SubShuffle[J] = Mask[MaxElementsInVector *
I + J];
5739 if (UniqueShuffles.insert(SubShuffle).second)
5740 NumUniqueGroups += 1;
5742 return C + ShuffleCost * NumUniqueGroups / NumGroups;
5748 SmallVector<int, 16>
Mask;
5749 SV->getShuffleMask(Mask);
5750 return AddShuffleMaskAdjustedCost(
C, Mask);
5753 auto AllShufflesHaveSameOperands =
5754 [](SmallPtrSetImpl<Instruction *> &InputShuffles) {
5755 if (InputShuffles.size() < 2)
5757 ShuffleVectorInst *FirstSV =
5764 std::next(InputShuffles.begin()), InputShuffles.end(),
5765 [&](Instruction *
I) {
5766 ShuffleVectorInst *SV = dyn_cast<ShuffleVectorInst>(I);
5767 return SV && SV->getOperand(0) == In0 && SV->getOperand(1) == In1;
5776 CostBefore += std::accumulate(Shuffles.begin(), Shuffles.end(),
5778 if (AllShufflesHaveSameOperands(InputShuffles)) {
5779 UniqueShuffles.clear();
5780 CostBefore += std::accumulate(InputShuffles.begin(), InputShuffles.end(),
5783 CostBefore += std::accumulate(InputShuffles.begin(), InputShuffles.end(),
5789 FixedVectorType *Op0SmallVT =
5791 FixedVectorType *Op1SmallVT =
5796 UniqueShuffles.clear();
5797 CostAfter += std::accumulate(ReconstructMasks.begin(), ReconstructMasks.end(),
5799 std::set<SmallVector<int>> OutputShuffleMasks({V1A, V1B, V2A, V2B});
5801 std::accumulate(OutputShuffleMasks.begin(), OutputShuffleMasks.end(),
5804 LLVM_DEBUG(
dbgs() <<
"Found a binop select shuffle pattern: " <<
I <<
"\n");
5806 <<
" vs CostAfter: " << CostAfter <<
"\n");
5807 if (CostBefore < CostAfter ||
5818 if (InputShuffles.contains(SSV))
5820 return SV->getOperand(
Op);
5824 GetShuffleOperand(SVI0A, 1), V1A);
5827 GetShuffleOperand(SVI0B, 1), V1B);
5830 GetShuffleOperand(SVI1A, 1), V2A);
5833 GetShuffleOperand(SVI1B, 1), V2B);
5838 I->copyIRFlags(Op0,
true);
5843 I->copyIRFlags(Op1,
true);
5845 for (
int S = 0,
E = ReconstructMasks.size(); S !=
E; S++) {
5848 replaceValue(*Shuffles[S], *NSV,
false);
5860bool VectorCombine::shrinkType(Instruction &
I) {
5861 Value *ZExted, *OtherOperand;
5867 Value *ZExtOperand =
I.getOperand(
I.getOperand(0) == OtherOperand ? 1 : 0);
5871 unsigned BW = SmallTy->getElementType()->getPrimitiveSizeInBits();
5873 if (
I.getOpcode() == Instruction::LShr) {
5890 Instruction::ZExt, BigTy, SmallTy,
5891 TargetTransformInfo::CastContextHint::None,
CostKind);
5896 for (User *U : ZExtOperand->
users()) {
5903 ShrinkCost += ZExtCost;
5918 ShrinkCost += ZExtCost;
5925 Instruction::Trunc, SmallTy, BigTy,
5926 TargetTransformInfo::CastContextHint::None,
CostKind);
5931 if (ShrinkCost > CurrentCost)
5935 Value *Op0 = ZExted;
5938 if (
I.getOperand(0) == OtherOperand)
5943 NewBinOpI->copyIRFlags(&
I);
5944 NewBinOpI->copyMetadata(
I);
5947 replaceValue(
I, *NewZExtr);
5953bool VectorCombine::foldInsExtVectorToShuffle(Instruction &
I) {
5954 Value *DstVec, *SrcVec;
5965 if (!DstVecTy || !SrcVecTy ||
5971 if (InsIdx >= NumDstElts || ExtIdx >= NumSrcElts || NumDstElts == 1)
5978 bool NeedExpOrNarrow = NumSrcElts != NumDstElts;
5980 if (NeedDstSrcSwap) {
5982 Mask[InsIdx] = ExtIdx % NumDstElts;
5986 std::iota(
Mask.begin(),
Mask.end(), 0);
5987 Mask[InsIdx] = (ExtIdx % NumDstElts) + NumDstElts;
6000 SmallVector<int> ExtToVecMask;
6001 if (!NeedExpOrNarrow) {
6006 nullptr, {DstVec, SrcVec});
6012 ExtToVecMask[ExtIdx % NumDstElts] = ExtIdx;
6015 DstVecTy, SrcVecTy,
CostKind, ExtToVecMask);
6019 if (!Ext->hasOneUse())
6022 LLVM_DEBUG(
dbgs() <<
"Found a insert/extract shuffle-like pair: " <<
I
6023 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
6026 if (OldCost < NewCost)
6029 if (NeedExpOrNarrow) {
6030 if (!NeedDstSrcSwap)
6043 replaceValue(
I, *Shuf);
6052bool VectorCombine::foldInsertScalarPartsToShuffle(Instruction &
I) {
6061 Type *EltTy = VecTy->getElementType();
6063 !
DL->typeSizeEqualsStoreSize(EltTy))
6066 unsigned NumElts = VecTy->getNumElements();
6068 Value *Src =
nullptr;
6069 unsigned NumSrcElts = 0;
6075 if (Ins != &
I && !Ins->hasOneUse())
6080 Vec = Ins->getOperand(0);
6082 if (DemandedElts[Idx])
6084 DemandedElts.
setBit(Idx);
6088 Value *Elt = Ins->getOperand(1);
6095 Value *Shift =
nullptr;
6103 unsigned SrcBits =
X->getType()->getIntegerBitWidth();
6104 if (SrcBits % EltBits)
6107 NumSrcElts = SrcBits / EltBits;
6108 }
else if (
X != Src) {
6112 if (ShAmt % EltBits || Part >= NumSrcElts)
6114 Mask[
Idx] =
DL->isBigEndian() ? NumSrcElts - 1 - Part : Part;
6117 for (
Value *V : {Elt == Trunc ? nullptr : Elt, Trunc, Shift}) {
6120 if (!
V->hasOneUse())
6142 bool IsIdentity = NumSrcElts == NumElts &&
6148 LLVM_DEBUG(
dbgs() <<
"Found an insertelement chain of scalar parts: " <<
I
6149 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
6151 if (!OldCost.
isValid() || !NewCost.
isValid() || NewCost >= OldCost)
6156 replaceValue(
I, *Shuf);
6163 return CB->arg_size();
6175 if (
II->hasOperandBundles() ||
6188 OperandTy->getElementCount() != ResultTy->getElementCount())
6197 auto GetSplatOrScalar = [](
Value *V) {
6201 Value *CommonValue = GetSplatOrScalar(
Values.front());
6205 if (GetSplatOrScalar(V) != CommonValue)
6214 for (
const auto &[Index, Member] :
enumerate(Members)) {
6216 if (!Extract || Extract->getNumIndices() != 1 ||
6217 *Extract->idx_begin() != Index)
6225 unsigned Factor = Members.
size();
6236 unsigned OperandIndex) {
6238 for (
Value *Member : Members)
6247 unsigned &NumScanned) {
6248 unsigned Factor = Members.
size();
6251 if (NumScanned + Factor > Opts.vector_combine_max_scan_instrs)
6253 NumScanned += Factor;
6257 !FirstInst->getSingleUndroppableUse())
6262 if (!Inst || !Inst->getSingleUndroppableUse() ||
6283 return Builder.CreateNAryOp(NarrowInst->
getOpcode(), NewOperands);
6285 return Builder.CreateCast(Cast->getOpcode(), NewOperands[0], WideResultTy);
6287 return Builder.CreateCmp(Cmp->getPredicate(), NewOperands[0],
6290 return Builder.CreateSelect(
6291 NewOperands[0], NewOperands[1], NewOperands[2],
"",
6294 return Builder.CreateFreeze(NewOperands[0]);
6296 return Builder.CreateIntrinsic(WideResultTy,
II->getIntrinsicID(),
6307 "deinterleave source must have the interleaved element count");
6314 NewOperands.
reserve(NumOperands);
6315 for (
unsigned Op = 0;
Op != NumOperands; ++
Op) {
6317 Value *NewOperand =
nullptr;
6320 Builder.SetCurrentDebugLocation(NarrowInst->getDebugLoc());
6321 NewOperand = Builder.CreateVectorSplat(WideEC, NewOperand);
6331 Builder.SetCurrentDebugLocation(NarrowInst->getDebugLoc());
6332 auto *WideResultTy =
6379bool VectorCombine::foldInterleaveOfDeinterleaveChains(Instruction &
I) {
6385 if (!Factor || Interleave->hasOperandBundles())
6388 SmallVector<Value *, 8> RootMembers(Interleave->args());
6389 unsigned NumScanned = 0;
6397 replaceValue(*Interleave, *WideValue);
6405bool VectorCombine::foldInterleaveIntrinsics(Instruction &
I) {
6406 if (foldInterleaveOfDeinterleaveChains(
I))
6409 const APInt *SplatVal0, *SplatVal1;
6419 auto *ExtVTy = VectorType::getExtendedElementVectorType(VTy);
6420 unsigned Width = VTy->getElementType()->getIntegerBitWidth();
6429 LLVM_DEBUG(
dbgs() <<
"VC: The cost to cast from " << *ExtVTy <<
" to "
6430 << *
I.getType() <<
" is too high.\n");
6434 APInt NewSplatVal = SplatVal1->
zext(Width * 2);
6435 NewSplatVal <<= Width;
6436 NewSplatVal |= SplatVal0->
zext(Width * 2);
6438 ExtVTy->getElementCount(), ConstantInt::get(
F.getContext(), NewSplatVal));
6473bool VectorCombine::foldDeinterleaveIntrinsics(Instruction &
I) {
6475 if (
DL->isBigEndian())
6478 using namespace PatternMatch;
6479 Value *DeinterleavedVal;
6490 unsigned HalfElementWidth = ElementWidth / 2;
6494 std::array<ExtractValueInst *, 2> OrigFields{};
6495 for (User *Usr :
I.users()) {
6498 if (!
E ||
E->getNumIndices() != 1)
6500 unsigned Idx = *
E->idx_begin();
6502 if (Idx >= 2 || OrigFields[Idx] || !
E->hasNUses(2))
6504 OrigFields[
Idx] =
E;
6508 SmallVector<Instruction *, 2> MergeInsts;
6509 for (
auto *FieldUsr : OrigFields[0]->
users()) {
6517 auto MatchMerge = [&](void) ->
bool {
6520 return match(MergeInsts[0],
6524 match(MergeInsts[1],
6529 if (!MatchMerge()) {
6530 std::swap(MergeInsts[0], MergeInsts[1]);
6545 auto *NewFieldTy = VecTy->getWithNewBitWidth(HalfElementWidth);
6555 if (OldCost <= NewCost || !NewCost.
isValid()) {
6557 dbgs() <<
"VC: New deinterleave2 sequence cost (" << NewCost <<
")"
6558 <<
" is higher than that of the old one (" << OldCost <<
")\n");
6566 Intrinsic::vector_deinterleave2, {NewVecTy}, {NewVecCast});
6567 for (
auto [Idx, MergeInst] :
enumerate(MergeInsts)) {
6569 NewField = Builder.
CreateBitCast(NewField, MergeInst->getType());
6570 replaceValue(*MergeInst, *NewField);
6576bool VectorCombine::foldBitcastOfVPLoad(Instruction &
I) {
6577 const DataLayout &
DL =
I.getDataLayout();
6592 DL.getValueOrABITypeAlignment(
II->getPointerAlignment(), OrigVecTy);
6593 ElementCount OrigVecCnt = OrigVecTy->getElementCount();
6595 ElementCount NewVecCnt = NewVecTy->getElementCount();
6607 II->getMemoryPointerParam(),
false,
6613 {Intrinsic::vp_load, NewVecTy,
II->getMemoryPointerParam(),
false,
6617 <<
" NewCost=" << NewCost <<
"\n");
6618 if (NewCost > OldCost || !NewCost.
isValid())
6626 NewVecTy, Intrinsic::vp_load,
6627 {
II->getMemoryPointerParam(), NewMask, NewEVL});
6630 0, AttrBuilder(
II->getContext()).addAlignmentAttr(OrigAlign));
6631 replaceValue(*Cast, *NewVP);
6641bool VectorCombine::foldBitOrderReverseAndSwap(Instruction &
I) {
6645 Type *Ty =
X->getType();
6646 Type *VecTy =
I.getOperand(0)->getType();
6660 if (CanUseBswap || CanUseFshl) {
6671 IntrinsicCostAttributes ICABSwap(Intrinsic::bswap, Ty, {Ty});
6672 IntrinsicCostAttributes ICABFshl(Intrinsic::fshl, Ty, {
X,
X, HalfBW},
6674 IntrinsicCostAttributes ICABRev(Intrinsic::bitreverse, Ty, {Ty});
6679 if (!InnerCall->hasOneUse())
6682 else if (!InnerBitCast->hasOneUse())
6685 <<
"\n OldCost: " << OldCost
6686 <<
" vs NewCost: " << NewCost <<
"\n");
6687 if (NewCost.isValid() && NewCost < OldCost) {
6694 replaceValue(
I, *BRev);
6703 Type *Ty =
I.getType();
6705 TypeSize ElementSize =
DL->getTypeStoreSize(Ty);
6708 Type *NewVecTy = VectorType::get(I8Ty, NewVecCnt);
6721 IntrinsicCostAttributes ICANew(Intrinsic::bitreverse, NewVecTy, {NewVecTy});
6724 InstructionCost NewCost = CastToVecCost + NewIntrinsicCost + CastToOrigCost;
6725 if (!InnerII->hasOneUse())
6728 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
6730 if (!NewCost.
isValid() || NewCost >= OldCost)
6738 replaceValue(
I, *CastToOrig);
6748 unsigned RawNumElements = MaxIdx + 1u;
6752 return RawNumElements;
6756 return RawNumElements;
6761 return RawNumElements;
6766 if (ElemsPerReg == 0 || RawNumElements <= ElemsPerReg)
6767 return RawNumElements;
6769 return alignTo(RawNumElements, ElemsPerReg);
6773bool VectorCombine::shrinkLoadForShuffles(Instruction &
I) {
6775 if (!OldLoad || !OldLoad->isSimple())
6782 unsigned const OldNumElements = OldLoadTy->getNumElements();
6788 using IndexRange = std::pair<int, int>;
6789 auto GetIndexRangeInShuffles = [&]() -> std::optional<IndexRange> {
6790 IndexRange OutputRange = IndexRange(OldNumElements, -1);
6791 for (llvm::Use &Use :
I.uses()) {
6793 User *Shuffle =
Use.getUser();
6798 return std::nullopt;
6805 for (
int Index : Mask) {
6806 if (Index >= 0 && Index <
static_cast<int>(OldNumElements)) {
6807 OutputRange.first = std::min(Index, OutputRange.first);
6808 OutputRange.second = std::max(Index, OutputRange.second);
6813 if (OutputRange.second < OutputRange.first)
6814 return std::nullopt;
6820 if (std::optional<IndexRange> Indices = GetIndexRangeInShuffles()) {
6821 unsigned const NewNumElements =
6826 if (NewNumElements < OldNumElements) {
6831 Type *ElemTy = OldLoadTy->getElementType();
6833 Value *PtrOp = OldLoad->getPointerOperand();
6836 Instruction::Load, OldLoad->getType(), OldLoad->getAlign(),
6837 OldLoad->getPointerAddressSpace(),
CostKind);
6840 OldLoad->getPointerAddressSpace(),
CostKind);
6842 using UseEntry = std::pair<ShuffleVectorInst *, std::vector<int>>;
6844 unsigned const MaxIndex = NewNumElements * 2u;
6846 for (llvm::Use &Use :
I.uses()) {
6853 ArrayRef<int> OldMask = Shuffle->getShuffleMask();
6859 for (
int Index : OldMask) {
6860 if (Index >=
static_cast<int>(MaxIndex))
6874 dbgs() <<
"Found a load used only by shufflevector instructions: "
6875 <<
I <<
"\n OldCost: " << OldCost
6876 <<
" vs NewCost: " << NewCost <<
"\n");
6878 if (OldCost < NewCost || !NewCost.
isValid())
6884 NewLoad->copyMetadata(
I);
6887 for (UseEntry &Use : NewUses) {
6888 ShuffleVectorInst *Shuffle =
Use.first;
6889 std::vector<int> &NewMask =
Use.second;
6896 replaceValue(*Shuffle, *NewShuffle,
false);
6909bool VectorCombine::shrinkPhiOfShuffles(Instruction &
I) {
6911 if (!Phi ||
Phi->getNumIncomingValues() != 2u)
6915 ArrayRef<int> Mask0;
6916 ArrayRef<int> Mask1;
6929 auto const InputNumElements = InputVT->getNumElements();
6931 if (InputNumElements >= ResultVT->getNumElements())
6936 SmallVector<int, 16> NewMask;
6939 for (
auto [
M0,
M1] :
zip(Mask0, Mask1)) {
6940 if (
M0 >= 0 &&
M1 >= 0)
6942 else if (
M0 == -1 &&
M1 == -1)
6955 int MaskOffset = NewMask[0
u];
6956 unsigned Index = (InputNumElements + MaskOffset) % InputNumElements;
6959 for (
unsigned I = 0u;
I < InputNumElements; ++
I) {
6973 <<
"\n OldCost: " << OldCost <<
" vs NewCost: " << NewCost
6976 if (NewCost > OldCost)
6987 auto *NewPhi = Builder.
CreatePHI(NewShuf0->getType(), 2u);
6989 NewPhi->addIncoming(
Op,
Phi->getIncomingBlock(1u));
6995 replaceValue(*Phi, *NewShuf1);
7001bool VectorCombine::run() {
7002 if (Opts.disable_vector_combine)
7015 auto Opcode =
I.getOpcode();
7023 if (IsFixedVectorType) {
7025 case Instruction::InsertElement:
7026 if (vectorizeLoadInsert(
I))
7029 case Instruction::ShuffleVector:
7030 if (widenSubvectorLoad(
I))
7041 if (scalarizeOpOrCmp(
I))
7043 if (scalarizeLoad(
I))
7045 if (scalarizeExtExtract(
I))
7047 if (foldInterleaveIntrinsics(
I))
7049 if (foldBitcastOfVPLoad(
I))
7053 if (foldDeinterleaveIntrinsics(
I))
7056 if (Opcode == Instruction::Store)
7057 if (foldInsertElementsToStores(
I))
7061 if (TryEarlyFoldsOnly)
7064 if (Opcode == Instruction::Call)
7065 if (foldBitOrderReverseAndSwap(
I))
7067 if (Opcode == Instruction::BitCast)
7068 if (foldBitOrderReverseAndSwap(
I))
7075 if (IsFixedVectorType) {
7077 case Instruction::InsertElement:
7078 if (foldInsExtFNeg(
I))
7080 if (foldInsExtBinop(
I))
7082 if (foldInsExtVectorToShuffle(
I))
7084 if (foldInsertScalarPartsToShuffle(
I))
7087 case Instruction::ShuffleVector:
7088 if (foldPermuteOfBinops(
I))
7090 if (foldShuffleOfBinops(
I))
7092 if (foldShuffleOfSelects(
I))
7094 if (foldShuffleOfCastops(
I))
7096 if (foldShuffleOfShuffles(
I))
7098 if (foldPermuteOfIntrinsic(
I))
7100 if (foldShufflesOfLengthChangingShuffles(
I))
7102 if (foldShuffleOfIntrinsics(
I))
7104 if (foldSelectShuffle(
I))
7106 if (foldShuffleToIdentity(
I))
7109 case Instruction::Load:
7110 if (shrinkLoadForShuffles(
I))
7113 case Instruction::BitCast:
7114 if (foldBitcastShuffle(
I))
7116 if (foldSelectsFromBitcast(
I))
7119 case Instruction::And:
7120 case Instruction::Or:
7121 case Instruction::Xor:
7122 if (foldBitOpOfCastops(
I))
7124 if (foldBitOpOfCastConstant(
I))
7127 case Instruction::PHI:
7128 if (shrinkPhiOfShuffles(
I))
7138 case Instruction::Call:
7139 if (foldShuffleFromReductions(
I))
7141 if (foldCastFromReductions(
I))
7144 case Instruction::ExtractElement:
7145 if (foldShuffleChainsToReduce(
I))
7148 case Instruction::ICmp:
7149 if (foldSignBitReductionCmp(
I))
7151 if (foldICmpEqZeroVectorReduce(
I))
7153 if (foldReductionZeroTest(
I))
7155 if (foldEquivalentReductionCmp(
I))
7157 if (foldReduceAddCmpZero(
I))
7160 case Instruction::FCmp:
7161 if (foldExtractExtract(
I))
7164 case Instruction::Or:
7165 if (foldConcatOfBoolMasks(
I))
7170 if (foldExtractExtract(
I))
7172 if (foldExtractedCmps(
I))
7174 if (foldBinopOfReductions(
I))
7183 bool MadeChange =
false;
7184 for (BasicBlock &BB :
F) {
7196 MadeChange |= FoldInst(*
I);
7203 while (!Worklist.isEmpty()) {
7206 while (Instruction *
I = Worklist.popDeferred()) {
7224 MadeChange |= FoldInst(*
I);
7240 F.getContext().getLibraryOptions().get<VectorizeOptions>(),
F,
TTI, DT,
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static const Function * getParent(const Value *V)
This is the interface for LLVM's primary stateless and local alias analysis.
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
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 Value * widenDeinterleavedOperations(ArrayRef< Value * > Members, ElementCount WideEC, IRBuilderBase &Builder)
static bool isEquivBitcast(Value *X, Value *Y)
Helper to peek through bitcasts to the same value.
static SmallVector< Value *, 8 > getInstrOperandsAtIdx(ArrayRef< Value * > Members, unsigned OperandIndex)
Return the operand at OperandIndex of each Members.
static bool isFreeConcat(ArrayRef< InstLane > Item, TTI::TargetCostKind CostKind, const TargetTransformInfo &TTI)
Detect concat of multiple values into a vector.
static void analyzeCostOfVecReduction(const IntrinsicInst &II, TTI::TargetCostKind CostKind, const TargetTransformInfo &TTI, InstructionCost &CostBeforeReduction, InstructionCost &CostAfterReduction)
static Value * generateNewInstTree(ArrayRef< InstLane > Item, Use *From, const DenseSet< std::pair< Value *, Use * > > &IdentityLeafs, const DenseSet< std::pair< Value *, Use * > > &SplatLeafs, const DenseSet< std::pair< Value *, Use * > > &ConcatLeafs, IRBuilderBase &Builder, InstructionWorklist &WorkList, const TargetTransformInfo *TTI)
static SmallVector< InstLane > generateInstLaneVectorFromOperand(ArrayRef< InstLane > Item, int Op)
static Value * createShiftShuffle(Value *Vec, unsigned OldIndex, unsigned NewIndex, IRBuilderBase &Builder)
Create a shuffle that translates (shifts) 1 element from the input vector to a new element location.
std::pair< Value *, int > InstLane
static Value * createWideInstruction(Instruction *NarrowInst, ArrayRef< Value * > NewOperands, VectorType *WideResultTy, IRBuilderBase &Builder)
static unsigned getNumDataOperands(const Instruction *Inst)
Return the number of data operands of Inst.
static bool isKnownNonPositive(const Value *V, const SimplifyQuery &SQ, unsigned Depth=0)
Used by foldReduceAddCmpZero to check if we can prove that a value is non-positive.
static bool isSupportedElementwise(Instruction *Inst)
Return true if Inst is an elementwise operation that can be rebuilt at a wider element count.
static Value * materializeScalarizedGEPIndex(Value *Idx, IntegerType *GEPIndexTy, IRBuilderBase &Builder)
Materialize an index for a scalarized GEP after profitability is known.
static Align computeAlignmentAfterScalarization(Align VectorAlignment, Type *ScalarType, Value *Idx, const DataLayout &DL)
The memory operation on a vector of ScalarType had alignment of VectorAlignment.
static bool feedsIntoVectorReduction(ShuffleVectorInst *SVI)
Returns true if this ShuffleVectorInst eventually feeds into a vector reduction intrinsic (e....
static bool canWidenDeinterleavedOperations(const VectorizeOptions &Opts, ArrayRef< Value * > Members, unsigned &NumScanned)
Check whether the tree of elementwise operations each feeding Members can be rebuilt at the interleav...
static bool canWidenLoad(LoadInst *Load, const TargetTransformInfo &TTI)
static const unsigned InvalidIndex
static Value * getCommonSplatValue(ArrayRef< Value * > Values)
Return the common splat value of Values.
static IntegerType * getScalarizedGEPIndexInfo(VectorType *VecTy, Value *Idx, Type *PtrTy, const DataLayout &DL)
Return the GEP index type if the unsigned vector index Idx can be represented by an inbounds GEP.
static Value * translateExtract(ExtractElementInst *ExtElt, unsigned NewIndex, IRBuilderBase &Builder)
Given an extract element instruction with constant index operand, shuffle the source vector (shift th...
static ScalarizationResult canScalarizeAccess(VectorType *VecTy, Value *Idx, const SimplifyQuery &SQ)
Check if it is legal to scalarize a memory access to VecTy at index Idx.
static unsigned getAlignedNumElements(unsigned MaxIdx, FixedVectorType *LoadTy, const TargetTransformInfo &TTI, const DataLayout &DL)
Given the maximum shuffle index and load vector type, compute the number of elements for the shrunk l...
static InstLane lookThroughShuffles(Value *V, int Lane)
static IntrinsicInst * getCommonDeinterleavedSource(ArrayRef< Value * > Members)
Return the common deinterleave intrinsic if Members are its extracts in field order.
static bool isMemModifiedBetween(const VectorizeOptions &Opts, BasicBlock::iterator Begin, BasicBlock::iterator End, const MemoryLocation &Loc, AAResults &AA)
static constexpr int Concat[]
A manager for alias analyses.
Class for arbitrary precision integers.
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
uint64_t getZExtValue() const
Get zero extended value.
void setBit(unsigned BitPosition)
Set the given bit to 1 whose position is given as "bitPosition".
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
unsigned getBitWidth() const
Return the number of bits in the APInt.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
bool isNegative() const
Determine sign of this APInt.
unsigned countl_one() const
Count the number of leading one bits.
LLVM_ABI APInt sext(unsigned width) const
Sign extend to a new width.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Constructs an APInt value that has the top hiBitsSet bits set.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
bool isOne() const
Determine if this is a value of 1.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Represent a constant reference to an array (0 or more elements consecutively in memory),...
ArrayRef< T > drop_front(size_t N=1) const
Drop the first N elements of the array.
const T & front() const
Get the first element.
size_t size() const
Get the array size.
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
InstListType::iterator iterator
Instruction iterators...
BinaryOps getOpcode() const
Represents analyses that only rely on functions' control flow.
Value * getArgOperand(unsigned i) const
void addParamAttrs(unsigned ArgNo, const AttrBuilder &B)
Adds attributes to the indicated argument.
This is the base class for all instructions that perform data casts.
static LLVM_ABI CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass's ...
This class is the base class for the comparison instructions.
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
bool isFPPredicate() const
static LLVM_ABI std::optional< CmpPredicate > getMatching(CmpPredicate A, CmpPredicate B)
Compares two CmpPredicates taking samesign into account and returns the canonicalized CmpPredicate if...
static LLVM_ABI Constant * getExtractElement(Constant *Vec, Constant *Idx, Type *OnlyIfReducedTy=nullptr)
static LLVM_ABI Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false, bool NSZ=false)
Return the identity constant for a binary opcode.
This is the shared class of boolean and integer constants.
const APInt & getValue() const
Return the constant as an APInt value reference.
This class represents a range of values.
LLVM_ABI ConstantRange urem(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned remainder operation of...
LLVM_ABI ConstantRange binaryAnd(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a binary-and of a value in this ra...
LLVM_ABI bool contains(const APInt &Val) const
Return true if the specified value is in the set.
static LLVM_ABI Constant * getSplat(ElementCount EC, Constant *Elt)
Return a ConstantVector with the specified constant in each element.
static LLVM_ABI Constant * get(ArrayRef< Constant * > V)
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
A parsed version of the target data layout string in and methods for querying it.
iterator find(const_arg_type_t< KeyT > Val)
ValueT lookup(const_arg_type_t< KeyT > Val) const
Return the entry for the specified key, or a default constructed value if no such entry exists.
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
Implements a dense probed hash-table based set.
Analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
LLVM_ABI bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
static constexpr ElementCount get(ScalarTy MinVal, bool Scalable)
Convenience struct for specifying and reasoning about fast-math flags.
bool noSignedZeros() const
Class to represent fixed width SIMD vectors.
unsigned getNumElements() const
static FixedVectorType * getDoubleElementsVectorType(FixedVectorType *VTy)
static LLVM_ABI FixedVectorType * get(Type *ElementType, unsigned NumElts)
This class represents a freeze function that returns random concrete value if an operand is either a ...
Predicate getSignedPredicate() const
For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.
bool isEquality() const
Return true if this predicate is either EQ or NE.
Common base class shared among various IRBuilders.
LLVM_ABI CallInst * CreateIntrinsicWithoutFolding(Intrinsic::ID ID, ArrayRef< Type * > OverloadTypes, ArrayRef< Value * > Args, FMFSource FMFSource={}, const Twine &Name="", ArrayRef< OperandBundleDef > OpBundles={})
Create a call to intrinsic ID with Args, mangled using OverloadTypes.
Value * CreateNUWMul(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateInsertElement(Type *VecTy, Value *NewElt, Value *Idx, const Twine &Name="")
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
LoadInst * CreateAlignedLoad(Type *Ty, Value *Ptr, MaybeAlign Align, const char *Name)
Value * CreateNoWrapBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, bool IsNUW, bool IsNSW, const Twine &Name="")
LLVM_ABI Value * CreateSelectFMF(Value *C, Value *True, Value *False, FMFSource FMFSource, const Twine &Name="", Instruction *MDFrom=nullptr)
LLVM_ABI Value * CreateVectorSplat(unsigned NumElts, Value *V, const Twine &Name="")
Return a vector value that contains.
Value * CreateExtractValue(Value *Agg, ArrayRef< unsigned > Idxs, const Twine &Name="")
ConstantInt * getTrue()
Get the constant value for i1 true.
LLVM_ABI Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Value * CreateFreeze(Value *V, const Twine &Name="")
void SetCurrentDebugLocation(const DebugLoc &L)
Set location information used by debugging information.
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Value * CreateCast(Instruction::CastOps Op, Value *V, Type *DestTy, const Twine &Name="", MDNode *FPMathTag=nullptr, FMFSource FMFSource={})
Value * CreateIsNotNeg(Value *Arg, const Twine &Name="")
Return a boolean value testing if Arg > -1.
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
Value * CreatePointerBitCastOrAddrSpaceCast(Value *V, Type *DestTy, const Twine &Name="")
Value * CreateFCmpFMF(CmpInst::Predicate P, Value *LHS, Value *RHS, FMFSource FMFSource, const Twine &Name="", MDNode *FPMathTag=nullptr)
ConstantInt * getInt64(uint64_t C)
Get a constant 64-bit value.
LLVM_ABI Value * CreateOrReduce(Value *Src)
Create a vector int OR reduction intrinsic of the source vector.
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Value * CreateCmp(CmpInst::Predicate Pred, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
PHINode * CreatePHI(Type *Ty, unsigned NumReservedValues, const Twine &Name="")
InstTy * Insert(InstTy *I, const Twine &Name="") const
Insert and return the specified instruction.
Value * CreateBinOpFMF(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, FMFSource FMFSource, const Twine &Name="", MDNode *FPMathTag=nullptr)
Value * CreateIsNeg(Value *Arg, const Twine &Name="")
Return a boolean value testing if Arg < 0.
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
LoadInst * CreateLoad(Type *Ty, Value *Ptr, const char *Name)
Provided to resolve 'CreateLoad(Ty, Ptr, "...")' correctly, instead of converting the string to 'bool...
Value * CreateUnOpFMF(Instruction::UnaryOps Opc, Value *V, FMFSource FMFSource, const Twine &Name="", MDNode *FPMathTag=nullptr)
Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
Value * CreateShuffleVector(Value *V1, Value *V2, Value *Mask, const Twine &Name="")
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
LLVM_ABI Value * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > OverloadTypes, ArrayRef< Value * > Args, FMFSource FMFSource={}, const Twine &Name="", ArrayRef< OperandBundleDef > OpBundles={}, function_ref< void(CallInst *)> SetFn=[](CallInst *) {})
Variant to create a possibly constant-folded intrinsic.
StoreInst * CreateStore(Value *Val, Value *Ptr, bool isVolatile=false)
Value * CreateExactBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, bool IsExact, const Twine &Name="")
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
PointerType * getPtrTy(unsigned AddrSpace=0)
Fetch the type representing a pointer.
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateFNegFMF(Value *V, FMFSource FMFSource, const Twine &Name="", MDNode *FPMathTag=nullptr)
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="", bool IsDisjoint=false)
IntegerType * getInt8Ty()
Fetch the type representing an 8-bit integer.
LLVM_ABI Value * CreateUnaryIntrinsic(Intrinsic::ID ID, Value *Op, FMFSource FMFSource={}, const Twine &Name="")
Create a call to intrinsic ID with 1 operand which is mangled on its type.
Provides an 'InsertHelper' that calls a user-provided callback after performing the default insertion...
InstSimplifyFolder - Use InstructionSimplify to fold operations to existing values.
CostType getValue() const
This function is intended to be used as sparingly as possible, since the class provides the full rang...
InstructionWorklist - This is the worklist management logic for InstCombine and other simplification ...
void push(Instruction *I)
Push the instruction onto the worklist stack.
void remove(Instruction *I)
Remove I from the worklist if it exists.
LLVM_ABI void setHasNoUnsignedWrap(bool b=true)
Set or clear the nuw flag on this instruction, which must be an operator which supports this flag.
LLVM_ABI void copyIRFlags(const Value *V, bool IncludeWrapFlags=true)
Convenience method to copy supported exact, fast-math, and (optionally) wrapping flags from V to this...
LLVM_ABI void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
LLVM_ABI void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
LLVM_ABI void setNonNeg(bool b=true)
Set or clear the nneg flag on this instruction, which must be a zext instruction.
LLVM_ABI bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
iterator_range< user_iterator > users()
LLVM_ABI void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
LLVM_ABI FastMathFlags getFastMathFlags() const LLVM_READONLY
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
@ 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.
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.
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