LCOV - code coverage report
Current view: top level - lib/Target/AMDGPU - SIMachineScheduler.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 628 809 77.6 %
Date: 2018-10-16 05:50:02 Functions: 46 54 85.2 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13