1//===- MachineScheduler.cpp - Machine Instruction Scheduler ---------------===// 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 "llvm/CodeGen/LiveIntervalAnalysis.h" 18#include "llvm/CodeGen/MachineScheduler.h" 19#include "llvm/CodeGen/Passes.h" 20#include "llvm/CodeGen/RegisterClassInfo.h" 21#include "llvm/CodeGen/ScheduleDAGILP.h" 22#include "llvm/CodeGen/ScheduleHazardRecognizer.h" 23#include "llvm/Analysis/AliasAnalysis.h" 24#include "llvm/Support/CommandLine.h" 25#include "llvm/Support/Debug.h" 26#include "llvm/Support/ErrorHandling.h" 27#include "llvm/Support/raw_ostream.h" 28#include "llvm/ADT/OwningPtr.h" 29#include "llvm/ADT/PriorityQueue.h" 30 31#include <queue> 32 33using namespace llvm; 34 35namespace llvm { 36cl::opt<bool> ForceTopDown("misched-topdown", cl::Hidden, 37 cl::desc("Force top-down list scheduling")); 38cl::opt<bool> ForceBottomUp("misched-bottomup", cl::Hidden, 39 cl::desc("Force bottom-up list scheduling")); 40} 41 42#ifndef NDEBUG 43static cl::opt<bool> ViewMISchedDAGs("view-misched-dags", cl::Hidden, 44 cl::desc("Pop up a window to show MISched dags after they are processed")); 45 46static cl::opt<unsigned> MISchedCutoff("misched-cutoff", cl::Hidden, 47 cl::desc("Stop scheduling after N instructions"), cl::init(~0U)); 48#else 49static bool ViewMISchedDAGs = false; 50#endif // NDEBUG 51 52//===----------------------------------------------------------------------===// 53// Machine Instruction Scheduling Pass and Registry 54//===----------------------------------------------------------------------===// 55 56MachineSchedContext::MachineSchedContext(): 57 MF(0), MLI(0), MDT(0), PassConfig(0), AA(0), LIS(0) { 58 RegClassInfo = new RegisterClassInfo(); 59} 60 61MachineSchedContext::~MachineSchedContext() { 62 delete RegClassInfo; 63} 64 65namespace { 66/// MachineScheduler runs after coalescing and before register allocation. 67class MachineScheduler : public MachineSchedContext, 68 public MachineFunctionPass { 69public: 70 MachineScheduler(); 71 72 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 73 74 virtual void releaseMemory() {} 75 76 virtual bool runOnMachineFunction(MachineFunction&); 77 78 virtual void print(raw_ostream &O, const Module* = 0) const; 79 80 static char ID; // Class identification, replacement for typeinfo 81}; 82} // namespace 83 84char MachineScheduler::ID = 0; 85 86char &llvm::MachineSchedulerID = MachineScheduler::ID; 87 88INITIALIZE_PASS_BEGIN(MachineScheduler, "misched", 89 "Machine Instruction Scheduler", false, false) 90INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 91INITIALIZE_PASS_DEPENDENCY(SlotIndexes) 92INITIALIZE_PASS_DEPENDENCY(LiveIntervals) 93INITIALIZE_PASS_END(MachineScheduler, "misched", 94 "Machine Instruction Scheduler", false, false) 95 96MachineScheduler::MachineScheduler() 97: MachineFunctionPass(ID) { 98 initializeMachineSchedulerPass(*PassRegistry::getPassRegistry()); 99} 100 101void MachineScheduler::getAnalysisUsage(AnalysisUsage &AU) const { 102 AU.setPreservesCFG(); 103 AU.addRequiredID(MachineDominatorsID); 104 AU.addRequired<MachineLoopInfo>(); 105 AU.addRequired<AliasAnalysis>(); 106 AU.addRequired<TargetPassConfig>(); 107 AU.addRequired<SlotIndexes>(); 108 AU.addPreserved<SlotIndexes>(); 109 AU.addRequired<LiveIntervals>(); 110 AU.addPreserved<LiveIntervals>(); 111 MachineFunctionPass::getAnalysisUsage(AU); 112} 113 114MachinePassRegistry MachineSchedRegistry::Registry; 115 116/// A dummy default scheduler factory indicates whether the scheduler 117/// is overridden on the command line. 118static ScheduleDAGInstrs *useDefaultMachineSched(MachineSchedContext *C) { 119 return 0; 120} 121 122/// MachineSchedOpt allows command line selection of the scheduler. 123static cl::opt<MachineSchedRegistry::ScheduleDAGCtor, false, 124 RegisterPassParser<MachineSchedRegistry> > 125MachineSchedOpt("misched", 126 cl::init(&useDefaultMachineSched), cl::Hidden, 127 cl::desc("Machine instruction scheduler to use")); 128 129static MachineSchedRegistry 130DefaultSchedRegistry("default", "Use the target's default scheduler choice.", 131 useDefaultMachineSched); 132 133/// Forward declare the standard machine scheduler. This will be used as the 134/// default scheduler if the target does not set a default. 135static ScheduleDAGInstrs *createConvergingSched(MachineSchedContext *C); 136 137 138/// Decrement this iterator until reaching the top or a non-debug instr. 139static MachineBasicBlock::iterator 140priorNonDebug(MachineBasicBlock::iterator I, MachineBasicBlock::iterator Beg) { 141 assert(I != Beg && "reached the top of the region, cannot decrement"); 142 while (--I != Beg) { 143 if (!I->isDebugValue()) 144 break; 145 } 146 return I; 147} 148 149/// If this iterator is a debug value, increment until reaching the End or a 150/// non-debug instruction. 151static MachineBasicBlock::iterator 152nextIfDebug(MachineBasicBlock::iterator I, MachineBasicBlock::iterator End) { 153 for(; I != End; ++I) { 154 if (!I->isDebugValue()) 155 break; 156 } 157 return I; 158} 159 160/// Top-level MachineScheduler pass driver. 161/// 162/// Visit blocks in function order. Divide each block into scheduling regions 163/// and visit them bottom-up. Visiting regions bottom-up is not required, but is 164/// consistent with the DAG builder, which traverses the interior of the 165/// scheduling regions bottom-up. 166/// 167/// This design avoids exposing scheduling boundaries to the DAG builder, 168/// simplifying the DAG builder's support for "special" target instructions. 169/// At the same time the design allows target schedulers to operate across 170/// scheduling boundaries, for example to bundle the boudary instructions 171/// without reordering them. This creates complexity, because the target 172/// scheduler must update the RegionBegin and RegionEnd positions cached by 173/// ScheduleDAGInstrs whenever adding or removing instructions. A much simpler 174/// design would be to split blocks at scheduling boundaries, but LLVM has a 175/// general bias against block splitting purely for implementation simplicity. 176bool MachineScheduler::runOnMachineFunction(MachineFunction &mf) { 177 DEBUG(dbgs() << "Before MISsched:\n"; mf.print(dbgs())); 178 179 // Initialize the context of the pass. 180 MF = &mf; 181 MLI = &getAnalysis<MachineLoopInfo>(); 182 MDT = &getAnalysis<MachineDominatorTree>(); 183 PassConfig = &getAnalysis<TargetPassConfig>(); 184 AA = &getAnalysis<AliasAnalysis>(); 185 186 LIS = &getAnalysis<LiveIntervals>(); 187 const TargetInstrInfo *TII = MF->getTarget().getInstrInfo(); 188 189 RegClassInfo->runOnMachineFunction(*MF); 190 191 // Select the scheduler, or set the default. 192 MachineSchedRegistry::ScheduleDAGCtor Ctor = MachineSchedOpt; 193 if (Ctor == useDefaultMachineSched) { 194 // Get the default scheduler set by the target. 195 Ctor = MachineSchedRegistry::getDefault(); 196 if (!Ctor) { 197 Ctor = createConvergingSched; 198 MachineSchedRegistry::setDefault(Ctor); 199 } 200 } 201 // Instantiate the selected scheduler. 202 OwningPtr<ScheduleDAGInstrs> Scheduler(Ctor(this)); 203 204 // Visit all machine basic blocks. 205 // 206 // TODO: Visit blocks in global postorder or postorder within the bottom-up 207 // loop tree. Then we can optionally compute global RegPressure. 208 for (MachineFunction::iterator MBB = MF->begin(), MBBEnd = MF->end(); 209 MBB != MBBEnd; ++MBB) { 210 211 Scheduler->startBlock(MBB); 212 213 // Break the block into scheduling regions [I, RegionEnd), and schedule each 214 // region as soon as it is discovered. RegionEnd points the scheduling 215 // boundary at the bottom of the region. The DAG does not include RegionEnd, 216 // but the region does (i.e. the next RegionEnd is above the previous 217 // RegionBegin). If the current block has no terminator then RegionEnd == 218 // MBB->end() for the bottom region. 219 // 220 // The Scheduler may insert instructions during either schedule() or 221 // exitRegion(), even for empty regions. So the local iterators 'I' and 222 // 'RegionEnd' are invalid across these calls. 223 unsigned RemainingCount = MBB->size(); 224 for(MachineBasicBlock::iterator RegionEnd = MBB->end(); 225 RegionEnd != MBB->begin(); RegionEnd = Scheduler->begin()) { 226 227 // Avoid decrementing RegionEnd for blocks with no terminator. 228 if (RegionEnd != MBB->end() 229 || TII->isSchedulingBoundary(llvm::prior(RegionEnd), MBB, *MF)) { 230 --RegionEnd; 231 // Count the boundary instruction. 232 --RemainingCount; 233 } 234 235 // The next region starts above the previous region. Look backward in the 236 // instruction stream until we find the nearest boundary. 237 MachineBasicBlock::iterator I = RegionEnd; 238 for(;I != MBB->begin(); --I, --RemainingCount) { 239 if (TII->isSchedulingBoundary(llvm::prior(I), MBB, *MF)) 240 break; 241 } 242 // Notify the scheduler of the region, even if we may skip scheduling 243 // it. Perhaps it still needs to be bundled. 244 Scheduler->enterRegion(MBB, I, RegionEnd, RemainingCount); 245 246 // Skip empty scheduling regions (0 or 1 schedulable instructions). 247 if (I == RegionEnd || I == llvm::prior(RegionEnd)) { 248 // Close the current region. Bundle the terminator if needed. 249 // This invalidates 'RegionEnd' and 'I'. 250 Scheduler->exitRegion(); 251 continue; 252 } 253 DEBUG(dbgs() << "********** MI Scheduling **********\n"); 254 DEBUG(dbgs() << MF->getName() 255 << ":BB#" << MBB->getNumber() << "\n From: " << *I << " To: "; 256 if (RegionEnd != MBB->end()) dbgs() << *RegionEnd; 257 else dbgs() << "End"; 258 dbgs() << " Remaining: " << RemainingCount << "\n"); 259 260 // Schedule a region: possibly reorder instructions. 261 // This invalidates 'RegionEnd' and 'I'. 262 Scheduler->schedule(); 263 264 // Close the current region. 265 Scheduler->exitRegion(); 266 267 // Scheduling has invalidated the current iterator 'I'. Ask the 268 // scheduler for the top of it's scheduled region. 269 RegionEnd = Scheduler->begin(); 270 } 271 assert(RemainingCount == 0 && "Instruction count mismatch!"); 272 Scheduler->finishBlock(); 273 } 274 Scheduler->finalizeSchedule(); 275 DEBUG(LIS->print(dbgs())); 276 return true; 277} 278 279void MachineScheduler::print(raw_ostream &O, const Module* m) const { 280 // unimplemented 281} 282 283#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 284void ReadyQueue::dump() { 285 dbgs() << Name << ": "; 286 for (unsigned i = 0, e = Queue.size(); i < e; ++i) 287 dbgs() << Queue[i]->NodeNum << " "; 288 dbgs() << "\n"; 289} 290#endif 291 292//===----------------------------------------------------------------------===// 293// ScheduleDAGMI - Base class for MachineInstr scheduling with LiveIntervals 294// preservation. 295//===----------------------------------------------------------------------===// 296 297/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. When 298/// NumPredsLeft reaches zero, release the successor node. 299/// 300/// FIXME: Adjust SuccSU height based on MinLatency. 301void ScheduleDAGMI::releaseSucc(SUnit *SU, SDep *SuccEdge) { 302 SUnit *SuccSU = SuccEdge->getSUnit(); 303 304#ifndef NDEBUG 305 if (SuccSU->NumPredsLeft == 0) { 306 dbgs() << "*** Scheduling failed! ***\n"; 307 SuccSU->dump(this); 308 dbgs() << " has been released too many times!\n"; 309 llvm_unreachable(0); 310 } 311#endif 312 --SuccSU->NumPredsLeft; 313 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) 314 SchedImpl->releaseTopNode(SuccSU); 315} 316 317/// releaseSuccessors - Call releaseSucc on each of SU's successors. 318void ScheduleDAGMI::releaseSuccessors(SUnit *SU) { 319 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 320 I != E; ++I) { 321 releaseSucc(SU, &*I); 322 } 323} 324 325/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. When 326/// NumSuccsLeft reaches zero, release the predecessor node. 327/// 328/// FIXME: Adjust PredSU height based on MinLatency. 329void ScheduleDAGMI::releasePred(SUnit *SU, SDep *PredEdge) { 330 SUnit *PredSU = PredEdge->getSUnit(); 331 332#ifndef NDEBUG 333 if (PredSU->NumSuccsLeft == 0) { 334 dbgs() << "*** Scheduling failed! ***\n"; 335 PredSU->dump(this); 336 dbgs() << " has been released too many times!\n"; 337 llvm_unreachable(0); 338 } 339#endif 340 --PredSU->NumSuccsLeft; 341 if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) 342 SchedImpl->releaseBottomNode(PredSU); 343} 344 345/// releasePredecessors - Call releasePred on each of SU's predecessors. 346void ScheduleDAGMI::releasePredecessors(SUnit *SU) { 347 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 348 I != E; ++I) { 349 releasePred(SU, &*I); 350 } 351} 352 353void ScheduleDAGMI::moveInstruction(MachineInstr *MI, 354 MachineBasicBlock::iterator InsertPos) { 355 // Advance RegionBegin if the first instruction moves down. 356 if (&*RegionBegin == MI) 357 ++RegionBegin; 358 359 // Update the instruction stream. 360 BB->splice(InsertPos, BB, MI); 361 362 // Update LiveIntervals 363 LIS->handleMove(MI); 364 365 // Recede RegionBegin if an instruction moves above the first. 366 if (RegionBegin == InsertPos) 367 RegionBegin = MI; 368} 369 370bool ScheduleDAGMI::checkSchedLimit() { 371#ifndef NDEBUG 372 if (NumInstrsScheduled == MISchedCutoff && MISchedCutoff != ~0U) { 373 CurrentTop = CurrentBottom; 374 return false; 375 } 376 ++NumInstrsScheduled; 377#endif 378 return true; 379} 380 381/// enterRegion - Called back from MachineScheduler::runOnMachineFunction after 382/// crossing a scheduling boundary. [begin, end) includes all instructions in 383/// the region, including the boundary itself and single-instruction regions 384/// that don't get scheduled. 385void ScheduleDAGMI::enterRegion(MachineBasicBlock *bb, 386 MachineBasicBlock::iterator begin, 387 MachineBasicBlock::iterator end, 388 unsigned endcount) 389{ 390 ScheduleDAGInstrs::enterRegion(bb, begin, end, endcount); 391 392 // For convenience remember the end of the liveness region. 393 LiveRegionEnd = 394 (RegionEnd == bb->end()) ? RegionEnd : llvm::next(RegionEnd); 395} 396 397// Setup the register pressure trackers for the top scheduled top and bottom 398// scheduled regions. 399void ScheduleDAGMI::initRegPressure() { 400 TopRPTracker.init(&MF, RegClassInfo, LIS, BB, RegionBegin); 401 BotRPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd); 402 403 // Close the RPTracker to finalize live ins. 404 RPTracker.closeRegion(); 405 406 DEBUG(RPTracker.getPressure().dump(TRI)); 407 408 // Initialize the live ins and live outs. 409 TopRPTracker.addLiveRegs(RPTracker.getPressure().LiveInRegs); 410 BotRPTracker.addLiveRegs(RPTracker.getPressure().LiveOutRegs); 411 412 // Close one end of the tracker so we can call 413 // getMaxUpward/DownwardPressureDelta before advancing across any 414 // instructions. This converts currently live regs into live ins/outs. 415 TopRPTracker.closeTop(); 416 BotRPTracker.closeBottom(); 417 418 // Account for liveness generated by the region boundary. 419 if (LiveRegionEnd != RegionEnd) 420 BotRPTracker.recede(); 421 422 assert(BotRPTracker.getPos() == RegionEnd && "Can't find the region bottom"); 423 424 // Cache the list of excess pressure sets in this region. This will also track 425 // the max pressure in the scheduled code for these sets. 426 RegionCriticalPSets.clear(); 427 std::vector<unsigned> RegionPressure = RPTracker.getPressure().MaxSetPressure; 428 for (unsigned i = 0, e = RegionPressure.size(); i < e; ++i) { 429 unsigned Limit = TRI->getRegPressureSetLimit(i); 430 DEBUG(dbgs() << TRI->getRegPressureSetName(i) 431 << "Limit " << Limit 432 << " Actual " << RegionPressure[i] << "\n"); 433 if (RegionPressure[i] > Limit) 434 RegionCriticalPSets.push_back(PressureElement(i, 0)); 435 } 436 DEBUG(dbgs() << "Excess PSets: "; 437 for (unsigned i = 0, e = RegionCriticalPSets.size(); i != e; ++i) 438 dbgs() << TRI->getRegPressureSetName( 439 RegionCriticalPSets[i].PSetID) << " "; 440 dbgs() << "\n"); 441} 442 443// FIXME: When the pressure tracker deals in pressure differences then we won't 444// iterate over all RegionCriticalPSets[i]. 445void ScheduleDAGMI:: 446updateScheduledPressure(std::vector<unsigned> NewMaxPressure) { 447 for (unsigned i = 0, e = RegionCriticalPSets.size(); i < e; ++i) { 448 unsigned ID = RegionCriticalPSets[i].PSetID; 449 int &MaxUnits = RegionCriticalPSets[i].UnitIncrease; 450 if ((int)NewMaxPressure[ID] > MaxUnits) 451 MaxUnits = NewMaxPressure[ID]; 452 } 453} 454 455/// schedule - Called back from MachineScheduler::runOnMachineFunction 456/// after setting up the current scheduling region. [RegionBegin, RegionEnd) 457/// only includes instructions that have DAG nodes, not scheduling boundaries. 458/// 459/// This is a skeletal driver, with all the functionality pushed into helpers, 460/// so that it can be easilly extended by experimental schedulers. Generally, 461/// implementing MachineSchedStrategy should be sufficient to implement a new 462/// scheduling algorithm. However, if a scheduler further subclasses 463/// ScheduleDAGMI then it will want to override this virtual method in order to 464/// update any specialized state. 465void ScheduleDAGMI::schedule() { 466 buildDAGWithRegPressure(); 467 468 postprocessDAG(); 469 470 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 471 SUnits[su].dumpAll(this)); 472 473 if (ViewMISchedDAGs) viewGraph(); 474 475 initQueues(); 476 477 bool IsTopNode = false; 478 while (SUnit *SU = SchedImpl->pickNode(IsTopNode)) { 479 assert(!SU->isScheduled && "Node already scheduled"); 480 if (!checkSchedLimit()) 481 break; 482 483 scheduleMI(SU, IsTopNode); 484 485 updateQueues(SU, IsTopNode); 486 } 487 assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone."); 488 489 placeDebugValues(); 490} 491 492/// Build the DAG and setup three register pressure trackers. 493void ScheduleDAGMI::buildDAGWithRegPressure() { 494 // Initialize the register pressure tracker used by buildSchedGraph. 495 RPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd); 496 497 // Account for liveness generate by the region boundary. 498 if (LiveRegionEnd != RegionEnd) 499 RPTracker.recede(); 500 501 // Build the DAG, and compute current register pressure. 502 buildSchedGraph(AA, &RPTracker); 503 if (ViewMISchedDAGs) viewGraph(); 504 505 // Initialize top/bottom trackers after computing region pressure. 506 initRegPressure(); 507} 508 509/// Apply each ScheduleDAGMutation step in order. 510void ScheduleDAGMI::postprocessDAG() { 511 for (unsigned i = 0, e = Mutations.size(); i < e; ++i) { 512 Mutations[i]->apply(this); 513 } 514} 515 516// Release all DAG roots for scheduling. 517void ScheduleDAGMI::releaseRoots() { 518 SmallVector<SUnit*, 16> BotRoots; 519 520 for (std::vector<SUnit>::iterator 521 I = SUnits.begin(), E = SUnits.end(); I != E; ++I) { 522 // A SUnit is ready to top schedule if it has no predecessors. 523 if (I->Preds.empty()) 524 SchedImpl->releaseTopNode(&(*I)); 525 // A SUnit is ready to bottom schedule if it has no successors. 526 if (I->Succs.empty()) 527 BotRoots.push_back(&(*I)); 528 } 529 // Release bottom roots in reverse order so the higher priority nodes appear 530 // first. This is more natural and slightly more efficient. 531 for (SmallVectorImpl<SUnit*>::const_reverse_iterator 532 I = BotRoots.rbegin(), E = BotRoots.rend(); I != E; ++I) 533 SchedImpl->releaseBottomNode(*I); 534} 535 536/// Identify DAG roots and setup scheduler queues. 537void ScheduleDAGMI::initQueues() { 538 539 // Initialize the strategy before modifying the DAG. 540 SchedImpl->initialize(this); 541 542 // Release edges from the special Entry node or to the special Exit node. 543 releaseSuccessors(&EntrySU); 544 releasePredecessors(&ExitSU); 545 546 // Release all DAG roots for scheduling. 547 releaseRoots(); 548 549 SchedImpl->registerRoots(); 550 551 CurrentTop = nextIfDebug(RegionBegin, RegionEnd); 552 CurrentBottom = RegionEnd; 553} 554 555/// Move an instruction and update register pressure. 556void ScheduleDAGMI::scheduleMI(SUnit *SU, bool IsTopNode) { 557 // Move the instruction to its new location in the instruction stream. 558 MachineInstr *MI = SU->getInstr(); 559 560 if (IsTopNode) { 561 assert(SU->isTopReady() && "node still has unscheduled dependencies"); 562 if (&*CurrentTop == MI) 563 CurrentTop = nextIfDebug(++CurrentTop, CurrentBottom); 564 else { 565 moveInstruction(MI, CurrentTop); 566 TopRPTracker.setPos(MI); 567 } 568 569 // Update top scheduled pressure. 570 TopRPTracker.advance(); 571 assert(TopRPTracker.getPos() == CurrentTop && "out of sync"); 572 updateScheduledPressure(TopRPTracker.getPressure().MaxSetPressure); 573 } 574 else { 575 assert(SU->isBottomReady() && "node still has unscheduled dependencies"); 576 MachineBasicBlock::iterator priorII = 577 priorNonDebug(CurrentBottom, CurrentTop); 578 if (&*priorII == MI) 579 CurrentBottom = priorII; 580 else { 581 if (&*CurrentTop == MI) { 582 CurrentTop = nextIfDebug(++CurrentTop, priorII); 583 TopRPTracker.setPos(CurrentTop); 584 } 585 moveInstruction(MI, CurrentBottom); 586 CurrentBottom = MI; 587 } 588 // Update bottom scheduled pressure. 589 BotRPTracker.recede(); 590 assert(BotRPTracker.getPos() == CurrentBottom && "out of sync"); 591 updateScheduledPressure(BotRPTracker.getPressure().MaxSetPressure); 592 } 593} 594 595/// Update scheduler queues after scheduling an instruction. 596void ScheduleDAGMI::updateQueues(SUnit *SU, bool IsTopNode) { 597 // Release dependent instructions for scheduling. 598 if (IsTopNode) 599 releaseSuccessors(SU); 600 else 601 releasePredecessors(SU); 602 603 SU->isScheduled = true; 604 605 // Notify the scheduling strategy after updating the DAG. 606 SchedImpl->schedNode(SU, IsTopNode); 607} 608 609/// Reinsert any remaining debug_values, just like the PostRA scheduler. 610void ScheduleDAGMI::placeDebugValues() { 611 // If first instruction was a DBG_VALUE then put it back. 612 if (FirstDbgValue) { 613 BB->splice(RegionBegin, BB, FirstDbgValue); 614 RegionBegin = FirstDbgValue; 615 } 616 617 for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator 618 DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) { 619 std::pair<MachineInstr *, MachineInstr *> P = *prior(DI); 620 MachineInstr *DbgValue = P.first; 621 MachineBasicBlock::iterator OrigPrevMI = P.second; 622 BB->splice(++OrigPrevMI, BB, DbgValue); 623 if (OrigPrevMI == llvm::prior(RegionEnd)) 624 RegionEnd = DbgValue; 625 } 626 DbgValues.clear(); 627 FirstDbgValue = NULL; 628} 629 630//===----------------------------------------------------------------------===// 631// ConvergingScheduler - Implementation of the standard MachineSchedStrategy. 632//===----------------------------------------------------------------------===// 633 634namespace { 635/// ConvergingScheduler shrinks the unscheduled zone using heuristics to balance 636/// the schedule. 637class ConvergingScheduler : public MachineSchedStrategy { 638 639 /// Store the state used by ConvergingScheduler heuristics, required for the 640 /// lifetime of one invocation of pickNode(). 641 struct SchedCandidate { 642 // The best SUnit candidate. 643 SUnit *SU; 644 645 // Register pressure values for the best candidate. 646 RegPressureDelta RPDelta; 647 648 SchedCandidate(): SU(NULL) {} 649 }; 650 /// Represent the type of SchedCandidate found within a single queue. 651 enum CandResult { 652 NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure }; 653 654 /// Each Scheduling boundary is associated with ready queues. It tracks the 655 /// current cycle in whichever direction at has moved, and maintains the state 656 /// of "hazards" and other interlocks at the current cycle. 657 struct SchedBoundary { 658 ScheduleDAGMI *DAG; 659 const TargetSchedModel *SchedModel; 660 661 ReadyQueue Available; 662 ReadyQueue Pending; 663 bool CheckPending; 664 665 ScheduleHazardRecognizer *HazardRec; 666 667 unsigned CurrCycle; 668 unsigned IssueCount; 669 670 /// MinReadyCycle - Cycle of the soonest available instruction. 671 unsigned MinReadyCycle; 672 673 // Remember the greatest min operand latency. 674 unsigned MaxMinLatency; 675 676 /// Pending queues extend the ready queues with the same ID and the 677 /// PendingFlag set. 678 SchedBoundary(unsigned ID, const Twine &Name): 679 DAG(0), SchedModel(0), Available(ID, Name+".A"), 680 Pending(ID << ConvergingScheduler::LogMaxQID, Name+".P"), 681 CheckPending(false), HazardRec(0), CurrCycle(0), IssueCount(0), 682 MinReadyCycle(UINT_MAX), MaxMinLatency(0) {} 683 684 ~SchedBoundary() { delete HazardRec; } 685 686 void init(ScheduleDAGMI *dag, const TargetSchedModel *smodel) { 687 DAG = dag; 688 SchedModel = smodel; 689 } 690 691 bool isTop() const { 692 return Available.getID() == ConvergingScheduler::TopQID; 693 } 694 695 bool checkHazard(SUnit *SU); 696 697 void releaseNode(SUnit *SU, unsigned ReadyCycle); 698 699 void bumpCycle(); 700 701 void bumpNode(SUnit *SU); 702 703 void releasePending(); 704 705 void removeReady(SUnit *SU); 706 707 SUnit *pickOnlyChoice(); 708 }; 709 710 ScheduleDAGMI *DAG; 711 const TargetSchedModel *SchedModel; 712 const TargetRegisterInfo *TRI; 713 714 // State of the top and bottom scheduled instruction boundaries. 715 SchedBoundary Top; 716 SchedBoundary Bot; 717 718public: 719 /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both) 720 enum { 721 TopQID = 1, 722 BotQID = 2, 723 LogMaxQID = 2 724 }; 725 726 ConvergingScheduler(): 727 DAG(0), SchedModel(0), TRI(0), Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {} 728 729 virtual void initialize(ScheduleDAGMI *dag); 730 731 virtual SUnit *pickNode(bool &IsTopNode); 732 733 virtual void schedNode(SUnit *SU, bool IsTopNode); 734 735 virtual void releaseTopNode(SUnit *SU); 736 737 virtual void releaseBottomNode(SUnit *SU); 738 739protected: 740 SUnit *pickNodeBidrectional(bool &IsTopNode); 741 742 CandResult pickNodeFromQueue(ReadyQueue &Q, 743 const RegPressureTracker &RPTracker, 744 SchedCandidate &Candidate); 745#ifndef NDEBUG 746 void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU, 747 PressureElement P = PressureElement()); 748#endif 749}; 750} // namespace 751 752void ConvergingScheduler::initialize(ScheduleDAGMI *dag) { 753 DAG = dag; 754 SchedModel = DAG->getSchedModel(); 755 TRI = DAG->TRI; 756 Top.init(DAG, SchedModel); 757 Bot.init(DAG, SchedModel); 758 759 // Initialize the HazardRecognizers. If itineraries don't exist, are empty, or 760 // are disabled, then these HazardRecs will be disabled. 761 const InstrItineraryData *Itin = SchedModel->getInstrItineraries(); 762 const TargetMachine &TM = DAG->MF.getTarget(); 763 Top.HazardRec = TM.getInstrInfo()->CreateTargetMIHazardRecognizer(Itin, DAG); 764 Bot.HazardRec = TM.getInstrInfo()->CreateTargetMIHazardRecognizer(Itin, DAG); 765 766 assert((!ForceTopDown || !ForceBottomUp) && 767 "-misched-topdown incompatible with -misched-bottomup"); 768} 769 770void ConvergingScheduler::releaseTopNode(SUnit *SU) { 771 if (SU->isScheduled) 772 return; 773 774 for (SUnit::succ_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 775 I != E; ++I) { 776 unsigned PredReadyCycle = I->getSUnit()->TopReadyCycle; 777 unsigned MinLatency = I->getMinLatency(); 778#ifndef NDEBUG 779 Top.MaxMinLatency = std::max(MinLatency, Top.MaxMinLatency); 780#endif 781 if (SU->TopReadyCycle < PredReadyCycle + MinLatency) 782 SU->TopReadyCycle = PredReadyCycle + MinLatency; 783 } 784 Top.releaseNode(SU, SU->TopReadyCycle); 785} 786 787void ConvergingScheduler::releaseBottomNode(SUnit *SU) { 788 if (SU->isScheduled) 789 return; 790 791 assert(SU->getInstr() && "Scheduled SUnit must have instr"); 792 793 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 794 I != E; ++I) { 795 unsigned SuccReadyCycle = I->getSUnit()->BotReadyCycle; 796 unsigned MinLatency = I->getMinLatency(); 797#ifndef NDEBUG 798 Bot.MaxMinLatency = std::max(MinLatency, Bot.MaxMinLatency); 799#endif 800 if (SU->BotReadyCycle < SuccReadyCycle + MinLatency) 801 SU->BotReadyCycle = SuccReadyCycle + MinLatency; 802 } 803 Bot.releaseNode(SU, SU->BotReadyCycle); 804} 805 806/// Does this SU have a hazard within the current instruction group. 807/// 808/// The scheduler supports two modes of hazard recognition. The first is the 809/// ScheduleHazardRecognizer API. It is a fully general hazard recognizer that 810/// supports highly complicated in-order reservation tables 811/// (ScoreboardHazardRecognizer) and arbitraty target-specific logic. 812/// 813/// The second is a streamlined mechanism that checks for hazards based on 814/// simple counters that the scheduler itself maintains. It explicitly checks 815/// for instruction dispatch limitations, including the number of micro-ops that 816/// can dispatch per cycle. 817/// 818/// TODO: Also check whether the SU must start a new group. 819bool ConvergingScheduler::SchedBoundary::checkHazard(SUnit *SU) { 820 if (HazardRec->isEnabled()) 821 return HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard; 822 823 unsigned uops = SchedModel->getNumMicroOps(SU->getInstr()); 824 if (IssueCount + uops > SchedModel->getIssueWidth()) 825 return true; 826 827 return false; 828} 829 830void ConvergingScheduler::SchedBoundary::releaseNode(SUnit *SU, 831 unsigned ReadyCycle) { 832 if (ReadyCycle < MinReadyCycle) 833 MinReadyCycle = ReadyCycle; 834 835 // Check for interlocks first. For the purpose of other heuristics, an 836 // instruction that cannot issue appears as if it's not in the ReadyQueue. 837 if (ReadyCycle > CurrCycle || checkHazard(SU)) 838 Pending.push(SU); 839 else 840 Available.push(SU); 841} 842 843/// Move the boundary of scheduled code by one cycle. 844void ConvergingScheduler::SchedBoundary::bumpCycle() { 845 unsigned Width = SchedModel->getIssueWidth(); 846 IssueCount = (IssueCount <= Width) ? 0 : IssueCount - Width; 847 848 assert(MinReadyCycle < UINT_MAX && "MinReadyCycle uninitialized"); 849 unsigned NextCycle = std::max(CurrCycle + 1, MinReadyCycle); 850 851 if (!HazardRec->isEnabled()) { 852 // Bypass HazardRec virtual calls. 853 CurrCycle = NextCycle; 854 } 855 else { 856 // Bypass getHazardType calls in case of long latency. 857 for (; CurrCycle != NextCycle; ++CurrCycle) { 858 if (isTop()) 859 HazardRec->AdvanceCycle(); 860 else 861 HazardRec->RecedeCycle(); 862 } 863 } 864 CheckPending = true; 865 866 DEBUG(dbgs() << "*** " << Available.getName() << " cycle " 867 << CurrCycle << '\n'); 868} 869 870/// Move the boundary of scheduled code by one SUnit. 871void ConvergingScheduler::SchedBoundary::bumpNode(SUnit *SU) { 872 // Update the reservation table. 873 if (HazardRec->isEnabled()) { 874 if (!isTop() && SU->isCall) { 875 // Calls are scheduled with their preceding instructions. For bottom-up 876 // scheduling, clear the pipeline state before emitting. 877 HazardRec->Reset(); 878 } 879 HazardRec->EmitInstruction(SU); 880 } 881 // Check the instruction group dispatch limit. 882 // TODO: Check if this SU must end a dispatch group. 883 IssueCount += SchedModel->getNumMicroOps(SU->getInstr()); 884 if (IssueCount >= SchedModel->getIssueWidth()) { 885 DEBUG(dbgs() << "*** Max instrs at cycle " << CurrCycle << '\n'); 886 bumpCycle(); 887 } 888} 889 890/// Release pending ready nodes in to the available queue. This makes them 891/// visible to heuristics. 892void ConvergingScheduler::SchedBoundary::releasePending() { 893 // If the available queue is empty, it is safe to reset MinReadyCycle. 894 if (Available.empty()) 895 MinReadyCycle = UINT_MAX; 896 897 // Check to see if any of the pending instructions are ready to issue. If 898 // so, add them to the available queue. 899 for (unsigned i = 0, e = Pending.size(); i != e; ++i) { 900 SUnit *SU = *(Pending.begin()+i); 901 unsigned ReadyCycle = isTop() ? SU->TopReadyCycle : SU->BotReadyCycle; 902 903 if (ReadyCycle < MinReadyCycle) 904 MinReadyCycle = ReadyCycle; 905 906 if (ReadyCycle > CurrCycle) 907 continue; 908 909 if (checkHazard(SU)) 910 continue; 911 912 Available.push(SU); 913 Pending.remove(Pending.begin()+i); 914 --i; --e; 915 } 916 CheckPending = false; 917} 918 919/// Remove SU from the ready set for this boundary. 920void ConvergingScheduler::SchedBoundary::removeReady(SUnit *SU) { 921 if (Available.isInQueue(SU)) 922 Available.remove(Available.find(SU)); 923 else { 924 assert(Pending.isInQueue(SU) && "bad ready count"); 925 Pending.remove(Pending.find(SU)); 926 } 927} 928 929/// If this queue only has one ready candidate, return it. As a side effect, 930/// advance the cycle until at least one node is ready. If multiple instructions 931/// are ready, return NULL. 932SUnit *ConvergingScheduler::SchedBoundary::pickOnlyChoice() { 933 if (CheckPending) 934 releasePending(); 935 936 for (unsigned i = 0; Available.empty(); ++i) { 937 assert(i <= (HazardRec->getMaxLookAhead() + MaxMinLatency) && 938 "permanent hazard"); (void)i; 939 bumpCycle(); 940 releasePending(); 941 } 942 if (Available.size() == 1) 943 return *Available.begin(); 944 return NULL; 945} 946 947#ifndef NDEBUG 948void ConvergingScheduler::traceCandidate(const char *Label, const ReadyQueue &Q, 949 SUnit *SU, PressureElement P) { 950 dbgs() << Label << " " << Q.getName() << " "; 951 if (P.isValid()) 952 dbgs() << TRI->getRegPressureSetName(P.PSetID) << ":" << P.UnitIncrease 953 << " "; 954 else 955 dbgs() << " "; 956 SU->dump(DAG); 957} 958#endif 959 960/// pickNodeFromQueue helper that returns true if the LHS reg pressure effect is 961/// more desirable than RHS from scheduling standpoint. 962static bool compareRPDelta(const RegPressureDelta &LHS, 963 const RegPressureDelta &RHS) { 964 // Compare each component of pressure in decreasing order of importance 965 // without checking if any are valid. Invalid PressureElements are assumed to 966 // have UnitIncrease==0, so are neutral. 967 968 // Avoid increasing the max critical pressure in the scheduled region. 969 if (LHS.Excess.UnitIncrease != RHS.Excess.UnitIncrease) 970 return LHS.Excess.UnitIncrease < RHS.Excess.UnitIncrease; 971 972 // Avoid increasing the max critical pressure in the scheduled region. 973 if (LHS.CriticalMax.UnitIncrease != RHS.CriticalMax.UnitIncrease) 974 return LHS.CriticalMax.UnitIncrease < RHS.CriticalMax.UnitIncrease; 975 976 // Avoid increasing the max pressure of the entire region. 977 if (LHS.CurrentMax.UnitIncrease != RHS.CurrentMax.UnitIncrease) 978 return LHS.CurrentMax.UnitIncrease < RHS.CurrentMax.UnitIncrease; 979 980 return false; 981} 982 983/// Pick the best candidate from the top queue. 984/// 985/// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during 986/// DAG building. To adjust for the current scheduling location we need to 987/// maintain the number of vreg uses remaining to be top-scheduled. 988ConvergingScheduler::CandResult ConvergingScheduler:: 989pickNodeFromQueue(ReadyQueue &Q, const RegPressureTracker &RPTracker, 990 SchedCandidate &Candidate) { 991 DEBUG(Q.dump()); 992 993 // getMaxPressureDelta temporarily modifies the tracker. 994 RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker); 995 996 // BestSU remains NULL if no top candidates beat the best existing candidate. 997 CandResult FoundCandidate = NoCand; 998 for (ReadyQueue::iterator I = Q.begin(), E = Q.end(); I != E; ++I) { 999 RegPressureDelta RPDelta; 1000 TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta, 1001 DAG->getRegionCriticalPSets(), 1002 DAG->getRegPressure().MaxSetPressure); 1003 1004 // Initialize the candidate if needed. 1005 if (!Candidate.SU) { 1006 Candidate.SU = *I; 1007 Candidate.RPDelta = RPDelta; 1008 FoundCandidate = NodeOrder; 1009 continue; 1010 } 1011 // Avoid exceeding the target's limit. 1012 if (RPDelta.Excess.UnitIncrease < Candidate.RPDelta.Excess.UnitIncrease) { 1013 DEBUG(traceCandidate("ECAND", Q, *I, RPDelta.Excess)); 1014 Candidate.SU = *I; 1015 Candidate.RPDelta = RPDelta; 1016 FoundCandidate = SingleExcess; 1017 continue; 1018 } 1019 if (RPDelta.Excess.UnitIncrease > Candidate.RPDelta.Excess.UnitIncrease) 1020 continue; 1021 if (FoundCandidate == SingleExcess) 1022 FoundCandidate = MultiPressure; 1023 1024 // Avoid increasing the max critical pressure in the scheduled region. 1025 if (RPDelta.CriticalMax.UnitIncrease 1026 < Candidate.RPDelta.CriticalMax.UnitIncrease) { 1027 DEBUG(traceCandidate("PCAND", Q, *I, RPDelta.CriticalMax)); 1028 Candidate.SU = *I; 1029 Candidate.RPDelta = RPDelta; 1030 FoundCandidate = SingleCritical; 1031 continue; 1032 } 1033 if (RPDelta.CriticalMax.UnitIncrease 1034 > Candidate.RPDelta.CriticalMax.UnitIncrease) 1035 continue; 1036 if (FoundCandidate == SingleCritical) 1037 FoundCandidate = MultiPressure; 1038 1039 // Avoid increasing the max pressure of the entire region. 1040 if (RPDelta.CurrentMax.UnitIncrease 1041 < Candidate.RPDelta.CurrentMax.UnitIncrease) { 1042 DEBUG(traceCandidate("MCAND", Q, *I, RPDelta.CurrentMax)); 1043 Candidate.SU = *I; 1044 Candidate.RPDelta = RPDelta; 1045 FoundCandidate = SingleMax; 1046 continue; 1047 } 1048 if (RPDelta.CurrentMax.UnitIncrease 1049 > Candidate.RPDelta.CurrentMax.UnitIncrease) 1050 continue; 1051 if (FoundCandidate == SingleMax) 1052 FoundCandidate = MultiPressure; 1053 1054 // Fall through to original instruction order. 1055 // Only consider node order if Candidate was chosen from this Q. 1056 if (FoundCandidate == NoCand) 1057 continue; 1058 1059 if ((Q.getID() == TopQID && (*I)->NodeNum < Candidate.SU->NodeNum) 1060 || (Q.getID() == BotQID && (*I)->NodeNum > Candidate.SU->NodeNum)) { 1061 DEBUG(traceCandidate("NCAND", Q, *I)); 1062 Candidate.SU = *I; 1063 Candidate.RPDelta = RPDelta; 1064 FoundCandidate = NodeOrder; 1065 } 1066 } 1067 return FoundCandidate; 1068} 1069 1070/// Pick the best candidate node from either the top or bottom queue. 1071SUnit *ConvergingScheduler::pickNodeBidrectional(bool &IsTopNode) { 1072 // Schedule as far as possible in the direction of no choice. This is most 1073 // efficient, but also provides the best heuristics for CriticalPSets. 1074 if (SUnit *SU = Bot.pickOnlyChoice()) { 1075 IsTopNode = false; 1076 return SU; 1077 } 1078 if (SUnit *SU = Top.pickOnlyChoice()) { 1079 IsTopNode = true; 1080 return SU; 1081 } 1082 SchedCandidate BotCand; 1083 // Prefer bottom scheduling when heuristics are silent. 1084 CandResult BotResult = pickNodeFromQueue(Bot.Available, 1085 DAG->getBotRPTracker(), BotCand); 1086 assert(BotResult != NoCand && "failed to find the first candidate"); 1087 1088 // If either Q has a single candidate that provides the least increase in 1089 // Excess pressure, we can immediately schedule from that Q. 1090 // 1091 // RegionCriticalPSets summarizes the pressure within the scheduled region and 1092 // affects picking from either Q. If scheduling in one direction must 1093 // increase pressure for one of the excess PSets, then schedule in that 1094 // direction first to provide more freedom in the other direction. 1095 if (BotResult == SingleExcess || BotResult == SingleCritical) { 1096 IsTopNode = false; 1097 return BotCand.SU; 1098 } 1099 // Check if the top Q has a better candidate. 1100 SchedCandidate TopCand; 1101 CandResult TopResult = pickNodeFromQueue(Top.Available, 1102 DAG->getTopRPTracker(), TopCand); 1103 assert(TopResult != NoCand && "failed to find the first candidate"); 1104 1105 if (TopResult == SingleExcess || TopResult == SingleCritical) { 1106 IsTopNode = true; 1107 return TopCand.SU; 1108 } 1109 // If either Q has a single candidate that minimizes pressure above the 1110 // original region's pressure pick it. 1111 if (BotResult == SingleMax) { 1112 IsTopNode = false; 1113 return BotCand.SU; 1114 } 1115 if (TopResult == SingleMax) { 1116 IsTopNode = true; 1117 return TopCand.SU; 1118 } 1119 // Check for a salient pressure difference and pick the best from either side. 1120 if (compareRPDelta(TopCand.RPDelta, BotCand.RPDelta)) { 1121 IsTopNode = true; 1122 return TopCand.SU; 1123 } 1124 // Otherwise prefer the bottom candidate in node order. 1125 IsTopNode = false; 1126 return BotCand.SU; 1127} 1128 1129/// Pick the best node to balance the schedule. Implements MachineSchedStrategy. 1130SUnit *ConvergingScheduler::pickNode(bool &IsTopNode) { 1131 if (DAG->top() == DAG->bottom()) { 1132 assert(Top.Available.empty() && Top.Pending.empty() && 1133 Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage"); 1134 return NULL; 1135 } 1136 SUnit *SU; 1137 do { 1138 if (ForceTopDown) { 1139 SU = Top.pickOnlyChoice(); 1140 if (!SU) { 1141 SchedCandidate TopCand; 1142 CandResult TopResult = 1143 pickNodeFromQueue(Top.Available, DAG->getTopRPTracker(), TopCand); 1144 assert(TopResult != NoCand && "failed to find the first candidate"); 1145 (void)TopResult; 1146 SU = TopCand.SU; 1147 } 1148 IsTopNode = true; 1149 } 1150 else if (ForceBottomUp) { 1151 SU = Bot.pickOnlyChoice(); 1152 if (!SU) { 1153 SchedCandidate BotCand; 1154 CandResult BotResult = 1155 pickNodeFromQueue(Bot.Available, DAG->getBotRPTracker(), BotCand); 1156 assert(BotResult != NoCand && "failed to find the first candidate"); 1157 (void)BotResult; 1158 SU = BotCand.SU; 1159 } 1160 IsTopNode = false; 1161 } 1162 else { 1163 SU = pickNodeBidrectional(IsTopNode); 1164 } 1165 } while (SU->isScheduled); 1166 1167 if (SU->isTopReady()) 1168 Top.removeReady(SU); 1169 if (SU->isBottomReady()) 1170 Bot.removeReady(SU); 1171 1172 DEBUG(dbgs() << "*** " << (IsTopNode ? "Top" : "Bottom") 1173 << " Scheduling Instruction in cycle " 1174 << (IsTopNode ? Top.CurrCycle : Bot.CurrCycle) << '\n'; 1175 SU->dump(DAG)); 1176 return SU; 1177} 1178 1179/// Update the scheduler's state after scheduling a node. This is the same node 1180/// that was just returned by pickNode(). However, ScheduleDAGMI needs to update 1181/// it's state based on the current cycle before MachineSchedStrategy does. 1182void ConvergingScheduler::schedNode(SUnit *SU, bool IsTopNode) { 1183 if (IsTopNode) { 1184 SU->TopReadyCycle = Top.CurrCycle; 1185 Top.bumpNode(SU); 1186 } 1187 else { 1188 SU->BotReadyCycle = Bot.CurrCycle; 1189 Bot.bumpNode(SU); 1190 } 1191} 1192 1193/// Create the standard converging machine scheduler. This will be used as the 1194/// default scheduler if the target does not set a default. 1195static ScheduleDAGInstrs *createConvergingSched(MachineSchedContext *C) { 1196 assert((!ForceTopDown || !ForceBottomUp) && 1197 "-misched-topdown incompatible with -misched-bottomup"); 1198 return new ScheduleDAGMI(C, new ConvergingScheduler()); 1199} 1200static MachineSchedRegistry 1201ConvergingSchedRegistry("converge", "Standard converging scheduler.", 1202 createConvergingSched); 1203 1204//===----------------------------------------------------------------------===// 1205// ILP Scheduler. Currently for experimental analysis of heuristics. 1206//===----------------------------------------------------------------------===// 1207 1208namespace { 1209/// \brief Order nodes by the ILP metric. 1210struct ILPOrder { 1211 ScheduleDAGILP *ILP; 1212 bool MaximizeILP; 1213 1214 ILPOrder(ScheduleDAGILP *ilp, bool MaxILP): ILP(ilp), MaximizeILP(MaxILP) {} 1215 1216 /// \brief Apply a less-than relation on node priority. 1217 bool operator()(const SUnit *A, const SUnit *B) const { 1218 // Return true if A comes after B in the Q. 1219 if (MaximizeILP) 1220 return ILP->getILP(A) < ILP->getILP(B); 1221 else 1222 return ILP->getILP(A) > ILP->getILP(B); 1223 } 1224}; 1225 1226/// \brief Schedule based on the ILP metric. 1227class ILPScheduler : public MachineSchedStrategy { 1228 ScheduleDAGILP ILP; 1229 ILPOrder Cmp; 1230 1231 std::vector<SUnit*> ReadyQ; 1232public: 1233 ILPScheduler(bool MaximizeILP) 1234 : ILP(/*BottomUp=*/true), Cmp(&ILP, MaximizeILP) {} 1235 1236 virtual void initialize(ScheduleDAGMI *DAG) { 1237 ReadyQ.clear(); 1238 ILP.resize(DAG->SUnits.size()); 1239 } 1240 1241 virtual void registerRoots() { 1242 for (std::vector<SUnit*>::const_iterator 1243 I = ReadyQ.begin(), E = ReadyQ.end(); I != E; ++I) { 1244 ILP.computeILP(*I); 1245 } 1246 } 1247 1248 /// Implement MachineSchedStrategy interface. 1249 /// ----------------------------------------- 1250 1251 virtual SUnit *pickNode(bool &IsTopNode) { 1252 if (ReadyQ.empty()) return NULL; 1253 pop_heap(ReadyQ.begin(), ReadyQ.end(), Cmp); 1254 SUnit *SU = ReadyQ.back(); 1255 ReadyQ.pop_back(); 1256 IsTopNode = false; 1257 DEBUG(dbgs() << "*** Scheduling " << *SU->getInstr() 1258 << " ILP: " << ILP.getILP(SU) << '\n'); 1259 return SU; 1260 } 1261 1262 virtual void schedNode(SUnit *, bool) {} 1263 1264 virtual void releaseTopNode(SUnit *) { /*only called for top roots*/ } 1265 1266 virtual void releaseBottomNode(SUnit *SU) { 1267 ReadyQ.push_back(SU); 1268 std::push_heap(ReadyQ.begin(), ReadyQ.end(), Cmp); 1269 } 1270}; 1271} // namespace 1272 1273static ScheduleDAGInstrs *createILPMaxScheduler(MachineSchedContext *C) { 1274 return new ScheduleDAGMI(C, new ILPScheduler(true)); 1275} 1276static ScheduleDAGInstrs *createILPMinScheduler(MachineSchedContext *C) { 1277 return new ScheduleDAGMI(C, new ILPScheduler(false)); 1278} 1279static MachineSchedRegistry ILPMaxRegistry( 1280 "ilpmax", "Schedule bottom-up for max ILP", createILPMaxScheduler); 1281static MachineSchedRegistry ILPMinRegistry( 1282 "ilpmin", "Schedule bottom-up for min ILP", createILPMinScheduler); 1283 1284//===----------------------------------------------------------------------===// 1285// Machine Instruction Shuffler for Correctness Testing 1286//===----------------------------------------------------------------------===// 1287 1288#ifndef NDEBUG 1289namespace { 1290/// Apply a less-than relation on the node order, which corresponds to the 1291/// instruction order prior to scheduling. IsReverse implements greater-than. 1292template<bool IsReverse> 1293struct SUnitOrder { 1294 bool operator()(SUnit *A, SUnit *B) const { 1295 if (IsReverse) 1296 return A->NodeNum > B->NodeNum; 1297 else 1298 return A->NodeNum < B->NodeNum; 1299 } 1300}; 1301 1302/// Reorder instructions as much as possible. 1303class InstructionShuffler : public MachineSchedStrategy { 1304 bool IsAlternating; 1305 bool IsTopDown; 1306 1307 // Using a less-than relation (SUnitOrder<false>) for the TopQ priority 1308 // gives nodes with a higher number higher priority causing the latest 1309 // instructions to be scheduled first. 1310 PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<false> > 1311 TopQ; 1312 // When scheduling bottom-up, use greater-than as the queue priority. 1313 PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<true> > 1314 BottomQ; 1315public: 1316 InstructionShuffler(bool alternate, bool topdown) 1317 : IsAlternating(alternate), IsTopDown(topdown) {} 1318 1319 virtual void initialize(ScheduleDAGMI *) { 1320 TopQ.clear(); 1321 BottomQ.clear(); 1322 } 1323 1324 /// Implement MachineSchedStrategy interface. 1325 /// ----------------------------------------- 1326 1327 virtual SUnit *pickNode(bool &IsTopNode) { 1328 SUnit *SU; 1329 if (IsTopDown) { 1330 do { 1331 if (TopQ.empty()) return NULL; 1332 SU = TopQ.top(); 1333 TopQ.pop(); 1334 } while (SU->isScheduled); 1335 IsTopNode = true; 1336 } 1337 else { 1338 do { 1339 if (BottomQ.empty()) return NULL; 1340 SU = BottomQ.top(); 1341 BottomQ.pop(); 1342 } while (SU->isScheduled); 1343 IsTopNode = false; 1344 } 1345 if (IsAlternating) 1346 IsTopDown = !IsTopDown; 1347 return SU; 1348 } 1349 1350 virtual void schedNode(SUnit *SU, bool IsTopNode) {} 1351 1352 virtual void releaseTopNode(SUnit *SU) { 1353 TopQ.push(SU); 1354 } 1355 virtual void releaseBottomNode(SUnit *SU) { 1356 BottomQ.push(SU); 1357 } 1358}; 1359} // namespace 1360 1361static ScheduleDAGInstrs *createInstructionShuffler(MachineSchedContext *C) { 1362 bool Alternate = !ForceTopDown && !ForceBottomUp; 1363 bool TopDown = !ForceBottomUp; 1364 assert((TopDown || !ForceTopDown) && 1365 "-misched-topdown incompatible with -misched-bottomup"); 1366 return new ScheduleDAGMI(C, new InstructionShuffler(Alternate, TopDown)); 1367} 1368static MachineSchedRegistry ShufflerRegistry( 1369 "shuffle", "Shuffle machine instructions alternating directions", 1370 createInstructionShuffler); 1371#endif // !NDEBUG 1372