LCOV - code coverage report
Current view: top level - lib/CodeGen/SelectionDAG - ResourcePriorityQueue.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 0 222 0.0 %
Date: 2018-10-20 13:21:21 Functions: 0 17 0.0 %
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/CodeGen/TargetLowering.h"
      26             : #include "llvm/CodeGen/TargetSubtargetInfo.h"
      27             : #include "llvm/Support/CommandLine.h"
      28             : #include "llvm/Support/Debug.h"
      29             : #include "llvm/Support/raw_ostream.h"
      30             : #include "llvm/Target/TargetMachine.h"
      31             : 
      32             : using namespace llvm;
      33             : 
      34             : #define DEBUG_TYPE "scheduler"
      35             : 
      36             : static cl::opt<bool> DisableDFASched("disable-dfa-sched", cl::Hidden,
      37             :   cl::ZeroOrMore, cl::init(false),
      38             :   cl::desc("Disable use of DFA during scheduling"));
      39             : 
      40             : static cl::opt<int> RegPressureThreshold(
      41             :   "dfa-sched-reg-pressure-threshold", cl::Hidden, cl::ZeroOrMore, cl::init(5),
      42             :   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             :   std::fill(RegLimit.begin(), RegLimit.end(), 0);
      59             :   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             :   unsigned NumberDeps = 0;
      70           0 :   for (SDep &Pred : SU->Preds) {
      71           0 :     if (Pred.isCtrl())
      72             :       continue;
      73             : 
      74             :     SUnit *PredSU = Pred.getSUnit();
      75           0 :     const SDNode *ScegN = PredSU->getNode();
      76             : 
      77           0 :     if (!ScegN)
      78             :       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             :       continue;
      91             : 
      92           0 :     for (unsigned i = 0, e = ScegN->getNumValues(); i != e; ++i) {
      93             :       MVT VT = ScegN->getSimpleValueType(i);
      94           0 :       if (TLI->isTypeLegal(VT)
      95           0 :           && (TLI->getRegClassFor(VT)->getID() == RCId)) {
      96           0 :         NumberDeps++;
      97             :         break;
      98             :       }
      99             :     }
     100             :   }
     101           0 :   return NumberDeps;
     102             : }
     103             : 
     104           0 : unsigned ResourcePriorityQueue::numberRCValSuccInSU(SUnit *SU,
     105             :                                                     unsigned RCId) {
     106             :   unsigned NumberDeps = 0;
     107           0 :   for (const SDep &Succ : SU->Succs) {
     108           0 :     if (Succ.isCtrl())
     109             :       continue;
     110             : 
     111             :     SUnit *SuccSU = Succ.getSUnit();
     112           0 :     const SDNode *ScegN = SuccSU->getNode();
     113           0 :     if (!ScegN)
     114             :       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             :       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             :         break;
     135             :       }
     136             :     }
     137             :   }
     138           0 :   return NumberDeps;
     139             : }
     140             : 
     141             : static unsigned numberCtrlDepsInSU(SUnit *SU) {
     142             :   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             :   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             :   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             :   SUnit *OnlyAvailablePred = nullptr;
     211           0 :   for (const SDep &Pred : SU->Preds) {
     212             :     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             :   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             :   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             :     switch (SU->getNode()->getMachineOpcode()) {
     251           0 :     default:
     252           0 :       if (!ResourcesModel->canReserveResources(&TII->get(
     253           0 :           SU->getNode()->getMachineOpcode())))
     254             :            return false;
     255             :       break;
     256             :     case TargetOpcode::EXTRACT_SUBREG:
     257             :     case TargetOpcode::INSERT_SUBREG:
     258             :     case TargetOpcode::SUBREG_TO_REG:
     259             :     case TargetOpcode::REG_SEQUENCE:
     260             :     case TargetOpcode::IMPLICIT_DEF:
     261             :         break;
     262             :     }
     263             : 
     264             :   // Now see if there are no other dependencies
     265             :   // to instructions already in the packet.
     266           0 :   for (unsigned i = 0, e = Packet.size(); i != e; ++i)
     267           0 :     for (const SDep &Succ : Packet[i]->Succs) {
     268             :       // Since we do not add pseudos to packets, might as well
     269             :       // ignore order deps.
     270           0 :       if (Succ.isCtrl())
     271             :         continue;
     272             : 
     273           0 :       if (Succ.getSUnit() == SU)
     274             :         return false;
     275             :     }
     276             : 
     277             :   return true;
     278             : }
     279             : 
     280             : /// Keep track of available resources.
     281           0 : void ResourcePriorityQueue::reserveResources(SUnit *SU) {
     282             :   // If this SU does not fit in the packet
     283             :   // start a new one.
     284           0 :   if (!isResourceAvailable(SU) || SU->getNode()->getGluedNode()) {
     285             :     ResourcesModel->clearResources();
     286             :     Packet.clear();
     287             :   }
     288             : 
     289           0 :   if (SU->getNode() && SU->getNode()->isMachineOpcode()) {
     290             :     switch (SU->getNode()->getMachineOpcode()) {
     291           0 :     default:
     292           0 :       ResourcesModel->reserveResources(&TII->get(
     293           0 :         SU->getNode()->getMachineOpcode()));
     294           0 :       break;
     295             :     case TargetOpcode::EXTRACT_SUBREG:
     296             :     case TargetOpcode::INSERT_SUBREG:
     297             :     case TargetOpcode::SUBREG_TO_REG:
     298             :     case TargetOpcode::REG_SEQUENCE:
     299             :     case TargetOpcode::IMPLICIT_DEF:
     300             :       break;
     301             :     }
     302           0 :     Packet.push_back(SU);
     303             :   }
     304             :   // Forcefully end packet for PseudoOps.
     305             :   else {
     306             :     ResourcesModel->clearResources();
     307             :     Packet.clear();
     308             :   }
     309             : 
     310             :   // If packet is now full, reset the state so in the next cycle
     311             :   // we start fresh.
     312           0 :   if (Packet.size() >= InstrItins->SchedModel.IssueWidth) {
     313             :     ResourcesModel->clearResources();
     314             :     Packet.clear();
     315             :   }
     316           0 : }
     317             : 
     318           0 : int ResourcePriorityQueue::rawRegPressureDelta(SUnit *SU, unsigned RCId) {
     319             :   int RegBalance = 0;
     320             : 
     321           0 :   if (!SU || !SU->getNode() || !SU->getNode()->isMachineOpcode())
     322             :     return RegBalance;
     323             : 
     324             :   // Gen estimate.
     325           0 :   for (unsigned i = 0, e = SU->getNode()->getNumValues(); i != e; ++i) {
     326           0 :       MVT VT = SU->getNode()->getSimpleValueType(i);
     327           0 :       if (TLI->isTypeLegal(VT)
     328           0 :           && TLI->getRegClassFor(VT)
     329           0 :           && TLI->getRegClassFor(VT)->getID() == RCId)
     330           0 :         RegBalance += numberRCValSuccInSU(SU, RCId);
     331             :   }
     332             :   // Kill estimate.
     333           0 :   for (unsigned i = 0, e = SU->getNode()->getNumOperands(); i != e; ++i) {
     334           0 :       const SDValue &Op = SU->getNode()->getOperand(i);
     335           0 :       MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo());
     336             :       if (isa<ConstantSDNode>(Op.getNode()))
     337             :         continue;
     338             : 
     339           0 :       if (TLI->isTypeLegal(VT) && TLI->getRegClassFor(VT)
     340           0 :           && TLI->getRegClassFor(VT)->getID() == RCId)
     341           0 :         RegBalance -= numberRCValPredInSU(SU, RCId);
     342             :   }
     343             :   return RegBalance;
     344             : }
     345             : 
     346             : /// Estimates change in reg pressure from this SU.
     347             : /// It is achieved by trivial tracking of defined
     348             : /// and used vregs in dependent instructions.
     349             : /// The RawPressure flag makes this function to ignore
     350             : /// existing reg file sizes, and report raw def/use
     351             : /// balance.
     352           0 : int ResourcePriorityQueue::regPressureDelta(SUnit *SU, bool RawPressure) {
     353             :   int RegBalance = 0;
     354             : 
     355           0 :   if (!SU || !SU->getNode() || !SU->getNode()->isMachineOpcode())
     356             :     return RegBalance;
     357             : 
     358           0 :   if (RawPressure) {
     359           0 :     for (const TargetRegisterClass *RC : TRI->regclasses())
     360           0 :       RegBalance += rawRegPressureDelta(SU, RC->getID());
     361             :   }
     362             :   else {
     363           0 :     for (const TargetRegisterClass *RC : TRI->regclasses()) {
     364           0 :       if ((RegPressure[RC->getID()] +
     365           0 :            rawRegPressureDelta(SU, RC->getID()) > 0) &&
     366           0 :           (RegPressure[RC->getID()] +
     367           0 :            rawRegPressureDelta(SU, RC->getID())  >= RegLimit[RC->getID()]))
     368           0 :         RegBalance += rawRegPressureDelta(SU, RC->getID());
     369             :     }
     370             :   }
     371             : 
     372             :   return RegBalance;
     373             : }
     374             : 
     375             : // Constants used to denote relative importance of
     376             : // heuristic components for cost computation.
     377             : static const unsigned PriorityOne = 200;
     378             : static const unsigned PriorityTwo = 50;
     379             : static const unsigned PriorityThree = 15;
     380             : static const unsigned PriorityFour = 5;
     381             : static const unsigned ScaleOne = 20;
     382             : static const unsigned ScaleTwo = 10;
     383             : static const unsigned ScaleThree = 5;
     384             : static const unsigned FactorOne = 2;
     385             : 
     386             : /// Returns single number reflecting benefit of scheduling SU
     387             : /// in the current cycle.
     388           0 : int ResourcePriorityQueue::SUSchedulingCost(SUnit *SU) {
     389             :   // Initial trivial priority.
     390             :   int ResCount = 1;
     391             : 
     392             :   // Do not waste time on a node that is already scheduled.
     393           0 :   if (SU->isScheduled)
     394             :     return ResCount;
     395             : 
     396             :   // Forced priority is high.
     397           0 :   if (SU->isScheduleHigh)
     398             :     ResCount += PriorityOne;
     399             : 
     400             :   // Adaptable scheduling
     401             :   // A small, but very parallel
     402             :   // region, where reg pressure is an issue.
     403           0 :   if (HorizontalVerticalBalance > RegPressureThreshold) {
     404             :     // Critical path first
     405           0 :     ResCount += (SU->getHeight() * ScaleTwo);
     406             :     // If resources are available for it, multiply the
     407             :     // chance of scheduling.
     408           0 :     if (isResourceAvailable(SU))
     409           0 :       ResCount <<= FactorOne;
     410             : 
     411             :     // Consider change to reg pressure from scheduling
     412             :     // this SU.
     413           0 :     ResCount -= (regPressureDelta(SU,true) * ScaleOne);
     414             :   }
     415             :   // Default heuristic, greeady and
     416             :   // critical path driven.
     417             :   else {
     418             :     // Critical path first.
     419           0 :     ResCount += (SU->getHeight() * ScaleTwo);
     420             :     // Now see how many instructions is blocked by this SU.
     421           0 :     ResCount += (NumNodesSolelyBlocking[SU->NodeNum] * ScaleTwo);
     422             :     // If resources are available for it, multiply the
     423             :     // chance of scheduling.
     424           0 :     if (isResourceAvailable(SU))
     425           0 :       ResCount <<= FactorOne;
     426             : 
     427           0 :     ResCount -= (regPressureDelta(SU) * ScaleTwo);
     428             :   }
     429             : 
     430             :   // These are platform-specific things.
     431             :   // Will need to go into the back end
     432             :   // and accessed from here via a hook.
     433           0 :   for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) {
     434           0 :     if (N->isMachineOpcode()) {
     435           0 :       const MCInstrDesc &TID = TII->get(N->getMachineOpcode());
     436           0 :       if (TID.isCall())
     437           0 :         ResCount += (PriorityTwo + (ScaleThree*N->getNumValues()));
     438             :     }
     439             :     else
     440           0 :       switch (N->getOpcode()) {
     441             :       default:  break;
     442           0 :       case ISD::TokenFactor:
     443             :       case ISD::CopyFromReg:
     444             :       case ISD::CopyToReg:
     445           0 :         ResCount += PriorityFour;
     446           0 :         break;
     447             : 
     448           0 :       case ISD::INLINEASM:
     449           0 :         ResCount += PriorityThree;
     450           0 :         break;
     451             :       }
     452             :   }
     453             :   return ResCount;
     454             : }
     455             : 
     456             : 
     457             : /// Main resource tracking point.
     458           0 : void ResourcePriorityQueue::scheduledNode(SUnit *SU) {
     459             :   // Use NULL entry as an event marker to reset
     460             :   // the DFA state.
     461           0 :   if (!SU) {
     462             :     ResourcesModel->clearResources();
     463             :     Packet.clear();
     464           0 :     return;
     465             :   }
     466             : 
     467           0 :   const SDNode *ScegN = SU->getNode();
     468             :   // Update reg pressure tracking.
     469             :   // First update current node.
     470           0 :   if (ScegN->isMachineOpcode()) {
     471             :     // Estimate generated regs.
     472           0 :     for (unsigned i = 0, e = ScegN->getNumValues(); i != e; ++i) {
     473             :       MVT VT = ScegN->getSimpleValueType(i);
     474             : 
     475           0 :       if (TLI->isTypeLegal(VT)) {
     476           0 :         const TargetRegisterClass *RC = TLI->getRegClassFor(VT);
     477           0 :         if (RC)
     478           0 :           RegPressure[RC->getID()] += numberRCValSuccInSU(SU, RC->getID());
     479             :       }
     480             :     }
     481             :     // Estimate killed regs.
     482           0 :     for (unsigned i = 0, e = ScegN->getNumOperands(); i != e; ++i) {
     483           0 :       const SDValue &Op = ScegN->getOperand(i);
     484           0 :       MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo());
     485             : 
     486           0 :       if (TLI->isTypeLegal(VT)) {
     487           0 :         const TargetRegisterClass *RC = TLI->getRegClassFor(VT);
     488           0 :         if (RC) {
     489           0 :           if (RegPressure[RC->getID()] >
     490           0 :             (numberRCValPredInSU(SU, RC->getID())))
     491           0 :             RegPressure[RC->getID()] -= numberRCValPredInSU(SU, RC->getID());
     492           0 :           else RegPressure[RC->getID()] = 0;
     493             :         }
     494             :       }
     495             :     }
     496           0 :     for (SDep &Pred : SU->Preds) {
     497           0 :       if (Pred.isCtrl() || (Pred.getSUnit()->NumRegDefsLeft == 0))
     498             :         continue;
     499           0 :       --Pred.getSUnit()->NumRegDefsLeft;
     500             :     }
     501             :   }
     502             : 
     503             :   // Reserve resources for this SU.
     504           0 :   reserveResources(SU);
     505             : 
     506             :   // Adjust number of parallel live ranges.
     507             :   // Heuristic is simple - node with no data successors reduces
     508             :   // number of live ranges. All others, increase it.
     509             :   unsigned NumberNonControlDeps = 0;
     510             : 
     511           0 :   for (const SDep &Succ : SU->Succs) {
     512           0 :     adjustPriorityOfUnscheduledPreds(Succ.getSUnit());
     513           0 :     if (!Succ.isCtrl())
     514           0 :       NumberNonControlDeps++;
     515             :   }
     516             : 
     517           0 :   if (!NumberNonControlDeps) {
     518           0 :     if (ParallelLiveRanges >= SU->NumPreds)
     519           0 :       ParallelLiveRanges -= SU->NumPreds;
     520             :     else
     521           0 :       ParallelLiveRanges = 0;
     522             : 
     523             :   }
     524             :   else
     525           0 :     ParallelLiveRanges += SU->NumRegDefsLeft;
     526             : 
     527             :   // Track parallel live chains.
     528           0 :   HorizontalVerticalBalance += (SU->Succs.size() - numberCtrlDepsInSU(SU));
     529           0 :   HorizontalVerticalBalance -= (SU->Preds.size() - numberCtrlPredInSU(SU));
     530             : }
     531             : 
     532           0 : void ResourcePriorityQueue::initNumRegDefsLeft(SUnit *SU) {
     533             :   unsigned  NodeNumDefs = 0;
     534           0 :   for (SDNode *N = SU->getNode(); N; N = N->getGluedNode())
     535           0 :     if (N->isMachineOpcode()) {
     536           0 :       const MCInstrDesc &TID = TII->get(N->getMachineOpcode());
     537             :       // No register need be allocated for this.
     538           0 :       if (N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF) {
     539             :         NodeNumDefs = 0;
     540             :         break;
     541             :       }
     542           0 :       NodeNumDefs = std::min(N->getNumValues(), TID.getNumDefs());
     543             :     }
     544             :     else
     545           0 :       switch(N->getOpcode()) {
     546             :         default:     break;
     547           0 :         case ISD::CopyFromReg:
     548           0 :           NodeNumDefs++;
     549           0 :           break;
     550           0 :         case ISD::INLINEASM:
     551           0 :           NodeNumDefs++;
     552           0 :           break;
     553             :       }
     554             : 
     555           0 :   SU->NumRegDefsLeft = NodeNumDefs;
     556           0 : }
     557             : 
     558             : /// adjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just
     559             : /// scheduled.  If SU is not itself available, then there is at least one
     560             : /// predecessor node that has not been scheduled yet.  If SU has exactly ONE
     561             : /// unscheduled predecessor, we want to increase its priority: it getting
     562             : /// scheduled will make this node available, so it is better than some other
     563             : /// node of the same priority that will not make a node available.
     564           0 : void ResourcePriorityQueue::adjustPriorityOfUnscheduledPreds(SUnit *SU) {
     565           0 :   if (SU->isAvailable) return;  // All preds scheduled.
     566             : 
     567           0 :   SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU);
     568           0 :   if (!OnlyAvailablePred || !OnlyAvailablePred->isAvailable)
     569             :     return;
     570             : 
     571             :   // Okay, we found a single predecessor that is available, but not scheduled.
     572             :   // Since it is available, it must be in the priority queue.  First remove it.
     573           0 :   remove(OnlyAvailablePred);
     574             : 
     575             :   // Reinsert the node into the priority queue, which recomputes its
     576             :   // NumNodesSolelyBlocking value.
     577           0 :   push(OnlyAvailablePred);
     578             : }
     579             : 
     580             : 
     581             : /// Main access point - returns next instructions
     582             : /// to be placed in scheduling sequence.
     583           0 : SUnit *ResourcePriorityQueue::pop() {
     584           0 :   if (empty())
     585             :     return nullptr;
     586             : 
     587             :   std::vector<SUnit *>::iterator Best = Queue.begin();
     588           0 :   if (!DisableDFASched) {
     589           0 :     int BestCost = SUSchedulingCost(*Best);
     590           0 :     for (auto I = std::next(Queue.begin()), E = Queue.end(); I != E; ++I) {
     591             : 
     592           0 :       if (SUSchedulingCost(*I) > BestCost) {
     593           0 :         BestCost = SUSchedulingCost(*I);
     594             :         Best = I;
     595             :       }
     596             :     }
     597             :   }
     598             :   // Use default TD scheduling mechanism.
     599             :   else {
     600           0 :     for (auto I = std::next(Queue.begin()), E = Queue.end(); I != E; ++I)
     601           0 :       if (Picker(*Best, *I))
     602             :         Best = I;
     603             :   }
     604             : 
     605           0 :   SUnit *V = *Best;
     606           0 :   if (Best != std::prev(Queue.end()))
     607             :     std::swap(*Best, Queue.back());
     608             : 
     609             :   Queue.pop_back();
     610             : 
     611           0 :   return V;
     612             : }
     613             : 
     614             : 
     615           0 : void ResourcePriorityQueue::remove(SUnit *SU) {
     616             :   assert(!Queue.empty() && "Queue is empty!");
     617             :   std::vector<SUnit *>::iterator I = find(Queue, SU);
     618           0 :   if (I != std::prev(Queue.end()))
     619             :     std::swap(*I, Queue.back());
     620             : 
     621             :   Queue.pop_back();
     622           0 : }

Generated by: LCOV version 1.13