MachineScheduler.cpp revision 81f1be3b5a920f75970bd3d3cdc65ada980bbfc1
1//===- MachineScheduler.cpp - Machine Instruction Scheduler ---------------===//excess 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 "RegisterClassInfo.h" 18#include "RegisterPressure.h" 19#include "llvm/CodeGen/LiveIntervalAnalysis.h" 20#include "llvm/CodeGen/MachineScheduler.h" 21#include "llvm/CodeGen/Passes.h" 22#include "llvm/CodeGen/ScheduleDAGInstrs.h" 23#include "llvm/Analysis/AliasAnalysis.h" 24#include "llvm/Target/TargetInstrInfo.h" 25#include "llvm/Support/CommandLine.h" 26#include "llvm/Support/Debug.h" 27#include "llvm/Support/ErrorHandling.h" 28#include "llvm/Support/raw_ostream.h" 29#include "llvm/ADT/OwningPtr.h" 30#include "llvm/ADT/PriorityQueue.h" 31 32#include <queue> 33 34using namespace llvm; 35 36static cl::opt<bool> ForceTopDown("misched-topdown", cl::Hidden, 37 cl::desc("Force top-down list scheduling")); 38static cl::opt<bool> ForceBottomUp("misched-bottomup", cl::Hidden, 39 cl::desc("Force bottom-up list scheduling")); 40 41#ifndef NDEBUG 42static cl::opt<bool> ViewMISchedDAGs("view-misched-dags", cl::Hidden, 43 cl::desc("Pop up a window to show MISched dags after they are processed")); 44 45static cl::opt<unsigned> MISchedCutoff("misched-cutoff", cl::Hidden, 46 cl::desc("Stop scheduling after N instructions"), cl::init(~0U)); 47#else 48static bool ViewMISchedDAGs = false; 49#endif // NDEBUG 50 51//===----------------------------------------------------------------------===// 52// Machine Instruction Scheduling Pass and Registry 53//===----------------------------------------------------------------------===// 54 55MachineSchedContext::MachineSchedContext(): 56 MF(0), MLI(0), MDT(0), PassConfig(0), AA(0), LIS(0) { 57 RegClassInfo = new RegisterClassInfo(); 58} 59 60MachineSchedContext::~MachineSchedContext() { 61 delete RegClassInfo; 62} 63 64namespace { 65/// MachineScheduler runs after coalescing and before register allocation. 66class MachineScheduler : public MachineSchedContext, 67 public MachineFunctionPass { 68public: 69 MachineScheduler(); 70 71 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 72 73 virtual void releaseMemory() {} 74 75 virtual bool runOnMachineFunction(MachineFunction&); 76 77 virtual void print(raw_ostream &O, const Module* = 0) const; 78 79 static char ID; // Class identification, replacement for typeinfo 80}; 81} // namespace 82 83char MachineScheduler::ID = 0; 84 85char &llvm::MachineSchedulerID = MachineScheduler::ID; 86 87INITIALIZE_PASS_BEGIN(MachineScheduler, "misched", 88 "Machine Instruction Scheduler", false, false) 89INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 90INITIALIZE_PASS_DEPENDENCY(SlotIndexes) 91INITIALIZE_PASS_DEPENDENCY(LiveIntervals) 92INITIALIZE_PASS_END(MachineScheduler, "misched", 93 "Machine Instruction Scheduler", false, false) 94 95MachineScheduler::MachineScheduler() 96: MachineFunctionPass(ID) { 97 initializeMachineSchedulerPass(*PassRegistry::getPassRegistry()); 98} 99 100void MachineScheduler::getAnalysisUsage(AnalysisUsage &AU) const { 101 AU.setPreservesCFG(); 102 AU.addRequiredID(MachineDominatorsID); 103 AU.addRequired<MachineLoopInfo>(); 104 AU.addRequired<AliasAnalysis>(); 105 AU.addRequired<TargetPassConfig>(); 106 AU.addRequired<SlotIndexes>(); 107 AU.addPreserved<SlotIndexes>(); 108 AU.addRequired<LiveIntervals>(); 109 AU.addPreserved<LiveIntervals>(); 110 MachineFunctionPass::getAnalysisUsage(AU); 111} 112 113MachinePassRegistry MachineSchedRegistry::Registry; 114 115/// A dummy default scheduler factory indicates whether the scheduler 116/// is overridden on the command line. 117static ScheduleDAGInstrs *useDefaultMachineSched(MachineSchedContext *C) { 118 return 0; 119} 120 121/// MachineSchedOpt allows command line selection of the scheduler. 122static cl::opt<MachineSchedRegistry::ScheduleDAGCtor, false, 123 RegisterPassParser<MachineSchedRegistry> > 124MachineSchedOpt("misched", 125 cl::init(&useDefaultMachineSched), cl::Hidden, 126 cl::desc("Machine instruction scheduler to use")); 127 128static MachineSchedRegistry 129DefaultSchedRegistry("default", "Use the target's default scheduler choice.", 130 useDefaultMachineSched); 131 132/// Forward declare the standard machine scheduler. This will be used as the 133/// default scheduler if the target does not set a default. 134static ScheduleDAGInstrs *createConvergingSched(MachineSchedContext *C); 135 136 137/// Decrement this iterator until reaching the top or a non-debug instr. 138static MachineBasicBlock::iterator 139priorNonDebug(MachineBasicBlock::iterator I, MachineBasicBlock::iterator Beg) { 140 assert(I != Beg && "reached the top of the region, cannot decrement"); 141 while (--I != Beg) { 142 if (!I->isDebugValue()) 143 break; 144 } 145 return I; 146} 147 148/// If this iterator is a debug value, increment until reaching the End or a 149/// non-debug instruction. 150static MachineBasicBlock::iterator 151nextIfDebug(MachineBasicBlock::iterator I, MachineBasicBlock::iterator End) { 152 for(; I != End; ++I) { 153 if (!I->isDebugValue()) 154 break; 155 } 156 return I; 157} 158 159/// Top-level MachineScheduler pass driver. 160/// 161/// Visit blocks in function order. Divide each block into scheduling regions 162/// and visit them bottom-up. Visiting regions bottom-up is not required, but is 163/// consistent with the DAG builder, which traverses the interior of the 164/// scheduling regions bottom-up. 165/// 166/// This design avoids exposing scheduling boundaries to the DAG builder, 167/// simplifying the DAG builder's support for "special" target instructions. 168/// At the same time the design allows target schedulers to operate across 169/// scheduling boundaries, for example to bundle the boudary instructions 170/// without reordering them. This creates complexity, because the target 171/// scheduler must update the RegionBegin and RegionEnd positions cached by 172/// ScheduleDAGInstrs whenever adding or removing instructions. A much simpler 173/// design would be to split blocks at scheduling boundaries, but LLVM has a 174/// general bias against block splitting purely for implementation simplicity. 175bool MachineScheduler::runOnMachineFunction(MachineFunction &mf) { 176 DEBUG(dbgs() << "Before MISsched:\n"; mf.print(dbgs())); 177 178 // Initialize the context of the pass. 179 MF = &mf; 180 MLI = &getAnalysis<MachineLoopInfo>(); 181 MDT = &getAnalysis<MachineDominatorTree>(); 182 PassConfig = &getAnalysis<TargetPassConfig>(); 183 AA = &getAnalysis<AliasAnalysis>(); 184 185 LIS = &getAnalysis<LiveIntervals>(); 186 const TargetInstrInfo *TII = MF->getTarget().getInstrInfo(); 187 188 RegClassInfo->runOnMachineFunction(*MF); 189 190 // Select the scheduler, or set the default. 191 MachineSchedRegistry::ScheduleDAGCtor Ctor = MachineSchedOpt; 192 if (Ctor == useDefaultMachineSched) { 193 // Get the default scheduler set by the target. 194 Ctor = MachineSchedRegistry::getDefault(); 195 if (!Ctor) { 196 Ctor = createConvergingSched; 197 MachineSchedRegistry::setDefault(Ctor); 198 } 199 } 200 // Instantiate the selected scheduler. 201 OwningPtr<ScheduleDAGInstrs> Scheduler(Ctor(this)); 202 203 // Visit all machine basic blocks. 204 // 205 // TODO: Visit blocks in global postorder or postorder within the bottom-up 206 // loop tree. Then we can optionally compute global RegPressure. 207 for (MachineFunction::iterator MBB = MF->begin(), MBBEnd = MF->end(); 208 MBB != MBBEnd; ++MBB) { 209 210 Scheduler->startBlock(MBB); 211 212 // Break the block into scheduling regions [I, RegionEnd), and schedule each 213 // region as soon as it is discovered. RegionEnd points the the scheduling 214 // boundary at the bottom of the region. The DAG does not include RegionEnd, 215 // but the region does (i.e. the next RegionEnd is above the previous 216 // RegionBegin). If the current block has no terminator then RegionEnd == 217 // MBB->end() for the bottom region. 218 // 219 // The Scheduler may insert instructions during either schedule() or 220 // exitRegion(), even for empty regions. So the local iterators 'I' and 221 // 'RegionEnd' are invalid across these calls. 222 unsigned RemainingCount = MBB->size(); 223 for(MachineBasicBlock::iterator RegionEnd = MBB->end(); 224 RegionEnd != MBB->begin(); RegionEnd = Scheduler->begin()) { 225 226 // Avoid decrementing RegionEnd for blocks with no terminator. 227 if (RegionEnd != MBB->end() 228 || TII->isSchedulingBoundary(llvm::prior(RegionEnd), MBB, *MF)) { 229 --RegionEnd; 230 // Count the boundary instruction. 231 --RemainingCount; 232 } 233 234 // The next region starts above the previous region. Look backward in the 235 // instruction stream until we find the nearest boundary. 236 MachineBasicBlock::iterator I = RegionEnd; 237 for(;I != MBB->begin(); --I, --RemainingCount) { 238 if (TII->isSchedulingBoundary(llvm::prior(I), MBB, *MF)) 239 break; 240 } 241 // Notify the scheduler of the region, even if we may skip scheduling 242 // it. Perhaps it still needs to be bundled. 243 Scheduler->enterRegion(MBB, I, RegionEnd, RemainingCount); 244 245 // Skip empty scheduling regions (0 or 1 schedulable instructions). 246 if (I == RegionEnd || I == llvm::prior(RegionEnd)) { 247 // Close the current region. Bundle the terminator if needed. 248 // This invalidates 'RegionEnd' and 'I'. 249 Scheduler->exitRegion(); 250 continue; 251 } 252 DEBUG(dbgs() << "MachineScheduling " << MF->getFunction()->getName() 253 << ":BB#" << MBB->getNumber() << "\n From: " << *I << " To: "; 254 if (RegionEnd != MBB->end()) dbgs() << *RegionEnd; 255 else dbgs() << "End"; 256 dbgs() << " Remaining: " << RemainingCount << "\n"); 257 258 // Schedule a region: possibly reorder instructions. 259 // This invalidates 'RegionEnd' and 'I'. 260 Scheduler->schedule(); 261 262 // Close the current region. 263 Scheduler->exitRegion(); 264 265 // Scheduling has invalidated the current iterator 'I'. Ask the 266 // scheduler for the top of it's scheduled region. 267 RegionEnd = Scheduler->begin(); 268 } 269 assert(RemainingCount == 0 && "Instruction count mismatch!"); 270 Scheduler->finishBlock(); 271 } 272 Scheduler->finalizeSchedule(); 273 DEBUG(LIS->print(dbgs())); 274 return true; 275} 276 277void MachineScheduler::print(raw_ostream &O, const Module* m) const { 278 // unimplemented 279} 280 281//===----------------------------------------------------------------------===// 282// MachineSchedStrategy - Interface to a machine scheduling algorithm. 283//===----------------------------------------------------------------------===// 284 285namespace { 286class ScheduleDAGMI; 287 288/// MachineSchedStrategy - Interface used by ScheduleDAGMI to drive the selected 289/// scheduling algorithm. 290/// 291/// If this works well and targets wish to reuse ScheduleDAGMI, we may expose it 292/// in ScheduleDAGInstrs.h 293class MachineSchedStrategy { 294public: 295 virtual ~MachineSchedStrategy() {} 296 297 /// Initialize the strategy after building the DAG for a new region. 298 virtual void initialize(ScheduleDAGMI *DAG) = 0; 299 300 /// Pick the next node to schedule, or return NULL. Set IsTopNode to true to 301 /// schedule the node at the top of the unscheduled region. Otherwise it will 302 /// be scheduled at the bottom. 303 virtual SUnit *pickNode(bool &IsTopNode) = 0; 304 305 /// When all predecessor dependencies have been resolved, free this node for 306 /// top-down scheduling. 307 virtual void releaseTopNode(SUnit *SU) = 0; 308 /// When all successor dependencies have been resolved, free this node for 309 /// bottom-up scheduling. 310 virtual void releaseBottomNode(SUnit *SU) = 0; 311}; 312} // namespace 313 314//===----------------------------------------------------------------------===// 315// ScheduleDAGMI - Base class for MachineInstr scheduling with LiveIntervals 316// preservation. 317//===----------------------------------------------------------------------===// 318 319namespace { 320/// ScheduleDAGMI is an implementation of ScheduleDAGInstrs that schedules 321/// machine instructions while updating LiveIntervals. 322class ScheduleDAGMI : public ScheduleDAGInstrs { 323 AliasAnalysis *AA; 324 RegisterClassInfo *RegClassInfo; 325 MachineSchedStrategy *SchedImpl; 326 327 MachineBasicBlock::iterator LiveRegionEnd; 328 329 /// Register pressure in this region computed by buildSchedGraph. 330 IntervalPressure RegPressure; 331 RegPressureTracker RPTracker; 332 333 /// List of pressure sets that exceed the target's pressure limit before 334 /// scheduling, listed in increasing set ID order. Each pressure set is paired 335 /// with its max pressure in the currently scheduled regions. 336 std::vector<PressureElement> RegionCriticalPSets; 337 338 /// The top of the unscheduled zone. 339 MachineBasicBlock::iterator CurrentTop; 340 IntervalPressure TopPressure; 341 RegPressureTracker TopRPTracker; 342 343 /// The bottom of the unscheduled zone. 344 MachineBasicBlock::iterator CurrentBottom; 345 IntervalPressure BotPressure; 346 RegPressureTracker BotRPTracker; 347 348 /// The number of instructions scheduled so far. Used to cut off the 349 /// scheduler at the point determined by misched-cutoff. 350 unsigned NumInstrsScheduled; 351public: 352 ScheduleDAGMI(MachineSchedContext *C, MachineSchedStrategy *S): 353 ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS), 354 AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S), 355 RPTracker(RegPressure), CurrentTop(), TopRPTracker(TopPressure), 356 CurrentBottom(), BotRPTracker(BotPressure), NumInstrsScheduled(0) {} 357 358 ~ScheduleDAGMI() { 359 delete SchedImpl; 360 } 361 362 MachineBasicBlock::iterator top() const { return CurrentTop; } 363 MachineBasicBlock::iterator bottom() const { return CurrentBottom; } 364 365 /// Implement the ScheduleDAGInstrs interface for handling the next scheduling 366 /// region. This covers all instructions in a block, while schedule() may only 367 /// cover a subset. 368 void enterRegion(MachineBasicBlock *bb, 369 MachineBasicBlock::iterator begin, 370 MachineBasicBlock::iterator end, 371 unsigned endcount); 372 373 /// Implement ScheduleDAGInstrs interface for scheduling a sequence of 374 /// reorderable instructions. 375 void schedule(); 376 377 /// Get current register pressure for the top scheduled instructions. 378 const IntervalPressure &getTopPressure() const { return TopPressure; } 379 const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; } 380 381 /// Get current register pressure for the bottom scheduled instructions. 382 const IntervalPressure &getBotPressure() const { return BotPressure; } 383 const RegPressureTracker &getBotRPTracker() const { return BotRPTracker; } 384 385 /// Get register pressure for the entire scheduling region before scheduling. 386 const IntervalPressure &getRegPressure() const { return RegPressure; } 387 388 const std::vector<PressureElement> &getRegionCriticalPSets() const { 389 return RegionCriticalPSets; 390 } 391 392protected: 393 void initRegPressure(); 394 void updateScheduledPressure(std::vector<unsigned> NewMaxPressure); 395 396 void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos); 397 bool checkSchedLimit(); 398 399 void releaseSucc(SUnit *SU, SDep *SuccEdge); 400 void releaseSuccessors(SUnit *SU); 401 void releasePred(SUnit *SU, SDep *PredEdge); 402 void releasePredecessors(SUnit *SU); 403 404 void placeDebugValues(); 405}; 406} // namespace 407 408/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. When 409/// NumPredsLeft reaches zero, release the successor node. 410void ScheduleDAGMI::releaseSucc(SUnit *SU, SDep *SuccEdge) { 411 SUnit *SuccSU = SuccEdge->getSUnit(); 412 413#ifndef NDEBUG 414 if (SuccSU->NumPredsLeft == 0) { 415 dbgs() << "*** Scheduling failed! ***\n"; 416 SuccSU->dump(this); 417 dbgs() << " has been released too many times!\n"; 418 llvm_unreachable(0); 419 } 420#endif 421 --SuccSU->NumPredsLeft; 422 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) 423 SchedImpl->releaseTopNode(SuccSU); 424} 425 426/// releaseSuccessors - Call releaseSucc on each of SU's successors. 427void ScheduleDAGMI::releaseSuccessors(SUnit *SU) { 428 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 429 I != E; ++I) { 430 releaseSucc(SU, &*I); 431 } 432} 433 434/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. When 435/// NumSuccsLeft reaches zero, release the predecessor node. 436void ScheduleDAGMI::releasePred(SUnit *SU, SDep *PredEdge) { 437 SUnit *PredSU = PredEdge->getSUnit(); 438 439#ifndef NDEBUG 440 if (PredSU->NumSuccsLeft == 0) { 441 dbgs() << "*** Scheduling failed! ***\n"; 442 PredSU->dump(this); 443 dbgs() << " has been released too many times!\n"; 444 llvm_unreachable(0); 445 } 446#endif 447 --PredSU->NumSuccsLeft; 448 if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) 449 SchedImpl->releaseBottomNode(PredSU); 450} 451 452/// releasePredecessors - Call releasePred on each of SU's predecessors. 453void ScheduleDAGMI::releasePredecessors(SUnit *SU) { 454 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 455 I != E; ++I) { 456 releasePred(SU, &*I); 457 } 458} 459 460void ScheduleDAGMI::moveInstruction(MachineInstr *MI, 461 MachineBasicBlock::iterator InsertPos) { 462 // Advance RegionBegin if the first instruction moves down. 463 if (&*RegionBegin == MI) 464 ++RegionBegin; 465 466 // Update the instruction stream. 467 BB->splice(InsertPos, BB, MI); 468 469 // Update LiveIntervals 470 LIS->handleMove(MI); 471 472 // Recede RegionBegin if an instruction moves above the first. 473 if (RegionBegin == InsertPos) 474 RegionBegin = MI; 475} 476 477bool ScheduleDAGMI::checkSchedLimit() { 478#ifndef NDEBUG 479 if (NumInstrsScheduled == MISchedCutoff && MISchedCutoff != ~0U) { 480 CurrentTop = CurrentBottom; 481 return false; 482 } 483 ++NumInstrsScheduled; 484#endif 485 return true; 486} 487 488/// enterRegion - Called back from MachineScheduler::runOnMachineFunction after 489/// crossing a scheduling boundary. [begin, end) includes all instructions in 490/// the region, including the boundary itself and single-instruction regions 491/// that don't get scheduled. 492void ScheduleDAGMI::enterRegion(MachineBasicBlock *bb, 493 MachineBasicBlock::iterator begin, 494 MachineBasicBlock::iterator end, 495 unsigned endcount) 496{ 497 ScheduleDAGInstrs::enterRegion(bb, begin, end, endcount); 498 499 // For convenience remember the end of the liveness region. 500 LiveRegionEnd = 501 (RegionEnd == bb->end()) ? RegionEnd : llvm::next(RegionEnd); 502} 503 504// Setup the register pressure trackers for the top scheduled top and bottom 505// scheduled regions. 506void ScheduleDAGMI::initRegPressure() { 507 TopRPTracker.init(&MF, RegClassInfo, LIS, BB, RegionBegin); 508 BotRPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd); 509 510 // Close the RPTracker to finalize live ins. 511 RPTracker.closeRegion(); 512 513 // Initialize the live ins and live outs. 514 TopRPTracker.addLiveRegs(RPTracker.getPressure().LiveInRegs); 515 BotRPTracker.addLiveRegs(RPTracker.getPressure().LiveOutRegs); 516 517 // Close one end of the tracker so we can call 518 // getMaxUpward/DownwardPressureDelta before advancing across any 519 // instructions. This converts currently live regs into live ins/outs. 520 TopRPTracker.closeTop(); 521 BotRPTracker.closeBottom(); 522 523 // Account for liveness generated by the region boundary. 524 if (LiveRegionEnd != RegionEnd) 525 BotRPTracker.recede(); 526 527 assert(BotRPTracker.getPos() == RegionEnd && "Can't find the region bottom"); 528 529 // Cache the list of excess pressure sets in this region. This will also track 530 // the max pressure in the scheduled code for these sets. 531 RegionCriticalPSets.clear(); 532 std::vector<unsigned> RegionPressure = RPTracker.getPressure().MaxSetPressure; 533 for (unsigned i = 0, e = RegionPressure.size(); i < e; ++i) { 534 unsigned Limit = TRI->getRegPressureSetLimit(i); 535 if (RegionPressure[i] > Limit) 536 RegionCriticalPSets.push_back(PressureElement(i, 0)); 537 } 538 DEBUG(dbgs() << "Excess PSets: "; 539 for (unsigned i = 0, e = RegionCriticalPSets.size(); i != e; ++i) 540 dbgs() << TRI->getRegPressureSetName( 541 RegionCriticalPSets[i].PSetID) << " "; 542 dbgs() << "\n"); 543} 544 545// FIXME: When the pressure tracker deals in pressure differences then we won't 546// iterate over all RegionCriticalPSets[i]. 547void ScheduleDAGMI:: 548updateScheduledPressure(std::vector<unsigned> NewMaxPressure) { 549 for (unsigned i = 0, e = RegionCriticalPSets.size(); i < e; ++i) { 550 unsigned ID = RegionCriticalPSets[i].PSetID; 551 int &MaxUnits = RegionCriticalPSets[i].UnitIncrease; 552 if ((int)NewMaxPressure[ID] > MaxUnits) 553 MaxUnits = NewMaxPressure[ID]; 554 } 555} 556 557/// schedule - Called back from MachineScheduler::runOnMachineFunction 558/// after setting up the current scheduling region. [RegionBegin, RegionEnd) 559/// only includes instructions that have DAG nodes, not scheduling boundaries. 560void ScheduleDAGMI::schedule() { 561 // Initialize the register pressure tracker used by buildSchedGraph. 562 RPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd); 563 564 // Account for liveness generate by the region boundary. 565 if (LiveRegionEnd != RegionEnd) 566 RPTracker.recede(); 567 568 // Build the DAG, and compute current register pressure. 569 buildSchedGraph(AA, &RPTracker); 570 571 // Initialize top/bottom trackers after computing region pressure. 572 initRegPressure(); 573 574 DEBUG(dbgs() << "********** MI Scheduling **********\n"); 575 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 576 SUnits[su].dumpAll(this)); 577 578 if (ViewMISchedDAGs) viewGraph(); 579 580 SchedImpl->initialize(this); 581 582 // Release edges from the special Entry node or to the special Exit node. 583 releaseSuccessors(&EntrySU); 584 releasePredecessors(&ExitSU); 585 586 // Release all DAG roots for scheduling. 587 for (std::vector<SUnit>::iterator I = SUnits.begin(), E = SUnits.end(); 588 I != E; ++I) { 589 // A SUnit is ready to top schedule if it has no predecessors. 590 if (I->Preds.empty()) 591 SchedImpl->releaseTopNode(&(*I)); 592 // A SUnit is ready to bottom schedule if it has no successors. 593 if (I->Succs.empty()) 594 SchedImpl->releaseBottomNode(&(*I)); 595 } 596 597 CurrentTop = nextIfDebug(RegionBegin, RegionEnd); 598 CurrentBottom = RegionEnd; 599 bool IsTopNode = false; 600 while (SUnit *SU = SchedImpl->pickNode(IsTopNode)) { 601 DEBUG(dbgs() << "*** " << (IsTopNode ? "Top" : "Bottom") 602 << " Scheduling Instruction:\n"; SU->dump(this)); 603 if (!checkSchedLimit()) 604 break; 605 606 // Move the instruction to its new location in the instruction stream. 607 MachineInstr *MI = SU->getInstr(); 608 609 if (IsTopNode) { 610 assert(SU->isTopReady() && "node still has unscheduled dependencies"); 611 if (&*CurrentTop == MI) 612 CurrentTop = nextIfDebug(++CurrentTop, CurrentBottom); 613 else { 614 moveInstruction(MI, CurrentTop); 615 TopRPTracker.setPos(MI); 616 } 617 618 // Update top scheduled pressure. 619 TopRPTracker.advance(); 620 assert(TopRPTracker.getPos() == CurrentTop && "out of sync"); 621 updateScheduledPressure(TopRPTracker.getPressure().MaxSetPressure); 622 623 // Release dependent instructions for scheduling. 624 releaseSuccessors(SU); 625 } 626 else { 627 assert(SU->isBottomReady() && "node still has unscheduled dependencies"); 628 MachineBasicBlock::iterator priorII = 629 priorNonDebug(CurrentBottom, CurrentTop); 630 if (&*priorII == MI) 631 CurrentBottom = priorII; 632 else { 633 if (&*CurrentTop == MI) { 634 CurrentTop = nextIfDebug(++CurrentTop, priorII); 635 TopRPTracker.setPos(CurrentTop); 636 } 637 moveInstruction(MI, CurrentBottom); 638 CurrentBottom = MI; 639 } 640 // Update bottom scheduled pressure. 641 BotRPTracker.recede(); 642 assert(BotRPTracker.getPos() == CurrentBottom && "out of sync"); 643 updateScheduledPressure(BotRPTracker.getPressure().MaxSetPressure); 644 645 // Release dependent instructions for scheduling. 646 releasePredecessors(SU); 647 } 648 SU->isScheduled = true; 649 } 650 assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone."); 651 652 placeDebugValues(); 653} 654 655/// Reinsert any remaining debug_values, just like the PostRA scheduler. 656void ScheduleDAGMI::placeDebugValues() { 657 // If first instruction was a DBG_VALUE then put it back. 658 if (FirstDbgValue) { 659 BB->splice(RegionBegin, BB, FirstDbgValue); 660 RegionBegin = FirstDbgValue; 661 } 662 663 for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator 664 DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) { 665 std::pair<MachineInstr *, MachineInstr *> P = *prior(DI); 666 MachineInstr *DbgValue = P.first; 667 MachineBasicBlock::iterator OrigPrevMI = P.second; 668 BB->splice(++OrigPrevMI, BB, DbgValue); 669 if (OrigPrevMI == llvm::prior(RegionEnd)) 670 RegionEnd = DbgValue; 671 } 672 DbgValues.clear(); 673 FirstDbgValue = NULL; 674} 675 676//===----------------------------------------------------------------------===// 677// ConvergingScheduler - Implementation of the standard MachineSchedStrategy. 678//===----------------------------------------------------------------------===// 679 680namespace { 681/// Wrapper around a vector of SUnits with some basic convenience methods. 682struct ReadyQ { 683 typedef std::vector<SUnit*>::iterator iterator; 684 685 unsigned ID; 686 std::vector<SUnit*> Queue; 687 688 ReadyQ(unsigned id): ID(id) {} 689 690 bool isInQueue(SUnit *SU) const { 691 return SU->NodeQueueId & ID; 692 } 693 694 bool empty() const { return Queue.empty(); } 695 696 unsigned size() const { return Queue.size(); } 697 698 iterator begin() { return Queue.begin(); } 699 700 iterator end() { return Queue.end(); } 701 702 iterator find(SUnit *SU) { 703 return std::find(Queue.begin(), Queue.end(), SU); 704 } 705 706 void push(SUnit *SU) { 707 Queue.push_back(SU); 708 SU->NodeQueueId |= ID; 709 } 710 711 void remove(iterator I) { 712 (*I)->NodeQueueId &= ~ID; 713 *I = Queue.back(); 714 Queue.pop_back(); 715 } 716 717 void dump(const char* Name) { 718 dbgs() << Name << ": "; 719 for (unsigned i = 0, e = Queue.size(); i < e; ++i) 720 dbgs() << Queue[i]->NodeNum << " "; 721 dbgs() << "\n"; 722 } 723}; 724 725/// ConvergingScheduler shrinks the unscheduled zone using heuristics to balance 726/// the schedule. 727class ConvergingScheduler : public MachineSchedStrategy { 728 729 /// Store the state used by ConvergingScheduler heuristics, required for the 730 /// lifetime of one invocation of pickNode(). 731 struct SchedCandidate { 732 // The best SUnit candidate. 733 SUnit *SU; 734 735 // Register pressure values for the best candidate. 736 RegPressureDelta RPDelta; 737 738 SchedCandidate(): SU(NULL) {} 739 }; 740 /// Represent the type of SchedCandidate found within a single queue. 741 enum CandResult { 742 NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure }; 743 744 ScheduleDAGMI *DAG; 745 const TargetRegisterInfo *TRI; 746 747 ReadyQ TopQueue; 748 ReadyQ BotQueue; 749 750public: 751 /// SUnit::NodeQueueId = 0 (none), = 1 (top), = 2 (bottom), = 3 (both) 752 enum { 753 TopQID = 1, 754 BotQID = 2 755 }; 756 757 ConvergingScheduler(): DAG(0), TRI(0), TopQueue(TopQID), BotQueue(BotQID) {} 758 759 static const char *getQName(unsigned ID) { 760 switch(ID) { 761 default: return "NoQ"; 762 case TopQID: return "TopQ"; 763 case BotQID: return "BotQ"; 764 }; 765 } 766 767 virtual void initialize(ScheduleDAGMI *dag) { 768 DAG = dag; 769 TRI = DAG->TRI; 770 771 assert((!ForceTopDown || !ForceBottomUp) && 772 "-misched-topdown incompatible with -misched-bottomup"); 773 } 774 775 virtual SUnit *pickNode(bool &IsTopNode); 776 777 virtual void releaseTopNode(SUnit *SU) { 778 if (!SU->isScheduled) 779 TopQueue.push(SU); 780 } 781 virtual void releaseBottomNode(SUnit *SU) { 782 if (!SU->isScheduled) 783 BotQueue.push(SU); 784 } 785protected: 786 SUnit *pickNodeBidrectional(bool &IsTopNode); 787 788 CandResult pickNodeFromQueue(ReadyQ &Q, const RegPressureTracker &RPTracker, 789 SchedCandidate &Candidate); 790#ifndef NDEBUG 791 void traceCandidate(const char *Label, unsigned QID, SUnit *SU, 792 PressureElement P = PressureElement()); 793#endif 794}; 795} // namespace 796 797#ifndef NDEBUG 798void ConvergingScheduler:: 799traceCandidate(const char *Label, unsigned QID, SUnit *SU, 800 PressureElement P) { 801 dbgs() << Label << getQName(QID) << " "; 802 if (P.isValid()) 803 dbgs() << TRI->getRegPressureSetName(P.PSetID) << ":" << P.UnitIncrease 804 << " "; 805 else 806 dbgs() << " "; 807 SU->dump(DAG); 808} 809#endif 810 811/// Return true if the LHS reg pressure effect is better than RHS. 812static bool compareRPDelta(const RegPressureDelta &LHS, 813 const RegPressureDelta &RHS) { 814 // Compare each component of pressure in decreasing order of importance 815 // without checking if any are valid. Invalid PressureElements are assumed to 816 // have UnitIncrease==0, so are neutral. 817 if (LHS.Excess.UnitIncrease != RHS.Excess.UnitIncrease) 818 return LHS.Excess.UnitIncrease < RHS.Excess.UnitIncrease; 819 820 if (LHS.CriticalMax.UnitIncrease != RHS.CriticalMax.UnitIncrease) 821 return LHS.CriticalMax.UnitIncrease < RHS.CriticalMax.UnitIncrease; 822 823 if (LHS.CurrentMax.UnitIncrease != RHS.CurrentMax.UnitIncrease) 824 return LHS.CurrentMax.UnitIncrease < RHS.CurrentMax.UnitIncrease; 825 826 return false; 827} 828 829 830/// Pick the best candidate from the top queue. 831/// 832/// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during 833/// DAG building. To adjust for the current scheduling location we need to 834/// maintain the number of vreg uses remaining to be top-scheduled. 835ConvergingScheduler::CandResult ConvergingScheduler:: 836pickNodeFromQueue(ReadyQ &Q, const RegPressureTracker &RPTracker, 837 SchedCandidate &Candidate) { 838 DEBUG(Q.dump(getQName(Q.ID))); 839 840 // getMaxPressureDelta temporarily modifies the tracker. 841 RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker); 842 843 // BestSU remains NULL if no top candidates beat the best existing candidate. 844 CandResult FoundCandidate = NoCand; 845 for (ReadyQ::iterator I = Q.begin(), E = Q.end(); I != E; ++I) { 846 847 RegPressureDelta RPDelta; 848 TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta, 849 DAG->getRegionCriticalPSets(), 850 DAG->getRegPressure().MaxSetPressure); 851 852 // Initialize the candidate if needed. 853 if (!Candidate.SU) { 854 Candidate.SU = *I; 855 Candidate.RPDelta = RPDelta; 856 FoundCandidate = NodeOrder; 857 continue; 858 } 859 // Avoid exceeding the target's limit. 860 if (RPDelta.Excess.UnitIncrease < Candidate.RPDelta.Excess.UnitIncrease) { 861 DEBUG(traceCandidate("ECAND", Q.ID, *I, RPDelta.Excess)); 862 Candidate.SU = *I; 863 Candidate.RPDelta = RPDelta; 864 FoundCandidate = SingleExcess; 865 continue; 866 } 867 if (RPDelta.Excess.UnitIncrease > Candidate.RPDelta.Excess.UnitIncrease) 868 continue; 869 if (FoundCandidate == SingleExcess) 870 FoundCandidate = MultiPressure; 871 872 // Avoid increasing the max critical pressure in the scheduled region. 873 if (RPDelta.CriticalMax.UnitIncrease 874 < Candidate.RPDelta.CriticalMax.UnitIncrease) { 875 DEBUG(traceCandidate("PCAND", Q.ID, *I, RPDelta.CriticalMax)); 876 Candidate.SU = *I; 877 Candidate.RPDelta = RPDelta; 878 FoundCandidate = SingleCritical; 879 continue; 880 } 881 if (RPDelta.CriticalMax.UnitIncrease 882 > Candidate.RPDelta.CriticalMax.UnitIncrease) 883 continue; 884 if (FoundCandidate == SingleCritical) 885 FoundCandidate = MultiPressure; 886 887 // Avoid increasing the max pressure of the entire region. 888 if (RPDelta.CurrentMax.UnitIncrease 889 < Candidate.RPDelta.CurrentMax.UnitIncrease) { 890 DEBUG(traceCandidate("MCAND", Q.ID, *I, RPDelta.CurrentMax)); 891 Candidate.SU = *I; 892 Candidate.RPDelta = RPDelta; 893 FoundCandidate = SingleMax; 894 continue; 895 } 896 if (RPDelta.CurrentMax.UnitIncrease 897 > Candidate.RPDelta.CurrentMax.UnitIncrease) 898 continue; 899 if (FoundCandidate == SingleMax) 900 FoundCandidate = MultiPressure; 901 902 // Fall through to original instruction order. 903 // Only consider node order if Candidate was chosen from this Q. 904 if (FoundCandidate == NoCand) 905 continue; 906 907 if ((Q.ID == TopQID && (*I)->NodeNum < Candidate.SU->NodeNum) 908 || (Q.ID == BotQID && (*I)->NodeNum > Candidate.SU->NodeNum)) { 909 DEBUG(traceCandidate("NCAND", Q.ID, *I)); 910 Candidate.SU = *I; 911 Candidate.RPDelta = RPDelta; 912 FoundCandidate = NodeOrder; 913 } 914 } 915 return FoundCandidate; 916} 917 918/// Pick the best candidate node from either the top or bottom queue. 919SUnit *ConvergingScheduler::pickNodeBidrectional(bool &IsTopNode) { 920 // Schedule as far as possible in the direction of no choice. This is most 921 // efficient, but also provides the best heuristics for CriticalPSets. 922 if (BotQueue.size() == 1) { 923 IsTopNode = false; 924 return *BotQueue.begin(); 925 } 926 if (TopQueue.size() == 1) { 927 IsTopNode = true; 928 return *TopQueue.begin(); 929 } 930 SchedCandidate BotCandidate; 931 // Prefer bottom scheduling when heuristics are silent. 932 CandResult BotResult = 933 pickNodeFromQueue(BotQueue, DAG->getBotRPTracker(), BotCandidate); 934 assert(BotResult != NoCand && "failed to find the first candidate"); 935 936 // If either Q has a single candidate that provides the least increase in 937 // Excess pressure, we can immediately schedule from that Q. 938 // 939 // RegionCriticalPSets summarizes the pressure within the scheduled region and 940 // affects picking from either Q. If scheduling in one direction must 941 // increase pressure for one of the excess PSets, then schedule in that 942 // direction first to provide more freedom in the other direction. 943 if (BotResult == SingleExcess || BotResult == SingleCritical) { 944 IsTopNode = false; 945 return BotCandidate.SU; 946 } 947 // Check if the top Q has a better candidate. 948 SchedCandidate TopCandidate; 949 CandResult TopResult = 950 pickNodeFromQueue(TopQueue, DAG->getTopRPTracker(), TopCandidate); 951 assert(TopResult != NoCand && "failed to find the first candidate"); 952 953 if (TopResult == SingleExcess || TopResult == SingleCritical) { 954 IsTopNode = true; 955 return TopCandidate.SU; 956 } 957 // If either Q has a single candidate that minimizes pressure above the 958 // original region's pressure pick it. 959 if (BotResult == SingleMax) { 960 IsTopNode = false; 961 return BotCandidate.SU; 962 } 963 if (TopResult == SingleMax) { 964 IsTopNode = true; 965 return TopCandidate.SU; 966 } 967 // Check for a salient pressure difference and pick the best from either side. 968 if (compareRPDelta(TopCandidate.RPDelta, BotCandidate.RPDelta)) { 969 IsTopNode = true; 970 return TopCandidate.SU; 971 } 972 // Otherwise prefer the bottom candidate in node order. 973 IsTopNode = false; 974 return BotCandidate.SU; 975} 976 977/// Pick the best node to balance the schedule. Implements MachineSchedStrategy. 978SUnit *ConvergingScheduler::pickNode(bool &IsTopNode) { 979 if (DAG->top() == DAG->bottom()) { 980 assert(TopQueue.empty() && BotQueue.empty() && "ReadyQ garbage"); 981 return NULL; 982 } 983 SUnit *SU; 984 if (ForceTopDown) { 985 SU = DAG->getSUnit(DAG->top()); 986 IsTopNode = true; 987 } 988 else if (ForceBottomUp) { 989 SU = DAG->getSUnit(priorNonDebug(DAG->bottom(), DAG->top())); 990 IsTopNode = false; 991 } 992 else { 993 SU = pickNodeBidrectional(IsTopNode); 994 } 995 if (SU->isTopReady()) { 996 assert(!TopQueue.empty() && "bad ready count"); 997 TopQueue.remove(TopQueue.find(SU)); 998 } 999 if (SU->isBottomReady()) { 1000 assert(!BotQueue.empty() && "bad ready count"); 1001 BotQueue.remove(BotQueue.find(SU)); 1002 } 1003 return SU; 1004} 1005 1006/// Create the standard converging machine scheduler. This will be used as the 1007/// default scheduler if the target does not set a default. 1008static ScheduleDAGInstrs *createConvergingSched(MachineSchedContext *C) { 1009 assert((!ForceTopDown || !ForceBottomUp) && 1010 "-misched-topdown incompatible with -misched-bottomup"); 1011 return new ScheduleDAGMI(C, new ConvergingScheduler()); 1012} 1013static MachineSchedRegistry 1014ConvergingSchedRegistry("converge", "Standard converging scheduler.", 1015 createConvergingSched); 1016 1017//===----------------------------------------------------------------------===// 1018// Machine Instruction Shuffler for Correctness Testing 1019//===----------------------------------------------------------------------===// 1020 1021#ifndef NDEBUG 1022namespace { 1023/// Apply a less-than relation on the node order, which corresponds to the 1024/// instruction order prior to scheduling. IsReverse implements greater-than. 1025template<bool IsReverse> 1026struct SUnitOrder { 1027 bool operator()(SUnit *A, SUnit *B) const { 1028 if (IsReverse) 1029 return A->NodeNum > B->NodeNum; 1030 else 1031 return A->NodeNum < B->NodeNum; 1032 } 1033}; 1034 1035/// Reorder instructions as much as possible. 1036class InstructionShuffler : public MachineSchedStrategy { 1037 bool IsAlternating; 1038 bool IsTopDown; 1039 1040 // Using a less-than relation (SUnitOrder<false>) for the TopQ priority 1041 // gives nodes with a higher number higher priority causing the latest 1042 // instructions to be scheduled first. 1043 PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<false> > 1044 TopQ; 1045 // When scheduling bottom-up, use greater-than as the queue priority. 1046 PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<true> > 1047 BottomQ; 1048public: 1049 InstructionShuffler(bool alternate, bool topdown) 1050 : IsAlternating(alternate), IsTopDown(topdown) {} 1051 1052 virtual void initialize(ScheduleDAGMI *) { 1053 TopQ.clear(); 1054 BottomQ.clear(); 1055 } 1056 1057 /// Implement MachineSchedStrategy interface. 1058 /// ----------------------------------------- 1059 1060 virtual SUnit *pickNode(bool &IsTopNode) { 1061 SUnit *SU; 1062 if (IsTopDown) { 1063 do { 1064 if (TopQ.empty()) return NULL; 1065 SU = TopQ.top(); 1066 TopQ.pop(); 1067 } while (SU->isScheduled); 1068 IsTopNode = true; 1069 } 1070 else { 1071 do { 1072 if (BottomQ.empty()) return NULL; 1073 SU = BottomQ.top(); 1074 BottomQ.pop(); 1075 } while (SU->isScheduled); 1076 IsTopNode = false; 1077 } 1078 if (IsAlternating) 1079 IsTopDown = !IsTopDown; 1080 return SU; 1081 } 1082 1083 virtual void releaseTopNode(SUnit *SU) { 1084 TopQ.push(SU); 1085 } 1086 virtual void releaseBottomNode(SUnit *SU) { 1087 BottomQ.push(SU); 1088 } 1089}; 1090} // namespace 1091 1092static ScheduleDAGInstrs *createInstructionShuffler(MachineSchedContext *C) { 1093 bool Alternate = !ForceTopDown && !ForceBottomUp; 1094 bool TopDown = !ForceBottomUp; 1095 assert((TopDown || !ForceTopDown) && 1096 "-misched-topdown incompatible with -misched-bottomup"); 1097 return new ScheduleDAGMI(C, new InstructionShuffler(Alternate, TopDown)); 1098} 1099static MachineSchedRegistry ShufflerRegistry( 1100 "shuffle", "Shuffle machine instructions alternating directions", 1101 createInstructionShuffler); 1102#endif // !NDEBUG 1103