647 class ScheduleEntity;
649 class ScheduleCopyableData;
650 class ScheduleBundle;
688 : BatchAA(*Aa), F(Func), SE(Se), TTI(Tti), TLI(TLi), LI(Li), DT(Dt),
708 MinVecRegSize = TTI->getMinVectorRegisterBitWidth();
721 ArrayRef<std::tuple<WeakTrackingVH, unsigned, bool, bool>>
722 VectorValuesAndScales = {});
746 const SmallDenseSet<Value *> &UserIgnoreLst);
754 NarrowedChainInsts.insert(Insts.
begin(), Insts.
end());
761 return HasRuntimeCheckableBlockers;
768 HasRuntimeCheckableBlockers = V;
791 HasRuntimeCheckableBlockers =
false;
792 HasNonCheckableMemBlocker =
false;
793 RTChecksFinalized =
false;
795 RTOrigBodyOrder.clear();
816 return ScalarFallbackBlocks.contains(BB);
822 return FailedRuntimeChecksBlocks.contains(BB);
828 FailedRuntimeChecksBlocks.insert(BB);
844 assert(!VectorizableTree.empty() &&
"No graph to get the first node from");
845 return *VectorizableTree.front();
849 assert(!VectorizableTree.empty() &&
"No graph to get the first node from");
850 return *VectorizableTree.front();
865 if (Root.State != TreeEntry::Vectorize || Root.isAltShuffle() ||
866 !Root.Scalars.
front()->getType()->isIntegerTy())
868 auto It = MinBWs.find(&Root);
869 if (It != MinBWs.end())
873 if (Root.getOpcode() == Instruction::ZExt ||
874 Root.getOpcode() == Instruction::SExt)
875 return std::make_pair(
cast<CastInst>(Root.getMainOp())->getSrcTy(),
876 Root.getOpcode() == Instruction::SExt);
888 if (ReductionBitWidth == 0 ||
904 (
getRootNode().CombinedOp == TreeEntry::ReducedBitcast ||
905 getRootNode().CombinedOp == TreeEntry::ReducedBitcastBSwap ||
906 getRootNode().CombinedOp == TreeEntry::ReducedBitcastLoads ||
907 getRootNode().CombinedOp == TreeEntry::ReducedBitcastBSwapLoads) &&
914 getRootNode().CombinedOp == TreeEntry::ReducedCmpBitcast &&
933 VectorizableTree.clear();
934 ScalarToTreeEntries.clear();
935 DeletedNodes.clear();
936 TransformedToGatherNodes.clear();
937 OperandsToTreeEntry.clear();
938 ScalarsInSplitNodes.clear();
940 ReassocScalarToTreeEntries.clear();
941 KeptReassocScalars.clear();
942 NonScheduledFirst.clear();
943 EntryToLastInstruction.clear();
944 LastInstructionToPos.clear();
945 LoadEntriesToVectorize.clear();
946 IsGraphTransformMode =
false;
947 GatheredLoadsEntriesFirst.reset();
948 CompressEntryToData.clear();
949 ExternalUses.clear();
950 ExternalUsesAsOriginalScalar.clear();
951 ExternalUsesWithNonUsers.clear();
952 ExternalUseReplacements.clear();
954 HasRuntimeCheckableBlockers =
false;
955 HasNonCheckableMemBlocker =
false;
956 RTChecksFinalized =
false;
957 for (
auto &Iter : BlocksSchedules) {
958 BlockScheduling *BS = Iter.second.get();
962 ReductionBitWidth = 0;
964 CastMaxMinBWSizes.reset();
965 ExtraBitWidthNodes.clear();
966 InstrElementSize.clear();
967 UserIgnoreList =
nullptr;
968 NarrowedChainInsts.clear();
969 PostponedGathers.clear();
970 ValueToGatherNodes.clear();
971 TreeEntryToStridedPtrInfoMap.clear();
972 CurrentLoopNest.clear();
973 MergedLoopBTCs.clear();
989 assert(!Order.
empty() &&
"expected non-empty order");
990 const unsigned Sz = Order.
size();
992 return P.value() ==
P.index() ||
P.value() == Sz;
1005 bool IgnoreReorder);
1018 std::optional<OrdersType>
1060 return MaxVecRegSize;
1065 return MinVecRegSize;
1073 unsigned Limit = std::numeric_limits<unsigned>::max())
const {
1074 auto [It, Inserted] =
1075 NumberOfPartsCache.try_emplace(std::make_tuple(VecTy, ScalarTy, Limit));
1086 unsigned MaxVF =
MaxVFOption.getNumOccurrences() ?
1087 MaxVFOption : TTI->getMaximumVF(ElemWidth, Opcode);
1088 return MaxVF ? MaxVF : UINT_MAX;
1121 Align Alignment,
const int64_t Diff,
1122 const size_t Sz)
const;
1162 Value *Ptr0, StridedPtrInfo &SPtrInfo)
const;
1181 Align CommonAlignment,
1183 StridedPtrInfo &SPtrInfo,
bool IsLoad)
const;
1198 StridedPtrInfo &SPtrInfo,
1199 unsigned *BestVF =
nullptr,
1200 bool TryRecursiveCheck =
true)
const;
1206 auto IsSame = [&](
const TreeEntry *TE) {
return TE->isSame(VL); };
1220 for (
Value *V : VL) {
1224 for (
const TreeEntry *TE : ValueToGatherNodes.lookup(V)) {
1225 if (!Visited.
insert(TE).second)
1236 ListOfKnonwnNonVectorizableLoads.insert(
hash_value(VL));
1240 template <
typename T>
1242 return ListOfKnonwnNonVectorizableLoads.contains(
hash_value(VL));
1267 OS <<
"{User:" << (
UserTE ? std::to_string(
UserTE->Idx) :
"null")
1268 <<
" EdgeIdx:" <<
EdgeIdx <<
"}";
1293 : TLI(TLI), DL(DL), SE(SE), R(R), NumLanes(NumLanes),
1294 MaxLevel(MaxLevel) {}
1352 auto AllUsersAreInternal = [U1, U2,
this](
Value *
V1,
Value *V2) {
1357 auto AllUsersVectorized = [U1, U2,
this](
Value *V) {
1359 return U == U1 || U == U2 || R.isVectorized(U);
1362 return AllUsersVectorized(
V1) && AllUsersVectorized(V2);
1365 if (R.TTI->isLegalBroadcastLoad(
V1->getType(),
1367 ((
int)
V1->getNumUses() == NumLanes ||
1368 AllUsersAreInternal(
V1, V2)))
1378 auto CheckSameEntryOrFail = [&]() {
1383 any_of(TEs2, [&](TreeEntry *E) {
return Set.contains(E); }))
1392 if (LI1->getParent() != LI2->getParent() || !LI1->isSimple() ||
1394 return CheckSameEntryOrFail();
1397 LI1->getType(), LI1->getPointerOperand(), LI2->getType(),
1398 LI2->getPointerOperand(), DL, SE,
true);
1399 if (!Dist || *Dist == 0) {
1402 R.TTI->isLegalMaskedGather(
1405 return CheckSameEntryOrFail();
1409 if (std::abs(*Dist) > NumLanes / 2)
1442 Value *EV2 =
nullptr;
1455 int Dist = Idx2 - Idx1;
1458 if (std::abs(Dist) == 0)
1460 if (std::abs(Dist) > NumLanes / 2)
1467 return CheckSameEntryOrFail();
1473 if (I1->getParent() != I2->getParent())
1474 return CheckSameEntryOrFail();
1483 V->getType() ==
Cond->getType()) ||
1486 V->getType() ==
Cond->getType()))
1512 return CheckSameEntryOrFail();
1546 int ShallowScoreAtThisLevel =
1557 if (CurrLevel == MaxLevel || !(I1 && I2) || I1 == I2 ||
1560 (I1->getNumOperands() > 2 && I2->getNumOperands() > 2) ||
1562 ShallowScoreAtThisLevel))
1563 return ShallowScoreAtThisLevel;
1564 assert(I1 && I2 &&
"Should have early exited.");
1571 if (I1->getNumOperands() != I2->getNumOperands())
1573 for (
unsigned OpIdx1 = 0, NumOperands1 = I1->getNumOperands();
1574 OpIdx1 != NumOperands1; ++OpIdx1) {
1576 int MaxTmpScore = 0;
1577 unsigned MaxOpIdx2 = 0;
1578 bool FoundBest =
false;
1582 ? I2->getNumOperands()
1583 : std::min(I2->getNumOperands(), OpIdx1 + 1);
1584 assert(FromIdx <= ToIdx &&
"Bad index");
1585 for (
unsigned OpIdx2 = FromIdx; OpIdx2 != ToIdx; ++OpIdx2) {
1587 if (Op2Used.
count(OpIdx2))
1592 I1, I2, CurrLevel + 1, {});
1595 TmpScore > MaxTmpScore) {
1596 MaxTmpScore = TmpScore;
1603 Op2Used.
insert(MaxOpIdx2);
1604 ShallowScoreAtThisLevel += MaxTmpScore;
1607 return ShallowScoreAtThisLevel;
1638 struct OperandData {
1639 OperandData() =
default;
1640 OperandData(
Value *V,
bool APO,
bool IsUsed)
1641 : V(V), APO(APO), IsUsed(IsUsed) {}
1651 bool IsUsed =
false;
1660 enum class ReorderingMode {
1674 unsigned ArgSize = 0;
1680 const Loop *L =
nullptr;
1683 OperandData &getData(
unsigned OpIdx,
unsigned Lane) {
1684 return OpsVec[OpIdx][Lane];
1688 const OperandData &getData(
unsigned OpIdx,
unsigned Lane)
const {
1689 return OpsVec[OpIdx][Lane];
1694 for (
unsigned OpIdx = 0, NumOperands = getNumOperands();
1695 OpIdx != NumOperands; ++OpIdx)
1696 for (
unsigned Lane = 0, NumLanes = getNumLanes(); Lane != NumLanes;
1698 OpsVec[OpIdx][Lane].IsUsed =
false;
1702 void swap(
unsigned OpIdx1,
unsigned OpIdx2,
unsigned Lane) {
1703 std::swap(OpsVec[OpIdx1][Lane], OpsVec[OpIdx2][Lane]);
1715 int getSplatScore(
unsigned Lane,
unsigned OpIdx,
unsigned Idx,
1717 Value *IdxLaneV = getData(Idx, Lane).V;
1725 Value *OpIdxLnV = getData(OpIdx, Ln).V;
1730 unsigned UniquesCount = Uniques.
size();
1731 auto IdxIt = Uniques.
find(IdxLaneV);
1732 unsigned UniquesCntWithIdxLaneV =
1733 IdxIt != Uniques.
end() ? UniquesCount : UniquesCount + 1;
1734 Value *OpIdxLaneV = getData(OpIdx, Lane).V;
1735 auto OpIdxIt = Uniques.
find(OpIdxLaneV);
1736 unsigned UniquesCntWithOpIdxLaneV =
1737 OpIdxIt != Uniques.
end() ? UniquesCount : UniquesCount + 1;
1738 if (UniquesCntWithIdxLaneV == UniquesCntWithOpIdxLaneV)
1740 return std::min(
bit_ceil(UniquesCntWithOpIdxLaneV) -
1741 UniquesCntWithOpIdxLaneV,
1742 UniquesCntWithOpIdxLaneV -
1744 ((IdxIt != Uniques.
end() && UsedLanes.
test(IdxIt->second))
1745 ? UniquesCntWithIdxLaneV -
bit_floor(UniquesCntWithIdxLaneV)
1746 :
bit_ceil(UniquesCntWithIdxLaneV) - UniquesCntWithIdxLaneV);
1755 int getExternalUseScore(
unsigned Lane,
unsigned OpIdx,
unsigned Idx)
const {
1756 Value *IdxLaneV = getData(Idx, Lane).V;
1757 Value *OpIdxLaneV = getData(OpIdx, Lane).V;
1769 return R.areAllUsersVectorized(IdxLaneI)
1777 static constexpr int ScoreScaleFactor = 10;
1779 static constexpr int ScoreConstantScaleFactor = 6;
1787 int Lane,
unsigned OpIdx,
unsigned Idx,
1798 getSplatScore(Lane, OpIdx, Idx, UsedLanes) * ScoreScaleFactor;
1799 if (Score <= -SplatScore) {
1803 Score += SplatScore;
1809 const int SF = (LHS == RHS &&
isConstant(LHS))
1810 ? ScoreConstantScaleFactor
1813 Score += getExternalUseScore(Lane, OpIdx, Idx);
1831 std::optional<unsigned>
1832 getBestOperand(
unsigned OpIdx,
int Lane,
int LastLane,
1836 unsigned NumOperands = getNumOperands();
1839 Value *OpLastLane = getData(OpIdx, LastLane).V;
1842 ReorderingMode RMode = ReorderingModes[OpIdx];
1843 if (RMode == ReorderingMode::Failed)
1844 return std::nullopt;
1847 bool OpIdxAPO = getData(OpIdx, Lane).APO;
1853 std::optional<unsigned> Idx;
1857 BestScoresPerLanes.try_emplace(std::make_pair(OpIdx, Lane), 0)
1863 bool IsUsed = RMode == ReorderingMode::Splat ||
1864 RMode == ReorderingMode::Constant ||
1865 RMode == ReorderingMode::Load;
1867 for (
unsigned Idx = 0; Idx != NumOperands; ++Idx) {
1869 OperandData &OpData = getData(Idx, Lane);
1871 bool OpAPO = OpData.APO;
1880 if (OpAPO != OpIdxAPO)
1885 case ReorderingMode::Load:
1886 case ReorderingMode::Opcode: {
1887 bool LeftToRight = Lane > LastLane;
1888 Value *OpLeft = (LeftToRight) ? OpLastLane :
Op;
1889 Value *OpRight = (LeftToRight) ?
Op : OpLastLane;
1890 int Score = getLookAheadScore(OpLeft, OpRight, MainAltOps, Lane,
1891 OpIdx, Idx, IsUsed, UsedLanes);
1892 if (Score >
static_cast<int>(BestOp.Score) ||
1893 (Score > 0 && Score ==
static_cast<int>(BestOp.Score) &&
1896 BestOp.Score = Score;
1897 BestScoresPerLanes[std::make_pair(OpIdx, Lane)] = Score;
1901 case ReorderingMode::Constant:
1903 (!BestOp.Score && L && L->isLoopInvariant(
Op))) {
1907 BestScoresPerLanes[std::make_pair(OpIdx, Lane)] =
1914 case ReorderingMode::Splat:
1916 IsUsed =
Op == OpLastLane;
1917 if (
Op == OpLastLane) {
1919 BestScoresPerLanes[std::make_pair(OpIdx, Lane)] =
1925 case ReorderingMode::Failed:
1931 getData(*BestOp.Idx, Lane).IsUsed = IsUsed;
1935 return std::nullopt;
1942 unsigned getBestLaneToStartReordering()
const {
1943 unsigned Min = UINT_MAX;
1944 unsigned SameOpNumber = 0;
1955 for (
int I = getNumLanes();
I > 0; --
I) {
1956 unsigned Lane =
I - 1;
1957 OperandsOrderData NumFreeOpsHash =
1958 getMaxNumOperandsThatCanBeReordered(Lane);
1961 if (NumFreeOpsHash.NumOfAPOs < Min) {
1962 Min = NumFreeOpsHash.NumOfAPOs;
1963 SameOpNumber = NumFreeOpsHash.NumOpsWithSameOpcodeParent;
1965 HashMap[NumFreeOpsHash.Hash] = std::make_pair(1, Lane);
1966 }
else if (NumFreeOpsHash.NumOfAPOs == Min &&
1967 NumFreeOpsHash.NumOpsWithSameOpcodeParent < SameOpNumber) {
1970 SameOpNumber = NumFreeOpsHash.NumOpsWithSameOpcodeParent;
1971 HashMap[NumFreeOpsHash.Hash] = std::make_pair(1, Lane);
1972 }
else if (NumFreeOpsHash.NumOfAPOs == Min &&
1973 NumFreeOpsHash.NumOpsWithSameOpcodeParent == SameOpNumber) {
1974 auto [It, Inserted] =
1975 HashMap.
try_emplace(NumFreeOpsHash.Hash, 1, Lane);
1981 unsigned BestLane = 0;
1982 unsigned CntMin = UINT_MAX;
1984 if (
Data.second.first < CntMin) {
1985 CntMin =
Data.second.first;
1986 BestLane =
Data.second.second;
1993 struct OperandsOrderData {
1996 unsigned NumOfAPOs = UINT_MAX;
1999 unsigned NumOpsWithSameOpcodeParent = 0;
2013 OperandsOrderData getMaxNumOperandsThatCanBeReordered(
unsigned Lane)
const {
2014 unsigned CntTrue = 0;
2015 unsigned NumOperands = getNumOperands();
2025 bool AllUndefs =
true;
2026 unsigned NumOpsWithSameOpcodeParent = 0;
2030 for (
unsigned OpIdx = 0; OpIdx != NumOperands; ++OpIdx) {
2031 const OperandData &OpData = getData(OpIdx, Lane);
2038 I->getParent() != Parent) {
2039 if (NumOpsWithSameOpcodeParent == 0) {
2040 NumOpsWithSameOpcodeParent = 1;
2042 Parent =
I->getParent();
2044 --NumOpsWithSameOpcodeParent;
2047 ++NumOpsWithSameOpcodeParent;
2056 OperandsOrderData
Data;
2057 Data.NumOfAPOs = std::max(CntTrue, NumOperands - CntTrue);
2058 Data.NumOpsWithSameOpcodeParent = NumOpsWithSameOpcodeParent;
2069 return VL.
size() == getNumLanes();
2071 "Expected same number of lanes");
2072 assert(S.
valid() &&
"InstructionsState is invalid.");
2077 OpsVec.resize(ArgSize);
2078 unsigned NumLanes = VL.
size();
2079 for (OperandDataVec &
Ops : OpsVec)
2080 Ops.resize(NumLanes);
2095 OpsVec[OpIdx][Lane] = {
Operands[OpIdx][Lane],
true,
false};
2098 bool IsInverseOperation =
false;
2101 IsInverseOperation =
2104 assert(
I &&
"Expected instruction");
2112 bool APO = (OpIdx == 0) ?
false : IsInverseOperation;
2113 OpsVec[OpIdx][Lane] = {
Operands[OpIdx][Lane], APO,
false};
2119 unsigned getNumOperands()
const {
return ArgSize; }
2122 unsigned getNumLanes()
const {
return OpsVec[0].size(); }
2125 Value *getValue(
unsigned OpIdx,
unsigned Lane)
const {
2126 return getData(OpIdx, Lane).V;
2130 bool empty()
const {
return OpsVec.empty(); }
2133 void clear() { OpsVec.clear(); }
2138 bool shouldBroadcast(
Value *
Op,
unsigned OpIdx,
unsigned Lane) {
2139 assert(
Op == getValue(OpIdx, Lane) &&
2140 "Op is expected to be getValue(OpIdx, Lane).");
2144 bool OpAPO = getData(OpIdx, Lane).APO;
2145 bool IsInvariant = L && L->isLoopInvariant(
Op);
2147 for (
unsigned Ln = 0, Lns = getNumLanes(); Ln != Lns; ++Ln) {
2151 bool FoundCandidate =
false;
2152 for (
unsigned OpI = 0, OpE = getNumOperands(); OpI != OpE; ++OpI) {
2153 OperandData &
Data = getData(OpI, Ln);
2154 if (
Data.APO != OpAPO ||
Data.IsUsed)
2156 Value *OpILane = getValue(OpI, Lane);
2180 L->isLoopInvariant(
Data.V))) {
2181 FoundCandidate =
true;
2188 if (!FoundCandidate)
2191 return getNumLanes() == 2 || Cnt > 1;
2196 bool canBeVectorized(
Instruction *
Op,
unsigned OpIdx,
unsigned Lane)
const {
2197 assert(
Op == getValue(OpIdx, Lane) &&
2198 "Op is expected to be getValue(OpIdx, Lane).");
2199 bool OpAPO = getData(OpIdx, Lane).APO;
2200 for (
unsigned Ln = 0, Lns = getNumLanes(); Ln != Lns; ++Ln) {
2204 const OperandData &
Data = getData(OpI, Ln);
2205 if (
Data.APO != OpAPO ||
Data.IsUsed)
2207 Value *OpILn = getValue(OpI, Ln);
2208 return (L && L->isLoopInvariant(OpILn)) ||
2221 : TLI(*R.TLI), DL(*R.DL), SE(*R.SE), R(R),
2222 L(R.LI->getLoopFor(S.getMainOp()->
getParent())) {
2224 appendOperands(RootVL,
Operands, S);
2231 : TLI(*R.TLI), DL(*R.DL), SE(*R.SE), R(R), L(R.LI->getLoopFor(BB)) {
2232 assert(!
Operands.empty() &&
"Expected at least one operand column");
2234 OpsVec.resize(ArgSize);
2235 unsigned NumLanes =
Operands.front().size();
2237 Ops.resize(NumLanes);
2239 Ops[Lane] = OperandData(
Operands[OpIdx][Lane],
false,
2248 assert(OpsVec[OpIdx].
size() == getNumLanes() &&
2249 "Expected same num of lanes across all operands");
2250 for (
unsigned Lane = 0, Lanes = getNumLanes(); Lane != Lanes; ++Lane)
2251 OpVL[Lane] = OpsVec[OpIdx][Lane].V;
2259 unsigned NumOperands = getNumOperands();
2260 unsigned NumLanes = getNumLanes();
2280 unsigned FirstLane = getBestLaneToStartReordering();
2283 for (
unsigned OpIdx = 0; OpIdx != NumOperands; ++OpIdx) {
2284 Value *OpLane0 = getValue(OpIdx, FirstLane);
2289 if (shouldBroadcast(OpLane0, OpIdx, FirstLane) ||
2290 !canBeVectorized(OpILane0, OpIdx, FirstLane))
2291 ReorderingModes[OpIdx] = ReorderingMode::Splat;
2293 ReorderingModes[OpIdx] = ReorderingMode::Load;
2295 ReorderingModes[OpIdx] = ReorderingMode::Opcode;
2297 ReorderingModes[OpIdx] = ReorderingMode::Constant;
2300 ReorderingModes[OpIdx] = ReorderingMode::Splat;
2309 auto &&SkipReordering = [
this]() {
2312 for (
const OperandData &
Data : Op0)
2315 ArrayRef(OpsVec).slice(1, getNumOperands() - 1)) {
2316 if (
any_of(
Op, [&UniqueValues](
const OperandData &
Data) {
2321 return UniqueValues.
size() != 2;
2333 if (SkipReordering())
2336 bool StrategyFailed =
false;
2344 for (
unsigned I = 0;
I < NumOperands; ++
I)
2345 MainAltOps[
I].push_back(getData(
I, FirstLane).V);
2348 UsedLanes.
set(FirstLane);
2349 for (
unsigned Distance = 1; Distance != NumLanes; ++Distance) {
2351 for (
int Direction : {+1, -1}) {
2352 int Lane = FirstLane + Direction * Distance;
2353 if (Lane < 0 || Lane >= (
int)NumLanes)
2355 UsedLanes.
set(Lane);
2356 int LastLane = Lane - Direction;
2357 assert(LastLane >= 0 && LastLane < (
int)NumLanes &&
2360 for (
unsigned OpIdx = 0; OpIdx != NumOperands; ++OpIdx) {
2362 std::optional<unsigned> BestIdx =
2363 getBestOperand(OpIdx, Lane, LastLane, ReorderingModes,
2364 MainAltOps[OpIdx], UsedLanes);
2371 swap(OpIdx, *BestIdx, Lane);
2374 StrategyFailed =
true;
2377 if (MainAltOps[OpIdx].
size() != 2) {
2378 OperandData &AltOp = getData(OpIdx, Lane);
2388 if (!StrategyFailed)
2393#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2396 case ReorderingMode::Load:
2398 case ReorderingMode::Opcode:
2400 case ReorderingMode::Constant:
2402 case ReorderingMode::Splat:
2404 case ReorderingMode::Failed:
2425 const unsigned Indent = 2;
2427 for (
const OperandDataVec &OpDataVec : OpsVec) {
2428 OS <<
"Operand " << Cnt++ <<
"\n";
2429 for (
const OperandData &OpData : OpDataVec) {
2430 OS.
indent(Indent) <<
"{";
2431 if (
Value *V = OpData.V)
2435 OS <<
", APO:" << OpData.APO <<
"}\n";
2452 std::pair<std::optional<int>,
int>
2457 int BestScore = Limit;
2458 std::optional<int> Index;
2459 for (
int I :
seq<int>(0, Candidates.size())) {
2461 Candidates[
I].second,
2464 if (Score > BestScore) {
2469 return std::make_pair(Index, BestScore);
2482 DeletedInstructions.insert(
I);
2487 template <
typename T>
2490 ArrayRef<std::tuple<WeakTrackingVH, unsigned, bool, bool>>
2491 VectorValuesAndScales) {
2493 for (T *V : DeadVals) {
2498 for (T *V : DeadVals) {
2499 if (!V || !Processed.
insert(V).second)
2504 for (
Use &U :
I->operands()) {
2506 OpI && !DeletedInstructions.contains(OpI) && OpI->hasOneUser() &&
2508 !ExternalUseReplacements.contains(OpI) &&
2509 (Entries.
empty() ||
none_of(Entries, [&](
const TreeEntry *Entry) {
2510 return Entry->VectorizedValue == OpI;
2514 I->dropAllReferences();
2516 for (T *V : DeadVals) {
2518 if (!
I->getParent())
2523 cast<Instruction>(U.getUser()));
2525 "trying to erase instruction with users.");
2526 I->removeFromParent();
2530 while (!DeadInsts.
empty()) {
2533 if (!VI || !VI->getParent())
2536 "Live instruction found in dead worklist!");
2537 assert(VI->use_empty() &&
"Instructions with uses are not dead.");
2544 for (
Use &OpU : VI->operands()) {
2545 Value *OpV = OpU.get();
2557 if (!DeletedInstructions.contains(OpI) &&
2558 !ExternalUseReplacements.contains(OpI) &&
2559 (!OpI->getType()->isVectorTy() ||
2561 VectorValuesAndScales,
2562 [&](
const std::tuple<WeakTrackingVH, unsigned, bool, bool>
2563 &V) {
return std::get<0>(V) == OpI; })) &&
2568 VI->removeFromParent();
2570 SE->forgetValue(VI);
2577 return AnalyzedReductionsRoots.count(
I);
2582 AnalyzedReductionsRoots.insert(
I);
2587 return AnalyzedReductionVals.contains(
hash_value(VL));
2592 AnalyzedReductionVals.insert(
hash_value(VL));
2596 return AnalyzedScalars.contains(V);
2600 return AnalyzedBundles.contains(
hash_value(VL));
2608 AnalyzedReductionsRoots.clear();
2609 AnalyzedReductionVals.clear();
2610 AnalyzedBundles.clear();
2611 AnalyzedMinBWVals.clear();
2619 return MustGather.contains(V);
2623 return NonScheduledFirst.contains(V);
2629 auto It = ReassocScalarToTreeEntries.find(V);
2630 return It != ReassocScalarToTreeEntries.end() &&
2631 any_of(It->second, [&](
const TreeEntry *E) {
2632 return !DeletedNodes.contains(E) &&
2633 !TransformedToGatherNodes.contains(E);
2639 assert(V &&
"V cannot be nullptr.");
2642 return any_of(getTreeEntries(V), [&](
const TreeEntry *E) {
2643 return !DeletedNodes.contains(E) && !TransformedToGatherNodes.contains(E);
2651 auto *UI = dyn_cast<Instruction>(U);
2652 return UI && isDeleted(UI);
2675 bool collectValuesToDemote(
2676 const TreeEntry &E,
bool IsProfitableToDemoteRoot,
unsigned &
BitWidth,
2679 bool &IsProfitableToDemote,
bool IsTruncRoot)
const;
2688 void buildReorderableOperands(
2696 void reorderNodeWithReuses(TreeEntry &TE,
ArrayRef<int> Mask)
const;
2699 bool areAllUsersVectorized(
2706 uint64_t getNumScalarInsts(
bool HasTreeLoop);
2711 uint64_t getNumVectorInsts(
bool HasTreeLoop);
2719 const TreeEntry *getOperandEntry(
const TreeEntry *E,
unsigned Idx)
const;
2720 TreeEntry *getOperandEntry(TreeEntry *E,
unsigned Idx) {
2721 return const_cast<TreeEntry *
>(
2722 getOperandEntry(
const_cast<const TreeEntry *
>(E), Idx));
2728 Instruction *getRootEntryInstruction(
const TreeEntry &Entry)
const;
2732 getCastContextHint(
const TreeEntry &TE)
const;
2739 uint64_t getScaleToLoopIterations(
const TreeEntry &TE,
2740 Value *Scalar =
nullptr,
2758 uint64_t getGatherNodeEffectiveScale(
const TreeEntry &TE,
2762 uint64_t getEntryEffectiveScale(
const TreeEntry &TE,
2778 getVectorSpillReloadCost(
const TreeEntry *
E,
Type *ScalarTy,
Type *VecTy,
2784 unsigned InterleaveFactor = 0);
2795 bool ResizeAllowed =
false)
const;
2802 Value *vectorizeOperand(TreeEntry *
E,
unsigned NodeIdx);
2807 template <
typename BVTy,
typename ResTy,
typename... Args>
2808 ResTy processBuildVector(
const TreeEntry *
E,
Type *ScalarTy, Args &...Params);
2813 Value *createBuildVector(
const TreeEntry *
E,
Type *ScalarTy);
2819 Instruction &getLastInstructionInBundle(
const TreeEntry *
E);
2826 std::optional<TargetTransformInfo::ShuffleKind>
2838 unsigned NumParts)
const;
2850 std::optional<TargetTransformInfo::ShuffleKind>
2851 isGatherShuffledSingleRegisterEntry(
2854 unsigned SliceSize);
2868 isGatherShuffledEntry(
2871 unsigned NumParts,
bool ForOrder =
false);
2877 Type *ScalarTy)
const;
2881 void setInsertPointAfterBundle(
const TreeEntry *
E);
2891 bool isFullyVectorizableTinyTree(
bool ForReduction)
const;
2896 void tryToVectorizeGatheredLoads(
2898 std::tuple<BasicBlock *, Value *, Type *>,
2906 collectUserStores(
const BoUpSLP::TreeEntry *TE)
const;
2922 findExternalStoreUsersReorderIndices(TreeEntry *TE)
const;
2926 void reorderGatherNode(TreeEntry &TE);
2933 bool matchesShlZExt(
const TreeEntry &TE,
OrdersType &Order,
bool &IsBSwap,
2934 bool &ForLoads)
const;
2938 bool matchesInversedZExtSelect(
2939 const TreeEntry &SelectTE,
2945 bool matchesSelectOfBits(
const TreeEntry &SelectTE)
const;
2950 TreeEntry(VecTreeTy &Container) : Container(Container) {}
2953 SmallVector<int> getCommonMask()
const {
2954 if (State == TreeEntry::SplitVectorize)
2956 SmallVector<int>
Mask;
2958 addMask(Mask, ReuseShuffleIndices);
2963 SmallVector<int> getSplitMask()
const {
2964 assert(State == TreeEntry::SplitVectorize && !ReorderIndices.empty() &&
2965 "Expected only split vectorize node.");
2966 unsigned CommonVF = std::max<unsigned>(
2967 CombinedEntriesWithIndices.back().second,
2968 Scalars.size() - CombinedEntriesWithIndices.back().second);
2969 const unsigned Scale =
getNumElements(Scalars.front()->getType());
2972 for (
auto [Idx,
I] :
enumerate(ReorderIndices)) {
2976 (Idx >= CombinedEntriesWithIndices.back().second
2977 ? CommonVF - CombinedEntriesWithIndices.back().second * Scale
2986 void reorderSplitNode(
unsigned Idx, ArrayRef<int> Mask,
2987 ArrayRef<int> MaskOrder);
2992 if (
Mask.size() != VL.
size() && VL.
size() == Scalars.size())
2993 return std::equal(VL.
begin(), VL.
end(), Scalars.begin());
2996 [Scalars](
Value *V,
int Idx) {
2997 return isa<PoisonValue>(V) ||
2998 (Idx != PoisonMaskElem && V == Scalars[Idx]);
3001 if (!ReorderIndices.empty()) {
3005 SmallVector<int>
Mask;
3007 if (VL.
size() == Scalars.size())
3008 return IsSame(Scalars, Mask);
3009 if (VL.
size() == ReuseShuffleIndices.size()) {
3010 addMask(Mask, ReuseShuffleIndices);
3011 return IsSame(Scalars, Mask);
3015 return IsSame(Scalars, ReuseShuffleIndices);
3019 bool hasEqualOperands(
const TreeEntry &TE)
const {
3020 if (
TE.getNumOperands() != getNumOperands())
3022 SmallBitVector
Used(getNumOperands());
3023 for (
unsigned I = 0,
E = getNumOperands();
I <
E; ++
I) {
3024 unsigned PrevCount =
Used.count();
3025 for (
unsigned K = 0;
K <
E; ++
K) {
3028 if (getOperand(K) ==
TE.getOperand(
I)) {
3034 if (PrevCount ==
Used.count())
3043 unsigned getVectorFactor()
const {
3044 if (!ReuseShuffleIndices.empty())
3045 return ReuseShuffleIndices.size();
3046 return Scalars.size();
3050 bool isGather()
const {
return State == NeedToGather; }
3056 WeakTrackingVH VectorizedValue =
nullptr;
3068 BlendedLoadVectorize,
3081 enum CombinedOpcode {
3083 MinMax = Instruction::OtherOpsEnd + 1,
3086 ReducedBitcastBSwap,
3087 ReducedBitcastLoads,
3088 ReducedBitcastBSwapLoads,
3091 CombinedOpcode CombinedOp = NotCombinedOp;
3094 SmallVector<int, 4> ReuseShuffleIndices;
3097 SmallVector<unsigned, 4> ReorderIndices;
3105 VecTreeTy &Container;
3108 EdgeInfo UserTreeIndex;
3121 SmallVector<unsigned, 1> StructEVIndices;
3127 SmallVector<ValueList, 2> Operands;
3130 SmallPtrSet<const Value *, 4> CopyableElements;
3134 SmallVector<Value *, 4> ReassocScalars;
3139 SmallBitVector ReassocNegatedOps;
3146 unsigned InterleaveFactor = 0;
3149 bool DoesNotNeedToSchedule =
false;
3153 if (Operands.size() < OpIdx + 1)
3154 Operands.resize(OpIdx + 1);
3155 assert(Operands[OpIdx].
empty() &&
"Already resized?");
3157 "Number of operands is greater than the number of scalars.");
3158 Operands[OpIdx].resize(OpVL.
size());
3163 mutable SmallDenseMap<Value *, unsigned> ValueToLane;
3167 unsigned getInterleaveFactor()
const {
return InterleaveFactor; }
3169 void setInterleave(
unsigned Factor) { InterleaveFactor = Factor; }
3172 void setDoesNotNeedToSchedule() { DoesNotNeedToSchedule =
true; }
3175 bool doesNotNeedToSchedule()
const {
return DoesNotNeedToSchedule; }
3180 setOperand(
I, Operands[
I]);
3184 void reorderOperands(ArrayRef<int> Mask) {
3191 assert(OpIdx < Operands.size() &&
"Off bounds");
3192 return Operands[OpIdx];
3197 assert(OpIdx < Operands.size() &&
"Off bounds");
3198 return Operands[OpIdx];
3202 unsigned getNumOperands()
const {
return Operands.size(); }
3205 Value *getSingleOperand(
unsigned OpIdx)
const {
3206 assert(OpIdx < Operands.size() &&
"Off bounds");
3207 assert(!Operands[OpIdx].
empty() &&
"No operand available");
3208 return Operands[OpIdx][0];
3212 bool isAltShuffle()
const {
return S.isAltShuffle(); }
3214 Instruction *getMatchingMainOpOrAltOp(Instruction *
I)
const {
3215 return S.getMatchingMainOpOrAltOp(
I);
3223 if (
I && getMatchingMainOpOrAltOp(
I))
3225 return S.getMainOp();
3228 void setOperations(
const InstructionsState &S) {
3229 assert(S &&
"InstructionsState is invalid.");
3233 Instruction *getMainOp()
const {
return S.getMainOp(); }
3235 Instruction *getAltOp()
const {
return S.getAltOp(); }
3238 unsigned getOpcode()
const {
return S.getOpcode(); }
3240 unsigned getAltOpcode()
const {
return S.getAltOpcode(); }
3242 bool hasState()
const {
return S.valid(); }
3245 void addCopyableElement(
Value *V) {
3246 assert(S.isCopyableElement(V) &&
"Not a copyable element.");
3247 CopyableElements.insert(V);
3251 bool isCopyableElement(
Value *V)
const {
3252 return CopyableElements.contains(V);
3257 bool isExpandedBinOp(
Value *V)
const {
3258 assert(hasState() &&
"InstructionsState is invalid.");
3259 if (isCopyableElement(V))
3261 return S.isExpandedBinOp(V);
3266 bool isExpandedOperand(Instruction *
I,
unsigned Idx)
const {
3267 assert(hasState() &&
"InstructionsState is invalid.");
3268 if (isCopyableElement(
I))
3270 if (!isExpandedBinOp(
I))
3272 return S.isExpandedOperand(
I, Idx);
3276 bool hasCopyableElements()
const {
return !CopyableElements.empty(); }
3279 void addReassocScalar(
Value *V) { ReassocScalars.push_back(V); }
3282 bool hasReassocScalars()
const {
return !ReassocScalars.empty(); }
3288 void setReassocNegatedOps(
const SmallBitVector &NegatedOps) {
3289 assert(NegatedOps.
size() == getNumOperands() &&
3290 "Signs must cover all operand columns.");
3291 ReassocNegatedOps = NegatedOps;
3295 bool isReassocNegatedOp(
unsigned Idx)
const {
3296 return Idx < ReassocNegatedOps.
size() && ReassocNegatedOps[Idx];
3300 const InstructionsState &getOperations()
const {
return S; }
3304 unsigned findLaneForValue(
Value *V)
const {
3305 auto Res = ValueToLane.try_emplace(V, getVectorFactor());
3307 return Res.first->second;
3308 unsigned &FoundLane = Res.first->getSecond();
3311 auto IsMatch = [
V](
Value *S) {
3314 for (
auto *It =
find_if(Scalars, IsMatch), *End = Scalars.end();
3315 It != End; std::advance(It, 1)) {
3318 FoundLane = std::distance(Scalars.begin(), It);
3319 assert(FoundLane < Scalars.size() &&
"Couldn't find extract lane");
3320 if (!ReorderIndices.empty())
3321 FoundLane = ReorderIndices[FoundLane];
3322 assert(FoundLane < Scalars.size() &&
"Couldn't find extract lane");
3323 if (ReuseShuffleIndices.empty())
3325 if (
auto *RIt =
find(ReuseShuffleIndices, FoundLane);
3326 RIt != ReuseShuffleIndices.end()) {
3327 FoundLane = std::distance(ReuseShuffleIndices.begin(), RIt);
3331 assert(FoundLane < getVectorFactor() &&
"Unable to find given value.");
3338 buildAltOpShuffleMask(
const function_ref<
bool(Instruction *)> IsAltOp,
3339 SmallVectorImpl<int> &Mask,
3340 SmallVectorImpl<Value *> *OpScalars =
nullptr,
3341 SmallVectorImpl<Value *> *AltScalars =
nullptr)
const;
3344 bool isNonPowOf2Vec()
const {
3346 return IsNonPowerOf2;
3349 Value *getOrdered(
unsigned Idx)
const {
3350 if (ReorderIndices.empty())
3351 return Scalars[Idx];
3352 SmallVector<int>
Mask;
3354 return Scalars[
Mask[Idx]];
3360 dbgs() << Idx <<
".\n";
3361 for (
unsigned OpI = 0, OpE = Operands.size(); OpI != OpE; ++OpI) {
3362 dbgs() <<
"Operand " << OpI <<
":\n";
3363 for (
const Value *V : Operands[OpI])
3366 dbgs() <<
"Scalars: \n";
3367 for (
Value *V : Scalars) {
3369 << ((S && S.isExpandedBinOp(V)) ?
" [[Expanded]]\n"
3372 dbgs() <<
"State: ";
3373 if (S && hasCopyableElements())
3374 dbgs() <<
"[[Copyable]] ";
3377 if (InterleaveFactor > 0) {
3378 dbgs() <<
"Vectorize with interleave factor " << InterleaveFactor
3381 dbgs() <<
"Vectorize\n";
3384 case ScatterVectorize:
3385 dbgs() <<
"ScatterVectorize\n";
3387 case StridedVectorize:
3388 dbgs() <<
"StridedVectorize\n";
3390 case ExpandVectorize:
3391 dbgs() <<
"ExpandVectorize\n";
3393 case CompressVectorize:
3394 dbgs() <<
"CompressVectorize\n";
3396 case BlendedLoadVectorize:
3397 dbgs() <<
"BlendedLoadVectorize\n";
3400 dbgs() <<
"NeedToGather\n";
3402 case CombinedVectorize:
3403 dbgs() <<
"CombinedVectorize\n";
3405 case SplitVectorize:
3406 dbgs() <<
"SplitVectorize\n";
3410 dbgs() <<
"MainOp: " << *S.getMainOp() <<
"\n";
3411 dbgs() <<
"AltOp: " << *S.getAltOp() <<
"\n";
3413 dbgs() <<
"MainOp: NULL\n";
3414 dbgs() <<
"AltOp: NULL\n";
3416 dbgs() <<
"VectorizedValue: ";
3417 if (VectorizedValue)
3418 dbgs() << *VectorizedValue <<
"\n";
3421 dbgs() <<
"ReuseShuffleIndices: ";
3422 if (ReuseShuffleIndices.empty())
3425 for (
int ReuseIdx : ReuseShuffleIndices)
3426 dbgs() << ReuseIdx <<
", ";
3428 dbgs() <<
"ReorderIndices: ";
3429 for (
unsigned ReorderIdx : ReorderIndices)
3430 dbgs() << ReorderIdx <<
", ";
3432 dbgs() <<
"UserTreeIndex: ";
3434 dbgs() << UserTreeIndex;
3436 dbgs() <<
"<invalid>";
3438 if (!StructEVIndices.empty()) {
3439 dbgs() <<
"StructEVIndices: ";
3443 if (!CombinedEntriesWithIndices.empty()) {
3444 dbgs() <<
"Combined entries: ";
3446 dbgs() <<
"Entry index " <<
P.first <<
" with offset " <<
P.second;
3457 StringRef Banner)
const {
3458 dbgs() <<
"SLP: " << Banner <<
":\n";
3460 dbgs() <<
"SLP: Costs:\n";
3461 dbgs() <<
"SLP: ReuseShuffleCost = " << ReuseShuffleCost <<
"\n";
3462 dbgs() <<
"SLP: VectorCost = " << VecCost <<
"\n";
3463 dbgs() <<
"SLP: ScalarCost = " << ScalarCost <<
"\n";
3464 dbgs() <<
"SLP: ReuseShuffleCost + VecCost - ScalarCost = "
3465 << ReuseShuffleCost + VecCost - ScalarCost <<
"\n";
3471 const InstructionsState &S,
3473 ArrayRef<int> ReuseShuffleIndices = {}) {
3474 auto Invalid = ScheduleBundle::invalid();
3475 return newTreeEntry(VL,
Invalid, S, UserTreeIdx, ReuseShuffleIndices);
3480 const InstructionsState &S,
3482 ArrayRef<int> ReuseShuffleIndices = {},
3483 ArrayRef<unsigned> ReorderIndices = {},
3484 unsigned InterleaveFactor = 0) {
3485 TreeEntry::EntryState EntryState =
3486 Bundle ? TreeEntry::Vectorize : TreeEntry::NeedToGather;
3487 TreeEntry *
E = newTreeEntry(VL, EntryState, Bundle, S, UserTreeIdx,
3488 ReuseShuffleIndices, ReorderIndices);
3489 if (
E && InterleaveFactor > 0)
3490 E->setInterleave(InterleaveFactor);
3495 TreeEntry::EntryState EntryState,
3496 ScheduleBundle &Bundle,
const InstructionsState &S,
3498 ArrayRef<int> ReuseShuffleIndices = {},
3499 ArrayRef<unsigned> ReorderIndices = {}) {
3500 assert(((!Bundle && (EntryState == TreeEntry::NeedToGather ||
3501 EntryState == TreeEntry::SplitVectorize)) ||
3502 (Bundle && EntryState != TreeEntry::NeedToGather &&
3503 EntryState != TreeEntry::SplitVectorize)) &&
3504 "Need to vectorize gather entry?");
3506 if (GatheredLoadsEntriesFirst.has_value() &&
3507 EntryState == TreeEntry::NeedToGather && S &&
3508 S.
getOpcode() == Instruction::Load && UserTreeIdx.EdgeIdx == UINT_MAX &&
3509 !UserTreeIdx.UserTE)
3511 VectorizableTree.push_back(std::make_unique<TreeEntry>(VectorizableTree));
3512 TreeEntry *
Last = VectorizableTree.back().get();
3513 Last->Idx = VectorizableTree.size() - 1;
3514 Last->State = EntryState;
3515 if (UserTreeIdx.UserTE)
3516 OperandsToTreeEntry.try_emplace(
3517 std::make_pair(UserTreeIdx.UserTE, UserTreeIdx.EdgeIdx),
Last);
3518 Last->ReuseShuffleIndices.append(ReuseShuffleIndices.begin(),
3519 ReuseShuffleIndices.end());
3520 if (ReorderIndices.
empty()) {
3523 Last->setOperations(S);
3526 Last->Scalars.assign(VL.
size(),
nullptr);
3528 [VL](
unsigned Idx) ->
Value * {
3529 if (Idx >= VL.size())
3530 return UndefValue::get(VL.front()->getType());
3535 Last->setOperations(S);
3536 Last->ReorderIndices.append(ReorderIndices.
begin(), ReorderIndices.
end());
3538 if (EntryState == TreeEntry::SplitVectorize) {
3539 assert(S &&
"Split nodes must have operations.");
3540 Last->setOperations(S);
3541 SmallPtrSet<Value *, 4> Processed;
3542 for (
Value *V : VL) {
3546 auto It = ScalarsInSplitNodes.find(V);
3547 if (It == ScalarsInSplitNodes.end()) {
3548 ScalarsInSplitNodes.try_emplace(V).first->getSecond().push_back(
Last);
3549 (void)Processed.
insert(V);
3550 }
else if (Processed.
insert(V).second) {
3552 "Value already associated with the node.");
3553 It->getSecond().push_back(
Last);
3556 }
else if (!
Last->isGather()) {
3562 Last->setDoesNotNeedToSchedule();
3563 SmallPtrSet<Value *, 4> Processed;
3564 for (
Value *V : VL) {
3568 Last->addCopyableElement(V);
3571 auto It = ScalarToTreeEntries.find(V);
3572 if (It == ScalarToTreeEntries.end()) {
3573 ScalarToTreeEntries.try_emplace(V).first->getSecond().push_back(
Last);
3574 (void)Processed.
insert(V);
3575 }
else if (Processed.
insert(V).second) {
3577 "Value already associated with the node.");
3578 It->getSecond().push_back(
Last);
3582 assert((!Bundle.getBundle().empty() ||
Last->doesNotNeedToSchedule()) &&
3583 "Bundle and VL out of sync");
3584 if (!Bundle.getBundle().empty()) {
3585#if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
3586 auto *BundleMember = Bundle.getBundle().begin();
3587 SmallPtrSet<Value *, 4> Processed;
3588 for (
Value *V : VL) {
3593 assert(BundleMember == Bundle.getBundle().end() &&
3594 "Bundle and VL out of sync");
3596 Bundle.setTreeEntry(
Last);
3600 bool AllConstsOrCasts =
true;
3601 for (
Value *V : VL) {
3604 Last->addCopyableElement(V);
3607 AllConstsOrCasts &=
I &&
I->getType()->isIntegerTy();
3608 if (UserTreeIdx.EdgeIdx != UINT_MAX || !UserTreeIdx.UserTE ||
3609 !UserTreeIdx.UserTE->isGather())
3610 ValueToGatherNodes.try_emplace(V).first->getSecond().insert(
Last);
3613 if (AllConstsOrCasts)
3615 std::make_pair(std::numeric_limits<unsigned>::max(), 1);
3616 MustGather.insert_range(VL);
3619 if (UserTreeIdx.UserTE)
3620 Last->UserTreeIndex = UserTreeIdx;
3626 TreeEntry::VecTreeTy VectorizableTree;
3631 for (
unsigned Id = 0, IdE = VectorizableTree.size(); Id != IdE; ++Id) {
3632 VectorizableTree[
Id]->dump();
3633 if (TransformedToGatherNodes.contains(VectorizableTree[Id].get()))
3634 dbgs() <<
"[[TRANSFORMED TO GATHER]]";
3635 else if (DeletedNodes.contains(VectorizableTree[Id].get()))
3636 dbgs() <<
"[[DELETED NODE]]";
3644 assert(V &&
"V cannot be nullptr.");
3645 auto It = ScalarToTreeEntries.find(V);
3646 if (It == ScalarToTreeEntries.end())
3648 return It->getSecond();
3653 assert(V &&
"V cannot be nullptr.");
3654 auto It = ScalarsInSplitNodes.find(V);
3655 if (It == ScalarsInSplitNodes.end())
3657 return It->getSecond();
3662 bool SameVF =
false)
const {
3663 assert(V &&
"V cannot be nullptr.");
3664 for (TreeEntry *TE : ScalarToTreeEntries.lookup(V))
3665 if ((!SameVF ||
TE->getVectorFactor() == VL.
size()) &&
TE->isSame(VL))
3672 class ScalarsVectorizationLegality {
3673 InstructionsState S;
3675 bool TryToFindDuplicates;
3676 bool TrySplitVectorize;
3679 ScalarsVectorizationLegality(InstructionsState S,
bool IsLegal,
3680 bool TryToFindDuplicates =
true,
3681 bool TrySplitVectorize =
false)
3682 : S(S), IsLegal(IsLegal), TryToFindDuplicates(TryToFindDuplicates),
3683 TrySplitVectorize(TrySplitVectorize) {
3684 assert((!IsLegal || (S.valid() && TryToFindDuplicates)) &&
3685 "Inconsistent state");
3687 const InstructionsState &getInstructionsState()
const {
return S; };
3688 bool isLegal()
const {
return IsLegal; }
3689 bool tryToFindDuplicates()
const {
return TryToFindDuplicates; }
3690 bool trySplitVectorize()
const {
return TrySplitVectorize; }
3695 ScalarsVectorizationLegality
3697 const EdgeInfo &UserTreeIdx)
const;
3701 TreeEntry::EntryState getScalarsVectorizationState(
3703 bool IsScatterVectorizeUserTE,
OrdersType &CurrentOrder,
3705 SmallVectorImpl<int> &ReuseShuffleIndices);
3708 SmallDenseMap<Value *, SmallVector<TreeEntry *>> ScalarToTreeEntries;
3711 SmallPtrSet<const TreeEntry *, 8> DeletedNodes;
3715 SmallDenseMap<const TreeEntry *, InstructionCost> TransformedToGatherNodes;
3718 SmallDenseMap<std::pair<const TreeEntry *, unsigned>, TreeEntry *>
3719 OperandsToTreeEntry;
3722 SmallDenseMap<Value *, SmallVector<TreeEntry *>> ScalarsInSplitNodes;
3725 SmallDenseMap<Value *, unsigned> InstrElementSize;
3732 SmallDenseMap<const Value *, SmallVector<const TreeEntry *>>
3733 ReassocScalarToTreeEntries;
3738 SmallPtrSet<const Value *, 8> KeptReassocScalars;
3749 SmallDenseMap<const TreeEntry *, WeakTrackingVH> EntryToLastInstruction;
3753 SmallDenseMap<const Instruction *, Instruction *> LastInstructionToPos;
3758 SetVector<const TreeEntry *> PostponedGathers;
3760 using ValueToGatherNodesMap =
3761 DenseMap<Value *, SmallSetVector<const TreeEntry *, 4>>;
3762 ValueToGatherNodesMap ValueToGatherNodes;
3764 SmallDenseMap<TreeEntry *, StridedPtrInfo> TreeEntryToStridedPtrInfoMap;
3769 SetVector<unsigned> LoadEntriesToVectorize;
3772 bool IsGraphTransformMode =
false;
3775 std::optional<unsigned> GatheredLoadsEntriesFirst;
3778 SmallDenseMap<
const TreeEntry *,
3779 std::tuple<SmallVector<int>,
VectorType *, unsigned,
bool>>
3780 CompressEntryToData;
3784 SmallVector<const Loop *> CurrentLoopNest;
3788 SmallVector<const SCEV *> MergedLoopBTCs;
3791 SmallDenseMap<const Loop *, SmallVector<const Loop *>> LoopToLoopNest;
3796 SmallDenseMap<const Loop *, uint64_t> LoopNestScaleCache;
3799 struct ExternalUser {
3800 ExternalUser(
Value *S, llvm::User *U,
const TreeEntry &E,
unsigned L)
3801 : Scalar(S), User(
U), E(E), Lane(
L) {}
3804 Value *Scalar =
nullptr;
3807 llvm::User *User =
nullptr;
3815 using UserList = SmallVector<ExternalUser, 16>;
3821 bool isAliased(
const MemoryLocation &Loc1, Instruction *Inst1,
3822 Instruction *Inst2) {
3825 AliasCacheKey
Key = std::make_pair(Inst1, Inst2);
3826 auto Res = AliasCache.try_emplace(
Key);
3828 return Res.first->second;
3829 bool Aliased =
isModOrRefSet(BatchAA.getModRefInfo(Inst2, Loc1));
3831 Res.first->getSecond() = Aliased;
3838 bool isRuntimeCheckableAliasPair(Instruction *Inst1, Instruction *Inst2);
3843 bool recordRuntimeAliasCheck(BasicBlock *BB, Instruction *Inst1,
3844 Instruction *Inst2);
3848 void versionBlocksForRuntimeChecks();
3853 Value *emitRuntimeAliasCheck(IRBuilderBase &Builder, SCEVExpander &Exp);
3856 struct RuntimeAliasCheckInfo {
3861 SmallSetVector<std::pair<const Value *, const Value *>, 4> BasePairs;
3863 SmallMapVector<const Value *, std::pair<const SCEV *, const SCEV *>, 4>
3876 bool TryRuntimeAliasChecks =
false;
3879 RuntimeAliasCheckInfo RTChecks;
3884 SmallDenseSet<std::pair<const Value *, const Value *>, 4>, 2>
3885 VersionedBlockCheckedPairs;
3888 SmallPtrSet<BasicBlock *, 4> ScalarFallbackBlocks;
3892 SmallPtrSet<BasicBlock *, 8> FailedRuntimeChecksBlocks;
3897 bool isCoveredByExistingVersionCheck(BasicBlock *BB, Instruction *Inst1,
3898 Instruction *Inst2)
const;
3902 bool HasRuntimeCheckableBlockers =
false;
3906 bool HasNonCheckableMemBlocker =
false;
3909 bool RTChecksFinalized =
false;
3913 bool CFGChanged =
false;
3916 SmallVector<Instruction *> RTOrigBodyOrder;
3918 using AliasCacheKey = std::pair<Instruction *, Instruction *>;
3922 SmallDenseMap<AliasCacheKey, bool> AliasCache;
3927 BatchAAResults BatchAA;
3934 DenseSet<Instruction *> DeletedInstructions;
3937 SmallPtrSet<Instruction *, 16> AnalyzedReductionsRoots;
3940 DenseSet<size_t> AnalyzedReductionVals;
3943 SmallDenseSet<size_t, 8> AnalyzedBundles;
3946 SmallPtrSet<const Value *, 32> AnalyzedScalars;
3949 mutable SmallDenseMap<std::tuple<Type *, Type *, unsigned>,
unsigned>
3954 DenseSet<Value *> AnalyzedMinBWVals;
3960 UserList ExternalUses;
3964 SmallPtrSet<Value *, 4> ExternalUsesAsOriginalScalar;
3968 SmallPtrSet<Value *, 4> ExternalUsesWithNonUsers;
3973 SmallPtrSet<Value *, 4> ExternalUseReplacements;
3976 SmallPtrSet<const Value *, 32> EphValues;
3980 SetVector<Instruction *> GatherShuffleExtractSeq;
3983 DenseSet<BasicBlock *> CSEBlocks;
3986 DenseSet<size_t> ListOfKnonwnNonVectorizableLoads;
3993 class ScheduleEntity {
3994 friend class ScheduleBundle;
3995 friend class ScheduleData;
3996 friend class ScheduleCopyableData;
3999 enum class Kind { ScheduleData, ScheduleBundle, ScheduleCopyableData };
4000 Kind getKind()
const {
return K; }
4001 ScheduleEntity(Kind K) : K(K) {}
4005 int SchedulingPriority = 0;
4008 bool IsScheduled =
false;
4010 const Kind K = Kind::ScheduleData;
4013 ScheduleEntity() =
delete;
4015 void setSchedulingPriority(
int Priority) { SchedulingPriority = Priority; }
4016 int getSchedulingPriority()
const {
return SchedulingPriority; }
4017 bool isReady()
const {
4019 return SD->isReady();
4021 return CD->isReady();
4027 bool hasValidDependencies()
const {
4029 return SD->hasValidDependencies();
4031 return CD->hasValidDependencies();
4035 int getUnscheduledDeps()
const {
4037 return SD->getUnscheduledDeps();
4039 return CD->getUnscheduledDeps();
4043 int incrementUnscheduledDeps(
int Incr) {
4045 return SD->incrementUnscheduledDeps(Incr);
4049 int getDependencies()
const {
4051 return SD->getDependencies();
4057 return SD->getInst();
4062 bool isScheduled()
const {
return IsScheduled; }
4063 void setScheduled(
bool Scheduled) { IsScheduled = Scheduled; }
4065 static bool classof(
const ScheduleEntity *) {
return true; }
4067#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4068 void dump(raw_ostream &OS)
const {
4070 return SD->dump(OS);
4072 return CD->dump(OS);
4083#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4085 const BoUpSLP::ScheduleEntity &SE) {
4095 class ScheduleData final :
public ScheduleEntity {
4099 enum { InvalidDeps = -1 };
4101 ScheduleData() : ScheduleEntity(Kind::ScheduleData) {}
4102 static bool classof(
const ScheduleEntity *Entity) {
4103 return Entity->getKind() == Kind::ScheduleData;
4106 void init(
int BlockSchedulingRegionID, Instruction *
I) {
4107 NextLoadStore =
nullptr;
4108 IsScheduled =
false;
4109 SchedulingRegionID = BlockSchedulingRegionID;
4110 clearDependencies();
4116 if (hasValidDependencies()) {
4117 assert(UnscheduledDeps <= Dependencies &&
"invariant");
4119 assert(UnscheduledDeps == Dependencies &&
"invariant");
4123 assert(hasValidDependencies() && UnscheduledDeps == 0 &&
4124 "unexpected scheduled state");
4131 bool hasValidDependencies()
const {
return Dependencies != InvalidDeps; }
4135 bool isReady()
const {
return UnscheduledDeps == 0 && !IsScheduled; }
4140 int incrementUnscheduledDeps(
int Incr) {
4141 assert(hasValidDependencies() &&
4142 "increment of unscheduled deps would be meaningless");
4143 UnscheduledDeps += Incr;
4144 assert(UnscheduledDeps >= 0 &&
4145 "Expected valid number of unscheduled deps");
4146 return UnscheduledDeps;
4151 void resetUnscheduledDeps() { UnscheduledDeps = Dependencies; }
4154 void clearDependencies() {
4155 clearDirectDependencies();
4156 MemoryDependencies.clear();
4157 ControlDependencies.clear();
4164 void clearDirectDependencies() {
4165 Dependencies = InvalidDeps;
4166 resetUnscheduledDeps();
4167 IsScheduled =
false;
4171 int getUnscheduledDeps()
const {
return UnscheduledDeps; }
4173 int getDependencies()
const {
return Dependencies; }
4175 void initDependencies() { Dependencies = 0; }
4177 void incDependencies() { Dependencies++; }
4180 int getSchedulingRegionID()
const {
return SchedulingRegionID; }
4187 return MemoryDependencies;
4190 void addMemoryDependency(ScheduleData *Dep) {
4191 MemoryDependencies.push_back(Dep);
4195 return ControlDependencies;
4198 void addControlDependency(ScheduleData *Dep) {
4199 ControlDependencies.push_back(Dep);
4202 ScheduleData *getNextLoadStore()
const {
return NextLoadStore; }
4203 void setNextLoadStore(ScheduleData *
Next) { NextLoadStore =
Next; }
4205 void dump(raw_ostream &OS)
const { OS << *Inst; }
4217 ScheduleData *NextLoadStore =
nullptr;
4221 SmallVector<ScheduleData *> MemoryDependencies;
4227 SmallVector<ScheduleData *> ControlDependencies;
4231 int SchedulingRegionID = 0;
4237 int Dependencies = InvalidDeps;
4243 int UnscheduledDeps = InvalidDeps;
4248 const BoUpSLP::ScheduleData &SD) {
4254 class ScheduleBundle final :
public ScheduleEntity {
4258 bool IsValid =
true;
4260 TreeEntry *TE =
nullptr;
4261 ScheduleBundle(
bool IsValid)
4262 : ScheduleEntity(Kind::ScheduleBundle), IsValid(IsValid) {}
4265 ScheduleBundle() : ScheduleEntity(Kind::ScheduleBundle) {}
4266 static bool classof(
const ScheduleEntity *Entity) {
4267 return Entity->getKind() == Kind::ScheduleBundle;
4272 for (
const ScheduleEntity *SD : Bundle) {
4273 if (SD->hasValidDependencies()) {
4274 assert(SD->getUnscheduledDeps() <= SD->getDependencies() &&
4277 assert(SD->getUnscheduledDeps() == SD->getDependencies() &&
4281 if (isScheduled()) {
4282 assert(SD->hasValidDependencies() && SD->getUnscheduledDeps() == 0 &&
4283 "unexpected scheduled state");
4289 int unscheduledDepsInBundle()
const {
4290 assert(*
this &&
"bundle must not be empty");
4292 for (
const ScheduleEntity *BundleMember : Bundle) {
4293 if (BundleMember->getUnscheduledDeps() == ScheduleData::InvalidDeps)
4294 return ScheduleData::InvalidDeps;
4295 Sum += BundleMember->getUnscheduledDeps();
4303 bool hasValidDependencies()
const {
4304 return all_of(Bundle, [](
const ScheduleEntity *SD) {
4305 return SD->hasValidDependencies();
4311 bool isReady()
const {
4312 assert(*
this &&
"bundle must not be empty");
4313 return unscheduledDepsInBundle() == 0 && !isScheduled();
4321 void add(ScheduleEntity *SD) { Bundle.push_back(SD); }
4324 void setTreeEntry(TreeEntry *TE) { this->TE = TE; }
4325 TreeEntry *getTreeEntry()
const {
return TE; }
4327 static ScheduleBundle invalid() {
return {
false}; }
4329 operator bool()
const {
return IsValid; }
4332 void dump(raw_ostream &OS)
const {
4341 OS << *SD->getInst();
4355 const BoUpSLP::ScheduleBundle &Bundle) {
4366 class ScheduleCopyableData final :
public ScheduleEntity {
4373 int SchedulingRegionID = 0;
4375 ScheduleBundle &Bundle;
4378 ScheduleCopyableData(
int BlockSchedulingRegionID,
Instruction *
I,
4379 const EdgeInfo &EI, ScheduleBundle &Bundle)
4380 : ScheduleEntity(Kind::ScheduleCopyableData), Inst(
I), EI(EI),
4381 SchedulingRegionID(BlockSchedulingRegionID), Bundle(Bundle) {}
4382 static bool classof(
const ScheduleEntity *Entity) {
4383 return Entity->getKind() == Kind::ScheduleCopyableData;
4388 if (hasValidDependencies()) {
4389 assert(UnscheduledDeps <= Dependencies &&
"invariant");
4391 assert(UnscheduledDeps == Dependencies &&
"invariant");
4395 assert(hasValidDependencies() && UnscheduledDeps == 0 &&
4396 "unexpected scheduled state");
4403 bool hasValidDependencies()
const {
4404 return Dependencies != ScheduleData::InvalidDeps;
4409 bool isReady()
const {
return UnscheduledDeps == 0 && !IsScheduled; }
4414 int incrementUnscheduledDeps(
int Incr) {
4415 assert(hasValidDependencies() &&
4416 "increment of unscheduled deps would be meaningless");
4417 UnscheduledDeps += Incr;
4418 assert(UnscheduledDeps >= 0 &&
"invariant");
4419 return UnscheduledDeps;
4424 void resetUnscheduledDeps() { UnscheduledDeps = Dependencies; }
4427 int getUnscheduledDeps()
const {
return UnscheduledDeps; }
4429 int getDependencies()
const {
return Dependencies; }
4431 void initDependencies() { Dependencies = 0; }
4433 void incDependencies() { Dependencies++; }
4436 int getSchedulingRegionID()
const {
return SchedulingRegionID; }
4442 void clearDependencies() {
4443 Dependencies = ScheduleData::InvalidDeps;
4444 UnscheduledDeps = ScheduleData::InvalidDeps;
4445 IsScheduled =
false;
4449 const EdgeInfo &getEdgeInfo()
const {
return EI; }
4452 ScheduleBundle &getBundle() {
return Bundle; }
4453 const ScheduleBundle &getBundle()
const {
return Bundle; }
4455#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4456 void dump(raw_ostream &OS)
const { OS <<
"[Copyable]" << *getInst(); }
4467 int Dependencies = ScheduleData::InvalidDeps;
4473 int UnscheduledDeps = ScheduleData::InvalidDeps;
4503 struct BlockScheduling {
4505 : BB(BB), ChunkSize(BB->
size()), ChunkPos(ChunkSize) {}
4508 ScheduledBundles.clear();
4509 ScheduledBundlesList.
clear();
4510 ScheduleCopyableDataMap.clear();
4511 ScheduleCopyableDataMapByInst.clear();
4512 ScheduleCopyableDataMapByInstUser.clear();
4513 ScheduleCopyableDataMapByUsers.clear();
4515 RecalcCopyableOperandDeps.
clear();
4516 IgnoredMemDeps.clear();
4517 ScheduleStart =
nullptr;
4518 ScheduleEnd =
nullptr;
4519 FirstLoadStoreInRegion =
nullptr;
4520 LastLoadStoreInRegion =
nullptr;
4521 RegionHasStackSave =
false;
4525 ScheduleRegionSizeLimit -= ScheduleRegionSize;
4528 ScheduleRegionSize = 0;
4532 ++SchedulingRegionID;
4535 ScheduleData *getScheduleData(Instruction *
I) {
4538 if (BB !=
I->getParent())
4541 ScheduleData *SD = ScheduleDataMap.lookup(
I);
4542 if (SD && isInSchedulingRegion(*SD))
4547 ScheduleData *getScheduleData(
Value *V) {
4553 ScheduleCopyableData *getScheduleCopyableData(
const EdgeInfo &EI,
4554 const Value *V)
const {
4555 if (ScheduleCopyableDataMap.empty())
4557 auto It = ScheduleCopyableDataMap.find(std::make_pair(EI, V));
4558 if (It == ScheduleCopyableDataMap.end())
4560 ScheduleCopyableData *SD = It->getSecond().get();
4561 if (!isInSchedulingRegion(*SD))
4569 getScheduleCopyableData(
const Value *User,
unsigned OperandIdx,
4571 if (ScheduleCopyableDataMapByInstUser.empty())
4573 const auto It = ScheduleCopyableDataMapByInstUser.find(
4574 std::make_pair(std::make_pair(User, OperandIdx), V));
4575 if (It == ScheduleCopyableDataMapByInstUser.end())
4578 for (ScheduleCopyableData *SD : It->getSecond()) {
4579 if (isInSchedulingRegion(*SD))
4593 bool areAllOperandsReplacedByCopyableData(Instruction *User,
4597 if (ScheduleCopyableDataMap.empty())
4599 SmallDenseMap<TreeEntry *, unsigned> PotentiallyReorderedEntriesCount;
4601 if (Entries.
empty())
4603 unsigned CurNumOps = 0;
4604 for (
const Use &U :
User->operands()) {
4610 for (TreeEntry *TE : Entries) {
4612 bool IsNonSchedulableWithParentPhiNode =
4613 TE->doesNotNeedToSchedule() &&
TE->UserTreeIndex &&
4614 TE->UserTreeIndex.UserTE->hasState() &&
4615 TE->UserTreeIndex.UserTE->State != TreeEntry::SplitVectorize &&
4616 TE->UserTreeIndex.UserTE->getOpcode() == Instruction::PHI;
4619 if (IsNonSchedulableWithParentPhiNode) {
4620 SmallPtrSet<Value *, 4> ParentsUniqueUsers;
4621 const TreeEntry *ParentTE =
TE->UserTreeIndex.UserTE;
4622 for (
Value *V : ParentTE->Scalars) {
4626 if (ParentsUniqueUsers.
insert(
PHI).second &&
4631 Inc =
count(
TE->Scalars, User);
4639 bool IsCommutativeUser =
4642 if (!IsCommutativeUser) {
4653 (!IsCommutativeUser ||
4661 "Expected commutative user with 2 first commutable operands");
4662 bool IsCommutativeWithSameOps =
4663 IsCommutativeUser &&
User->getOperand(0) ==
User->getOperand(1);
4664 if ((!IsCommutativeUser || IsCommutativeWithSameOps) &&
4666 User->getOperand(0) ==
User->getOperand(1))) {
4672 if (
TE->hasReassocScalars()) {
4673 bool ReplacedByCopyable =
false;
4674 for (
auto It =
find(
TE->Scalars, User); It !=
TE->Scalars.end();
4677 int Lane = std::distance(
TE->Scalars.begin(), It);
4679 ReplacedByCopyable |=
4680 TE->getOperand(OpIdx)[Lane] ==
Op &&
4681 getScheduleCopyableData(EdgeInfo(TE, OpIdx),
Op);
4683 if (ReplacedByCopyable)
4687 EdgeInfo EI(TE,
U.getOperandNo());
4688 if (getScheduleCopyableData(EI,
Op))
4695 PotentiallyReorderedEntriesCount.
try_emplace(TE, 0)
4696 .first->getSecond() += Inc;
4699 if (PotentiallyReorderedEntriesCount.
empty())
4702 for (
auto &
P : PotentiallyReorderedEntriesCount) {
4703 SmallPtrSet<Value *, 4> ParentsUniqueUsers;
4704 bool IsNonSchedulableWithParentPhiNode =
4705 P.first->doesNotNeedToSchedule() &&
P.first->UserTreeIndex &&
4706 P.first->UserTreeIndex.UserTE->hasState() &&
4707 P.first->UserTreeIndex.UserTE->State != TreeEntry::SplitVectorize &&
4708 P.first->UserTreeIndex.UserTE->getOpcode() == Instruction::PHI;
4709 auto *It =
find(
P.first->Scalars, User);
4711 assert(It !=
P.first->Scalars.end() &&
4712 "User is not in the tree entry");
4713 int Lane = std::distance(
P.first->Scalars.begin(), It);
4714 assert(Lane >= 0 &&
"Lane is not found");
4716 !
P.first->ReorderIndices.empty())
4717 Lane =
P.first->ReorderIndices[Lane];
4718 assert(Lane <
static_cast<int>(
P.first->Scalars.size()) &&
4719 "Couldn't find extract lane");
4722 if (IsNonSchedulableWithParentPhiNode) {
4723 const TreeEntry *ParentTE =
P.first->UserTreeIndex.UserTE;
4725 if (!ParentsUniqueUsers.
insert(User).second) {
4733 for (
unsigned OpIdx :
4735 ?
P.first->getNumOperands()
4737 P.first->getMainOp()))) {
4738 if (
P.first->getOperand(OpIdx)[Lane] ==
Op &&
4739 getScheduleCopyableData(EdgeInfo(
P.first, OpIdx),
Op))
4744 }
while (It !=
P.first->Scalars.end());
4746 return all_of(PotentiallyReorderedEntriesCount,
4747 [&](
const std::pair<const TreeEntry *, unsigned> &
P) {
4748 return P.second ==
NumOps - 1;
4753 getScheduleCopyableData(
const Instruction *
I)
const {
4754 if (ScheduleCopyableDataMapByInst.empty())
4756 const auto It = ScheduleCopyableDataMapByInst.find(
I);
4757 if (It == ScheduleCopyableDataMapByInst.end())
4760 for (ScheduleCopyableData *SD : It->getSecond()) {
4761 if (isInSchedulingRegion(*SD))
4768 getScheduleCopyableDataUsers(
const Instruction *User)
const {
4769 if (ScheduleCopyableDataMapByUsers.empty())
4771 const auto It = ScheduleCopyableDataMapByUsers.find(User);
4772 if (It == ScheduleCopyableDataMapByUsers.end())
4775 for (ScheduleCopyableData *SD : It->getSecond()) {
4776 if (isInSchedulingRegion(*SD))
4787 void markCopyableDepsForRecalc(
const TreeEntry &TE) {
4789 for (
Value *V :
TE.getOperand(OpIdx))
4791 if (ScheduleData *SD = getScheduleData(
I);
4792 SD && !getScheduleCopyableData(
I).empty())
4793 RecalcCopyableOperandDeps.
insert(SD);
4796 ScheduleCopyableData &addScheduleCopyableData(
const EdgeInfo &EI,
4798 int SchedulingRegionID,
4799 ScheduleBundle &Bundle) {
4800 assert(!getScheduleCopyableData(EI,
I) &&
"already in the map");
4801 ScheduleCopyableData *CD =
4802 ScheduleCopyableDataMap
4803 .try_emplace(std::make_pair(EI,
I),
4804 std::make_unique<ScheduleCopyableData>(
4805 SchedulingRegionID,
I, EI, Bundle))
4808 ScheduleCopyableDataMapByInst[
I].push_back(CD);
4812 assert(It !=
Op.end() &&
"Lane not set");
4813 SmallPtrSet<Instruction *, 4> Visited;
4815 int Lane = std::distance(
Op.begin(), It);
4816 assert(Lane >= 0 &&
"Lane not set");
4818 !EI.UserTE->ReorderIndices.empty())
4819 Lane = EI.UserTE->ReorderIndices[Lane];
4820 assert(Lane <
static_cast<int>(EI.UserTE->Scalars.size()) &&
4821 "Couldn't find extract lane");
4823 if (!Visited.
insert(In).second) {
4827 ScheduleCopyableDataMapByInstUser
4828 .try_emplace(std::make_pair(std::make_pair(In, EI.EdgeIdx),
I))
4831 ScheduleCopyableDataMapByUsers.try_emplace(
I)
4838 EdgeInfo UserEI = EI.UserTE->UserTreeIndex;
4839 if (ScheduleCopyableData *UserCD =
4840 getScheduleCopyableData(UserEI, In))
4841 ScheduleCopyableDataMapByUsers[
I].remove(UserCD);
4844 }
while (It !=
Op.end());
4846 ScheduleCopyableDataMapByUsers.try_emplace(
I).first->getSecond().insert(
4856 auto It = ScheduledBundles.find(
I);
4857 if (It == ScheduledBundles.end())
4859 return It->getSecond();
4863 bool isInSchedulingRegion(
const ScheduleEntity &SD)
const {
4865 return Data->getSchedulingRegionID() == SchedulingRegionID;
4867 return CD->getSchedulingRegionID() == SchedulingRegionID;
4869 [&](
const ScheduleEntity *BundleMember) {
4870 return isInSchedulingRegion(*BundleMember);
4876 template <
typename ReadyListType>
4877 void schedule(
const BoUpSLP &R,
const InstructionsState &S,
4878 const EdgeInfo &EI, ScheduleEntity *
Data,
4879 ReadyListType &ReadyList) {
4880 auto ProcessBundleMember = [&](ScheduleEntity *BundleMember,
4885 auto DecrUnsched = [&](
auto *
Data,
bool IsControl =
false) {
4886 if ((IsControl ||
Data->hasValidDependencies()) &&
4887 Data->incrementUnscheduledDeps(-1) == 0) {
4894 CopyableBundle.
push_back(&CD->getBundle());
4895 Bundles = CopyableBundle;
4897 Bundles = getScheduleBundles(
Data->getInst());
4899 if (!Bundles.
empty()) {
4900 for (ScheduleBundle *Bundle : Bundles) {
4901 if (Bundle->unscheduledDepsInBundle() == 0) {
4902 assert(!Bundle->isScheduled() &&
4903 "already scheduled bundle gets ready");
4904 ReadyList.insert(Bundle);
4906 <<
"SLP: gets ready: " << *Bundle <<
"\n");
4912 "already scheduled bundle gets ready");
4914 "Expected non-copyable data");
4915 ReadyList.insert(
Data);
4922 if (!ScheduleCopyableDataMap.empty()) {
4924 getScheduleCopyableData(User, OpIdx,
I);
4925 bool ReleasedAsCopyable =
false;
4926 for (ScheduleCopyableData *CD : CopyableData) {
4932 if (CD->getEdgeInfo().UserTE->isCopyableElement(User))
4934 DecrUnsched(CD,
false);
4935 ReleasedAsCopyable =
true;
4937 if (ReleasedAsCopyable)
4940 if (ScheduleData *OpSD = getScheduleData(
I))
4941 DecrUnsched(OpSD,
false);
4947 if (!Bundles.empty()) {
4948 auto *
In = BundleMember->getInst();
4950 SmallDenseMap<const Instruction *, unsigned> OperandsUses;
4951 unsigned TotalOpCount = 0;
4954 TotalOpCount = OperandsUses[
In] = 1;
4956 for (
const Use &U :
In->operands()) {
4959 unsigned ExtraDeps = 1;
4961 for (ScheduleBundle *Bundle : Bundles) {
4962 if (
const TreeEntry *TE = Bundle->getTreeEntry()) {
4963 if (
TE->isExpandedBinOp(In))
4969 Res.first->getSecond() += ExtraDeps;
4970 TotalOpCount += ExtraDeps;
4977 bool FoundInOpColumns =
false;
4980 auto DecrUnschedForInst =
4982 SmallDenseSet<std::pair<const ScheduleEntity *, unsigned>>
4984 bool IsExpandedOperand =
false,
4985 bool CopyableDepsOnly =
false) {
4986 if (!ScheduleCopyableDataMap.empty()) {
4987 const EdgeInfo EI = {UserTE, OpIdx};
4988 if (ScheduleCopyableData *CD =
4989 getScheduleCopyableData(EI,
I)) {
4990 if (!Checked.insert(std::make_pair(CD, OpIdx)).second)
4992 DecrUnsched(CD,
false);
4996 if (CopyableDepsOnly)
4998 auto It = OperandsUses.
find(
I);
4999 if (It == OperandsUses.
end()) {
5003 <<
" not modeled as a direct operand of "
5004 << *In <<
", skipping.\n");
5007 if (It->second > 0) {
5008 if (ScheduleData *OpSD = getScheduleData(
I)) {
5009 if (!IsExpandedOperand &&
5010 !Checked.insert(std::make_pair(OpSD, OpIdx)).second)
5013 assert(TotalOpCount > 0 &&
"No more operands to decrement");
5015 DecrUnsched(OpSD,
false);
5018 assert(TotalOpCount > 0 &&
"No more operands to decrement");
5024 SmallDenseSet<std::pair<const ScheduleEntity *, unsigned>> Checked;
5025 for (ScheduleBundle *Bundle : Bundles) {
5026 if (ScheduleCopyableDataMap.empty() && TotalOpCount == 0)
5028 SmallPtrSet<Value *, 4> ParentsUniqueUsers;
5031 auto *It =
find(Bundle->getTreeEntry()->Scalars, In);
5032 bool IsNonSchedulableWithParentPhiNode =
5033 Bundle->getTreeEntry()->doesNotNeedToSchedule() &&
5034 Bundle->getTreeEntry()->UserTreeIndex &&
5035 Bundle->getTreeEntry()->UserTreeIndex.UserTE->hasState() &&
5036 Bundle->getTreeEntry()->UserTreeIndex.UserTE->State !=
5037 TreeEntry::SplitVectorize &&
5038 Bundle->getTreeEntry()->UserTreeIndex.UserTE->getOpcode() ==
5042 std::distance(Bundle->getTreeEntry()->Scalars.begin(), It);
5043 assert(Lane >= 0 &&
"Lane not set");
5045 !Bundle->getTreeEntry()->ReorderIndices.empty())
5046 Lane = Bundle->getTreeEntry()->ReorderIndices[Lane];
5047 assert(Lane <
static_cast<int>(
5048 Bundle->getTreeEntry()->Scalars.size()) &&
5049 "Couldn't find extract lane");
5060 In->getNumOperands() ==
5061 Bundle->getTreeEntry()->getNumOperands() ||
5062 (
isa<ZExtInst>(In) && Bundle->getTreeEntry()->getOpcode() ==
5063 Instruction::Select) ||
5064 Bundle->getTreeEntry()->isCopyableElement(In) ||
5065 Bundle->getTreeEntry()->hasReassocScalars()) &&
5066 "Missed TreeEntry operands?");
5072 bool CopyableDepsOnly =
5073 IsNonSchedulableWithParentPhiNode &&
5075 .
insert(Bundle->getTreeEntry()
5076 ->UserTreeIndex.UserTE->Scalars[Lane])
5083 bool IsBlended = Bundle->getTreeEntry()->State ==
5084 TreeEntry::BlendedLoadVectorize;
5085 for (
unsigned OpIdx :
5088 IsBlended ?
In->getOperand(OpIdx)
5089 : Bundle->getTreeEntry()->getOperand(
5091 FoundInOpColumns |= (
I ==
In) && !CopyableDepsOnly;
5095 I, Bundle->getTreeEntry(), OpIdx, Checked,
5096 Bundle->getTreeEntry()->isExpandedOperand(In, OpIdx),
5100 if (Bundle->getTreeEntry()->isCopyableElement(In))
5102 It = std::find(std::next(It),
5103 Bundle->getTreeEntry()->Scalars.end(), In);
5104 }
while (It != Bundle->getTreeEntry()->Scalars.end());
5114 auto UseIt = OperandsUses.
find(In);
5115 if (UseIt != OperandsUses.
end() && UseIt->second > 0) {
5116 --UseIt->getSecond();
5119 if (ScheduleData *OpSD = getScheduleData(In))
5120 DecrUnsched(OpSD,
false);
5129 if (TotalOpCount > 0) {
5138 auto UseIt = OperandsUses.
find(OpI);
5139 if (UseIt == OperandsUses.
end() || UseIt->second == 0)
5141 --UseIt->getSecond();
5143 if (ScheduleData *OpSD = getScheduleData(OpI)) {
5145 <<
"SLP: check for readiness (scalar arg): "
5147 DecrUnsched(OpSD,
false);
5153 for (
const ScheduleBundle *Bundle : Bundles) {
5154 if (TotalOpCount == 0)
5156 TreeEntry *
TE = Bundle->getTreeEntry();
5157 if (!
TE->hasReassocScalars())
5159 for (
Value *V :
TE->getReassocScalars()) {
5163 auto UseIt = OperandsUses.
find(OpI);
5164 if (UseIt == OperandsUses.
end() || UseIt->second == 0)
5167 "(reassociated operand): "
5170 bool ReleasedAsCopyable =
false;
5171 if (!ScheduleCopyableDataMap.empty()) {
5172 for (
const Use &U :
In->operands()) {
5175 for (ScheduleCopyableData *CD :
5176 getScheduleCopyableData(In,
U.getOperandNo(), OpI)) {
5180 if (Checked.
insert(std::make_pair(CD,
U.getOperandNo()))
5182 DecrUnsched(CD,
false);
5190 for (
auto It =
find(
TE->Scalars, In);
5191 It !=
TE->Scalars.end() && !ReleasedAsCopyable;
5194 int Lane = std::distance(
TE->Scalars.begin(), It);
5196 ReleasedAsCopyable |=
5197 TE->getOperand(OpIdx)[Lane] == OpI &&
5198 getScheduleCopyableData(EdgeInfo(TE, OpIdx), OpI);
5201 if (!ReleasedAsCopyable) {
5202 if (ScheduleData *OpSD = getScheduleData(OpI))
5203 for (
unsigned I = 0,
E = UseIt->second;
I !=
E; ++
I)
5204 DecrUnsched(OpSD,
false);
5206 TotalOpCount -= UseIt->second;
5214 for (Use &U : BundleMember->getInst()->operands()) {
5217 <<
"SLP: check for readiness (def): " << *
I <<
"\n");
5218 DecrUnschedForInst(BundleMember->getInst(),
U.getOperandNo(),
I);
5226 SmallPtrSet<const ScheduleData *, 4> VisitedMemory;
5227 for (ScheduleData *MemoryDep : SD->getMemoryDependencies()) {
5228 if (!VisitedMemory.
insert(MemoryDep).second)
5233 << *MemoryDep <<
"\n");
5234 DecrUnsched(MemoryDep);
5237 SmallPtrSet<const ScheduleData *, 4> VisitedControl;
5238 for (ScheduleData *Dep : SD->getControlDependencies()) {
5239 if (!VisitedControl.
insert(Dep).second)
5244 <<
"SLP: check for readiness (ctrl): " << *Dep <<
"\n");
5245 DecrUnsched(Dep,
true);
5249 SD->setScheduled(
true);
5255 if (!Entries.
empty()) {
5256 for (TreeEntry *TE : Entries) {
5258 In->getNumOperands() !=
TE->getNumOperands() &&
5259 !
TE->hasReassocScalars())
5262 PseudoBundles.
emplace_back(std::make_unique<ScheduleBundle>());
5263 BundlePtr->setTreeEntry(TE);
5268 ProcessBundleMember(SD, Bundles);
5271 Bundle.setScheduled(
true);
5273 auto AreAllBundlesScheduled =
5274 [&](
const ScheduleEntity *SD,
5278 return !SDBundles.empty() &&
5279 all_of(SDBundles, [&](
const ScheduleBundle *SDBundle) {
5280 return SDBundle->isScheduled();
5283 for (ScheduleEntity *SD : Bundle.getBundle()) {
5286 SDBundles = getScheduleBundles(SD->getInst());
5287 if (!AreAllBundlesScheduled(SD, SDBundles))
5289 SD->setScheduled(
true);
5304 (ScheduleCopyableDataMap.empty() &&
5305 none_of(
R.getTreeEntries(In), [&](
const TreeEntry *TE) {
5306 return TE->isExpandedBinOp(In);
5315 for (TreeEntry *TE :
R.getTreeEntries(In)) {
5316 if (
TE->isCopyableElement(In))
5319 In->getNumOperands() !=
TE->getNumOperands() &&
5320 !
TE->hasReassocScalars())
5322 if (
any_of(SDBundles, [&](
const ScheduleBundle *SDBundle) {
5323 return SDBundle->getTreeEntry() ==
TE;
5326 ScheduleBundle &PseudoBundle =
5327 *PseudoBundles.
emplace_back(std::make_unique<ScheduleBundle>());
5328 PseudoBundle.setTreeEntry(TE);
5329 PseudoBundle.add(SD);
5330 AllBundles.push_back(&PseudoBundle);
5332 ProcessBundleMember(SD, AllBundles);
5342 assert(ScheduleStart->getParent() == ScheduleEnd->getParent() &&
5343 ScheduleStart->comesBefore(ScheduleEnd) &&
5344 "Not a valid scheduling region?");
5346 for (
auto *
I = ScheduleStart;
I != ScheduleEnd;
I =
I->getNextNode()) {
5348 if (!Bundles.
empty()) {
5349 for (ScheduleBundle *Bundle : Bundles) {
5350 assert(isInSchedulingRegion(*Bundle) &&
5351 "primary schedule data not in window?");
5356 auto *SD = getScheduleData(
I);
5359 assert(isInSchedulingRegion(*SD) &&
5360 "primary schedule data not in window?");
5365 [](
const ScheduleEntity *Bundle) {
5366 return Bundle->isReady();
5368 "item in ready list not ready?");
5372 template <
typename ReadyListType>
5373 void initialFillReadyList(ReadyListType &ReadyList) {
5374 SmallPtrSet<ScheduleBundle *, 16> Visited;
5375 for (
auto *
I = ScheduleStart;
I != ScheduleEnd;
I =
I->getNextNode()) {
5376 ScheduleData *SD = getScheduleData(
I);
5377 if (SD && SD->hasValidDependencies() && SD->isReady()) {
5380 for (ScheduleBundle *Bundle : Bundles) {
5381 if (!Visited.
insert(Bundle).second)
5383 if (Bundle->hasValidDependencies() && Bundle->isReady()) {
5384 ReadyList.insert(Bundle);
5386 << *Bundle <<
"\n");
5391 ReadyList.insert(SD);
5393 <<
"SLP: initially in ready list: " << *SD <<
"\n");
5404 const InstructionsState &S,
const EdgeInfo &EI);
5411 std::optional<ScheduleBundle *>
5413 const InstructionsState &S,
const EdgeInfo &EI);
5416 ScheduleData *allocateScheduleDataChunks();
5420 bool extendSchedulingRegion(
Value *V,
const InstructionsState &S);
5424 void initScheduleData(Instruction *FromI, Instruction *ToI,
5425 ScheduleData *PrevLoadStore,
5426 ScheduleData *NextLoadStore);
5430 void calculateDependencies(ScheduleBundle &Bundle,
bool InsertInReadyList,
5432 const SmallPtrSetImpl<Value *> &ExpandedOps,
5436 void resetSchedule();
5453 SmallDenseMap<Instruction *, ScheduleData *> ScheduleDataMap;
5457 SmallDenseMap<std::pair<EdgeInfo, const Value *>,
5458 std::unique_ptr<ScheduleCopyableData>>
5459 ScheduleCopyableDataMap;
5465 SmallDenseMap<const Instruction *, SmallVector<ScheduleCopyableData *>>
5466 ScheduleCopyableDataMapByInst;
5472 SmallDenseMap<std::pair<std::pair<const Value *, unsigned>,
const Value *>,
5474 ScheduleCopyableDataMapByInstUser;
5494 SmallSetVector<ScheduleCopyableData *, 4>>
5495 ScheduleCopyableDataMapByUsers;
5498 SmallDenseMap<Instruction *, SmallVector<ScheduleBundle *>>
5504 SetVector<ScheduleEntity *> ReadyInsts;
5514 ScheduleData *FirstLoadStoreInRegion =
nullptr;
5518 ScheduleData *LastLoadStoreInRegion =
nullptr;
5523 bool RegionHasStackSave =
false;
5526 int ScheduleRegionSize = 0;
5541 SmallSetVector<ScheduleData *, 8> RecalcCopyableOperandDeps;
5545 SmallDenseSet<std::pair<Instruction *, Instruction *>, 8> IgnoredMemDeps;
5551 int SchedulingRegionID = 1;
5555 MapVector<BasicBlock *, std::unique_ptr<BlockScheduling>> BlocksSchedules;
5559 void scheduleBlock(
const BoUpSLP &R, BlockScheduling *BS);
5562 const SmallDenseSet<Value *> *UserIgnoreList =
nullptr;
5566 SmallPtrSet<Value *, 4> NarrowedChainInsts;
5570 struct OrdersTypeDenseMapInfo {
5571 static unsigned getHashValue(
const OrdersType &V) {
5582 ScalarEvolution *SE;
5583 TargetTransformInfo *TTI;
5584 TargetLibraryInfo *TLI;
5587 AssumptionCache *AC;
5589 const DataLayout *DL;
5590 OptimizationRemarkEmitter *ORE;
5595 unsigned MaxVecRegSize;
5596 unsigned MinVecRegSize;
5599 IRBuilder<TargetFolder> Builder;
5606 DenseMap<const TreeEntry *, std::pair<uint64_t, bool>> MinBWs;
5611 unsigned ReductionBitWidth = 0;
5614 unsigned BaseGraphSize = 1;
5618 std::optional<std::pair<unsigned, unsigned>> CastMaxMinBWSizes;
5622 DenseSet<unsigned> ExtraBitWidthNodes;
8349 struct TreeEntryCompare {
8350 bool operator()(
const TreeEntry *LHS,
const TreeEntry *RHS)
const {
8351 if (LHS->UserTreeIndex && RHS->UserTreeIndex)
8352 return LHS->UserTreeIndex.UserTE->Idx < RHS->UserTreeIndex.UserTE->Idx;
8353 return LHS->Idx < RHS->Idx;
8362 for (
const std::unique_ptr<TreeEntry> &TE : VectorizableTree) {
8363 if (TE->State != TreeEntry::Vectorize &&
8364 TE->State != TreeEntry::StridedVectorize &&
8365 TE->State != TreeEntry::ExpandVectorize &&
8366 TE->State != TreeEntry::CompressVectorize &&
8367 TE->State != TreeEntry::BlendedLoadVectorize &&
8368 TE->State != TreeEntry::SplitVectorize)
8369 NonVectorized.
insert(TE.get());
8370 if (std::optional<OrdersType> CurrentOrder =
8372 Queue.push(TE.get());
8373 if (!(TE->State == TreeEntry::Vectorize ||
8374 TE->State == TreeEntry::StridedVectorize ||
8375 TE->State == TreeEntry::ExpandVectorize ||
8376 TE->State == TreeEntry::CompressVectorize ||
8377 TE->State == TreeEntry::BlendedLoadVectorize ||
8378 TE->State == TreeEntry::SplitVectorize) ||
8379 !TE->ReuseShuffleIndices.empty())
8380 GathersToOrders.
insert(TE.get());
8389 while (!Queue.empty()) {
8391 std::pair<TreeEntry *, SmallVector<std::pair<unsigned, TreeEntry *>>>
Users;
8392 TreeEntry *TE = Queue.top();
8393 const TreeEntry *UserTE = TE->UserTreeIndex.UserTE;
8396 while (!Queue.empty()) {
8398 if (!UserTE || UserTE != TE->UserTreeIndex.UserTE)
8403 for (TreeEntry *TE : OrderedOps) {
8404 if (!(TE->State == TreeEntry::Vectorize ||
8405 TE->State == TreeEntry::StridedVectorize ||
8406 TE->State == TreeEntry::ExpandVectorize ||
8407 TE->State == TreeEntry::CompressVectorize ||
8408 TE->State == TreeEntry::BlendedLoadVectorize ||
8409 TE->State == TreeEntry::SplitVectorize ||
8410 (TE->isGather() && GathersToOrders.
contains(TE))) ||
8411 !TE->UserTreeIndex ||
8412 TE->UserTreeIndex.UserTE->State == TreeEntry::BlendedLoadVectorize ||
8413 !TE->ReuseShuffleIndices.empty() || !Visited.
insert(TE).second)
8417 Users.first = TE->UserTreeIndex.UserTE;
8418 Users.second.emplace_back(TE->UserTreeIndex.EdgeIdx, TE);
8423 if (
Data.first->State == TreeEntry::Vectorize &&
8426 if (
Data.first->State == TreeEntry::SplitVectorize) {
8428 Data.second.size() <= 2 &&
8429 "Expected not greater than 2 operands for split vectorize node.");
8431 [](
const auto &
Op) { return !Op.second->UserTreeIndex; }))
8434 assert(
Data.first->CombinedEntriesWithIndices.size() == 2 &&
8435 "Expected exactly 2 entries.");
8436 for (
const auto &
P :
Data.first->CombinedEntriesWithIndices) {
8437 TreeEntry &OpTE = *VectorizableTree[
P.first];
8443 if (OpTE.State != TreeEntry::SplitVectorize &&
8444 !OpTE.ReorderIndices.empty() && !OpTE.ReuseShuffleIndices.empty())
8447 if (Order.
empty() || !OpTE.ReuseShuffleIndices.empty()) {
8448 if (!OpTE.isGather() && OpTE.ReuseShuffleIndices.empty())
8450 const auto BestOrder =
8459 const unsigned E = Order.
size();
8462 return I < E ? static_cast<int>(I) : PoisonMaskElem;
8464 Data.first->reorderSplitNode(
P.second ? 1 : 0, Mask, MaskOrder);
8466 if (!OpTE.ReorderIndices.empty()) {
8467 OpTE.ReorderIndices.clear();
8468 }
else if (!OpTE.ReuseShuffleIndices.empty()) {
8471 assert(OpTE.isGather() &&
"Expected only gather/buildvector node.");
8475 if (
Data.first->ReuseShuffleIndices.empty() &&
8476 !
Data.first->ReorderIndices.empty()) {
8479 Queue.push(
Data.first);
8487 !
Data.first->UserTreeIndex &&
8488 Data.first->State == TreeEntry::Vectorize &&
8489 Data.first->getOpcode() == Instruction::PHI &&
8490 Data.first->ReuseShuffleIndices.empty())
8494 buildReorderableOperands(
Data.first,
Data.second, NonVectorized,
8506 for (
const auto &
Op :
Data.second) {
8507 TreeEntry *OpTE =
Op.second;
8508 if (!VisitedOps.
insert(OpTE).second)
8510 if (!OpTE->ReuseShuffleIndices.empty() && !GathersToOrders.
count(OpTE))
8512 const auto Order = [&]() ->
const OrdersType {
8513 if (OpTE->isGather() || !OpTE->ReuseShuffleIndices.empty())
8517 return OpTE->ReorderIndices;
8521 if (Order.
size() == 1)
8527 Value *Root = OpTE->hasState()
8530 auto GetSameNodesUsers = [&](
Value *Root) {
8532 for (
const TreeEntry *TE : ValueToGatherNodes.lookup(Root)) {
8533 if (TE != OpTE && TE->UserTreeIndex &&
8534 TE->getVectorFactor() == OpTE->getVectorFactor() &&
8535 TE->Scalars.size() == OpTE->Scalars.size() &&
8536 ((TE->ReorderIndices.empty() && OpTE->isSame(TE->Scalars)) ||
8537 (OpTE->ReorderIndices.empty() && TE->isSame(OpTE->Scalars))))
8538 Res.
insert(TE->UserTreeIndex.UserTE);
8540 for (
const TreeEntry *TE : getTreeEntries(Root)) {
8541 if (TE != OpTE && TE->UserTreeIndex &&
8542 TE->getVectorFactor() == OpTE->getVectorFactor() &&
8543 TE->Scalars.size() == OpTE->Scalars.size() &&
8544 ((TE->ReorderIndices.empty() && OpTE->isSame(TE->Scalars)) ||
8545 (OpTE->ReorderIndices.empty() && TE->isSame(OpTE->Scalars))))
8546 Res.
insert(TE->UserTreeIndex.UserTE);
8550 auto GetNumOperands = [](
const TreeEntry *TE) {
8551 if (TE->State == TreeEntry::SplitVectorize)
8552 return TE->getNumOperands();
8554 return CI->arg_size();
8555 return TE->getNumOperands();
8557 auto NodeShouldBeReorderedWithOperands = [&, TTI = TTI](
8558 const TreeEntry *TE) {
8566 const TreeEntry *
Op = getOperandEntry(TE, Idx);
8567 if (
Op->isGather() &&
Op->hasState()) {
8568 const TreeEntry *VecOp =
8569 getSameValuesTreeEntry(
Op->getMainOp(),
Op->Scalars);
8573 if (
Op->ReorderIndices.empty() &&
Op->ReuseShuffleIndices.empty())
8580 if (!RevisitedOps.
insert(UTE).second)
8582 return UTE ==
Data.first || !UTE->ReorderIndices.empty() ||
8583 !UTE->ReuseShuffleIndices.empty() ||
8584 (UTE->UserTreeIndex &&
8585 UTE->UserTreeIndex.UserTE ==
Data.first) ||
8586 (
Data.first->UserTreeIndex &&
8587 Data.first->UserTreeIndex.UserTE == UTE) ||
8588 (IgnoreReorder && UTE->UserTreeIndex &&
8589 UTE->UserTreeIndex.UserTE->Idx == 0) ||
8590 NodeShouldBeReorderedWithOperands(UTE);
8593 for (TreeEntry *UTE :
Users) {
8601 const TreeEntry *
Op = getOperandEntry(UTE, Idx);
8603 Queue.push(
const_cast<TreeEntry *
>(
Op));
8608 Data.second, [OpTE](
const std::pair<unsigned, TreeEntry *> &
P) {
8609 return P.second == OpTE;
8612 if (OpTE->State == TreeEntry::Vectorize &&
8613 OpTE->getOpcode() == Instruction::Store && !Order.
empty()) {
8614 assert(!OpTE->isAltShuffle() &&
8615 "Alternate instructions are only supported by BinaryOperator "
8619 unsigned E = Order.
size();
8622 return Idx == PoisonMaskElem ? E : static_cast<unsigned>(Idx);
8625 OrdersUses.try_emplace(CurrentOrder, 0).first->second +=
NumOps;
8627 OrdersUses.try_emplace(Order, 0).first->second +=
NumOps;
8629 auto Res = OrdersUses.try_emplace(
OrdersType(), 0);
8630 const auto AllowsReordering = [&](
const TreeEntry *TE) {
8631 if (!TE->ReorderIndices.empty() || !TE->ReuseShuffleIndices.empty() ||
8632 (TE->State == TreeEntry::Vectorize && TE->isAltShuffle()) ||
8633 (IgnoreReorder && TE->Idx == 0))
8635 if (TE->isGather()) {
8645 if (OpTE->UserTreeIndex) {
8646 TreeEntry *UserTE = OpTE->UserTreeIndex.UserTE;
8647 if (!VisitedUsers.
insert(UserTE).second)
8652 if (AllowsReordering(UserTE))
8660 if (
static_cast<unsigned>(
count_if(
8661 Ops, [UserTE, &AllowsReordering](
8662 const std::pair<unsigned, TreeEntry *> &
Op) {
8663 return AllowsReordering(
Op.second) &&
8664 Op.second->UserTreeIndex.UserTE == UserTE;
8665 })) <=
Ops.size() / 2)
8666 ++Res.first->second;
8669 if (OrdersUses.empty()) {
8674 unsigned IdentityCnt = 0;
8675 unsigned VF =
Data.second.front().second->getVectorFactor();
8677 for (
auto &Pair : OrdersUses) {
8679 IdentityCnt += Pair.second;
8684 unsigned Cnt = IdentityCnt;
8685 for (
auto &Pair : OrdersUses) {
8689 if (Cnt < Pair.second) {
8691 BestOrder = Pair.first;
8708 unsigned E = BestOrder.
size();
8710 return I < E ? static_cast<int>(I) : PoisonMaskElem;
8712 for (
const std::pair<unsigned, TreeEntry *> &
Op :
Data.second) {
8713 TreeEntry *TE =
Op.second;
8714 if (!VisitedOps.
insert(TE).second)
8717 if (TE->State == TreeEntry::Vectorize &&
8720 if (TE->ReuseShuffleIndices.size() == BestOrder.
size()) {
8721 reorderNodeWithReuses(*TE, Mask);
8725 if (TE->State != TreeEntry::Vectorize &&
8726 TE->State != TreeEntry::StridedVectorize &&
8727 TE->State != TreeEntry::ExpandVectorize &&
8728 TE->State != TreeEntry::CompressVectorize &&
8729 TE->State != TreeEntry::BlendedLoadVectorize &&
8730 TE->State != TreeEntry::SplitVectorize &&
8731 (TE->State != TreeEntry::ScatterVectorize ||
8732 TE->ReorderIndices.empty()))
8734 assert((BestOrder.
size() == TE->ReorderIndices.size() ||
8735 TE->ReorderIndices.empty()) &&
8736 "Non-matching sizes of user/operand entries.");
8739 IgnoreReorder =
false;
8742 for (TreeEntry *
Gather : GatherOps) {
8744 "Unexpected reordering of gathers.");
8745 if (!
Gather->ReuseShuffleIndices.empty()) {
8756 if (
Gather->State == TreeEntry::ScatterVectorize) {
8766 auto IsNotProfitableAltCodeNode = [](
const TreeEntry &TE) {
8767 return TE.isAltShuffle() &&
8768 (!TE.ReuseShuffleIndices.empty() || TE.getVectorFactor() == 2 ||
8769 TE.ReorderIndices.empty());
8771 if (
Data.first->State != TreeEntry::Vectorize ||
8773 Data.first->getMainOp()) ||
8774 IsNotProfitableAltCodeNode(*
Data.first)) {
8775 Data.first->reorderOperands(Mask);
8779 Data.first->getMainOp()) ||
8780 IsNotProfitableAltCodeNode(*
Data.first) ||
8781 Data.first->State == TreeEntry::CompressVectorize) {
8785 if (
Data.first->ReuseShuffleIndices.empty() &&
8786 !
Data.first->ReorderIndices.empty() &&
8787 !IsNotProfitableAltCodeNode(*
Data.first)) {
8790 Queue.push(
Data.first);