PostRASchedulerList.cpp revision cf6b6131dd0da37903a6e3a5173ea12aa8263713
1//===----- SchedulePostRAList.cpp - list 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// This implements a top-down list scheduler, using standard algorithms. 11// The basic approach uses a priority queue of available nodes to schedule. 12// One at a time, nodes are taken from the priority queue (thus in priority 13// order), checked for legality to schedule, and emitted if legal. 14// 15// Nodes may not be legal to schedule either due to structural hazards (e.g. 16// pipeline or resource constraints) or because an input to the instruction has 17// not completed execution. 18// 19//===----------------------------------------------------------------------===// 20 21#define DEBUG_TYPE "post-RA-sched" 22#include "AntiDepBreaker.h" 23#include "AggressiveAntiDepBreaker.h" 24#include "CriticalAntiDepBreaker.h" 25#include "llvm/CodeGen/Passes.h" 26#include "llvm/CodeGen/LatencyPriorityQueue.h" 27#include "llvm/CodeGen/SchedulerRegistry.h" 28#include "llvm/CodeGen/MachineDominators.h" 29#include "llvm/CodeGen/MachineFrameInfo.h" 30#include "llvm/CodeGen/MachineFunctionPass.h" 31#include "llvm/CodeGen/MachineLoopInfo.h" 32#include "llvm/CodeGen/MachineRegisterInfo.h" 33#include "llvm/CodeGen/RegisterClassInfo.h" 34#include "llvm/CodeGen/ScheduleDAGInstrs.h" 35#include "llvm/CodeGen/ScheduleHazardRecognizer.h" 36#include "llvm/Analysis/AliasAnalysis.h" 37#include "llvm/Target/TargetLowering.h" 38#include "llvm/Target/TargetMachine.h" 39#include "llvm/Target/TargetInstrInfo.h" 40#include "llvm/Target/TargetRegisterInfo.h" 41#include "llvm/Target/TargetSubtargetInfo.h" 42#include "llvm/Support/CommandLine.h" 43#include "llvm/Support/Debug.h" 44#include "llvm/Support/ErrorHandling.h" 45#include "llvm/Support/raw_ostream.h" 46#include "llvm/ADT/BitVector.h" 47#include "llvm/ADT/Statistic.h" 48using namespace llvm; 49 50STATISTIC(NumNoops, "Number of noops inserted"); 51STATISTIC(NumStalls, "Number of pipeline stalls"); 52STATISTIC(NumFixedAnti, "Number of fixed anti-dependencies"); 53 54// Post-RA scheduling is enabled with 55// TargetSubtargetInfo.enablePostRAScheduler(). This flag can be used to 56// override the target. 57static cl::opt<bool> 58EnablePostRAScheduler("post-RA-scheduler", 59 cl::desc("Enable scheduling after register allocation"), 60 cl::init(false), cl::Hidden); 61static cl::opt<std::string> 62EnableAntiDepBreaking("break-anti-dependencies", 63 cl::desc("Break post-RA scheduling anti-dependencies: " 64 "\"critical\", \"all\", or \"none\""), 65 cl::init("none"), cl::Hidden); 66 67// If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod 68static cl::opt<int> 69DebugDiv("postra-sched-debugdiv", 70 cl::desc("Debug control MBBs that are scheduled"), 71 cl::init(0), cl::Hidden); 72static cl::opt<int> 73DebugMod("postra-sched-debugmod", 74 cl::desc("Debug control MBBs that are scheduled"), 75 cl::init(0), cl::Hidden); 76 77AntiDepBreaker::~AntiDepBreaker() { } 78 79namespace { 80 class PostRAScheduler : public MachineFunctionPass { 81 const TargetInstrInfo *TII; 82 RegisterClassInfo RegClassInfo; 83 84 public: 85 static char ID; 86 PostRAScheduler() : MachineFunctionPass(ID) {} 87 88 void getAnalysisUsage(AnalysisUsage &AU) const { 89 AU.setPreservesCFG(); 90 AU.addRequired<AliasAnalysis>(); 91 AU.addRequired<TargetPassConfig>(); 92 AU.addRequired<MachineDominatorTree>(); 93 AU.addPreserved<MachineDominatorTree>(); 94 AU.addRequired<MachineLoopInfo>(); 95 AU.addPreserved<MachineLoopInfo>(); 96 MachineFunctionPass::getAnalysisUsage(AU); 97 } 98 99 bool runOnMachineFunction(MachineFunction &Fn); 100 }; 101 char PostRAScheduler::ID = 0; 102 103 class SchedulePostRATDList : public ScheduleDAGInstrs { 104 /// AvailableQueue - The priority queue to use for the available SUnits. 105 /// 106 LatencyPriorityQueue AvailableQueue; 107 108 /// PendingQueue - This contains all of the instructions whose operands have 109 /// been issued, but their results are not ready yet (due to the latency of 110 /// the operation). Once the operands becomes available, the instruction is 111 /// added to the AvailableQueue. 112 std::vector<SUnit*> PendingQueue; 113 114 /// HazardRec - The hazard recognizer to use. 115 ScheduleHazardRecognizer *HazardRec; 116 117 /// AntiDepBreak - Anti-dependence breaking object, or NULL if none 118 AntiDepBreaker *AntiDepBreak; 119 120 /// AA - AliasAnalysis for making memory reference queries. 121 AliasAnalysis *AA; 122 123 /// LiveRegs - true if the register is live. 124 BitVector LiveRegs; 125 126 /// The schedule. Null SUnit*'s represent noop instructions. 127 std::vector<SUnit*> Sequence; 128 129 public: 130 SchedulePostRATDList( 131 MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT, 132 AliasAnalysis *AA, const RegisterClassInfo&, 133 TargetSubtargetInfo::AntiDepBreakMode AntiDepMode, 134 SmallVectorImpl<const TargetRegisterClass*> &CriticalPathRCs); 135 136 ~SchedulePostRATDList(); 137 138 /// startBlock - Initialize register live-range state for scheduling in 139 /// this block. 140 /// 141 void startBlock(MachineBasicBlock *BB); 142 143 /// Initialize the scheduler state for the next scheduling region. 144 virtual void enterRegion(MachineBasicBlock *bb, 145 MachineBasicBlock::iterator begin, 146 MachineBasicBlock::iterator end, 147 unsigned endcount); 148 149 /// Notify that the scheduler has finished scheduling the current region. 150 virtual void exitRegion(); 151 152 /// Schedule - Schedule the instruction range using list scheduling. 153 /// 154 void schedule(); 155 156 void EmitSchedule(); 157 158 /// Observe - Update liveness information to account for the current 159 /// instruction, which will not be scheduled. 160 /// 161 void Observe(MachineInstr *MI, unsigned Count); 162 163 /// finishBlock - Clean up register live-range state. 164 /// 165 void finishBlock(); 166 167 /// FixupKills - Fix register kill flags that have been made 168 /// invalid due to scheduling 169 /// 170 void FixupKills(MachineBasicBlock *MBB); 171 172 private: 173 void ReleaseSucc(SUnit *SU, SDep *SuccEdge); 174 void ReleaseSuccessors(SUnit *SU); 175 void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle); 176 void ListScheduleTopDown(); 177 void StartBlockForKills(MachineBasicBlock *BB); 178 179 // ToggleKillFlag - Toggle a register operand kill flag. Other 180 // adjustments may be made to the instruction if necessary. Return 181 // true if the operand has been deleted, false if not. 182 bool ToggleKillFlag(MachineInstr *MI, MachineOperand &MO); 183 184 void dumpSchedule() const; 185 }; 186} 187 188char &llvm::PostRASchedulerID = PostRAScheduler::ID; 189 190INITIALIZE_PASS(PostRAScheduler, "post-RA-sched", 191 "Post RA top-down list latency scheduler", false, false) 192 193SchedulePostRATDList::SchedulePostRATDList( 194 MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT, 195 AliasAnalysis *AA, const RegisterClassInfo &RCI, 196 TargetSubtargetInfo::AntiDepBreakMode AntiDepMode, 197 SmallVectorImpl<const TargetRegisterClass*> &CriticalPathRCs) 198 : ScheduleDAGInstrs(MF, MLI, MDT, /*IsPostRA=*/true), AA(AA), 199 LiveRegs(TRI->getNumRegs()) 200{ 201 const TargetMachine &TM = MF.getTarget(); 202 const InstrItineraryData *InstrItins = TM.getInstrItineraryData(); 203 HazardRec = 204 TM.getInstrInfo()->CreateTargetPostRAHazardRecognizer(InstrItins, this); 205 206 assert((AntiDepMode == TargetSubtargetInfo::ANTIDEP_NONE || 207 MRI.tracksLiveness()) && 208 "Live-ins must be accurate for anti-dependency breaking"); 209 AntiDepBreak = 210 ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_ALL) ? 211 (AntiDepBreaker *)new AggressiveAntiDepBreaker(MF, RCI, CriticalPathRCs) : 212 ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_CRITICAL) ? 213 (AntiDepBreaker *)new CriticalAntiDepBreaker(MF, RCI) : NULL)); 214} 215 216SchedulePostRATDList::~SchedulePostRATDList() { 217 delete HazardRec; 218 delete AntiDepBreak; 219} 220 221/// Initialize state associated with the next scheduling region. 222void SchedulePostRATDList::enterRegion(MachineBasicBlock *bb, 223 MachineBasicBlock::iterator begin, 224 MachineBasicBlock::iterator end, 225 unsigned endcount) { 226 ScheduleDAGInstrs::enterRegion(bb, begin, end, endcount); 227 Sequence.clear(); 228} 229 230/// Print the schedule before exiting the region. 231void SchedulePostRATDList::exitRegion() { 232 DEBUG({ 233 dbgs() << "*** Final schedule ***\n"; 234 dumpSchedule(); 235 dbgs() << '\n'; 236 }); 237 ScheduleDAGInstrs::exitRegion(); 238} 239 240#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 241/// dumpSchedule - dump the scheduled Sequence. 242void SchedulePostRATDList::dumpSchedule() const { 243 for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 244 if (SUnit *SU = Sequence[i]) 245 SU->dump(this); 246 else 247 dbgs() << "**** NOOP ****\n"; 248 } 249} 250#endif 251 252bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { 253 TII = Fn.getTarget().getInstrInfo(); 254 MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>(); 255 MachineDominatorTree &MDT = getAnalysis<MachineDominatorTree>(); 256 AliasAnalysis *AA = &getAnalysis<AliasAnalysis>(); 257 TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>(); 258 259 RegClassInfo.runOnMachineFunction(Fn); 260 261 // Check for explicit enable/disable of post-ra scheduling. 262 TargetSubtargetInfo::AntiDepBreakMode AntiDepMode = 263 TargetSubtargetInfo::ANTIDEP_NONE; 264 SmallVector<const TargetRegisterClass*, 4> CriticalPathRCs; 265 if (EnablePostRAScheduler.getPosition() > 0) { 266 if (!EnablePostRAScheduler) 267 return false; 268 } else { 269 // Check that post-RA scheduling is enabled for this target. 270 // This may upgrade the AntiDepMode. 271 const TargetSubtargetInfo &ST = Fn.getTarget().getSubtarget<TargetSubtargetInfo>(); 272 if (!ST.enablePostRAScheduler(PassConfig->getOptLevel(), AntiDepMode, 273 CriticalPathRCs)) 274 return false; 275 } 276 277 // Check for antidep breaking override... 278 if (EnableAntiDepBreaking.getPosition() > 0) { 279 AntiDepMode = (EnableAntiDepBreaking == "all") 280 ? TargetSubtargetInfo::ANTIDEP_ALL 281 : ((EnableAntiDepBreaking == "critical") 282 ? TargetSubtargetInfo::ANTIDEP_CRITICAL 283 : TargetSubtargetInfo::ANTIDEP_NONE); 284 } 285 286 DEBUG(dbgs() << "PostRAScheduler\n"); 287 288 SchedulePostRATDList Scheduler(Fn, MLI, MDT, AA, RegClassInfo, AntiDepMode, 289 CriticalPathRCs); 290 291 // Loop over all of the basic blocks 292 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); 293 MBB != MBBe; ++MBB) { 294#ifndef NDEBUG 295 // If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod 296 if (DebugDiv > 0) { 297 static int bbcnt = 0; 298 if (bbcnt++ % DebugDiv != DebugMod) 299 continue; 300 dbgs() << "*** DEBUG scheduling " << Fn.getName() 301 << ":BB#" << MBB->getNumber() << " ***\n"; 302 } 303#endif 304 305 // Initialize register live-range state for scheduling in this block. 306 Scheduler.startBlock(MBB); 307 308 // Schedule each sequence of instructions not interrupted by a label 309 // or anything else that effectively needs to shut down scheduling. 310 MachineBasicBlock::iterator Current = MBB->end(); 311 unsigned Count = MBB->size(), CurrentCount = Count; 312 for (MachineBasicBlock::iterator I = Current; I != MBB->begin(); ) { 313 MachineInstr *MI = llvm::prior(I); 314 // Calls are not scheduling boundaries before register allocation, but 315 // post-ra we don't gain anything by scheduling across calls since we 316 // don't need to worry about register pressure. 317 if (MI->isCall() || TII->isSchedulingBoundary(MI, MBB, Fn)) { 318 Scheduler.enterRegion(MBB, I, Current, CurrentCount); 319 Scheduler.schedule(); 320 Scheduler.exitRegion(); 321 Scheduler.EmitSchedule(); 322 Current = MI; 323 CurrentCount = Count - 1; 324 Scheduler.Observe(MI, CurrentCount); 325 } 326 I = MI; 327 --Count; 328 if (MI->isBundle()) 329 Count -= MI->getBundleSize(); 330 } 331 assert(Count == 0 && "Instruction count mismatch!"); 332 assert((MBB->begin() == Current || CurrentCount != 0) && 333 "Instruction count mismatch!"); 334 Scheduler.enterRegion(MBB, MBB->begin(), Current, CurrentCount); 335 Scheduler.schedule(); 336 Scheduler.exitRegion(); 337 Scheduler.EmitSchedule(); 338 339 // Clean up register live-range state. 340 Scheduler.finishBlock(); 341 342 // Update register kills 343 Scheduler.FixupKills(MBB); 344 } 345 346 return true; 347} 348 349/// StartBlock - Initialize register live-range state for scheduling in 350/// this block. 351/// 352void SchedulePostRATDList::startBlock(MachineBasicBlock *BB) { 353 // Call the superclass. 354 ScheduleDAGInstrs::startBlock(BB); 355 356 // Reset the hazard recognizer and anti-dep breaker. 357 HazardRec->Reset(); 358 if (AntiDepBreak != NULL) 359 AntiDepBreak->StartBlock(BB); 360} 361 362/// Schedule - Schedule the instruction range using list scheduling. 363/// 364void SchedulePostRATDList::schedule() { 365 // Build the scheduling graph. 366 buildSchedGraph(AA); 367 368 if (AntiDepBreak != NULL) { 369 unsigned Broken = 370 AntiDepBreak->BreakAntiDependencies(SUnits, RegionBegin, RegionEnd, 371 EndIndex, DbgValues); 372 373 if (Broken != 0) { 374 // We made changes. Update the dependency graph. 375 // Theoretically we could update the graph in place: 376 // When a live range is changed to use a different register, remove 377 // the def's anti-dependence *and* output-dependence edges due to 378 // that register, and add new anti-dependence and output-dependence 379 // edges based on the next live range of the register. 380 ScheduleDAG::clearDAG(); 381 buildSchedGraph(AA); 382 383 NumFixedAnti += Broken; 384 } 385 } 386 387 DEBUG(dbgs() << "********** List Scheduling **********\n"); 388 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 389 SUnits[su].dumpAll(this)); 390 391 AvailableQueue.initNodes(SUnits); 392 ListScheduleTopDown(); 393 AvailableQueue.releaseState(); 394} 395 396/// Observe - Update liveness information to account for the current 397/// instruction, which will not be scheduled. 398/// 399void SchedulePostRATDList::Observe(MachineInstr *MI, unsigned Count) { 400 if (AntiDepBreak != NULL) 401 AntiDepBreak->Observe(MI, Count, EndIndex); 402} 403 404/// FinishBlock - Clean up register live-range state. 405/// 406void SchedulePostRATDList::finishBlock() { 407 if (AntiDepBreak != NULL) 408 AntiDepBreak->FinishBlock(); 409 410 // Call the superclass. 411 ScheduleDAGInstrs::finishBlock(); 412} 413 414/// StartBlockForKills - Initialize register live-range state for updating kills 415/// 416void SchedulePostRATDList::StartBlockForKills(MachineBasicBlock *BB) { 417 // Start with no live registers. 418 LiveRegs.reset(); 419 420 // Determine the live-out physregs for this block. 421 if (!BB->empty() && BB->back().isReturn()) { 422 // In a return block, examine the function live-out regs. 423 for (MachineRegisterInfo::liveout_iterator I = MRI.liveout_begin(), 424 E = MRI.liveout_end(); I != E; ++I) { 425 unsigned Reg = *I; 426 LiveRegs.set(Reg); 427 // Repeat, for all subregs. 428 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) 429 LiveRegs.set(*SubRegs); 430 } 431 } 432 else { 433 // In a non-return block, examine the live-in regs of all successors. 434 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 435 SE = BB->succ_end(); SI != SE; ++SI) { 436 for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(), 437 E = (*SI)->livein_end(); I != E; ++I) { 438 unsigned Reg = *I; 439 LiveRegs.set(Reg); 440 // Repeat, for all subregs. 441 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) 442 LiveRegs.set(*SubRegs); 443 } 444 } 445 } 446} 447 448bool SchedulePostRATDList::ToggleKillFlag(MachineInstr *MI, 449 MachineOperand &MO) { 450 // Setting kill flag... 451 if (!MO.isKill()) { 452 MO.setIsKill(true); 453 return false; 454 } 455 456 // If MO itself is live, clear the kill flag... 457 if (LiveRegs.test(MO.getReg())) { 458 MO.setIsKill(false); 459 return false; 460 } 461 462 // If any subreg of MO is live, then create an imp-def for that 463 // subreg and keep MO marked as killed. 464 MO.setIsKill(false); 465 bool AllDead = true; 466 const unsigned SuperReg = MO.getReg(); 467 for (MCSubRegIterator SubRegs(SuperReg, TRI); SubRegs.isValid(); ++SubRegs) { 468 if (LiveRegs.test(*SubRegs)) { 469 MI->addOperand(MachineOperand::CreateReg(*SubRegs, 470 true /*IsDef*/, 471 true /*IsImp*/, 472 false /*IsKill*/, 473 false /*IsDead*/)); 474 AllDead = false; 475 } 476 } 477 478 if(AllDead) 479 MO.setIsKill(true); 480 return false; 481} 482 483/// FixupKills - Fix the register kill flags, they may have been made 484/// incorrect by instruction reordering. 485/// 486void SchedulePostRATDList::FixupKills(MachineBasicBlock *MBB) { 487 DEBUG(dbgs() << "Fixup kills for BB#" << MBB->getNumber() << '\n'); 488 489 BitVector killedRegs(TRI->getNumRegs()); 490 491 StartBlockForKills(MBB); 492 493 // Examine block from end to start... 494 unsigned Count = MBB->size(); 495 for (MachineBasicBlock::iterator I = MBB->end(), E = MBB->begin(); 496 I != E; --Count) { 497 MachineInstr *MI = --I; 498 if (MI->isDebugValue()) 499 continue; 500 501 // Update liveness. Registers that are defed but not used in this 502 // instruction are now dead. Mark register and all subregs as they 503 // are completely defined. 504 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 505 MachineOperand &MO = MI->getOperand(i); 506 if (MO.isRegMask()) 507 LiveRegs.clearBitsNotInMask(MO.getRegMask()); 508 if (!MO.isReg()) continue; 509 unsigned Reg = MO.getReg(); 510 if (Reg == 0) continue; 511 if (!MO.isDef()) continue; 512 // Ignore two-addr defs. 513 if (MI->isRegTiedToUseOperand(i)) continue; 514 515 LiveRegs.reset(Reg); 516 517 // Repeat for all subregs. 518 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) 519 LiveRegs.reset(*SubRegs); 520 } 521 522 // Examine all used registers and set/clear kill flag. When a 523 // register is used multiple times we only set the kill flag on 524 // the first use. 525 killedRegs.reset(); 526 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 527 MachineOperand &MO = MI->getOperand(i); 528 if (!MO.isReg() || !MO.isUse()) continue; 529 unsigned Reg = MO.getReg(); 530 if ((Reg == 0) || MRI.isReserved(Reg)) continue; 531 532 bool kill = false; 533 if (!killedRegs.test(Reg)) { 534 kill = true; 535 // A register is not killed if any subregs are live... 536 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 537 if (LiveRegs.test(*SubRegs)) { 538 kill = false; 539 break; 540 } 541 } 542 543 // If subreg is not live, then register is killed if it became 544 // live in this instruction 545 if (kill) 546 kill = !LiveRegs.test(Reg); 547 } 548 549 if (MO.isKill() != kill) { 550 DEBUG(dbgs() << "Fixing " << MO << " in "); 551 // Warning: ToggleKillFlag may invalidate MO. 552 ToggleKillFlag(MI, MO); 553 DEBUG(MI->dump()); 554 } 555 556 killedRegs.set(Reg); 557 } 558 559 // Mark any used register (that is not using undef) and subregs as 560 // now live... 561 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 562 MachineOperand &MO = MI->getOperand(i); 563 if (!MO.isReg() || !MO.isUse() || MO.isUndef()) continue; 564 unsigned Reg = MO.getReg(); 565 if ((Reg == 0) || MRI.isReserved(Reg)) continue; 566 567 LiveRegs.set(Reg); 568 569 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) 570 LiveRegs.set(*SubRegs); 571 } 572 } 573} 574 575//===----------------------------------------------------------------------===// 576// Top-Down Scheduling 577//===----------------------------------------------------------------------===// 578 579/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to 580/// the PendingQueue if the count reaches zero. 581void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) { 582 SUnit *SuccSU = SuccEdge->getSUnit(); 583 584 if (SuccEdge->isWeak()) { 585 --SuccSU->WeakPredsLeft; 586 return; 587 } 588#ifndef NDEBUG 589 if (SuccSU->NumPredsLeft == 0) { 590 dbgs() << "*** Scheduling failed! ***\n"; 591 SuccSU->dump(this); 592 dbgs() << " has been released too many times!\n"; 593 llvm_unreachable(0); 594 } 595#endif 596 --SuccSU->NumPredsLeft; 597 598 // Standard scheduler algorithms will recompute the depth of the successor 599 // here as such: 600 // SuccSU->setDepthToAtLeast(SU->getDepth() + SuccEdge->getLatency()); 601 // 602 // However, we lazily compute node depth instead. Note that 603 // ScheduleNodeTopDown has already updated the depth of this node which causes 604 // all descendents to be marked dirty. Setting the successor depth explicitly 605 // here would cause depth to be recomputed for all its ancestors. If the 606 // successor is not yet ready (because of a transitively redundant edge) then 607 // this causes depth computation to be quadratic in the size of the DAG. 608 609 // If all the node's predecessors are scheduled, this node is ready 610 // to be scheduled. Ignore the special ExitSU node. 611 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) 612 PendingQueue.push_back(SuccSU); 613} 614 615/// ReleaseSuccessors - Call ReleaseSucc on each of SU's successors. 616void SchedulePostRATDList::ReleaseSuccessors(SUnit *SU) { 617 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 618 I != E; ++I) { 619 ReleaseSucc(SU, &*I); 620 } 621} 622 623/// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending 624/// count of its successors. If a successor pending count is zero, add it to 625/// the Available queue. 626void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { 627 DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: "); 628 DEBUG(SU->dump(this)); 629 630 Sequence.push_back(SU); 631 assert(CurCycle >= SU->getDepth() && 632 "Node scheduled above its depth!"); 633 SU->setDepthToAtLeast(CurCycle); 634 635 ReleaseSuccessors(SU); 636 SU->isScheduled = true; 637 AvailableQueue.scheduledNode(SU); 638} 639 640/// ListScheduleTopDown - The main loop of list scheduling for top-down 641/// schedulers. 642void SchedulePostRATDList::ListScheduleTopDown() { 643 unsigned CurCycle = 0; 644 645 // We're scheduling top-down but we're visiting the regions in 646 // bottom-up order, so we don't know the hazards at the start of a 647 // region. So assume no hazards (this should usually be ok as most 648 // blocks are a single region). 649 HazardRec->Reset(); 650 651 // Release any successors of the special Entry node. 652 ReleaseSuccessors(&EntrySU); 653 654 // Add all leaves to Available queue. 655 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 656 // It is available if it has no predecessors. 657 if (!SUnits[i].NumPredsLeft && !SUnits[i].isAvailable) { 658 AvailableQueue.push(&SUnits[i]); 659 SUnits[i].isAvailable = true; 660 } 661 } 662 663 // In any cycle where we can't schedule any instructions, we must 664 // stall or emit a noop, depending on the target. 665 bool CycleHasInsts = false; 666 667 // While Available queue is not empty, grab the node with the highest 668 // priority. If it is not ready put it back. Schedule the node. 669 std::vector<SUnit*> NotReady; 670 Sequence.reserve(SUnits.size()); 671 while (!AvailableQueue.empty() || !PendingQueue.empty()) { 672 // Check to see if any of the pending instructions are ready to issue. If 673 // so, add them to the available queue. 674 unsigned MinDepth = ~0u; 675 for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) { 676 if (PendingQueue[i]->getDepth() <= CurCycle) { 677 AvailableQueue.push(PendingQueue[i]); 678 PendingQueue[i]->isAvailable = true; 679 PendingQueue[i] = PendingQueue.back(); 680 PendingQueue.pop_back(); 681 --i; --e; 682 } else if (PendingQueue[i]->getDepth() < MinDepth) 683 MinDepth = PendingQueue[i]->getDepth(); 684 } 685 686 DEBUG(dbgs() << "\n*** Examining Available\n"; AvailableQueue.dump(this)); 687 688 SUnit *FoundSUnit = 0; 689 bool HasNoopHazards = false; 690 while (!AvailableQueue.empty()) { 691 SUnit *CurSUnit = AvailableQueue.pop(); 692 693 ScheduleHazardRecognizer::HazardType HT = 694 HazardRec->getHazardType(CurSUnit, 0/*no stalls*/); 695 if (HT == ScheduleHazardRecognizer::NoHazard) { 696 FoundSUnit = CurSUnit; 697 break; 698 } 699 700 // Remember if this is a noop hazard. 701 HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard; 702 703 NotReady.push_back(CurSUnit); 704 } 705 706 // Add the nodes that aren't ready back onto the available list. 707 if (!NotReady.empty()) { 708 AvailableQueue.push_all(NotReady); 709 NotReady.clear(); 710 } 711 712 // If we found a node to schedule... 713 if (FoundSUnit) { 714 // ... schedule the node... 715 ScheduleNodeTopDown(FoundSUnit, CurCycle); 716 HazardRec->EmitInstruction(FoundSUnit); 717 CycleHasInsts = true; 718 if (HazardRec->atIssueLimit()) { 719 DEBUG(dbgs() << "*** Max instructions per cycle " << CurCycle << '\n'); 720 HazardRec->AdvanceCycle(); 721 ++CurCycle; 722 CycleHasInsts = false; 723 } 724 } else { 725 if (CycleHasInsts) { 726 DEBUG(dbgs() << "*** Finished cycle " << CurCycle << '\n'); 727 HazardRec->AdvanceCycle(); 728 } else if (!HasNoopHazards) { 729 // Otherwise, we have a pipeline stall, but no other problem, 730 // just advance the current cycle and try again. 731 DEBUG(dbgs() << "*** Stall in cycle " << CurCycle << '\n'); 732 HazardRec->AdvanceCycle(); 733 ++NumStalls; 734 } else { 735 // Otherwise, we have no instructions to issue and we have instructions 736 // that will fault if we don't do this right. This is the case for 737 // processors without pipeline interlocks and other cases. 738 DEBUG(dbgs() << "*** Emitting noop in cycle " << CurCycle << '\n'); 739 HazardRec->EmitNoop(); 740 Sequence.push_back(0); // NULL here means noop 741 ++NumNoops; 742 } 743 744 ++CurCycle; 745 CycleHasInsts = false; 746 } 747 } 748 749#ifndef NDEBUG 750 unsigned ScheduledNodes = VerifyScheduledDAG(/*isBottomUp=*/false); 751 unsigned Noops = 0; 752 for (unsigned i = 0, e = Sequence.size(); i != e; ++i) 753 if (!Sequence[i]) 754 ++Noops; 755 assert(Sequence.size() - Noops == ScheduledNodes && 756 "The number of nodes scheduled doesn't match the expected number!"); 757#endif // NDEBUG 758} 759 760// EmitSchedule - Emit the machine code in scheduled order. 761void SchedulePostRATDList::EmitSchedule() { 762 RegionBegin = RegionEnd; 763 764 // If first instruction was a DBG_VALUE then put it back. 765 if (FirstDbgValue) 766 BB->splice(RegionEnd, BB, FirstDbgValue); 767 768 // Then re-insert them according to the given schedule. 769 for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 770 if (SUnit *SU = Sequence[i]) 771 BB->splice(RegionEnd, BB, SU->getInstr()); 772 else 773 // Null SUnit* is a noop. 774 TII->insertNoop(*BB, RegionEnd); 775 776 // Update the Begin iterator, as the first instruction in the block 777 // may have been scheduled later. 778 if (i == 0) 779 RegionBegin = prior(RegionEnd); 780 } 781 782 // Reinsert any remaining debug_values. 783 for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator 784 DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) { 785 std::pair<MachineInstr *, MachineInstr *> P = *prior(DI); 786 MachineInstr *DbgValue = P.first; 787 MachineBasicBlock::iterator OrigPrivMI = P.second; 788 BB->splice(++OrigPrivMI, BB, DbgValue); 789 } 790 DbgValues.clear(); 791 FirstDbgValue = NULL; 792} 793