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