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 "llvm/CodeGen/MachineLoopInfo.h" 17 #include "llvm/IR/Function.h" 18 19 using namespace llvm; 20 21 #define DEBUG_TYPE "misched" 22 23 /// Platform-specific modifications to DAG. 24 void VLIWMachineScheduler::postprocessDAG() { 25 SUnit* LastSequentialCall = nullptr; 26 // Currently we only catch the situation when compare gets scheduled 27 // before preceding call. 28 for (unsigned su = 0, e = SUnits.size(); su != e; ++su) { 29 // Remember the call. 30 if (SUnits[su].getInstr()->isCall()) 31 LastSequentialCall = &(SUnits[su]); 32 // Look for a compare that defines a predicate. 33 else if (SUnits[su].getInstr()->isCompare() && LastSequentialCall) 34 SUnits[su].addPred(SDep(LastSequentialCall, SDep::Barrier)); 35 } 36 } 37 38 /// Check if scheduling of this SU is possible 39 /// in the current packet. 40 /// It is _not_ precise (statefull), it is more like 41 /// another heuristic. Many corner cases are figured 42 /// empirically. 43 bool VLIWResourceModel::isResourceAvailable(SUnit *SU) { 44 if (!SU || !SU->getInstr()) 45 return false; 46 47 // First see if the pipeline could receive this instruction 48 // in the current cycle. 49 switch (SU->getInstr()->getOpcode()) { 50 default: 51 if (!ResourcesModel->canReserveResources(SU->getInstr())) 52 return false; 53 case TargetOpcode::EXTRACT_SUBREG: 54 case TargetOpcode::INSERT_SUBREG: 55 case TargetOpcode::SUBREG_TO_REG: 56 case TargetOpcode::REG_SEQUENCE: 57 case TargetOpcode::IMPLICIT_DEF: 58 case TargetOpcode::COPY: 59 case TargetOpcode::INLINEASM: 60 break; 61 } 62 63 // Now see if there are no other dependencies to instructions already 64 // in the packet. 65 for (unsigned i = 0, e = Packet.size(); i != e; ++i) { 66 if (Packet[i]->Succs.size() == 0) 67 continue; 68 for (SUnit::const_succ_iterator I = Packet[i]->Succs.begin(), 69 E = Packet[i]->Succs.end(); I != E; ++I) { 70 // Since we do not add pseudos to packets, might as well 71 // ignore order dependencies. 72 if (I->isCtrl()) 73 continue; 74 75 if (I->getSUnit() == SU) 76 return false; 77 } 78 } 79 return true; 80 } 81 82 /// Keep track of available resources. 83 bool VLIWResourceModel::reserveResources(SUnit *SU) { 84 bool startNewCycle = false; 85 // Artificially reset state. 86 if (!SU) { 87 ResourcesModel->clearResources(); 88 Packet.clear(); 89 TotalPackets++; 90 return false; 91 } 92 // If this SU does not fit in the packet 93 // start a new one. 94 if (!isResourceAvailable(SU)) { 95 ResourcesModel->clearResources(); 96 Packet.clear(); 97 TotalPackets++; 98 startNewCycle = true; 99 } 100 101 switch (SU->getInstr()->getOpcode()) { 102 default: 103 ResourcesModel->reserveResources(SU->getInstr()); 104 break; 105 case TargetOpcode::EXTRACT_SUBREG: 106 case TargetOpcode::INSERT_SUBREG: 107 case TargetOpcode::SUBREG_TO_REG: 108 case TargetOpcode::REG_SEQUENCE: 109 case TargetOpcode::IMPLICIT_DEF: 110 case TargetOpcode::KILL: 111 case TargetOpcode::CFI_INSTRUCTION: 112 case TargetOpcode::EH_LABEL: 113 case TargetOpcode::COPY: 114 case TargetOpcode::INLINEASM: 115 break; 116 } 117 Packet.push_back(SU); 118 119 #ifndef NDEBUG 120 DEBUG(dbgs() << "Packet[" << TotalPackets << "]:\n"); 121 for (unsigned i = 0, e = Packet.size(); i != e; ++i) { 122 DEBUG(dbgs() << "\t[" << i << "] SU("); 123 DEBUG(dbgs() << Packet[i]->NodeNum << ")\t"); 124 DEBUG(Packet[i]->getInstr()->dump()); 125 } 126 #endif 127 128 // If packet is now full, reset the state so in the next cycle 129 // we start fresh. 130 if (Packet.size() >= SchedModel->getIssueWidth()) { 131 ResourcesModel->clearResources(); 132 Packet.clear(); 133 TotalPackets++; 134 startNewCycle = true; 135 } 136 137 return startNewCycle; 138 } 139 140 /// schedule - Called back from MachineScheduler::runOnMachineFunction 141 /// after setting up the current scheduling region. [RegionBegin, RegionEnd) 142 /// only includes instructions that have DAG nodes, not scheduling boundaries. 143 void VLIWMachineScheduler::schedule() { 144 DEBUG(dbgs() 145 << "********** MI Converging Scheduling VLIW BB#" << BB->getNumber() 146 << " " << BB->getName() 147 << " in_func " << BB->getParent()->getFunction()->getName() 148 << " at loop depth " << MLI->getLoopDepth(BB) 149 << " \n"); 150 151 buildDAGWithRegPressure(); 152 153 // Postprocess the DAG to add platform-specific artificial dependencies. 154 postprocessDAG(); 155 156 SmallVector<SUnit*, 8> TopRoots, BotRoots; 157 findRootsAndBiasEdges(TopRoots, BotRoots); 158 159 // Initialize the strategy before modifying the DAG. 160 SchedImpl->initialize(this); 161 162 // To view Height/Depth correctly, they should be accessed at least once. 163 // 164 // FIXME: SUnit::dumpAll always recompute depth and height now. The max 165 // depth/height could be computed directly from the roots and leaves. 166 DEBUG(unsigned maxH = 0; 167 for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 168 if (SUnits[su].getHeight() > maxH) 169 maxH = SUnits[su].getHeight(); 170 dbgs() << "Max Height " << maxH << "\n";); 171 DEBUG(unsigned maxD = 0; 172 for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 173 if (SUnits[su].getDepth() > maxD) 174 maxD = SUnits[su].getDepth(); 175 dbgs() << "Max Depth " << maxD << "\n";); 176 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 177 SUnits[su].dumpAll(this)); 178 179 initQueues(TopRoots, BotRoots); 180 181 bool IsTopNode = false; 182 while (SUnit *SU = SchedImpl->pickNode(IsTopNode)) { 183 if (!checkSchedLimit()) 184 break; 185 186 scheduleMI(SU, IsTopNode); 187 188 updateQueues(SU, IsTopNode); 189 190 // Notify the scheduling strategy after updating the DAG. 191 SchedImpl->schedNode(SU, IsTopNode); 192 } 193 assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone."); 194 195 placeDebugValues(); 196 } 197 198 void ConvergingVLIWScheduler::initialize(ScheduleDAGMI *dag) { 199 DAG = static_cast<VLIWMachineScheduler*>(dag); 200 SchedModel = DAG->getSchedModel(); 201 202 Top.init(DAG, SchedModel); 203 Bot.init(DAG, SchedModel); 204 205 // Initialize the HazardRecognizers. If itineraries don't exist, are empty, or 206 // are disabled, then these HazardRecs will be disabled. 207 const InstrItineraryData *Itin = DAG->getSchedModel()->getInstrItineraries(); 208 const TargetSubtargetInfo &STI = DAG->MF.getSubtarget(); 209 const TargetInstrInfo *TII = STI.getInstrInfo(); 210 delete Top.HazardRec; 211 delete Bot.HazardRec; 212 Top.HazardRec = TII->CreateTargetMIHazardRecognizer(Itin, DAG); 213 Bot.HazardRec = TII->CreateTargetMIHazardRecognizer(Itin, DAG); 214 215 delete Top.ResourceModel; 216 delete Bot.ResourceModel; 217 Top.ResourceModel = new VLIWResourceModel(STI, DAG->getSchedModel()); 218 Bot.ResourceModel = new VLIWResourceModel(STI, DAG->getSchedModel()); 219 220 assert((!llvm::ForceTopDown || !llvm::ForceBottomUp) && 221 "-misched-topdown incompatible with -misched-bottomup"); 222 } 223 224 void ConvergingVLIWScheduler::releaseTopNode(SUnit *SU) { 225 if (SU->isScheduled) 226 return; 227 228 for (SUnit::succ_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 229 I != E; ++I) { 230 unsigned PredReadyCycle = I->getSUnit()->TopReadyCycle; 231 unsigned MinLatency = I->getLatency(); 232 #ifndef NDEBUG 233 Top.MaxMinLatency = std::max(MinLatency, Top.MaxMinLatency); 234 #endif 235 if (SU->TopReadyCycle < PredReadyCycle + MinLatency) 236 SU->TopReadyCycle = PredReadyCycle + MinLatency; 237 } 238 Top.releaseNode(SU, SU->TopReadyCycle); 239 } 240 241 void ConvergingVLIWScheduler::releaseBottomNode(SUnit *SU) { 242 if (SU->isScheduled) 243 return; 244 245 assert(SU->getInstr() && "Scheduled SUnit must have instr"); 246 247 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 248 I != E; ++I) { 249 unsigned SuccReadyCycle = I->getSUnit()->BotReadyCycle; 250 unsigned MinLatency = I->getLatency(); 251 #ifndef NDEBUG 252 Bot.MaxMinLatency = std::max(MinLatency, Bot.MaxMinLatency); 253 #endif 254 if (SU->BotReadyCycle < SuccReadyCycle + MinLatency) 255 SU->BotReadyCycle = SuccReadyCycle + MinLatency; 256 } 257 Bot.releaseNode(SU, SU->BotReadyCycle); 258 } 259 260 /// Does this SU have a hazard within the current instruction group. 261 /// 262 /// The scheduler supports two modes of hazard recognition. The first is the 263 /// ScheduleHazardRecognizer API. It is a fully general hazard recognizer that 264 /// supports highly complicated in-order reservation tables 265 /// (ScoreboardHazardRecognizer) and arbitrary target-specific logic. 266 /// 267 /// The second is a streamlined mechanism that checks for hazards based on 268 /// simple counters that the scheduler itself maintains. It explicitly checks 269 /// for instruction dispatch limitations, including the number of micro-ops that 270 /// can dispatch per cycle. 271 /// 272 /// TODO: Also check whether the SU must start a new group. 273 bool ConvergingVLIWScheduler::VLIWSchedBoundary::checkHazard(SUnit *SU) { 274 if (HazardRec->isEnabled()) 275 return HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard; 276 277 unsigned uops = SchedModel->getNumMicroOps(SU->getInstr()); 278 if (IssueCount + uops > SchedModel->getIssueWidth()) 279 return true; 280 281 return false; 282 } 283 284 void ConvergingVLIWScheduler::VLIWSchedBoundary::releaseNode(SUnit *SU, 285 unsigned ReadyCycle) { 286 if (ReadyCycle < MinReadyCycle) 287 MinReadyCycle = ReadyCycle; 288 289 // Check for interlocks first. For the purpose of other heuristics, an 290 // instruction that cannot issue appears as if it's not in the ReadyQueue. 291 if (ReadyCycle > CurrCycle || checkHazard(SU)) 292 293 Pending.push(SU); 294 else 295 Available.push(SU); 296 } 297 298 /// Move the boundary of scheduled code by one cycle. 299 void ConvergingVLIWScheduler::VLIWSchedBoundary::bumpCycle() { 300 unsigned Width = SchedModel->getIssueWidth(); 301 IssueCount = (IssueCount <= Width) ? 0 : IssueCount - Width; 302 303 assert(MinReadyCycle < UINT_MAX && "MinReadyCycle uninitialized"); 304 unsigned NextCycle = std::max(CurrCycle + 1, MinReadyCycle); 305 306 if (!HazardRec->isEnabled()) { 307 // Bypass HazardRec virtual calls. 308 CurrCycle = NextCycle; 309 } else { 310 // Bypass getHazardType calls in case of long latency. 311 for (; CurrCycle != NextCycle; ++CurrCycle) { 312 if (isTop()) 313 HazardRec->AdvanceCycle(); 314 else 315 HazardRec->RecedeCycle(); 316 } 317 } 318 CheckPending = true; 319 320 DEBUG(dbgs() << "*** " << Available.getName() << " cycle " 321 << CurrCycle << '\n'); 322 } 323 324 /// Move the boundary of scheduled code by one SUnit. 325 void ConvergingVLIWScheduler::VLIWSchedBoundary::bumpNode(SUnit *SU) { 326 bool startNewCycle = false; 327 328 // Update the reservation table. 329 if (HazardRec->isEnabled()) { 330 if (!isTop() && SU->isCall) { 331 // Calls are scheduled with their preceding instructions. For bottom-up 332 // scheduling, clear the pipeline state before emitting. 333 HazardRec->Reset(); 334 } 335 HazardRec->EmitInstruction(SU); 336 } 337 338 // Update DFA model. 339 startNewCycle = ResourceModel->reserveResources(SU); 340 341 // Check the instruction group dispatch limit. 342 // TODO: Check if this SU must end a dispatch group. 343 IssueCount += SchedModel->getNumMicroOps(SU->getInstr()); 344 if (startNewCycle) { 345 DEBUG(dbgs() << "*** Max instrs at cycle " << CurrCycle << '\n'); 346 bumpCycle(); 347 } 348 else 349 DEBUG(dbgs() << "*** IssueCount " << IssueCount 350 << " at cycle " << CurrCycle << '\n'); 351 } 352 353 /// Release pending ready nodes in to the available queue. This makes them 354 /// visible to heuristics. 355 void ConvergingVLIWScheduler::VLIWSchedBoundary::releasePending() { 356 // If the available queue is empty, it is safe to reset MinReadyCycle. 357 if (Available.empty()) 358 MinReadyCycle = UINT_MAX; 359 360 // Check to see if any of the pending instructions are ready to issue. If 361 // so, add them to the available queue. 362 for (unsigned i = 0, e = Pending.size(); i != e; ++i) { 363 SUnit *SU = *(Pending.begin()+i); 364 unsigned ReadyCycle = isTop() ? SU->TopReadyCycle : SU->BotReadyCycle; 365 366 if (ReadyCycle < MinReadyCycle) 367 MinReadyCycle = ReadyCycle; 368 369 if (ReadyCycle > CurrCycle) 370 continue; 371 372 if (checkHazard(SU)) 373 continue; 374 375 Available.push(SU); 376 Pending.remove(Pending.begin()+i); 377 --i; --e; 378 } 379 CheckPending = false; 380 } 381 382 /// Remove SU from the ready set for this boundary. 383 void ConvergingVLIWScheduler::VLIWSchedBoundary::removeReady(SUnit *SU) { 384 if (Available.isInQueue(SU)) 385 Available.remove(Available.find(SU)); 386 else { 387 assert(Pending.isInQueue(SU) && "bad ready count"); 388 Pending.remove(Pending.find(SU)); 389 } 390 } 391 392 /// If this queue only has one ready candidate, return it. As a side effect, 393 /// advance the cycle until at least one node is ready. If multiple instructions 394 /// are ready, return NULL. 395 SUnit *ConvergingVLIWScheduler::VLIWSchedBoundary::pickOnlyChoice() { 396 if (CheckPending) 397 releasePending(); 398 399 for (unsigned i = 0; Available.empty(); ++i) { 400 assert(i <= (HazardRec->getMaxLookAhead() + MaxMinLatency) && 401 "permanent hazard"); (void)i; 402 ResourceModel->reserveResources(nullptr); 403 bumpCycle(); 404 releasePending(); 405 } 406 if (Available.size() == 1) 407 return *Available.begin(); 408 return nullptr; 409 } 410 411 #ifndef NDEBUG 412 void ConvergingVLIWScheduler::traceCandidate(const char *Label, 413 const ReadyQueue &Q, 414 SUnit *SU, PressureChange P) { 415 dbgs() << Label << " " << Q.getName() << " "; 416 if (P.isValid()) 417 dbgs() << DAG->TRI->getRegPressureSetName(P.getPSet()) << ":" 418 << P.getUnitInc() << " "; 419 else 420 dbgs() << " "; 421 SU->dump(DAG); 422 } 423 #endif 424 425 /// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor 426 /// of SU, return it, otherwise return null. 427 static SUnit *getSingleUnscheduledPred(SUnit *SU) { 428 SUnit *OnlyAvailablePred = nullptr; 429 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 430 I != E; ++I) { 431 SUnit &Pred = *I->getSUnit(); 432 if (!Pred.isScheduled) { 433 // We found an available, but not scheduled, predecessor. If it's the 434 // only one we have found, keep track of it... otherwise give up. 435 if (OnlyAvailablePred && OnlyAvailablePred != &Pred) 436 return nullptr; 437 OnlyAvailablePred = &Pred; 438 } 439 } 440 return OnlyAvailablePred; 441 } 442 443 /// getSingleUnscheduledSucc - If there is exactly one unscheduled successor 444 /// of SU, return it, otherwise return null. 445 static SUnit *getSingleUnscheduledSucc(SUnit *SU) { 446 SUnit *OnlyAvailableSucc = nullptr; 447 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 448 I != E; ++I) { 449 SUnit &Succ = *I->getSUnit(); 450 if (!Succ.isScheduled) { 451 // We found an available, but not scheduled, successor. If it's the 452 // only one we have found, keep track of it... otherwise give up. 453 if (OnlyAvailableSucc && OnlyAvailableSucc != &Succ) 454 return nullptr; 455 OnlyAvailableSucc = &Succ; 456 } 457 } 458 return OnlyAvailableSucc; 459 } 460 461 // Constants used to denote relative importance of 462 // heuristic components for cost computation. 463 static const unsigned PriorityOne = 200; 464 static const unsigned PriorityTwo = 50; 465 static const unsigned ScaleTwo = 10; 466 static const unsigned FactorOne = 2; 467 468 /// Single point to compute overall scheduling cost. 469 /// TODO: More heuristics will be used soon. 470 int ConvergingVLIWScheduler::SchedulingCost(ReadyQueue &Q, SUnit *SU, 471 SchedCandidate &Candidate, 472 RegPressureDelta &Delta, 473 bool verbose) { 474 // Initial trivial priority. 475 int ResCount = 1; 476 477 // Do not waste time on a node that is already scheduled. 478 if (!SU || SU->isScheduled) 479 return ResCount; 480 481 // Forced priority is high. 482 if (SU->isScheduleHigh) 483 ResCount += PriorityOne; 484 485 // Critical path first. 486 if (Q.getID() == TopQID) { 487 ResCount += (SU->getHeight() * ScaleTwo); 488 489 // If resources are available for it, multiply the 490 // chance of scheduling. 491 if (Top.ResourceModel->isResourceAvailable(SU)) 492 ResCount <<= FactorOne; 493 } else { 494 ResCount += (SU->getDepth() * ScaleTwo); 495 496 // If resources are available for it, multiply the 497 // chance of scheduling. 498 if (Bot.ResourceModel->isResourceAvailable(SU)) 499 ResCount <<= FactorOne; 500 } 501 502 unsigned NumNodesBlocking = 0; 503 if (Q.getID() == TopQID) { 504 // How many SUs does it block from scheduling? 505 // Look at all of the successors of this node. 506 // Count the number of nodes that 507 // this node is the sole unscheduled node for. 508 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 509 I != E; ++I) 510 if (getSingleUnscheduledPred(I->getSUnit()) == SU) 511 ++NumNodesBlocking; 512 } else { 513 // How many unscheduled predecessors block this node? 514 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 515 I != E; ++I) 516 if (getSingleUnscheduledSucc(I->getSUnit()) == SU) 517 ++NumNodesBlocking; 518 } 519 ResCount += (NumNodesBlocking * ScaleTwo); 520 521 // Factor in reg pressure as a heuristic. 522 ResCount -= (Delta.Excess.getUnitInc()*PriorityTwo); 523 ResCount -= (Delta.CriticalMax.getUnitInc()*PriorityTwo); 524 525 DEBUG(if (verbose) dbgs() << " Total(" << ResCount << ")"); 526 527 return ResCount; 528 } 529 530 /// Pick the best candidate from the top queue. 531 /// 532 /// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during 533 /// DAG building. To adjust for the current scheduling location we need to 534 /// maintain the number of vreg uses remaining to be top-scheduled. 535 ConvergingVLIWScheduler::CandResult ConvergingVLIWScheduler:: 536 pickNodeFromQueue(ReadyQueue &Q, const RegPressureTracker &RPTracker, 537 SchedCandidate &Candidate) { 538 DEBUG(Q.dump()); 539 540 // getMaxPressureDelta temporarily modifies the tracker. 541 RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker); 542 543 // BestSU remains NULL if no top candidates beat the best existing candidate. 544 CandResult FoundCandidate = NoCand; 545 for (ReadyQueue::iterator I = Q.begin(), E = Q.end(); I != E; ++I) { 546 RegPressureDelta RPDelta; 547 TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta, 548 DAG->getRegionCriticalPSets(), 549 DAG->getRegPressure().MaxSetPressure); 550 551 int CurrentCost = SchedulingCost(Q, *I, Candidate, RPDelta, false); 552 553 // Initialize the candidate if needed. 554 if (!Candidate.SU) { 555 Candidate.SU = *I; 556 Candidate.RPDelta = RPDelta; 557 Candidate.SCost = CurrentCost; 558 FoundCandidate = NodeOrder; 559 continue; 560 } 561 562 // Best cost. 563 if (CurrentCost > Candidate.SCost) { 564 DEBUG(traceCandidate("CCAND", Q, *I)); 565 Candidate.SU = *I; 566 Candidate.RPDelta = RPDelta; 567 Candidate.SCost = CurrentCost; 568 FoundCandidate = BestCost; 569 continue; 570 } 571 572 // Fall through to original instruction order. 573 // Only consider node order if Candidate was chosen from this Q. 574 if (FoundCandidate == NoCand) 575 continue; 576 } 577 return FoundCandidate; 578 } 579 580 /// Pick the best candidate node from either the top or bottom queue. 581 SUnit *ConvergingVLIWScheduler::pickNodeBidrectional(bool &IsTopNode) { 582 // Schedule as far as possible in the direction of no choice. This is most 583 // efficient, but also provides the best heuristics for CriticalPSets. 584 if (SUnit *SU = Bot.pickOnlyChoice()) { 585 IsTopNode = false; 586 return SU; 587 } 588 if (SUnit *SU = Top.pickOnlyChoice()) { 589 IsTopNode = true; 590 return SU; 591 } 592 SchedCandidate BotCand; 593 // Prefer bottom scheduling when heuristics are silent. 594 CandResult BotResult = pickNodeFromQueue(Bot.Available, 595 DAG->getBotRPTracker(), BotCand); 596 assert(BotResult != NoCand && "failed to find the first candidate"); 597 598 // If either Q has a single candidate that provides the least increase in 599 // Excess pressure, we can immediately schedule from that Q. 600 // 601 // RegionCriticalPSets summarizes the pressure within the scheduled region and 602 // affects picking from either Q. If scheduling in one direction must 603 // increase pressure for one of the excess PSets, then schedule in that 604 // direction first to provide more freedom in the other direction. 605 if (BotResult == SingleExcess || BotResult == SingleCritical) { 606 IsTopNode = false; 607 return BotCand.SU; 608 } 609 // Check if the top Q has a better candidate. 610 SchedCandidate TopCand; 611 CandResult TopResult = pickNodeFromQueue(Top.Available, 612 DAG->getTopRPTracker(), TopCand); 613 assert(TopResult != NoCand && "failed to find the first candidate"); 614 615 if (TopResult == SingleExcess || TopResult == SingleCritical) { 616 IsTopNode = true; 617 return TopCand.SU; 618 } 619 // If either Q has a single candidate that minimizes pressure above the 620 // original region's pressure pick it. 621 if (BotResult == SingleMax) { 622 IsTopNode = false; 623 return BotCand.SU; 624 } 625 if (TopResult == SingleMax) { 626 IsTopNode = true; 627 return TopCand.SU; 628 } 629 if (TopCand.SCost > BotCand.SCost) { 630 IsTopNode = true; 631 return TopCand.SU; 632 } 633 // Otherwise prefer the bottom candidate in node order. 634 IsTopNode = false; 635 return BotCand.SU; 636 } 637 638 /// Pick the best node to balance the schedule. Implements MachineSchedStrategy. 639 SUnit *ConvergingVLIWScheduler::pickNode(bool &IsTopNode) { 640 if (DAG->top() == DAG->bottom()) { 641 assert(Top.Available.empty() && Top.Pending.empty() && 642 Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage"); 643 return nullptr; 644 } 645 SUnit *SU; 646 if (llvm::ForceTopDown) { 647 SU = Top.pickOnlyChoice(); 648 if (!SU) { 649 SchedCandidate TopCand; 650 CandResult TopResult = 651 pickNodeFromQueue(Top.Available, DAG->getTopRPTracker(), TopCand); 652 assert(TopResult != NoCand && "failed to find the first candidate"); 653 (void)TopResult; 654 SU = TopCand.SU; 655 } 656 IsTopNode = true; 657 } else if (llvm::ForceBottomUp) { 658 SU = Bot.pickOnlyChoice(); 659 if (!SU) { 660 SchedCandidate BotCand; 661 CandResult BotResult = 662 pickNodeFromQueue(Bot.Available, DAG->getBotRPTracker(), BotCand); 663 assert(BotResult != NoCand && "failed to find the first candidate"); 664 (void)BotResult; 665 SU = BotCand.SU; 666 } 667 IsTopNode = false; 668 } else { 669 SU = pickNodeBidrectional(IsTopNode); 670 } 671 if (SU->isTopReady()) 672 Top.removeReady(SU); 673 if (SU->isBottomReady()) 674 Bot.removeReady(SU); 675 676 DEBUG(dbgs() << "*** " << (IsTopNode ? "Top" : "Bottom") 677 << " Scheduling Instruction in cycle " 678 << (IsTopNode ? Top.CurrCycle : Bot.CurrCycle) << '\n'; 679 SU->dump(DAG)); 680 return SU; 681 } 682 683 /// Update the scheduler's state after scheduling a node. This is the same node 684 /// that was just returned by pickNode(). However, VLIWMachineScheduler needs 685 /// to update it's state based on the current cycle before MachineSchedStrategy 686 /// does. 687 void ConvergingVLIWScheduler::schedNode(SUnit *SU, bool IsTopNode) { 688 if (IsTopNode) { 689 SU->TopReadyCycle = Top.CurrCycle; 690 Top.bumpNode(SU); 691 } else { 692 SU->BotReadyCycle = Bot.CurrCycle; 693 Bot.bumpNode(SU); 694 } 695 } 696