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