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