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