30#define DEBUG_TYPE "igrouplp"
36 cl::desc(
"Whether to use the exponential time solver to fit "
37 "the instructions to the pipeline as closely as "
43 cl::desc(
"The maximum number of scheduling group conflicts "
44 "which we attempt to solve with the exponential time "
45 "exact solver. Problem sizes greater than this will"
46 "be solved by the less accurate greedy algorithm. Selecting "
47 "solver by size is superseded by manually selecting "
48 "the solver (e.g. by amdgpu-igrouplp-exact-solver"));
52 cl::desc(
"The amount of branches that we are willing to explore with"
53 "the exact algorithm before giving up."));
57 cl::desc(
"Whether to use the cost heuristic to make choices as we "
58 "traverse the search space using the exact solver. Defaulted "
59 "to on, and if turned off, we will use the node order -- "
60 "attempting to put the later nodes in the later sched groups. "
61 "Experimentally, results are mixed, so this should be set on a "
62 "case-by-case basis."));
66enum class SchedGroupMask {
78 ALL = ALU | VALU | SALU | MFMA | VMEM | VMEM_READ | VMEM_WRITE | DS |
88class InstructionRule {
94 std::optional<SmallVector<SUnit *, 4>> Cache;
104 bool NeedsCache =
false)
111 virtual ~InstructionRule() =
default;
124 SchedGroupMask SGMask;
127 std::optional<unsigned> MaxSize;
140 static unsigned NumSchedGroups;
158 bool canAddSU(
SUnit &SU)
const;
163 void link(
SUnit &SU,
bool MakePred =
false);
167 int link(
SUnit &SU,
bool MakePred,
168 std::vector<std::pair<SUnit *, SUnit *>> &AddedEdges);
177 void link(SchedGroup &OtherGroup);
180 bool isFull()
const {
return MaxSize && Collection.
size() >= *MaxSize; }
186 void addRule(std::shared_ptr<InstructionRule> NewRule) {
191 bool allowedByRules(
const SUnit *SU,
195 for (
size_t I = 0;
I < Rules.
size();
I++) {
196 auto TheRule = Rules[
I].get();
197 if (!TheRule->apply(SU, Collection, SyncPipe)) {
205 void add(
SUnit &SU) {
207 <<
format_hex((
int)SGMask, 10,
true) <<
" adding "
213 void pop() { Collection.
pop_back(); }
216 void initSchedGroup();
223 void initSchedGroup(std::vector<SUnit>::reverse_iterator RIter,
224 SUnitsToCandidateSGsMap &SyncedInstrs);
226 void initSchedGroup(SUnitsToCandidateSGsMap &SyncedInstrs);
228 int getSyncID() {
return SyncID; }
230 int getSGID() {
return SGID; }
232 SchedGroupMask getMask() {
return SGMask; }
234 SchedGroup(SchedGroupMask SGMask, std::optional<unsigned> MaxSize,
236 : SGMask(SGMask), MaxSize(MaxSize),
TII(
TII), DAG(DAG) {
237 SGID = NumSchedGroups++;
240 SchedGroup(SchedGroupMask SGMask, std::optional<unsigned> MaxSize,
int SyncID,
242 : SGMask(SGMask), MaxSize(MaxSize), SyncID(SyncID),
TII(
TII), DAG(DAG) {
243 SGID = NumSchedGroups++;
253 while (!SU.
Preds.empty())
257 while (!SU.
Succs.empty())
258 for (
auto &S : SU.
Succs)
259 for (
auto &SP : S.getSUnit()->Preds)
260 if (SP.getSUnit() == &SU)
261 S.getSUnit()->removePred(SP);
264typedef std::pair<SUnit *, SmallVector<int, 4>> SUToCandSGsPair;
276class PipelineSolver {
289 bool NeedsSolver =
false;
293 unsigned computeProblemSize();
304 int CurrConflInstNo = 0;
306 int CurrSyncGroupIdx = 0;
308 int BeginSyncGroupIdx = 0;
317 void advancePosition();
320 void retreatPosition();
329 template <
typename T>
330 void greedyFind(std::vector<std::pair<SUnit *, SUnit *>> &AddedEdges,
T I,
336 template <
typename T>
343 template <
typename T>
void linkSchedGroups(
T I,
T E);
347 std::vector<std::pair<SUnit *, SUnit *>> &AddedEdges);
351 template <
typename T>
352 int linkSUnit(
SUnit *SU,
int SGID,
353 std::vector<std::pair<SUnit *, SUnit *>> &AddedEdges,
T I,
T E);
355 void removeEdges(
const std::vector<std::pair<SUnit *, SUnit *>> &AddedEdges);
357 void convertSyncMapsToArrays();
369 : DAG(DAG), SyncedInstrs(SyncedInstrs),
370 SyncedSchedGroups(SyncedSchedGroups), IsBottomUp(IsBottomUp) {
372 for (
auto &PipelineInstrs : SyncedInstrs) {
373 if (PipelineInstrs.second.
size() > 0) {
382 convertSyncMapsToArrays();
384 CurrPipeline = BestPipeline;
386 while (
static_cast<size_t>(BeginSyncGroupIdx) < PipelineInstrs.
size() &&
387 PipelineInstrs[BeginSyncGroupIdx].
size() == 0)
390 if (
static_cast<size_t>(BeginSyncGroupIdx) >= PipelineInstrs.
size())
395void PipelineSolver::reset() {
397 for (
auto &SyncPipeline : CurrPipeline) {
398 for (
auto &SG : SyncPipeline) {
400 SG.Collection.
clear();
404 if (SchedBarr != TempCollection.
end())
405 SG.Collection.push_back(*SchedBarr);
409 CurrSyncGroupIdx = BeginSyncGroupIdx;
414void PipelineSolver::convertSyncMapsToArrays() {
415 for (
auto &SyncPipe : SyncedSchedGroups) {
416 BestPipeline.insert(BestPipeline.begin(), SyncPipe.second);
419 int PipelineIDx = SyncedInstrs.size() - 1;
420 PipelineInstrs.resize(SyncedInstrs.size());
421 for (
auto &SyncInstrMap : SyncedInstrs) {
422 for (
auto &SUsToCandSGs : SyncInstrMap.second) {
423 if (PipelineInstrs[PipelineIDx].
size() == 0) {
424 PipelineInstrs[PipelineIDx].push_back(
425 std::pair(SUsToCandSGs.first, SUsToCandSGs.second));
428 auto SortPosition = PipelineInstrs[PipelineIDx].begin();
431 while (SortPosition != PipelineInstrs[PipelineIDx].end() &&
432 SUsToCandSGs.first->NodeNum > SortPosition->first->NodeNum)
434 PipelineInstrs[PipelineIDx].insert(
435 SortPosition, std::pair(SUsToCandSGs.first, SUsToCandSGs.second));
441template <
typename T>
void PipelineSolver::linkSchedGroups(
T I,
T E) {
442 for (;
I !=
E; ++
I) {
444 for (
auto J = std::next(
I); J !=
E; ++J) {
451void PipelineSolver::makePipeline() {
453 for (
auto &SyncPipeline : BestPipeline) {
455 for (
auto &SG : SyncPipeline) {
458 SUnit *SGBarr =
nullptr;
459 for (
auto &SU : SG.Collection) {
467 resetEdges(*SGBarr, DAG);
468 SG.link(*SGBarr,
false);
472 for (
auto &SyncPipeline : BestPipeline) {
473 IsBottomUp ? linkSchedGroups(SyncPipeline.rbegin(), SyncPipeline.rend())
474 : linkSchedGroups(SyncPipeline.begin(), SyncPipeline.end());
479int PipelineSolver::linkSUnit(
480 SUnit *SU,
int SGID, std::vector<std::pair<SUnit *, SUnit *>> &AddedEdges,
482 bool MakePred =
false;
485 if (
I->getSGID() == SGID) {
490 AddedCost += Group.link(*SU, MakePred, AddedEdges);
496int PipelineSolver::addEdges(
498 std::vector<std::pair<SUnit *, SUnit *>> &AddedEdges) {
508 return IsBottomUp ? linkSUnit(SU, SGID, AddedEdges, SyncPipeline.
rbegin(),
510 : linkSUnit(SU, SGID, AddedEdges, SyncPipeline.
begin(),
514void PipelineSolver::removeEdges(
515 const std::vector<std::pair<SUnit *, SUnit *>> &EdgesToRemove) {
518 for (
auto &PredSuccPair : EdgesToRemove) {
519 SUnit *Pred = PredSuccPair.first;
520 SUnit *Succ = PredSuccPair.second;
523 Succ->
Preds, [&Pred](
SDep &
P) { return P.getSUnit() == Pred; });
531void PipelineSolver::advancePosition() {
534 if (
static_cast<size_t>(CurrConflInstNo) >=
535 PipelineInstrs[CurrSyncGroupIdx].
size()) {
539 while (
static_cast<size_t>(CurrSyncGroupIdx) < PipelineInstrs.size() &&
540 PipelineInstrs[CurrSyncGroupIdx].size() == 0)
545void PipelineSolver::retreatPosition() {
546 assert(CurrConflInstNo >= 0);
547 assert(CurrSyncGroupIdx >= 0);
549 if (CurrConflInstNo > 0) {
554 if (CurrConflInstNo == 0) {
557 if (CurrSyncGroupIdx == BeginSyncGroupIdx)
562 while (PipelineInstrs[CurrSyncGroupIdx].
size() == 0)
565 CurrConflInstNo = PipelineInstrs[CurrSyncGroupIdx].size() - 1;
569bool PipelineSolver::checkOptimal() {
570 if (
static_cast<size_t>(CurrSyncGroupIdx) == PipelineInstrs.size()) {
571 if (BestCost == -1 || CurrCost < BestCost) {
572 BestPipeline = CurrPipeline;
579 bool DoneExploring =
false;
580 if (MaxBranchesExplored > 0 && BranchesExplored >= MaxBranchesExplored)
581 DoneExploring =
true;
583 return (DoneExploring || BestCost == 0);
587void PipelineSolver::populateReadyList(
589 SUToCandSGsPair CurrSU = PipelineInstrs[CurrSyncGroupIdx][CurrConflInstNo];
590 auto SyncPipeline = CurrPipeline[CurrSyncGroupIdx];
591 assert(CurrSU.second.size() >= 1);
593 for (;
I !=
E; ++
I) {
594 std::vector<std::pair<SUnit *, SUnit *>> AddedEdges;
597 return SG.getSGID() == CandSGID;
602 if (
Match->isFull()) {
603 ReadyList.push_back(std::pair(*
I, MissPenalty));
607 int TempCost = addEdges(SyncPipeline, CurrSU.first, CandSGID, AddedEdges);
608 ReadyList.push_back(std::pair(*
I, TempCost));
609 removeEdges(AddedEdges);
611 ReadyList.push_back(std::pair(*
I, -1));
615 std::sort(ReadyList.begin(), ReadyList.end(),
616 [](std::pair<int, int>
A, std::pair<int, int>
B) {
617 return A.second < B.second;
621 assert(ReadyList.size() == CurrSU.second.size());
624bool PipelineSolver::solveExact() {
628 if (
static_cast<size_t>(CurrSyncGroupIdx) == PipelineInstrs.size())
631 assert(
static_cast<size_t>(CurrSyncGroupIdx) < PipelineInstrs.size());
632 assert(
static_cast<size_t>(CurrConflInstNo) <
633 PipelineInstrs[CurrSyncGroupIdx].
size());
634 SUToCandSGsPair CurrSU = PipelineInstrs[CurrSyncGroupIdx][CurrConflInstNo];
636 <<
") in Pipeline # " << CurrSyncGroupIdx <<
"\n");
641 IsBottomUp ? populateReadyList(ReadyList, CurrSU.second.
rbegin(),
642 CurrSU.second.rend())
643 : populateReadyList(ReadyList, CurrSU.second.
begin(),
644 CurrSU.second.end());
646 auto I = ReadyList.
begin();
647 auto E = ReadyList.
end();
648 for (;
I !=
E; ++
I) {
652 if (BestCost != -1 && (CurrCost +
I->second > BestCost))
655 int CandSGID =
I->first;
657 std::vector<std::pair<SUnit *, SUnit *>> AddedEdges;
658 auto &SyncPipeline = CurrPipeline[CurrSyncGroupIdx];
660 for (
auto &SG : SyncPipeline) {
661 if (SG.getSGID() == CandSGID)
668 if (!
Match->allowedByRules(CurrSU.first, SyncPipeline))
672 << (
int)
Match->getMask() <<
"and ID " << CandSGID
674 Match->add(*CurrSU.first);
675 AddedCost = addEdges(SyncPipeline, CurrSU.first, CandSGID, AddedEdges);
676 LLVM_DEBUG(
dbgs() <<
"Cost of Assignment: " << AddedCost <<
"\n");
677 CurrCost += AddedCost;
680 bool FinishedExploring =
false;
683 if (CurrCost < BestCost || BestCost == -1) {
685 FinishedExploring = BestCost != 0;
686 if (!FinishedExploring)
692 CurrCost -= AddedCost;
693 removeEdges(AddedEdges);
695 CurrPipeline[CurrSyncGroupIdx] = SyncPipeline;
696 if (FinishedExploring)
703 CurrCost += MissPenalty;
706 LLVM_DEBUG(
dbgs() <<
"NOT Assigned (" << CurrSU.first->NodeNum <<
")\n");
708 bool FinishedExploring =
false;
709 if (CurrCost < BestCost || BestCost == -1) {
711 bool FinishedExploring = BestCost != 0;
712 if (!FinishedExploring)
718 CurrCost -= MissPenalty;
719 return FinishedExploring;
723void PipelineSolver::greedyFind(
724 std::vector<std::pair<SUnit *, SUnit *>> &AddedEdges,
T I,
T E) {
725 SUToCandSGsPair CurrSU = PipelineInstrs[CurrSyncGroupIdx][CurrConflInstNo];
726 int BestNodeCost = -1;
728 SchedGroup *BestGroup =
nullptr;
729 int BestGroupID = -1;
730 auto &SyncPipeline = CurrPipeline[CurrSyncGroupIdx];
732 <<
") in Pipeline # " << CurrSyncGroupIdx <<
"\n");
738 for (;
I !=
E; ++
I) {
739 std::vector<std::pair<SUnit *, SUnit *>> AddedEdges;
742 return SG.getSGID() == CandSGID;
746 LLVM_DEBUG(
dbgs() <<
"Trying SGID # " << CandSGID <<
" with Mask "
747 << (
int)
Match->getMask() <<
"\n");
749 if (
Match->isFull()) {
753 if (!
Match->allowedByRules(CurrSU.first, SyncPipeline)) {
754 LLVM_DEBUG(
dbgs() <<
"SGID # " << CandSGID <<
" has conflicting rule\n");
757 TempCost = addEdges(SyncPipeline, CurrSU.first, CandSGID, AddedEdges);
759 if (TempCost < BestNodeCost || BestNodeCost == -1) {
761 BestNodeCost = TempCost;
762 BestGroupID = CandSGID;
764 removeEdges(AddedEdges);
765 if (BestNodeCost == 0)
769 if (BestGroupID != -1) {
770 BestGroup->add(*CurrSU.first);
771 addEdges(SyncPipeline, CurrSU.first, BestGroupID, AddedEdges);
772 LLVM_DEBUG(
dbgs() <<
"Best Group has ID: " << BestGroupID <<
" and Mask"
773 << (
int)BestGroup->getMask() <<
"\n");
774 BestCost += TempCost;
776 BestCost += MissPenalty;
778 CurrPipeline[CurrSyncGroupIdx] = SyncPipeline;
781bool PipelineSolver::solveGreedy() {
783 std::vector<std::pair<SUnit *, SUnit *>> AddedEdges;
785 while (
static_cast<size_t>(CurrSyncGroupIdx) < PipelineInstrs.size()) {
786 SUToCandSGsPair CurrSU = PipelineInstrs[CurrSyncGroupIdx][CurrConflInstNo];
788 ? greedyFind(AddedEdges, CurrSU.second.rbegin(), CurrSU.second.rend())
789 : greedyFind(AddedEdges, CurrSU.second.begin(), CurrSU.second.end());
792 BestPipeline = CurrPipeline;
793 removeEdges(AddedEdges);
797unsigned PipelineSolver::computeProblemSize() {
798 unsigned ProblemSize = 0;
799 for (
auto &PipeConflicts : PipelineInstrs) {
800 ProblemSize += PipeConflicts.size();
806void PipelineSolver::solve() {
810 unsigned ProblemSize = computeProblemSize();
813 bool BelowCutoff = (CutoffForExact > 0) && ProblemSize <= CutoffForExact;
814 MissPenalty = (ProblemSize / 2) + 1;
817 if (EnableExactSolver || BelowCutoff) {
821 LLVM_DEBUG(
dbgs() <<
"Greedy produced best cost of " << BestCost <<
"\n");
825 LLVM_DEBUG(
dbgs() <<
"Exact produced best cost of " << BestCost <<
"\n");
837enum IGLPStrategyID :
int {
838 MFMASmallGemmOptID = 0,
839 MFMASmallGemmSingleWaveOptID = 1,
851 virtual void applyIGLPStrategy(
863 virtual ~IGLPStrategy() =
default;
866class MFMASmallGemmOpt final :
public IGLPStrategy {
869 void applyIGLPStrategy(
876 : IGLPStrategy(DAG,
TII) {
881void MFMASmallGemmOpt::applyIGLPStrategy(
885 unsigned MFMACount = 0;
887 if (
TII->isMFMAorWMMA(
I))
890 const unsigned PipelineSyncID = 0;
891 SchedGroup *SG =
nullptr;
892 for (
unsigned I = 0;
I < MFMACount * 3; ++
I) {
893 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
894 SchedGroupMask::DS, 2, PipelineSyncID, DAG,
TII);
895 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
897 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
898 SchedGroupMask::MFMA, 1, PipelineSyncID, DAG,
TII);
899 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
903class MFMASmallGemmSingleWaveOpt final :
public IGLPStrategy {
906 class EnablesInitialMFMA final :
public InstructionRule {
910 if (!SyncPipe.
size())
913 if (!Cache->size()) {
914 for (
auto &Elt : SyncPipe[0].DAG->
SUnits) {
915 if (
TII->isMFMAorWMMA(*Elt.getInstr())) {
919 Cache->push_back(&Elt);
925 auto DAG = SyncPipe[0].DAG;
926 for (
auto &Elt : *Cache) {
934 bool NeedsCache =
false)
935 : InstructionRule(
TII, SGID, NeedsCache) {}
939 class IsPermForDSW final :
public InstructionRule {
944 if (
MI->getOpcode() != AMDGPU::V_PERM_B32_e64)
947 bool FitsInGroup =
false;
949 if (!Collection.
size()) {
950 for (
auto &Succ : SU->
Succs) {
951 SUnit *SuccUnit = Succ.getSUnit();
954 Cache->push_back(SuccUnit);
965 return std::any_of(Cache->begin(), Cache->end(), [&SU](
SUnit *Elt) {
966 return std::any_of(SU->Succs.begin(), SU->Succs.end(),
967 [&Elt](const SDep &ThisSucc) {
968 return ThisSucc.getSUnit() == Elt;
973 IsPermForDSW(
const SIInstrInfo *
TII,
unsigned SGID,
bool NeedsCache =
false)
974 : InstructionRule(
TII, SGID, NeedsCache) {}
978 class IsSuccOfPrevGroup final :
public InstructionRule {
982 SchedGroup *OtherGroup =
nullptr;
983 for (
auto &PipeSG : SyncPipe) {
984 if ((
unsigned)PipeSG.getSGID() == SGID - 1) {
985 OtherGroup = &PipeSG;
991 if (!OtherGroup->Collection.size())
995 return (std::any_of(OtherGroup->Collection.begin(),
996 OtherGroup->Collection.end(), [&SU](
SUnit *Elt) {
997 return std::any_of(Elt->Succs.begin(),
1000 return Succ.getSUnit() == SU;
1005 bool NeedsCache =
false)
1006 : InstructionRule(
TII, SGID, NeedsCache) {}
1010 class VMEMSize final :
public InstructionRule {
1015 if (
MI->getOpcode() == TargetOpcode::BUNDLE)
1017 if (!Collection.
size())
1022 auto TRI =
TII->getRegisterInfo();
1023 auto &
MRI =
MI->getParent()->getParent()->getRegInfo();
1024 for (
auto &Elt : Collection) {
1025 auto Op = Elt->getInstr()->getOperand(0);
1027 TRI.getRegSizeInBits(*
TRI.getRegClassForOperandReg(
MRI,
Op));
1031 if (NumBits < 128) {
1033 if (NumBits +
TRI.getRegSizeInBits(*
TRI.getRegClassForOperandReg(
1034 MRI,
MI->getOperand(0))) <=
1042 VMEMSize(
const SIInstrInfo *
TII,
unsigned SGID,
bool NeedsCache =
false)
1043 : InstructionRule(
TII, SGID, NeedsCache) {}
1048 class SharesPredWithPrevNthGroup final :
public InstructionRule {
1050 unsigned Distance = 1;
1055 SchedGroup *OtherGroup =
nullptr;
1056 if (!SyncPipe.
size())
1059 if (!Cache->size()) {
1061 for (
auto &PipeSG : SyncPipe) {
1062 if ((
unsigned)PipeSG.getSGID() == SGID - Distance) {
1063 OtherGroup = &PipeSG;
1069 if (!OtherGroup->Collection.size())
1072 for (
auto &OtherEle : OtherGroup->Collection) {
1073 for (
auto &Pred : OtherEle->Preds) {
1074 if (Pred.getSUnit()->getInstr()->getOpcode() ==
1075 AMDGPU::V_PERM_B32_e64)
1076 Cache->push_back(Pred.getSUnit());
1082 auto DAG = SyncPipe[0].DAG;
1086 std::any_of(Cache->begin(), Cache->end(), [&SU, &DAG](
SUnit *Elt) {
1087 return DAG->IsReachable(const_cast<SUnit *>(SU), Elt);
1090 SharesPredWithPrevNthGroup(
unsigned Distance,
const SIInstrInfo *
TII,
1091 unsigned SGID,
bool NeedsCache =
false)
1092 : InstructionRule(
TII, SGID, NeedsCache), Distance(Distance) {}
1096 void applyIGLPStrategy(
1103 : IGLPStrategy(DAG,
TII) {
1108void MFMASmallGemmSingleWaveOpt::applyIGLPStrategy(
1111 unsigned MFMACount = 0;
1112 unsigned DSWCount = 0;
1113 unsigned DSWWithPermCount = 0;
1114 unsigned DSWWithSharedVMEMCount = 0;
1115 unsigned DSRCount = 0;
1117 for (
auto &SU : DAG->SUnits) {
1119 if (
TII->isMFMAorWMMA(*
I))
1121 else if (
TII->isDS(*
I)) {
1124 else if (
I->mayStore()) {
1126 for (
auto Pred : SU.
Preds) {
1127 if (Pred.getSUnit()->getInstr()->getOpcode() ==
1128 AMDGPU::V_PERM_B32_e64) {
1136 DSWWithPermCount = DSWithPerms.
size();
1137 auto I = DSWithPerms.
begin();
1138 auto E = DSWithPerms.
end();
1148 for (;
I !=
E;
I++) {
1149 SUnit *Cand =
nullptr;
1150 bool MissedAny =
false;
1151 for (
auto &Pred : (*I)->Preds) {
1152 if (Pred.getSUnit()->getInstr()->getOpcode() != AMDGPU::V_PERM_B32_e64)
1158 for (
auto &Succ : Pred.getSUnit()->Succs) {
1159 auto MI = Succ.getSUnit()->getInstr();
1160 if (!
TII->isVMEM(*
MI) || !
MI->mayLoad())
1163 if (MissedAny || !VMEMLookup.
size()) {
1165 VMEMLookup[
MI] = *
I;
1171 VMEMLookup[
MI] = *
I;
1175 Cand = VMEMLookup[
MI];
1182 if (!MissedAny && Cand) {
1183 DSWWithSharedVMEMCount += 2;
1189 assert(DSWWithSharedVMEMCount <= DSWWithPermCount);
1191 unsigned PipelineSyncID = 0;
1193 if (DSWWithPermCount) {
1194 for (
unsigned I = 0;
I < MFMACount;
I++) {
1195 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1196 SchedGroupMask::MFMA, 1, PipelineSyncID, DAG,
TII);
1197 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
1199 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1200 SchedGroupMask::VALU, 2, PipelineSyncID, DAG,
TII);
1201 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
1211 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1212 SchedGroupMask::DS_READ, 4, PipelineSyncID, DAG,
TII);
1213 SG->addRule(std::make_shared<EnablesInitialMFMA>(
TII, SG->getSGID(),
true));
1214 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
1216 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1217 SchedGroupMask::MFMA, 1, PipelineSyncID, DAG,
TII);
1218 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
1221 for (
unsigned I = 0;
I < DSRCount - 4; ++
I) {
1222 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1223 SchedGroupMask::DS_READ, 1, PipelineSyncID, DAG,
TII);
1224 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
1226 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1227 SchedGroupMask::MFMA, 1, PipelineSyncID, DAG,
TII);
1228 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
1234 for (
unsigned I = 0;
I < DSWWithPermCount - DSWWithSharedVMEMCount; ++
I) {
1235 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1236 SchedGroupMask::VALU, 4, PipelineSyncID, DAG,
TII);
1237 SG->addRule(std::make_shared<IsPermForDSW>(
TII, SG->getSGID(),
true));
1238 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
1240 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1241 SchedGroupMask::DS_WRITE, 1, PipelineSyncID, DAG,
TII);
1242 SG->addRule(std::make_shared<IsSuccOfPrevGroup>(
TII, SG->getSGID(),
false));
1243 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
1245 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1246 SchedGroupMask::VMEM_READ, 4, PipelineSyncID, DAG,
TII);
1247 SG->addRule(std::make_shared<SharesPredWithPrevNthGroup>(
1248 1,
TII, SG->getSGID(),
true));
1249 SG->addRule(std::make_shared<VMEMSize>(
TII, SG->getSGID(),
false));
1250 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
1252 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1253 SchedGroupMask::MFMA, 1, PipelineSyncID, DAG,
TII);
1254 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
1256 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1257 SchedGroupMask::VMEM_READ, 4, PipelineSyncID, DAG,
TII);
1258 SG->addRule(std::make_shared<SharesPredWithPrevNthGroup>(
1259 3,
TII, SG->getSGID(),
true));
1260 SG->addRule(std::make_shared<VMEMSize>(
TII, SG->getSGID(),
false));
1261 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
1263 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1264 SchedGroupMask::MFMA, 1, PipelineSyncID, DAG,
TII);
1265 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
1271 for (
unsigned I = 0;
I < DSWCount - DSWWithPermCount;
I++) {
1272 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1273 SchedGroupMask::DS_WRITE, 1, PipelineSyncID, DAG,
TII);
1274 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
1276 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1277 SchedGroupMask::VMEM_READ, 4, PipelineSyncID, DAG,
TII);
1278 SG->addRule(std::make_shared<VMEMSize>(
TII, SG->getSGID(),
false));
1279 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
1281 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1282 SchedGroupMask::MFMA, 1, PipelineSyncID, DAG,
TII);
1283 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
1291 for (
unsigned I = 0;
I < DSWWithSharedVMEMCount; ++
I) {
1292 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1293 SchedGroupMask::VALU, 4, PipelineSyncID, DAG,
TII);
1294 SG->addRule(std::make_shared<IsPermForDSW>(
TII, SG->getSGID(),
true));
1295 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
1297 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1298 SchedGroupMask::DS_WRITE, 1, PipelineSyncID, DAG,
TII);
1299 SG->addRule(std::make_shared<IsSuccOfPrevGroup>(
TII, SG->getSGID(),
false));
1300 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
1302 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1303 SchedGroupMask::MFMA, 1, PipelineSyncID, DAG,
TII);
1304 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
1306 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1307 SchedGroupMask::VALU, 4, PipelineSyncID, DAG,
TII);
1308 SG->addRule(std::make_shared<IsPermForDSW>(
TII, SG->getSGID(),
true));
1309 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
1311 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1312 SchedGroupMask::DS_WRITE, 1, PipelineSyncID, DAG,
TII);
1313 SG->addRule(std::make_shared<IsSuccOfPrevGroup>(
TII, SG->getSGID(),
false));
1314 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
1316 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1317 SchedGroupMask::MFMA, 1, PipelineSyncID, DAG,
TII);
1318 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
1320 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1321 SchedGroupMask::VMEM_READ, 4, PipelineSyncID, DAG,
TII);
1322 SG->addRule(std::make_shared<SharesPredWithPrevNthGroup>(
1323 2,
TII, SG->getSGID(),
true));
1324 SG->addRule(std::make_shared<VMEMSize>(
TII, SG->getSGID(),
false));
1325 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
1327 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1328 SchedGroupMask::MFMA, 1, PipelineSyncID, DAG,
TII);
1329 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
1331 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1332 SchedGroupMask::VMEM_READ, 4, PipelineSyncID, DAG,
TII);
1333 SG->addRule(std::make_shared<SharesPredWithPrevNthGroup>(
1334 4,
TII, SG->getSGID(),
true));
1335 SG->addRule(std::make_shared<VMEMSize>(
TII, SG->getSGID(),
false));
1336 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
1338 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1339 SchedGroupMask::MFMA, 1, PipelineSyncID, DAG,
TII);
1340 SG->initSchedGroup(SyncedInstrs[SG->getSyncID()]);
1344static std::unique_ptr<IGLPStrategy>
1348 case MFMASmallGemmOptID:
1349 return std::make_unique<MFMASmallGemmOpt>(DAG,
TII);
1350 case MFMASmallGemmSingleWaveOptID:
1351 return std::make_unique<MFMASmallGemmSingleWaveOpt>(DAG,
TII);
1372 void addSchedBarrierEdges(
SUnit &SU);
1383 SchedGroupMask invertSchedBarrierMask(SchedGroupMask Mask)
const;
1386 void initSchedGroupBarrierPipelineStage(
1387 std::vector<SUnit>::reverse_iterator RIter);
1389 void initIGLPOpt(
SUnit &SU);
1399 bool IsBottomUp = 1;
1401 IGroupLPDAGMutation() =
default;
1404unsigned SchedGroup::NumSchedGroups = 0;
1416 if (
MI.isMetaInstruction())
1419 else if (((SGMask & SchedGroupMask::ALU) != SchedGroupMask::NONE) &&
1423 else if (((SGMask & SchedGroupMask::VALU) != SchedGroupMask::NONE) &&
1427 else if (((SGMask & SchedGroupMask::SALU) != SchedGroupMask::NONE) &&
1431 else if (((SGMask & SchedGroupMask::MFMA) != SchedGroupMask::NONE) &&
1432 TII->isMFMAorWMMA(
MI))
1435 else if (((SGMask & SchedGroupMask::VMEM) != SchedGroupMask::NONE) &&
1439 else if (((SGMask & SchedGroupMask::VMEM_READ) != SchedGroupMask::NONE) &&
1444 else if (((SGMask & SchedGroupMask::VMEM_WRITE) != SchedGroupMask::NONE) &&
1449 else if (((SGMask & SchedGroupMask::DS) != SchedGroupMask::NONE) &&
1453 else if (((SGMask & SchedGroupMask::DS_READ) != SchedGroupMask::NONE) &&
1454 MI.mayLoad() &&
TII->isDS(
MI))
1457 else if (((SGMask & SchedGroupMask::DS_WRITE) != SchedGroupMask::NONE) &&
1458 MI.mayStore() &&
TII->isDS(
MI))
1462 dbgs() <<
"For SchedGroup with mask " <<
format_hex((
int)SGMask, 10,
true)
1463 << (Result ?
" could classify " :
" unable to classify ") <<
MI);
1468int SchedGroup::link(
SUnit &SU,
bool MakePred,
1469 std::vector<std::pair<SUnit *, SUnit *>> &AddedEdges) {
1470 int MissedEdges = 0;
1471 for (
auto *
A : Collection) {
1473 if (
A ==
B ||
A->getInstr()->getOpcode() == AMDGPU::SCHED_GROUP_BARRIER)
1483 bool Added = tryAddEdge(
A,
B);
1485 AddedEdges.push_back(std::pair(
A,
B));
1493void SchedGroup::link(
SUnit &SU,
bool MakePred) {
1494 for (
auto *
A : Collection) {
1496 if (
A->getInstr()->getOpcode() == AMDGPU::SCHED_GROUP_BARRIER)
1505void SchedGroup::link(
SUnit &SU,
1507 for (
auto *
A : Collection) {
1516void SchedGroup::link(SchedGroup &OtherGroup) {
1517 for (
auto *
B : OtherGroup.Collection)
1521bool SchedGroup::canAddSU(
SUnit &SU)
const {
1523 if (
MI.getOpcode() != TargetOpcode::BUNDLE)
1524 return canAddMI(
MI);
1529 while (
E !=
MBB->
end() &&
E->isBundledWithPred())
1536void SchedGroup::initSchedGroup() {
1537 for (
auto &SU : DAG->
SUnits) {
1546void SchedGroup::initSchedGroup(std::vector<SUnit>::reverse_iterator RIter,
1547 SUnitsToCandidateSGsMap &SyncedInstrs) {
1548 SUnit &InitSU = *RIter;
1549 for (
auto E = DAG->
SUnits.rend(); RIter !=
E; ++RIter) {
1555 SyncedInstrs[&SU].push_back(SGID);
1563void SchedGroup::initSchedGroup(SUnitsToCandidateSGsMap &SyncedInstrs) {
1564 auto I = DAG->
SUnits.rbegin();
1566 for (;
I !=
E; ++
I) {
1572 SyncedInstrs[&SU].push_back(SGID);
1578 if (!TSchedModel || DAGInstrs->
SUnits.empty())
1583 TII =
ST.getInstrInfo();
1585 SyncedSchedGroups.clear();
1586 SyncedInstrs.clear();
1587 bool foundSB =
false;
1588 bool foundIGLP =
false;
1590 unsigned Opc =
R->getInstr()->getOpcode();
1592 if (Opc == AMDGPU::SCHED_BARRIER) {
1593 addSchedBarrierEdges(*R);
1595 }
else if (Opc == AMDGPU::SCHED_GROUP_BARRIER) {
1596 initSchedGroupBarrierPipelineStage(R);
1598 }
else if (Opc == AMDGPU::IGLP_OPT) {
1599 resetEdges(*R, DAG);
1600 if (!foundSB && !foundIGLP)
1606 if (foundSB || foundIGLP) {
1607 PipelineSolver PS(SyncedSchedGroups, SyncedInstrs, DAG, IsBottomUp);
1614void IGroupLPDAGMutation::addSchedBarrierEdges(
SUnit &SchedBarrier) {
1616 assert(
MI.getOpcode() == AMDGPU::SCHED_BARRIER);
1619 resetEdges(SchedBarrier, DAG);
1621 invertSchedBarrierMask((SchedGroupMask)
MI.getOperand(0).getImm());
1622 SchedGroup SG(InvertedMask, std::nullopt, DAG,
TII);
1623 SG.initSchedGroup();
1628 const SUnit *
A,
const SUnit *
B) {
return A->NodeNum >
B->NodeNum; });
1632IGroupLPDAGMutation::invertSchedBarrierMask(SchedGroupMask Mask)
const {
1635 SchedGroupMask InvertedMask = ~Mask;
1638 if ((InvertedMask & SchedGroupMask::ALU) == SchedGroupMask::NONE)
1640 ~SchedGroupMask::VALU & ~SchedGroupMask::SALU & ~SchedGroupMask::MFMA;
1642 else if ((InvertedMask & SchedGroupMask::VALU) == SchedGroupMask::NONE ||
1643 (InvertedMask & SchedGroupMask::SALU) == SchedGroupMask::NONE ||
1644 (InvertedMask & SchedGroupMask::MFMA) == SchedGroupMask::NONE)
1645 InvertedMask &= ~SchedGroupMask::ALU;
1648 if ((InvertedMask & SchedGroupMask::VMEM) == SchedGroupMask::NONE)
1649 InvertedMask &= ~SchedGroupMask::VMEM_READ & ~SchedGroupMask::VMEM_WRITE;
1651 else if ((InvertedMask & SchedGroupMask::VMEM_READ) == SchedGroupMask::NONE ||
1652 (InvertedMask & SchedGroupMask::VMEM_WRITE) == SchedGroupMask::NONE)
1653 InvertedMask &= ~SchedGroupMask::VMEM;
1656 if ((InvertedMask & SchedGroupMask::DS) == SchedGroupMask::NONE)
1657 InvertedMask &= ~SchedGroupMask::DS_READ & ~SchedGroupMask::DS_WRITE;
1659 else if ((InvertedMask & SchedGroupMask::DS_READ) == SchedGroupMask::NONE ||
1660 (InvertedMask & SchedGroupMask::DS_WRITE) == SchedGroupMask::NONE)
1661 InvertedMask &= ~SchedGroupMask::DS;
1663 return InvertedMask;
1666void IGroupLPDAGMutation::initSchedGroupBarrierPipelineStage(
1667 std::vector<SUnit>::reverse_iterator RIter) {
1670 resetEdges(*RIter, DAG);
1677 auto &SG = SyncedSchedGroups[SyncID].emplace_back((SchedGroupMask)SGMask,
1680 SG.initSchedGroup(RIter, SyncedInstrs[SG.getSyncID()]);
1683void IGroupLPDAGMutation::initIGLPOpt(
SUnit &SU) {
1684 IGLPStrategyID StrategyID =
1686 auto S = createIGLPStrategy(StrategyID, DAG,
TII);
1687 if (S->shouldApplyStrategy(DAG)) {
1688 IsBottomUp = S->IsBottomUp;
1689 S->applyIGLPStrategy(SyncedInstrs, SyncedSchedGroups);
1698 return std::make_unique<IGroupLPDAGMutation>();
unsigned const MachineRegisterInfo * MRI
Provides AMDGPU specific target descriptions.
The AMDGPU TargetMachine interface definition for hw codegen targets.
#define LLVM_MARK_AS_BITMASK_ENUM(LargestValue)
LLVM_MARK_AS_BITMASK_ENUM lets you opt in an individual enum type so you can perform bitwise operatio...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the DenseMap class.
const HexagonInstrInfo * TII
unsigned const TargetRegisterInfo * TRI
Interface definition for SIInstrInfo.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static std::optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)
Returns the opcode of Values or ~0 if they do not all agree.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
size - Get the array size.
This class represents an Operation in the Expression.
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Representation of each machine instruction.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
bool mayStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly modify memory.
const MachineOperand & getOperand(unsigned i) const
@ Artificial
Arbitrary strong DAG edge (no real dependence).
Scheduling unit. This is a node in the scheduling DAG.
unsigned NodeNum
Entry # of node in the node vector.
void removePred(const SDep &D)
Removes the specified edge as a pred of the current node if it exists.
SmallVector< SDep, 4 > Succs
All sunit successors.
SmallVector< SDep, 4 > Preds
All sunit predecessors.
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
A ScheduleDAG for scheduling lists of MachineInstr.
const TargetSchedModel * getSchedModel() const
Gets the machine model for instruction scheduling.
bool addEdge(SUnit *SuccSU, const SDep &PredDep)
Add a DAG edge to the given SU with the given predecessor dependence data.
bool IsReachable(SUnit *SU, SUnit *TargetSU)
IsReachable - Checks if SU is reachable from TargetSU.
bool canAddEdge(SUnit *SuccSU, SUnit *PredSU)
True if an edge can be added from PredSU to SuccSU without creating a cycle.
void dump() const override
ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply schedules machine instructions ac...
Mutate the DAG as a postpass after normal DAG building.
virtual void apply(ScheduleDAGInstrs *DAG)=0
std::vector< SUnit > SUnits
The scheduling units.
MachineFunction & MF
Machine function.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
reverse_iterator rbegin()
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Provide an instruction scheduling machine model to CodeGen passes.
An efficient, type-erasing, non-owning reference to a callable.
Iterator for intrusive lists based on ilist_node.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void apply(Opt *O, const Mod &M, const Mods &... Ms)
initializer< Ty > init(const Ty &Val)
void link(std::unique_ptr< LinkGraph > G, std::unique_ptr< JITLinkContext > Ctx)
Link the given graph.
This is an optimization pass for GlobalISel generic memory operations.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
std::unique_ptr< ScheduleDAGMutation > createIGroupLPDAGMutation()
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
FormattedNumber format_hex(uint64_t N, unsigned Width, bool Upper=false)
format_hex - Output N as a fixed width hexadecimal.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.