PostRASchedulerList.cpp revision 97b549fb49d067d356c8acf74185f1da9b1ca335
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 "llvm/CodeGen/Passes.h" 23#include "llvm/CodeGen/ScheduleDAGInstrs.h" 24#include "llvm/CodeGen/LatencyPriorityQueue.h" 25#include "llvm/CodeGen/SchedulerRegistry.h" 26#include "llvm/CodeGen/MachineFunctionPass.h" 27#include "llvm/CodeGen/MachineRegisterInfo.h" 28#include "llvm/Target/TargetInstrInfo.h" 29#include "llvm/Target/TargetRegisterInfo.h" 30#include "llvm/Support/Compiler.h" 31#include "llvm/Support/Debug.h" 32#include "llvm/ADT/Statistic.h" 33#include "llvm/ADT/DenseSet.h" 34#include <map> 35#include <climits> 36using namespace llvm; 37 38STATISTIC(NumStalls, "Number of pipeline stalls"); 39 40static cl::opt<bool> 41EnableAntiDepBreaking("break-anti-dependencies", 42 cl::desc("Break scheduling anti-dependencies"), 43 cl::init(false)); 44 45namespace { 46 class VISIBILITY_HIDDEN PostRAScheduler : public MachineFunctionPass { 47 public: 48 static char ID; 49 PostRAScheduler() : MachineFunctionPass(&ID) {} 50 51 const char *getPassName() const { 52 return "Post RA top-down list latency scheduler"; 53 } 54 55 bool runOnMachineFunction(MachineFunction &Fn); 56 }; 57 char PostRAScheduler::ID = 0; 58 59 class VISIBILITY_HIDDEN SchedulePostRATDList : public ScheduleDAGInstrs { 60 /// AvailableQueue - The priority queue to use for the available SUnits. 61 /// 62 LatencyPriorityQueue AvailableQueue; 63 64 /// PendingQueue - This contains all of the instructions whose operands have 65 /// been issued, but their results are not ready yet (due to the latency of 66 /// the operation). Once the operands becomes available, the instruction is 67 /// added to the AvailableQueue. 68 std::vector<SUnit*> PendingQueue; 69 70 /// Topo - A topological ordering for SUnits. 71 ScheduleDAGTopologicalSort Topo; 72 73 public: 74 SchedulePostRATDList(MachineBasicBlock *mbb, const TargetMachine &tm) 75 : ScheduleDAGInstrs(mbb, tm), Topo(SUnits) {} 76 77 void Schedule(); 78 79 private: 80 void ReleaseSucc(SUnit *SU, SUnit *SuccSU, bool isChain); 81 void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle); 82 void ListScheduleTopDown(); 83 bool BreakAntiDependencies(); 84 }; 85} 86 87bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { 88 DOUT << "PostRAScheduler\n"; 89 90 // Loop over all of the basic blocks 91 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); 92 MBB != MBBe; ++MBB) { 93 94 SchedulePostRATDList Scheduler(MBB, Fn.getTarget()); 95 96 Scheduler.Run(); 97 98 Scheduler.EmitSchedule(); 99 } 100 101 return true; 102} 103 104/// Schedule - Schedule the DAG using list scheduling. 105void SchedulePostRATDList::Schedule() { 106 DOUT << "********** List Scheduling **********\n"; 107 108 // Build scheduling units. 109 BuildSchedUnits(); 110 111 if (EnableAntiDepBreaking) { 112 if (BreakAntiDependencies()) { 113 // We made changes. Update the dependency graph. 114 // Theoretically we could update the graph in place: 115 // When a live range is changed to use a different register, remove 116 // the def's anti-dependence *and* output-dependence edges due to 117 // that register, and add new anti-dependence and output-dependence 118 // edges based on the next live range of the register. 119 SUnits.clear(); 120 BuildSchedUnits(); 121 } 122 } 123 124 AvailableQueue.initNodes(SUnits); 125 126 ListScheduleTopDown(); 127 128 AvailableQueue.releaseState(); 129} 130 131/// getInstrOperandRegClass - Return register class of the operand of an 132/// instruction of the specified TargetInstrDesc. 133static const TargetRegisterClass* 134getInstrOperandRegClass(const TargetRegisterInfo *TRI, 135 const TargetInstrInfo *TII, const TargetInstrDesc &II, 136 unsigned Op) { 137 if (Op >= II.getNumOperands()) 138 return NULL; 139 if (II.OpInfo[Op].isLookupPtrRegClass()) 140 return TII->getPointerRegClass(); 141 return TRI->getRegClass(II.OpInfo[Op].RegClass); 142} 143 144/// BreakAntiDependencies - Identifiy anti-dependencies along the critical path 145/// of the ScheduleDAG and break them by renaming registers. 146/// 147bool SchedulePostRATDList::BreakAntiDependencies() { 148 // The code below assumes that there is at least one instruction, 149 // so just duck out immediately if the block is empty. 150 if (BB->empty()) return false; 151 152 Topo.InitDAGTopologicalSorting(); 153 154 // Compute a critical path for the DAG. 155 SUnit *Max = 0; 156 std::vector<SDep *> CriticalPath(SUnits.size()); 157 for (ScheduleDAGTopologicalSort::const_iterator I = Topo.begin(), 158 E = Topo.end(); I != E; ++I) { 159 SUnit *SU = &SUnits[*I]; 160 for (SUnit::pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end(); 161 P != PE; ++P) { 162 SUnit *PredSU = P->Dep; 163 unsigned PredLatency = PredSU->CycleBound + PredSU->Latency; 164 if (SU->CycleBound < PredLatency) { 165 SU->CycleBound = PredLatency; 166 CriticalPath[*I] = &*P; 167 } 168 } 169 // Keep track of the node at the end of the critical path. 170 if (!Max || SU->CycleBound + SU->Latency > Max->CycleBound + Max->Latency) 171 Max = SU; 172 } 173 174 DOUT << "Critical path has total latency " 175 << (Max ? Max->CycleBound + Max->Latency : 0) << "\n"; 176 177 // Walk the critical path from the bottom up. Collect all anti-dependence 178 // edges on the critical path. Skip anti-dependencies between SUnits that 179 // are connected with other edges, since such units won't be able to be 180 // scheduled past each other anyway. 181 // 182 // The heuristic is that edges on the critical path are more important to 183 // break than other edges. And since there are a limited number of 184 // registers, we don't want to waste them breaking edges that aren't 185 // important. 186 // 187 // TODO: Instructions with multiple defs could have multiple 188 // anti-dependencies. The current code here only knows how to break one 189 // edge per instruction. Note that we'd have to be able to break all of 190 // the anti-dependencies in an instruction in order to be effective. 191 BitVector AllocatableSet = TRI->getAllocatableSet(*MF); 192 DenseMap<MachineInstr *, unsigned> CriticalAntiDeps; 193 for (SUnit *SU = Max; CriticalPath[SU->NodeNum]; 194 SU = CriticalPath[SU->NodeNum]->Dep) { 195 SDep *Edge = CriticalPath[SU->NodeNum]; 196 SUnit *NextSU = Edge->Dep; 197 unsigned AntiDepReg = Edge->Reg; 198 // Don't break anti-dependencies on non-allocatable registers. 199 if (!AllocatableSet.test(AntiDepReg)) 200 continue; 201 // If the SUnit has other dependencies on the SUnit that it 202 // anti-depends on, don't bother breaking the anti-dependency. 203 // Also, if there are dependencies on other SUnits with the 204 // same register as the anti-dependency, don't attempt to 205 // break it. 206 for (SUnit::pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end(); 207 P != PE; ++P) 208 if (P->Dep == NextSU ? 209 (!P->isAntiDep || P->Reg != AntiDepReg) : 210 (!P->isCtrl && !P->isAntiDep && P->Reg == AntiDepReg)) { 211 AntiDepReg = 0; 212 break; 213 } 214 if (AntiDepReg != 0) 215 CriticalAntiDeps[SU->getInstr()] = AntiDepReg; 216 } 217 218 // For live regs that are only used in one register class in a live range, 219 // the register class. If the register is not live or is referenced in 220 // multiple register classes, the corresponding value is null. If the 221 // register is used in multiple register classes, the corresponding value 222 // is -1 casted to a pointer. 223 const TargetRegisterClass * 224 Classes[TargetRegisterInfo::FirstVirtualRegister] = {}; 225 226 // Map registers to all their references within a live range. 227 std::multimap<unsigned, MachineOperand *> RegRefs; 228 229 // The index of the most recent kill (proceding bottom-up), or -1 if 230 // the register is not live. 231 unsigned KillIndices[TargetRegisterInfo::FirstVirtualRegister]; 232 std::fill(KillIndices, array_endof(KillIndices), -1); 233 // The index of the most recent def (proceding bottom up), or -1 if 234 // the register is live. 235 unsigned DefIndices[TargetRegisterInfo::FirstVirtualRegister]; 236 std::fill(DefIndices, array_endof(DefIndices), BB->size()); 237 238 // Determine the live-out physregs for this block. 239 if (!BB->empty() && BB->back().getDesc().isReturn()) 240 // In a return block, examine the function live-out regs. 241 for (MachineRegisterInfo::liveout_iterator I = MRI.liveout_begin(), 242 E = MRI.liveout_end(); I != E; ++I) { 243 unsigned Reg = *I; 244 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 245 KillIndices[Reg] = BB->size(); 246 DefIndices[Reg] = -1; 247 // Repeat, for all aliases. 248 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 249 unsigned AliasReg = *Alias; 250 Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1); 251 KillIndices[AliasReg] = BB->size(); 252 DefIndices[AliasReg] = -1; 253 } 254 } 255 else 256 // In a non-return block, examine the live-in regs of all successors. 257 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 258 SE = BB->succ_end(); SI != SE; ++SI) 259 for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(), 260 E = (*SI)->livein_end(); I != E; ++I) { 261 unsigned Reg = *I; 262 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 263 KillIndices[Reg] = BB->size(); 264 DefIndices[Reg] = -1; 265 // Repeat, for all aliases. 266 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 267 unsigned AliasReg = *Alias; 268 Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1); 269 KillIndices[AliasReg] = BB->size(); 270 DefIndices[AliasReg] = -1; 271 } 272 } 273 274 // Consider callee-saved registers as live-out, since we're running after 275 // prologue/epilogue insertion so there's no way to add additional 276 // saved registers. 277 // 278 // TODO: If the callee saves and restores these, then we can potentially 279 // use them between the save and the restore. To do that, we could scan 280 // the exit blocks to see which of these registers are defined. 281 for (const unsigned *I = TRI->getCalleeSavedRegs(); *I; ++I) { 282 unsigned Reg = *I; 283 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 284 KillIndices[Reg] = BB->size(); 285 DefIndices[Reg] = -1; 286 // Repeat, for all aliases. 287 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 288 unsigned AliasReg = *Alias; 289 Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1); 290 KillIndices[AliasReg] = BB->size(); 291 DefIndices[AliasReg] = -1; 292 } 293 } 294 295 // Consider this pattern: 296 // A = ... 297 // ... = A 298 // A = ... 299 // ... = A 300 // A = ... 301 // ... = A 302 // A = ... 303 // ... = A 304 // There are three anti-dependencies here, and without special care, 305 // we'd break all of them using the same register: 306 // A = ... 307 // ... = A 308 // B = ... 309 // ... = B 310 // B = ... 311 // ... = B 312 // B = ... 313 // ... = B 314 // because at each anti-dependence, B is the first register that 315 // isn't A which is free. This re-introduces anti-dependencies 316 // at all but one of the original anti-dependencies that we were 317 // trying to break. To avoid this, keep track of the most recent 318 // register that each register was replaced with, avoid avoid 319 // using it to repair an anti-dependence on the same register. 320 // This lets us produce this: 321 // A = ... 322 // ... = A 323 // B = ... 324 // ... = B 325 // C = ... 326 // ... = C 327 // B = ... 328 // ... = B 329 // This still has an anti-dependence on B, but at least it isn't on the 330 // original critical path. 331 // 332 // TODO: If we tracked more than one register here, we could potentially 333 // fix that remaining critical edge too. This is a little more involved, 334 // because unlike the most recent register, less recent registers should 335 // still be considered, though only if no other registers are available. 336 unsigned LastNewReg[TargetRegisterInfo::FirstVirtualRegister] = {}; 337 338 // A registers defined and not used in an instruction. This is used for 339 // liveness tracking and is declared outside the loop only to avoid 340 // having it be re-allocated on each iteration. 341 DenseSet<unsigned> Defs; 342 343 // Attempt to break anti-dependence edges on the critical path. Walk the 344 // instructions from the bottom up, tracking information about liveness 345 // as we go to help determine which registers are available. 346 bool Changed = false; 347 unsigned Count = BB->size() - 1; 348 for (MachineBasicBlock::reverse_iterator I = BB->rbegin(), E = BB->rend(); 349 I != E; ++I, --Count) { 350 MachineInstr *MI = &*I; 351 352 // Check if this instruction has an anti-dependence that we're 353 // interested in. 354 DenseMap<MachineInstr *, unsigned>::iterator C = CriticalAntiDeps.find(MI); 355 unsigned AntiDepReg = C != CriticalAntiDeps.end() ? 356 C->second : 0; 357 358 // Scan the register operands for this instruction and update 359 // Classes and RegRefs. 360 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 361 MachineOperand &MO = MI->getOperand(i); 362 if (!MO.isReg()) continue; 363 unsigned Reg = MO.getReg(); 364 if (Reg == 0) continue; 365 const TargetRegisterClass *NewRC = 366 getInstrOperandRegClass(TRI, TII, MI->getDesc(), i); 367 368 // If this instruction has a use of AntiDepReg, breaking it 369 // is invalid. 370 if (MO.isUse() && AntiDepReg == Reg) 371 AntiDepReg = 0; 372 373 // For now, only allow the register to be changed if its register 374 // class is consistent across all uses. 375 if (!Classes[Reg] && NewRC) 376 Classes[Reg] = NewRC; 377 else if (!NewRC || Classes[Reg] != NewRC) 378 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 379 380 // Now check for aliases. 381 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 382 // If an alias of the reg is used during the live range, give up. 383 // Note that this allows us to skip checking if AntiDepReg 384 // overlaps with any of the aliases, among other things. 385 unsigned AliasReg = *Alias; 386 if (Classes[AliasReg]) { 387 Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1); 388 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 389 } 390 } 391 392 // If we're still willing to consider this register, note the reference. 393 if (Classes[Reg] != reinterpret_cast<TargetRegisterClass *>(-1)) 394 RegRefs.insert(std::make_pair(Reg, &MO)); 395 } 396 397 // Determine AntiDepReg's register class, if it is live and is 398 // consistently used within a single class. 399 const TargetRegisterClass *RC = AntiDepReg != 0 ? Classes[AntiDepReg] : 0; 400 assert((AntiDepReg == 0 || RC != NULL) && 401 "Register should be live if it's causing an anti-dependence!"); 402 if (RC == reinterpret_cast<TargetRegisterClass *>(-1)) 403 AntiDepReg = 0; 404 405 // Look for a suitable register to use to break the anti-depenence. 406 // 407 // TODO: Instead of picking the first free register, consider which might 408 // be the best. 409 if (AntiDepReg != 0) { 410 for (TargetRegisterClass::iterator R = RC->allocation_order_begin(*MF), 411 RE = RC->allocation_order_end(*MF); R != RE; ++R) { 412 unsigned NewReg = *R; 413 // Don't replace a register with itself. 414 if (NewReg == AntiDepReg) continue; 415 // Don't replace a register with one that was recently used to repair 416 // an anti-dependence with this AntiDepReg, because that would 417 // re-introduce that anti-dependence. 418 if (NewReg == LastNewReg[AntiDepReg]) continue; 419 // If NewReg is dead and NewReg's most recent def is not before 420 // AntiDepReg's kill, it's safe to replace AntiDepReg with NewReg. 421 assert(((KillIndices[AntiDepReg] == -1u) != (DefIndices[AntiDepReg] == -1u)) && 422 "Kill and Def maps aren't consistent for AntiDepReg!"); 423 assert(((KillIndices[NewReg] == -1u) != (DefIndices[NewReg] == -1u)) && 424 "Kill and Def maps aren't consistent for NewReg!"); 425 if (KillIndices[NewReg] == -1u && 426 KillIndices[AntiDepReg] <= DefIndices[NewReg]) { 427 DOUT << "Breaking anti-dependence edge on reg " << AntiDepReg 428 << " with reg " << NewReg << "!\n"; 429 430 // Update the references to the old register to refer to the new 431 // register. 432 std::pair<std::multimap<unsigned, MachineOperand *>::iterator, 433 std::multimap<unsigned, MachineOperand *>::iterator> 434 Range = RegRefs.equal_range(AntiDepReg); 435 for (std::multimap<unsigned, MachineOperand *>::iterator 436 Q = Range.first, QE = Range.second; Q != QE; ++Q) 437 Q->second->setReg(NewReg); 438 439 // We just went back in time and modified history; the 440 // liveness information for the anti-depenence reg is now 441 // inconsistent. Set the state as if it were dead. 442 Classes[NewReg] = Classes[AntiDepReg]; 443 DefIndices[NewReg] = DefIndices[AntiDepReg]; 444 KillIndices[NewReg] = KillIndices[AntiDepReg]; 445 446 Classes[AntiDepReg] = 0; 447 DefIndices[AntiDepReg] = KillIndices[AntiDepReg]; 448 KillIndices[AntiDepReg] = -1; 449 450 RegRefs.erase(AntiDepReg); 451 Changed = true; 452 LastNewReg[AntiDepReg] = NewReg; 453 break; 454 } 455 } 456 } 457 458 // Update liveness. 459 Defs.clear(); 460 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 461 MachineOperand &MO = MI->getOperand(i); 462 if (!MO.isReg()) continue; 463 unsigned Reg = MO.getReg(); 464 if (Reg == 0) continue; 465 if (MO.isDef()) 466 Defs.insert(Reg); 467 else { 468 // Treat a use in the same instruction as a def as an extension of 469 // a live range. 470 Defs.erase(Reg); 471 // It wasn't previously live but now it is, this is a kill. 472 if (KillIndices[Reg] == -1u) { 473 KillIndices[Reg] = Count; 474 DefIndices[Reg] = -1u; 475 } 476 // Repeat, for all aliases. 477 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 478 unsigned AliasReg = *Alias; 479 Defs.erase(AliasReg); 480 if (KillIndices[AliasReg] == -1u) { 481 KillIndices[AliasReg] = Count; 482 DefIndices[AliasReg] = -1u; 483 } 484 } 485 } 486 } 487 // Proceding upwards, registers that are defed but not used in this 488 // instruction are now dead. 489 for (DenseSet<unsigned>::iterator D = Defs.begin(), DE = Defs.end(); 490 D != DE; ++D) { 491 unsigned Reg = *D; 492 DefIndices[Reg] = Count; 493 KillIndices[Reg] = -1; 494 Classes[Reg] = 0; 495 RegRefs.erase(Reg); 496 // Repeat, for all subregs. 497 for (const unsigned *Subreg = TRI->getSubRegisters(Reg); 498 *Subreg; ++Subreg) { 499 unsigned SubregReg = *Subreg; 500 DefIndices[SubregReg] = Count; 501 KillIndices[SubregReg] = -1; 502 Classes[SubregReg] = 0; 503 RegRefs.erase(SubregReg); 504 } 505 } 506 } 507 assert(Count == -1u && "Count mismatch!"); 508 509 return Changed; 510} 511 512//===----------------------------------------------------------------------===// 513// Top-Down Scheduling 514//===----------------------------------------------------------------------===// 515 516/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to 517/// the PendingQueue if the count reaches zero. Also update its cycle bound. 518void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SUnit *SuccSU, bool isChain) { 519 --SuccSU->NumPredsLeft; 520 521#ifndef NDEBUG 522 if (SuccSU->NumPredsLeft < 0) { 523 cerr << "*** Scheduling failed! ***\n"; 524 SuccSU->dump(this); 525 cerr << " has been released too many times!\n"; 526 assert(0); 527 } 528#endif 529 530 // Compute how many cycles it will be before this actually becomes 531 // available. This is the max of the start time of all predecessors plus 532 // their latencies. 533 // If this is a token edge, we don't need to wait for the latency of the 534 // preceeding instruction (e.g. a long-latency load) unless there is also 535 // some other data dependence. 536 unsigned PredDoneCycle = SU->Cycle; 537 if (!isChain) 538 PredDoneCycle += SU->Latency; 539 else if (SU->Latency) 540 PredDoneCycle += 1; 541 SuccSU->CycleBound = std::max(SuccSU->CycleBound, PredDoneCycle); 542 543 if (SuccSU->NumPredsLeft == 0) { 544 PendingQueue.push_back(SuccSU); 545 } 546} 547 548/// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending 549/// count of its successors. If a successor pending count is zero, add it to 550/// the Available queue. 551void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { 552 DOUT << "*** Scheduling [" << CurCycle << "]: "; 553 DEBUG(SU->dump(this)); 554 555 Sequence.push_back(SU); 556 SU->Cycle = CurCycle; 557 558 // Top down: release successors. 559 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 560 I != E; ++I) 561 ReleaseSucc(SU, I->Dep, I->isCtrl); 562 563 SU->isScheduled = true; 564 AvailableQueue.ScheduledNode(SU); 565} 566 567/// ListScheduleTopDown - The main loop of list scheduling for top-down 568/// schedulers. 569void SchedulePostRATDList::ListScheduleTopDown() { 570 unsigned CurCycle = 0; 571 572 // All leaves to Available queue. 573 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 574 // It is available if it has no predecessors. 575 if (SUnits[i].Preds.empty()) { 576 AvailableQueue.push(&SUnits[i]); 577 SUnits[i].isAvailable = true; 578 } 579 } 580 581 // While Available queue is not empty, grab the node with the highest 582 // priority. If it is not ready put it back. Schedule the node. 583 Sequence.reserve(SUnits.size()); 584 while (!AvailableQueue.empty() || !PendingQueue.empty()) { 585 // Check to see if any of the pending instructions are ready to issue. If 586 // so, add them to the available queue. 587 for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) { 588 if (PendingQueue[i]->CycleBound == CurCycle) { 589 AvailableQueue.push(PendingQueue[i]); 590 PendingQueue[i]->isAvailable = true; 591 PendingQueue[i] = PendingQueue.back(); 592 PendingQueue.pop_back(); 593 --i; --e; 594 } else { 595 assert(PendingQueue[i]->CycleBound > CurCycle && "Negative latency?"); 596 } 597 } 598 599 // If there are no instructions available, don't try to issue anything. 600 if (AvailableQueue.empty()) { 601 ++CurCycle; 602 continue; 603 } 604 605 SUnit *FoundSUnit = AvailableQueue.pop(); 606 607 // If we found a node to schedule, do it now. 608 if (FoundSUnit) { 609 ScheduleNodeTopDown(FoundSUnit, CurCycle); 610 611 // If this is a pseudo-op node, we don't want to increment the current 612 // cycle. 613 if (FoundSUnit->Latency) // Don't increment CurCycle for pseudo-ops! 614 ++CurCycle; 615 } else { 616 // Otherwise, we have a pipeline stall, but no other problem, just advance 617 // the current cycle and try again. 618 DOUT << "*** Advancing cycle, no work to do\n"; 619 ++NumStalls; 620 ++CurCycle; 621 } 622 } 623 624#ifndef NDEBUG 625 VerifySchedule(/*isBottomUp=*/false); 626#endif 627} 628 629//===----------------------------------------------------------------------===// 630// Public Constructor Functions 631//===----------------------------------------------------------------------===// 632 633FunctionPass *llvm::createPostRAScheduler() { 634 return new PostRAScheduler(); 635} 636