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