1 //===-- SIMachineScheduler.cpp - SI Scheduler Interface -------------------===//
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
10 /// SI Machine Scheduler interface
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "SIMachineScheduler.h"
15 #include "AMDGPU.h"
16 #include "SIInstrInfo.h"
17 #include "SIRegisterInfo.h"
18 #include "MCTargetDesc/AMDGPUMCTargetDesc.h"
19 #include "llvm/ADT/STLExtras.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/CodeGen/LiveInterval.h"
22 #include "llvm/CodeGen/LiveIntervals.h"
23 #include "llvm/CodeGen/MachineInstr.h"
24 #include "llvm/CodeGen/MachineRegisterInfo.h"
25 #include "llvm/CodeGen/MachineScheduler.h"
26 #include "llvm/CodeGen/RegisterPressure.h"
27 #include "llvm/CodeGen/SlotIndexes.h"
28 #include "llvm/CodeGen/TargetRegisterInfo.h"
29 #include "llvm/Support/Debug.h"
30 #include "llvm/Support/ErrorHandling.h"
31 #include "llvm/Support/raw_ostream.h"
32 #include <algorithm>
33 #include <cassert>
34 #include <map>
35 #include <set>
36 #include <utility>
37 #include <vector>
38 
39 using namespace llvm;
40 
41 #define DEBUG_TYPE "machine-scheduler"
42 
43 // This scheduler implements a different scheduling algorithm than
44 // GenericScheduler.
45 //
46 // There are several specific architecture behaviours that can't be modelled
47 // for GenericScheduler:
48 // . When accessing the result of an SGPR load instruction, you have to wait
49 // for all the SGPR load instructions before your current instruction to
50 // have finished.
51 // . When accessing the result of an VGPR load instruction, you have to wait
52 // for all the VGPR load instructions previous to the VGPR load instruction
53 // you are interested in to finish.
54 // . The less the register pressure, the best load latencies are hidden
55 //
56 // Moreover some specifities (like the fact a lot of instructions in the shader
57 // have few dependencies) makes the generic scheduler have some unpredictable
58 // behaviours. For example when register pressure becomes high, it can either
59 // manage to prevent register pressure from going too high, or it can
60 // increase register pressure even more than if it hadn't taken register
61 // pressure into account.
62 //
63 // Also some other bad behaviours are generated, like loading at the beginning
64 // of the shader a constant in VGPR you won't need until the end of the shader.
65 //
66 // The scheduling problem for SI can distinguish three main parts:
67 // . Hiding high latencies (texture sampling, etc)
68 // . Hiding low latencies (SGPR constant loading, etc)
69 // . Keeping register usage low for better latency hiding and general
70 //   performance
71 //
72 // Some other things can also affect performance, but are hard to predict
73 // (cache usage, the fact the HW can issue several instructions from different
74 // wavefronts if different types, etc)
75 //
76 // This scheduler tries to solve the scheduling problem by dividing it into
77 // simpler sub-problems. It divides the instructions into blocks, schedules
78 // locally inside the blocks where it takes care of low latencies, and then
79 // chooses the order of the blocks by taking care of high latencies.
80 // Dividing the instructions into blocks helps control keeping register
81 // usage low.
82 //
83 // First the instructions are put into blocks.
84 //   We want the blocks help control register usage and hide high latencies
85 //   later. To help control register usage, we typically want all local
86 //   computations, when for example you create a result that can be comsummed
87 //   right away, to be contained in a block. Block inputs and outputs would
88 //   typically be important results that are needed in several locations of
89 //   the shader. Since we do want blocks to help hide high latencies, we want
90 //   the instructions inside the block to have a minimal set of dependencies
91 //   on high latencies. It will make it easy to pick blocks to hide specific
92 //   high latencies.
93 //   The block creation algorithm is divided into several steps, and several
94 //   variants can be tried during the scheduling process.
95 //
96 // Second the order of the instructions inside the blocks is chosen.
97 //   At that step we do take into account only register usage and hiding
98 //   low latency instructions
99 //
100 // Third the block order is chosen, there we try to hide high latencies
101 // and keep register usage low.
102 //
103 // After the third step, a pass is done to improve the hiding of low
104 // latencies.
105 //
106 // Actually when talking about 'low latency' or 'high latency' it includes
107 // both the latency to get the cache (or global mem) data go to the register,
108 // and the bandwidth limitations.
109 // Increasing the number of active wavefronts helps hide the former, but it
110 // doesn't solve the latter, thus why even if wavefront count is high, we have
111 // to try have as many instructions hiding high latencies as possible.
112 // The OpenCL doc says for example latency of 400 cycles for a global mem access,
113 // which is hidden by 10 instructions if the wavefront count is 10.
114 
115 // Some figures taken from AMD docs:
116 // Both texture and constant L1 caches are 4-way associative with 64 bytes
117 // lines.
118 // Constant cache is shared with 4 CUs.
119 // For texture sampling, the address generation unit receives 4 texture
120 // addresses per cycle, thus we could expect texture sampling latency to be
121 // equivalent to 4 instructions in the very best case (a VGPR is 64 work items,
122 // instructions in a wavefront group are executed every 4 cycles),
123 // or 16 instructions if the other wavefronts associated to the 3 other VALUs
124 // of the CU do texture sampling too. (Don't take these figures too seriously,
125 // as I'm not 100% sure of the computation)
126 // Data exports should get similar latency.
127 // For constant loading, the cache is shader with 4 CUs.
128 // The doc says "a throughput of 16B/cycle for each of the 4 Compute Unit"
129 // I guess if the other CU don't read the cache, it can go up to 64B/cycle.
130 // It means a simple s_buffer_load should take one instruction to hide, as
131 // well as a s_buffer_loadx2 and potentially a s_buffer_loadx8 if on the same
132 // cache line.
133 //
134 // As of today the driver doesn't preload the constants in cache, thus the
135 // first loads get extra latency. The doc says global memory access can be
136 // 300-600 cycles. We do not specially take that into account when scheduling
137 // As we expect the driver to be able to preload the constants soon.
138 
139 // common code //
140 
141 #ifndef NDEBUG
142 
getReasonStr(SIScheduleCandReason Reason)143 static const char *getReasonStr(SIScheduleCandReason Reason) {
144   switch (Reason) {
145   case NoCand:         return "NOCAND";
146   case RegUsage:       return "REGUSAGE";
147   case Latency:        return "LATENCY";
148   case Successor:      return "SUCCESSOR";
149   case Depth:          return "DEPTH";
150   case NodeOrder:      return "ORDER";
151   }
152   llvm_unreachable("Unknown reason!");
153 }
154 
155 #endif
156 
157 namespace llvm {
158 namespace SISched {
tryLess(int TryVal,int CandVal,SISchedulerCandidate & TryCand,SISchedulerCandidate & Cand,SIScheduleCandReason Reason)159 static bool tryLess(int TryVal, int CandVal,
160                     SISchedulerCandidate &TryCand,
161                     SISchedulerCandidate &Cand,
162                     SIScheduleCandReason Reason) {
163   if (TryVal < CandVal) {
164     TryCand.Reason = Reason;
165     return true;
166   }
167   if (TryVal > CandVal) {
168     if (Cand.Reason > Reason)
169       Cand.Reason = Reason;
170     return true;
171   }
172   Cand.setRepeat(Reason);
173   return false;
174 }
175 
tryGreater(int TryVal,int CandVal,SISchedulerCandidate & TryCand,SISchedulerCandidate & Cand,SIScheduleCandReason Reason)176 static bool tryGreater(int TryVal, int CandVal,
177                        SISchedulerCandidate &TryCand,
178                        SISchedulerCandidate &Cand,
179                        SIScheduleCandReason Reason) {
180   if (TryVal > CandVal) {
181     TryCand.Reason = Reason;
182     return true;
183   }
184   if (TryVal < CandVal) {
185     if (Cand.Reason > Reason)
186       Cand.Reason = Reason;
187     return true;
188   }
189   Cand.setRepeat(Reason);
190   return false;
191 }
192 } // end namespace SISched
193 } // end namespace llvm
194 
195 // SIScheduleBlock //
196 
addUnit(SUnit * SU)197 void SIScheduleBlock::addUnit(SUnit *SU) {
198   NodeNum2Index[SU->NodeNum] = SUnits.size();
199   SUnits.push_back(SU);
200 }
201 
202 #ifndef NDEBUG
traceCandidate(const SISchedCandidate & Cand)203 void SIScheduleBlock::traceCandidate(const SISchedCandidate &Cand) {
204 
205   dbgs() << "  SU(" << Cand.SU->NodeNum << ") " << getReasonStr(Cand.Reason);
206   dbgs() << '\n';
207 }
208 #endif
209 
tryCandidateTopDown(SISchedCandidate & Cand,SISchedCandidate & TryCand)210 void SIScheduleBlock::tryCandidateTopDown(SISchedCandidate &Cand,
211                                           SISchedCandidate &TryCand) {
212   // Initialize the candidate if needed.
213   if (!Cand.isValid()) {
214     TryCand.Reason = NodeOrder;
215     return;
216   }
217 
218   if (Cand.SGPRUsage > 60 &&
219       SISched::tryLess(TryCand.SGPRUsage, Cand.SGPRUsage,
220                        TryCand, Cand, RegUsage))
221     return;
222 
223   // Schedule low latency instructions as top as possible.
224   // Order of priority is:
225   // . Low latency instructions which do not depend on other low latency
226   //   instructions we haven't waited for
227   // . Other instructions which do not depend on low latency instructions
228   //   we haven't waited for
229   // . Low latencies
230   // . All other instructions
231   // Goal is to get: low latency instructions - independent instructions
232   //     - (eventually some more low latency instructions)
233   //     - instructions that depend on the first low latency instructions.
234   // If in the block there is a lot of constant loads, the SGPR usage
235   // could go quite high, thus above the arbitrary limit of 60 will encourage
236   // use the already loaded constants (in order to release some SGPRs) before
237   // loading more.
238   if (SISched::tryLess(TryCand.HasLowLatencyNonWaitedParent,
239                        Cand.HasLowLatencyNonWaitedParent,
240                        TryCand, Cand, SIScheduleCandReason::Depth))
241     return;
242 
243   if (SISched::tryGreater(TryCand.IsLowLatency, Cand.IsLowLatency,
244                           TryCand, Cand, SIScheduleCandReason::Depth))
245     return;
246 
247   if (TryCand.IsLowLatency &&
248       SISched::tryLess(TryCand.LowLatencyOffset, Cand.LowLatencyOffset,
249                        TryCand, Cand, SIScheduleCandReason::Depth))
250     return;
251 
252   if (SISched::tryLess(TryCand.VGPRUsage, Cand.VGPRUsage,
253                        TryCand, Cand, RegUsage))
254     return;
255 
256   // Fall through to original instruction order.
257   if (TryCand.SU->NodeNum < Cand.SU->NodeNum) {
258     TryCand.Reason = NodeOrder;
259   }
260 }
261 
pickNode()262 SUnit* SIScheduleBlock::pickNode() {
263   SISchedCandidate TopCand;
264 
265   for (SUnit* SU : TopReadySUs) {
266     SISchedCandidate TryCand;
267     std::vector<unsigned> pressure;
268     std::vector<unsigned> MaxPressure;
269     // Predict register usage after this instruction.
270     TryCand.SU = SU;
271     TopRPTracker.getDownwardPressure(SU->getInstr(), pressure, MaxPressure);
272     TryCand.SGPRUsage = pressure[DAG->getSGPRSetID()];
273     TryCand.VGPRUsage = pressure[DAG->getVGPRSetID()];
274     TryCand.IsLowLatency = DAG->IsLowLatencySU[SU->NodeNum];
275     TryCand.LowLatencyOffset = DAG->LowLatencyOffset[SU->NodeNum];
276     TryCand.HasLowLatencyNonWaitedParent =
277       HasLowLatencyNonWaitedParent[NodeNum2Index[SU->NodeNum]];
278     tryCandidateTopDown(TopCand, TryCand);
279     if (TryCand.Reason != NoCand)
280       TopCand.setBest(TryCand);
281   }
282 
283   return TopCand.SU;
284 }
285 
286 
287 // Schedule something valid.
fastSchedule()288 void SIScheduleBlock::fastSchedule() {
289   TopReadySUs.clear();
290   if (Scheduled)
291     undoSchedule();
292 
293   for (SUnit* SU : SUnits) {
294     if (!SU->NumPredsLeft)
295       TopReadySUs.push_back(SU);
296   }
297 
298   while (!TopReadySUs.empty()) {
299     SUnit *SU = TopReadySUs[0];
300     ScheduledSUnits.push_back(SU);
301     nodeScheduled(SU);
302   }
303 
304   Scheduled = true;
305 }
306 
307 // Returns if the register was set between first and last.
isDefBetween(unsigned Reg,SlotIndex First,SlotIndex Last,const MachineRegisterInfo * MRI,const LiveIntervals * LIS)308 static bool isDefBetween(unsigned Reg,
309                            SlotIndex First, SlotIndex Last,
310                            const MachineRegisterInfo *MRI,
311                            const LiveIntervals *LIS) {
312   for (MachineRegisterInfo::def_instr_iterator
313        UI = MRI->def_instr_begin(Reg),
314        UE = MRI->def_instr_end(); UI != UE; ++UI) {
315     const MachineInstr* MI = &*UI;
316     if (MI->isDebugValue())
317       continue;
318     SlotIndex InstSlot = LIS->getInstructionIndex(*MI).getRegSlot();
319     if (InstSlot >= First && InstSlot <= Last)
320       return true;
321   }
322   return false;
323 }
324 
initRegPressure(MachineBasicBlock::iterator BeginBlock,MachineBasicBlock::iterator EndBlock)325 void SIScheduleBlock::initRegPressure(MachineBasicBlock::iterator BeginBlock,
326                                       MachineBasicBlock::iterator EndBlock) {
327   IntervalPressure Pressure, BotPressure;
328   RegPressureTracker RPTracker(Pressure), BotRPTracker(BotPressure);
329   LiveIntervals *LIS = DAG->getLIS();
330   MachineRegisterInfo *MRI = DAG->getMRI();
331   DAG->initRPTracker(TopRPTracker);
332   DAG->initRPTracker(BotRPTracker);
333   DAG->initRPTracker(RPTracker);
334 
335   // Goes though all SU. RPTracker captures what had to be alive for the SUs
336   // to execute, and what is still alive at the end.
337   for (SUnit* SU : ScheduledSUnits) {
338     RPTracker.setPos(SU->getInstr());
339     RPTracker.advance();
340   }
341 
342   // Close the RPTracker to finalize live ins/outs.
343   RPTracker.closeRegion();
344 
345   // Initialize the live ins and live outs.
346   TopRPTracker.addLiveRegs(RPTracker.getPressure().LiveInRegs);
347   BotRPTracker.addLiveRegs(RPTracker.getPressure().LiveOutRegs);
348 
349   // Do not Track Physical Registers, because it messes up.
350   for (const auto &RegMaskPair : RPTracker.getPressure().LiveInRegs) {
351     if (Register::isVirtualRegister(RegMaskPair.RegUnit))
352       LiveInRegs.insert(RegMaskPair.RegUnit);
353   }
354   LiveOutRegs.clear();
355   // There is several possibilities to distinguish:
356   // 1) Reg is not input to any instruction in the block, but is output of one
357   // 2) 1) + read in the block and not needed after it
358   // 3) 1) + read in the block but needed in another block
359   // 4) Reg is input of an instruction but another block will read it too
360   // 5) Reg is input of an instruction and then rewritten in the block.
361   //    result is not read in the block (implies used in another block)
362   // 6) Reg is input of an instruction and then rewritten in the block.
363   //    result is read in the block and not needed in another block
364   // 7) Reg is input of an instruction and then rewritten in the block.
365   //    result is read in the block but also needed in another block
366   // LiveInRegs will contains all the regs in situation 4, 5, 6, 7
367   // We want LiveOutRegs to contain only Regs whose content will be read after
368   // in another block, and whose content was written in the current block,
369   // that is we want it to get 1, 3, 5, 7
370   // Since we made the MIs of a block to be packed all together before
371   // scheduling, then the LiveIntervals were correct, and the RPTracker was
372   // able to correctly handle 5 vs 6, 2 vs 3.
373   // (Note: This is not sufficient for RPTracker to not do mistakes for case 4)
374   // The RPTracker's LiveOutRegs has 1, 3, (some correct or incorrect)4, 5, 7
375   // Comparing to LiveInRegs is not sufficient to differenciate 4 vs 5, 7
376   // The use of findDefBetween removes the case 4.
377   for (const auto &RegMaskPair : RPTracker.getPressure().LiveOutRegs) {
378     unsigned Reg = RegMaskPair.RegUnit;
379     if (Register::isVirtualRegister(Reg) &&
380         isDefBetween(Reg, LIS->getInstructionIndex(*BeginBlock).getRegSlot(),
381                      LIS->getInstructionIndex(*EndBlock).getRegSlot(), MRI,
382                      LIS)) {
383       LiveOutRegs.insert(Reg);
384     }
385   }
386 
387   // Pressure = sum_alive_registers register size
388   // Internally llvm will represent some registers as big 128 bits registers
389   // for example, but they actually correspond to 4 actual 32 bits registers.
390   // Thus Pressure is not equal to num_alive_registers * constant.
391   LiveInPressure = TopPressure.MaxSetPressure;
392   LiveOutPressure = BotPressure.MaxSetPressure;
393 
394   // Prepares TopRPTracker for top down scheduling.
395   TopRPTracker.closeTop();
396 }
397 
schedule(MachineBasicBlock::iterator BeginBlock,MachineBasicBlock::iterator EndBlock)398 void SIScheduleBlock::schedule(MachineBasicBlock::iterator BeginBlock,
399                                MachineBasicBlock::iterator EndBlock) {
400   if (!Scheduled)
401     fastSchedule();
402 
403   // PreScheduling phase to set LiveIn and LiveOut.
404   initRegPressure(BeginBlock, EndBlock);
405   undoSchedule();
406 
407   // Schedule for real now.
408 
409   TopReadySUs.clear();
410 
411   for (SUnit* SU : SUnits) {
412     if (!SU->NumPredsLeft)
413       TopReadySUs.push_back(SU);
414   }
415 
416   while (!TopReadySUs.empty()) {
417     SUnit *SU = pickNode();
418     ScheduledSUnits.push_back(SU);
419     TopRPTracker.setPos(SU->getInstr());
420     TopRPTracker.advance();
421     nodeScheduled(SU);
422   }
423 
424   // TODO: compute InternalAdditionnalPressure.
425   InternalAdditionnalPressure.resize(TopPressure.MaxSetPressure.size());
426 
427   // Check everything is right.
428 #ifndef NDEBUG
429   assert(SUnits.size() == ScheduledSUnits.size() &&
430             TopReadySUs.empty());
431   for (SUnit* SU : SUnits) {
432     assert(SU->isScheduled &&
433               SU->NumPredsLeft == 0);
434   }
435 #endif
436 
437   Scheduled = true;
438 }
439 
undoSchedule()440 void SIScheduleBlock::undoSchedule() {
441   for (SUnit* SU : SUnits) {
442     SU->isScheduled = false;
443     for (SDep& Succ : SU->Succs) {
444       if (BC->isSUInBlock(Succ.getSUnit(), ID))
445         undoReleaseSucc(SU, &Succ);
446     }
447   }
448   HasLowLatencyNonWaitedParent.assign(SUnits.size(), 0);
449   ScheduledSUnits.clear();
450   Scheduled = false;
451 }
452 
undoReleaseSucc(SUnit * SU,SDep * SuccEdge)453 void SIScheduleBlock::undoReleaseSucc(SUnit *SU, SDep *SuccEdge) {
454   SUnit *SuccSU = SuccEdge->getSUnit();
455 
456   if (SuccEdge->isWeak()) {
457     ++SuccSU->WeakPredsLeft;
458     return;
459   }
460   ++SuccSU->NumPredsLeft;
461 }
462 
releaseSucc(SUnit * SU,SDep * SuccEdge)463 void SIScheduleBlock::releaseSucc(SUnit *SU, SDep *SuccEdge) {
464   SUnit *SuccSU = SuccEdge->getSUnit();
465 
466   if (SuccEdge->isWeak()) {
467     --SuccSU->WeakPredsLeft;
468     return;
469   }
470 #ifndef NDEBUG
471   if (SuccSU->NumPredsLeft == 0) {
472     dbgs() << "*** Scheduling failed! ***\n";
473     DAG->dumpNode(*SuccSU);
474     dbgs() << " has been released too many times!\n";
475     llvm_unreachable(nullptr);
476   }
477 #endif
478 
479   --SuccSU->NumPredsLeft;
480 }
481 
482 /// Release Successors of the SU that are in the block or not.
releaseSuccessors(SUnit * SU,bool InOrOutBlock)483 void SIScheduleBlock::releaseSuccessors(SUnit *SU, bool InOrOutBlock) {
484   for (SDep& Succ : SU->Succs) {
485     SUnit *SuccSU = Succ.getSUnit();
486 
487     if (SuccSU->NodeNum >= DAG->SUnits.size())
488         continue;
489 
490     if (BC->isSUInBlock(SuccSU, ID) != InOrOutBlock)
491       continue;
492 
493     releaseSucc(SU, &Succ);
494     if (SuccSU->NumPredsLeft == 0 && InOrOutBlock)
495       TopReadySUs.push_back(SuccSU);
496   }
497 }
498 
nodeScheduled(SUnit * SU)499 void SIScheduleBlock::nodeScheduled(SUnit *SU) {
500   // Is in TopReadySUs
501   assert (!SU->NumPredsLeft);
502   std::vector<SUnit *>::iterator I = llvm::find(TopReadySUs, SU);
503   if (I == TopReadySUs.end()) {
504     dbgs() << "Data Structure Bug in SI Scheduler\n";
505     llvm_unreachable(nullptr);
506   }
507   TopReadySUs.erase(I);
508 
509   releaseSuccessors(SU, true);
510   // Scheduling this node will trigger a wait,
511   // thus propagate to other instructions that they do not need to wait either.
512   if (HasLowLatencyNonWaitedParent[NodeNum2Index[SU->NodeNum]])
513     HasLowLatencyNonWaitedParent.assign(SUnits.size(), 0);
514 
515   if (DAG->IsLowLatencySU[SU->NodeNum]) {
516      for (SDep& Succ : SU->Succs) {
517       std::map<unsigned, unsigned>::iterator I =
518         NodeNum2Index.find(Succ.getSUnit()->NodeNum);
519       if (I != NodeNum2Index.end())
520         HasLowLatencyNonWaitedParent[I->second] = 1;
521     }
522   }
523   SU->isScheduled = true;
524 }
525 
finalizeUnits()526 void SIScheduleBlock::finalizeUnits() {
527   // We remove links from outside blocks to enable scheduling inside the block.
528   for (SUnit* SU : SUnits) {
529     releaseSuccessors(SU, false);
530     if (DAG->IsHighLatencySU[SU->NodeNum])
531       HighLatencyBlock = true;
532   }
533   HasLowLatencyNonWaitedParent.resize(SUnits.size(), 0);
534 }
535 
536 // we maintain ascending order of IDs
addPred(SIScheduleBlock * Pred)537 void SIScheduleBlock::addPred(SIScheduleBlock *Pred) {
538   unsigned PredID = Pred->getID();
539 
540   // Check if not already predecessor.
541   for (SIScheduleBlock* P : Preds) {
542     if (PredID == P->getID())
543       return;
544   }
545   Preds.push_back(Pred);
546 
547   assert(none_of(Succs,
548                  [=](std::pair<SIScheduleBlock*,
549                      SIScheduleBlockLinkKind> S) {
550                    return PredID == S.first->getID();
551                     }) &&
552          "Loop in the Block Graph!");
553 }
554 
addSucc(SIScheduleBlock * Succ,SIScheduleBlockLinkKind Kind)555 void SIScheduleBlock::addSucc(SIScheduleBlock *Succ,
556                               SIScheduleBlockLinkKind Kind) {
557   unsigned SuccID = Succ->getID();
558 
559   // Check if not already predecessor.
560   for (std::pair<SIScheduleBlock*, SIScheduleBlockLinkKind> &S : Succs) {
561     if (SuccID == S.first->getID()) {
562       if (S.second == SIScheduleBlockLinkKind::NoData &&
563           Kind == SIScheduleBlockLinkKind::Data)
564         S.second = Kind;
565       return;
566     }
567   }
568   if (Succ->isHighLatencyBlock())
569     ++NumHighLatencySuccessors;
570   Succs.push_back(std::make_pair(Succ, Kind));
571 
572   assert(none_of(Preds,
573                  [=](SIScheduleBlock *P) { return SuccID == P->getID(); }) &&
574          "Loop in the Block Graph!");
575 }
576 
577 #ifndef NDEBUG
printDebug(bool full)578 void SIScheduleBlock::printDebug(bool full) {
579   dbgs() << "Block (" << ID << ")\n";
580   if (!full)
581     return;
582 
583   dbgs() << "\nContains High Latency Instruction: "
584          << HighLatencyBlock << '\n';
585   dbgs() << "\nDepends On:\n";
586   for (SIScheduleBlock* P : Preds) {
587     P->printDebug(false);
588   }
589 
590   dbgs() << "\nSuccessors:\n";
591   for (std::pair<SIScheduleBlock*, SIScheduleBlockLinkKind> S : Succs) {
592     if (S.second == SIScheduleBlockLinkKind::Data)
593       dbgs() << "(Data Dep) ";
594     S.first->printDebug(false);
595   }
596 
597   if (Scheduled) {
598     dbgs() << "LiveInPressure " << LiveInPressure[DAG->getSGPRSetID()] << ' '
599            << LiveInPressure[DAG->getVGPRSetID()] << '\n';
600     dbgs() << "LiveOutPressure " << LiveOutPressure[DAG->getSGPRSetID()] << ' '
601            << LiveOutPressure[DAG->getVGPRSetID()] << "\n\n";
602     dbgs() << "LiveIns:\n";
603     for (unsigned Reg : LiveInRegs)
604       dbgs() << printVRegOrUnit(Reg, DAG->getTRI()) << ' ';
605 
606     dbgs() << "\nLiveOuts:\n";
607     for (unsigned Reg : LiveOutRegs)
608       dbgs() << printVRegOrUnit(Reg, DAG->getTRI()) << ' ';
609   }
610 
611   dbgs() << "\nInstructions:\n";
612   for (const SUnit* SU : SUnits)
613       DAG->dumpNode(*SU);
614 
615   dbgs() << "///////////////////////\n";
616 }
617 #endif
618 
619 // SIScheduleBlockCreator //
620 
SIScheduleBlockCreator(SIScheduleDAGMI * DAG)621 SIScheduleBlockCreator::SIScheduleBlockCreator(SIScheduleDAGMI *DAG)
622     : DAG(DAG) {}
623 
624 SIScheduleBlocks
getBlocks(SISchedulerBlockCreatorVariant BlockVariant)625 SIScheduleBlockCreator::getBlocks(SISchedulerBlockCreatorVariant BlockVariant) {
626   std::map<SISchedulerBlockCreatorVariant, SIScheduleBlocks>::iterator B =
627     Blocks.find(BlockVariant);
628   if (B == Blocks.end()) {
629     SIScheduleBlocks Res;
630     createBlocksForVariant(BlockVariant);
631     topologicalSort();
632     scheduleInsideBlocks();
633     fillStats();
634     Res.Blocks = CurrentBlocks;
635     Res.TopDownIndex2Block = TopDownIndex2Block;
636     Res.TopDownBlock2Index = TopDownBlock2Index;
637     Blocks[BlockVariant] = Res;
638     return Res;
639   } else {
640     return B->second;
641   }
642 }
643 
isSUInBlock(SUnit * SU,unsigned ID)644 bool SIScheduleBlockCreator::isSUInBlock(SUnit *SU, unsigned ID) {
645   if (SU->NodeNum >= DAG->SUnits.size())
646     return false;
647   return CurrentBlocks[Node2CurrentBlock[SU->NodeNum]]->getID() == ID;
648 }
649 
colorHighLatenciesAlone()650 void SIScheduleBlockCreator::colorHighLatenciesAlone() {
651   unsigned DAGSize = DAG->SUnits.size();
652 
653   for (unsigned i = 0, e = DAGSize; i != e; ++i) {
654     SUnit *SU = &DAG->SUnits[i];
655     if (DAG->IsHighLatencySU[SU->NodeNum]) {
656       CurrentColoring[SU->NodeNum] = NextReservedID++;
657     }
658   }
659 }
660 
661 static bool
hasDataDependencyPred(const SUnit & SU,const SUnit & FromSU)662 hasDataDependencyPred(const SUnit &SU, const SUnit &FromSU) {
663   for (const auto &PredDep : SU.Preds) {
664     if (PredDep.getSUnit() == &FromSU &&
665         PredDep.getKind() == llvm::SDep::Data)
666       return true;
667   }
668   return false;
669 }
670 
colorHighLatenciesGroups()671 void SIScheduleBlockCreator::colorHighLatenciesGroups() {
672   unsigned DAGSize = DAG->SUnits.size();
673   unsigned NumHighLatencies = 0;
674   unsigned GroupSize;
675   int Color = NextReservedID;
676   unsigned Count = 0;
677   std::set<unsigned> FormingGroup;
678 
679   for (unsigned i = 0, e = DAGSize; i != e; ++i) {
680     SUnit *SU = &DAG->SUnits[i];
681     if (DAG->IsHighLatencySU[SU->NodeNum])
682       ++NumHighLatencies;
683   }
684 
685   if (NumHighLatencies == 0)
686     return;
687 
688   if (NumHighLatencies <= 6)
689     GroupSize = 2;
690   else if (NumHighLatencies <= 12)
691     GroupSize = 3;
692   else
693     GroupSize = 4;
694 
695   for (unsigned SUNum : DAG->TopDownIndex2SU) {
696     const SUnit &SU = DAG->SUnits[SUNum];
697     if (DAG->IsHighLatencySU[SU.NodeNum]) {
698       unsigned CompatibleGroup = true;
699       int ProposedColor = Color;
700       std::vector<int> AdditionalElements;
701 
702       // We don't want to put in the same block
703       // two high latency instructions that depend
704       // on each other.
705       // One way would be to check canAddEdge
706       // in both directions, but that currently is not
707       // enough because there the high latency order is
708       // enforced (via links).
709       // Instead, look at the dependencies between the
710       // high latency instructions and deduce if it is
711       // a data dependency or not.
712       for (unsigned j : FormingGroup) {
713         bool HasSubGraph;
714         std::vector<int> SubGraph;
715         // By construction (topological order), if SU and
716         // DAG->SUnits[j] are linked, DAG->SUnits[j] is neccessary
717         // in the parent graph of SU.
718 #ifndef NDEBUG
719         SubGraph = DAG->GetTopo()->GetSubGraph(SU, DAG->SUnits[j],
720                                                HasSubGraph);
721         assert(!HasSubGraph);
722 #endif
723         SubGraph = DAG->GetTopo()->GetSubGraph(DAG->SUnits[j], SU,
724                                                HasSubGraph);
725         if (!HasSubGraph)
726           continue; // No dependencies between each other
727         else if (SubGraph.size() > 5) {
728           // Too many elements would be required to be added to the block.
729           CompatibleGroup = false;
730           break;
731         }
732         else {
733           // Check the type of dependency
734           for (unsigned k : SubGraph) {
735             // If in the path to join the two instructions,
736             // there is another high latency instruction,
737             // or instructions colored for another block
738             // abort the merge.
739             if (DAG->IsHighLatencySU[k] ||
740                 (CurrentColoring[k] != ProposedColor &&
741                  CurrentColoring[k] != 0)) {
742               CompatibleGroup = false;
743               break;
744             }
745             // If one of the SU in the subgraph depends on the result of SU j,
746             // there'll be a data dependency.
747             if (hasDataDependencyPred(DAG->SUnits[k], DAG->SUnits[j])) {
748               CompatibleGroup = false;
749               break;
750             }
751           }
752           if (!CompatibleGroup)
753             break;
754           // Same check for the SU
755           if (hasDataDependencyPred(SU, DAG->SUnits[j])) {
756             CompatibleGroup = false;
757             break;
758           }
759           // Add all the required instructions to the block
760           // These cannot live in another block (because they
761           // depend (order dependency) on one of the
762           // instruction in the block, and are required for the
763           // high latency instruction we add.
764           AdditionalElements.insert(AdditionalElements.end(),
765                                     SubGraph.begin(), SubGraph.end());
766         }
767       }
768       if (CompatibleGroup) {
769         FormingGroup.insert(SU.NodeNum);
770         for (unsigned j : AdditionalElements)
771           CurrentColoring[j] = ProposedColor;
772         CurrentColoring[SU.NodeNum] = ProposedColor;
773         ++Count;
774       }
775       // Found one incompatible instruction,
776       // or has filled a big enough group.
777       // -> start a new one.
778       if (!CompatibleGroup) {
779         FormingGroup.clear();
780         Color = ++NextReservedID;
781         ProposedColor = Color;
782         FormingGroup.insert(SU.NodeNum);
783         CurrentColoring[SU.NodeNum] = ProposedColor;
784         Count = 0;
785       } else if (Count == GroupSize) {
786         FormingGroup.clear();
787         Color = ++NextReservedID;
788         ProposedColor = Color;
789         Count = 0;
790       }
791     }
792   }
793 }
794 
colorComputeReservedDependencies()795 void SIScheduleBlockCreator::colorComputeReservedDependencies() {
796   unsigned DAGSize = DAG->SUnits.size();
797   std::map<std::set<unsigned>, unsigned> ColorCombinations;
798 
799   CurrentTopDownReservedDependencyColoring.clear();
800   CurrentBottomUpReservedDependencyColoring.clear();
801 
802   CurrentTopDownReservedDependencyColoring.resize(DAGSize, 0);
803   CurrentBottomUpReservedDependencyColoring.resize(DAGSize, 0);
804 
805   // Traverse TopDown, and give different colors to SUs depending
806   // on which combination of High Latencies they depend on.
807 
808   for (unsigned SUNum : DAG->TopDownIndex2SU) {
809     SUnit *SU = &DAG->SUnits[SUNum];
810     std::set<unsigned> SUColors;
811 
812     // Already given.
813     if (CurrentColoring[SU->NodeNum]) {
814       CurrentTopDownReservedDependencyColoring[SU->NodeNum] =
815         CurrentColoring[SU->NodeNum];
816       continue;
817     }
818 
819    for (SDep& PredDep : SU->Preds) {
820       SUnit *Pred = PredDep.getSUnit();
821       if (PredDep.isWeak() || Pred->NodeNum >= DAGSize)
822         continue;
823       if (CurrentTopDownReservedDependencyColoring[Pred->NodeNum] > 0)
824         SUColors.insert(CurrentTopDownReservedDependencyColoring[Pred->NodeNum]);
825     }
826     // Color 0 by default.
827     if (SUColors.empty())
828       continue;
829     // Same color than parents.
830     if (SUColors.size() == 1 && *SUColors.begin() > DAGSize)
831       CurrentTopDownReservedDependencyColoring[SU->NodeNum] =
832         *SUColors.begin();
833     else {
834       std::map<std::set<unsigned>, unsigned>::iterator Pos =
835         ColorCombinations.find(SUColors);
836       if (Pos != ColorCombinations.end()) {
837           CurrentTopDownReservedDependencyColoring[SU->NodeNum] = Pos->second;
838       } else {
839         CurrentTopDownReservedDependencyColoring[SU->NodeNum] =
840           NextNonReservedID;
841         ColorCombinations[SUColors] = NextNonReservedID++;
842       }
843     }
844   }
845 
846   ColorCombinations.clear();
847 
848   // Same as before, but BottomUp.
849 
850   for (unsigned SUNum : DAG->BottomUpIndex2SU) {
851     SUnit *SU = &DAG->SUnits[SUNum];
852     std::set<unsigned> SUColors;
853 
854     // Already given.
855     if (CurrentColoring[SU->NodeNum]) {
856       CurrentBottomUpReservedDependencyColoring[SU->NodeNum] =
857         CurrentColoring[SU->NodeNum];
858       continue;
859     }
860 
861     for (SDep& SuccDep : SU->Succs) {
862       SUnit *Succ = SuccDep.getSUnit();
863       if (SuccDep.isWeak() || Succ->NodeNum >= DAGSize)
864         continue;
865       if (CurrentBottomUpReservedDependencyColoring[Succ->NodeNum] > 0)
866         SUColors.insert(CurrentBottomUpReservedDependencyColoring[Succ->NodeNum]);
867     }
868     // Keep color 0.
869     if (SUColors.empty())
870       continue;
871     // Same color than parents.
872     if (SUColors.size() == 1 && *SUColors.begin() > DAGSize)
873       CurrentBottomUpReservedDependencyColoring[SU->NodeNum] =
874         *SUColors.begin();
875     else {
876       std::map<std::set<unsigned>, unsigned>::iterator Pos =
877         ColorCombinations.find(SUColors);
878       if (Pos != ColorCombinations.end()) {
879         CurrentBottomUpReservedDependencyColoring[SU->NodeNum] = Pos->second;
880       } else {
881         CurrentBottomUpReservedDependencyColoring[SU->NodeNum] =
882           NextNonReservedID;
883         ColorCombinations[SUColors] = NextNonReservedID++;
884       }
885     }
886   }
887 }
888 
colorAccordingToReservedDependencies()889 void SIScheduleBlockCreator::colorAccordingToReservedDependencies() {
890   unsigned DAGSize = DAG->SUnits.size();
891   std::map<std::pair<unsigned, unsigned>, unsigned> ColorCombinations;
892 
893   // Every combination of colors given by the top down
894   // and bottom up Reserved node dependency
895 
896   for (unsigned i = 0, e = DAGSize; i != e; ++i) {
897     SUnit *SU = &DAG->SUnits[i];
898     std::pair<unsigned, unsigned> SUColors;
899 
900     // High latency instructions: already given.
901     if (CurrentColoring[SU->NodeNum])
902       continue;
903 
904     SUColors.first = CurrentTopDownReservedDependencyColoring[SU->NodeNum];
905     SUColors.second = CurrentBottomUpReservedDependencyColoring[SU->NodeNum];
906 
907     std::map<std::pair<unsigned, unsigned>, unsigned>::iterator Pos =
908       ColorCombinations.find(SUColors);
909     if (Pos != ColorCombinations.end()) {
910       CurrentColoring[SU->NodeNum] = Pos->second;
911     } else {
912       CurrentColoring[SU->NodeNum] = NextNonReservedID;
913       ColorCombinations[SUColors] = NextNonReservedID++;
914     }
915   }
916 }
917 
colorEndsAccordingToDependencies()918 void SIScheduleBlockCreator::colorEndsAccordingToDependencies() {
919   unsigned DAGSize = DAG->SUnits.size();
920   std::vector<int> PendingColoring = CurrentColoring;
921 
922   assert(DAGSize >= 1 &&
923          CurrentBottomUpReservedDependencyColoring.size() == DAGSize &&
924          CurrentTopDownReservedDependencyColoring.size() == DAGSize);
925   // If there is no reserved block at all, do nothing. We don't want
926   // everything in one block.
927   if (*std::max_element(CurrentBottomUpReservedDependencyColoring.begin(),
928                         CurrentBottomUpReservedDependencyColoring.end()) == 0 &&
929       *std::max_element(CurrentTopDownReservedDependencyColoring.begin(),
930                         CurrentTopDownReservedDependencyColoring.end()) == 0)
931     return;
932 
933   for (unsigned SUNum : DAG->BottomUpIndex2SU) {
934     SUnit *SU = &DAG->SUnits[SUNum];
935     std::set<unsigned> SUColors;
936     std::set<unsigned> SUColorsPending;
937 
938     if (CurrentColoring[SU->NodeNum] <= (int)DAGSize)
939       continue;
940 
941     if (CurrentBottomUpReservedDependencyColoring[SU->NodeNum] > 0 ||
942         CurrentTopDownReservedDependencyColoring[SU->NodeNum] > 0)
943       continue;
944 
945     for (SDep& SuccDep : SU->Succs) {
946       SUnit *Succ = SuccDep.getSUnit();
947       if (SuccDep.isWeak() || Succ->NodeNum >= DAGSize)
948         continue;
949       if (CurrentBottomUpReservedDependencyColoring[Succ->NodeNum] > 0 ||
950           CurrentTopDownReservedDependencyColoring[Succ->NodeNum] > 0)
951         SUColors.insert(CurrentColoring[Succ->NodeNum]);
952       SUColorsPending.insert(PendingColoring[Succ->NodeNum]);
953     }
954     // If there is only one child/parent block, and that block
955     // is not among the ones we are removing in this path, then
956     // merge the instruction to that block
957     if (SUColors.size() == 1 && SUColorsPending.size() == 1)
958       PendingColoring[SU->NodeNum] = *SUColors.begin();
959     else // TODO: Attribute new colors depending on color
960          // combination of children.
961       PendingColoring[SU->NodeNum] = NextNonReservedID++;
962   }
963   CurrentColoring = PendingColoring;
964 }
965 
966 
colorForceConsecutiveOrderInGroup()967 void SIScheduleBlockCreator::colorForceConsecutiveOrderInGroup() {
968   unsigned DAGSize = DAG->SUnits.size();
969   unsigned PreviousColor;
970   std::set<unsigned> SeenColors;
971 
972   if (DAGSize <= 1)
973     return;
974 
975   PreviousColor = CurrentColoring[0];
976 
977   for (unsigned i = 1, e = DAGSize; i != e; ++i) {
978     SUnit *SU = &DAG->SUnits[i];
979     unsigned CurrentColor = CurrentColoring[i];
980     unsigned PreviousColorSave = PreviousColor;
981     assert(i == SU->NodeNum);
982 
983     if (CurrentColor != PreviousColor)
984       SeenColors.insert(PreviousColor);
985     PreviousColor = CurrentColor;
986 
987     if (CurrentColoring[SU->NodeNum] <= (int)DAGSize)
988       continue;
989 
990     if (SeenColors.find(CurrentColor) == SeenColors.end())
991       continue;
992 
993     if (PreviousColorSave != CurrentColor)
994       CurrentColoring[i] = NextNonReservedID++;
995     else
996       CurrentColoring[i] = CurrentColoring[i-1];
997   }
998 }
999 
colorMergeConstantLoadsNextGroup()1000 void SIScheduleBlockCreator::colorMergeConstantLoadsNextGroup() {
1001   unsigned DAGSize = DAG->SUnits.size();
1002 
1003   for (unsigned SUNum : DAG->BottomUpIndex2SU) {
1004     SUnit *SU = &DAG->SUnits[SUNum];
1005     std::set<unsigned> SUColors;
1006 
1007     if (CurrentColoring[SU->NodeNum] <= (int)DAGSize)
1008       continue;
1009 
1010     // No predecessor: Vgpr constant loading.
1011     // Low latency instructions usually have a predecessor (the address)
1012     if (SU->Preds.size() > 0 && !DAG->IsLowLatencySU[SU->NodeNum])
1013       continue;
1014 
1015     for (SDep& SuccDep : SU->Succs) {
1016       SUnit *Succ = SuccDep.getSUnit();
1017       if (SuccDep.isWeak() || Succ->NodeNum >= DAGSize)
1018         continue;
1019       SUColors.insert(CurrentColoring[Succ->NodeNum]);
1020     }
1021     if (SUColors.size() == 1)
1022       CurrentColoring[SU->NodeNum] = *SUColors.begin();
1023   }
1024 }
1025 
colorMergeIfPossibleNextGroup()1026 void SIScheduleBlockCreator::colorMergeIfPossibleNextGroup() {
1027   unsigned DAGSize = DAG->SUnits.size();
1028 
1029   for (unsigned SUNum : DAG->BottomUpIndex2SU) {
1030     SUnit *SU = &DAG->SUnits[SUNum];
1031     std::set<unsigned> SUColors;
1032 
1033     if (CurrentColoring[SU->NodeNum] <= (int)DAGSize)
1034       continue;
1035 
1036     for (SDep& SuccDep : SU->Succs) {
1037        SUnit *Succ = SuccDep.getSUnit();
1038       if (SuccDep.isWeak() || Succ->NodeNum >= DAGSize)
1039         continue;
1040       SUColors.insert(CurrentColoring[Succ->NodeNum]);
1041     }
1042     if (SUColors.size() == 1)
1043       CurrentColoring[SU->NodeNum] = *SUColors.begin();
1044   }
1045 }
1046 
colorMergeIfPossibleNextGroupOnlyForReserved()1047 void SIScheduleBlockCreator::colorMergeIfPossibleNextGroupOnlyForReserved() {
1048   unsigned DAGSize = DAG->SUnits.size();
1049 
1050   for (unsigned SUNum : DAG->BottomUpIndex2SU) {
1051     SUnit *SU = &DAG->SUnits[SUNum];
1052     std::set<unsigned> SUColors;
1053 
1054     if (CurrentColoring[SU->NodeNum] <= (int)DAGSize)
1055       continue;
1056 
1057     for (SDep& SuccDep : SU->Succs) {
1058        SUnit *Succ = SuccDep.getSUnit();
1059       if (SuccDep.isWeak() || Succ->NodeNum >= DAGSize)
1060         continue;
1061       SUColors.insert(CurrentColoring[Succ->NodeNum]);
1062     }
1063     if (SUColors.size() == 1 && *SUColors.begin() <= DAGSize)
1064       CurrentColoring[SU->NodeNum] = *SUColors.begin();
1065   }
1066 }
1067 
colorMergeIfPossibleSmallGroupsToNextGroup()1068 void SIScheduleBlockCreator::colorMergeIfPossibleSmallGroupsToNextGroup() {
1069   unsigned DAGSize = DAG->SUnits.size();
1070   std::map<unsigned, unsigned> ColorCount;
1071 
1072   for (unsigned SUNum : DAG->BottomUpIndex2SU) {
1073     SUnit *SU = &DAG->SUnits[SUNum];
1074     unsigned color = CurrentColoring[SU->NodeNum];
1075      ++ColorCount[color];
1076   }
1077 
1078   for (unsigned SUNum : DAG->BottomUpIndex2SU) {
1079     SUnit *SU = &DAG->SUnits[SUNum];
1080     unsigned color = CurrentColoring[SU->NodeNum];
1081     std::set<unsigned> SUColors;
1082 
1083     if (CurrentColoring[SU->NodeNum] <= (int)DAGSize)
1084       continue;
1085 
1086     if (ColorCount[color] > 1)
1087       continue;
1088 
1089     for (SDep& SuccDep : SU->Succs) {
1090        SUnit *Succ = SuccDep.getSUnit();
1091       if (SuccDep.isWeak() || Succ->NodeNum >= DAGSize)
1092         continue;
1093       SUColors.insert(CurrentColoring[Succ->NodeNum]);
1094     }
1095     if (SUColors.size() == 1 && *SUColors.begin() != color) {
1096       --ColorCount[color];
1097       CurrentColoring[SU->NodeNum] = *SUColors.begin();
1098       ++ColorCount[*SUColors.begin()];
1099     }
1100   }
1101 }
1102 
cutHugeBlocks()1103 void SIScheduleBlockCreator::cutHugeBlocks() {
1104   // TODO
1105 }
1106 
regroupNoUserInstructions()1107 void SIScheduleBlockCreator::regroupNoUserInstructions() {
1108   unsigned DAGSize = DAG->SUnits.size();
1109   int GroupID = NextNonReservedID++;
1110 
1111   for (unsigned SUNum : DAG->BottomUpIndex2SU) {
1112     SUnit *SU = &DAG->SUnits[SUNum];
1113     bool hasSuccessor = false;
1114 
1115     if (CurrentColoring[SU->NodeNum] <= (int)DAGSize)
1116       continue;
1117 
1118     for (SDep& SuccDep : SU->Succs) {
1119        SUnit *Succ = SuccDep.getSUnit();
1120       if (SuccDep.isWeak() || Succ->NodeNum >= DAGSize)
1121         continue;
1122       hasSuccessor = true;
1123     }
1124     if (!hasSuccessor)
1125       CurrentColoring[SU->NodeNum] = GroupID;
1126   }
1127 }
1128 
colorExports()1129 void SIScheduleBlockCreator::colorExports() {
1130   unsigned ExportColor = NextNonReservedID++;
1131   SmallVector<unsigned, 8> ExpGroup;
1132 
1133   // Put all exports together in a block.
1134   // The block will naturally end up being scheduled last,
1135   // thus putting exports at the end of the schedule, which
1136   // is better for performance.
1137   // However we must ensure, for safety, the exports can be put
1138   // together in the same block without any other instruction.
1139   // This could happen, for example, when scheduling after regalloc
1140   // if reloading a spilled register from memory using the same
1141   // register than used in a previous export.
1142   // If that happens, do not regroup the exports.
1143   for (unsigned SUNum : DAG->TopDownIndex2SU) {
1144     const SUnit &SU = DAG->SUnits[SUNum];
1145     if (SIInstrInfo::isEXP(*SU.getInstr())) {
1146       // Check the EXP can be added to the group safely,
1147       // ie without needing any other instruction.
1148       // The EXP is allowed to depend on other EXP
1149       // (they will be in the same group).
1150       for (unsigned j : ExpGroup) {
1151         bool HasSubGraph;
1152         std::vector<int> SubGraph;
1153         // By construction (topological order), if SU and
1154         // DAG->SUnits[j] are linked, DAG->SUnits[j] is neccessary
1155         // in the parent graph of SU.
1156 #ifndef NDEBUG
1157         SubGraph = DAG->GetTopo()->GetSubGraph(SU, DAG->SUnits[j],
1158                                                HasSubGraph);
1159         assert(!HasSubGraph);
1160 #endif
1161         SubGraph = DAG->GetTopo()->GetSubGraph(DAG->SUnits[j], SU,
1162                                                HasSubGraph);
1163         if (!HasSubGraph)
1164           continue; // No dependencies between each other
1165 
1166         // SubGraph contains all the instructions required
1167         // between EXP SUnits[j] and EXP SU.
1168         for (unsigned k : SubGraph) {
1169           if (!SIInstrInfo::isEXP(*DAG->SUnits[k].getInstr()))
1170             // Other instructions than EXP would be required in the group.
1171             // Abort the groupping.
1172             return;
1173         }
1174       }
1175 
1176       ExpGroup.push_back(SUNum);
1177     }
1178   }
1179 
1180   // The group can be formed. Give the color.
1181   for (unsigned j : ExpGroup)
1182     CurrentColoring[j] = ExportColor;
1183 }
1184 
createBlocksForVariant(SISchedulerBlockCreatorVariant BlockVariant)1185 void SIScheduleBlockCreator::createBlocksForVariant(SISchedulerBlockCreatorVariant BlockVariant) {
1186   unsigned DAGSize = DAG->SUnits.size();
1187   std::map<unsigned,unsigned> RealID;
1188 
1189   CurrentBlocks.clear();
1190   CurrentColoring.clear();
1191   CurrentColoring.resize(DAGSize, 0);
1192   Node2CurrentBlock.clear();
1193 
1194   // Restore links previous scheduling variant has overridden.
1195   DAG->restoreSULinksLeft();
1196 
1197   NextReservedID = 1;
1198   NextNonReservedID = DAGSize + 1;
1199 
1200   LLVM_DEBUG(dbgs() << "Coloring the graph\n");
1201 
1202   if (BlockVariant == SISchedulerBlockCreatorVariant::LatenciesGrouped)
1203     colorHighLatenciesGroups();
1204   else
1205     colorHighLatenciesAlone();
1206   colorComputeReservedDependencies();
1207   colorAccordingToReservedDependencies();
1208   colorEndsAccordingToDependencies();
1209   if (BlockVariant == SISchedulerBlockCreatorVariant::LatenciesAlonePlusConsecutive)
1210     colorForceConsecutiveOrderInGroup();
1211   regroupNoUserInstructions();
1212   colorMergeConstantLoadsNextGroup();
1213   colorMergeIfPossibleNextGroupOnlyForReserved();
1214   colorExports();
1215 
1216   // Put SUs of same color into same block
1217   Node2CurrentBlock.resize(DAGSize, -1);
1218   for (unsigned i = 0, e = DAGSize; i != e; ++i) {
1219     SUnit *SU = &DAG->SUnits[i];
1220     unsigned Color = CurrentColoring[SU->NodeNum];
1221     if (RealID.find(Color) == RealID.end()) {
1222       int ID = CurrentBlocks.size();
1223       BlockPtrs.push_back(std::make_unique<SIScheduleBlock>(DAG, this, ID));
1224       CurrentBlocks.push_back(BlockPtrs.rbegin()->get());
1225       RealID[Color] = ID;
1226     }
1227     CurrentBlocks[RealID[Color]]->addUnit(SU);
1228     Node2CurrentBlock[SU->NodeNum] = RealID[Color];
1229   }
1230 
1231   // Build dependencies between blocks.
1232   for (unsigned i = 0, e = DAGSize; i != e; ++i) {
1233     SUnit *SU = &DAG->SUnits[i];
1234     int SUID = Node2CurrentBlock[i];
1235      for (SDep& SuccDep : SU->Succs) {
1236        SUnit *Succ = SuccDep.getSUnit();
1237       if (SuccDep.isWeak() || Succ->NodeNum >= DAGSize)
1238         continue;
1239       if (Node2CurrentBlock[Succ->NodeNum] != SUID)
1240         CurrentBlocks[SUID]->addSucc(CurrentBlocks[Node2CurrentBlock[Succ->NodeNum]],
1241                                      SuccDep.isCtrl() ? NoData : Data);
1242     }
1243     for (SDep& PredDep : SU->Preds) {
1244       SUnit *Pred = PredDep.getSUnit();
1245       if (PredDep.isWeak() || Pred->NodeNum >= DAGSize)
1246         continue;
1247       if (Node2CurrentBlock[Pred->NodeNum] != SUID)
1248         CurrentBlocks[SUID]->addPred(CurrentBlocks[Node2CurrentBlock[Pred->NodeNum]]);
1249     }
1250   }
1251 
1252   // Free root and leafs of all blocks to enable scheduling inside them.
1253   for (unsigned i = 0, e = CurrentBlocks.size(); i != e; ++i) {
1254     SIScheduleBlock *Block = CurrentBlocks[i];
1255     Block->finalizeUnits();
1256   }
1257   LLVM_DEBUG(dbgs() << "Blocks created:\n\n";
1258              for (unsigned i = 0, e = CurrentBlocks.size(); i != e; ++i) {
1259                SIScheduleBlock *Block = CurrentBlocks[i];
1260                Block->printDebug(true);
1261              });
1262 }
1263 
1264 // Two functions taken from Codegen/MachineScheduler.cpp
1265 
1266 /// Non-const version.
1267 static MachineBasicBlock::iterator
nextIfDebug(MachineBasicBlock::iterator I,MachineBasicBlock::const_iterator End)1268 nextIfDebug(MachineBasicBlock::iterator I,
1269             MachineBasicBlock::const_iterator End) {
1270   for (; I != End; ++I) {
1271     if (!I->isDebugInstr())
1272       break;
1273   }
1274   return I;
1275 }
1276 
topologicalSort()1277 void SIScheduleBlockCreator::topologicalSort() {
1278   unsigned DAGSize = CurrentBlocks.size();
1279   std::vector<int> WorkList;
1280 
1281   LLVM_DEBUG(dbgs() << "Topological Sort\n");
1282 
1283   WorkList.reserve(DAGSize);
1284   TopDownIndex2Block.resize(DAGSize);
1285   TopDownBlock2Index.resize(DAGSize);
1286   BottomUpIndex2Block.resize(DAGSize);
1287 
1288   for (unsigned i = 0, e = DAGSize; i != e; ++i) {
1289     SIScheduleBlock *Block = CurrentBlocks[i];
1290     unsigned Degree = Block->getSuccs().size();
1291     TopDownBlock2Index[i] = Degree;
1292     if (Degree == 0) {
1293       WorkList.push_back(i);
1294     }
1295   }
1296 
1297   int Id = DAGSize;
1298   while (!WorkList.empty()) {
1299     int i = WorkList.back();
1300     SIScheduleBlock *Block = CurrentBlocks[i];
1301     WorkList.pop_back();
1302     TopDownBlock2Index[i] = --Id;
1303     TopDownIndex2Block[Id] = i;
1304     for (SIScheduleBlock* Pred : Block->getPreds()) {
1305       if (!--TopDownBlock2Index[Pred->getID()])
1306         WorkList.push_back(Pred->getID());
1307     }
1308   }
1309 
1310 #ifndef NDEBUG
1311   // Check correctness of the ordering.
1312   for (unsigned i = 0, e = DAGSize; i != e; ++i) {
1313     SIScheduleBlock *Block = CurrentBlocks[i];
1314     for (SIScheduleBlock* Pred : Block->getPreds()) {
1315       assert(TopDownBlock2Index[i] > TopDownBlock2Index[Pred->getID()] &&
1316       "Wrong Top Down topological sorting");
1317     }
1318   }
1319 #endif
1320 
1321   BottomUpIndex2Block = std::vector<int>(TopDownIndex2Block.rbegin(),
1322                                          TopDownIndex2Block.rend());
1323 }
1324 
scheduleInsideBlocks()1325 void SIScheduleBlockCreator::scheduleInsideBlocks() {
1326   unsigned DAGSize = CurrentBlocks.size();
1327 
1328   LLVM_DEBUG(dbgs() << "\nScheduling Blocks\n\n");
1329 
1330   // We do schedule a valid scheduling such that a Block corresponds
1331   // to a range of instructions.
1332   LLVM_DEBUG(dbgs() << "First phase: Fast scheduling for Reg Liveness\n");
1333   for (unsigned i = 0, e = DAGSize; i != e; ++i) {
1334     SIScheduleBlock *Block = CurrentBlocks[i];
1335     Block->fastSchedule();
1336   }
1337 
1338   // Note: the following code, and the part restoring previous position
1339   // is by far the most expensive operation of the Scheduler.
1340 
1341   // Do not update CurrentTop.
1342   MachineBasicBlock::iterator CurrentTopFastSched = DAG->getCurrentTop();
1343   std::vector<MachineBasicBlock::iterator> PosOld;
1344   std::vector<MachineBasicBlock::iterator> PosNew;
1345   PosOld.reserve(DAG->SUnits.size());
1346   PosNew.reserve(DAG->SUnits.size());
1347 
1348   for (unsigned i = 0, e = DAGSize; i != e; ++i) {
1349     int BlockIndice = TopDownIndex2Block[i];
1350     SIScheduleBlock *Block = CurrentBlocks[BlockIndice];
1351     std::vector<SUnit*> SUs = Block->getScheduledUnits();
1352 
1353     for (SUnit* SU : SUs) {
1354       MachineInstr *MI = SU->getInstr();
1355       MachineBasicBlock::iterator Pos = MI;
1356       PosOld.push_back(Pos);
1357       if (&*CurrentTopFastSched == MI) {
1358         PosNew.push_back(Pos);
1359         CurrentTopFastSched = nextIfDebug(++CurrentTopFastSched,
1360                                           DAG->getCurrentBottom());
1361       } else {
1362         // Update the instruction stream.
1363         DAG->getBB()->splice(CurrentTopFastSched, DAG->getBB(), MI);
1364 
1365         // Update LiveIntervals.
1366         // Note: Moving all instructions and calling handleMove every time
1367         // is the most cpu intensive operation of the scheduler.
1368         // It would gain a lot if there was a way to recompute the
1369         // LiveIntervals for the entire scheduling region.
1370         DAG->getLIS()->handleMove(*MI, /*UpdateFlags=*/true);
1371         PosNew.push_back(CurrentTopFastSched);
1372       }
1373     }
1374   }
1375 
1376   // Now we have Block of SUs == Block of MI.
1377   // We do the final schedule for the instructions inside the block.
1378   // The property that all the SUs of the Block are grouped together as MI
1379   // is used for correct reg usage tracking.
1380   for (unsigned i = 0, e = DAGSize; i != e; ++i) {
1381     SIScheduleBlock *Block = CurrentBlocks[i];
1382     std::vector<SUnit*> SUs = Block->getScheduledUnits();
1383     Block->schedule((*SUs.begin())->getInstr(), (*SUs.rbegin())->getInstr());
1384   }
1385 
1386   LLVM_DEBUG(dbgs() << "Restoring MI Pos\n");
1387   // Restore old ordering (which prevents a LIS->handleMove bug).
1388   for (unsigned i = PosOld.size(), e = 0; i != e; --i) {
1389     MachineBasicBlock::iterator POld = PosOld[i-1];
1390     MachineBasicBlock::iterator PNew = PosNew[i-1];
1391     if (PNew != POld) {
1392       // Update the instruction stream.
1393       DAG->getBB()->splice(POld, DAG->getBB(), PNew);
1394 
1395       // Update LiveIntervals.
1396       DAG->getLIS()->handleMove(*POld, /*UpdateFlags=*/true);
1397     }
1398   }
1399 
1400   LLVM_DEBUG(for (unsigned i = 0, e = CurrentBlocks.size(); i != e; ++i) {
1401     SIScheduleBlock *Block = CurrentBlocks[i];
1402     Block->printDebug(true);
1403   });
1404 }
1405 
fillStats()1406 void SIScheduleBlockCreator::fillStats() {
1407   unsigned DAGSize = CurrentBlocks.size();
1408 
1409   for (unsigned i = 0, e = DAGSize; i != e; ++i) {
1410     int BlockIndice = TopDownIndex2Block[i];
1411     SIScheduleBlock *Block = CurrentBlocks[BlockIndice];
1412     if (Block->getPreds().empty())
1413       Block->Depth = 0;
1414     else {
1415       unsigned Depth = 0;
1416       for (SIScheduleBlock *Pred : Block->getPreds()) {
1417         if (Depth < Pred->Depth + Pred->getCost())
1418           Depth = Pred->Depth + Pred->getCost();
1419       }
1420       Block->Depth = Depth;
1421     }
1422   }
1423 
1424   for (unsigned i = 0, e = DAGSize; i != e; ++i) {
1425     int BlockIndice = BottomUpIndex2Block[i];
1426     SIScheduleBlock *Block = CurrentBlocks[BlockIndice];
1427     if (Block->getSuccs().empty())
1428       Block->Height = 0;
1429     else {
1430       unsigned Height = 0;
1431       for (const auto &Succ : Block->getSuccs())
1432         Height = std::max(Height, Succ.first->Height + Succ.first->getCost());
1433       Block->Height = Height;
1434     }
1435   }
1436 }
1437 
1438 // SIScheduleBlockScheduler //
1439 
SIScheduleBlockScheduler(SIScheduleDAGMI * DAG,SISchedulerBlockSchedulerVariant Variant,SIScheduleBlocks BlocksStruct)1440 SIScheduleBlockScheduler::SIScheduleBlockScheduler(SIScheduleDAGMI *DAG,
1441                                                    SISchedulerBlockSchedulerVariant Variant,
1442                                                    SIScheduleBlocks  BlocksStruct) :
1443   DAG(DAG), Variant(Variant), Blocks(BlocksStruct.Blocks),
1444   LastPosWaitedHighLatency(0), NumBlockScheduled(0), VregCurrentUsage(0),
1445   SregCurrentUsage(0), maxVregUsage(0), maxSregUsage(0) {
1446 
1447   // Fill the usage of every output
1448   // Warning: while by construction we always have a link between two blocks
1449   // when one needs a result from the other, the number of users of an output
1450   // is not the sum of child blocks having as input the same virtual register.
1451   // Here is an example. A produces x and y. B eats x and produces x'.
1452   // C eats x' and y. The register coalescer may have attributed the same
1453   // virtual register to x and x'.
1454   // To count accurately, we do a topological sort. In case the register is
1455   // found for several parents, we increment the usage of the one with the
1456   // highest topological index.
1457   LiveOutRegsNumUsages.resize(Blocks.size());
1458   for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
1459     SIScheduleBlock *Block = Blocks[i];
1460     for (unsigned Reg : Block->getInRegs()) {
1461       bool Found = false;
1462       int topoInd = -1;
1463       for (SIScheduleBlock* Pred: Block->getPreds()) {
1464         std::set<unsigned> PredOutRegs = Pred->getOutRegs();
1465         std::set<unsigned>::iterator RegPos = PredOutRegs.find(Reg);
1466 
1467         if (RegPos != PredOutRegs.end()) {
1468           Found = true;
1469           if (topoInd < BlocksStruct.TopDownBlock2Index[Pred->getID()]) {
1470             topoInd = BlocksStruct.TopDownBlock2Index[Pred->getID()];
1471           }
1472         }
1473       }
1474 
1475       if (!Found)
1476         continue;
1477 
1478       int PredID = BlocksStruct.TopDownIndex2Block[topoInd];
1479       ++LiveOutRegsNumUsages[PredID][Reg];
1480     }
1481   }
1482 
1483   LastPosHighLatencyParentScheduled.resize(Blocks.size(), 0);
1484   BlockNumPredsLeft.resize(Blocks.size());
1485   BlockNumSuccsLeft.resize(Blocks.size());
1486 
1487   for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
1488     SIScheduleBlock *Block = Blocks[i];
1489     BlockNumPredsLeft[i] = Block->getPreds().size();
1490     BlockNumSuccsLeft[i] = Block->getSuccs().size();
1491   }
1492 
1493 #ifndef NDEBUG
1494   for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
1495     SIScheduleBlock *Block = Blocks[i];
1496     assert(Block->getID() == i);
1497   }
1498 #endif
1499 
1500   std::set<unsigned> InRegs = DAG->getInRegs();
1501   addLiveRegs(InRegs);
1502 
1503   // Increase LiveOutRegsNumUsages for blocks
1504   // producing registers consumed in another
1505   // scheduling region.
1506   for (unsigned Reg : DAG->getOutRegs()) {
1507     for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
1508       // Do reverse traversal
1509       int ID = BlocksStruct.TopDownIndex2Block[Blocks.size()-1-i];
1510       SIScheduleBlock *Block = Blocks[ID];
1511       const std::set<unsigned> &OutRegs = Block->getOutRegs();
1512 
1513       if (OutRegs.find(Reg) == OutRegs.end())
1514         continue;
1515 
1516       ++LiveOutRegsNumUsages[ID][Reg];
1517       break;
1518     }
1519   }
1520 
1521   // Fill LiveRegsConsumers for regs that were already
1522   // defined before scheduling.
1523   for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
1524     SIScheduleBlock *Block = Blocks[i];
1525     for (unsigned Reg : Block->getInRegs()) {
1526       bool Found = false;
1527       for (SIScheduleBlock* Pred: Block->getPreds()) {
1528         std::set<unsigned> PredOutRegs = Pred->getOutRegs();
1529         std::set<unsigned>::iterator RegPos = PredOutRegs.find(Reg);
1530 
1531         if (RegPos != PredOutRegs.end()) {
1532           Found = true;
1533           break;
1534         }
1535       }
1536 
1537       if (!Found)
1538         ++LiveRegsConsumers[Reg];
1539     }
1540   }
1541 
1542   for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
1543     SIScheduleBlock *Block = Blocks[i];
1544     if (BlockNumPredsLeft[i] == 0) {
1545       ReadyBlocks.push_back(Block);
1546     }
1547   }
1548 
1549   while (SIScheduleBlock *Block = pickBlock()) {
1550     BlocksScheduled.push_back(Block);
1551     blockScheduled(Block);
1552   }
1553 
1554   LLVM_DEBUG(dbgs() << "Block Order:"; for (SIScheduleBlock *Block
1555                                             : BlocksScheduled) {
1556     dbgs() << ' ' << Block->getID();
1557   } dbgs() << '\n';);
1558 }
1559 
tryCandidateLatency(SIBlockSchedCandidate & Cand,SIBlockSchedCandidate & TryCand)1560 bool SIScheduleBlockScheduler::tryCandidateLatency(SIBlockSchedCandidate &Cand,
1561                                                    SIBlockSchedCandidate &TryCand) {
1562   if (!Cand.isValid()) {
1563     TryCand.Reason = NodeOrder;
1564     return true;
1565   }
1566 
1567   // Try to hide high latencies.
1568   if (SISched::tryLess(TryCand.LastPosHighLatParentScheduled,
1569                  Cand.LastPosHighLatParentScheduled, TryCand, Cand, Latency))
1570     return true;
1571   // Schedule high latencies early so you can hide them better.
1572   if (SISched::tryGreater(TryCand.IsHighLatency, Cand.IsHighLatency,
1573                           TryCand, Cand, Latency))
1574     return true;
1575   if (TryCand.IsHighLatency && SISched::tryGreater(TryCand.Height, Cand.Height,
1576                                                    TryCand, Cand, Depth))
1577     return true;
1578   if (SISched::tryGreater(TryCand.NumHighLatencySuccessors,
1579                           Cand.NumHighLatencySuccessors,
1580                           TryCand, Cand, Successor))
1581     return true;
1582   return false;
1583 }
1584 
tryCandidateRegUsage(SIBlockSchedCandidate & Cand,SIBlockSchedCandidate & TryCand)1585 bool SIScheduleBlockScheduler::tryCandidateRegUsage(SIBlockSchedCandidate &Cand,
1586                                                     SIBlockSchedCandidate &TryCand) {
1587   if (!Cand.isValid()) {
1588     TryCand.Reason = NodeOrder;
1589     return true;
1590   }
1591 
1592   if (SISched::tryLess(TryCand.VGPRUsageDiff > 0, Cand.VGPRUsageDiff > 0,
1593                        TryCand, Cand, RegUsage))
1594     return true;
1595   if (SISched::tryGreater(TryCand.NumSuccessors > 0,
1596                           Cand.NumSuccessors > 0,
1597                           TryCand, Cand, Successor))
1598     return true;
1599   if (SISched::tryGreater(TryCand.Height, Cand.Height, TryCand, Cand, Depth))
1600     return true;
1601   if (SISched::tryLess(TryCand.VGPRUsageDiff, Cand.VGPRUsageDiff,
1602                        TryCand, Cand, RegUsage))
1603     return true;
1604   return false;
1605 }
1606 
pickBlock()1607 SIScheduleBlock *SIScheduleBlockScheduler::pickBlock() {
1608   SIBlockSchedCandidate Cand;
1609   std::vector<SIScheduleBlock*>::iterator Best;
1610   SIScheduleBlock *Block;
1611   if (ReadyBlocks.empty())
1612     return nullptr;
1613 
1614   DAG->fillVgprSgprCost(LiveRegs.begin(), LiveRegs.end(),
1615                         VregCurrentUsage, SregCurrentUsage);
1616   if (VregCurrentUsage > maxVregUsage)
1617     maxVregUsage = VregCurrentUsage;
1618   if (SregCurrentUsage > maxSregUsage)
1619     maxSregUsage = SregCurrentUsage;
1620   LLVM_DEBUG(dbgs() << "Picking New Blocks\n"; dbgs() << "Available: ";
1621              for (SIScheduleBlock *Block
1622                   : ReadyBlocks) dbgs()
1623              << Block->getID() << ' ';
1624              dbgs() << "\nCurrent Live:\n";
1625              for (unsigned Reg
1626                   : LiveRegs) dbgs()
1627              << printVRegOrUnit(Reg, DAG->getTRI()) << ' ';
1628              dbgs() << '\n';
1629              dbgs() << "Current VGPRs: " << VregCurrentUsage << '\n';
1630              dbgs() << "Current SGPRs: " << SregCurrentUsage << '\n';);
1631 
1632   Cand.Block = nullptr;
1633   for (std::vector<SIScheduleBlock*>::iterator I = ReadyBlocks.begin(),
1634        E = ReadyBlocks.end(); I != E; ++I) {
1635     SIBlockSchedCandidate TryCand;
1636     TryCand.Block = *I;
1637     TryCand.IsHighLatency = TryCand.Block->isHighLatencyBlock();
1638     TryCand.VGPRUsageDiff =
1639       checkRegUsageImpact(TryCand.Block->getInRegs(),
1640                           TryCand.Block->getOutRegs())[DAG->getVGPRSetID()];
1641     TryCand.NumSuccessors = TryCand.Block->getSuccs().size();
1642     TryCand.NumHighLatencySuccessors =
1643       TryCand.Block->getNumHighLatencySuccessors();
1644     TryCand.LastPosHighLatParentScheduled =
1645       (unsigned int) std::max<int> (0,
1646          LastPosHighLatencyParentScheduled[TryCand.Block->getID()] -
1647            LastPosWaitedHighLatency);
1648     TryCand.Height = TryCand.Block->Height;
1649     // Try not to increase VGPR usage too much, else we may spill.
1650     if (VregCurrentUsage > 120 ||
1651         Variant != SISchedulerBlockSchedulerVariant::BlockLatencyRegUsage) {
1652       if (!tryCandidateRegUsage(Cand, TryCand) &&
1653           Variant != SISchedulerBlockSchedulerVariant::BlockRegUsage)
1654         tryCandidateLatency(Cand, TryCand);
1655     } else {
1656       if (!tryCandidateLatency(Cand, TryCand))
1657         tryCandidateRegUsage(Cand, TryCand);
1658     }
1659     if (TryCand.Reason != NoCand) {
1660       Cand.setBest(TryCand);
1661       Best = I;
1662       LLVM_DEBUG(dbgs() << "Best Current Choice: " << Cand.Block->getID() << ' '
1663                         << getReasonStr(Cand.Reason) << '\n');
1664     }
1665   }
1666 
1667   LLVM_DEBUG(dbgs() << "Picking: " << Cand.Block->getID() << '\n';
1668              dbgs() << "Is a block with high latency instruction: "
1669                     << (Cand.IsHighLatency ? "yes\n" : "no\n");
1670              dbgs() << "Position of last high latency dependency: "
1671                     << Cand.LastPosHighLatParentScheduled << '\n';
1672              dbgs() << "VGPRUsageDiff: " << Cand.VGPRUsageDiff << '\n';
1673              dbgs() << '\n';);
1674 
1675   Block = Cand.Block;
1676   ReadyBlocks.erase(Best);
1677   return Block;
1678 }
1679 
1680 // Tracking of currently alive registers to determine VGPR Usage.
1681 
addLiveRegs(std::set<unsigned> & Regs)1682 void SIScheduleBlockScheduler::addLiveRegs(std::set<unsigned> &Regs) {
1683   for (unsigned Reg : Regs) {
1684     // For now only track virtual registers.
1685     if (!Register::isVirtualRegister(Reg))
1686       continue;
1687     // If not already in the live set, then add it.
1688     (void) LiveRegs.insert(Reg);
1689   }
1690 }
1691 
decreaseLiveRegs(SIScheduleBlock * Block,std::set<unsigned> & Regs)1692 void SIScheduleBlockScheduler::decreaseLiveRegs(SIScheduleBlock *Block,
1693                                        std::set<unsigned> &Regs) {
1694   for (unsigned Reg : Regs) {
1695     // For now only track virtual registers.
1696     std::set<unsigned>::iterator Pos = LiveRegs.find(Reg);
1697     assert (Pos != LiveRegs.end() && // Reg must be live.
1698                LiveRegsConsumers.find(Reg) != LiveRegsConsumers.end() &&
1699                LiveRegsConsumers[Reg] >= 1);
1700     --LiveRegsConsumers[Reg];
1701     if (LiveRegsConsumers[Reg] == 0)
1702       LiveRegs.erase(Pos);
1703   }
1704 }
1705 
releaseBlockSuccs(SIScheduleBlock * Parent)1706 void SIScheduleBlockScheduler::releaseBlockSuccs(SIScheduleBlock *Parent) {
1707   for (const auto &Block : Parent->getSuccs()) {
1708     if (--BlockNumPredsLeft[Block.first->getID()] == 0)
1709       ReadyBlocks.push_back(Block.first);
1710 
1711     if (Parent->isHighLatencyBlock() &&
1712         Block.second == SIScheduleBlockLinkKind::Data)
1713       LastPosHighLatencyParentScheduled[Block.first->getID()] = NumBlockScheduled;
1714   }
1715 }
1716 
blockScheduled(SIScheduleBlock * Block)1717 void SIScheduleBlockScheduler::blockScheduled(SIScheduleBlock *Block) {
1718   decreaseLiveRegs(Block, Block->getInRegs());
1719   addLiveRegs(Block->getOutRegs());
1720   releaseBlockSuccs(Block);
1721   for (std::map<unsigned, unsigned>::iterator RegI =
1722        LiveOutRegsNumUsages[Block->getID()].begin(),
1723        E = LiveOutRegsNumUsages[Block->getID()].end(); RegI != E; ++RegI) {
1724     std::pair<unsigned, unsigned> RegP = *RegI;
1725     // We produce this register, thus it must not be previously alive.
1726     assert(LiveRegsConsumers.find(RegP.first) == LiveRegsConsumers.end() ||
1727            LiveRegsConsumers[RegP.first] == 0);
1728     LiveRegsConsumers[RegP.first] += RegP.second;
1729   }
1730   if (LastPosHighLatencyParentScheduled[Block->getID()] >
1731         (unsigned)LastPosWaitedHighLatency)
1732     LastPosWaitedHighLatency =
1733       LastPosHighLatencyParentScheduled[Block->getID()];
1734   ++NumBlockScheduled;
1735 }
1736 
1737 std::vector<int>
checkRegUsageImpact(std::set<unsigned> & InRegs,std::set<unsigned> & OutRegs)1738 SIScheduleBlockScheduler::checkRegUsageImpact(std::set<unsigned> &InRegs,
1739                                      std::set<unsigned> &OutRegs) {
1740   std::vector<int> DiffSetPressure;
1741   DiffSetPressure.assign(DAG->getTRI()->getNumRegPressureSets(), 0);
1742 
1743   for (unsigned Reg : InRegs) {
1744     // For now only track virtual registers.
1745     if (!Register::isVirtualRegister(Reg))
1746       continue;
1747     if (LiveRegsConsumers[Reg] > 1)
1748       continue;
1749     PSetIterator PSetI = DAG->getMRI()->getPressureSets(Reg);
1750     for (; PSetI.isValid(); ++PSetI) {
1751       DiffSetPressure[*PSetI] -= PSetI.getWeight();
1752     }
1753   }
1754 
1755   for (unsigned Reg : OutRegs) {
1756     // For now only track virtual registers.
1757     if (!Register::isVirtualRegister(Reg))
1758       continue;
1759     PSetIterator PSetI = DAG->getMRI()->getPressureSets(Reg);
1760     for (; PSetI.isValid(); ++PSetI) {
1761       DiffSetPressure[*PSetI] += PSetI.getWeight();
1762     }
1763   }
1764 
1765   return DiffSetPressure;
1766 }
1767 
1768 // SIScheduler //
1769 
1770 struct SIScheduleBlockResult
scheduleVariant(SISchedulerBlockCreatorVariant BlockVariant,SISchedulerBlockSchedulerVariant ScheduleVariant)1771 SIScheduler::scheduleVariant(SISchedulerBlockCreatorVariant BlockVariant,
1772                              SISchedulerBlockSchedulerVariant ScheduleVariant) {
1773   SIScheduleBlocks Blocks = BlockCreator.getBlocks(BlockVariant);
1774   SIScheduleBlockScheduler Scheduler(DAG, ScheduleVariant, Blocks);
1775   std::vector<SIScheduleBlock*> ScheduledBlocks;
1776   struct SIScheduleBlockResult Res;
1777 
1778   ScheduledBlocks = Scheduler.getBlocks();
1779 
1780   for (unsigned b = 0; b < ScheduledBlocks.size(); ++b) {
1781     SIScheduleBlock *Block = ScheduledBlocks[b];
1782     std::vector<SUnit*> SUs = Block->getScheduledUnits();
1783 
1784     for (SUnit* SU : SUs)
1785       Res.SUs.push_back(SU->NodeNum);
1786   }
1787 
1788   Res.MaxSGPRUsage = Scheduler.getSGPRUsage();
1789   Res.MaxVGPRUsage = Scheduler.getVGPRUsage();
1790   return Res;
1791 }
1792 
1793 // SIScheduleDAGMI //
1794 
SIScheduleDAGMI(MachineSchedContext * C)1795 SIScheduleDAGMI::SIScheduleDAGMI(MachineSchedContext *C) :
1796   ScheduleDAGMILive(C, std::make_unique<GenericScheduler>(C)) {
1797   SITII = static_cast<const SIInstrInfo*>(TII);
1798   SITRI = static_cast<const SIRegisterInfo*>(TRI);
1799 
1800   VGPRSetID = SITRI->getVGPRPressureSet();
1801   SGPRSetID = SITRI->getSGPRPressureSet();
1802 }
1803 
1804 SIScheduleDAGMI::~SIScheduleDAGMI() = default;
1805 
1806 // Code adapted from scheduleDAG.cpp
1807 // Does a topological sort over the SUs.
1808 // Both TopDown and BottomUp
topologicalSort()1809 void SIScheduleDAGMI::topologicalSort() {
1810   Topo.InitDAGTopologicalSorting();
1811 
1812   TopDownIndex2SU = std::vector<int>(Topo.begin(), Topo.end());
1813   BottomUpIndex2SU = std::vector<int>(Topo.rbegin(), Topo.rend());
1814 }
1815 
1816 // Move low latencies further from their user without
1817 // increasing SGPR usage (in general)
1818 // This is to be replaced by a better pass that would
1819 // take into account SGPR usage (based on VGPR Usage
1820 // and the corresponding wavefront count), that would
1821 // try to merge groups of loads if it make sense, etc
moveLowLatencies()1822 void SIScheduleDAGMI::moveLowLatencies() {
1823    unsigned DAGSize = SUnits.size();
1824    int LastLowLatencyUser = -1;
1825    int LastLowLatencyPos = -1;
1826 
1827    for (unsigned i = 0, e = ScheduledSUnits.size(); i != e; ++i) {
1828     SUnit *SU = &SUnits[ScheduledSUnits[i]];
1829     bool IsLowLatencyUser = false;
1830     unsigned MinPos = 0;
1831 
1832     for (SDep& PredDep : SU->Preds) {
1833       SUnit *Pred = PredDep.getSUnit();
1834       if (SITII->isLowLatencyInstruction(*Pred->getInstr())) {
1835         IsLowLatencyUser = true;
1836       }
1837       if (Pred->NodeNum >= DAGSize)
1838         continue;
1839       unsigned PredPos = ScheduledSUnitsInv[Pred->NodeNum];
1840       if (PredPos >= MinPos)
1841         MinPos = PredPos + 1;
1842     }
1843 
1844     if (SITII->isLowLatencyInstruction(*SU->getInstr())) {
1845       unsigned BestPos = LastLowLatencyUser + 1;
1846       if ((int)BestPos <= LastLowLatencyPos)
1847         BestPos = LastLowLatencyPos + 1;
1848       if (BestPos < MinPos)
1849         BestPos = MinPos;
1850       if (BestPos < i) {
1851         for (unsigned u = i; u > BestPos; --u) {
1852           ++ScheduledSUnitsInv[ScheduledSUnits[u-1]];
1853           ScheduledSUnits[u] = ScheduledSUnits[u-1];
1854         }
1855         ScheduledSUnits[BestPos] = SU->NodeNum;
1856         ScheduledSUnitsInv[SU->NodeNum] = BestPos;
1857       }
1858       LastLowLatencyPos = BestPos;
1859       if (IsLowLatencyUser)
1860         LastLowLatencyUser = BestPos;
1861     } else if (IsLowLatencyUser) {
1862       LastLowLatencyUser = i;
1863     // Moves COPY instructions on which depends
1864     // the low latency instructions too.
1865     } else if (SU->getInstr()->getOpcode() == AMDGPU::COPY) {
1866       bool CopyForLowLat = false;
1867       for (SDep& SuccDep : SU->Succs) {
1868         SUnit *Succ = SuccDep.getSUnit();
1869         if (SuccDep.isWeak() || Succ->NodeNum >= DAGSize)
1870           continue;
1871         if (SITII->isLowLatencyInstruction(*Succ->getInstr())) {
1872           CopyForLowLat = true;
1873         }
1874       }
1875       if (!CopyForLowLat)
1876         continue;
1877       if (MinPos < i) {
1878         for (unsigned u = i; u > MinPos; --u) {
1879           ++ScheduledSUnitsInv[ScheduledSUnits[u-1]];
1880           ScheduledSUnits[u] = ScheduledSUnits[u-1];
1881         }
1882         ScheduledSUnits[MinPos] = SU->NodeNum;
1883         ScheduledSUnitsInv[SU->NodeNum] = MinPos;
1884       }
1885     }
1886   }
1887 }
1888 
restoreSULinksLeft()1889 void SIScheduleDAGMI::restoreSULinksLeft() {
1890   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
1891     SUnits[i].isScheduled = false;
1892     SUnits[i].WeakPredsLeft = SUnitsLinksBackup[i].WeakPredsLeft;
1893     SUnits[i].NumPredsLeft = SUnitsLinksBackup[i].NumPredsLeft;
1894     SUnits[i].WeakSuccsLeft = SUnitsLinksBackup[i].WeakSuccsLeft;
1895     SUnits[i].NumSuccsLeft = SUnitsLinksBackup[i].NumSuccsLeft;
1896   }
1897 }
1898 
1899 // Return the Vgpr and Sgpr usage corresponding to some virtual registers.
1900 template<typename _Iterator> void
fillVgprSgprCost(_Iterator First,_Iterator End,unsigned & VgprUsage,unsigned & SgprUsage)1901 SIScheduleDAGMI::fillVgprSgprCost(_Iterator First, _Iterator End,
1902                                   unsigned &VgprUsage, unsigned &SgprUsage) {
1903   VgprUsage = 0;
1904   SgprUsage = 0;
1905   for (_Iterator RegI = First; RegI != End; ++RegI) {
1906     unsigned Reg = *RegI;
1907     // For now only track virtual registers
1908     if (!Register::isVirtualRegister(Reg))
1909       continue;
1910     PSetIterator PSetI = MRI.getPressureSets(Reg);
1911     for (; PSetI.isValid(); ++PSetI) {
1912       if (*PSetI == VGPRSetID)
1913         VgprUsage += PSetI.getWeight();
1914       else if (*PSetI == SGPRSetID)
1915         SgprUsage += PSetI.getWeight();
1916     }
1917   }
1918 }
1919 
schedule()1920 void SIScheduleDAGMI::schedule()
1921 {
1922   SmallVector<SUnit*, 8> TopRoots, BotRoots;
1923   SIScheduleBlockResult Best, Temp;
1924   LLVM_DEBUG(dbgs() << "Preparing Scheduling\n");
1925 
1926   buildDAGWithRegPressure();
1927   LLVM_DEBUG(dump());
1928 
1929   topologicalSort();
1930   findRootsAndBiasEdges(TopRoots, BotRoots);
1931   // We reuse several ScheduleDAGMI and ScheduleDAGMILive
1932   // functions, but to make them happy we must initialize
1933   // the default Scheduler implementation (even if we do not
1934   // run it)
1935   SchedImpl->initialize(this);
1936   initQueues(TopRoots, BotRoots);
1937 
1938   // Fill some stats to help scheduling.
1939 
1940   SUnitsLinksBackup = SUnits;
1941   IsLowLatencySU.clear();
1942   LowLatencyOffset.clear();
1943   IsHighLatencySU.clear();
1944 
1945   IsLowLatencySU.resize(SUnits.size(), 0);
1946   LowLatencyOffset.resize(SUnits.size(), 0);
1947   IsHighLatencySU.resize(SUnits.size(), 0);
1948 
1949   for (unsigned i = 0, e = (unsigned)SUnits.size(); i != e; ++i) {
1950     SUnit *SU = &SUnits[i];
1951     const MachineOperand *BaseLatOp;
1952     int64_t OffLatReg;
1953     if (SITII->isLowLatencyInstruction(*SU->getInstr())) {
1954       IsLowLatencySU[i] = 1;
1955       if (SITII->getMemOperandWithOffset(*SU->getInstr(), BaseLatOp, OffLatReg,
1956                                          TRI))
1957         LowLatencyOffset[i] = OffLatReg;
1958     } else if (SITII->isHighLatencyInstruction(*SU->getInstr()))
1959       IsHighLatencySU[i] = 1;
1960   }
1961 
1962   SIScheduler Scheduler(this);
1963   Best = Scheduler.scheduleVariant(SISchedulerBlockCreatorVariant::LatenciesAlone,
1964                                    SISchedulerBlockSchedulerVariant::BlockLatencyRegUsage);
1965 
1966   // if VGPR usage is extremely high, try other good performing variants
1967   // which could lead to lower VGPR usage
1968   if (Best.MaxVGPRUsage > 180) {
1969     static const std::pair<SISchedulerBlockCreatorVariant,
1970                            SISchedulerBlockSchedulerVariant>
1971         Variants[] = {
1972       { LatenciesAlone, BlockRegUsageLatency },
1973 //      { LatenciesAlone, BlockRegUsage },
1974       { LatenciesGrouped, BlockLatencyRegUsage },
1975 //      { LatenciesGrouped, BlockRegUsageLatency },
1976 //      { LatenciesGrouped, BlockRegUsage },
1977       { LatenciesAlonePlusConsecutive, BlockLatencyRegUsage },
1978 //      { LatenciesAlonePlusConsecutive, BlockRegUsageLatency },
1979 //      { LatenciesAlonePlusConsecutive, BlockRegUsage }
1980     };
1981     for (std::pair<SISchedulerBlockCreatorVariant, SISchedulerBlockSchedulerVariant> v : Variants) {
1982       Temp = Scheduler.scheduleVariant(v.first, v.second);
1983       if (Temp.MaxVGPRUsage < Best.MaxVGPRUsage)
1984         Best = Temp;
1985     }
1986   }
1987   // if VGPR usage is still extremely high, we may spill. Try other variants
1988   // which are less performing, but that could lead to lower VGPR usage.
1989   if (Best.MaxVGPRUsage > 200) {
1990     static const std::pair<SISchedulerBlockCreatorVariant,
1991                            SISchedulerBlockSchedulerVariant>
1992         Variants[] = {
1993 //      { LatenciesAlone, BlockRegUsageLatency },
1994       { LatenciesAlone, BlockRegUsage },
1995 //      { LatenciesGrouped, BlockLatencyRegUsage },
1996       { LatenciesGrouped, BlockRegUsageLatency },
1997       { LatenciesGrouped, BlockRegUsage },
1998 //      { LatenciesAlonePlusConsecutive, BlockLatencyRegUsage },
1999       { LatenciesAlonePlusConsecutive, BlockRegUsageLatency },
2000       { LatenciesAlonePlusConsecutive, BlockRegUsage }
2001     };
2002     for (std::pair<SISchedulerBlockCreatorVariant, SISchedulerBlockSchedulerVariant> v : Variants) {
2003       Temp = Scheduler.scheduleVariant(v.first, v.second);
2004       if (Temp.MaxVGPRUsage < Best.MaxVGPRUsage)
2005         Best = Temp;
2006     }
2007   }
2008 
2009   ScheduledSUnits = Best.SUs;
2010   ScheduledSUnitsInv.resize(SUnits.size());
2011 
2012   for (unsigned i = 0, e = (unsigned)SUnits.size(); i != e; ++i) {
2013     ScheduledSUnitsInv[ScheduledSUnits[i]] = i;
2014   }
2015 
2016   moveLowLatencies();
2017 
2018   // Tell the outside world about the result of the scheduling.
2019 
2020   assert(TopRPTracker.getPos() == RegionBegin && "bad initial Top tracker");
2021   TopRPTracker.setPos(CurrentTop);
2022 
2023   for (std::vector<unsigned>::iterator I = ScheduledSUnits.begin(),
2024        E = ScheduledSUnits.end(); I != E; ++I) {
2025     SUnit *SU = &SUnits[*I];
2026 
2027     scheduleMI(SU, true);
2028 
2029     LLVM_DEBUG(dbgs() << "Scheduling SU(" << SU->NodeNum << ") "
2030                       << *SU->getInstr());
2031   }
2032 
2033   assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
2034 
2035   placeDebugValues();
2036 
2037   LLVM_DEBUG({
2038     dbgs() << "*** Final schedule for "
2039            << printMBBReference(*begin()->getParent()) << " ***\n";
2040     dumpSchedule();
2041     dbgs() << '\n';
2042   });
2043 }
2044