contrib/llvm/lib/Target/Hexagon/HexagonMachineScheduler.cpp

   1 //===- HexagonMachineScheduler.cpp - MI Scheduler for Hexagon -------------===//
   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 // MachineScheduler schedules machine instructions after phi elimination. It
  11 // preserves LiveIntervals so it can be invoked before register allocation.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "HexagonMachineScheduler.h"
  16 #include "HexagonSubtarget.h"
  17 #include "llvm/CodeGen/MachineLoopInfo.h"
  18 #include "llvm/CodeGen/ScheduleDAGMutation.h"
  19 #include "llvm/IR/Function.h"
  20
  21 #include <iomanip>
  22 #include <sstream>
  23
  24 static cl::opt<bool> IgnoreBBRegPressure("ignore-bb-reg-pressure",
  25     cl::Hidden, cl::ZeroOrMore, cl::init(false));
  26
  27 static cl::opt<bool> SchedPredsCloser("sched-preds-closer",
  28     cl::Hidden, cl::ZeroOrMore, cl::init(true));
  29
  30 static cl::opt<unsigned> SchedDebugVerboseLevel("misched-verbose-level",
  31     cl::Hidden, cl::ZeroOrMore, cl::init(1));
  32
  33 static cl::opt<bool> TopUseShorterTie("top-use-shorter-tie",
  34     cl::Hidden, cl::ZeroOrMore, cl::init(false));
  35
  36 static cl::opt<bool> BotUseShorterTie("bot-use-shorter-tie",
  37     cl::Hidden, cl::ZeroOrMore, cl::init(false));
  38
  39 static cl::opt<bool> DisableTCTie("disable-tc-tie",
  40     cl::Hidden, cl::ZeroOrMore, cl::init(false));
  41
  42 static cl::opt<bool> SchedRetvalOptimization("sched-retval-optimization",
  43     cl::Hidden, cl::ZeroOrMore, cl::init(true));
  44
  45 // Check if the scheduler should penalize instructions that are available to
  46 // early due to a zero-latency dependence.
  47 static cl::opt<bool> CheckEarlyAvail("check-early-avail", cl::Hidden,
  48     cl::ZeroOrMore, cl::init(true));
  49
  50 using namespace llvm;
  51
  52 #define DEBUG_TYPE "misched"
  53
  54 class HexagonCallMutation : public ScheduleDAGMutation {
  55 public:
  56   void apply(ScheduleDAGInstrs *DAG) override;
  57 private:
  58   bool shouldTFRICallBind(const HexagonInstrInfo &HII,
  59                           const SUnit &Inst1, const SUnit &Inst2) const;
  60 };
  61
  62 // Check if a call and subsequent A2_tfrpi instructions should maintain
  63 // scheduling affinity. We are looking for the TFRI to be consumed in
  64 // the next instruction. This should help reduce the instances of
  65 // double register pairs being allocated and scheduled before a call
  66 // when not used until after the call. This situation is exacerbated
  67 // by the fact that we allocate the pair from the callee saves list,
  68 // leading to excess spills and restores.
  69 bool HexagonCallMutation::shouldTFRICallBind(const HexagonInstrInfo &HII,
  70       const SUnit &Inst1, const SUnit &Inst2) const {
  71   if (Inst1.getInstr()->getOpcode() != Hexagon::A2_tfrpi)
  72     return false;
  73
  74   // TypeXTYPE are 64 bit operations.
  75   if (HII.getType(Inst2.getInstr()) == HexagonII::TypeXTYPE)
  76     return true;
  77   return false;
  78 }
  79
  80 void HexagonCallMutation::apply(ScheduleDAGInstrs *DAG) {
  81   SUnit* LastSequentialCall = nullptr;
  82   unsigned VRegHoldingRet = 0;
  83   unsigned RetRegister;
  84   SUnit* LastUseOfRet = nullptr;
  85   auto &TRI = *DAG->MF.getSubtarget().getRegisterInfo();
  86   auto &HII = *DAG->MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
  87
  88   // Currently we only catch the situation when compare gets scheduled
  89   // before preceding call.
  90   for (unsigned su = 0, e = DAG->SUnits.size(); su != e; ++su) {
  91     // Remember the call.
  92     if (DAG->SUnits[su].getInstr()->isCall())
  93       LastSequentialCall = &DAG->SUnits[su];
  94     // Look for a compare that defines a predicate.
  95     else if (DAG->SUnits[su].getInstr()->isCompare() && LastSequentialCall)
  96       DAG->SUnits[su].addPred(SDep(LastSequentialCall, SDep::Barrier));
  97     // Look for call and tfri* instructions.
  98     else if (SchedPredsCloser && LastSequentialCall && su > 1 && su < e-1 &&
  99              shouldTFRICallBind(HII, DAG->SUnits[su], DAG->SUnits[su+1]))
 100       DAG->SUnits[su].addPred(SDep(&DAG->SUnits[su-1], SDep::Barrier));
 101     // Prevent redundant register copies between two calls, which are caused by
 102     // both the return value and the argument for the next call being in %R0.
 103     // Example:
 104     //   1: <call1>
 105     //   2: %VregX = COPY %R0
 106     //   3: <use of %VregX>
 107     //   4: %R0 = ...
 108     //   5: <call2>
 109     // The scheduler would often swap 3 and 4, so an additional register is
 110     // needed. This code inserts a Barrier dependence between 3 & 4 to prevent
 111     // this. The same applies for %D0 and %V0/%W0, which are also handled.
 112     else if (SchedRetvalOptimization) {
 113       const MachineInstr *MI = DAG->SUnits[su].getInstr();
 114       if (MI->isCopy() && (MI->readsRegister(Hexagon::R0, &TRI) ||
 115                            MI->readsRegister(Hexagon::V0, &TRI)))  {
 116         // %vregX = COPY %R0
 117         VRegHoldingRet = MI->getOperand(0).getReg();
 118         RetRegister = MI->getOperand(1).getReg();
 119         LastUseOfRet = nullptr;
 120       } else if (VRegHoldingRet && MI->readsVirtualRegister(VRegHoldingRet))
 121         // <use of %vregX>
 122         LastUseOfRet = &DAG->SUnits[su];
 123       else if (LastUseOfRet && MI->definesRegister(RetRegister, &TRI))
 124         // %R0 = ...
 125         DAG->SUnits[su].addPred(SDep(LastUseOfRet, SDep::Barrier));
 126     }
 127   }
 128 }
 129
 130
 131 /// Save the last formed packet
 132 void VLIWResourceModel::savePacket() {
 133   OldPacket = Packet;
 134 }
 135
 136 /// Check if scheduling of this SU is possible
 137 /// in the current packet.
 138 /// It is _not_ precise (statefull), it is more like
 139 /// another heuristic. Many corner cases are figured
 140 /// empirically.
 141 bool VLIWResourceModel::isResourceAvailable(SUnit *SU) {
 142   if (!SU || !SU->getInstr())
 143     return false;
 144
 145   // First see if the pipeline could receive this instruction
 146   // in the current cycle.
 147   switch (SU->getInstr()->getOpcode()) {
 148   default:
 149     if (!ResourcesModel->canReserveResources(*SU->getInstr()))
 150       return false;
 151   case TargetOpcode::EXTRACT_SUBREG:
 152   case TargetOpcode::INSERT_SUBREG:
 153   case TargetOpcode::SUBREG_TO_REG:
 154   case TargetOpcode::REG_SEQUENCE:
 155   case TargetOpcode::IMPLICIT_DEF:
 156   case TargetOpcode::COPY:
 157   case TargetOpcode::INLINEASM:
 158     break;
 159   }
 160
 161   MachineFunction &MF = *SU->getInstr()->getParent()->getParent();
 162   auto &QII = *MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
 163
 164   // Now see if there are no other dependencies to instructions already
 165   // in the packet.
 166   for (unsigned i = 0, e = Packet.size(); i != e; ++i) {
 167     if (Packet[i]->Succs.size() == 0)
 168       continue;
 169
 170     // Enable .cur formation.
 171     if (QII.mayBeCurLoad(Packet[i]->getInstr()))
 172       continue;
 173
 174     for (SUnit::const_succ_iterator I = Packet[i]->Succs.begin(),
 175          E = Packet[i]->Succs.end(); I != E; ++I) {
 176       // Since we do not add pseudos to packets, might as well
 177       // ignore order dependencies.
 178       if (I->isCtrl())
 179         continue;
 180
 181       if (I->getSUnit() == SU)
 182         return false;
 183     }
 184   }
 185   return true;
 186 }
 187
 188 /// Keep track of available resources.
 189 bool VLIWResourceModel::reserveResources(SUnit *SU) {
 190   bool startNewCycle = false;
 191   // Artificially reset state.
 192   if (!SU) {
 193     ResourcesModel->clearResources();
 194     savePacket();
 195     Packet.clear();
 196     TotalPackets++;
 197     return false;
 198   }
 199   // If this SU does not fit in the packet
 200   // start a new one.
 201   if (!isResourceAvailable(SU)) {
 202     ResourcesModel->clearResources();
 203     savePacket();
 204     Packet.clear();
 205     TotalPackets++;
 206     startNewCycle = true;
 207   }
 208
 209   switch (SU->getInstr()->getOpcode()) {
 210   default:
 211     ResourcesModel->reserveResources(*SU->getInstr());
 212     break;
 213   case TargetOpcode::EXTRACT_SUBREG:
 214   case TargetOpcode::INSERT_SUBREG:
 215   case TargetOpcode::SUBREG_TO_REG:
 216   case TargetOpcode::REG_SEQUENCE:
 217   case TargetOpcode::IMPLICIT_DEF:
 218   case TargetOpcode::KILL:
 219   case TargetOpcode::CFI_INSTRUCTION:
 220   case TargetOpcode::EH_LABEL:
 221   case TargetOpcode::COPY:
 222   case TargetOpcode::INLINEASM:
 223     break;
 224   }
 225   Packet.push_back(SU);
 226
 227 #ifndef NDEBUG
 228   DEBUG(dbgs() << "Packet[" << TotalPackets << "]:\n");
 229   for (unsigned i = 0, e = Packet.size(); i != e; ++i) {
 230     DEBUG(dbgs() << "\t[" << i << "] SU(");
 231     DEBUG(dbgs() << Packet[i]->NodeNum << ")\t");
 232     DEBUG(Packet[i]->getInstr()->dump());
 233   }
 234 #endif
 235
 236   // If packet is now full, reset the state so in the next cycle
 237   // we start fresh.
 238   if (Packet.size() >= SchedModel->getIssueWidth()) {
 239     ResourcesModel->clearResources();
 240     savePacket();
 241     Packet.clear();
 242     TotalPackets++;
 243     startNewCycle = true;
 244   }
 245
 246   return startNewCycle;
 247 }
 248
 249 /// schedule - Called back from MachineScheduler::runOnMachineFunction
 250 /// after setting up the current scheduling region. [RegionBegin, RegionEnd)
 251 /// only includes instructions that have DAG nodes, not scheduling boundaries.
 252 void VLIWMachineScheduler::schedule() {
 253   DEBUG(dbgs()
 254         << "********** MI Converging Scheduling VLIW BB#" << BB->getNumber()
 255         << " " << BB->getName()
 256         << " in_func " << BB->getParent()->getFunction()->getName()
 257         << " at loop depth "  << MLI->getLoopDepth(BB)
 258         << " \n");
 259
 260   buildDAGWithRegPressure();
 261
 262   SmallVector<SUnit*, 8> TopRoots, BotRoots;
 263   findRootsAndBiasEdges(TopRoots, BotRoots);
 264
 265   // Initialize the strategy before modifying the DAG.
 266   SchedImpl->initialize(this);
 267
 268   DEBUG(unsigned maxH = 0;
 269         for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
 270           if (SUnits[su].getHeight() > maxH)
 271             maxH = SUnits[su].getHeight();
 272         dbgs() << "Max Height " << maxH << "\n";);
 273   DEBUG(unsigned maxD = 0;
 274         for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
 275           if (SUnits[su].getDepth() > maxD)
 276             maxD = SUnits[su].getDepth();
 277         dbgs() << "Max Depth " << maxD << "\n";);
 278   DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
 279           SUnits[su].dumpAll(this));
 280
 281   initQueues(TopRoots, BotRoots);
 282
 283   bool IsTopNode = false;
 284   while (true) {
 285     DEBUG(dbgs() << "** VLIWMachineScheduler::schedule picking next node\n");
 286     SUnit *SU = SchedImpl->pickNode(IsTopNode);
 287     if (!SU) break;
 288
 289     if (!checkSchedLimit())
 290       break;
 291
 292     scheduleMI(SU, IsTopNode);
 293
 294     updateQueues(SU, IsTopNode);
 295
 296     // Notify the scheduling strategy after updating the DAG.
 297     SchedImpl->schedNode(SU, IsTopNode);
 298   }
 299   assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
 300
 301   placeDebugValues();
 302
 303   DEBUG({
 304     unsigned BBNum = begin()->getParent()->getNumber();
 305     dbgs() << "*** Final schedule for BB#" << BBNum << " ***\n";
 306     dumpSchedule();
 307     dbgs() << '\n';
 308   });
 309 }
 310
 311 void ConvergingVLIWScheduler::initialize(ScheduleDAGMI *dag) {
 312   DAG = static_cast<VLIWMachineScheduler*>(dag);
 313   SchedModel = DAG->getSchedModel();
 314
 315   Top.init(DAG, SchedModel);
 316   Bot.init(DAG, SchedModel);
 317
 318   // Initialize the HazardRecognizers. If itineraries don't exist, are empty, or
 319   // are disabled, then these HazardRecs will be disabled.
 320   const InstrItineraryData *Itin = DAG->getSchedModel()->getInstrItineraries();
 321   const TargetSubtargetInfo &STI = DAG->MF.getSubtarget();
 322   const TargetInstrInfo *TII = STI.getInstrInfo();
 323   delete Top.HazardRec;
 324   delete Bot.HazardRec;
 325   Top.HazardRec = TII->CreateTargetMIHazardRecognizer(Itin, DAG);
 326   Bot.HazardRec = TII->CreateTargetMIHazardRecognizer(Itin, DAG);
 327
 328   delete Top.ResourceModel;
 329   delete Bot.ResourceModel;
 330   Top.ResourceModel = new VLIWResourceModel(STI, DAG->getSchedModel());
 331   Bot.ResourceModel = new VLIWResourceModel(STI, DAG->getSchedModel());
 332
 333   assert((!llvm::ForceTopDown || !llvm::ForceBottomUp) &&
 334          "-misched-topdown incompatible with -misched-bottomup");
 335
 336   DAG->addMutation(make_unique<HexagonSubtarget::HexagonDAGMutation>());
 337   DAG->addMutation(make_unique<HexagonCallMutation>());
 338 }
 339
 340 void ConvergingVLIWScheduler::releaseTopNode(SUnit *SU) {
 341   if (SU->isScheduled)
 342     return;
 343
 344   for (const SDep &PI : SU->Preds) {
 345     unsigned PredReadyCycle = PI.getSUnit()->TopReadyCycle;
 346     unsigned MinLatency = PI.getLatency();
 347 #ifndef NDEBUG
 348     Top.MaxMinLatency = std::max(MinLatency, Top.MaxMinLatency);
 349 #endif
 350     if (SU->TopReadyCycle < PredReadyCycle + MinLatency)
 351       SU->TopReadyCycle = PredReadyCycle + MinLatency;
 352   }
 353   Top.releaseNode(SU, SU->TopReadyCycle);
 354 }
 355
 356 void ConvergingVLIWScheduler::releaseBottomNode(SUnit *SU) {
 357   if (SU->isScheduled)
 358     return;
 359
 360   assert(SU->getInstr() && "Scheduled SUnit must have instr");
 361
 362   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
 363        I != E; ++I) {
 364     unsigned SuccReadyCycle = I->getSUnit()->BotReadyCycle;
 365     unsigned MinLatency = I->getLatency();
 366 #ifndef NDEBUG
 367     Bot.MaxMinLatency = std::max(MinLatency, Bot.MaxMinLatency);
 368 #endif
 369     if (SU->BotReadyCycle < SuccReadyCycle + MinLatency)
 370       SU->BotReadyCycle = SuccReadyCycle + MinLatency;
 371   }
 372   Bot.releaseNode(SU, SU->BotReadyCycle);
 373 }
 374
 375 /// Does this SU have a hazard within the current instruction group.
 376 ///
 377 /// The scheduler supports two modes of hazard recognition. The first is the
 378 /// ScheduleHazardRecognizer API. It is a fully general hazard recognizer that
 379 /// supports highly complicated in-order reservation tables
 380 /// (ScoreboardHazardRecognizer) and arbitrary target-specific logic.
 381 ///
 382 /// The second is a streamlined mechanism that checks for hazards based on
 383 /// simple counters that the scheduler itself maintains. It explicitly checks
 384 /// for instruction dispatch limitations, including the number of micro-ops that
 385 /// can dispatch per cycle.
 386 ///
 387 /// TODO: Also check whether the SU must start a new group.
 388 bool ConvergingVLIWScheduler::VLIWSchedBoundary::checkHazard(SUnit *SU) {
 389   if (HazardRec->isEnabled())
 390     return HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard;
 391
 392   unsigned uops = SchedModel->getNumMicroOps(SU->getInstr());
 393   if (IssueCount + uops > SchedModel->getIssueWidth())
 394     return true;
 395
 396   return false;
 397 }
 398
 399 void ConvergingVLIWScheduler::VLIWSchedBoundary::releaseNode(SUnit *SU,
 400                                                      unsigned ReadyCycle) {
 401   if (ReadyCycle < MinReadyCycle)
 402     MinReadyCycle = ReadyCycle;
 403
 404   // Check for interlocks first. For the purpose of other heuristics, an
 405   // instruction that cannot issue appears as if it's not in the ReadyQueue.
 406   if (ReadyCycle > CurrCycle || checkHazard(SU))
 407
 408     Pending.push(SU);
 409   else
 410     Available.push(SU);
 411 }
 412
 413 /// Move the boundary of scheduled code by one cycle.
 414 void ConvergingVLIWScheduler::VLIWSchedBoundary::bumpCycle() {
 415   unsigned Width = SchedModel->getIssueWidth();
 416   IssueCount = (IssueCount <= Width) ? 0 : IssueCount - Width;
 417
 418   assert(MinReadyCycle < UINT_MAX && "MinReadyCycle uninitialized");
 419   unsigned NextCycle = std::max(CurrCycle + 1, MinReadyCycle);
 420
 421   if (!HazardRec->isEnabled()) {
 422     // Bypass HazardRec virtual calls.
 423     CurrCycle = NextCycle;
 424   } else {
 425     // Bypass getHazardType calls in case of long latency.
 426     for (; CurrCycle != NextCycle; ++CurrCycle) {
 427       if (isTop())
 428         HazardRec->AdvanceCycle();
 429       else
 430         HazardRec->RecedeCycle();
 431     }
 432   }
 433   CheckPending = true;
 434
 435   DEBUG(dbgs() << "*** Next cycle " << Available.getName() << " cycle "
 436                << CurrCycle << '\n');
 437 }
 438
 439 /// Move the boundary of scheduled code by one SUnit.
 440 void ConvergingVLIWScheduler::VLIWSchedBoundary::bumpNode(SUnit *SU) {
 441   bool startNewCycle = false;
 442
 443   // Update the reservation table.
 444   if (HazardRec->isEnabled()) {
 445     if (!isTop() && SU->isCall) {
 446       // Calls are scheduled with their preceding instructions. For bottom-up
 447       // scheduling, clear the pipeline state before emitting.
 448       HazardRec->Reset();
 449     }
 450     HazardRec->EmitInstruction(SU);
 451   }
 452
 453   // Update DFA model.
 454   startNewCycle = ResourceModel->reserveResources(SU);
 455
 456   // Check the instruction group dispatch limit.
 457   // TODO: Check if this SU must end a dispatch group.
 458   IssueCount += SchedModel->getNumMicroOps(SU->getInstr());
 459   if (startNewCycle) {
 460     DEBUG(dbgs() << "*** Max instrs at cycle " << CurrCycle << '\n');
 461     bumpCycle();
 462   }
 463   else
 464     DEBUG(dbgs() << "*** IssueCount " << IssueCount
 465           << " at cycle " << CurrCycle << '\n');
 466 }
 467
 468 /// Release pending ready nodes in to the available queue. This makes them
 469 /// visible to heuristics.
 470 void ConvergingVLIWScheduler::VLIWSchedBoundary::releasePending() {
 471   // If the available queue is empty, it is safe to reset MinReadyCycle.
 472   if (Available.empty())
 473     MinReadyCycle = UINT_MAX;
 474
 475   // Check to see if any of the pending instructions are ready to issue.  If
 476   // so, add them to the available queue.
 477   for (unsigned i = 0, e = Pending.size(); i != e; ++i) {
 478     SUnit *SU = *(Pending.begin()+i);
 479     unsigned ReadyCycle = isTop() ? SU->TopReadyCycle : SU->BotReadyCycle;
 480
 481     if (ReadyCycle < MinReadyCycle)
 482       MinReadyCycle = ReadyCycle;
 483
 484     if (ReadyCycle > CurrCycle)
 485       continue;
 486
 487     if (checkHazard(SU))
 488       continue;
 489
 490     Available.push(SU);
 491     Pending.remove(Pending.begin()+i);
 492     --i; --e;
 493   }
 494   CheckPending = false;
 495 }
 496
 497 /// Remove SU from the ready set for this boundary.
 498 void ConvergingVLIWScheduler::VLIWSchedBoundary::removeReady(SUnit *SU) {
 499   if (Available.isInQueue(SU))
 500     Available.remove(Available.find(SU));
 501   else {
 502     assert(Pending.isInQueue(SU) && "bad ready count");
 503     Pending.remove(Pending.find(SU));
 504   }
 505 }
 506
 507 /// If this queue only has one ready candidate, return it. As a side effect,
 508 /// advance the cycle until at least one node is ready. If multiple instructions
 509 /// are ready, return NULL.
 510 SUnit *ConvergingVLIWScheduler::VLIWSchedBoundary::pickOnlyChoice() {
 511   if (CheckPending)
 512     releasePending();
 513
 514   for (unsigned i = 0; Available.empty(); ++i) {
 515     assert(i <= (HazardRec->getMaxLookAhead() + MaxMinLatency) &&
 516            "permanent hazard"); (void)i;
 517     ResourceModel->reserveResources(nullptr);
 518     bumpCycle();
 519     releasePending();
 520   }
 521   if (Available.size() == 1)
 522     return *Available.begin();
 523   return nullptr;
 524 }
 525
 526 #ifndef NDEBUG
 527 void ConvergingVLIWScheduler::traceCandidate(const char *Label,
 528       const ReadyQueue &Q, SUnit *SU, int Cost, PressureChange P) {
 529   dbgs() << Label << " " << Q.getName() << " ";
 530   if (P.isValid())
 531     dbgs() << DAG->TRI->getRegPressureSetName(P.getPSet()) << ":"
 532            << P.getUnitInc() << " ";
 533   else
 534     dbgs() << "     ";
 535   dbgs() << "cost(" << Cost << ")\t";
 536   SU->dump(DAG);
 537 }
 538
 539 // Very detailed queue dump, to be used with higher verbosity levels.
 540 void ConvergingVLIWScheduler::readyQueueVerboseDump(
 541       const RegPressureTracker &RPTracker, SchedCandidate &Candidate,
 542       ReadyQueue &Q) {
 543   RegPressureTracker &TempTracker = const_cast<RegPressureTracker &>(RPTracker);
 544
 545   dbgs() << ">>> " << Q.getName() << "\n";
 546   for (ReadyQueue::iterator I = Q.begin(), E = Q.end(); I != E; ++I) {
 547     RegPressureDelta RPDelta;
 548     TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta,
 549                                     DAG->getRegionCriticalPSets(),
 550                                     DAG->getRegPressure().MaxSetPressure);
 551     std::stringstream dbgstr;
 552     dbgstr << "SU(" << std::setw(3) << (*I)->NodeNum << ")";
 553     dbgs() << dbgstr.str();
 554     SchedulingCost(Q, *I, Candidate, RPDelta, true);
 555     dbgs() << "\t";
 556     (*I)->getInstr()->dump();
 557   }
 558   dbgs() << "\n";
 559 }
 560 #endif
 561
 562 /// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor
 563 /// of SU, return it, otherwise return null.
 564 static SUnit *getSingleUnscheduledPred(SUnit *SU) {
 565   SUnit *OnlyAvailablePred = nullptr;
 566   for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
 567        I != E; ++I) {
 568     SUnit &Pred = *I->getSUnit();
 569     if (!Pred.isScheduled) {
 570       // We found an available, but not scheduled, predecessor.  If it's the
 571       // only one we have found, keep track of it... otherwise give up.
 572       if (OnlyAvailablePred && OnlyAvailablePred != &Pred)
 573         return nullptr;
 574       OnlyAvailablePred = &Pred;
 575     }
 576   }
 577   return OnlyAvailablePred;
 578 }
 579
 580 /// getSingleUnscheduledSucc - If there is exactly one unscheduled successor
 581 /// of SU, return it, otherwise return null.
 582 static SUnit *getSingleUnscheduledSucc(SUnit *SU) {
 583   SUnit *OnlyAvailableSucc = nullptr;
 584   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
 585        I != E; ++I) {
 586     SUnit &Succ = *I->getSUnit();
 587     if (!Succ.isScheduled) {
 588       // We found an available, but not scheduled, successor.  If it's the
 589       // only one we have found, keep track of it... otherwise give up.
 590       if (OnlyAvailableSucc && OnlyAvailableSucc != &Succ)
 591         return nullptr;
 592       OnlyAvailableSucc = &Succ;
 593     }
 594   }
 595   return OnlyAvailableSucc;
 596 }
 597
 598 // Constants used to denote relative importance of
 599 // heuristic components for cost computation.
 600 static const unsigned PriorityOne = 200;
 601 static const unsigned PriorityTwo = 50;
 602 static const unsigned PriorityThree = 75;
 603 static const unsigned ScaleTwo = 10;
 604 static const unsigned FactorOne = 2;
 605
 606 /// Single point to compute overall scheduling cost.
 607 /// TODO: More heuristics will be used soon.
 608 int ConvergingVLIWScheduler::SchedulingCost(ReadyQueue &Q, SUnit *SU,
 609                                             SchedCandidate &Candidate,
 610                                             RegPressureDelta &Delta,
 611                                             bool verbose) {
 612   // Initial trivial priority.
 613   int ResCount = 1;
 614
 615   // Do not waste time on a node that is already scheduled.
 616   if (!SU || SU->isScheduled)
 617     return ResCount;
 618
 619   MachineInstr *Instr = SU->getInstr();
 620
 621   DEBUG(if (verbose) dbgs() << ((Q.getID() == TopQID) ? "(top|" : "(bot|"));
 622   // Forced priority is high.
 623   if (SU->isScheduleHigh) {
 624     ResCount += PriorityOne;
 625     DEBUG(dbgs() << "H|");
 626   }
 627
 628   // Critical path first.
 629   if (Q.getID() == TopQID) {
 630     ResCount += (SU->getHeight() * ScaleTwo);
 631
 632     DEBUG(if (verbose) {
 633       std::stringstream dbgstr;
 634       dbgstr << "h" << std::setw(3) << SU->getHeight() << "|";
 635       dbgs() << dbgstr.str();
 636     });
 637
 638     // If resources are available for it, multiply the
 639     // chance of scheduling.
 640     if (Top.ResourceModel->isResourceAvailable(SU)) {
 641       ResCount <<= FactorOne;
 642       ResCount += PriorityThree;
 643       DEBUG(if (verbose) dbgs() << "A|");
 644     } else
 645       DEBUG(if (verbose) dbgs() << " |");
 646   } else {
 647     ResCount += (SU->getDepth() * ScaleTwo);
 648
 649     DEBUG(if (verbose) {
 650       std::stringstream dbgstr;
 651       dbgstr << "d" << std::setw(3) << SU->getDepth() << "|";
 652       dbgs() << dbgstr.str();
 653     });
 654
 655     // If resources are available for it, multiply the
 656     // chance of scheduling.
 657     if (Bot.ResourceModel->isResourceAvailable(SU)) {
 658       ResCount <<= FactorOne;
 659       ResCount += PriorityThree;
 660       DEBUG(if (verbose) dbgs() << "A|");
 661     } else
 662       DEBUG(if (verbose) dbgs() << " |");
 663   }
 664
 665   unsigned NumNodesBlocking = 0;
 666   if (Q.getID() == TopQID) {
 667     // How many SUs does it block from scheduling?
 668     // Look at all of the successors of this node.
 669     // Count the number of nodes that
 670     // this node is the sole unscheduled node for.
 671     for (const SDep &SI : SU->Succs)
 672       if (getSingleUnscheduledPred(SI.getSUnit()) == SU)
 673         ++NumNodesBlocking;
 674   } else {
 675     // How many unscheduled predecessors block this node?
 676     for (const SDep &PI : SU->Preds)
 677       if (getSingleUnscheduledSucc(PI.getSUnit()) == SU)
 678         ++NumNodesBlocking;
 679   }
 680   ResCount += (NumNodesBlocking * ScaleTwo);
 681
 682   DEBUG(if (verbose) {
 683     std::stringstream dbgstr;
 684     dbgstr << "blk " << std::setw(2) << NumNodesBlocking << ")|";
 685     dbgs() << dbgstr.str();
 686   });
 687
 688   // Factor in reg pressure as a heuristic.
 689   if (!IgnoreBBRegPressure) {
 690     // Decrease priority by the amount that register pressure exceeds the limit.
 691     ResCount -= (Delta.Excess.getUnitInc()*PriorityOne);
 692     // Decrease priority if register pressure exceeds the limit.
 693     ResCount -= (Delta.CriticalMax.getUnitInc()*PriorityOne);
 694     // Decrease priority slightly if register pressure would increase over the
 695     // current maximum.
 696     ResCount -= (Delta.CurrentMax.getUnitInc()*PriorityTwo);
 697     DEBUG(if (verbose) {
 698         dbgs() << "RP " << Delta.Excess.getUnitInc() << "/"
 699                << Delta.CriticalMax.getUnitInc() <<"/"
 700                << Delta.CurrentMax.getUnitInc() << ")|";
 701     });
 702   }
 703
 704   // Give a little extra priority to a .cur instruction if there is a resource
 705   // available for it.
 706   auto &QST = DAG->MF.getSubtarget<HexagonSubtarget>();
 707   auto &QII = *QST.getInstrInfo();
 708   if (SU->isInstr() && QII.mayBeCurLoad(SU->getInstr())) {
 709     if (Q.getID() == TopQID && Top.ResourceModel->isResourceAvailable(SU)) {
 710       ResCount += PriorityTwo;
 711       DEBUG(if (verbose) dbgs() << "C|");
 712     } else if (Q.getID() == BotQID &&
 713                Bot.ResourceModel->isResourceAvailable(SU)) {
 714       ResCount += PriorityTwo;
 715       DEBUG(if (verbose) dbgs() << "C|");
 716     }
 717   }
 718
 719   // Give preference to a zero latency instruction if the dependent
 720   // instruction is in the current packet.
 721   if (Q.getID() == TopQID) {
 722     for (const SDep &PI : SU->Preds) {
 723       if (!PI.getSUnit()->getInstr()->isPseudo() && PI.isAssignedRegDep() &&
 724           PI.getLatency() == 0 &&
 725           Top.ResourceModel->isInPacket(PI.getSUnit())) {
 726         ResCount += PriorityThree;
 727         DEBUG(if (verbose) dbgs() << "Z|");
 728       }
 729     }
 730   } else {
 731     for (const SDep &SI : SU->Succs) {
 732       if (!SI.getSUnit()->getInstr()->isPseudo() && SI.isAssignedRegDep() &&
 733           SI.getLatency() == 0 &&
 734           Bot.ResourceModel->isInPacket(SI.getSUnit())) {
 735         ResCount += PriorityThree;
 736         DEBUG(if (verbose) dbgs() << "Z|");
 737       }
 738     }
 739   }
 740
 741   // Give less preference to an instruction that will cause a stall with
 742   // an instruction in the previous packet.
 743   if (QII.isV60VectorInstruction(Instr)) {
 744     // Check for stalls in the previous packet.
 745     if (Q.getID() == TopQID) {
 746       for (auto J : Top.ResourceModel->OldPacket)
 747         if (QII.producesStall(J->getInstr(), Instr))
 748           ResCount -= PriorityOne;
 749     } else {
 750       for (auto J : Bot.ResourceModel->OldPacket)
 751         if (QII.producesStall(Instr, J->getInstr()))
 752           ResCount -= PriorityOne;
 753     }
 754   }
 755
 756   // If the instruction has a non-zero latency dependence with an instruction in
 757   // the current packet, then it should not be scheduled yet. The case occurs
 758   // when the dependent instruction is scheduled in a new packet, so the
 759   // scheduler updates the current cycle and pending instructions become
 760   // available.
 761   if (CheckEarlyAvail) {
 762     if (Q.getID() == TopQID) {
 763       for (const auto &PI : SU->Preds) {
 764         if (PI.getLatency() > 0 &&
 765             Top.ResourceModel->isInPacket(PI.getSUnit())) {
 766           ResCount -= PriorityOne;
 767           DEBUG(if (verbose) dbgs() << "D|");
 768         }
 769       }
 770     } else {
 771       for (const auto &SI : SU->Succs) {
 772         if (SI.getLatency() > 0 &&
 773             Bot.ResourceModel->isInPacket(SI.getSUnit())) {
 774           ResCount -= PriorityOne;
 775           DEBUG(if (verbose) dbgs() << "D|");
 776         }
 777       }
 778     }
 779   }
 780
 781   DEBUG(if (verbose) {
 782     std::stringstream dbgstr;
 783     dbgstr << "Total " << std::setw(4) << ResCount << ")";
 784     dbgs() << dbgstr.str();
 785   });
 786
 787   return ResCount;
 788 }
 789
 790 /// Pick the best candidate from the top queue.
 791 ///
 792 /// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during
 793 /// DAG building. To adjust for the current scheduling location we need to
 794 /// maintain the number of vreg uses remaining to be top-scheduled.
 795 ConvergingVLIWScheduler::CandResult ConvergingVLIWScheduler::
 796 pickNodeFromQueue(ReadyQueue &Q, const RegPressureTracker &RPTracker,
 797                   SchedCandidate &Candidate) {
 798   DEBUG(if (SchedDebugVerboseLevel > 1)
 799         readyQueueVerboseDump(RPTracker, Candidate, Q);
 800         else Q.dump(););
 801
 802   // getMaxPressureDelta temporarily modifies the tracker.
 803   RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker);
 804
 805   // BestSU remains NULL if no top candidates beat the best existing candidate.
 806   CandResult FoundCandidate = NoCand;
 807   for (ReadyQueue::iterator I = Q.begin(), E = Q.end(); I != E; ++I) {
 808     RegPressureDelta RPDelta;
 809     TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta,
 810                                     DAG->getRegionCriticalPSets(),
 811                                     DAG->getRegPressure().MaxSetPressure);
 812
 813     int CurrentCost = SchedulingCost(Q, *I, Candidate, RPDelta, false);
 814
 815     // Initialize the candidate if needed.
 816     if (!Candidate.SU) {
 817       DEBUG(traceCandidate("DCAND", Q, *I, CurrentCost));
 818       Candidate.SU = *I;
 819       Candidate.RPDelta = RPDelta;
 820       Candidate.SCost = CurrentCost;
 821       FoundCandidate = NodeOrder;
 822       continue;
 823     }
 824
 825     // Best cost.
 826     if (CurrentCost > Candidate.SCost) {
 827       DEBUG(traceCandidate("CCAND", Q, *I, CurrentCost));
 828       Candidate.SU = *I;
 829       Candidate.RPDelta = RPDelta;
 830       Candidate.SCost = CurrentCost;
 831       FoundCandidate = BestCost;
 832       continue;
 833     }
 834
 835     // Tie breaker using Timing Class.
 836     if (!DisableTCTie) {
 837       auto &QST = DAG->MF.getSubtarget<HexagonSubtarget>();
 838       auto &QII = *QST.getInstrInfo();
 839
 840       const MachineInstr *MI = (*I)->getInstr();
 841       const MachineInstr *CandI = Candidate.SU->getInstr();
 842       const InstrItineraryData *InstrItins = QST.getInstrItineraryData();
 843
 844       unsigned InstrLatency = QII.getInstrTimingClassLatency(InstrItins, MI);
 845       unsigned CandLatency = QII.getInstrTimingClassLatency(InstrItins, CandI);
 846       DEBUG(dbgs() << "TC Tie Breaker Cand: "
 847                    << CandLatency << " Instr:" << InstrLatency << "\n"
 848                    << *MI << *CandI << "\n");
 849       if (Q.getID() == TopQID && CurrentCost == Candidate.SCost) {
 850         if (InstrLatency < CandLatency && TopUseShorterTie) {
 851           Candidate.SU = *I;
 852           Candidate.RPDelta = RPDelta;
 853           Candidate.SCost = CurrentCost;
 854           FoundCandidate = BestCost;
 855           DEBUG(dbgs() << "Used top shorter tie breaker\n");
 856           continue;
 857         } else if (InstrLatency > CandLatency && !TopUseShorterTie) {
 858           Candidate.SU = *I;
 859           Candidate.RPDelta = RPDelta;
 860           Candidate.SCost = CurrentCost;
 861           FoundCandidate = BestCost;
 862           DEBUG(dbgs() << "Used top longer tie breaker\n");
 863           continue;
 864         }
 865       } else if (Q.getID() == BotQID && CurrentCost == Candidate.SCost) {
 866         if (InstrLatency < CandLatency && BotUseShorterTie) {
 867           Candidate.SU = *I;
 868           Candidate.RPDelta = RPDelta;
 869           Candidate.SCost = CurrentCost;
 870           FoundCandidate = BestCost;
 871           DEBUG(dbgs() << "Used Bot shorter tie breaker\n");
 872           continue;
 873         } else if (InstrLatency > CandLatency && !BotUseShorterTie) {
 874           Candidate.SU = *I;
 875           Candidate.RPDelta = RPDelta;
 876           Candidate.SCost = CurrentCost;
 877           FoundCandidate = BestCost;
 878           DEBUG(dbgs() << "Used Bot longer tie breaker\n");
 879           continue;
 880         }
 881       }
 882     }
 883
 884     if (CurrentCost == Candidate.SCost) {
 885       if ((Q.getID() == TopQID &&
 886            (*I)->Succs.size() > Candidate.SU->Succs.size()) ||
 887           (Q.getID() == BotQID &&
 888            (*I)->Preds.size() < Candidate.SU->Preds.size())) {
 889         DEBUG(traceCandidate("SPCAND", Q, *I, CurrentCost));
 890         Candidate.SU = *I;
 891         Candidate.RPDelta = RPDelta;
 892         Candidate.SCost = CurrentCost;
 893         FoundCandidate = BestCost;
 894         continue;
 895       }
 896     }
 897
 898     // Fall through to original instruction order.
 899     // Only consider node order if Candidate was chosen from this Q.
 900     if (FoundCandidate == NoCand)
 901       continue;
 902   }
 903   return FoundCandidate;
 904 }
 905
 906 /// Pick the best candidate node from either the top or bottom queue.
 907 SUnit *ConvergingVLIWScheduler::pickNodeBidrectional(bool &IsTopNode) {
 908   // Schedule as far as possible in the direction of no choice. This is most
 909   // efficient, but also provides the best heuristics for CriticalPSets.
 910   if (SUnit *SU = Bot.pickOnlyChoice()) {
 911     DEBUG(dbgs() << "Picked only Bottom\n");
 912     IsTopNode = false;
 913     return SU;
 914   }
 915   if (SUnit *SU = Top.pickOnlyChoice()) {
 916     DEBUG(dbgs() << "Picked only Top\n");
 917     IsTopNode = true;
 918     return SU;
 919   }
 920   SchedCandidate BotCand;
 921   // Prefer bottom scheduling when heuristics are silent.
 922   CandResult BotResult = pickNodeFromQueue(Bot.Available,
 923                                            DAG->getBotRPTracker(), BotCand);
 924   assert(BotResult != NoCand && "failed to find the first candidate");
 925
 926   // If either Q has a single candidate that provides the least increase in
 927   // Excess pressure, we can immediately schedule from that Q.
 928   //
 929   // RegionCriticalPSets summarizes the pressure within the scheduled region and
 930   // affects picking from either Q. If scheduling in one direction must
 931   // increase pressure for one of the excess PSets, then schedule in that
 932   // direction first to provide more freedom in the other direction.
 933   if (BotResult == SingleExcess || BotResult == SingleCritical) {
 934     DEBUG(dbgs() << "Prefered Bottom Node\n");
 935     IsTopNode = false;
 936     return BotCand.SU;
 937   }
 938   // Check if the top Q has a better candidate.
 939   SchedCandidate TopCand;
 940   CandResult TopResult = pickNodeFromQueue(Top.Available,
 941                                            DAG->getTopRPTracker(), TopCand);
 942   assert(TopResult != NoCand && "failed to find the first candidate");
 943
 944   if (TopResult == SingleExcess || TopResult == SingleCritical) {
 945     DEBUG(dbgs() << "Prefered Top Node\n");
 946     IsTopNode = true;
 947     return TopCand.SU;
 948   }
 949   // If either Q has a single candidate that minimizes pressure above the
 950   // original region's pressure pick it.
 951   if (BotResult == SingleMax) {
 952     DEBUG(dbgs() << "Prefered Bottom Node SingleMax\n");
 953     IsTopNode = false;
 954     return BotCand.SU;
 955   }
 956   if (TopResult == SingleMax) {
 957     DEBUG(dbgs() << "Prefered Top Node SingleMax\n");
 958     IsTopNode = true;
 959     return TopCand.SU;
 960   }
 961   if (TopCand.SCost > BotCand.SCost) {
 962     DEBUG(dbgs() << "Prefered Top Node Cost\n");
 963     IsTopNode = true;
 964     return TopCand.SU;
 965   }
 966   // Otherwise prefer the bottom candidate in node order.
 967   DEBUG(dbgs() << "Prefered Bottom in Node order\n");
 968   IsTopNode = false;
 969   return BotCand.SU;
 970 }
 971
 972 /// Pick the best node to balance the schedule. Implements MachineSchedStrategy.
 973 SUnit *ConvergingVLIWScheduler::pickNode(bool &IsTopNode) {
 974   if (DAG->top() == DAG->bottom()) {
 975     assert(Top.Available.empty() && Top.Pending.empty() &&
 976            Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");
 977     return nullptr;
 978   }
 979   SUnit *SU;
 980   if (llvm::ForceTopDown) {
 981     SU = Top.pickOnlyChoice();
 982     if (!SU) {
 983       SchedCandidate TopCand;
 984       CandResult TopResult =
 985         pickNodeFromQueue(Top.Available, DAG->getTopRPTracker(), TopCand);
 986       assert(TopResult != NoCand && "failed to find the first candidate");
 987       (void)TopResult;
 988       SU = TopCand.SU;
 989     }
 990     IsTopNode = true;
 991   } else if (llvm::ForceBottomUp) {
 992     SU = Bot.pickOnlyChoice();
 993     if (!SU) {
 994       SchedCandidate BotCand;
 995       CandResult BotResult =
 996         pickNodeFromQueue(Bot.Available, DAG->getBotRPTracker(), BotCand);
 997       assert(BotResult != NoCand && "failed to find the first candidate");
 998       (void)BotResult;
 999       SU = BotCand.SU;
1000     }
1001     IsTopNode = false;
1002   } else {
1003     SU = pickNodeBidrectional(IsTopNode);
1004   }
1005   if (SU->isTopReady())
1006     Top.removeReady(SU);
1007   if (SU->isBottomReady())
1008     Bot.removeReady(SU);
1009
1010   DEBUG(dbgs() << "*** " << (IsTopNode ? "Top" : "Bottom")
1011         << " Scheduling Instruction in cycle "
1012         << (IsTopNode ? Top.CurrCycle : Bot.CurrCycle) << '\n';
1013         SU->dump(DAG));
1014   return SU;
1015 }
1016
1017 /// Update the scheduler's state after scheduling a node. This is the same node
1018 /// that was just returned by pickNode(). However, VLIWMachineScheduler needs
1019 /// to update it's state based on the current cycle before MachineSchedStrategy
1020 /// does.
1021 void ConvergingVLIWScheduler::schedNode(SUnit *SU, bool IsTopNode) {
1022   if (IsTopNode) {
1023     SU->TopReadyCycle = Top.CurrCycle;
1024     Top.bumpNode(SU);
1025   } else {
1026     SU->BotReadyCycle = Bot.CurrCycle;
1027     Bot.bumpNode(SU);
1028   }
1029 }