PostRASchedulerList.cpp revision fb9ebbf236974beac31705eaeb9f50ab585af6ab
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 /// Topo - A topological ordering for SUnits. 115 ScheduleDAGTopologicalSort Topo; 116 117 /// HazardRec - The hazard recognizer to use. 118 ScheduleHazardRecognizer *HazardRec; 119 120 /// AntiDepBreak - Anti-dependence breaking object, or NULL if none 121 AntiDepBreaker *AntiDepBreak; 122 123 /// AA - AliasAnalysis for making memory reference queries. 124 AliasAnalysis *AA; 125 126 /// LiveRegs - true if the register is live. 127 BitVector LiveRegs; 128 129 /// The schedule. Null SUnit*'s represent noop instructions. 130 std::vector<SUnit*> Sequence; 131 132 public: 133 SchedulePostRATDList( 134 MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT, 135 AliasAnalysis *AA, const RegisterClassInfo&, 136 TargetSubtargetInfo::AntiDepBreakMode AntiDepMode, 137 SmallVectorImpl<const TargetRegisterClass*> &CriticalPathRCs); 138 139 ~SchedulePostRATDList(); 140 141 /// startBlock - Initialize register live-range state for scheduling in 142 /// this block. 143 /// 144 void startBlock(MachineBasicBlock *BB); 145 146 /// Initialize the scheduler state for the next scheduling region. 147 virtual void enterRegion(MachineBasicBlock *bb, 148 MachineBasicBlock::iterator begin, 149 MachineBasicBlock::iterator end, 150 unsigned endcount); 151 152 /// Notify that the scheduler has finished scheduling the current region. 153 virtual void exitRegion(); 154 155 /// Schedule - Schedule the instruction range using list scheduling. 156 /// 157 void schedule(); 158 159 void EmitSchedule(); 160 161 /// Observe - Update liveness information to account for the current 162 /// instruction, which will not be scheduled. 163 /// 164 void Observe(MachineInstr *MI, unsigned Count); 165 166 /// finishBlock - Clean up register live-range state. 167 /// 168 void finishBlock(); 169 170 /// FixupKills - Fix register kill flags that have been made 171 /// invalid due to scheduling 172 /// 173 void FixupKills(MachineBasicBlock *MBB); 174 175 private: 176 void ReleaseSucc(SUnit *SU, SDep *SuccEdge); 177 void ReleaseSuccessors(SUnit *SU); 178 void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle); 179 void ListScheduleTopDown(); 180 void StartBlockForKills(MachineBasicBlock *BB); 181 182 // ToggleKillFlag - Toggle a register operand kill flag. Other 183 // adjustments may be made to the instruction if necessary. Return 184 // true if the operand has been deleted, false if not. 185 bool ToggleKillFlag(MachineInstr *MI, MachineOperand &MO); 186 187 void dumpSchedule() const; 188 }; 189} 190 191char &llvm::PostRASchedulerID = PostRAScheduler::ID; 192 193INITIALIZE_PASS(PostRAScheduler, "post-RA-sched", 194 "Post RA top-down list latency scheduler", false, false) 195 196SchedulePostRATDList::SchedulePostRATDList( 197 MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT, 198 AliasAnalysis *AA, const RegisterClassInfo &RCI, 199 TargetSubtargetInfo::AntiDepBreakMode AntiDepMode, 200 SmallVectorImpl<const TargetRegisterClass*> &CriticalPathRCs) 201 : ScheduleDAGInstrs(MF, MLI, MDT, /*IsPostRA=*/true), Topo(SUnits), AA(AA), 202 LiveRegs(TRI->getNumRegs()) 203{ 204 const TargetMachine &TM = MF.getTarget(); 205 const InstrItineraryData *InstrItins = TM.getInstrItineraryData(); 206 HazardRec = 207 TM.getInstrInfo()->CreateTargetPostRAHazardRecognizer(InstrItins, this); 208 209 assert((AntiDepMode == TargetSubtargetInfo::ANTIDEP_NONE || 210 MRI.tracksLiveness()) && 211 "Live-ins must be accurate for anti-dependency breaking"); 212 AntiDepBreak = 213 ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_ALL) ? 214 (AntiDepBreaker *)new AggressiveAntiDepBreaker(MF, RCI, CriticalPathRCs) : 215 ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_CRITICAL) ? 216 (AntiDepBreaker *)new CriticalAntiDepBreaker(MF, RCI) : NULL)); 217} 218 219SchedulePostRATDList::~SchedulePostRATDList() { 220 delete HazardRec; 221 delete AntiDepBreak; 222} 223 224/// Initialize state associated with the next scheduling region. 225void SchedulePostRATDList::enterRegion(MachineBasicBlock *bb, 226 MachineBasicBlock::iterator begin, 227 MachineBasicBlock::iterator end, 228 unsigned endcount) { 229 ScheduleDAGInstrs::enterRegion(bb, begin, end, endcount); 230 Sequence.clear(); 231} 232 233/// Print the schedule before exiting the region. 234void SchedulePostRATDList::exitRegion() { 235 DEBUG({ 236 dbgs() << "*** Final schedule ***\n"; 237 dumpSchedule(); 238 dbgs() << '\n'; 239 }); 240 ScheduleDAGInstrs::exitRegion(); 241} 242 243#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 244/// dumpSchedule - dump the scheduled Sequence. 245void SchedulePostRATDList::dumpSchedule() const { 246 for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 247 if (SUnit *SU = Sequence[i]) 248 SU->dump(this); 249 else 250 dbgs() << "**** NOOP ****\n"; 251 } 252} 253#endif 254 255bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { 256 TII = Fn.getTarget().getInstrInfo(); 257 MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>(); 258 MachineDominatorTree &MDT = getAnalysis<MachineDominatorTree>(); 259 AliasAnalysis *AA = &getAnalysis<AliasAnalysis>(); 260 TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>(); 261 262 RegClassInfo.runOnMachineFunction(Fn); 263 264 // Check for explicit enable/disable of post-ra scheduling. 265 TargetSubtargetInfo::AntiDepBreakMode AntiDepMode = 266 TargetSubtargetInfo::ANTIDEP_NONE; 267 SmallVector<const TargetRegisterClass*, 4> CriticalPathRCs; 268 if (EnablePostRAScheduler.getPosition() > 0) { 269 if (!EnablePostRAScheduler) 270 return false; 271 } else { 272 // Check that post-RA scheduling is enabled for this target. 273 // This may upgrade the AntiDepMode. 274 const TargetSubtargetInfo &ST = Fn.getTarget().getSubtarget<TargetSubtargetInfo>(); 275 if (!ST.enablePostRAScheduler(PassConfig->getOptLevel(), AntiDepMode, 276 CriticalPathRCs)) 277 return false; 278 } 279 280 // Check for antidep breaking override... 281 if (EnableAntiDepBreaking.getPosition() > 0) { 282 AntiDepMode = (EnableAntiDepBreaking == "all") 283 ? TargetSubtargetInfo::ANTIDEP_ALL 284 : ((EnableAntiDepBreaking == "critical") 285 ? TargetSubtargetInfo::ANTIDEP_CRITICAL 286 : TargetSubtargetInfo::ANTIDEP_NONE); 287 } 288 289 DEBUG(dbgs() << "PostRAScheduler\n"); 290 291 SchedulePostRATDList Scheduler(Fn, MLI, MDT, AA, RegClassInfo, AntiDepMode, 292 CriticalPathRCs); 293 294 // Loop over all of the basic blocks 295 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); 296 MBB != MBBe; ++MBB) { 297#ifndef NDEBUG 298 // If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod 299 if (DebugDiv > 0) { 300 static int bbcnt = 0; 301 if (bbcnt++ % DebugDiv != DebugMod) 302 continue; 303 dbgs() << "*** DEBUG scheduling " << Fn.getName() 304 << ":BB#" << MBB->getNumber() << " ***\n"; 305 } 306#endif 307 308 // Initialize register live-range state for scheduling in this block. 309 Scheduler.startBlock(MBB); 310 311 // Schedule each sequence of instructions not interrupted by a label 312 // or anything else that effectively needs to shut down scheduling. 313 MachineBasicBlock::iterator Current = MBB->end(); 314 unsigned Count = MBB->size(), CurrentCount = Count; 315 for (MachineBasicBlock::iterator I = Current; I != MBB->begin(); ) { 316 MachineInstr *MI = llvm::prior(I); 317 // Calls are not scheduling boundaries before register allocation, but 318 // post-ra we don't gain anything by scheduling across calls since we 319 // don't need to worry about register pressure. 320 if (MI->isCall() || TII->isSchedulingBoundary(MI, MBB, Fn)) { 321 Scheduler.enterRegion(MBB, I, Current, CurrentCount); 322 Scheduler.schedule(); 323 Scheduler.exitRegion(); 324 Scheduler.EmitSchedule(); 325 Current = MI; 326 CurrentCount = Count - 1; 327 Scheduler.Observe(MI, CurrentCount); 328 } 329 I = MI; 330 --Count; 331 if (MI->isBundle()) 332 Count -= MI->getBundleSize(); 333 } 334 assert(Count == 0 && "Instruction count mismatch!"); 335 assert((MBB->begin() == Current || CurrentCount != 0) && 336 "Instruction count mismatch!"); 337 Scheduler.enterRegion(MBB, MBB->begin(), Current, CurrentCount); 338 Scheduler.schedule(); 339 Scheduler.exitRegion(); 340 Scheduler.EmitSchedule(); 341 342 // Clean up register live-range state. 343 Scheduler.finishBlock(); 344 345 // Update register kills 346 Scheduler.FixupKills(MBB); 347 } 348 349 return true; 350} 351 352/// StartBlock - Initialize register live-range state for scheduling in 353/// this block. 354/// 355void SchedulePostRATDList::startBlock(MachineBasicBlock *BB) { 356 // Call the superclass. 357 ScheduleDAGInstrs::startBlock(BB); 358 359 // Reset the hazard recognizer and anti-dep breaker. 360 HazardRec->Reset(); 361 if (AntiDepBreak != NULL) 362 AntiDepBreak->StartBlock(BB); 363} 364 365/// Schedule - Schedule the instruction range using list scheduling. 366/// 367void SchedulePostRATDList::schedule() { 368 // Build the scheduling graph. 369 buildSchedGraph(AA); 370 371 if (AntiDepBreak != NULL) { 372 unsigned Broken = 373 AntiDepBreak->BreakAntiDependencies(SUnits, RegionBegin, RegionEnd, 374 EndIndex, DbgValues); 375 376 if (Broken != 0) { 377 // We made changes. Update the dependency graph. 378 // Theoretically we could update the graph in place: 379 // When a live range is changed to use a different register, remove 380 // the def's anti-dependence *and* output-dependence edges due to 381 // that register, and add new anti-dependence and output-dependence 382 // edges based on the next live range of the register. 383 ScheduleDAG::clearDAG(); 384 buildSchedGraph(AA); 385 386 NumFixedAnti += Broken; 387 } 388 } 389 390 DEBUG(dbgs() << "********** List Scheduling **********\n"); 391 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 392 SUnits[su].dumpAll(this)); 393 394 AvailableQueue.initNodes(SUnits); 395 ListScheduleTopDown(); 396 AvailableQueue.releaseState(); 397} 398 399/// Observe - Update liveness information to account for the current 400/// instruction, which will not be scheduled. 401/// 402void SchedulePostRATDList::Observe(MachineInstr *MI, unsigned Count) { 403 if (AntiDepBreak != NULL) 404 AntiDepBreak->Observe(MI, Count, EndIndex); 405} 406 407/// FinishBlock - Clean up register live-range state. 408/// 409void SchedulePostRATDList::finishBlock() { 410 if (AntiDepBreak != NULL) 411 AntiDepBreak->FinishBlock(); 412 413 // Call the superclass. 414 ScheduleDAGInstrs::finishBlock(); 415} 416 417/// StartBlockForKills - Initialize register live-range state for updating kills 418/// 419void SchedulePostRATDList::StartBlockForKills(MachineBasicBlock *BB) { 420 // Start with no live registers. 421 LiveRegs.reset(); 422 423 // Determine the live-out physregs for this block. 424 if (!BB->empty() && BB->back().isReturn()) { 425 // In a return block, examine the function live-out regs. 426 for (MachineRegisterInfo::liveout_iterator I = MRI.liveout_begin(), 427 E = MRI.liveout_end(); I != E; ++I) { 428 unsigned Reg = *I; 429 LiveRegs.set(Reg); 430 // Repeat, for all subregs. 431 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) 432 LiveRegs.set(*SubRegs); 433 } 434 } 435 else { 436 // In a non-return block, examine the live-in regs of all successors. 437 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 438 SE = BB->succ_end(); SI != SE; ++SI) { 439 for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(), 440 E = (*SI)->livein_end(); I != E; ++I) { 441 unsigned Reg = *I; 442 LiveRegs.set(Reg); 443 // Repeat, for all subregs. 444 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) 445 LiveRegs.set(*SubRegs); 446 } 447 } 448 } 449} 450 451bool SchedulePostRATDList::ToggleKillFlag(MachineInstr *MI, 452 MachineOperand &MO) { 453 // Setting kill flag... 454 if (!MO.isKill()) { 455 MO.setIsKill(true); 456 return false; 457 } 458 459 // If MO itself is live, clear the kill flag... 460 if (LiveRegs.test(MO.getReg())) { 461 MO.setIsKill(false); 462 return false; 463 } 464 465 // If any subreg of MO is live, then create an imp-def for that 466 // subreg and keep MO marked as killed. 467 MO.setIsKill(false); 468 bool AllDead = true; 469 const unsigned SuperReg = MO.getReg(); 470 for (MCSubRegIterator SubRegs(SuperReg, TRI); SubRegs.isValid(); ++SubRegs) { 471 if (LiveRegs.test(*SubRegs)) { 472 MI->addOperand(MachineOperand::CreateReg(*SubRegs, 473 true /*IsDef*/, 474 true /*IsImp*/, 475 false /*IsKill*/, 476 false /*IsDead*/)); 477 AllDead = false; 478 } 479 } 480 481 if(AllDead) 482 MO.setIsKill(true); 483 return false; 484} 485 486/// FixupKills - Fix the register kill flags, they may have been made 487/// incorrect by instruction reordering. 488/// 489void SchedulePostRATDList::FixupKills(MachineBasicBlock *MBB) { 490 DEBUG(dbgs() << "Fixup kills for BB#" << MBB->getNumber() << '\n'); 491 492 BitVector killedRegs(TRI->getNumRegs()); 493 494 StartBlockForKills(MBB); 495 496 // Examine block from end to start... 497 unsigned Count = MBB->size(); 498 for (MachineBasicBlock::iterator I = MBB->end(), E = MBB->begin(); 499 I != E; --Count) { 500 MachineInstr *MI = --I; 501 if (MI->isDebugValue()) 502 continue; 503 504 // Update liveness. Registers that are defed but not used in this 505 // instruction are now dead. Mark register and all subregs as they 506 // are completely defined. 507 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 508 MachineOperand &MO = MI->getOperand(i); 509 if (MO.isRegMask()) 510 LiveRegs.clearBitsNotInMask(MO.getRegMask()); 511 if (!MO.isReg()) continue; 512 unsigned Reg = MO.getReg(); 513 if (Reg == 0) continue; 514 if (!MO.isDef()) continue; 515 // Ignore two-addr defs. 516 if (MI->isRegTiedToUseOperand(i)) continue; 517 518 LiveRegs.reset(Reg); 519 520 // Repeat for all subregs. 521 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) 522 LiveRegs.reset(*SubRegs); 523 } 524 525 // Examine all used registers and set/clear kill flag. When a 526 // register is used multiple times we only set the kill flag on 527 // the first use. 528 killedRegs.reset(); 529 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 530 MachineOperand &MO = MI->getOperand(i); 531 if (!MO.isReg() || !MO.isUse()) continue; 532 unsigned Reg = MO.getReg(); 533 if ((Reg == 0) || MRI.isReserved(Reg)) continue; 534 535 bool kill = false; 536 if (!killedRegs.test(Reg)) { 537 kill = true; 538 // A register is not killed if any subregs are live... 539 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 540 if (LiveRegs.test(*SubRegs)) { 541 kill = false; 542 break; 543 } 544 } 545 546 // If subreg is not live, then register is killed if it became 547 // live in this instruction 548 if (kill) 549 kill = !LiveRegs.test(Reg); 550 } 551 552 if (MO.isKill() != kill) { 553 DEBUG(dbgs() << "Fixing " << MO << " in "); 554 // Warning: ToggleKillFlag may invalidate MO. 555 ToggleKillFlag(MI, MO); 556 DEBUG(MI->dump()); 557 } 558 559 killedRegs.set(Reg); 560 } 561 562 // Mark any used register (that is not using undef) and subregs as 563 // now live... 564 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 565 MachineOperand &MO = MI->getOperand(i); 566 if (!MO.isReg() || !MO.isUse() || MO.isUndef()) continue; 567 unsigned Reg = MO.getReg(); 568 if ((Reg == 0) || MRI.isReserved(Reg)) continue; 569 570 LiveRegs.set(Reg); 571 572 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) 573 LiveRegs.set(*SubRegs); 574 } 575 } 576} 577 578//===----------------------------------------------------------------------===// 579// Top-Down Scheduling 580//===----------------------------------------------------------------------===// 581 582/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to 583/// the PendingQueue if the count reaches zero. Also update its cycle bound. 584void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) { 585 SUnit *SuccSU = SuccEdge->getSUnit(); 586 587#ifndef NDEBUG 588 if (SuccSU->NumPredsLeft == 0) { 589 dbgs() << "*** Scheduling failed! ***\n"; 590 SuccSU->dump(this); 591 dbgs() << " has been released too many times!\n"; 592 llvm_unreachable(0); 593 } 594#endif 595 --SuccSU->NumPredsLeft; 596 597 // Standard scheduler algorithms will recompute the depth of the successor 598 // here as such: 599 // SuccSU->setDepthToAtLeast(SU->getDepth() + SuccEdge->getLatency()); 600 // 601 // However, we lazily compute node depth instead. Note that 602 // ScheduleNodeTopDown has already updated the depth of this node which causes 603 // all descendents to be marked dirty. Setting the successor depth explicitly 604 // here would cause depth to be recomputed for all its ancestors. If the 605 // successor is not yet ready (because of a transitively redundant edge) then 606 // this causes depth computation to be quadratic in the size of the DAG. 607 608 // If all the node's predecessors are scheduled, this node is ready 609 // to be scheduled. Ignore the special ExitSU node. 610 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) 611 PendingQueue.push_back(SuccSU); 612} 613 614/// ReleaseSuccessors - Call ReleaseSucc on each of SU's successors. 615void SchedulePostRATDList::ReleaseSuccessors(SUnit *SU) { 616 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 617 I != E; ++I) { 618 ReleaseSucc(SU, &*I); 619 } 620} 621 622/// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending 623/// count of its successors. If a successor pending count is zero, add it to 624/// the Available queue. 625void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { 626 DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: "); 627 DEBUG(SU->dump(this)); 628 629 Sequence.push_back(SU); 630 assert(CurCycle >= SU->getDepth() && 631 "Node scheduled above its depth!"); 632 SU->setDepthToAtLeast(CurCycle); 633 634 ReleaseSuccessors(SU); 635 SU->isScheduled = true; 636 AvailableQueue.scheduledNode(SU); 637} 638 639/// ListScheduleTopDown - The main loop of list scheduling for top-down 640/// schedulers. 641void SchedulePostRATDList::ListScheduleTopDown() { 642 unsigned CurCycle = 0; 643 644 // We're scheduling top-down but we're visiting the regions in 645 // bottom-up order, so we don't know the hazards at the start of a 646 // region. So assume no hazards (this should usually be ok as most 647 // blocks are a single region). 648 HazardRec->Reset(); 649 650 // Release any successors of the special Entry node. 651 ReleaseSuccessors(&EntrySU); 652 653 // Add all leaves to Available queue. 654 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 655 // It is available if it has no predecessors. 656 bool available = SUnits[i].Preds.empty(); 657 if (available) { 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