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