LCOV - code coverage report
Current view: top level - lib/CodeGen/SelectionDAG - ResourcePriorityQueue.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 7 278 2.5 %
Date: 2017-09-14 15:23:50 Functions: 2 19 10.5 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- ResourcePriorityQueue.cpp - A DFA-oriented priority queue -*- C++ -*-==//
       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             : // This file implements the ResourcePriorityQueue class, which is a
      11             : // SchedulingPriorityQueue that prioritizes instructions using DFA state to
      12             : // reduce the length of the critical path through the basic block
      13             : // on VLIW platforms.
      14             : // The scheduler is basically a top-down adaptable list scheduler with DFA
      15             : // resource tracking added to the cost function.
      16             : // DFA is queried as a state machine to model "packets/bundles" during
      17             : // schedule. Currently packets/bundles are discarded at the end of
      18             : // scheduling, affecting only order of instructions.
      19             : //
      20             : //===----------------------------------------------------------------------===//
      21             : 
      22             : #include "llvm/CodeGen/ResourcePriorityQueue.h"
      23             : #include "llvm/CodeGen/MachineInstr.h"
      24             : #include "llvm/CodeGen/SelectionDAGNodes.h"
      25             : #include "llvm/Support/CommandLine.h"
      26             : #include "llvm/Support/Debug.h"
      27             : #include "llvm/Support/raw_ostream.h"
      28             : #include "llvm/Target/TargetLowering.h"
      29             : #include "llvm/Target/TargetMachine.h"
      30             : #include "llvm/Target/TargetSubtargetInfo.h"
      31             : 
      32             : using namespace llvm;
      33             : 
      34             : #define DEBUG_TYPE "scheduler"
      35             : 
      36       72306 : static cl::opt<bool> DisableDFASched("disable-dfa-sched", cl::Hidden,
      37      216918 :   cl::ZeroOrMore, cl::init(false),
      38      289224 :   cl::desc("Disable use of DFA during scheduling"));
      39             : 
      40       72306 : static cl::opt<int> RegPressureThreshold(
      41      216918 :   "dfa-sched-reg-pressure-threshold", cl::Hidden, cl::ZeroOrMore, cl::init(5),
      42      289224 :   cl::desc("Track reg pressure and switch priority to in-depth"));
      43             : 
      44           0 : ResourcePriorityQueue::ResourcePriorityQueue(SelectionDAGISel *IS)
      45           0 :     : Picker(this), InstrItins(IS->MF->getSubtarget().getInstrItineraryData()) {
      46           0 :   const TargetSubtargetInfo &STI = IS->MF->getSubtarget();
      47           0 :   TRI = STI.getRegisterInfo();
      48           0 :   TLI = IS->TLI;
      49           0 :   TII = STI.getInstrInfo();
      50           0 :   ResourcesModel.reset(TII->CreateTargetScheduleState(STI));
      51             :   // This hard requirement could be relaxed, but for now
      52             :   // do not let it proceed.
      53             :   assert(ResourcesModel && "Unimplemented CreateTargetScheduleState.");
      54             : 
      55           0 :   unsigned NumRC = TRI->getNumRegClasses();
      56           0 :   RegLimit.resize(NumRC);
      57           0 :   RegPressure.resize(NumRC);
      58           0 :   std::fill(RegLimit.begin(), RegLimit.end(), 0);
      59           0 :   std::fill(RegPressure.begin(), RegPressure.end(), 0);
      60           0 :   for (const TargetRegisterClass *RC : TRI->regclasses())
      61           0 :     RegLimit[RC->getID()] = TRI->getRegPressureLimit(RC, *IS->MF);
      62             : 
      63           0 :   ParallelLiveRanges = 0;
      64           0 :   HorizontalVerticalBalance = 0;
      65           0 : }
      66             : 
      67             : unsigned
      68           0 : ResourcePriorityQueue::numberRCValPredInSU(SUnit *SU, unsigned RCId) {
      69           0 :   unsigned NumberDeps = 0;
      70           0 :   for (SDep &Pred : SU->Preds) {
      71           0 :     if (Pred.isCtrl())
      72           0 :       continue;
      73             : 
      74           0 :     SUnit *PredSU = Pred.getSUnit();
      75           0 :     const SDNode *ScegN = PredSU->getNode();
      76             : 
      77           0 :     if (!ScegN)
      78           0 :       continue;
      79             : 
      80             :     // If value is passed to CopyToReg, it is probably
      81             :     // live outside BB.
      82           0 :     switch (ScegN->getOpcode()) {
      83             :       default:  break;
      84             :       case ISD::TokenFactor:    break;
      85           0 :       case ISD::CopyFromReg:    NumberDeps++;  break;
      86             :       case ISD::CopyToReg:      break;
      87             :       case ISD::INLINEASM:      break;
      88             :     }
      89           0 :     if (!ScegN->isMachineOpcode())
      90           0 :       continue;
      91             : 
      92           0 :     for (unsigned i = 0, e = ScegN->getNumValues(); i != e; ++i) {
      93           0 :       MVT VT = ScegN->getSimpleValueType(i);
      94           0 :       if (TLI->isTypeLegal(VT)
      95           0 :           && (TLI->getRegClassFor(VT)->getID() == RCId)) {
      96           0 :         NumberDeps++;
      97           0 :         break;
      98             :       }
      99             :     }
     100             :   }
     101           0 :   return NumberDeps;
     102             : }
     103             : 
     104           0 : unsigned ResourcePriorityQueue::numberRCValSuccInSU(SUnit *SU,
     105             :                                                     unsigned RCId) {
     106           0 :   unsigned NumberDeps = 0;
     107           0 :   for (const SDep &Succ : SU->Succs) {
     108           0 :     if (Succ.isCtrl())
     109           0 :       continue;
     110             : 
     111           0 :     SUnit *SuccSU = Succ.getSUnit();
     112           0 :     const SDNode *ScegN = SuccSU->getNode();
     113           0 :     if (!ScegN)
     114           0 :       continue;
     115             : 
     116             :     // If value is passed to CopyToReg, it is probably
     117             :     // live outside BB.
     118           0 :     switch (ScegN->getOpcode()) {
     119             :       default:  break;
     120             :       case ISD::TokenFactor:    break;
     121             :       case ISD::CopyFromReg:    break;
     122           0 :       case ISD::CopyToReg:      NumberDeps++;  break;
     123             :       case ISD::INLINEASM:      break;
     124             :     }
     125           0 :     if (!ScegN->isMachineOpcode())
     126           0 :       continue;
     127             : 
     128           0 :     for (unsigned i = 0, e = ScegN->getNumOperands(); i != e; ++i) {
     129           0 :       const SDValue &Op = ScegN->getOperand(i);
     130           0 :       MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo());
     131           0 :       if (TLI->isTypeLegal(VT)
     132           0 :           && (TLI->getRegClassFor(VT)->getID() == RCId)) {
     133           0 :         NumberDeps++;
     134           0 :         break;
     135             :       }
     136             :     }
     137             :   }
     138           0 :   return NumberDeps;
     139             : }
     140             : 
     141             : static unsigned numberCtrlDepsInSU(SUnit *SU) {
     142           0 :   unsigned NumberDeps = 0;
     143           0 :   for (const SDep &Succ : SU->Succs)
     144           0 :     if (Succ.isCtrl())
     145           0 :       NumberDeps++;
     146             : 
     147             :   return NumberDeps;
     148             : }
     149             : 
     150             : static unsigned numberCtrlPredInSU(SUnit *SU) {
     151           0 :   unsigned NumberDeps = 0;
     152           0 :   for (SDep &Pred : SU->Preds)
     153           0 :     if (Pred.isCtrl())
     154           0 :       NumberDeps++;
     155             : 
     156             :   return NumberDeps;
     157             : }
     158             : 
     159             : ///
     160             : /// Initialize nodes.
     161             : ///
     162           0 : void ResourcePriorityQueue::initNodes(std::vector<SUnit> &sunits) {
     163           0 :   SUnits = &sunits;
     164           0 :   NumNodesSolelyBlocking.resize(SUnits->size(), 0);
     165             : 
     166           0 :   for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
     167           0 :     SUnit *SU = &(*SUnits)[i];
     168           0 :     initNumRegDefsLeft(SU);
     169           0 :     SU->NodeQueueId = 0;
     170             :   }
     171           0 : }
     172             : 
     173             : /// This heuristic is used if DFA scheduling is not desired
     174             : /// for some VLIW platform.
     175           0 : bool resource_sort::operator()(const SUnit *LHS, const SUnit *RHS) const {
     176             :   // The isScheduleHigh flag allows nodes with wraparound dependencies that
     177             :   // cannot easily be modeled as edges with latencies to be scheduled as
     178             :   // soon as possible in a top-down schedule.
     179           0 :   if (LHS->isScheduleHigh && !RHS->isScheduleHigh)
     180             :     return false;
     181             : 
     182           0 :   if (!LHS->isScheduleHigh && RHS->isScheduleHigh)
     183             :     return true;
     184             : 
     185           0 :   unsigned LHSNum = LHS->NodeNum;
     186           0 :   unsigned RHSNum = RHS->NodeNum;
     187             : 
     188             :   // The most important heuristic is scheduling the critical path.
     189           0 :   unsigned LHSLatency = PQ->getLatency(LHSNum);
     190           0 :   unsigned RHSLatency = PQ->getLatency(RHSNum);
     191           0 :   if (LHSLatency < RHSLatency) return true;
     192           0 :   if (LHSLatency > RHSLatency) return false;
     193             : 
     194             :   // After that, if two nodes have identical latencies, look to see if one will
     195             :   // unblock more other nodes than the other.
     196           0 :   unsigned LHSBlocked = PQ->getNumSolelyBlockNodes(LHSNum);
     197           0 :   unsigned RHSBlocked = PQ->getNumSolelyBlockNodes(RHSNum);
     198           0 :   if (LHSBlocked < RHSBlocked) return true;
     199           0 :   if (LHSBlocked > RHSBlocked) return false;
     200             : 
     201             :   // Finally, just to provide a stable ordering, use the node number as a
     202             :   // deciding factor.
     203           0 :   return LHSNum < RHSNum;
     204             : }
     205             : 
     206             : 
     207             : /// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor
     208             : /// of SU, return it, otherwise return null.
     209           0 : SUnit *ResourcePriorityQueue::getSingleUnscheduledPred(SUnit *SU) {
     210           0 :   SUnit *OnlyAvailablePred = nullptr;
     211           0 :   for (const SDep &Pred : SU->Preds) {
     212           0 :     SUnit &PredSU = *Pred.getSUnit();
     213           0 :     if (!PredSU.isScheduled) {
     214             :       // We found an available, but not scheduled, predecessor.  If it's the
     215             :       // only one we have found, keep track of it... otherwise give up.
     216           0 :       if (OnlyAvailablePred && OnlyAvailablePred != &PredSU)
     217             :         return nullptr;
     218             :       OnlyAvailablePred = &PredSU;
     219             :     }
     220             :   }
     221             :   return OnlyAvailablePred;
     222             : }
     223             : 
     224           0 : void ResourcePriorityQueue::push(SUnit *SU) {
     225             :   // Look at all of the successors of this node.  Count the number of nodes that
     226             :   // this node is the sole unscheduled node for.
     227           0 :   unsigned NumNodesBlocking = 0;
     228           0 :   for (const SDep &Succ : SU->Succs)
     229           0 :     if (getSingleUnscheduledPred(Succ.getSUnit()) == SU)
     230           0 :       ++NumNodesBlocking;
     231             : 
     232           0 :   NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking;
     233           0 :   Queue.push_back(SU);
     234           0 : }
     235             : 
     236             : /// Check if scheduling of this SU is possible
     237             : /// in the current packet.
     238           0 : bool ResourcePriorityQueue::isResourceAvailable(SUnit *SU) {
     239           0 :   if (!SU || !SU->getNode())
     240             :     return false;
     241             : 
     242             :   // If this is a compound instruction,
     243             :   // it is likely to be a call. Do not delay it.
     244           0 :   if (SU->getNode()->getGluedNode())
     245             :     return true;
     246             : 
     247             :   // First see if the pipeline could receive this instruction
     248             :   // in the current cycle.
     249           0 :   if (SU->getNode()->isMachineOpcode())
     250           0 :     switch (SU->getNode()->getMachineOpcode()) {
     251           0 :     default:
     252           0 :       if (!ResourcesModel->canReserveResources(&TII->get(
     253           0 :           SU->getNode()->getMachineOpcode())))
     254             :            return false;
     255             :     case TargetOpcode::EXTRACT_SUBREG:
     256             :     case TargetOpcode::INSERT_SUBREG:
     257             :     case TargetOpcode::SUBREG_TO_REG:
     258             :     case TargetOpcode::REG_SEQUENCE:
     259             :     case TargetOpcode::IMPLICIT_DEF:
     260             :         break;
     261             :     }
     262             : 
     263             :   // Now see if there are no other dependencies
     264             :   // to instructions already in the packet.
     265           0 :   for (unsigned i = 0, e = Packet.size(); i != e; ++i)
     266           0 :     for (const SDep &Succ : Packet[i]->Succs) {
     267             :       // Since we do not add pseudos to packets, might as well
     268             :       // ignore order deps.
     269           0 :       if (Succ.isCtrl())
     270           0 :         continue;
     271             : 
     272           0 :       if (Succ.getSUnit() == SU)
     273             :         return false;
     274             :     }
     275             : 
     276             :   return true;
     277             : }
     278             : 
     279             : /// Keep track of available resources.
     280           0 : void ResourcePriorityQueue::reserveResources(SUnit *SU) {
     281             :   // If this SU does not fit in the packet
     282             :   // start a new one.
     283           0 :   if (!isResourceAvailable(SU) || SU->getNode()->getGluedNode()) {
     284           0 :     ResourcesModel->clearResources();
     285           0 :     Packet.clear();
     286             :   }
     287             : 
     288           0 :   if (SU->getNode() && SU->getNode()->isMachineOpcode()) {
     289           0 :     switch (SU->getNode()->getMachineOpcode()) {
     290           0 :     default:
     291           0 :       ResourcesModel->reserveResources(&TII->get(
     292           0 :         SU->getNode()->getMachineOpcode()));
     293           0 :       break;
     294             :     case TargetOpcode::EXTRACT_SUBREG:
     295             :     case TargetOpcode::INSERT_SUBREG:
     296             :     case TargetOpcode::SUBREG_TO_REG:
     297             :     case TargetOpcode::REG_SEQUENCE:
     298             :     case TargetOpcode::IMPLICIT_DEF:
     299             :       break;
     300             :     }
     301           0 :     Packet.push_back(SU);
     302             :   }
     303             :   // Forcefully end packet for PseudoOps.
     304             :   else {
     305           0 :     ResourcesModel->clearResources();
     306           0 :     Packet.clear();
     307             :   }
     308             : 
     309             :   // If packet is now full, reset the state so in the next cycle
     310             :   // we start fresh.
     311           0 :   if (Packet.size() >= InstrItins->SchedModel.IssueWidth) {
     312           0 :     ResourcesModel->clearResources();
     313           0 :     Packet.clear();
     314             :   }
     315           0 : }
     316             : 
     317           0 : int ResourcePriorityQueue::rawRegPressureDelta(SUnit *SU, unsigned RCId) {
     318           0 :   int RegBalance = 0;
     319             : 
     320           0 :   if (!SU || !SU->getNode() || !SU->getNode()->isMachineOpcode())
     321             :     return RegBalance;
     322             : 
     323             :   // Gen estimate.
     324           0 :   for (unsigned i = 0, e = SU->getNode()->getNumValues(); i != e; ++i) {
     325           0 :       MVT VT = SU->getNode()->getSimpleValueType(i);
     326           0 :       if (TLI->isTypeLegal(VT)
     327           0 :           && TLI->getRegClassFor(VT)
     328           0 :           && TLI->getRegClassFor(VT)->getID() == RCId)
     329           0 :         RegBalance += numberRCValSuccInSU(SU, RCId);
     330             :   }
     331             :   // Kill estimate.
     332           0 :   for (unsigned i = 0, e = SU->getNode()->getNumOperands(); i != e; ++i) {
     333           0 :       const SDValue &Op = SU->getNode()->getOperand(i);
     334           0 :       MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo());
     335           0 :       if (isa<ConstantSDNode>(Op.getNode()))
     336           0 :         continue;
     337             : 
     338           0 :       if (TLI->isTypeLegal(VT) && TLI->getRegClassFor(VT)
     339           0 :           && TLI->getRegClassFor(VT)->getID() == RCId)
     340           0 :         RegBalance -= numberRCValPredInSU(SU, RCId);
     341             :   }
     342             :   return RegBalance;
     343             : }
     344             : 
     345             : /// Estimates change in reg pressure from this SU.
     346             : /// It is achieved by trivial tracking of defined
     347             : /// and used vregs in dependent instructions.
     348             : /// The RawPressure flag makes this function to ignore
     349             : /// existing reg file sizes, and report raw def/use
     350             : /// balance.
     351           0 : int ResourcePriorityQueue::regPressureDelta(SUnit *SU, bool RawPressure) {
     352           0 :   int RegBalance = 0;
     353             : 
     354           0 :   if (!SU || !SU->getNode() || !SU->getNode()->isMachineOpcode())
     355             :     return RegBalance;
     356             : 
     357           0 :   if (RawPressure) {
     358           0 :     for (const TargetRegisterClass *RC : TRI->regclasses())
     359           0 :       RegBalance += rawRegPressureDelta(SU, RC->getID());
     360             :   }
     361             :   else {
     362           0 :     for (const TargetRegisterClass *RC : TRI->regclasses()) {
     363           0 :       if ((RegPressure[RC->getID()] +
     364           0 :            rawRegPressureDelta(SU, RC->getID()) > 0) &&
     365           0 :           (RegPressure[RC->getID()] +
     366           0 :            rawRegPressureDelta(SU, RC->getID())  >= RegLimit[RC->getID()]))
     367           0 :         RegBalance += rawRegPressureDelta(SU, RC->getID());
     368             :     }
     369             :   }
     370             : 
     371             :   return RegBalance;
     372             : }
     373             : 
     374             : // Constants used to denote relative importance of
     375             : // heuristic components for cost computation.
     376             : static const unsigned PriorityOne = 200;
     377             : static const unsigned PriorityTwo = 50;
     378             : static const unsigned PriorityThree = 15;
     379             : static const unsigned PriorityFour = 5;
     380             : static const unsigned ScaleOne = 20;
     381             : static const unsigned ScaleTwo = 10;
     382             : static const unsigned ScaleThree = 5;
     383             : static const unsigned FactorOne = 2;
     384             : 
     385             : /// Returns single number reflecting benefit of scheduling SU
     386             : /// in the current cycle.
     387           0 : int ResourcePriorityQueue::SUSchedulingCost(SUnit *SU) {
     388             :   // Initial trivial priority.
     389           0 :   int ResCount = 1;
     390             : 
     391             :   // Do not waste time on a node that is already scheduled.
     392           0 :   if (SU->isScheduled)
     393             :     return ResCount;
     394             : 
     395             :   // Forced priority is high.
     396           0 :   if (SU->isScheduleHigh)
     397           0 :     ResCount += PriorityOne;
     398             : 
     399             :   // Adaptable scheduling
     400             :   // A small, but very parallel
     401             :   // region, where reg pressure is an issue.
     402           0 :   if (HorizontalVerticalBalance > RegPressureThreshold) {
     403             :     // Critical path first
     404           0 :     ResCount += (SU->getHeight() * ScaleTwo);
     405             :     // If resources are available for it, multiply the
     406             :     // chance of scheduling.
     407           0 :     if (isResourceAvailable(SU))
     408           0 :       ResCount <<= FactorOne;
     409             : 
     410             :     // Consider change to reg pressure from scheduling
     411             :     // this SU.
     412           0 :     ResCount -= (regPressureDelta(SU,true) * ScaleOne);
     413             :   }
     414             :   // Default heuristic, greeady and
     415             :   // critical path driven.
     416             :   else {
     417             :     // Critical path first.
     418           0 :     ResCount += (SU->getHeight() * ScaleTwo);
     419             :     // Now see how many instructions is blocked by this SU.
     420           0 :     ResCount += (NumNodesSolelyBlocking[SU->NodeNum] * ScaleTwo);
     421             :     // If resources are available for it, multiply the
     422             :     // chance of scheduling.
     423           0 :     if (isResourceAvailable(SU))
     424           0 :       ResCount <<= FactorOne;
     425             : 
     426           0 :     ResCount -= (regPressureDelta(SU) * ScaleTwo);
     427             :   }
     428             : 
     429             :   // These are platform-specific things.
     430             :   // Will need to go into the back end
     431             :   // and accessed from here via a hook.
     432           0 :   for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) {
     433           0 :     if (N->isMachineOpcode()) {
     434           0 :       const MCInstrDesc &TID = TII->get(N->getMachineOpcode());
     435           0 :       if (TID.isCall())
     436           0 :         ResCount += (PriorityTwo + (ScaleThree*N->getNumValues()));
     437             :     }
     438             :     else
     439           0 :       switch (N->getOpcode()) {
     440             :       default:  break;
     441           0 :       case ISD::TokenFactor:
     442             :       case ISD::CopyFromReg:
     443             :       case ISD::CopyToReg:
     444           0 :         ResCount += PriorityFour;
     445           0 :         break;
     446             : 
     447           0 :       case ISD::INLINEASM:
     448           0 :         ResCount += PriorityThree;
     449           0 :         break;
     450             :       }
     451             :   }
     452             :   return ResCount;
     453             : }
     454             : 
     455             : 
     456             : /// Main resource tracking point.
     457           0 : void ResourcePriorityQueue::scheduledNode(SUnit *SU) {
     458             :   // Use NULL entry as an event marker to reset
     459             :   // the DFA state.
     460           0 :   if (!SU) {
     461           0 :     ResourcesModel->clearResources();
     462           0 :     Packet.clear();
     463             :     return;
     464             :   }
     465             : 
     466           0 :   const SDNode *ScegN = SU->getNode();
     467             :   // Update reg pressure tracking.
     468             :   // First update current node.
     469           0 :   if (ScegN->isMachineOpcode()) {
     470             :     // Estimate generated regs.
     471           0 :     for (unsigned i = 0, e = ScegN->getNumValues(); i != e; ++i) {
     472           0 :       MVT VT = ScegN->getSimpleValueType(i);
     473             : 
     474           0 :       if (TLI->isTypeLegal(VT)) {
     475           0 :         const TargetRegisterClass *RC = TLI->getRegClassFor(VT);
     476           0 :         if (RC)
     477           0 :           RegPressure[RC->getID()] += numberRCValSuccInSU(SU, RC->getID());
     478             :       }
     479             :     }
     480             :     // Estimate killed regs.
     481           0 :     for (unsigned i = 0, e = ScegN->getNumOperands(); i != e; ++i) {
     482           0 :       const SDValue &Op = ScegN->getOperand(i);
     483           0 :       MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo());
     484             : 
     485           0 :       if (TLI->isTypeLegal(VT)) {
     486           0 :         const TargetRegisterClass *RC = TLI->getRegClassFor(VT);
     487           0 :         if (RC) {
     488           0 :           if (RegPressure[RC->getID()] >
     489           0 :             (numberRCValPredInSU(SU, RC->getID())))
     490           0 :             RegPressure[RC->getID()] -= numberRCValPredInSU(SU, RC->getID());
     491           0 :           else RegPressure[RC->getID()] = 0;
     492             :         }
     493             :       }
     494             :     }
     495           0 :     for (SDep &Pred : SU->Preds) {
     496           0 :       if (Pred.isCtrl() || (Pred.getSUnit()->NumRegDefsLeft == 0))
     497           0 :         continue;
     498           0 :       --Pred.getSUnit()->NumRegDefsLeft;
     499             :     }
     500             :   }
     501             : 
     502             :   // Reserve resources for this SU.
     503           0 :   reserveResources(SU);
     504             : 
     505             :   // Adjust number of parallel live ranges.
     506             :   // Heuristic is simple - node with no data successors reduces
     507             :   // number of live ranges. All others, increase it.
     508           0 :   unsigned NumberNonControlDeps = 0;
     509             : 
     510           0 :   for (const SDep &Succ : SU->Succs) {
     511           0 :     adjustPriorityOfUnscheduledPreds(Succ.getSUnit());
     512           0 :     if (!Succ.isCtrl())
     513           0 :       NumberNonControlDeps++;
     514             :   }
     515             : 
     516           0 :   if (!NumberNonControlDeps) {
     517           0 :     if (ParallelLiveRanges >= SU->NumPreds)
     518           0 :       ParallelLiveRanges -= SU->NumPreds;
     519             :     else
     520           0 :       ParallelLiveRanges = 0;
     521             : 
     522             :   }
     523             :   else
     524           0 :     ParallelLiveRanges += SU->NumRegDefsLeft;
     525             : 
     526             :   // Track parallel live chains.
     527           0 :   HorizontalVerticalBalance += (SU->Succs.size() - numberCtrlDepsInSU(SU));
     528           0 :   HorizontalVerticalBalance -= (SU->Preds.size() - numberCtrlPredInSU(SU));
     529             : }
     530             : 
     531           0 : void ResourcePriorityQueue::initNumRegDefsLeft(SUnit *SU) {
     532           0 :   unsigned  NodeNumDefs = 0;
     533           0 :   for (SDNode *N = SU->getNode(); N; N = N->getGluedNode())
     534           0 :     if (N->isMachineOpcode()) {
     535           0 :       const MCInstrDesc &TID = TII->get(N->getMachineOpcode());
     536             :       // No register need be allocated for this.
     537           0 :       if (N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF) {
     538             :         NodeNumDefs = 0;
     539             :         break;
     540             :       }
     541           0 :       NodeNumDefs = std::min(N->getNumValues(), TID.getNumDefs());
     542             :     }
     543             :     else
     544           0 :       switch(N->getOpcode()) {
     545             :         default:     break;
     546           0 :         case ISD::CopyFromReg:
     547           0 :           NodeNumDefs++;
     548           0 :           break;
     549           0 :         case ISD::INLINEASM:
     550           0 :           NodeNumDefs++;
     551           0 :           break;
     552             :       }
     553             : 
     554           0 :   SU->NumRegDefsLeft = NodeNumDefs;
     555           0 : }
     556             : 
     557             : /// adjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just
     558             : /// scheduled.  If SU is not itself available, then there is at least one
     559             : /// predecessor node that has not been scheduled yet.  If SU has exactly ONE
     560             : /// unscheduled predecessor, we want to increase its priority: it getting
     561             : /// scheduled will make this node available, so it is better than some other
     562             : /// node of the same priority that will not make a node available.
     563           0 : void ResourcePriorityQueue::adjustPriorityOfUnscheduledPreds(SUnit *SU) {
     564           0 :   if (SU->isAvailable) return;  // All preds scheduled.
     565             : 
     566           0 :   SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU);
     567           0 :   if (!OnlyAvailablePred || !OnlyAvailablePred->isAvailable)
     568             :     return;
     569             : 
     570             :   // Okay, we found a single predecessor that is available, but not scheduled.
     571             :   // Since it is available, it must be in the priority queue.  First remove it.
     572           0 :   remove(OnlyAvailablePred);
     573             : 
     574             :   // Reinsert the node into the priority queue, which recomputes its
     575             :   // NumNodesSolelyBlocking value.
     576           0 :   push(OnlyAvailablePred);
     577             : }
     578             : 
     579             : 
     580             : /// Main access point - returns next instructions
     581             : /// to be placed in scheduling sequence.
     582           0 : SUnit *ResourcePriorityQueue::pop() {
     583           0 :   if (empty())
     584             :     return nullptr;
     585             : 
     586           0 :   std::vector<SUnit *>::iterator Best = Queue.begin();
     587           0 :   if (!DisableDFASched) {
     588           0 :     int BestCost = SUSchedulingCost(*Best);
     589           0 :     for (auto I = std::next(Queue.begin()), E = Queue.end(); I != E; ++I) {
     590             : 
     591           0 :       if (SUSchedulingCost(*I) > BestCost) {
     592           0 :         BestCost = SUSchedulingCost(*I);
     593           0 :         Best = I;
     594             :       }
     595             :     }
     596             :   }
     597             :   // Use default TD scheduling mechanism.
     598             :   else {
     599           0 :     for (auto I = std::next(Queue.begin()), E = Queue.end(); I != E; ++I)
     600           0 :       if (Picker(*Best, *I))
     601           0 :         Best = I;
     602             :   }
     603             : 
     604           0 :   SUnit *V = *Best;
     605           0 :   if (Best != std::prev(Queue.end()))
     606           0 :     std::swap(*Best, Queue.back());
     607             : 
     608           0 :   Queue.pop_back();
     609             : 
     610           0 :   return V;
     611             : }
     612             : 
     613             : 
     614           0 : void ResourcePriorityQueue::remove(SUnit *SU) {
     615             :   assert(!Queue.empty() && "Queue is empty!");
     616           0 :   std::vector<SUnit *>::iterator I = find(Queue, SU);
     617           0 :   if (I != std::prev(Queue.end()))
     618           0 :     std::swap(*I, Queue.back());
     619             : 
     620           0 :   Queue.pop_back();
     621      216918 : }

Generated by: LCOV version 1.13