HexagonMachineScheduler.cpp revision 263508
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#define DEBUG_TYPE "misched" 16 17#include "HexagonMachineScheduler.h" 18#include "llvm/CodeGen/MachineLoopInfo.h" 19#include "llvm/IR/Function.h" 20 21using namespace llvm; 22 23/// Platform specific modifications to DAG. 24void VLIWMachineScheduler::postprocessDAG() { 25 SUnit* LastSequentialCall = NULL; 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. 43bool 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. 83bool 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::PROLOG_LABEL: 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. 143void 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 assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone."); 191 192 placeDebugValues(); 193} 194 195void ConvergingVLIWScheduler::initialize(ScheduleDAGMI *dag) { 196 DAG = static_cast<VLIWMachineScheduler*>(dag); 197 SchedModel = DAG->getSchedModel(); 198 199 Top.init(DAG, SchedModel); 200 Bot.init(DAG, SchedModel); 201 202 // Initialize the HazardRecognizers. If itineraries don't exist, are empty, or 203 // are disabled, then these HazardRecs will be disabled. 204 const InstrItineraryData *Itin = DAG->getSchedModel()->getInstrItineraries(); 205 const TargetMachine &TM = DAG->MF.getTarget(); 206 delete Top.HazardRec; 207 delete Bot.HazardRec; 208 Top.HazardRec = TM.getInstrInfo()->CreateTargetMIHazardRecognizer(Itin, DAG); 209 Bot.HazardRec = TM.getInstrInfo()->CreateTargetMIHazardRecognizer(Itin, DAG); 210 211 delete Top.ResourceModel; 212 delete Bot.ResourceModel; 213 Top.ResourceModel = new VLIWResourceModel(TM, DAG->getSchedModel()); 214 Bot.ResourceModel = new VLIWResourceModel(TM, DAG->getSchedModel()); 215 216 assert((!llvm::ForceTopDown || !llvm::ForceBottomUp) && 217 "-misched-topdown incompatible with -misched-bottomup"); 218} 219 220void ConvergingVLIWScheduler::releaseTopNode(SUnit *SU) { 221 if (SU->isScheduled) 222 return; 223 224 for (SUnit::succ_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 225 I != E; ++I) { 226 unsigned PredReadyCycle = I->getSUnit()->TopReadyCycle; 227 unsigned MinLatency = I->getLatency(); 228#ifndef NDEBUG 229 Top.MaxMinLatency = std::max(MinLatency, Top.MaxMinLatency); 230#endif 231 if (SU->TopReadyCycle < PredReadyCycle + MinLatency) 232 SU->TopReadyCycle = PredReadyCycle + MinLatency; 233 } 234 Top.releaseNode(SU, SU->TopReadyCycle); 235} 236 237void ConvergingVLIWScheduler::releaseBottomNode(SUnit *SU) { 238 if (SU->isScheduled) 239 return; 240 241 assert(SU->getInstr() && "Scheduled SUnit must have instr"); 242 243 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 244 I != E; ++I) { 245 unsigned SuccReadyCycle = I->getSUnit()->BotReadyCycle; 246 unsigned MinLatency = I->getLatency(); 247#ifndef NDEBUG 248 Bot.MaxMinLatency = std::max(MinLatency, Bot.MaxMinLatency); 249#endif 250 if (SU->BotReadyCycle < SuccReadyCycle + MinLatency) 251 SU->BotReadyCycle = SuccReadyCycle + MinLatency; 252 } 253 Bot.releaseNode(SU, SU->BotReadyCycle); 254} 255 256/// Does this SU have a hazard within the current instruction group. 257/// 258/// The scheduler supports two modes of hazard recognition. The first is the 259/// ScheduleHazardRecognizer API. It is a fully general hazard recognizer that 260/// supports highly complicated in-order reservation tables 261/// (ScoreboardHazardRecognizer) and arbitrary target-specific logic. 262/// 263/// The second is a streamlined mechanism that checks for hazards based on 264/// simple counters that the scheduler itself maintains. It explicitly checks 265/// for instruction dispatch limitations, including the number of micro-ops that 266/// can dispatch per cycle. 267/// 268/// TODO: Also check whether the SU must start a new group. 269bool ConvergingVLIWScheduler::SchedBoundary::checkHazard(SUnit *SU) { 270 if (HazardRec->isEnabled()) 271 return HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard; 272 273 unsigned uops = SchedModel->getNumMicroOps(SU->getInstr()); 274 if (IssueCount + uops > SchedModel->getIssueWidth()) 275 return true; 276 277 return false; 278} 279 280void ConvergingVLIWScheduler::SchedBoundary::releaseNode(SUnit *SU, 281 unsigned ReadyCycle) { 282 if (ReadyCycle < MinReadyCycle) 283 MinReadyCycle = ReadyCycle; 284 285 // Check for interlocks first. For the purpose of other heuristics, an 286 // instruction that cannot issue appears as if it's not in the ReadyQueue. 287 if (ReadyCycle > CurrCycle || checkHazard(SU)) 288 289 Pending.push(SU); 290 else 291 Available.push(SU); 292} 293 294/// Move the boundary of scheduled code by one cycle. 295void ConvergingVLIWScheduler::SchedBoundary::bumpCycle() { 296 unsigned Width = SchedModel->getIssueWidth(); 297 IssueCount = (IssueCount <= Width) ? 0 : IssueCount - Width; 298 299 assert(MinReadyCycle < UINT_MAX && "MinReadyCycle uninitialized"); 300 unsigned NextCycle = std::max(CurrCycle + 1, MinReadyCycle); 301 302 if (!HazardRec->isEnabled()) { 303 // Bypass HazardRec virtual calls. 304 CurrCycle = NextCycle; 305 } else { 306 // Bypass getHazardType calls in case of long latency. 307 for (; CurrCycle != NextCycle; ++CurrCycle) { 308 if (isTop()) 309 HazardRec->AdvanceCycle(); 310 else 311 HazardRec->RecedeCycle(); 312 } 313 } 314 CheckPending = true; 315 316 DEBUG(dbgs() << "*** " << Available.getName() << " cycle " 317 << CurrCycle << '\n'); 318} 319 320/// Move the boundary of scheduled code by one SUnit. 321void ConvergingVLIWScheduler::SchedBoundary::bumpNode(SUnit *SU) { 322 bool startNewCycle = false; 323 324 // Update the reservation table. 325 if (HazardRec->isEnabled()) { 326 if (!isTop() && SU->isCall) { 327 // Calls are scheduled with their preceding instructions. For bottom-up 328 // scheduling, clear the pipeline state before emitting. 329 HazardRec->Reset(); 330 } 331 HazardRec->EmitInstruction(SU); 332 } 333 334 // Update DFA model. 335 startNewCycle = ResourceModel->reserveResources(SU); 336 337 // Check the instruction group dispatch limit. 338 // TODO: Check if this SU must end a dispatch group. 339 IssueCount += SchedModel->getNumMicroOps(SU->getInstr()); 340 if (startNewCycle) { 341 DEBUG(dbgs() << "*** Max instrs at cycle " << CurrCycle << '\n'); 342 bumpCycle(); 343 } 344 else 345 DEBUG(dbgs() << "*** IssueCount " << IssueCount 346 << " at cycle " << CurrCycle << '\n'); 347} 348 349/// Release pending ready nodes in to the available queue. This makes them 350/// visible to heuristics. 351void ConvergingVLIWScheduler::SchedBoundary::releasePending() { 352 // If the available queue is empty, it is safe to reset MinReadyCycle. 353 if (Available.empty()) 354 MinReadyCycle = UINT_MAX; 355 356 // Check to see if any of the pending instructions are ready to issue. If 357 // so, add them to the available queue. 358 for (unsigned i = 0, e = Pending.size(); i != e; ++i) { 359 SUnit *SU = *(Pending.begin()+i); 360 unsigned ReadyCycle = isTop() ? SU->TopReadyCycle : SU->BotReadyCycle; 361 362 if (ReadyCycle < MinReadyCycle) 363 MinReadyCycle = ReadyCycle; 364 365 if (ReadyCycle > CurrCycle) 366 continue; 367 368 if (checkHazard(SU)) 369 continue; 370 371 Available.push(SU); 372 Pending.remove(Pending.begin()+i); 373 --i; --e; 374 } 375 CheckPending = false; 376} 377 378/// Remove SU from the ready set for this boundary. 379void ConvergingVLIWScheduler::SchedBoundary::removeReady(SUnit *SU) { 380 if (Available.isInQueue(SU)) 381 Available.remove(Available.find(SU)); 382 else { 383 assert(Pending.isInQueue(SU) && "bad ready count"); 384 Pending.remove(Pending.find(SU)); 385 } 386} 387 388/// If this queue only has one ready candidate, return it. As a side effect, 389/// advance the cycle until at least one node is ready. If multiple instructions 390/// are ready, return NULL. 391SUnit *ConvergingVLIWScheduler::SchedBoundary::pickOnlyChoice() { 392 if (CheckPending) 393 releasePending(); 394 395 for (unsigned i = 0; Available.empty(); ++i) { 396 assert(i <= (HazardRec->getMaxLookAhead() + MaxMinLatency) && 397 "permanent hazard"); (void)i; 398 ResourceModel->reserveResources(0); 399 bumpCycle(); 400 releasePending(); 401 } 402 if (Available.size() == 1) 403 return *Available.begin(); 404 return NULL; 405} 406 407#ifndef NDEBUG 408void ConvergingVLIWScheduler::traceCandidate(const char *Label, 409 const ReadyQueue &Q, 410 SUnit *SU, PressureChange P) { 411 dbgs() << Label << " " << Q.getName() << " "; 412 if (P.isValid()) 413 dbgs() << DAG->TRI->getRegPressureSetName(P.getPSet()) << ":" 414 << P.getUnitInc() << " "; 415 else 416 dbgs() << " "; 417 SU->dump(DAG); 418} 419#endif 420 421/// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor 422/// of SU, return it, otherwise return null. 423static SUnit *getSingleUnscheduledPred(SUnit *SU) { 424 SUnit *OnlyAvailablePred = 0; 425 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 426 I != E; ++I) { 427 SUnit &Pred = *I->getSUnit(); 428 if (!Pred.isScheduled) { 429 // We found an available, but not scheduled, predecessor. If it's the 430 // only one we have found, keep track of it... otherwise give up. 431 if (OnlyAvailablePred && OnlyAvailablePred != &Pred) 432 return 0; 433 OnlyAvailablePred = &Pred; 434 } 435 } 436 return OnlyAvailablePred; 437} 438 439/// getSingleUnscheduledSucc - If there is exactly one unscheduled successor 440/// of SU, return it, otherwise return null. 441static SUnit *getSingleUnscheduledSucc(SUnit *SU) { 442 SUnit *OnlyAvailableSucc = 0; 443 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 444 I != E; ++I) { 445 SUnit &Succ = *I->getSUnit(); 446 if (!Succ.isScheduled) { 447 // We found an available, but not scheduled, successor. If it's the 448 // only one we have found, keep track of it... otherwise give up. 449 if (OnlyAvailableSucc && OnlyAvailableSucc != &Succ) 450 return 0; 451 OnlyAvailableSucc = &Succ; 452 } 453 } 454 return OnlyAvailableSucc; 455} 456 457// Constants used to denote relative importance of 458// heuristic components for cost computation. 459static const unsigned PriorityOne = 200; 460static const unsigned PriorityTwo = 50; 461static const unsigned ScaleTwo = 10; 462static const unsigned FactorOne = 2; 463 464/// Single point to compute overall scheduling cost. 465/// TODO: More heuristics will be used soon. 466int ConvergingVLIWScheduler::SchedulingCost(ReadyQueue &Q, SUnit *SU, 467 SchedCandidate &Candidate, 468 RegPressureDelta &Delta, 469 bool verbose) { 470 // Initial trivial priority. 471 int ResCount = 1; 472 473 // Do not waste time on a node that is already scheduled. 474 if (!SU || SU->isScheduled) 475 return ResCount; 476 477 // Forced priority is high. 478 if (SU->isScheduleHigh) 479 ResCount += PriorityOne; 480 481 // Critical path first. 482 if (Q.getID() == TopQID) { 483 ResCount += (SU->getHeight() * ScaleTwo); 484 485 // If resources are available for it, multiply the 486 // chance of scheduling. 487 if (Top.ResourceModel->isResourceAvailable(SU)) 488 ResCount <<= FactorOne; 489 } else { 490 ResCount += (SU->getDepth() * ScaleTwo); 491 492 // If resources are available for it, multiply the 493 // chance of scheduling. 494 if (Bot.ResourceModel->isResourceAvailable(SU)) 495 ResCount <<= FactorOne; 496 } 497 498 unsigned NumNodesBlocking = 0; 499 if (Q.getID() == TopQID) { 500 // How many SUs does it block from scheduling? 501 // Look at all of the successors of this node. 502 // Count the number of nodes that 503 // this node is the sole unscheduled node for. 504 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 505 I != E; ++I) 506 if (getSingleUnscheduledPred(I->getSUnit()) == SU) 507 ++NumNodesBlocking; 508 } else { 509 // How many unscheduled predecessors block this node? 510 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 511 I != E; ++I) 512 if (getSingleUnscheduledSucc(I->getSUnit()) == SU) 513 ++NumNodesBlocking; 514 } 515 ResCount += (NumNodesBlocking * ScaleTwo); 516 517 // Factor in reg pressure as a heuristic. 518 ResCount -= (Delta.Excess.getUnitInc()*PriorityTwo); 519 ResCount -= (Delta.CriticalMax.getUnitInc()*PriorityTwo); 520 521 DEBUG(if (verbose) dbgs() << " Total(" << ResCount << ")"); 522 523 return ResCount; 524} 525 526/// Pick the best candidate from the top queue. 527/// 528/// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during 529/// DAG building. To adjust for the current scheduling location we need to 530/// maintain the number of vreg uses remaining to be top-scheduled. 531ConvergingVLIWScheduler::CandResult ConvergingVLIWScheduler:: 532pickNodeFromQueue(ReadyQueue &Q, const RegPressureTracker &RPTracker, 533 SchedCandidate &Candidate) { 534 DEBUG(Q.dump()); 535 536 // getMaxPressureDelta temporarily modifies the tracker. 537 RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker); 538 539 // BestSU remains NULL if no top candidates beat the best existing candidate. 540 CandResult FoundCandidate = NoCand; 541 for (ReadyQueue::iterator I = Q.begin(), E = Q.end(); I != E; ++I) { 542 RegPressureDelta RPDelta; 543 TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta, 544 DAG->getRegionCriticalPSets(), 545 DAG->getRegPressure().MaxSetPressure); 546 547 int CurrentCost = SchedulingCost(Q, *I, Candidate, RPDelta, false); 548 549 // Initialize the candidate if needed. 550 if (!Candidate.SU) { 551 Candidate.SU = *I; 552 Candidate.RPDelta = RPDelta; 553 Candidate.SCost = CurrentCost; 554 FoundCandidate = NodeOrder; 555 continue; 556 } 557 558 // Best cost. 559 if (CurrentCost > Candidate.SCost) { 560 DEBUG(traceCandidate("CCAND", Q, *I)); 561 Candidate.SU = *I; 562 Candidate.RPDelta = RPDelta; 563 Candidate.SCost = CurrentCost; 564 FoundCandidate = BestCost; 565 continue; 566 } 567 568 // Fall through to original instruction order. 569 // Only consider node order if Candidate was chosen from this Q. 570 if (FoundCandidate == NoCand) 571 continue; 572 } 573 return FoundCandidate; 574} 575 576/// Pick the best candidate node from either the top or bottom queue. 577SUnit *ConvergingVLIWScheduler::pickNodeBidrectional(bool &IsTopNode) { 578 // Schedule as far as possible in the direction of no choice. This is most 579 // efficient, but also provides the best heuristics for CriticalPSets. 580 if (SUnit *SU = Bot.pickOnlyChoice()) { 581 IsTopNode = false; 582 return SU; 583 } 584 if (SUnit *SU = Top.pickOnlyChoice()) { 585 IsTopNode = true; 586 return SU; 587 } 588 SchedCandidate BotCand; 589 // Prefer bottom scheduling when heuristics are silent. 590 CandResult BotResult = pickNodeFromQueue(Bot.Available, 591 DAG->getBotRPTracker(), BotCand); 592 assert(BotResult != NoCand && "failed to find the first candidate"); 593 594 // If either Q has a single candidate that provides the least increase in 595 // Excess pressure, we can immediately schedule from that Q. 596 // 597 // RegionCriticalPSets summarizes the pressure within the scheduled region and 598 // affects picking from either Q. If scheduling in one direction must 599 // increase pressure for one of the excess PSets, then schedule in that 600 // direction first to provide more freedom in the other direction. 601 if (BotResult == SingleExcess || BotResult == SingleCritical) { 602 IsTopNode = false; 603 return BotCand.SU; 604 } 605 // Check if the top Q has a better candidate. 606 SchedCandidate TopCand; 607 CandResult TopResult = pickNodeFromQueue(Top.Available, 608 DAG->getTopRPTracker(), TopCand); 609 assert(TopResult != NoCand && "failed to find the first candidate"); 610 611 if (TopResult == SingleExcess || TopResult == SingleCritical) { 612 IsTopNode = true; 613 return TopCand.SU; 614 } 615 // If either Q has a single candidate that minimizes pressure above the 616 // original region's pressure pick it. 617 if (BotResult == SingleMax) { 618 IsTopNode = false; 619 return BotCand.SU; 620 } 621 if (TopResult == SingleMax) { 622 IsTopNode = true; 623 return TopCand.SU; 624 } 625 if (TopCand.SCost > BotCand.SCost) { 626 IsTopNode = true; 627 return TopCand.SU; 628 } 629 // Otherwise prefer the bottom candidate in node order. 630 IsTopNode = false; 631 return BotCand.SU; 632} 633 634/// Pick the best node to balance the schedule. Implements MachineSchedStrategy. 635SUnit *ConvergingVLIWScheduler::pickNode(bool &IsTopNode) { 636 if (DAG->top() == DAG->bottom()) { 637 assert(Top.Available.empty() && Top.Pending.empty() && 638 Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage"); 639 return NULL; 640 } 641 SUnit *SU; 642 if (llvm::ForceTopDown) { 643 SU = Top.pickOnlyChoice(); 644 if (!SU) { 645 SchedCandidate TopCand; 646 CandResult TopResult = 647 pickNodeFromQueue(Top.Available, DAG->getTopRPTracker(), TopCand); 648 assert(TopResult != NoCand && "failed to find the first candidate"); 649 (void)TopResult; 650 SU = TopCand.SU; 651 } 652 IsTopNode = true; 653 } else if (llvm::ForceBottomUp) { 654 SU = Bot.pickOnlyChoice(); 655 if (!SU) { 656 SchedCandidate BotCand; 657 CandResult BotResult = 658 pickNodeFromQueue(Bot.Available, DAG->getBotRPTracker(), BotCand); 659 assert(BotResult != NoCand && "failed to find the first candidate"); 660 (void)BotResult; 661 SU = BotCand.SU; 662 } 663 IsTopNode = false; 664 } else { 665 SU = pickNodeBidrectional(IsTopNode); 666 } 667 if (SU->isTopReady()) 668 Top.removeReady(SU); 669 if (SU->isBottomReady()) 670 Bot.removeReady(SU); 671 672 DEBUG(dbgs() << "*** " << (IsTopNode ? "Top" : "Bottom") 673 << " Scheduling Instruction in cycle " 674 << (IsTopNode ? Top.CurrCycle : Bot.CurrCycle) << '\n'; 675 SU->dump(DAG)); 676 return SU; 677} 678 679/// Update the scheduler's state after scheduling a node. This is the same node 680/// that was just returned by pickNode(). However, VLIWMachineScheduler needs 681/// to update it's state based on the current cycle before MachineSchedStrategy 682/// does. 683void ConvergingVLIWScheduler::schedNode(SUnit *SU, bool IsTopNode) { 684 if (IsTopNode) { 685 SU->TopReadyCycle = Top.CurrCycle; 686 Top.bumpNode(SU); 687 } else { 688 SU->BotReadyCycle = Bot.CurrCycle; 689 Bot.bumpNode(SU); 690 } 691} 692