1//===--- AMDGPUIGroupLP.cpp - AMDGPU IGroupLP ------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// \file This file defines a set of schedule DAG mutations that can be used to
10// override default scheduler behavior to enforce specific scheduling patterns.
11// They should be used in cases where runtime performance considerations such as
12// inter-wavefront interactions, mean that compile-time heuristics cannot
13// predict the optimal instruction ordering, or in kernels where optimum
14// instruction scheduling is important enough to warrant manual intervention.
15//
16//===----------------------------------------------------------------------===//
17
18#include "AMDGPUIGroupLP.h"
19#include "SIInstrInfo.h"
20#include "SIMachineFunctionInfo.h"
21#include "llvm/CodeGen/MachineScheduler.h"
22#include "llvm/CodeGen/TargetOpcodes.h"
23
24using namespace llvm;
25using namespace llvm::AMDGPU;
26
27#define DEBUG_TYPE "igrouplp"
28
29namespace {
30
31class SchedGroup;
32
33// InstructionRule class is used to enact a filter which determines whether or
34// not an SU maps to a given SchedGroup. It contains complementary data
35// structures (e.g Cache) to help those filters.
36class InstructionRule {
37protected:
38 const SIInstrInfo *TII;
39 unsigned SGID;
40 // A cache made available to the Filter to store SUnits for subsequent
41 // invocations of the Filter
42 std::optional<SmallVector<SUnit *, 4>> Cache;
43
44public:
45 virtual bool
46 apply(const SUnit *, const ArrayRef<SUnit *>,
47 SmallVectorImpl<SchedGroup> &) {
48 return true;
49 };
50
51 InstructionRule(const SIInstrInfo *TII, unsigned SGID,
52 bool NeedsCache = false)
53 : TII(TII), SGID(SGID) {
54 if (NeedsCache) {
55 Cache = SmallVector<SUnit *, 4>();
56 }
57 }
58
59 virtual ~InstructionRule() = default;
60};
61
62using SUnitsToCandidateSGsMap = DenseMap<SUnit *, SmallVector<int, 4>>;
63
64// Classify instructions into groups to enable fine tuned control over the
65// scheduler. These groups may be more specific than current SchedModel
66// instruction classes.
67class SchedGroup {
68private:
69 // Mask that defines which instruction types can be classified into this
70 // SchedGroup. The instruction types correspond to the mask from SCHED_BARRIER
71 // and SCHED_GROUP_BARRIER.
72 SchedGroupMask SGMask;
73
74 // Maximum number of SUnits that can be added to this group.
75 std::optional<unsigned> MaxSize;
76
77 // SchedGroups will only synchronize with other SchedGroups that have the same
78 // SyncID.
79 int SyncID = 0;
80
81 // SGID is used to map instructions to candidate SchedGroups
82 unsigned SGID;
83
84 // The different rules each instruction in this SchedGroup must conform to
85 SmallVector<std::shared_ptr<InstructionRule>, 4> Rules;
86
87 // Count of the number of created SchedGroups, used to initialize SGID.
88 static unsigned NumSchedGroups;
89
90 // Use SGMask to determine whether we can classify MI as a member of this
91 // SchedGroup object.
92 bool canAddMI(const MachineInstr &MI) const;
93
94public:
95 // Collection of SUnits that are classified as members of this group.
96 SmallVector<SUnit *, 32> Collection;
97
98 ScheduleDAGInstrs *DAG;
99 const SIInstrInfo *TII;
100
101 // Try to add and edge from SU A to SU B.
102 bool tryAddEdge(SUnit *A, SUnit *B);
103
104 // Returns true if SU can be added to this SchedGroup.
105 bool canAddSU(SUnit &SU) const;
106
107 // Add DAG dependencies from all SUnits in this SchedGroup and this SU. If
108 // MakePred is true, SU will be a predecessor of the SUnits in this
109 // SchedGroup, otherwise SU will be a successor.
110 void link(SUnit &SU, bool MakePred = false);
111
112 // Add DAG dependencies and track which edges are added, and the count of
113 // missed edges
114 int link(SUnit &SU, bool MakePred,
115 std::list<std::pair<SUnit *, SUnit *>> &AddedEdges);
116
117 // Add DAG dependencies from all SUnits in this SchedGroup and this SU.
118 // Use the predicate to determine whether SU should be a predecessor (P =
119 // true) or a successor (P = false) of this SchedGroup.
120 void link(SUnit &SU, function_ref<bool(const SUnit *A, const SUnit *B)> P);
121
122 // Add DAG dependencies such that SUnits in this group shall be ordered
123 // before SUnits in OtherGroup.
124 void link(SchedGroup &OtherGroup);
125
126 // Returns true if no more instructions may be added to this group.
127 bool isFull() const { return MaxSize && Collection.size() >= *MaxSize; }
128
129 // Append a constraint that SUs must meet in order to fit into this
130 // SchedGroup. Since many rules involve the relationship between a SchedGroup
131 // and the SUnits in other SchedGroups, rules are checked at Pipeline Solve
132 // time (rather than SchedGroup init time.)
133 void addRule(std::shared_ptr<InstructionRule> NewRule) {
134 Rules.push_back(Elt: NewRule);
135 }
136
137 // Returns true if the SU matches all rules
138 bool allowedByRules(const SUnit *SU,
139 SmallVectorImpl<SchedGroup> &SyncPipe) const {
140 for (auto &Rule : Rules) {
141 if (!Rule->apply(SU, Collection, SyncPipe))
142 return false;
143 }
144 return true;
145 }
146
147 // Add SU to the SchedGroup.
148 void add(SUnit &SU) {
149 LLVM_DEBUG(dbgs() << "For SchedGroup with mask "
150 << format_hex((int)SGMask, 10, true) << " adding "
151 << *SU.getInstr());
152 Collection.push_back(Elt: &SU);
153 }
154
155 // Remove last element in the SchedGroup
156 void pop() { Collection.pop_back(); }
157
158 template <class T>
159 void findCandidateSUnits(T Begin, T End,
160 SUnitsToCandidateSGsMap &SyncedInstrs);
161
162 /// Find each SUnit in the DAG that could potentially be added to
163 /// this SchedGroup and add the SGID to the candidate SchedGroups
164 /// for SU in \p SyncedInstrs.
165 void findCandidateSUnits(SUnitsToCandidateSGsMap &SyncedInstrs);
166
167 int getSyncID() { return SyncID; }
168
169 int getSGID() { return SGID; }
170
171 SchedGroupMask getMask() { return SGMask; }
172
173 SchedGroup(SchedGroupMask SGMask, std::optional<unsigned> MaxSize,
174 ScheduleDAGInstrs *DAG, const SIInstrInfo *TII)
175 : SGMask(SGMask), MaxSize(MaxSize), DAG(DAG), TII(TII) {
176 SGID = NumSchedGroups++;
177 }
178
179 SchedGroup(SchedGroupMask SGMask, std::optional<unsigned> MaxSize, int SyncID,
180 ScheduleDAGInstrs *DAG, const SIInstrInfo *TII)
181 : SGMask(SGMask), MaxSize(MaxSize), SyncID(SyncID), DAG(DAG), TII(TII) {
182 SGID = NumSchedGroups++;
183 }
184};
185
186using SUToCandSGsPair = std::pair<SUnit *, SmallVector<int, 4>>;
187using SUsToCandSGsVec = SmallVector<SUToCandSGsPair, 4>;
188
189// The PipelineSolver is used to assign SUnits to SchedGroups in a pipeline
190// in non-trivial cases. For example, if the requested pipeline is
191// {VMEM_READ, VALU, MFMA, VMEM_READ} and we encounter a VMEM_READ instruction
192// in the DAG, then we will have an instruction that can not be trivially
193// assigned to a SchedGroup. The PipelineSolver class implements two algorithms
194// to find a good solution to the pipeline -- a greedy algorithm and an exact
195// algorithm. The exact algorithm has an exponential time complexity and should
196// only be used for small sized problems or medium sized problems where an exact
197// solution is highly desired.
198class PipelineSolver {
199 const AMDGPUOptions &CLOpts;
200 [[maybe_unused]] ScheduleDAGMI *DAG;
201
202 // Instructions that can be assigned to multiple SchedGroups
203 DenseMap<int, SUnitsToCandidateSGsMap> SyncedInstrs;
204 SmallVector<SUsToCandSGsVec, 4> PipelineInstrs;
205 DenseMap<int, SmallVector<SchedGroup, 4>> SyncedSchedGroups;
206 // The current working pipeline
207 SmallVector<SmallVector<SchedGroup, 4>, 4> CurrPipeline;
208 // The pipeline that has the best solution found so far
209 SmallVector<SmallVector<SchedGroup, 4>, 4> BestPipeline;
210
211 // Whether or not we actually have any SyncedInstrs to try to solve.
212 bool NeedsSolver = false;
213
214 // Compute an estimate of the size of search tree -- the true size is
215 // the product of each conflictedInst.Matches.size() across all SyncPipelines
216 unsigned computeProblemSize();
217
218 // The cost penalty of not assigning a SU to a SchedGroup
219 int MissPenalty = 0;
220
221 // Costs in terms of the number of edges we are unable to add
222 int BestCost = -1;
223 int CurrCost = 0;
224
225 // Index pointing to the conflicting instruction that is currently being
226 // fitted
227 int CurrConflInstNo = 0;
228 // Index to the pipeline that is currently being fitted
229 int CurrSyncGroupIdx = 0;
230 // The first non trivial pipeline
231 int BeginSyncGroupIdx = 0;
232
233 // How many branches we have explored
234 uint64_t BranchesExplored = 0;
235
236 // The direction in which we process the candidate SchedGroups per SU
237 bool IsBottomUp = true;
238
239 // Update indices to fit next conflicting instruction
240 void advancePosition();
241 // Recede indices to attempt to find better fit for previous conflicting
242 // instruction
243 void retreatPosition();
244
245 // The exponential time algorithm which finds the provably best fit
246 bool solveExact();
247 // The polynomial time algorithm which attempts to find a good fit
248 bool solveGreedy();
249 // Find the best SchedGroup for the current SU using the heuristic given all
250 // current information. One step in the greedy algorithm. Templated against
251 // the SchedGroup iterator (either reverse or forward).
252 template <typename T>
253 void greedyFind(std::list<std::pair<SUnit *, SUnit *>> &AddedEdges, T I, T E);
254 // Whether or not the current solution is optimal
255 bool checkOptimal();
256 // Populate the ready list, prioiritizing fewest missed edges first
257 // Templated against the SchedGroup iterator (either reverse or forward).
258 template <typename T>
259 void populateReadyList(SmallVectorImpl<std::pair<int, int>> &ReadyList, T I,
260 T E);
261 // Add edges corresponding to the SchedGroups as assigned by solver
262 void makePipeline();
263 // Link the SchedGroups in the best found pipeline.
264 // Tmplated against the SchedGroup iterator (either reverse or forward).
265 template <typename T> void linkSchedGroups(T I, T E);
266 // Add the edges from the SU to the other SchedGroups in pipeline, and
267 // return the number of edges missed.
268 int addEdges(SmallVectorImpl<SchedGroup> &SyncPipeline, SUnit *SU, int SGID,
269 std::list<std::pair<SUnit *, SUnit *>> &AddedEdges);
270
271 /// This class is used to build the edge set implied by an
272 /// assignment of an SUnit to a SchedGroup and to compute the cost
273 /// (edges that cannot be assigned without introducing cycles) of
274 /// the assignment.
275 class EdgeSetBuilder {
276 SUnit *SU;
277 SmallVectorImpl<SchedGroup> &SyncPipeline;
278 bool IsBottomUp;
279 DenseSet<SUnit *> InitialPreds;
280 DenseSet<SUnit *> Succs;
281 bool Initialized = false;
282
283 /// Compute reachability via DFS. If ComputePreds is true, follows
284 /// predecessor edges; otherwise follows successor edges.
285 template <bool ComputePreds>
286 static void computeReachable(DenseSet<SUnit *> &Reachable, SUnit *Start);
287
288 /// Compute all nodes that can reach Start via predecessor edges, including
289 /// Start itself.
290 static void computePreds(DenseSet<SUnit *> &Preds, SUnit *Start);
291
292 /// Compute all nodes reachable from Start via successor edges, including
293 /// Start itself.
294 static void computeSuccs(DenseSet<SUnit *> &Succs, SUnit *Start);
295
296 public:
297 EdgeSetBuilder(SUnit *SU, SmallVectorImpl<SchedGroup> &SyncPipeline,
298 bool IsBottomUp)
299 : SU(SU), SyncPipeline(SyncPipeline), IsBottomUp(IsBottomUp) {}
300
301 /// Determine the edges implied by assigning SU to the SchedGroup
302 /// with ID SGID. Edges are added to NewEdges unless they
303 /// introduce cycles. Return the number of edges that cannot be
304 /// added.
305 int build(int SGID, std::list<std::pair<SUnit *, SUnit *>> &NewEdges);
306
307 private:
308 template <typename T>
309 int buildImpl(int SGID, const iterator_range<T> SchedGroups,
310 std::list<std::pair<SUnit *, SUnit *>> &NewEdges);
311 };
312
313 /// Link the pipeline as if \p SU was in the SchedGroup with ID \p SGID. It
314 /// returns the cost (in terms of missed pipeline edges), and tracks the edges
315 /// added in \p AddedEdges
316 template <typename T>
317 int linkSUnit(SUnit *SU, int SGID,
318 std::list<std::pair<SUnit *, SUnit *>> &AddedEdges, T I, T E);
319 /// Remove the edges passed via \p AddedEdges
320 void removeEdges(const std::list<std::pair<SUnit *, SUnit *>> &AddedEdges);
321 // Convert the passed in maps to arrays for bidirectional iterators
322 void convertSyncMapsToArrays();
323
324 void reset();
325
326public:
327 // Invoke the solver to map instructions to instruction groups. Heuristic &&
328 // command-line-option determines to use exact or greedy algorithm.
329 void solve();
330
331 PipelineSolver(DenseMap<int, SmallVector<SchedGroup, 4>> &SyncedSchedGroups,
332 DenseMap<int, SUnitsToCandidateSGsMap> &SyncedInstrs,
333 ScheduleDAGMI *DAG, bool IsBottomUp = true)
334 : CLOpts(DAG->MF.getSubtarget<GCNSubtarget>().getCLOpts()), DAG(DAG),
335 SyncedInstrs(SyncedInstrs), SyncedSchedGroups(SyncedSchedGroups),
336 IsBottomUp(IsBottomUp) {
337
338 for (auto &PipelineInstrs : SyncedInstrs) {
339 if (!PipelineInstrs.second.empty()) {
340 NeedsSolver = true;
341 break;
342 }
343 }
344
345 if (!NeedsSolver)
346 return;
347
348 convertSyncMapsToArrays();
349
350 CurrPipeline = BestPipeline;
351
352 while (static_cast<size_t>(BeginSyncGroupIdx) < PipelineInstrs.size() &&
353 PipelineInstrs[BeginSyncGroupIdx].empty())
354 ++BeginSyncGroupIdx;
355
356 if (static_cast<size_t>(BeginSyncGroupIdx) >= PipelineInstrs.size())
357 return;
358 }
359};
360
361void PipelineSolver::reset() {
362
363 for (auto &SyncPipeline : CurrPipeline) {
364 for (auto &SG : SyncPipeline) {
365 SmallVector<SUnit *, 32> TempCollection = SG.Collection;
366 SG.Collection.clear();
367 auto *SchedBarr = llvm::find_if(Range&: TempCollection, P: [](SUnit *SU) {
368 return SU->getInstr()->getOpcode() == AMDGPU::SCHED_GROUP_BARRIER;
369 });
370 if (SchedBarr != TempCollection.end())
371 SG.Collection.push_back(Elt: *SchedBarr);
372 }
373 }
374
375 CurrSyncGroupIdx = BeginSyncGroupIdx;
376 CurrConflInstNo = 0;
377 CurrCost = 0;
378}
379
380void PipelineSolver::convertSyncMapsToArrays() {
381 for (auto &SyncPipe : SyncedSchedGroups) {
382 BestPipeline.insert(I: BestPipeline.begin(), Elt: SyncPipe.second);
383 }
384
385 int PipelineIDx = SyncedInstrs.size() - 1;
386 PipelineInstrs.resize(N: SyncedInstrs.size());
387 for (auto &SyncInstrMap : SyncedInstrs) {
388 for (auto &SUsToCandSGs : SyncInstrMap.second) {
389 if (PipelineInstrs[PipelineIDx].empty()) {
390 PipelineInstrs[PipelineIDx].push_back(
391 Elt: std::pair(SUsToCandSGs.first, SUsToCandSGs.second));
392 continue;
393 }
394 auto *SortPosition = PipelineInstrs[PipelineIDx].begin();
395 // Insert them in sorted order -- this allows for good parsing order in
396 // the greedy algorithm
397 while (SortPosition != PipelineInstrs[PipelineIDx].end() &&
398 SUsToCandSGs.first->NodeNum > SortPosition->first->NodeNum)
399 ++SortPosition;
400 PipelineInstrs[PipelineIDx].insert(
401 I: SortPosition, Elt: std::pair(SUsToCandSGs.first, SUsToCandSGs.second));
402 }
403 --PipelineIDx;
404 }
405}
406
407template <typename T> void PipelineSolver::linkSchedGroups(T I, T E) {
408 for (; I != E; ++I) {
409 auto &GroupA = *I;
410 for (auto J = std::next(I); J != E; ++J) {
411 auto &GroupB = *J;
412 GroupA.link(GroupB);
413 }
414 }
415}
416
417void PipelineSolver::makePipeline() {
418 // Preserve the order of barrier for subsequent SchedGroupBarrier mutations
419 for (auto &SyncPipeline : BestPipeline) {
420 LLVM_DEBUG(dbgs() << "Printing SchedGroups\n");
421 for (auto &SG : SyncPipeline) {
422 LLVM_DEBUG(dbgs() << "SchedGroup with SGID " << SG.getSGID()
423 << " has: \n");
424 SUnit *SGBarr = nullptr;
425 for (auto &SU : SG.Collection) {
426 if (SU->getInstr()->getOpcode() == AMDGPU::SCHED_GROUP_BARRIER)
427 SGBarr = SU;
428 LLVM_DEBUG(dbgs() << *SU << "\n");
429 }
430 // Command line requested IGroupLP doesn't have SGBarr
431 if (!SGBarr)
432 continue;
433 SG.link(SU&: *SGBarr, MakePred: false);
434 }
435 }
436
437 for (auto &SyncPipeline : BestPipeline) {
438 IsBottomUp ? linkSchedGroups(I: SyncPipeline.rbegin(), E: SyncPipeline.rend())
439 : linkSchedGroups(I: SyncPipeline.begin(), E: SyncPipeline.end());
440 }
441}
442
443template <typename T>
444int PipelineSolver::linkSUnit(
445 SUnit *SU, int SGID, std::list<std::pair<SUnit *, SUnit *>> &AddedEdges,
446 T I, T E) {
447 bool MakePred = false;
448 int AddedCost = 0;
449 for (; I < E; ++I) {
450 if (I->getSGID() == SGID) {
451 MakePred = true;
452 continue;
453 }
454 auto Group = *I;
455 AddedCost += Group.link(*SU, MakePred, AddedEdges);
456 assert(AddedCost >= 0);
457 }
458 return AddedCost;
459}
460
461template <bool ComputePreds>
462void PipelineSolver::EdgeSetBuilder::computeReachable(
463 DenseSet<SUnit *> &Reachable, SUnit *Start) {
464 if (!Reachable.insert(V: Start).second)
465 return;
466
467 SmallVector<SUnit *, 32> WorkList = {Start};
468
469 while (!WorkList.empty()) {
470 SUnit *Current = WorkList.pop_back_val();
471
472 for (const SDep &Dep : ComputePreds ? Current->Preds : Current->Succs) {
473 if (Reachable.insert(V: Dep.getSUnit()).second)
474 WorkList.push_back(Elt: Dep.getSUnit());
475 }
476 }
477}
478
479void PipelineSolver::EdgeSetBuilder::computePreds(DenseSet<SUnit *> &Preds,
480 SUnit *Start) {
481 computeReachable</*ComputePreds*/ true>(Reachable&: Preds, Start);
482}
483
484void PipelineSolver::EdgeSetBuilder::computeSuccs(DenseSet<SUnit *> &Succs,
485 SUnit *Start) {
486 computeReachable</*ComputePreds*/ false>(Reachable&: Succs, Start);
487}
488
489int PipelineSolver::EdgeSetBuilder::build(
490 int SGID, std::list<std::pair<SUnit *, SUnit *>> &NewEdges) {
491 if (!Initialized) {
492 computePreds(Preds&: InitialPreds, Start: SU);
493 computeSuccs(Succs, Start: SU);
494 Initialized = true;
495 }
496
497 // See comment in addEdges concerning the iterator direction.
498 return IsBottomUp ? buildImpl(SGID, SchedGroups: reverse(C&: SyncPipeline), NewEdges)
499 : buildImpl(SGID,
500 SchedGroups: llvm::make_range(x: SyncPipeline.begin(),
501 y: SyncPipeline.end()),
502 NewEdges);
503}
504
505template <typename T>
506int PipelineSolver::EdgeSetBuilder::buildImpl(
507 int SGID, iterator_range<T> SchedGroups,
508 std::list<std::pair<SUnit *, SUnit *>> &NewEdges) {
509
510 // Determine the edges that will be added to the DAG if SU is
511 // assigned to the SchedGroup SG with the given SGID. It might be
512 // impossible to add some edges because they would introduce
513 // cycles. The number of such edges is counted and returned, all
514 // other edges are added to NewEdges.
515 //
516 // SU is made a successor of SUnits in SchedGroups before SG, and a
517 // predecessor of SUnits after SG. In each case, the cycle check
518 // requires reachability information for the opposing direction.
519
520 // Nodes U that can reach SU (U ~> SU).
521 // Will be extended as new edges are added and hence cannot be
522 // shared between calls to this function, in contrast to Succs.
523 DenseSet<SUnit *> Preds = InitialPreds;
524
525 int MissedEdges = 0;
526 bool MakePred = false;
527 for (SchedGroup &SG : SchedGroups) {
528 if (SG.getSGID() == SGID) {
529 MakePred = true;
530 continue;
531 }
532
533 for (SUnit *A : SG.Collection) {
534 if (A->getInstr()->getOpcode() == AMDGPU::SCHED_GROUP_BARRIER)
535 continue;
536
537 if (MakePred) {
538 // Try add SU -> A.
539 if (Preds.contains(V: A)) { // Would add cycle since A ~> SU.
540 ++MissedEdges;
541 continue;
542 }
543 // Succs does not need to be updated, since it will not be
544 // queried after entering the MakePred case.
545 NewEdges.emplace_back(args&: SU, args&: A);
546 continue;
547 }
548
549 // Try add A -> SU.
550 if (Succs.contains(V: A)) { // Would add cycle since SU ~> A.
551 ++MissedEdges;
552 continue;
553 }
554 NewEdges.emplace_back(args&: A, args&: SU);
555 computePreds(Preds, Start: A);
556 }
557 }
558
559 return MissedEdges;
560}
561
562int PipelineSolver::addEdges(
563 SmallVectorImpl<SchedGroup> &SyncPipeline, SUnit *SU, int SGID,
564 std::list<std::pair<SUnit *, SUnit *>> &AddedEdges) {
565
566 // For IsBottomUp, the first SchedGroup in SyncPipeline contains the
567 // instructions that are the ultimate successors in the resultant mutation.
568 // Therefore, in such a configuration, the SchedGroups occurring before the
569 // candidate SGID are successors of the candidate SchedGroup, thus the current
570 // SU should be linked as a predecessor to SUs in those SchedGroups. The
571 // opposite is true if !IsBottomUp. IsBottomUp occurs in the case of multiple
572 // SCHED_GROUP_BARRIERS, or if a user specifies IGLP_OPT SchedGroups using
573 // IsBottomUp (in reverse).
574 return IsBottomUp ? linkSUnit(SU, SGID, AddedEdges, I: SyncPipeline.rbegin(),
575 E: SyncPipeline.rend())
576 : linkSUnit(SU, SGID, AddedEdges, I: SyncPipeline.begin(),
577 E: SyncPipeline.end());
578}
579
580void PipelineSolver::removeEdges(
581 const std::list<std::pair<SUnit *, SUnit *>> &EdgesToRemove) {
582 // Only remove the edges that we have added when testing
583 // the fit.
584 for (auto &PredSuccPair : EdgesToRemove) {
585 SUnit *Pred = PredSuccPair.first;
586 SUnit *Succ = PredSuccPair.second;
587
588 auto *Match = llvm::find_if(Range&: Succ->Preds, P: [&Pred](SDep &P) {
589 return P.getSUnit() == Pred && P.isArtificial();
590 });
591 if (Match != Succ->Preds.end())
592 Succ->removePred(D: *Match);
593 }
594}
595
596void PipelineSolver::advancePosition() {
597 ++CurrConflInstNo;
598
599 if (static_cast<size_t>(CurrConflInstNo) >=
600 PipelineInstrs[CurrSyncGroupIdx].size()) {
601 CurrConflInstNo = 0;
602 ++CurrSyncGroupIdx;
603 // Advance to next non-trivial pipeline
604 while (static_cast<size_t>(CurrSyncGroupIdx) < PipelineInstrs.size() &&
605 PipelineInstrs[CurrSyncGroupIdx].empty())
606 ++CurrSyncGroupIdx;
607 }
608}
609
610void PipelineSolver::retreatPosition() {
611 assert(CurrConflInstNo >= 0);
612 assert(CurrSyncGroupIdx >= 0);
613
614 if (CurrConflInstNo > 0) {
615 --CurrConflInstNo;
616 return;
617 }
618
619 if (CurrConflInstNo == 0) {
620 // If we return to the starting position, we have explored
621 // the entire tree
622 if (CurrSyncGroupIdx == BeginSyncGroupIdx)
623 return;
624
625 --CurrSyncGroupIdx;
626 // Go to previous non-trivial pipeline
627 while (PipelineInstrs[CurrSyncGroupIdx].empty())
628 --CurrSyncGroupIdx;
629
630 CurrConflInstNo =
631 static_cast<int>(PipelineInstrs[CurrSyncGroupIdx].size() - 1);
632 }
633}
634
635bool PipelineSolver::checkOptimal() {
636 if (static_cast<size_t>(CurrSyncGroupIdx) == PipelineInstrs.size()) {
637 if (BestCost == -1 || CurrCost < BestCost) {
638 BestPipeline = CurrPipeline;
639 BestCost = CurrCost;
640 LLVM_DEBUG(dbgs() << "Found Fit with cost " << BestCost << "\n");
641 }
642 assert(BestCost >= 0);
643 }
644
645 bool DoneExploring = false;
646 if (CLOpts.igrouplp_exact_solver_max_branches > 0 &&
647 BranchesExplored >= CLOpts.igrouplp_exact_solver_max_branches)
648 DoneExploring = true;
649
650 return (DoneExploring || BestCost == 0);
651}
652
653template <typename T>
654void PipelineSolver::populateReadyList(
655 SmallVectorImpl<std::pair<int, int>> &ReadyList, T I, T E) {
656 SUToCandSGsPair CurrSU = PipelineInstrs[CurrSyncGroupIdx][CurrConflInstNo];
657 auto SyncPipeline = CurrPipeline[CurrSyncGroupIdx];
658 assert(CurrSU.second.size() >= 1);
659
660 for (; I != E; ++I) {
661 std::list<std::pair<SUnit *, SUnit *>> AddedEdges;
662 int CandSGID = *I;
663 SchedGroup *Match = llvm::find_if(SyncPipeline, [CandSGID](SchedGroup &SG) {
664 return SG.getSGID() == CandSGID;
665 });
666 assert(Match);
667
668 if (CLOpts.igrouplp_exact_solver_cost_heur) {
669 if (Match->isFull()) {
670 ReadyList.push_back(Elt: std::pair(*I, MissPenalty));
671 continue;
672 }
673
674 int TempCost = addEdges(SyncPipeline, SU: CurrSU.first, SGID: CandSGID, AddedEdges);
675 ReadyList.push_back(Elt: std::pair(*I, TempCost));
676 removeEdges(EdgesToRemove: AddedEdges);
677 } else
678 ReadyList.push_back(Elt: std::pair(*I, -1));
679 }
680
681 if (CLOpts.igrouplp_exact_solver_cost_heur)
682 std::sort(first: ReadyList.begin(), last: ReadyList.end(), comp: llvm::less_second());
683
684 assert(ReadyList.size() == CurrSU.second.size());
685}
686
687bool PipelineSolver::solveExact() {
688 if (checkOptimal())
689 return true;
690
691 if (static_cast<size_t>(CurrSyncGroupIdx) == PipelineInstrs.size())
692 return false;
693
694 assert(static_cast<size_t>(CurrSyncGroupIdx) < PipelineInstrs.size());
695 assert(static_cast<size_t>(CurrConflInstNo) <
696 PipelineInstrs[CurrSyncGroupIdx].size());
697 SUToCandSGsPair CurrSU = PipelineInstrs[CurrSyncGroupIdx][CurrConflInstNo];
698 LLVM_DEBUG(dbgs() << "Fitting " << *CurrSU.first << " in Pipeline # "
699 << CurrSyncGroupIdx << "\n");
700
701 // SchedGroup -> Cost pairs
702 SmallVector<std::pair<int, int>, 4> ReadyList;
703 // Prioritize the candidate sched groups in terms of lowest cost first
704 IsBottomUp ? populateReadyList(ReadyList, I: CurrSU.second.rbegin(),
705 E: CurrSU.second.rend())
706 : populateReadyList(ReadyList, I: CurrSU.second.begin(),
707 E: CurrSU.second.end());
708
709 auto *I = ReadyList.begin();
710 auto *E = ReadyList.end();
711 for (; I != E; ++I) {
712 // If we are trying SGs in least cost order, and the current SG is cost
713 // infeasible, then all subsequent SGs will also be cost infeasible, so we
714 // can prune.
715 if (BestCost != -1 && (CurrCost + I->second > BestCost))
716 return false;
717
718 int CandSGID = I->first;
719 int AddedCost = 0;
720 std::list<std::pair<SUnit *, SUnit *>> AddedEdges;
721 auto &SyncPipeline = CurrPipeline[CurrSyncGroupIdx];
722 SchedGroup *Match = llvm::find_if(Range&: SyncPipeline, P: [CandSGID](SchedGroup &SG) {
723 return SG.getSGID() == CandSGID;
724 });
725 assert(Match);
726
727 if (Match->isFull())
728 continue;
729
730 if (!Match->allowedByRules(SU: CurrSU.first, SyncPipe&: SyncPipeline))
731 continue;
732
733 LLVM_DEBUG(dbgs() << "Assigning to SchedGroup with Mask "
734 << (int)Match->getMask() << "and ID " << CandSGID
735 << "\n");
736 Match->add(SU&: *CurrSU.first);
737 AddedCost = addEdges(SyncPipeline, SU: CurrSU.first, SGID: CandSGID, AddedEdges);
738 LLVM_DEBUG(dbgs() << "Cost of Assignment: " << AddedCost << "\n");
739 CurrCost += AddedCost;
740 advancePosition();
741 ++BranchesExplored;
742 bool FinishedExploring = false;
743 // If the Cost after adding edges is greater than a known solution,
744 // backtrack
745 if (CurrCost < BestCost || BestCost == -1) {
746 if (solveExact()) {
747 FinishedExploring = BestCost != 0;
748 if (!FinishedExploring)
749 return true;
750 }
751 }
752
753 retreatPosition();
754 CurrCost -= AddedCost;
755 removeEdges(EdgesToRemove: AddedEdges);
756 Match->pop();
757 CurrPipeline[CurrSyncGroupIdx] = SyncPipeline;
758 if (FinishedExploring)
759 return true;
760 }
761
762 // Try the pipeline where the current instruction is omitted
763 // Potentially if we omit a problematic instruction from the pipeline,
764 // all the other instructions can nicely fit.
765 CurrCost += MissPenalty;
766 advancePosition();
767
768 LLVM_DEBUG(dbgs() << "NOT Assigned " << *CurrSU.first << "\n");
769
770 bool FinishedExploring = false;
771 if (CurrCost < BestCost || BestCost == -1) {
772 if (solveExact()) {
773 bool FinishedExploring = BestCost != 0;
774 if (!FinishedExploring)
775 return true;
776 }
777 }
778
779 retreatPosition();
780 CurrCost -= MissPenalty;
781 return FinishedExploring;
782}
783
784template <typename T>
785void PipelineSolver::greedyFind(
786 std::list<std::pair<SUnit *, SUnit *>> &AddedEdges, T I, T E) {
787 SUToCandSGsPair CurrSU = PipelineInstrs[CurrSyncGroupIdx][CurrConflInstNo];
788
789 struct GroupInfo {
790 SchedGroup *SG;
791 std::list<std::pair<SUnit *, SUnit *>> Edges;
792 int Cost = 0;
793 };
794 std::optional<GroupInfo> Best;
795
796 auto &SyncPipeline = CurrPipeline[CurrSyncGroupIdx];
797 LLVM_DEBUG(dbgs() << "Fitting " << *CurrSU.first << " in Pipeline # "
798 << CurrSyncGroupIdx << "\n");
799
800 EdgeSetBuilder Builder(CurrSU.first, SyncPipeline, IsBottomUp);
801
802 // Since we have added the potential SchedGroups from bottom up, but
803 // traversed the DAG from top down, parse over the groups from last to
804 // first. If we fail to do this for the greedy algorithm, the solution will
805 // likely not be good in more complex cases.
806 for (; I != E; ++I) {
807 int CandSGID = *I;
808 SchedGroup *Match = llvm::find_if(SyncPipeline, [CandSGID](SchedGroup &SG) {
809 return SG.getSGID() == CandSGID;
810 });
811 assert(Match);
812
813 LLVM_DEBUG(dbgs() << "Trying SGID # " << CandSGID << " with Mask "
814 << (int)Match->getMask() << "\n");
815
816 if (Match->isFull()) {
817 LLVM_DEBUG(dbgs() << "SGID # " << CandSGID << " is full\n");
818 continue;
819 }
820 if (!Match->allowedByRules(SU: CurrSU.first, SyncPipe&: SyncPipeline)) {
821 LLVM_DEBUG(dbgs() << "SGID # " << CandSGID << " has conflicting rule\n");
822 continue;
823 }
824
825 std::list<std::pair<SUnit *, SUnit *>> TempEdges;
826 int TempCost = Builder.build(SGID: CandSGID, NewEdges&: TempEdges);
827 LLVM_DEBUG(dbgs() << "Cost of Group " << TempCost << "\n");
828
829 if (!Best || TempCost < Best->Cost) {
830 Best = {Match, TempEdges, TempCost};
831 if (Best->Cost == 0)
832 break;
833 }
834 }
835
836 if (Best) {
837 SchedGroup *SG = Best->SG;
838 std::list<std::pair<SUnit *, SUnit *>> &Edges = Best->Edges;
839
840 SG->add(SU&: *CurrSU.first);
841 if (AddedEdges.empty())
842 AddedEdges = Edges;
843 else
844 AddedEdges.splice(position: std::prev(x: AddedEdges.cend()), x&: Edges);
845
846 for (const std::pair<SUnit *, SUnit *> &E : Edges) {
847 if (!SG->tryAddEdge(A: E.first, B: E.second))
848 llvm_unreachable("Edges known to be insertable.");
849 }
850
851 LLVM_DEBUG(dbgs() << "Best Group has ID: " << SG->getSGID() << " and Mask"
852 << (int)SG->getMask() << "\n");
853 BestCost += Best->Cost;
854 } else
855 BestCost += MissPenalty;
856}
857
858bool PipelineSolver::solveGreedy() {
859 BestCost = 0;
860 std::list<std::pair<SUnit *, SUnit *>> AddedEdges;
861
862 while (static_cast<size_t>(CurrSyncGroupIdx) < PipelineInstrs.size()) {
863 SUToCandSGsPair CurrSU = PipelineInstrs[CurrSyncGroupIdx][CurrConflInstNo];
864 IsBottomUp
865 ? greedyFind(AddedEdges, I: CurrSU.second.rbegin(), E: CurrSU.second.rend())
866 : greedyFind(AddedEdges, I: CurrSU.second.begin(), E: CurrSU.second.end());
867 advancePosition();
868 }
869 BestPipeline = CurrPipeline;
870 removeEdges(EdgesToRemove: AddedEdges);
871 return false;
872}
873
874unsigned PipelineSolver::computeProblemSize() {
875 unsigned ProblemSize = 0;
876 for (auto &PipeConflicts : PipelineInstrs) {
877 ProblemSize += static_cast<unsigned>(PipeConflicts.size());
878 }
879
880 return ProblemSize;
881}
882
883void PipelineSolver::solve() {
884 if (!NeedsSolver)
885 return;
886
887 unsigned ProblemSize = computeProblemSize();
888 assert(ProblemSize > 0);
889
890 bool BelowCutoff = (CLOpts.igrouplp_exact_solver_cutoff > 0) &&
891 ProblemSize <= CLOpts.igrouplp_exact_solver_cutoff;
892 MissPenalty = (ProblemSize / 2) + 1;
893
894 LLVM_DEBUG(DAG->dump());
895 if (CLOpts.igrouplp_exact_solver || BelowCutoff) {
896 LLVM_DEBUG(dbgs() << "Starting Greedy pipeline solver\n");
897 solveGreedy();
898 reset();
899 LLVM_DEBUG(dbgs() << "Greedy produced best cost of " << BestCost << "\n");
900 if (BestCost > 0) {
901 LLVM_DEBUG(dbgs() << "Starting EXACT pipeline solver\n");
902 solveExact();
903 LLVM_DEBUG(dbgs() << "Exact produced best cost of " << BestCost << "\n");
904 }
905 } else { // Use the Greedy Algorithm by default
906 LLVM_DEBUG(dbgs() << "Starting GREEDY pipeline solver\n");
907 solveGreedy();
908 LLVM_DEBUG(dbgs() << "Greedy produced best cost of " << BestCost << "\n");
909 }
910
911 makePipeline();
912 LLVM_DEBUG(dbgs() << "After applying mutation\n");
913 LLVM_DEBUG(DAG->dump());
914}
915
916// Implement a IGLP scheduling strategy.
917class IGLPStrategy {
918protected:
919 ScheduleDAGInstrs *DAG;
920
921 const SIInstrInfo *TII;
922
923 // The IGLP_OPT instruction that selected this strategy. Operand 0 is the
924 // strategy ID. Strategies that need results of the pre-RA DAG analysis in
925 // later scheduling phases store them as additional immediate operands (see
926 // setIGLPOptData), so they stay attached to this IGLP_OPT and are serialized
927 // with the MIR.
928 MachineInstr *IGLPOptMI;
929
930 /// Returns true if IGLPOptMI holds \p NumValues analysis data values.
931 bool hasIGLPOptData(unsigned NumValues) const {
932 return IGLPOptMI->getNumOperands() == NumValues + 1 &&
933 all_of(Range: drop_begin(RangeOrContainer: IGLPOptMI->operands()),
934 P: [](const MachineOperand &MO) { return MO.isImm(); });
935 }
936
937 /// Replace the analysis data stored on IGLPOptMI with \p Data.
938 void setIGLPOptData(ArrayRef<int64_t> Data) {
939 // Overwrite the values in place if an earlier scheduling stage already
940 // stored the same number of values.
941 if (hasIGLPOptData(NumValues: Data.size())) {
942 for (auto [MO, V] : zip_equal(t: drop_begin(RangeOrContainer: IGLPOptMI->operands()), u&: Data))
943 MO.setImm(V);
944 return;
945 }
946 while (IGLPOptMI->getNumOperands() > 1)
947 IGLPOptMI->removeOperand(OpNo: IGLPOptMI->getNumOperands() - 1);
948 for (int64_t V : Data)
949 IGLPOptMI->addOperand(Op: MachineOperand::CreateImm(Val: V));
950 }
951
952 /// Returns the \p NumValues analysis data values stored on IGLPOptMI, or
953 /// std::nullopt if there are none.
954 template <unsigned NumValues>
955 std::optional<std::array<int64_t, NumValues>> getIGLPOptData() const {
956 if (!hasIGLPOptData(NumValues))
957 return std::nullopt;
958 std::array<int64_t, NumValues> Data;
959 for (auto [V, MO] : zip_equal(Data, drop_begin(RangeOrContainer: IGLPOptMI->operands())))
960 V = MO.getImm();
961 return Data;
962 }
963
964public:
965 /// Add SchedGroups to \p SyncedSchedGroups to implement this Strategy.
966 virtual bool applyIGLPStrategy(
967 DenseMap<int, SUnitsToCandidateSGsMap> &SyncedInstrs,
968 DenseMap<int, SmallVector<SchedGroup, 4>> &SyncedSchedGroups,
969 AMDGPU::SchedulingPhase Phase) = 0;
970
971 // Returns true if this strategy should be applied to a ScheduleDAG.
972 virtual bool shouldApplyStrategy(ScheduleDAGInstrs *DAG,
973 AMDGPU::SchedulingPhase Phase) = 0;
974
975 bool IsBottomUp = true;
976
977 IGLPStrategy(ScheduleDAGInstrs *DAG, const SIInstrInfo *TII,
978 MachineInstr *IGLPOptMI)
979 : DAG(DAG), TII(TII), IGLPOptMI(IGLPOptMI) {}
980
981 virtual ~IGLPStrategy() = default;
982};
983
984class MFMASmallGemmOpt final : public IGLPStrategy {
985private:
986public:
987 bool applyIGLPStrategy(
988 DenseMap<int, SUnitsToCandidateSGsMap> &SyncedInstrs,
989 DenseMap<int, SmallVector<SchedGroup, 4>> &SyncedSchedGroups,
990 AMDGPU::SchedulingPhase Phase) override;
991
992 bool shouldApplyStrategy(ScheduleDAGInstrs *DAG,
993 AMDGPU::SchedulingPhase Phase) override {
994 return true;
995 }
996
997 MFMASmallGemmOpt(ScheduleDAGInstrs *DAG, const SIInstrInfo *TII,
998 MachineInstr *IGLPOptMI)
999 : IGLPStrategy(DAG, TII, IGLPOptMI) {
1000 IsBottomUp = true;
1001 }
1002};
1003
1004bool MFMASmallGemmOpt::applyIGLPStrategy(
1005 DenseMap<int, SUnitsToCandidateSGsMap> &SyncedInstrs,
1006 DenseMap<int, SmallVector<SchedGroup, 4>> &SyncedSchedGroups,
1007 AMDGPU::SchedulingPhase Phase) {
1008 // Count the number of MFMA instructions.
1009 unsigned MFMACount = 0;
1010 for (const MachineInstr &I : *DAG)
1011 if (TII->isMFMAorWMMA(MI: I))
1012 ++MFMACount;
1013
1014 const unsigned PipelineSyncID = 0;
1015 SchedGroup *SG = nullptr;
1016 for (unsigned I = 0; I < MFMACount * 3; ++I) {
1017 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1018 Args: SchedGroupMask::DS, Args: 2, Args: PipelineSyncID, Args&: DAG, Args&: TII);
1019 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
1020
1021 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1022 Args: SchedGroupMask::MFMA, Args: 1, Args: PipelineSyncID, Args&: DAG, Args&: TII);
1023 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
1024 }
1025
1026 return true;
1027}
1028
1029class MFMAExpInterleaveOpt final : public IGLPStrategy {
1030private:
1031 // The count of TRANS SUs involved in the interleaved pipeline
1032 unsigned TransPipeCount = 0;
1033 // The count of MFMA SUs involved in the interleaved pipeline
1034 unsigned MFMAPipeCount = 0;
1035 // The count of Add SUs involved in the interleaved pipeline
1036 unsigned AddPipeCount = 0;
1037 // The number of transitive MFMA successors for each TRANS SU
1038 unsigned MFMAEnablement = 0;
1039 // The number of transitive TRANS predecessors for each MFMA SU
1040 unsigned ExpRequirement = 0;
1041 // The count of independent "chains" of MFMA instructions in the pipeline
1042 unsigned MFMAChains = 0;
1043 // Whether or not the pipeline has V_CVT instructions
1044 bool HasCvt = false;
1045 // Whether or not there are instructions between the TRANS instruction and
1046 // V_CVT
1047 bool HasChainBetweenCvt = false;
1048 // The first occuring DS_READ which feeds an MFMA chain
1049 std::optional<unsigned> FirstPipeDSR;
1050 // The MFMAPipe SUs with no MFMA predecessors
1051 SmallVector<SUnit *, 4> MFMAChainSeeds;
1052 // Compute the analysis data for the pipeline, returning whether or not the
1053 // DAG is well formatted for the mutation
1054 bool analyzeDAG(const SIInstrInfo *TII);
1055
1056 // The number of analysis data values stored on the IGLP_OPT by
1057 // storeAnalysisData.
1058 static constexpr unsigned NumAnalysisValues = 8;
1059 // Store the analysis data on the IGLP_OPT for PostRA scheduling, where the
1060 // DAG dependencies differ and the analysis cannot be repeated.
1061 void storeAnalysisData() {
1062 setIGLPOptData({TransPipeCount, MFMAPipeCount, AddPipeCount, MFMAEnablement,
1063 ExpRequirement, MFMAChains, HasCvt, HasChainBetweenCvt});
1064 }
1065 // Load the analysis data stored by storeAnalysisData. Returns false if there
1066 // is none, i.e. the pre-RA analysis did not run or failed.
1067 bool loadAnalysisData() {
1068 std::optional<std::array<int64_t, NumAnalysisValues>> Data =
1069 getIGLPOptData<NumAnalysisValues>();
1070 if (!Data)
1071 return false;
1072 TransPipeCount = (*Data)[0];
1073 MFMAPipeCount = (*Data)[1];
1074 AddPipeCount = (*Data)[2];
1075 MFMAEnablement = (*Data)[3];
1076 ExpRequirement = (*Data)[4];
1077 MFMAChains = (*Data)[5];
1078 HasCvt = (*Data)[6];
1079 HasChainBetweenCvt = (*Data)[7];
1080 assert(TransPipeCount > 0 && MFMAPipeCount > 0 && MFMAChains > 0 &&
1081 "guaranteed by a successful analyzeDAG");
1082 return true;
1083 }
1084
1085 /// Whether or not the instruction is a transitive predecessor of an MFMA
1086 /// instruction
1087 class IsPipeExp final : public InstructionRule {
1088 public:
1089 bool apply(const SUnit *SU, const ArrayRef<SUnit *> Collection,
1090 SmallVectorImpl<SchedGroup> &SyncPipe) override {
1091
1092 auto *DAG = SyncPipe[0].DAG;
1093
1094 if (Cache->empty()) {
1095 auto I = DAG->SUnits.rbegin();
1096 auto E = DAG->SUnits.rend();
1097 for (; I != E; I++) {
1098 if (TII->isMFMAorWMMA(MI: *I->getInstr()))
1099 Cache->push_back(Elt: &*I);
1100 }
1101 if (Cache->empty())
1102 return false;
1103 }
1104
1105 auto Reaches = any_of(Range&: *Cache, P: [&SU, &DAG](SUnit *TargetSU) {
1106 return DAG->IsReachable(SU: TargetSU, TargetSU: const_cast<SUnit *>(SU));
1107 });
1108
1109 return Reaches;
1110 }
1111 IsPipeExp(const SIInstrInfo *TII, unsigned SGID, bool NeedsCache = false)
1112 : InstructionRule(TII, SGID, NeedsCache) {}
1113 };
1114
1115 /// Whether or not the instruction is a transitive predecessor of the
1116 /// \p Number th MFMA of the MFMAs occuring after a TRANS instruction
1117 class EnablesNthMFMA final : public InstructionRule {
1118 private:
1119 unsigned Number = 1;
1120
1121 public:
1122 bool apply(const SUnit *SU, const ArrayRef<SUnit *> Collection,
1123 SmallVectorImpl<SchedGroup> &SyncPipe) override {
1124 bool FoundTrans = false;
1125 unsigned Counter = 1;
1126 auto *DAG = SyncPipe[0].DAG;
1127
1128 if (Cache->empty()) {
1129 auto I = DAG->SUnits.begin();
1130 auto E = DAG->SUnits.end();
1131 for (; I != E; I++) {
1132 if (FoundTrans && TII->isMFMAorWMMA(MI: *I->getInstr())) {
1133 if (Counter == Number) {
1134 Cache->push_back(Elt: &*I);
1135 break;
1136 }
1137 ++Counter;
1138 }
1139 if (!FoundTrans && TII->isTRANS(Opcode: I->getInstr()->getOpcode()))
1140 FoundTrans = true;
1141 }
1142 if (Cache->empty())
1143 return false;
1144 }
1145
1146 return DAG->IsReachable(SU: (*Cache)[0], TargetSU: const_cast<SUnit *>(SU));
1147 }
1148
1149 EnablesNthMFMA(unsigned Number, const SIInstrInfo *TII, unsigned SGID,
1150 bool NeedsCache = false)
1151 : InstructionRule(TII, SGID, NeedsCache), Number(Number) {}
1152 };
1153
1154 /// Whether or not the instruction enables the exact MFMA that is the \p
1155 /// Number th MFMA in the chain starting with \p ChainSeed
1156 class EnablesNthMFMAInChain final : public InstructionRule {
1157 private:
1158 unsigned Number = 1;
1159 SUnit *ChainSeed;
1160
1161 public:
1162 bool apply(const SUnit *SU, const ArrayRef<SUnit *> Collection,
1163 SmallVectorImpl<SchedGroup> &SyncPipe) override {
1164 auto *DAG = SyncPipe[0].DAG;
1165
1166 if (!SU || !TII->isMFMAorWMMA(MI: *ChainSeed->getInstr()))
1167 return false;
1168
1169 if (Cache->empty()) {
1170 auto *TempSU = ChainSeed;
1171 auto Depth = Number;
1172 while (Depth > 0) {
1173 --Depth;
1174 bool Found = false;
1175 for (auto &Succ : TempSU->Succs) {
1176 if (TII->isMFMAorWMMA(MI: *Succ.getSUnit()->getInstr())) {
1177 TempSU = Succ.getSUnit();
1178 Found = true;
1179 break;
1180 }
1181 }
1182 if (!Found)
1183 return false;
1184 }
1185
1186 Cache->push_back(Elt: TempSU);
1187 }
1188 // If we failed to find the instruction to be placed into the cache, we
1189 // would have already exited.
1190 assert(!Cache->empty());
1191
1192 return DAG->IsReachable(SU: (*Cache)[0], TargetSU: const_cast<SUnit *>(SU));
1193 }
1194
1195 EnablesNthMFMAInChain(unsigned Number, SUnit *ChainSeed,
1196 const SIInstrInfo *TII, unsigned SGID,
1197 bool NeedsCache = false)
1198 : InstructionRule(TII, SGID, NeedsCache), Number(Number),
1199 ChainSeed(ChainSeed) {}
1200 };
1201
1202 /// Whether or not the instruction has less than \p Size immediate successors.
1203 /// If \p HasIntermediary is true, this tests also whether all successors of
1204 /// the SUnit have less than \p Size successors.
1205 class LessThanNSuccs final : public InstructionRule {
1206 private:
1207 unsigned Size = 1;
1208 bool HasIntermediary = false;
1209
1210 public:
1211 bool apply(const SUnit *SU, const ArrayRef<SUnit *> Collection,
1212 SmallVectorImpl<SchedGroup> &SyncPipe) override {
1213 if (!SyncPipe.size())
1214 return false;
1215
1216 size_t SuccSize = llvm::count_if(Range: SU->Succs, P: [](const SDep &Succ) {
1217 return Succ.getKind() == SDep::Data;
1218 });
1219 if (SuccSize >= Size)
1220 return false;
1221
1222 if (HasIntermediary) {
1223 for (auto Succ : SU->Succs) {
1224 size_t SuccSize =
1225 llvm::count_if(Range&: Succ.getSUnit()->Succs, P: [](const SDep &SuccSucc) {
1226 return SuccSucc.getKind() == SDep::Data;
1227 });
1228 if (SuccSize >= Size)
1229 return false;
1230 }
1231 }
1232
1233 return true;
1234 }
1235 LessThanNSuccs(unsigned Size, const SIInstrInfo *TII, unsigned SGID,
1236 bool HasIntermediary = false, bool NeedsCache = false)
1237 : InstructionRule(TII, SGID, NeedsCache), Size(Size),
1238 HasIntermediary(HasIntermediary) {}
1239 };
1240
1241 /// Whether or not the instruction has greater than or equal to \p Size
1242 /// immediate successors. If \p HasIntermediary is true, this tests also
1243 /// whether all successors of the SUnit have greater than or equal to \p Size
1244 /// successors.
1245 class GreaterThanOrEqualToNSuccs final : public InstructionRule {
1246 private:
1247 unsigned Size = 1;
1248 bool HasIntermediary = false;
1249
1250 public:
1251 bool apply(const SUnit *SU, const ArrayRef<SUnit *> Collection,
1252 SmallVectorImpl<SchedGroup> &SyncPipe) override {
1253 if (!SyncPipe.size())
1254 return false;
1255
1256 size_t SuccSize = llvm::count_if(Range: SU->Succs, P: [](const SDep &Succ) {
1257 return Succ.getKind() == SDep::Data;
1258 });
1259 if (SuccSize >= Size)
1260 return true;
1261
1262 if (HasIntermediary) {
1263 for (auto Succ : SU->Succs) {
1264 size_t SuccSize =
1265 llvm::count_if(Range&: Succ.getSUnit()->Succs, P: [](const SDep &SuccSucc) {
1266 return SuccSucc.getKind() == SDep::Data;
1267 });
1268 if (SuccSize >= Size)
1269 return true;
1270 }
1271 }
1272
1273 return false;
1274 }
1275 GreaterThanOrEqualToNSuccs(unsigned Size, const SIInstrInfo *TII,
1276 unsigned SGID, bool HasIntermediary = false,
1277 bool NeedsCache = false)
1278 : InstructionRule(TII, SGID, NeedsCache), Size(Size),
1279 HasIntermediary(HasIntermediary) {}
1280 };
1281
1282 // Whether or not the instruction is a relevant V_CVT instruction.
1283 class IsCvt final : public InstructionRule {
1284 public:
1285 bool apply(const SUnit *SU, const ArrayRef<SUnit *> Collection,
1286 SmallVectorImpl<SchedGroup> &SyncPipe) override {
1287 auto Opc = SU->getInstr()->getOpcode();
1288 return Opc == AMDGPU::V_CVT_F16_F32_e32 ||
1289 Opc == AMDGPU::V_CVT_I32_F32_e32;
1290 }
1291 IsCvt(const SIInstrInfo *TII, unsigned SGID, bool NeedsCache = false)
1292 : InstructionRule(TII, SGID, NeedsCache) {}
1293 };
1294
1295 // Whether or not the instruction is FMA_F32.
1296 class IsFMA final : public InstructionRule {
1297 public:
1298 bool apply(const SUnit *SU, const ArrayRef<SUnit *> Collection,
1299 SmallVectorImpl<SchedGroup> &SyncPipe) override {
1300 return SU->getInstr()->getOpcode() == AMDGPU::V_FMA_F32_e64 ||
1301 SU->getInstr()->getOpcode() == AMDGPU::V_PK_FMA_F32;
1302 }
1303 IsFMA(const SIInstrInfo *TII, unsigned SGID, bool NeedsCache = false)
1304 : InstructionRule(TII, SGID, NeedsCache) {}
1305 };
1306
1307 // Whether or not the instruction is a V_ADD_F32 instruction.
1308 class IsPipeAdd final : public InstructionRule {
1309 public:
1310 bool apply(const SUnit *SU, const ArrayRef<SUnit *> Collection,
1311 SmallVectorImpl<SchedGroup> &SyncPipe) override {
1312 return SU->getInstr()->getOpcode() == AMDGPU::V_ADD_F32_e32;
1313 }
1314 IsPipeAdd(const SIInstrInfo *TII, unsigned SGID, bool NeedsCache = false)
1315 : InstructionRule(TII, SGID, NeedsCache) {}
1316 };
1317
1318 /// Whether or not the instruction is an immediate RAW successor
1319 /// of the SchedGroup \p Distance steps before.
1320 class IsSuccOfPrevNthGroup final : public InstructionRule {
1321 private:
1322 unsigned Distance = 1;
1323
1324 public:
1325 bool apply(const SUnit *SU, const ArrayRef<SUnit *> Collection,
1326 SmallVectorImpl<SchedGroup> &SyncPipe) override {
1327 SchedGroup *OtherGroup = nullptr;
1328 if (!SyncPipe.size())
1329 return false;
1330
1331 for (auto &PipeSG : SyncPipe) {
1332 if ((unsigned)PipeSG.getSGID() == SGID - Distance)
1333 OtherGroup = &PipeSG;
1334 }
1335
1336 if (!OtherGroup)
1337 return false;
1338 if (!OtherGroup->Collection.size())
1339 return true;
1340
1341 for (auto &OtherEle : OtherGroup->Collection) {
1342 for (auto &Succ : OtherEle->Succs) {
1343 if (Succ.getSUnit() == SU && Succ.getKind() == SDep::Data)
1344 return true;
1345 }
1346 }
1347
1348 return false;
1349 }
1350 IsSuccOfPrevNthGroup(unsigned Distance, const SIInstrInfo *TII,
1351 unsigned SGID, bool NeedsCache = false)
1352 : InstructionRule(TII, SGID, NeedsCache), Distance(Distance) {}
1353 };
1354
1355 /// Whether or not the instruction is a transitive successor of any
1356 /// instruction the the SchedGroup \p Distance steps before.
1357 class IsReachableFromPrevNthGroup final : public InstructionRule {
1358 private:
1359 unsigned Distance = 1;
1360
1361 public:
1362 bool apply(const SUnit *SU, const ArrayRef<SUnit *> Collection,
1363 SmallVectorImpl<SchedGroup> &SyncPipe) override {
1364 SchedGroup *OtherGroup = nullptr;
1365 if (!SyncPipe.size())
1366 return false;
1367
1368 for (auto &PipeSG : SyncPipe) {
1369 if ((unsigned)PipeSG.getSGID() == SGID - Distance)
1370 OtherGroup = &PipeSG;
1371 }
1372
1373 if (!OtherGroup)
1374 return false;
1375 if (!OtherGroup->Collection.size())
1376 return true;
1377
1378 auto *DAG = SyncPipe[0].DAG;
1379
1380 for (auto &OtherEle : OtherGroup->Collection)
1381 if (DAG->IsReachable(SU: const_cast<SUnit *>(SU), TargetSU: OtherEle))
1382 return true;
1383
1384 return false;
1385 }
1386 IsReachableFromPrevNthGroup(unsigned Distance, const SIInstrInfo *TII,
1387 unsigned SGID, bool NeedsCache = false)
1388 : InstructionRule(TII, SGID, NeedsCache), Distance(Distance) {}
1389 };
1390
1391 /// Whether or not the instruction occurs after the SU with NodeNUm \p Number
1392 class OccursAtOrAfterNode final : public InstructionRule {
1393 private:
1394 unsigned Number = 1;
1395
1396 public:
1397 bool apply(const SUnit *SU, const ArrayRef<SUnit *> Collection,
1398 SmallVectorImpl<SchedGroup> &SyncPipe) override {
1399
1400 return SU->NodeNum >= Number;
1401 }
1402 OccursAtOrAfterNode(unsigned Number, const SIInstrInfo *TII, unsigned SGID,
1403 bool NeedsCache = false)
1404 : InstructionRule(TII, SGID, NeedsCache), Number(Number) {}
1405 };
1406
1407 /// Whether or not the SU is exactly the \p Number th MFMA in the chain
1408 /// starting with \p ChainSeed
1409 class IsExactMFMA final : public InstructionRule {
1410 private:
1411 unsigned Number = 1;
1412 SUnit *ChainSeed;
1413
1414 public:
1415 bool apply(const SUnit *SU, const ArrayRef<SUnit *> Collection,
1416 SmallVectorImpl<SchedGroup> &SyncPipe) override {
1417 if (!SU || !TII->isMFMAorWMMA(MI: *ChainSeed->getInstr()))
1418 return false;
1419
1420 if (Cache->empty()) {
1421 auto *TempSU = ChainSeed;
1422 auto Depth = Number;
1423 while (Depth > 0) {
1424 --Depth;
1425 bool Found = false;
1426 for (auto &Succ : TempSU->Succs) {
1427 if (TII->isMFMAorWMMA(MI: *Succ.getSUnit()->getInstr())) {
1428 TempSU = Succ.getSUnit();
1429 Found = true;
1430 break;
1431 }
1432 }
1433 if (!Found) {
1434 return false;
1435 }
1436 }
1437 Cache->push_back(Elt: TempSU);
1438 }
1439 // If we failed to find the instruction to be placed into the cache, we
1440 // would have already exited.
1441 assert(!Cache->empty());
1442
1443 return (*Cache)[0] == SU;
1444 }
1445
1446 IsExactMFMA(unsigned Number, SUnit *ChainSeed, const SIInstrInfo *TII,
1447 unsigned SGID, bool NeedsCache = false)
1448 : InstructionRule(TII, SGID, NeedsCache), Number(Number),
1449 ChainSeed(ChainSeed) {}
1450 };
1451
1452 // Whether the instruction occurs after the first TRANS instruction. This
1453 // implies the instruction can not be a predecessor of the first TRANS
1454 // instruction.
1455 class OccursAfterExp final : public InstructionRule {
1456 public:
1457 bool apply(const SUnit *SU, const ArrayRef<SUnit *> Collection,
1458 SmallVectorImpl<SchedGroup> &SyncPipe) override {
1459
1460 auto *DAG = SyncPipe[0].DAG;
1461 if (Cache->empty()) {
1462 for (auto &SU : DAG->SUnits)
1463 if (TII->isTRANS(Opcode: SU.getInstr()->getOpcode())) {
1464 Cache->push_back(Elt: &SU);
1465 break;
1466 }
1467 if (Cache->empty())
1468 return false;
1469 }
1470
1471 return SU->NodeNum > (*Cache)[0]->NodeNum;
1472 }
1473
1474 OccursAfterExp(const SIInstrInfo *TII, unsigned SGID,
1475 bool NeedsCache = false)
1476 : InstructionRule(TII, SGID, NeedsCache) {}
1477 };
1478
1479public:
1480 bool applyIGLPStrategy(
1481 DenseMap<int, SUnitsToCandidateSGsMap> &SyncedInstrs,
1482 DenseMap<int, SmallVector<SchedGroup, 4>> &SyncedSchedGroups,
1483 AMDGPU::SchedulingPhase Phase) override;
1484
1485 bool shouldApplyStrategy(ScheduleDAGInstrs *DAG,
1486 AMDGPU::SchedulingPhase Phase) override;
1487
1488 MFMAExpInterleaveOpt(ScheduleDAGInstrs *DAG, const SIInstrInfo *TII,
1489 MachineInstr *IGLPOptMI)
1490 : IGLPStrategy(DAG, TII, IGLPOptMI) {
1491 IsBottomUp = false;
1492 }
1493};
1494
1495bool MFMAExpInterleaveOpt::analyzeDAG(const SIInstrInfo *TII) {
1496 SmallVector<SUnit *, 10> ExpPipeCands;
1497 SmallVector<SUnit *, 10> MFMAPipeCands;
1498 SmallVector<SUnit *, 10> MFMAPipeSUs;
1499 SmallVector<SUnit *, 10> PackSUs;
1500 SmallVector<SUnit *, 10> CvtSUs;
1501
1502 auto isBitPack = [](unsigned Opc) {
1503 return Opc == AMDGPU::V_PACK_B32_F16_e64 || Opc == AMDGPU::V_PERM_B32_e64;
1504 };
1505
1506 auto isCvt = [](unsigned Opc) {
1507 return Opc == AMDGPU::V_CVT_F16_F32_e32 || Opc == AMDGPU::V_CVT_I32_F32_e32;
1508 };
1509
1510 auto isAdd = [](unsigned Opc) { return Opc == AMDGPU::V_ADD_F32_e32; };
1511
1512 for (SUnit &SU : DAG->SUnits) {
1513 auto Opc = SU.getInstr()->getOpcode();
1514 if (TII->isTRANS(Opcode: Opc)) {
1515 // Avoid counting a potential bonus V_EXP which all the MFMA depend on
1516 if (SU.Succs.size() >= 7)
1517 continue;
1518 for (auto &Succ : SU.Succs) {
1519 if (Succ.getSUnit()->Succs.size() >= 7)
1520 continue;
1521 }
1522 ExpPipeCands.push_back(Elt: &SU);
1523 }
1524
1525 if (TII->isMFMAorWMMA(MI: *SU.getInstr()))
1526 MFMAPipeCands.push_back(Elt: &SU);
1527
1528 if (isBitPack(Opc))
1529 PackSUs.push_back(Elt: &SU);
1530
1531 if (isCvt(Opc))
1532 CvtSUs.push_back(Elt: &SU);
1533
1534 if (isAdd(Opc))
1535 ++AddPipeCount;
1536 }
1537
1538 if (!(PackSUs.size() && MFMAPipeCands.size() && ExpPipeCands.size()))
1539 return false;
1540
1541 std::optional<SUnit *> TempMFMA;
1542 std::optional<SUnit *> TempExp;
1543 // Count the number of EXPs that reach an MFMA
1544 for (auto &PredSU : ExpPipeCands) {
1545 for (auto &SuccSU : MFMAPipeCands) {
1546 if (DAG->IsReachable(SU: SuccSU, TargetSU: PredSU)) {
1547 if (!TempExp) {
1548 TempExp = PredSU;
1549 TempMFMA = SuccSU;
1550 }
1551 MFMAPipeSUs.push_back(Elt: SuccSU);
1552 ++TransPipeCount;
1553 break;
1554 }
1555 }
1556 }
1557
1558 if (!(TempExp && TempMFMA))
1559 return false;
1560
1561 HasChainBetweenCvt = none_of(Range&: (*TempExp)->Succs, P: [&isCvt](SDep &Succ) {
1562 return isCvt(Succ.getSUnit()->getInstr()->getOpcode());
1563 });
1564
1565 // Count the number of MFMAs that are reached by an EXP
1566 for (auto &SuccSU : MFMAPipeCands) {
1567 if (MFMAPipeSUs.size() &&
1568 any_of(Range&: MFMAPipeSUs, P: [&SuccSU](SUnit *PotentialMatch) {
1569 return PotentialMatch->NodeNum == SuccSU->NodeNum;
1570 }))
1571 continue;
1572
1573 for (auto &PredSU : ExpPipeCands) {
1574 if (DAG->IsReachable(SU: SuccSU, TargetSU: PredSU)) {
1575 MFMAPipeSUs.push_back(Elt: SuccSU);
1576 break;
1577 }
1578 }
1579 }
1580
1581 MFMAPipeCount = static_cast<unsigned>(MFMAPipeSUs.size());
1582
1583 assert(TempExp && TempMFMA);
1584 assert(MFMAPipeCount > 0);
1585
1586 std::optional<SUnit *> TempCvt;
1587 for (auto &SuccSU : CvtSUs) {
1588 if (DAG->IsReachable(SU: SuccSU, TargetSU: *TempExp)) {
1589 TempCvt = SuccSU;
1590 break;
1591 }
1592 }
1593
1594 if (TempCvt.has_value()) {
1595 for (auto &SuccSU : MFMAPipeSUs) {
1596 if (DAG->IsReachable(SU: SuccSU, TargetSU: *TempCvt)) {
1597 HasCvt = true;
1598 break;
1599 }
1600 }
1601 }
1602
1603 for (auto &MFMAPipeSU : MFMAPipeSUs) {
1604 if (is_contained(Range&: MFMAChainSeeds, Element: MFMAPipeSU))
1605 continue;
1606 if (none_of(Range&: MFMAPipeSU->Preds, P: [&TII](SDep &Succ) {
1607 return TII->isMFMAorWMMA(MI: *Succ.getSUnit()->getInstr());
1608 })) {
1609 MFMAChainSeeds.push_back(Elt: MFMAPipeSU);
1610 ++MFMAChains;
1611 }
1612 }
1613
1614 if (!MFMAChains)
1615 return false;
1616
1617 for (auto Pred : MFMAChainSeeds[0]->Preds) {
1618 if (TII->isDS(Opcode: Pred.getSUnit()->getInstr()->getOpcode()) &&
1619 Pred.getSUnit()->getInstr()->mayLoad())
1620 FirstPipeDSR = Pred.getSUnit()->NodeNum;
1621 }
1622
1623 // The number of bit pack operations that depend on a single V_EXP
1624 unsigned PackSuccCount = static_cast<unsigned>(
1625 llvm::count_if(Range&: PackSUs, P: [this, &TempExp](SUnit *VPack) {
1626 return DAG->IsReachable(SU: VPack, TargetSU: *TempExp);
1627 }));
1628
1629 // The number of bit pack operations an MFMA depends on
1630 unsigned PackPredCount = static_cast<unsigned>(
1631 llvm::count_if(Range&: (*TempMFMA)->Preds, P: [&isBitPack](SDep &Pred) {
1632 auto Opc = Pred.getSUnit()->getInstr()->getOpcode();
1633 return isBitPack(Opc);
1634 }));
1635
1636 auto *PackPred = llvm::find_if(Range&: (*TempMFMA)->Preds, P: [&isBitPack](SDep &Pred) {
1637 auto Opc = Pred.getSUnit()->getInstr()->getOpcode();
1638 return isBitPack(Opc);
1639 });
1640
1641 if (PackPred == (*TempMFMA)->Preds.end())
1642 return false;
1643
1644 // How many MFMAs depend on a single bit pack operation
1645 MFMAEnablement = static_cast<unsigned>(
1646 llvm::count_if(Range&: PackPred->getSUnit()->Succs, P: [&TII](SDep &Succ) {
1647 return TII->isMFMAorWMMA(MI: *Succ.getSUnit()->getInstr());
1648 }));
1649
1650 // The number of MFMAs that depend on a single V_EXP
1651 MFMAEnablement *= PackSuccCount;
1652
1653 // The number of V_EXPs required to resolve all dependencies for an MFMA
1654 ExpRequirement = static_cast<unsigned>(
1655 llvm::count_if(Range&: ExpPipeCands, P: [this, &PackPred](SUnit *ExpBase) {
1656 return DAG->IsReachable(SU: PackPred->getSUnit(), TargetSU: ExpBase);
1657 }));
1658
1659 ExpRequirement *= PackPredCount;
1660 return true;
1661}
1662
1663bool MFMAExpInterleaveOpt::shouldApplyStrategy(ScheduleDAGInstrs *DAG,
1664 AMDGPU::SchedulingPhase Phase) {
1665 const GCNSubtarget &ST = DAG->MF.getSubtarget<GCNSubtarget>();
1666 const SIInstrInfo *TII = ST.getInstrInfo();
1667
1668 if (Phase == AMDGPU::SchedulingPhase::PostRA)
1669 return loadAnalysisData();
1670
1671 if (!analyzeDAG(TII)) {
1672 // Drop analysis data stored by an earlier pre-RA stage.
1673 setIGLPOptData({});
1674 return false;
1675 }
1676
1677 storeAnalysisData();
1678 return true;
1679}
1680
1681bool MFMAExpInterleaveOpt::applyIGLPStrategy(
1682 DenseMap<int, SUnitsToCandidateSGsMap> &SyncedInstrs,
1683 DenseMap<int, SmallVector<SchedGroup, 4>> &SyncedSchedGroups,
1684 AMDGPU::SchedulingPhase Phase) {
1685
1686 bool IsSmallKernelType =
1687 MFMAEnablement == 2 && ExpRequirement == 4 && TransPipeCount == 32;
1688 bool IsLargeKernelType =
1689 MFMAEnablement == 4 && ExpRequirement == 4 && TransPipeCount == 64;
1690
1691 if (!(IsSmallKernelType || IsLargeKernelType))
1692 return false;
1693
1694 const GCNSubtarget &ST = DAG->MF.getSubtarget<GCNSubtarget>();
1695 const SIInstrInfo *TII = ST.getInstrInfo();
1696
1697 unsigned PipelineSyncID = 0;
1698 SchedGroup *SG = nullptr;
1699
1700 unsigned MFMAChain = 0;
1701 unsigned PositionInChain = 0;
1702 unsigned CurrMFMAForTransPosition = 0;
1703
1704 auto incrementTransPosition = [&MFMAChain, &PositionInChain,
1705 &CurrMFMAForTransPosition, this]() {
1706 CurrMFMAForTransPosition += MFMAEnablement;
1707 PositionInChain = (CurrMFMAForTransPosition / MFMAChains);
1708 MFMAChain = CurrMFMAForTransPosition % MFMAChains;
1709 };
1710
1711 auto getNextTransPositionInChain = [&CurrMFMAForTransPosition, this]() {
1712 auto TempMFMAForTrans = CurrMFMAForTransPosition + MFMAEnablement;
1713 return (TempMFMAForTrans / MFMAChains);
1714 };
1715
1716 auto getNextTransMFMAChain = [&CurrMFMAForTransPosition, this]() {
1717 auto TempMFMAForTrans = CurrMFMAForTransPosition + MFMAEnablement;
1718 return TempMFMAForTrans % MFMAChains;
1719 };
1720
1721 unsigned CurrMFMAPosition = 0;
1722 unsigned MFMAChainForMFMA = 0;
1723 unsigned PositionInChainForMFMA = 0;
1724
1725 auto incrementMFMAPosition = [&CurrMFMAPosition, &MFMAChainForMFMA,
1726 &PositionInChainForMFMA, this]() {
1727 ++CurrMFMAPosition;
1728 MFMAChainForMFMA = CurrMFMAPosition % MFMAChains;
1729 PositionInChainForMFMA = CurrMFMAPosition / MFMAChains;
1730 };
1731
1732 bool IsPostRA = Phase == AMDGPU::SchedulingPhase::PostRA;
1733 assert(IsPostRA || MFMAChainSeeds.size() == MFMAChains);
1734
1735 bool UsesFMA = IsSmallKernelType || !IsPostRA;
1736 bool UsesDSRead = IsLargeKernelType && !IsPostRA && FirstPipeDSR;
1737 bool UsesCvt = HasCvt && (IsSmallKernelType || !IsPostRA);
1738 bool UsesVALU = IsSmallKernelType;
1739
1740 // PHASE 1: "Prefetch"
1741 if (UsesFMA) {
1742 // First Round FMA
1743 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1744 Args: SchedGroupMask::VALU, Args&: ExpRequirement, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
1745 if (!IsPostRA && MFMAChains) {
1746 SG->addRule(NewRule: std::make_shared<EnablesNthMFMAInChain>(
1747 args&: PositionInChain, args&: MFMAChainSeeds[MFMAChain], args&: TII, args: SG->getSGID(),
1748 args: true));
1749 } else
1750 SG->addRule(
1751 NewRule: std::make_shared<EnablesNthMFMA>(args: 1, args&: TII, args: SG->getSGID(), args: true));
1752 SG->addRule(NewRule: std::make_shared<IsFMA>(args&: TII, args: SG->getSGID()));
1753 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
1754
1755 // Second Round FMA
1756 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1757 Args: SchedGroupMask::VALU, Args&: ExpRequirement, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
1758 if (!IsPostRA && MFMAChains) {
1759 SG->addRule(NewRule: std::make_shared<EnablesNthMFMAInChain>(
1760 args: getNextTransPositionInChain(),
1761 args&: MFMAChainSeeds[getNextTransMFMAChain()], args&: TII, args: SG->getSGID(), args: true));
1762 } else
1763 SG->addRule(NewRule: std::make_shared<EnablesNthMFMA>(args: MFMAEnablement + 1, args&: TII,
1764 args: SG->getSGID(), args: true));
1765 SG->addRule(NewRule: std::make_shared<IsFMA>(args&: TII, args: SG->getSGID()));
1766 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
1767 }
1768
1769 if (UsesDSRead) {
1770 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1771 Args: SchedGroupMask::DS_READ, Args: 2, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
1772 SG->addRule(NewRule: std::make_shared<OccursAtOrAfterNode>(args&: *FirstPipeDSR, args&: TII,
1773 args: SG->getSGID()));
1774 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
1775 }
1776
1777 // First Round EXP
1778 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1779 Args: SchedGroupMask::TRANS, Args&: ExpRequirement, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
1780 if (!IsPostRA && MFMAChains)
1781 SG->addRule(NewRule: std::make_shared<EnablesNthMFMAInChain>(
1782 args&: PositionInChain, args&: MFMAChainSeeds[MFMAChain], args&: TII, args: SG->getSGID(), args: true));
1783 else
1784 SG->addRule(NewRule: std::make_shared<EnablesNthMFMA>(args: 1, args&: TII, args: SG->getSGID(), args: true));
1785 SG->addRule(NewRule: std::make_shared<IsPipeExp>(args&: TII, args: SG->getSGID(), args: true));
1786 SG->addRule(NewRule: std::make_shared<LessThanNSuccs>(args: 8, args&: TII, args: SG->getSGID(),
1787 args&: HasChainBetweenCvt));
1788 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
1789
1790 incrementTransPosition();
1791
1792 // First Round CVT, Third Round FMA, Second Round EXP; interleaved
1793 for (unsigned I = 0; I < ExpRequirement; I++) {
1794 // First Round CVT
1795 if (UsesCvt) {
1796 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1797 Args: SchedGroupMask::VALU, Args: 1, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
1798 SG->addRule(NewRule: std::make_shared<IsCvt>(args&: TII, args: SG->getSGID()));
1799 if (HasChainBetweenCvt)
1800 SG->addRule(NewRule: std::make_shared<IsReachableFromPrevNthGroup>(
1801 args: 1 + (2 + UsesFMA) * I, args&: TII, args: SG->getSGID()));
1802 else
1803 SG->addRule(NewRule: std::make_shared<IsSuccOfPrevNthGroup>(
1804 args: 1 + (2 + UsesFMA) * I, args&: TII, args: SG->getSGID()));
1805 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
1806 }
1807
1808 // Third Round FMA
1809 if (UsesFMA) {
1810 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1811 Args: SchedGroupMask::VALU, Args: 1, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
1812 if (!IsPostRA && MFMAChains) {
1813 SG->addRule(NewRule: std::make_shared<EnablesNthMFMAInChain>(
1814 args: getNextTransPositionInChain(),
1815 args&: MFMAChainSeeds[getNextTransMFMAChain()], args&: TII, args: SG->getSGID(), args: true));
1816 } else
1817 SG->addRule(NewRule: std::make_shared<EnablesNthMFMA>(args: 2 * MFMAEnablement + 1,
1818 args&: TII, args: SG->getSGID(), args: true));
1819 SG->addRule(NewRule: std::make_shared<IsFMA>(args&: TII, args: SG->getSGID()));
1820 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
1821 }
1822
1823 // Second Round EXP
1824 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1825 Args: SchedGroupMask::TRANS, Args: 1, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
1826 if (!IsPostRA && MFMAChains)
1827 SG->addRule(NewRule: std::make_shared<EnablesNthMFMAInChain>(
1828 args&: PositionInChain, args&: MFMAChainSeeds[MFMAChain], args&: TII, args: SG->getSGID(),
1829 args: true));
1830 else
1831 SG->addRule(NewRule: std::make_shared<EnablesNthMFMA>(args: MFMAEnablement + 1, args&: TII,
1832 args: SG->getSGID(), args: true));
1833 SG->addRule(NewRule: std::make_shared<IsPipeExp>(args&: TII, args: SG->getSGID(), args: true));
1834 SG->addRule(NewRule: std::make_shared<LessThanNSuccs>(args: 8, args&: TII, args: SG->getSGID(),
1835 args&: HasChainBetweenCvt));
1836 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
1837 }
1838
1839 // The "extra" EXP which enables all MFMA
1840 // TODO: UsesExtraExp
1841 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1842 Args: SchedGroupMask::TRANS, Args: 1, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
1843 SG->addRule(NewRule: std::make_shared<IsPipeExp>(args&: TII, args: SG->getSGID(), args: true));
1844 SG->addRule(NewRule: std::make_shared<GreaterThanOrEqualToNSuccs>(
1845 args: 8, args&: TII, args: SG->getSGID(), args&: HasChainBetweenCvt));
1846 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
1847
1848 // PHASE 2: Main Interleave Loop
1849
1850 // The number of MFMAs per iteration
1851 unsigned MFMARatio =
1852 MFMAEnablement > ExpRequirement ? MFMAEnablement / ExpRequirement : 1;
1853 // The number of Exps per iteration
1854 unsigned ExpRatio =
1855 MFMAEnablement > ExpRequirement ? 1 : ExpRequirement / MFMAEnablement;
1856 // The reamaining Exps
1857 unsigned RemainingExp = TransPipeCount > (2 * ExpRequirement)
1858 ? TransPipeCount - (2 * ExpRequirement)
1859 : 0;
1860 unsigned ExpLoopCount = RemainingExp / ExpRatio;
1861 // In loop MFMAs
1862 unsigned MFMAInLoop = MFMAPipeCount > (MFMAEnablement * 2)
1863 ? MFMAPipeCount - (MFMAEnablement * 2)
1864 : 0;
1865 unsigned MFMALoopCount = MFMAInLoop / MFMARatio;
1866 unsigned VALUOps =
1867 AddPipeCount < MFMAPipeCount ? 1 : AddPipeCount / MFMAPipeCount;
1868 unsigned LoopSize = std::min(a: ExpLoopCount, b: MFMALoopCount);
1869
1870 for (unsigned I = 0; I < LoopSize; I++) {
1871 if (!(I * ExpRatio % ExpRequirement))
1872 incrementTransPosition();
1873
1874 // Round N MFMA
1875 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1876 Args: SchedGroupMask::MFMA, Args&: MFMARatio, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
1877 if (!IsPostRA && MFMAChains)
1878 SG->addRule(NewRule: std::make_shared<IsExactMFMA>(
1879 args&: PositionInChainForMFMA, args&: MFMAChainSeeds[MFMAChainForMFMA], args&: TII,
1880 args: SG->getSGID(), args: true));
1881 else
1882 SG->addRule(NewRule: std::make_shared<OccursAfterExp>(args&: TII, args: SG->getSGID(), args: true));
1883 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
1884 incrementMFMAPosition();
1885
1886 if (UsesVALU) {
1887 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1888 Args: SchedGroupMask::VALU, Args&: VALUOps, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
1889 SG->addRule(NewRule: std::make_shared<IsPipeAdd>(args&: TII, args: SG->getSGID()));
1890 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
1891 }
1892
1893 if (UsesDSRead && !(I % 4)) {
1894 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1895 Args: SchedGroupMask::DS_READ, Args: 2, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
1896 SG->addRule(NewRule: std::make_shared<OccursAtOrAfterNode>(args&: *FirstPipeDSR, args&: TII,
1897 args: SG->getSGID()));
1898 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
1899 }
1900
1901 // CVT, EXP, FMA Interleaving
1902 for (unsigned J = 0; J < ExpRatio; J++) {
1903 auto MFMAOffset = (1 + UsesVALU) * MFMARatio * (I + 1);
1904 auto MaxMFMAOffset =
1905 (1 + UsesVALU) * ExpRequirement * MFMARatio / ExpRatio;
1906
1907 // Round N + 1 CVT
1908 if (UsesCvt) {
1909 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1910 Args: SchedGroupMask::VALU, Args: 1, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
1911 SG->addRule(NewRule: std::make_shared<IsCvt>(args&: TII, args: SG->getSGID()));
1912 auto BaseDiff = (2 + UsesFMA) * (ExpRequirement - 1) + 1;
1913 auto DSROffset = I / 4 + 1;
1914 auto MaxDSROffset = MaxMFMAOffset / 4;
1915 // TODO: UsesExtraExp
1916 auto ExpOffset = I * ExpRatio + J >= ExpRequirement ? 0 : 1;
1917 auto CurrentOffset = UsesDSRead * std::min(a: MaxDSROffset, b: DSROffset) +
1918 std::min(a: MaxMFMAOffset, b: MFMAOffset) + BaseDiff +
1919 ExpOffset;
1920 if (HasChainBetweenCvt)
1921 SG->addRule(NewRule: std::make_shared<IsReachableFromPrevNthGroup>(
1922 args&: CurrentOffset, args&: TII, args: SG->getSGID()));
1923 else
1924 SG->addRule(NewRule: std::make_shared<IsSuccOfPrevNthGroup>(args&: CurrentOffset, args&: TII,
1925 args: SG->getSGID()));
1926 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
1927 }
1928
1929 // Round N + 3 FMA
1930 if (UsesFMA) {
1931 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1932 Args: SchedGroupMask::VALU, Args: 1, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
1933 if (!IsPostRA && MFMAChains)
1934 SG->addRule(NewRule: std::make_shared<EnablesNthMFMAInChain>(
1935 args: getNextTransPositionInChain(),
1936 args&: MFMAChainSeeds[getNextTransMFMAChain()], args&: TII, args: SG->getSGID(),
1937 args: true));
1938 else
1939 SG->addRule(NewRule: std::make_shared<EnablesNthMFMA>(
1940 args: (((I * ExpRatio + J) / ExpRequirement) + 3) * MFMAEnablement + 1,
1941 args&: TII, args: SG->getSGID(), args: true));
1942 SG->addRule(NewRule: std::make_shared<IsFMA>(args&: TII, args: SG->getSGID()));
1943 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
1944 }
1945
1946 // Round N + 2 Exp
1947 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1948 Args: SchedGroupMask::TRANS, Args: 1, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
1949 if (!IsPostRA && MFMAChains)
1950 SG->addRule(NewRule: std::make_shared<EnablesNthMFMAInChain>(
1951 args&: PositionInChain, args&: MFMAChainSeeds[MFMAChain], args&: TII, args: SG->getSGID(),
1952 args: true));
1953 else
1954 SG->addRule(NewRule: std::make_shared<EnablesNthMFMA>(
1955 args: (((I * ExpRatio + J) / ExpRequirement) + 2) * MFMAEnablement + 1,
1956 args&: TII, args: SG->getSGID(), args: true));
1957 SG->addRule(NewRule: std::make_shared<IsPipeExp>(args&: TII, args: SG->getSGID(), args: true));
1958 SG->addRule(NewRule: std::make_shared<LessThanNSuccs>(args: 8, args&: TII, args: SG->getSGID(),
1959 args&: HasChainBetweenCvt));
1960 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
1961 }
1962 }
1963
1964 // PHASE 3: Remaining MFMAs
1965 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
1966 Args: SchedGroupMask::MFMA, Args: MFMAEnablement * 2, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
1967 SG->addRule(NewRule: std::make_shared<OccursAfterExp>(args&: TII, args: SG->getSGID(), args: true));
1968 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
1969 return true;
1970}
1971
1972class MFMAExpSimpleInterleaveOpt final : public IGLPStrategy {
1973public:
1974 bool applyIGLPStrategy(
1975 DenseMap<int, SUnitsToCandidateSGsMap> &SyncedInstrs,
1976 DenseMap<int, SmallVector<SchedGroup, 4>> &SyncedSchedGroups,
1977 AMDGPU::SchedulingPhase Phase) override;
1978
1979 bool shouldApplyStrategy(ScheduleDAGInstrs *DAG,
1980 AMDGPU::SchedulingPhase Phase) override {
1981 return true;
1982 }
1983
1984 MFMAExpSimpleInterleaveOpt(ScheduleDAGInstrs *DAG, const SIInstrInfo *TII,
1985 MachineInstr *IGLPOptMI)
1986 : IGLPStrategy(DAG, TII, IGLPOptMI) {
1987 IsBottomUp = true;
1988 }
1989};
1990
1991bool MFMAExpSimpleInterleaveOpt::applyIGLPStrategy(
1992 DenseMap<int, SUnitsToCandidateSGsMap> &SyncedInstrs,
1993 DenseMap<int, SmallVector<SchedGroup, 4>> &SyncedSchedGroups,
1994 AMDGPU::SchedulingPhase Phase) {
1995 // Count the number of MFMA instructions.
1996 unsigned MFMACount = 0;
1997 for (const MachineInstr &I : *DAG)
1998 if (TII->isMFMAorWMMA(MI: I))
1999 ++MFMACount;
2000
2001 const unsigned PipelineSyncID = 0;
2002 for (unsigned I = 0; I < MFMACount * 3; ++I) {
2003 SchedGroup *SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2004 Args: SchedGroupMask::TRANS, Args: 1, Args: PipelineSyncID, Args&: DAG, Args&: TII);
2005 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2006
2007 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2008 Args: SchedGroupMask::MFMA, Args: 1, Args: PipelineSyncID, Args&: DAG, Args&: TII);
2009 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2010 }
2011
2012 return true;
2013}
2014
2015class MFMASmallGemmSingleWaveOpt final : public IGLPStrategy {
2016private:
2017 // Whether the DS_READ is a predecessor of first four MFMA in region
2018 class EnablesInitialMFMA final : public InstructionRule {
2019 public:
2020 bool apply(const SUnit *SU, const ArrayRef<SUnit *> Collection,
2021 SmallVectorImpl<SchedGroup> &SyncPipe) override {
2022 if (!SyncPipe.size())
2023 return false;
2024 int MFMAsFound = 0;
2025 if (!Cache->size()) {
2026 for (auto &Elt : SyncPipe[0].DAG->SUnits) {
2027 if (TII->isMFMAorWMMA(MI: *Elt.getInstr())) {
2028 ++MFMAsFound;
2029 if (MFMAsFound > 4)
2030 break;
2031 Cache->push_back(Elt: &Elt);
2032 }
2033 }
2034 }
2035
2036 auto *DAG = SyncPipe[0].DAG;
2037 for (auto &Elt : *Cache) {
2038 if (DAG->IsReachable(SU: Elt, TargetSU: const_cast<SUnit *>(SU)))
2039 return true;
2040 }
2041 return false;
2042 }
2043
2044 EnablesInitialMFMA(const SIInstrInfo *TII, unsigned SGID,
2045 bool NeedsCache = false)
2046 : InstructionRule(TII, SGID, NeedsCache) {}
2047 };
2048
2049 // Whether the MI is a V_PERM and is a predecessor of a common DS_WRITE
2050 class IsPermForDSW final : public InstructionRule {
2051 public:
2052 bool apply(const SUnit *SU, const ArrayRef<SUnit *> Collection,
2053 SmallVectorImpl<SchedGroup> &SyncPipe) override {
2054 auto *MI = SU->getInstr();
2055 if (MI->getOpcode() != AMDGPU::V_PERM_B32_e64)
2056 return false;
2057
2058 bool FitsInGroup = false;
2059 // Does the VALU have a DS_WRITE successor
2060 if (!Collection.size()) {
2061 for (auto &Succ : SU->Succs) {
2062 SUnit *SuccUnit = Succ.getSUnit();
2063 if (TII->isDS(MI: *SuccUnit->getInstr()) &&
2064 SuccUnit->getInstr()->mayStore()) {
2065 Cache->push_back(Elt: SuccUnit);
2066 FitsInGroup = true;
2067 }
2068 }
2069 return FitsInGroup;
2070 }
2071
2072 // Does the VALU have a DS_WRITE successor that is the same as other
2073 // VALU already in the group. The V_PERMs will all share 1 DS_W succ
2074 return llvm::any_of(Range&: *Cache, P: [&SU](SUnit *Elt) {
2075 return llvm::any_of(Range: SU->Succs, P: [&Elt](const SDep &ThisSucc) {
2076 return ThisSucc.getSUnit() == Elt;
2077 });
2078 });
2079 }
2080
2081 IsPermForDSW(const SIInstrInfo *TII, unsigned SGID, bool NeedsCache = false)
2082 : InstructionRule(TII, SGID, NeedsCache) {}
2083 };
2084
2085 // Whether the SU is a successor of any element in previous SchedGroup
2086 class IsSuccOfPrevGroup final : public InstructionRule {
2087 public:
2088 bool apply(const SUnit *SU, const ArrayRef<SUnit *> Collection,
2089 SmallVectorImpl<SchedGroup> &SyncPipe) override {
2090 SchedGroup *OtherGroup = nullptr;
2091 for (auto &PipeSG : SyncPipe) {
2092 if ((unsigned)PipeSG.getSGID() == SGID - 1) {
2093 OtherGroup = &PipeSG;
2094 }
2095 }
2096
2097 if (!OtherGroup)
2098 return false;
2099 if (!OtherGroup->Collection.size())
2100 return true;
2101
2102 // Does the previous VALU have this DS_Write as a successor
2103 return any_of(Range&: OtherGroup->Collection, P: [&SU](SUnit *Elt) {
2104 return any_of(Range&: Elt->Succs,
2105 P: [&SU](SDep &Succ) { return Succ.getSUnit() == SU; });
2106 });
2107 }
2108 IsSuccOfPrevGroup(const SIInstrInfo *TII, unsigned SGID,
2109 bool NeedsCache = false)
2110 : InstructionRule(TII, SGID, NeedsCache) {}
2111 };
2112
2113 // Whether the combined load width of group is 128 bits
2114 class VMEMSize final : public InstructionRule {
2115 public:
2116 bool apply(const SUnit *SU, const ArrayRef<SUnit *> Collection,
2117 SmallVectorImpl<SchedGroup> &SyncPipe) override {
2118 auto *MI = SU->getInstr();
2119 if (MI->getOpcode() == TargetOpcode::BUNDLE)
2120 return false;
2121 if (!Collection.size())
2122 return true;
2123
2124 uint64_t NumBits = 0;
2125
2126 auto TRI = TII->getRegisterInfo();
2127 auto &MRI = MI->getMF()->getRegInfo();
2128 for (auto &Elt : Collection) {
2129 auto Op = Elt->getInstr()->getOperand(i: 0);
2130 auto Size =
2131 TRI.getRegSizeInBits(RC: *TRI.getRegClassForOperandReg(MRI, MO: Op));
2132 NumBits += Size;
2133 }
2134
2135 if (NumBits < 128) {
2136 assert(TII->isVMEM(*MI) && MI->mayLoad());
2137 if (NumBits + TRI.getRegSizeInBits(RC: *TRI.getRegClassForOperandReg(
2138 MRI, MO: MI->getOperand(i: 0))) <=
2139 128)
2140 return true;
2141 }
2142
2143 return false;
2144 }
2145
2146 VMEMSize(const SIInstrInfo *TII, unsigned SGID, bool NeedsCache = false)
2147 : InstructionRule(TII, SGID, NeedsCache) {}
2148 };
2149
2150 /// Whether the SU shares a V_PERM predecessor with any SU in the SchedGroup
2151 /// that is \p Distance steps away
2152 class SharesPredWithPrevNthGroup final : public InstructionRule {
2153 private:
2154 unsigned Distance = 1;
2155
2156 public:
2157 bool apply(const SUnit *SU, const ArrayRef<SUnit *> Collection,
2158 SmallVectorImpl<SchedGroup> &SyncPipe) override {
2159 SchedGroup *OtherGroup = nullptr;
2160 if (!SyncPipe.size())
2161 return false;
2162
2163 if (!Cache->size()) {
2164
2165 for (auto &PipeSG : SyncPipe) {
2166 if ((unsigned)PipeSG.getSGID() == SGID - Distance) {
2167 OtherGroup = &PipeSG;
2168 }
2169 }
2170
2171 if (!OtherGroup)
2172 return false;
2173 if (!OtherGroup->Collection.size())
2174 return true;
2175
2176 for (auto &OtherEle : OtherGroup->Collection) {
2177 for (auto &Pred : OtherEle->Preds) {
2178 if (Pred.getSUnit()->getInstr()->getOpcode() ==
2179 AMDGPU::V_PERM_B32_e64)
2180 Cache->push_back(Elt: Pred.getSUnit());
2181 }
2182 }
2183
2184 // If the other group has no PERM preds, then this group won't share any
2185 if (!Cache->size())
2186 return false;
2187 }
2188
2189 auto *DAG = SyncPipe[0].DAG;
2190 // Does the previous DS_WRITE share a V_PERM predecessor with this
2191 // VMEM_READ
2192 return llvm::any_of(Range&: *Cache, P: [&SU, &DAG](SUnit *Elt) {
2193 return DAG->IsReachable(SU: const_cast<SUnit *>(SU), TargetSU: Elt);
2194 });
2195 }
2196 SharesPredWithPrevNthGroup(unsigned Distance, const SIInstrInfo *TII,
2197 unsigned SGID, bool NeedsCache = false)
2198 : InstructionRule(TII, SGID, NeedsCache), Distance(Distance) {}
2199 };
2200
2201public:
2202 bool applyIGLPStrategy(
2203 DenseMap<int, SUnitsToCandidateSGsMap> &SyncedInstrs,
2204 DenseMap<int, SmallVector<SchedGroup, 4>> &SyncedSchedGroups,
2205 AMDGPU::SchedulingPhase Phase) override;
2206
2207 // The number of DS_WRITE counts stored on the IGLP_OPT in the Initial phase.
2208 static constexpr unsigned NumDSWCounts = 3;
2209
2210 bool shouldApplyStrategy(ScheduleDAGInstrs *DAG,
2211 AMDGPU::SchedulingPhase Phase) override {
2212 // The later phases need the DS_WRITE counts of the Initial phase.
2213 return Phase == AMDGPU::SchedulingPhase::Initial ||
2214 hasIGLPOptData(NumValues: NumDSWCounts);
2215 }
2216
2217 MFMASmallGemmSingleWaveOpt(ScheduleDAGInstrs *DAG, const SIInstrInfo *TII,
2218 MachineInstr *IGLPOptMI)
2219 : IGLPStrategy(DAG, TII, IGLPOptMI) {
2220 IsBottomUp = false;
2221 }
2222};
2223
2224bool MFMASmallGemmSingleWaveOpt::applyIGLPStrategy(
2225 DenseMap<int, SUnitsToCandidateSGsMap> &SyncedInstrs,
2226 DenseMap<int, SmallVector<SchedGroup, 4>> &SyncedSchedGroups,
2227 AMDGPU::SchedulingPhase Phase) {
2228 unsigned MFMACount = 0;
2229 unsigned DSRCount = 0;
2230 // The DS_WRITE counts are computed in the Initial phase and stored on the
2231 // IGLP_OPT for the later phases.
2232 unsigned DSWCount = 0;
2233 unsigned DSWWithPermCount = 0;
2234 unsigned DSWWithSharedVMEMCount = 0;
2235
2236 bool IsInitial = Phase == AMDGPU::SchedulingPhase::Initial;
2237
2238 if (!IsInitial) {
2239 std::optional<std::array<int64_t, NumDSWCounts>> Data =
2240 getIGLPOptData<NumDSWCounts>();
2241 assert(Data && "checked by shouldApplyStrategy");
2242 DSWCount = (*Data)[0];
2243 DSWWithPermCount = (*Data)[1];
2244 DSWWithSharedVMEMCount = (*Data)[2];
2245 }
2246
2247 SmallVector<SUnit *, 6> DSWithPerms;
2248 for (auto &SU : DAG->SUnits) {
2249 auto *I = SU.getInstr();
2250 if (TII->isMFMAorWMMA(MI: *I))
2251 ++MFMACount;
2252 else if (TII->isDS(MI: *I)) {
2253 if (I->mayLoad())
2254 ++DSRCount;
2255 else if (I->mayStore() && IsInitial) {
2256 ++DSWCount;
2257 for (auto Pred : SU.Preds) {
2258 if (Pred.getSUnit()->getInstr()->getOpcode() ==
2259 AMDGPU::V_PERM_B32_e64) {
2260 DSWithPerms.push_back(Elt: &SU);
2261 break;
2262 }
2263 }
2264 }
2265 }
2266 }
2267
2268 if (IsInitial) {
2269 DSWWithPermCount = static_cast<unsigned>(DSWithPerms.size());
2270 auto *I = DSWithPerms.begin();
2271 auto *E = DSWithPerms.end();
2272
2273 // Get the count of DS_WRITES with V_PERM predecessors which
2274 // have loop carried dependencies (WAR) on the same VMEM_READs.
2275 // We consider partial overlap as a miss -- in other words,
2276 // for a given DS_W, we only consider another DS_W as matching
2277 // if there is a corresponding (in terms of the VMEM_R it uses) V_PERM pred
2278 // for every V_PERM pred of this DS_W.
2279 DenseMap<MachineInstr *, SUnit *> VMEMLookup;
2280 SmallVector<SUnit *, 6> Counted;
2281 for (; I != E; I++) {
2282 SUnit *Cand = nullptr;
2283 bool MissedAny = false;
2284 for (auto &Pred : (*I)->Preds) {
2285 if (Pred.getSUnit()->getInstr()->getOpcode() != AMDGPU::V_PERM_B32_e64)
2286 continue;
2287
2288 if (Cand && llvm::is_contained(Range&: Counted, Element: Cand))
2289 break;
2290
2291 for (auto &Succ : Pred.getSUnit()->Succs) {
2292 auto *MI = Succ.getSUnit()->getInstr();
2293 if (!TII->isVMEM(MI: *MI) || !MI->mayLoad())
2294 continue;
2295
2296 if (MissedAny || !VMEMLookup.size()) {
2297 MissedAny = true;
2298 VMEMLookup[MI] = *I;
2299 continue;
2300 }
2301
2302 auto [It, Inserted] = VMEMLookup.try_emplace(Key: MI, Args&: *I);
2303 if (Inserted) {
2304 MissedAny = true;
2305 continue;
2306 }
2307
2308 Cand = It->second;
2309 if (llvm::is_contained(Range&: Counted, Element: Cand)) {
2310 MissedAny = true;
2311 break;
2312 }
2313 }
2314 }
2315 if (!MissedAny && Cand) {
2316 DSWWithSharedVMEMCount += 2;
2317 Counted.push_back(Elt: Cand);
2318 Counted.push_back(Elt: *I);
2319 }
2320 }
2321
2322 setIGLPOptData({DSWCount, DSWWithPermCount, DSWWithSharedVMEMCount});
2323 }
2324
2325 assert(DSWWithSharedVMEMCount <= DSWWithPermCount);
2326 SchedGroup *SG;
2327 unsigned PipelineSyncID = 0;
2328 // For kernels with V_PERM, there are enough VALU to mix in between MFMAs
2329 if (DSWWithPermCount) {
2330 for (unsigned I = 0; I < MFMACount; I++) {
2331 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2332 Args: SchedGroupMask::MFMA, Args: 1, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
2333 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2334
2335 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2336 Args: SchedGroupMask::VALU, Args: 2, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
2337 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2338 }
2339 }
2340
2341 PipelineSyncID = 1;
2342 // Phase 1: Break up DS_READ and MFMA clusters.
2343 // First DS_READ to make ready initial MFMA, then interleave MFMA with DS_READ
2344 // prefetch
2345
2346 // Make ready initial MFMA
2347 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2348 Args: SchedGroupMask::DS_READ, Args: 4, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
2349 SG->addRule(NewRule: std::make_shared<EnablesInitialMFMA>(args&: TII, args: SG->getSGID(), args: true));
2350 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2351
2352 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2353 Args: SchedGroupMask::MFMA, Args: 1, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
2354 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2355
2356 // Interleave MFMA with DS_READ prefetch
2357 for (unsigned I = 4; I < DSRCount; ++I) {
2358 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2359 Args: SchedGroupMask::DS_READ, Args: 1, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
2360 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2361
2362 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2363 Args: SchedGroupMask::MFMA, Args: 1, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
2364 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2365 }
2366
2367 // Phase 2a: Loop carried dependency with V_PERM
2368 // Schedule VPerm & DS_WRITE as closely as possible to the VMEM_READ they
2369 // depend on. Interleave MFMA to keep XDL unit busy throughout.
2370 for (unsigned I = DSWWithSharedVMEMCount; I < DSWWithPermCount; ++I) {
2371 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2372 Args: SchedGroupMask::VALU, Args: 4, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
2373 SG->addRule(NewRule: std::make_shared<IsPermForDSW>(args&: TII, args: SG->getSGID(), args: true));
2374 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2375
2376 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2377 Args: SchedGroupMask::DS_WRITE, Args: 1, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
2378 SG->addRule(NewRule: std::make_shared<IsSuccOfPrevGroup>(args&: TII, args: SG->getSGID()));
2379 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2380
2381 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2382 Args: SchedGroupMask::VMEM_READ, Args: 4, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
2383 SG->addRule(NewRule: std::make_shared<SharesPredWithPrevNthGroup>(
2384 args: 1, args&: TII, args: SG->getSGID(), args: true));
2385 SG->addRule(NewRule: std::make_shared<VMEMSize>(args&: TII, args: SG->getSGID()));
2386 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2387
2388 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2389 Args: SchedGroupMask::MFMA, Args: 1, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
2390 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2391
2392 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2393 Args: SchedGroupMask::VMEM_READ, Args: 4, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
2394 SG->addRule(NewRule: std::make_shared<SharesPredWithPrevNthGroup>(
2395 args: 3, args&: TII, args: SG->getSGID(), args: true));
2396 SG->addRule(NewRule: std::make_shared<VMEMSize>(args&: TII, args: SG->getSGID()));
2397 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2398
2399 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2400 Args: SchedGroupMask::MFMA, Args: 1, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
2401 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2402 }
2403
2404 // Phase 2b: Loop carried dependency without V_PERM
2405 // Schedule DS_WRITE as closely as possible to the VMEM_READ they depend on.
2406 // Interleave MFMA to keep XDL unit busy throughout.
2407 for (unsigned I = DSWWithPermCount; I < DSWCount; I++) {
2408 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2409 Args: SchedGroupMask::DS_WRITE, Args: 1, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
2410 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2411
2412 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2413 Args: SchedGroupMask::VMEM_READ, Args: 4, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
2414 SG->addRule(NewRule: std::make_shared<VMEMSize>(args&: TII, args: SG->getSGID()));
2415 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2416
2417 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2418 Args: SchedGroupMask::MFMA, Args: 1, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
2419 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2420 }
2421
2422 // Phase 2c: Loop carried dependency with V_PERM, VMEM_READs are
2423 // ultimately used by two DS_WRITE
2424 // Schedule VPerm & DS_WRITE as closely as possible to the VMEM_READ they
2425 // depend on. Interleave MFMA to keep XDL unit busy throughout.
2426
2427 for (unsigned I = 0; I < DSWWithSharedVMEMCount; ++I) {
2428 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2429 Args: SchedGroupMask::VALU, Args: 4, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
2430 SG->addRule(NewRule: std::make_shared<IsPermForDSW>(args&: TII, args: SG->getSGID(), args: true));
2431 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2432
2433 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2434 Args: SchedGroupMask::DS_WRITE, Args: 1, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
2435 SG->addRule(NewRule: std::make_shared<IsSuccOfPrevGroup>(args&: TII, args: SG->getSGID()));
2436 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2437
2438 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2439 Args: SchedGroupMask::MFMA, Args: 1, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
2440 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2441
2442 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2443 Args: SchedGroupMask::VALU, Args: 4, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
2444 SG->addRule(NewRule: std::make_shared<IsPermForDSW>(args&: TII, args: SG->getSGID(), args: true));
2445 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2446
2447 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2448 Args: SchedGroupMask::DS_WRITE, Args: 1, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
2449 SG->addRule(NewRule: std::make_shared<IsSuccOfPrevGroup>(args&: TII, args: SG->getSGID()));
2450 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2451
2452 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2453 Args: SchedGroupMask::MFMA, Args: 1, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
2454 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2455
2456 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2457 Args: SchedGroupMask::VMEM_READ, Args: 4, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
2458 SG->addRule(NewRule: std::make_shared<SharesPredWithPrevNthGroup>(
2459 args: 2, args&: TII, args: SG->getSGID(), args: true));
2460 SG->addRule(NewRule: std::make_shared<VMEMSize>(args&: TII, args: SG->getSGID()));
2461 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2462
2463 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2464 Args: SchedGroupMask::MFMA, Args: 1, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
2465 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2466
2467 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2468 Args: SchedGroupMask::VMEM_READ, Args: 4, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
2469 SG->addRule(NewRule: std::make_shared<SharesPredWithPrevNthGroup>(
2470 args: 4, args&: TII, args: SG->getSGID(), args: true));
2471 SG->addRule(NewRule: std::make_shared<VMEMSize>(args&: TII, args: SG->getSGID()));
2472 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2473
2474 SG = &SyncedSchedGroups[PipelineSyncID].emplace_back(
2475 Args: SchedGroupMask::MFMA, Args: 1, Args&: PipelineSyncID, Args&: DAG, Args&: TII);
2476 SG->findCandidateSUnits(SyncedInstrs&: SyncedInstrs[SG->getSyncID()]);
2477 }
2478
2479 return true;
2480}
2481
2482static std::unique_ptr<IGLPStrategy>
2483createIGLPStrategy(IGLPStrategyID ID, ScheduleDAGInstrs *DAG,
2484 const SIInstrInfo *TII, MachineInstr *IGLPOptMI) {
2485 switch (ID) {
2486 case MFMASmallGemmOptID:
2487 return std::make_unique<MFMASmallGemmOpt>(args&: DAG, args&: TII, args&: IGLPOptMI);
2488 case MFMASmallGemmSingleWaveOptID:
2489 return std::make_unique<MFMASmallGemmSingleWaveOpt>(args&: DAG, args&: TII, args&: IGLPOptMI);
2490 case MFMAExpInterleaveID:
2491 return std::make_unique<MFMAExpInterleaveOpt>(args&: DAG, args&: TII, args&: IGLPOptMI);
2492 case MFMAExpSimpleInterleaveID:
2493 return std::make_unique<MFMAExpSimpleInterleaveOpt>(args&: DAG, args&: TII, args&: IGLPOptMI);
2494 }
2495
2496 llvm_unreachable("Unknown IGLPStrategyID");
2497}
2498
2499class IGroupLPDAGMutation : public ScheduleDAGMutation {
2500private:
2501 const SIInstrInfo *TII;
2502
2503 ScheduleDAGMI *DAG;
2504
2505 // Organize lists of SchedGroups by their SyncID. SchedGroups /
2506 // SCHED_GROUP_BARRIERs with different SyncIDs will have no edges added
2507 // between then.
2508 DenseMap<int, SmallVector<SchedGroup, 4>> SyncedSchedGroups;
2509
2510 // Used to track instructions that can be mapped to multiple sched groups
2511 DenseMap<int, SUnitsToCandidateSGsMap> SyncedInstrs;
2512
2513 // Add DAG edges that enforce SCHED_BARRIER ordering.
2514 void addSchedBarrierEdges(SUnit &SU);
2515
2516 // Use a SCHED_BARRIER's mask to identify instruction SchedGroups that should
2517 // not be reordered accross the SCHED_BARRIER. This is used for the base
2518 // SCHED_BARRIER, and not SCHED_GROUP_BARRIER. The difference is that
2519 // SCHED_BARRIER will always block all instructions that can be classified
2520 // into a particular SchedClass, whereas SCHED_GROUP_BARRIER has a fixed size
2521 // and may only synchronize with some SchedGroups. Returns the inverse of
2522 // Mask. SCHED_BARRIER's mask describes which instruction types should be
2523 // allowed to be scheduled across it. Invert the mask to get the
2524 // SchedGroupMask of instructions that should be barred.
2525 SchedGroupMask invertSchedBarrierMask(SchedGroupMask Mask) const;
2526
2527 // Create SchedGroups for a SCHED_GROUP_BARRIER.
2528 void initSchedGroupBarrierPipelineStage(
2529 std::vector<SUnit>::reverse_iterator RIter);
2530
2531 bool initIGLPOpt(SUnit &SU);
2532
2533public:
2534 void apply(ScheduleDAGInstrs *DAGInstrs) override;
2535
2536 // The order in which the PipelineSolver should process the candidate
2537 // SchedGroup for a PipelineInstr. BOTTOM_UP will try to add SUs to the last
2538 // created SchedGroup first, and will consider that as the ultimate
2539 // predecessor group when linking. TOP_DOWN instead links and processes the
2540 // first created SchedGroup first.
2541 bool IsBottomUp = true;
2542
2543 // The scheduling phase this application of IGLP corresponds with.
2544 AMDGPU::SchedulingPhase Phase = AMDGPU::SchedulingPhase::Initial;
2545
2546 IGroupLPDAGMutation() = default;
2547 IGroupLPDAGMutation(AMDGPU::SchedulingPhase Phase) : Phase(Phase) {}
2548};
2549
2550unsigned SchedGroup::NumSchedGroups = 0;
2551
2552bool SchedGroup::tryAddEdge(SUnit *A, SUnit *B) {
2553 return A != B && DAG->addEdge(SuccSU: B, PredDep: SDep(A, SDep::Artificial));
2554}
2555
2556bool SchedGroup::canAddMI(const MachineInstr &MI) const {
2557 bool Result = false;
2558 if (MI.isMetaInstruction())
2559 Result = false;
2560
2561 else if (MI.isInlineAsm()) {
2562 const SIRegisterInfo &TRI = TII->getRegisterInfo();
2563 auto &MRI = MI.getParent()->getParent()->getRegInfo();
2564 bool SGPR_used = false, SGPR_big_def = false, VGPR_used = false,
2565 VMFMA_used = false, VReg32_used = false, MayLoad = MI.mayLoad(),
2566 MayStore = MI.mayStore();
2567 for (const MachineOperand &Operand : MI.operands())
2568 if (Operand.isReg()) {
2569 const TargetRegisterClass &RegClass =
2570 *TRI.getRegClassForOperandReg(MRI, MO: Operand);
2571 if (TRI.hasVGPRs(RC: &RegClass)) {
2572 VGPR_used = true;
2573 if (Operand.isUse() && TRI.getRegSizeInBits(RC: RegClass) == 32)
2574 VReg32_used = true;
2575 }
2576 // > 128 bit registers are usually only used by MFMA instructions, so
2577 // we're using that as a heuristic to guess the schedule group mask of
2578 // the inline asm.
2579 if (TRI.hasAGPRs(RC: &RegClass) || TRI.getRegSizeInBits(RC: RegClass) > 128)
2580 VMFMA_used = true;
2581 if (TRI.hasSGPRs(RC: &RegClass))
2582 SGPR_used = true;
2583 if (TRI.getRegSizeInBits(RC: RegClass) > 64 && Operand.isDef())
2584 SGPR_big_def = true;
2585 }
2586
2587 typedef std::underlying_type_t<SchedGroupMask> SGMask_t;
2588 SGMask_t InlineAsmMask = 0;
2589 if (VGPR_used && !VMFMA_used && !MayLoad && !MayStore)
2590 InlineAsmMask |= (SGMask_t)SchedGroupMask::VALU;
2591 if (SGPR_used && !VGPR_used && !MayLoad && !MayStore)
2592 InlineAsmMask |= (SGMask_t)SchedGroupMask::SALU;
2593 if (VMFMA_used)
2594 InlineAsmMask |= (SGMask_t)SchedGroupMask::MFMA;
2595 if (VGPR_used && MayLoad)
2596 InlineAsmMask |= (SGMask_t)(VReg32_used ? SchedGroupMask::DS_READ
2597 : SchedGroupMask::VMEM_READ);
2598 if (VGPR_used && MayStore)
2599 InlineAsmMask |= (SGMask_t)(VReg32_used ? SchedGroupMask::DS_WRITE
2600 : SchedGroupMask::VMEM_WRITE);
2601 if (SGPR_big_def)
2602 InlineAsmMask |= (SGMask_t)SchedGroupMask::DS_READ;
2603 if (InlineAsmMask & (SGMask_t)SchedGroupMask::VALU ||
2604 InlineAsmMask & (SGMask_t)SchedGroupMask::SALU)
2605 InlineAsmMask |= (SGMask_t)SchedGroupMask::ALU;
2606 if (InlineAsmMask & (SGMask_t)SchedGroupMask::DS_READ ||
2607 InlineAsmMask & (SGMask_t)SchedGroupMask::DS_WRITE)
2608 InlineAsmMask |= (SGMask_t)SchedGroupMask::DS;
2609 if (InlineAsmMask & (SGMask_t)SchedGroupMask::VMEM_READ ||
2610 InlineAsmMask & (SGMask_t)SchedGroupMask::VMEM_WRITE)
2611 InlineAsmMask |= (SGMask_t)SchedGroupMask::VMEM;
2612
2613 Result = ((SGMask_t)SGMask & InlineAsmMask) != 0;
2614 }
2615
2616 else if (((SGMask & SchedGroupMask::ALU) != SchedGroupMask::NONE) &&
2617 (TII->isVALU(MI, /*AllowLDSDMA=*/true) || TII->isMFMAorWMMA(MI) ||
2618 TII->isSALU(MI) || TII->isTRANS(MI)))
2619 Result = !MI.mayLoadOrStore();
2620
2621 else if (((SGMask & SchedGroupMask::VALU) != SchedGroupMask::NONE) &&
2622 TII->isVALU(MI, /*AllowLDSDMA=*/false) && !TII->isMFMAorWMMA(MI) &&
2623 !TII->isTRANS(MI)) {
2624 // Some memory instructions may be marked as VALU (e.g. BUFFER_LOAD_*_LDS).
2625 // For our purposes, these shall not be classified as VALU as this results
2626 // in unexpected behavior.
2627 Result = !MI.mayLoadOrStore();
2628 }
2629
2630 else if (((SGMask & SchedGroupMask::SALU) != SchedGroupMask::NONE) &&
2631 TII->isSALU(MI))
2632 Result = !MI.mayLoadOrStore();
2633
2634 else if (((SGMask & SchedGroupMask::MFMA) != SchedGroupMask::NONE) &&
2635 TII->isMFMAorWMMA(MI))
2636 Result = true;
2637
2638 else if (((SGMask & SchedGroupMask::VMEM) != SchedGroupMask::NONE) &&
2639 (TII->isVMEM(MI) || TII->isLDSDMA(MI)))
2640 Result = true;
2641
2642 else if (((SGMask & SchedGroupMask::VMEM_READ) != SchedGroupMask::NONE) &&
2643 MI.mayLoad() && TII->isVMEM(MI) && !TII->isLDSDMA(MI))
2644 Result = true;
2645
2646 else if (((SGMask & SchedGroupMask::VMEM_WRITE) != SchedGroupMask::NONE) &&
2647 MI.mayStore() && TII->isVMEM(MI) && !TII->isLDSDMA(MI))
2648 Result = true;
2649
2650 else if (((SGMask & SchedGroupMask::DS) != SchedGroupMask::NONE) &&
2651 (TII->isDS(MI) || TII->isLDSDMA(MI)))
2652 Result = true;
2653
2654 else if (((SGMask & SchedGroupMask::DS_READ) != SchedGroupMask::NONE) &&
2655 MI.mayLoad() && TII->isDS(MI))
2656 Result = true;
2657
2658 else if (((SGMask & SchedGroupMask::DS_WRITE) != SchedGroupMask::NONE) &&
2659 MI.mayStore() && TII->isDS(MI))
2660 Result = true;
2661
2662 else if (((SGMask & SchedGroupMask::TRANS) != SchedGroupMask::NONE) &&
2663 TII->isTRANS(MI))
2664 Result = true;
2665
2666 else if (((SGMask & SchedGroupMask::LDSDMA) != SchedGroupMask::NONE) &&
2667 TII->isLDSDMA(MI))
2668 Result = true;
2669
2670 LLVM_DEBUG(
2671 dbgs() << "For SchedGroup with mask " << format_hex((int)SGMask, 10, true)
2672 << (Result ? " could classify " : " unable to classify ") << MI);
2673
2674 return Result;
2675}
2676
2677int SchedGroup::link(SUnit &SU, bool MakePred,
2678 std::list<std::pair<SUnit *, SUnit *>> &AddedEdges) {
2679 int MissedEdges = 0;
2680 for (auto *A : Collection) {
2681 SUnit *B = &SU;
2682 if (A == B || A->getInstr()->getOpcode() == AMDGPU::SCHED_GROUP_BARRIER)
2683 continue;
2684 if (MakePred)
2685 std::swap(a&: A, b&: B);
2686
2687 if (DAG->IsReachable(SU: B, TargetSU: A))
2688 continue;
2689
2690 // tryAddEdge returns false if there is a dependency that makes adding
2691 // the A->B edge impossible, otherwise it returns true;
2692 bool Added = tryAddEdge(A, B);
2693 if (Added)
2694 AddedEdges.emplace_back(args&: A, args&: B);
2695 else
2696 ++MissedEdges;
2697 }
2698
2699 return MissedEdges;
2700}
2701
2702void SchedGroup::link(SUnit &SU, bool MakePred) {
2703 for (auto *A : Collection) {
2704 SUnit *B = &SU;
2705 if (A->getInstr()->getOpcode() == AMDGPU::SCHED_GROUP_BARRIER)
2706 continue;
2707 if (MakePred)
2708 std::swap(a&: A, b&: B);
2709
2710 tryAddEdge(A, B);
2711 }
2712}
2713
2714void SchedGroup::link(SUnit &SU,
2715 function_ref<bool(const SUnit *A, const SUnit *B)> P) {
2716 for (auto *A : Collection) {
2717 SUnit *B = &SU;
2718 if (P(A, B))
2719 std::swap(a&: A, b&: B);
2720
2721 tryAddEdge(A, B);
2722 }
2723}
2724
2725void SchedGroup::link(SchedGroup &OtherGroup) {
2726 for (auto *B : OtherGroup.Collection)
2727 link(SU&: *B);
2728}
2729
2730bool SchedGroup::canAddSU(SUnit &SU) const {
2731 MachineInstr &MI = *SU.getInstr();
2732 if (MI.getOpcode() != TargetOpcode::BUNDLE)
2733 return canAddMI(MI);
2734
2735 // Special case for bundled MIs.
2736 const MachineBasicBlock *MBB = MI.getParent();
2737 MachineBasicBlock::instr_iterator B = MI.getIterator(), E = ++B;
2738 while (E != MBB->end() && E->isBundledWithPred())
2739 ++E;
2740
2741 // Return true if all of the bundled MIs can be added to this group.
2742 return std::all_of(first: B, last: E, pred: [this](MachineInstr &MI) { return canAddMI(MI); });
2743}
2744
2745template <class T>
2746void SchedGroup::findCandidateSUnits(T Begin, T End,
2747 SUnitsToCandidateSGsMap &SyncedInstrs) {
2748 for (SUnit &SU : make_range(Begin, End)) {
2749 if (canAddSU(SU))
2750 SyncedInstrs[&SU].push_back(Elt: SGID);
2751 }
2752}
2753
2754void SchedGroup::findCandidateSUnits(SUnitsToCandidateSGsMap &SyncedInstrs) {
2755 findCandidateSUnits(Begin: DAG->SUnits.rbegin(), End: DAG->SUnits.rend(), SyncedInstrs);
2756}
2757
2758void IGroupLPDAGMutation::apply(ScheduleDAGInstrs *DAGInstrs) {
2759 const TargetSchedModel *TSchedModel = DAGInstrs->getSchedModel();
2760 if (!TSchedModel || DAGInstrs->SUnits.empty())
2761 return;
2762
2763 LLVM_DEBUG(dbgs() << "Applying IGroupLPDAGMutation...\n");
2764 const GCNSubtarget &ST = DAGInstrs->MF.getSubtarget<GCNSubtarget>();
2765 TII = ST.getInstrInfo();
2766 DAG = static_cast<ScheduleDAGMI *>(DAGInstrs);
2767 SyncedSchedGroups.clear();
2768 SyncedInstrs.clear();
2769 bool FoundSB = false;
2770 bool FoundIGLP = false;
2771 bool ShouldApplyIGLP = false;
2772 for (auto R = DAG->SUnits.rbegin(), E = DAG->SUnits.rend(); R != E; ++R) {
2773 unsigned Opc = R->getInstr()->getOpcode();
2774 // SCHED_[GROUP_]BARRIER and IGLP are mutually exclusive.
2775 if (Opc == AMDGPU::SCHED_BARRIER) {
2776 addSchedBarrierEdges(SU&: *R);
2777 FoundSB = true;
2778 } else if (Opc == AMDGPU::SCHED_GROUP_BARRIER) {
2779 initSchedGroupBarrierPipelineStage(RIter: R);
2780 FoundSB = true;
2781 } else if (Opc == AMDGPU::IGLP_OPT) {
2782 if (!FoundSB && !FoundIGLP) {
2783 FoundIGLP = true;
2784 ShouldApplyIGLP = initIGLPOpt(SU&: *R);
2785 }
2786 }
2787 }
2788
2789 if (FoundSB || (FoundIGLP && ShouldApplyIGLP)) {
2790 PipelineSolver PS(SyncedSchedGroups, SyncedInstrs, DAG, IsBottomUp);
2791 // PipelineSolver performs the mutation by adding the edges it
2792 // determined as the best
2793 PS.solve();
2794 return;
2795 }
2796}
2797
2798void IGroupLPDAGMutation::addSchedBarrierEdges(SUnit &SchedBarrier) {
2799 MachineInstr &MI = *SchedBarrier.getInstr();
2800 assert(MI.getOpcode() == AMDGPU::SCHED_BARRIER);
2801 LLVM_DEBUG(dbgs() << "Building SchedGroup for SchedBarrier with Mask: "
2802 << MI.getOperand(0).getImm() << "\n");
2803 auto InvertedMask =
2804 invertSchedBarrierMask(Mask: (SchedGroupMask)MI.getOperand(i: 0).getImm());
2805 SchedGroup SG(InvertedMask, std::nullopt, DAG, TII);
2806
2807 for (SUnit &SU : DAG->SUnits)
2808 if (SG.canAddSU(SU))
2809 SG.add(SU);
2810
2811 // Preserve original instruction ordering relative to the SCHED_BARRIER.
2812 SG.link(
2813 SU&: SchedBarrier,
2814 P: (function_ref<bool(const SUnit *A, const SUnit *B)>)[](
2815 const SUnit *A, const SUnit *B) { return A->NodeNum > B->NodeNum; });
2816}
2817
2818SchedGroupMask
2819IGroupLPDAGMutation::invertSchedBarrierMask(SchedGroupMask Mask) const {
2820 // Invert mask and erase bits for types of instructions that are implied to be
2821 // allowed past the SCHED_BARRIER.
2822 SchedGroupMask InvertedMask = ~Mask;
2823
2824 static constexpr std::pair<SchedGroupMask, SchedGroupMask> ImpliedGroups[] = {
2825 {SchedGroupMask::ALU, SchedGroupMask::VALU | SchedGroupMask::SALU |
2826 SchedGroupMask::MFMA | SchedGroupMask::TRANS},
2827 {SchedGroupMask::VMEM, SchedGroupMask::VMEM_READ |
2828 SchedGroupMask::VMEM_WRITE |
2829 SchedGroupMask::LDSDMA},
2830 {SchedGroupMask::DS, SchedGroupMask::DS_READ | SchedGroupMask::DS_WRITE |
2831 SchedGroupMask::LDSDMA},
2832 };
2833
2834 for (auto [Aggregate, Members] : ImpliedGroups) {
2835 // Aggregate allowed past the barrier implies all its members are too.
2836 if ((InvertedMask & Aggregate) == SchedGroupMask::NONE)
2837 InvertedMask &= ~Members;
2838 // Any member allowed past the barrier implies the aggregate is too.
2839 else if ((InvertedMask & Members) != Members)
2840 InvertedMask &= ~Aggregate;
2841 }
2842
2843 LLVM_DEBUG(dbgs() << "After Inverting, SchedGroup Mask: " << (int)InvertedMask
2844 << "\n");
2845
2846 return InvertedMask;
2847}
2848
2849void IGroupLPDAGMutation::initSchedGroupBarrierPipelineStage(
2850 std::vector<SUnit>::reverse_iterator RIter) {
2851 MachineInstr &SGB = *RIter->getInstr();
2852 assert(SGB.getOpcode() == AMDGPU::SCHED_GROUP_BARRIER);
2853 int64_t SGMask = SGB.getOperand(i: 0).getImm();
2854 int32_t Size = static_cast<int32_t>(SGB.getOperand(i: 1).getImm());
2855 int32_t SyncID = static_cast<int32_t>(SGB.getOperand(i: 2).getImm());
2856
2857 Size++; // Make room for the SCHED_GROUP_BARRIER instruction
2858 auto &SG = SyncedSchedGroups[SyncID].emplace_back(Args: (SchedGroupMask)SGMask,
2859 Args&: Size, Args&: SyncID, Args&: DAG, Args&: TII);
2860 SG.add(SU&: *RIter);
2861 SG.findCandidateSUnits(Begin: RIter, End: SG.DAG->SUnits.rend(),
2862 SyncedInstrs&: SyncedInstrs[SG.getSyncID()]);
2863}
2864
2865bool IGroupLPDAGMutation::initIGLPOpt(SUnit &SU) {
2866 IGLPStrategyID StrategyID =
2867 (IGLPStrategyID)SU.getInstr()->getOperand(i: 0).getImm();
2868 auto S = createIGLPStrategy(ID: StrategyID, DAG, TII, IGLPOptMI: SU.getInstr());
2869 if (!S->shouldApplyStrategy(DAG, Phase))
2870 return false;
2871
2872 IsBottomUp = S->IsBottomUp;
2873 return S->applyIGLPStrategy(SyncedInstrs, SyncedSchedGroups, Phase);
2874}
2875
2876} // namespace
2877
2878/// \p Phase specifes whether or not this is a reentry into the
2879/// IGroupLPDAGMutation. Since there may be multiple scheduling passes on the
2880/// same scheduling region (e.g. pre and post-RA scheduling / multiple
2881/// scheduling "phases"), we can reenter this mutation framework more than once
2882/// for a given region.
2883std::unique_ptr<ScheduleDAGMutation>
2884llvm::createIGroupLPDAGMutation(AMDGPU::SchedulingPhase Phase) {
2885 return std::make_unique<IGroupLPDAGMutation>(args&: Phase);
2886}
2887