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