PostRASchedulerList.cpp revision 37cc9be77ec9c314c58336101cd1abe730bf5440
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 // Only consider anti-dependence edges. 199 if (!Edge->isAntiDep) 200 continue; 201 assert(AntiDepReg != 0 && "Anti-dependence on reg0?"); 202 // Don't break anti-dependencies on non-allocatable registers. 203 if (!AllocatableSet.test(AntiDepReg)) 204 continue; 205 // If the SUnit has other dependencies on the SUnit that it 206 // anti-depends on, don't bother breaking the anti-dependency. 207 // Also, if there are dependencies on other SUnits with the 208 // same register as the anti-dependency, don't attempt to 209 // break it. 210 for (SUnit::pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end(); 211 P != PE; ++P) 212 if (P->Dep == NextSU ? 213 (!P->isAntiDep || P->Reg != AntiDepReg) : 214 (!P->isCtrl && !P->isAntiDep && P->Reg == AntiDepReg)) { 215 AntiDepReg = 0; 216 break; 217 } 218 if (AntiDepReg != 0) 219 CriticalAntiDeps[SU->getInstr()] = AntiDepReg; 220 } 221 222 // For live regs that are only used in one register class in a live range, 223 // the register class. If the register is not live or is referenced in 224 // multiple register classes, the corresponding value is null. If the 225 // register is used in multiple register classes, the corresponding value 226 // is -1 casted to a pointer. 227 const TargetRegisterClass * 228 Classes[TargetRegisterInfo::FirstVirtualRegister] = {}; 229 230 // Map registers to all their references within a live range. 231 std::multimap<unsigned, MachineOperand *> RegRefs; 232 233 // The index of the most recent kill (proceding bottom-up), or -1 if 234 // the register is not live. 235 unsigned KillIndices[TargetRegisterInfo::FirstVirtualRegister]; 236 std::fill(KillIndices, array_endof(KillIndices), -1); 237 // The index of the most recent def (proceding bottom up), or -1 if 238 // the register is live. 239 unsigned DefIndices[TargetRegisterInfo::FirstVirtualRegister]; 240 std::fill(DefIndices, array_endof(DefIndices), BB->size()); 241 242 // Determine the live-out physregs for this block. 243 if (!BB->empty() && BB->back().getDesc().isReturn()) 244 // In a return block, examine the function live-out regs. 245 for (MachineRegisterInfo::liveout_iterator I = MRI.liveout_begin(), 246 E = MRI.liveout_end(); I != E; ++I) { 247 unsigned Reg = *I; 248 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 249 KillIndices[Reg] = BB->size(); 250 DefIndices[Reg] = -1; 251 // Repeat, for all aliases. 252 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 253 unsigned AliasReg = *Alias; 254 Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1); 255 KillIndices[AliasReg] = BB->size(); 256 DefIndices[AliasReg] = -1; 257 } 258 } 259 else 260 // In a non-return block, examine the live-in regs of all successors. 261 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 262 SE = BB->succ_end(); SI != SE; ++SI) 263 for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(), 264 E = (*SI)->livein_end(); I != E; ++I) { 265 unsigned Reg = *I; 266 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 267 KillIndices[Reg] = BB->size(); 268 DefIndices[Reg] = -1; 269 // Repeat, for all aliases. 270 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 271 unsigned AliasReg = *Alias; 272 Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1); 273 KillIndices[AliasReg] = BB->size(); 274 DefIndices[AliasReg] = -1; 275 } 276 } 277 278 // Consider callee-saved registers as live-out, since we're running after 279 // prologue/epilogue insertion so there's no way to add additional 280 // saved registers. 281 // 282 // TODO: If the callee saves and restores these, then we can potentially 283 // use them between the save and the restore. To do that, we could scan 284 // the exit blocks to see which of these registers are defined. 285 // Alternatively, calle-saved registers that aren't saved and restored 286 // could be marked live-in in every block. 287 for (const unsigned *I = TRI->getCalleeSavedRegs(); *I; ++I) { 288 unsigned Reg = *I; 289 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 290 KillIndices[Reg] = BB->size(); 291 DefIndices[Reg] = -1; 292 // Repeat, for all aliases. 293 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 294 unsigned AliasReg = *Alias; 295 Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1); 296 KillIndices[AliasReg] = BB->size(); 297 DefIndices[AliasReg] = -1; 298 } 299 } 300 301 // Consider this pattern: 302 // A = ... 303 // ... = A 304 // A = ... 305 // ... = A 306 // A = ... 307 // ... = A 308 // A = ... 309 // ... = A 310 // There are three anti-dependencies here, and without special care, 311 // we'd break all of them using the same register: 312 // A = ... 313 // ... = A 314 // B = ... 315 // ... = B 316 // B = ... 317 // ... = B 318 // B = ... 319 // ... = B 320 // because at each anti-dependence, B is the first register that 321 // isn't A which is free. This re-introduces anti-dependencies 322 // at all but one of the original anti-dependencies that we were 323 // trying to break. To avoid this, keep track of the most recent 324 // register that each register was replaced with, avoid avoid 325 // using it to repair an anti-dependence on the same register. 326 // This lets us produce this: 327 // A = ... 328 // ... = A 329 // B = ... 330 // ... = B 331 // C = ... 332 // ... = C 333 // B = ... 334 // ... = B 335 // This still has an anti-dependence on B, but at least it isn't on the 336 // original critical path. 337 // 338 // TODO: If we tracked more than one register here, we could potentially 339 // fix that remaining critical edge too. This is a little more involved, 340 // because unlike the most recent register, less recent registers should 341 // still be considered, though only if no other registers are available. 342 unsigned LastNewReg[TargetRegisterInfo::FirstVirtualRegister] = {}; 343 344 // A registers defined and not used in an instruction. This is used for 345 // liveness tracking and is declared outside the loop only to avoid 346 // having it be re-allocated on each iteration. 347 DenseSet<unsigned> Defs; 348 349 // Attempt to break anti-dependence edges on the critical path. Walk the 350 // instructions from the bottom up, tracking information about liveness 351 // as we go to help determine which registers are available. 352 bool Changed = false; 353 unsigned Count = BB->size() - 1; 354 for (MachineBasicBlock::reverse_iterator I = BB->rbegin(), E = BB->rend(); 355 I != E; ++I, --Count) { 356 MachineInstr *MI = &*I; 357 358 // Check if this instruction has an anti-dependence that we're 359 // interested in. 360 DenseMap<MachineInstr *, unsigned>::iterator C = CriticalAntiDeps.find(MI); 361 unsigned AntiDepReg = C != CriticalAntiDeps.end() ? 362 C->second : 0; 363 364 // Scan the register operands for this instruction and update 365 // Classes and RegRefs. 366 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 367 MachineOperand &MO = MI->getOperand(i); 368 if (!MO.isReg()) continue; 369 unsigned Reg = MO.getReg(); 370 if (Reg == 0) continue; 371 const TargetRegisterClass *NewRC = 372 getInstrOperandRegClass(TRI, TII, MI->getDesc(), i); 373 374 // If this instruction has a use of AntiDepReg, breaking it 375 // is invalid. 376 if (MO.isUse() && AntiDepReg == Reg) 377 AntiDepReg = 0; 378 379 // For now, only allow the register to be changed if its register 380 // class is consistent across all uses. 381 if (!Classes[Reg] && NewRC) 382 Classes[Reg] = NewRC; 383 else if (!NewRC || Classes[Reg] != NewRC) 384 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 385 386 // Now check for aliases. 387 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 388 // If an alias of the reg is used during the live range, give up. 389 // Note that this allows us to skip checking if AntiDepReg 390 // overlaps with any of the aliases, among other things. 391 unsigned AliasReg = *Alias; 392 if (Classes[AliasReg]) { 393 Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1); 394 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 395 } 396 } 397 398 // If we're still willing to consider this register, note the reference. 399 if (Classes[Reg] != reinterpret_cast<TargetRegisterClass *>(-1)) 400 RegRefs.insert(std::make_pair(Reg, &MO)); 401 } 402 403 // Determine AntiDepReg's register class, if it is live and is 404 // consistently used within a single class. 405 const TargetRegisterClass *RC = AntiDepReg != 0 ? Classes[AntiDepReg] : 0; 406 assert((AntiDepReg == 0 || RC != NULL) && 407 "Register should be live if it's causing an anti-dependence!"); 408 if (RC == reinterpret_cast<TargetRegisterClass *>(-1)) 409 AntiDepReg = 0; 410 411 // Look for a suitable register to use to break the anti-depenence. 412 // 413 // TODO: Instead of picking the first free register, consider which might 414 // be the best. 415 if (AntiDepReg != 0) { 416 for (TargetRegisterClass::iterator R = RC->allocation_order_begin(*MF), 417 RE = RC->allocation_order_end(*MF); R != RE; ++R) { 418 unsigned NewReg = *R; 419 // Don't replace a register with itself. 420 if (NewReg == AntiDepReg) continue; 421 // Don't replace a register with one that was recently used to repair 422 // an anti-dependence with this AntiDepReg, because that would 423 // re-introduce that anti-dependence. 424 if (NewReg == LastNewReg[AntiDepReg]) continue; 425 // If NewReg is dead and NewReg's most recent def is not before 426 // AntiDepReg's kill, it's safe to replace AntiDepReg with NewReg. 427 assert(((KillIndices[AntiDepReg] == -1u) != (DefIndices[AntiDepReg] == -1u)) && 428 "Kill and Def maps aren't consistent for AntiDepReg!"); 429 assert(((KillIndices[NewReg] == -1u) != (DefIndices[NewReg] == -1u)) && 430 "Kill and Def maps aren't consistent for NewReg!"); 431 if (KillIndices[NewReg] == -1u && 432 KillIndices[AntiDepReg] <= DefIndices[NewReg]) { 433 DOUT << "Breaking anti-dependence edge on reg " << AntiDepReg 434 << " with reg " << NewReg << "!\n"; 435 436 // Update the references to the old register to refer to the new 437 // register. 438 std::pair<std::multimap<unsigned, MachineOperand *>::iterator, 439 std::multimap<unsigned, MachineOperand *>::iterator> 440 Range = RegRefs.equal_range(AntiDepReg); 441 for (std::multimap<unsigned, MachineOperand *>::iterator 442 Q = Range.first, QE = Range.second; Q != QE; ++Q) 443 Q->second->setReg(NewReg); 444 445 // We just went back in time and modified history; the 446 // liveness information for the anti-depenence reg is now 447 // inconsistent. Set the state as if it were dead. 448 Classes[NewReg] = Classes[AntiDepReg]; 449 DefIndices[NewReg] = DefIndices[AntiDepReg]; 450 KillIndices[NewReg] = KillIndices[AntiDepReg]; 451 452 Classes[AntiDepReg] = 0; 453 DefIndices[AntiDepReg] = KillIndices[AntiDepReg]; 454 KillIndices[AntiDepReg] = -1; 455 456 RegRefs.erase(AntiDepReg); 457 Changed = true; 458 LastNewReg[AntiDepReg] = NewReg; 459 break; 460 } 461 } 462 } 463 464 // Update liveness. 465 Defs.clear(); 466 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 467 MachineOperand &MO = MI->getOperand(i); 468 if (!MO.isReg()) continue; 469 unsigned Reg = MO.getReg(); 470 if (Reg == 0) continue; 471 if (MO.isDef()) 472 Defs.insert(Reg); 473 else { 474 // Treat a use in the same instruction as a def as an extension of 475 // a live range. 476 Defs.erase(Reg); 477 // It wasn't previously live but now it is, this is a kill. 478 if (KillIndices[Reg] == -1u) { 479 KillIndices[Reg] = Count; 480 DefIndices[Reg] = -1u; 481 } 482 // Repeat, for all aliases. 483 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 484 unsigned AliasReg = *Alias; 485 Defs.erase(AliasReg); 486 if (KillIndices[AliasReg] == -1u) { 487 KillIndices[AliasReg] = Count; 488 DefIndices[AliasReg] = -1u; 489 } 490 } 491 } 492 } 493 // Proceding upwards, registers that are defed but not used in this 494 // instruction are now dead. 495 for (DenseSet<unsigned>::iterator D = Defs.begin(), DE = Defs.end(); 496 D != DE; ++D) { 497 unsigned Reg = *D; 498 DefIndices[Reg] = Count; 499 KillIndices[Reg] = -1; 500 Classes[Reg] = 0; 501 RegRefs.erase(Reg); 502 // Repeat, for all subregs. 503 for (const unsigned *Subreg = TRI->getSubRegisters(Reg); 504 *Subreg; ++Subreg) { 505 unsigned SubregReg = *Subreg; 506 DefIndices[SubregReg] = Count; 507 KillIndices[SubregReg] = -1; 508 Classes[SubregReg] = 0; 509 RegRefs.erase(SubregReg); 510 } 511 } 512 } 513 assert(Count == -1u && "Count mismatch!"); 514 515 return Changed; 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, SUnit *SuccSU, bool isChain) { 525 --SuccSU->NumPredsLeft; 526 527#ifndef NDEBUG 528 if (SuccSU->NumPredsLeft < 0) { 529 cerr << "*** Scheduling failed! ***\n"; 530 SuccSU->dump(this); 531 cerr << " has been released too many times!\n"; 532 assert(0); 533 } 534#endif 535 536 // Compute how many cycles it will be before this actually becomes 537 // available. This is the max of the start time of all predecessors plus 538 // their latencies. 539 // If this is a token edge, we don't need to wait for the latency of the 540 // preceeding instruction (e.g. a long-latency load) unless there is also 541 // some other data dependence. 542 unsigned PredDoneCycle = SU->Cycle; 543 if (!isChain) 544 PredDoneCycle += SU->Latency; 545 else if (SU->Latency) 546 PredDoneCycle += 1; 547 SuccSU->CycleBound = std::max(SuccSU->CycleBound, PredDoneCycle); 548 549 if (SuccSU->NumPredsLeft == 0) { 550 PendingQueue.push_back(SuccSU); 551 } 552} 553 554/// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending 555/// count of its successors. If a successor pending count is zero, add it to 556/// the Available queue. 557void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { 558 DOUT << "*** Scheduling [" << CurCycle << "]: "; 559 DEBUG(SU->dump(this)); 560 561 Sequence.push_back(SU); 562 SU->Cycle = CurCycle; 563 564 // Top down: release successors. 565 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 566 I != E; ++I) 567 ReleaseSucc(SU, I->Dep, I->isCtrl); 568 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 // All leaves to Available queue. 579 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 580 // It is available if it has no predecessors. 581 if (SUnits[i].Preds.empty()) { 582 AvailableQueue.push(&SUnits[i]); 583 SUnits[i].isAvailable = true; 584 } 585 } 586 587 // While Available queue is not empty, grab the node with the highest 588 // priority. If it is not ready put it back. Schedule the node. 589 Sequence.reserve(SUnits.size()); 590 while (!AvailableQueue.empty() || !PendingQueue.empty()) { 591 // Check to see if any of the pending instructions are ready to issue. If 592 // so, add them to the available queue. 593 for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) { 594 if (PendingQueue[i]->CycleBound == CurCycle) { 595 AvailableQueue.push(PendingQueue[i]); 596 PendingQueue[i]->isAvailable = true; 597 PendingQueue[i] = PendingQueue.back(); 598 PendingQueue.pop_back(); 599 --i; --e; 600 } else { 601 assert(PendingQueue[i]->CycleBound > CurCycle && "Negative latency?"); 602 } 603 } 604 605 // If there are no instructions available, don't try to issue anything. 606 if (AvailableQueue.empty()) { 607 ++CurCycle; 608 continue; 609 } 610 611 SUnit *FoundSUnit = AvailableQueue.pop(); 612 613 // If we found a node to schedule, do it now. 614 if (FoundSUnit) { 615 ScheduleNodeTopDown(FoundSUnit, CurCycle); 616 617 // If this is a pseudo-op node, we don't want to increment the current 618 // cycle. 619 if (FoundSUnit->Latency) // Don't increment CurCycle for pseudo-ops! 620 ++CurCycle; 621 } else { 622 // Otherwise, we have a pipeline stall, but no other problem, just advance 623 // the current cycle and try again. 624 DOUT << "*** Advancing cycle, no work to do\n"; 625 ++NumStalls; 626 ++CurCycle; 627 } 628 } 629 630#ifndef NDEBUG 631 VerifySchedule(/*isBottomUp=*/false); 632#endif 633} 634 635//===----------------------------------------------------------------------===// 636// Public Constructor Functions 637//===----------------------------------------------------------------------===// 638 639FunctionPass *llvm::createPostRAScheduler() { 640 return new PostRAScheduler(); 641} 642