ResourcePriorityQueue.cpp revision 263508
1//===- ResourcePriorityQueue.cpp - A DFA-oriented priority queue -*- C++ -*-==// 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 file implements the ResourcePriorityQueue class, which is a 11// SchedulingPriorityQueue that prioritizes instructions using DFA state to 12// reduce the length of the critical path through the basic block 13// on VLIW platforms. 14// The scheduler is basically a top-down adaptable list scheduler with DFA 15// resource tracking added to the cost function. 16// DFA is queried as a state machine to model "packets/bundles" during 17// schedule. Currently packets/bundles are discarded at the end of 18// scheduling, affecting only order of instructions. 19// 20//===----------------------------------------------------------------------===// 21 22#define DEBUG_TYPE "scheduler" 23#include "llvm/CodeGen/ResourcePriorityQueue.h" 24#include "llvm/CodeGen/MachineInstr.h" 25#include "llvm/CodeGen/SelectionDAGNodes.h" 26#include "llvm/Support/CommandLine.h" 27#include "llvm/Support/Debug.h" 28#include "llvm/Support/raw_ostream.h" 29#include "llvm/Target/TargetLowering.h" 30#include "llvm/Target/TargetMachine.h" 31 32using namespace llvm; 33 34static cl::opt<bool> DisableDFASched("disable-dfa-sched", cl::Hidden, 35 cl::ZeroOrMore, cl::init(false), 36 cl::desc("Disable use of DFA during scheduling")); 37 38static cl::opt<signed> RegPressureThreshold( 39 "dfa-sched-reg-pressure-threshold", cl::Hidden, cl::ZeroOrMore, cl::init(5), 40 cl::desc("Track reg pressure and switch priority to in-depth")); 41 42 43ResourcePriorityQueue::ResourcePriorityQueue(SelectionDAGISel *IS) : 44 Picker(this), 45 InstrItins(IS->getTargetLowering()->getTargetMachine().getInstrItineraryData()) 46{ 47 TII = IS->getTargetLowering()->getTargetMachine().getInstrInfo(); 48 TRI = IS->getTargetLowering()->getTargetMachine().getRegisterInfo(); 49 TLI = IS->getTargetLowering(); 50 51 const TargetMachine &tm = (*IS->MF).getTarget(); 52 ResourcesModel = tm.getInstrInfo()->CreateTargetScheduleState(&tm,NULL); 53 // This hard requirement could be relaxed, but for now 54 // do not let it procede. 55 assert (ResourcesModel && "Unimplemented CreateTargetScheduleState."); 56 57 unsigned NumRC = TRI->getNumRegClasses(); 58 RegLimit.resize(NumRC); 59 RegPressure.resize(NumRC); 60 std::fill(RegLimit.begin(), RegLimit.end(), 0); 61 std::fill(RegPressure.begin(), RegPressure.end(), 0); 62 for (TargetRegisterInfo::regclass_iterator I = TRI->regclass_begin(), 63 E = TRI->regclass_end(); I != E; ++I) 64 RegLimit[(*I)->getID()] = TRI->getRegPressureLimit(*I, *IS->MF); 65 66 ParallelLiveRanges = 0; 67 HorizontalVerticalBalance = 0; 68} 69 70unsigned 71ResourcePriorityQueue::numberRCValPredInSU(SUnit *SU, unsigned RCId) { 72 unsigned NumberDeps = 0; 73 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 74 I != E; ++I) { 75 if (I->isCtrl()) 76 continue; 77 78 SUnit *PredSU = I->getSUnit(); 79 const SDNode *ScegN = PredSU->getNode(); 80 81 if (!ScegN) 82 continue; 83 84 // If value is passed to CopyToReg, it is probably 85 // live outside BB. 86 switch (ScegN->getOpcode()) { 87 default: break; 88 case ISD::TokenFactor: break; 89 case ISD::CopyFromReg: NumberDeps++; break; 90 case ISD::CopyToReg: break; 91 case ISD::INLINEASM: break; 92 } 93 if (!ScegN->isMachineOpcode()) 94 continue; 95 96 for (unsigned i = 0, e = ScegN->getNumValues(); i != e; ++i) { 97 MVT VT = ScegN->getSimpleValueType(i); 98 if (TLI->isTypeLegal(VT) 99 && (TLI->getRegClassFor(VT)->getID() == RCId)) { 100 NumberDeps++; 101 break; 102 } 103 } 104 } 105 return NumberDeps; 106} 107 108unsigned ResourcePriorityQueue::numberRCValSuccInSU(SUnit *SU, 109 unsigned RCId) { 110 unsigned NumberDeps = 0; 111 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 112 I != E; ++I) { 113 if (I->isCtrl()) 114 continue; 115 116 SUnit *SuccSU = I->getSUnit(); 117 const SDNode *ScegN = SuccSU->getNode(); 118 if (!ScegN) 119 continue; 120 121 // If value is passed to CopyToReg, it is probably 122 // live outside BB. 123 switch (ScegN->getOpcode()) { 124 default: break; 125 case ISD::TokenFactor: break; 126 case ISD::CopyFromReg: break; 127 case ISD::CopyToReg: NumberDeps++; break; 128 case ISD::INLINEASM: break; 129 } 130 if (!ScegN->isMachineOpcode()) 131 continue; 132 133 for (unsigned i = 0, e = ScegN->getNumOperands(); i != e; ++i) { 134 const SDValue &Op = ScegN->getOperand(i); 135 MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo()); 136 if (TLI->isTypeLegal(VT) 137 && (TLI->getRegClassFor(VT)->getID() == RCId)) { 138 NumberDeps++; 139 break; 140 } 141 } 142 } 143 return NumberDeps; 144} 145 146static unsigned numberCtrlDepsInSU(SUnit *SU) { 147 unsigned NumberDeps = 0; 148 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 149 I != E; ++I) 150 if (I->isCtrl()) 151 NumberDeps++; 152 153 return NumberDeps; 154} 155 156static unsigned numberCtrlPredInSU(SUnit *SU) { 157 unsigned NumberDeps = 0; 158 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 159 I != E; ++I) 160 if (I->isCtrl()) 161 NumberDeps++; 162 163 return NumberDeps; 164} 165 166/// 167/// Initialize nodes. 168/// 169void ResourcePriorityQueue::initNodes(std::vector<SUnit> &sunits) { 170 SUnits = &sunits; 171 NumNodesSolelyBlocking.resize(SUnits->size(), 0); 172 173 for (unsigned i = 0, e = SUnits->size(); i != e; ++i) { 174 SUnit *SU = &(*SUnits)[i]; 175 initNumRegDefsLeft(SU); 176 SU->NodeQueueId = 0; 177 } 178} 179 180/// This heuristic is used if DFA scheduling is not desired 181/// for some VLIW platform. 182bool resource_sort::operator()(const SUnit *LHS, const SUnit *RHS) const { 183 // The isScheduleHigh flag allows nodes with wraparound dependencies that 184 // cannot easily be modeled as edges with latencies to be scheduled as 185 // soon as possible in a top-down schedule. 186 if (LHS->isScheduleHigh && !RHS->isScheduleHigh) 187 return false; 188 189 if (!LHS->isScheduleHigh && RHS->isScheduleHigh) 190 return true; 191 192 unsigned LHSNum = LHS->NodeNum; 193 unsigned RHSNum = RHS->NodeNum; 194 195 // The most important heuristic is scheduling the critical path. 196 unsigned LHSLatency = PQ->getLatency(LHSNum); 197 unsigned RHSLatency = PQ->getLatency(RHSNum); 198 if (LHSLatency < RHSLatency) return true; 199 if (LHSLatency > RHSLatency) return false; 200 201 // After that, if two nodes have identical latencies, look to see if one will 202 // unblock more other nodes than the other. 203 unsigned LHSBlocked = PQ->getNumSolelyBlockNodes(LHSNum); 204 unsigned RHSBlocked = PQ->getNumSolelyBlockNodes(RHSNum); 205 if (LHSBlocked < RHSBlocked) return true; 206 if (LHSBlocked > RHSBlocked) return false; 207 208 // Finally, just to provide a stable ordering, use the node number as a 209 // deciding factor. 210 return LHSNum < RHSNum; 211} 212 213 214/// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor 215/// of SU, return it, otherwise return null. 216SUnit *ResourcePriorityQueue::getSingleUnscheduledPred(SUnit *SU) { 217 SUnit *OnlyAvailablePred = 0; 218 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 219 I != E; ++I) { 220 SUnit &Pred = *I->getSUnit(); 221 if (!Pred.isScheduled) { 222 // We found an available, but not scheduled, predecessor. If it's the 223 // only one we have found, keep track of it... otherwise give up. 224 if (OnlyAvailablePred && OnlyAvailablePred != &Pred) 225 return 0; 226 OnlyAvailablePred = &Pred; 227 } 228 } 229 return OnlyAvailablePred; 230} 231 232void ResourcePriorityQueue::push(SUnit *SU) { 233 // Look at all of the successors of this node. Count the number of nodes that 234 // this node is the sole unscheduled node for. 235 unsigned NumNodesBlocking = 0; 236 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 237 I != E; ++I) 238 if (getSingleUnscheduledPred(I->getSUnit()) == SU) 239 ++NumNodesBlocking; 240 241 NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking; 242 Queue.push_back(SU); 243} 244 245/// Check if scheduling of this SU is possible 246/// in the current packet. 247bool ResourcePriorityQueue::isResourceAvailable(SUnit *SU) { 248 if (!SU || !SU->getNode()) 249 return false; 250 251 // If this is a compound instruction, 252 // it is likely to be a call. Do not delay it. 253 if (SU->getNode()->getGluedNode()) 254 return true; 255 256 // First see if the pipeline could receive this instruction 257 // in the current cycle. 258 if (SU->getNode()->isMachineOpcode()) 259 switch (SU->getNode()->getMachineOpcode()) { 260 default: 261 if (!ResourcesModel->canReserveResources(&TII->get( 262 SU->getNode()->getMachineOpcode()))) 263 return false; 264 case TargetOpcode::EXTRACT_SUBREG: 265 case TargetOpcode::INSERT_SUBREG: 266 case TargetOpcode::SUBREG_TO_REG: 267 case TargetOpcode::REG_SEQUENCE: 268 case TargetOpcode::IMPLICIT_DEF: 269 break; 270 } 271 272 // Now see if there are no other dependencies 273 // to instructions alredy in the packet. 274 for (unsigned i = 0, e = Packet.size(); i != e; ++i) 275 for (SUnit::const_succ_iterator I = Packet[i]->Succs.begin(), 276 E = Packet[i]->Succs.end(); I != E; ++I) { 277 // Since we do not add pseudos to packets, might as well 278 // ignor order deps. 279 if (I->isCtrl()) 280 continue; 281 282 if (I->getSUnit() == SU) 283 return false; 284 } 285 286 return true; 287} 288 289/// Keep track of available resources. 290void ResourcePriorityQueue::reserveResources(SUnit *SU) { 291 // If this SU does not fit in the packet 292 // start a new one. 293 if (!isResourceAvailable(SU) || SU->getNode()->getGluedNode()) { 294 ResourcesModel->clearResources(); 295 Packet.clear(); 296 } 297 298 if (SU->getNode() && SU->getNode()->isMachineOpcode()) { 299 switch (SU->getNode()->getMachineOpcode()) { 300 default: 301 ResourcesModel->reserveResources(&TII->get( 302 SU->getNode()->getMachineOpcode())); 303 break; 304 case TargetOpcode::EXTRACT_SUBREG: 305 case TargetOpcode::INSERT_SUBREG: 306 case TargetOpcode::SUBREG_TO_REG: 307 case TargetOpcode::REG_SEQUENCE: 308 case TargetOpcode::IMPLICIT_DEF: 309 break; 310 } 311 Packet.push_back(SU); 312 } 313 // Forcefully end packet for PseudoOps. 314 else { 315 ResourcesModel->clearResources(); 316 Packet.clear(); 317 } 318 319 // If packet is now full, reset the state so in the next cycle 320 // we start fresh. 321 if (Packet.size() >= InstrItins->SchedModel->IssueWidth) { 322 ResourcesModel->clearResources(); 323 Packet.clear(); 324 } 325} 326 327signed ResourcePriorityQueue::rawRegPressureDelta(SUnit *SU, unsigned RCId) { 328 signed RegBalance = 0; 329 330 if (!SU || !SU->getNode() || !SU->getNode()->isMachineOpcode()) 331 return RegBalance; 332 333 // Gen estimate. 334 for (unsigned i = 0, e = SU->getNode()->getNumValues(); i != e; ++i) { 335 MVT VT = SU->getNode()->getSimpleValueType(i); 336 if (TLI->isTypeLegal(VT) 337 && TLI->getRegClassFor(VT) 338 && TLI->getRegClassFor(VT)->getID() == RCId) 339 RegBalance += numberRCValSuccInSU(SU, RCId); 340 } 341 // Kill estimate. 342 for (unsigned i = 0, e = SU->getNode()->getNumOperands(); i != e; ++i) { 343 const SDValue &Op = SU->getNode()->getOperand(i); 344 MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo()); 345 if (isa<ConstantSDNode>(Op.getNode())) 346 continue; 347 348 if (TLI->isTypeLegal(VT) && TLI->getRegClassFor(VT) 349 && TLI->getRegClassFor(VT)->getID() == RCId) 350 RegBalance -= numberRCValPredInSU(SU, RCId); 351 } 352 return RegBalance; 353} 354 355/// Estimates change in reg pressure from this SU. 356/// It is achieved by trivial tracking of defined 357/// and used vregs in dependent instructions. 358/// The RawPressure flag makes this function to ignore 359/// existing reg file sizes, and report raw def/use 360/// balance. 361signed ResourcePriorityQueue::regPressureDelta(SUnit *SU, bool RawPressure) { 362 signed RegBalance = 0; 363 364 if (!SU || !SU->getNode() || !SU->getNode()->isMachineOpcode()) 365 return RegBalance; 366 367 if (RawPressure) { 368 for (TargetRegisterInfo::regclass_iterator I = TRI->regclass_begin(), 369 E = TRI->regclass_end(); I != E; ++I) { 370 const TargetRegisterClass *RC = *I; 371 RegBalance += rawRegPressureDelta(SU, RC->getID()); 372 } 373 } 374 else { 375 for (TargetRegisterInfo::regclass_iterator I = TRI->regclass_begin(), 376 E = TRI->regclass_end(); I != E; ++I) { 377 const TargetRegisterClass *RC = *I; 378 if ((RegPressure[RC->getID()] + 379 rawRegPressureDelta(SU, RC->getID()) > 0) && 380 (RegPressure[RC->getID()] + 381 rawRegPressureDelta(SU, RC->getID()) >= RegLimit[RC->getID()])) 382 RegBalance += rawRegPressureDelta(SU, RC->getID()); 383 } 384 } 385 386 return RegBalance; 387} 388 389// Constants used to denote relative importance of 390// heuristic components for cost computation. 391static const unsigned PriorityOne = 200; 392static const unsigned PriorityTwo = 50; 393static const unsigned PriorityThree = 15; 394static const unsigned PriorityFour = 5; 395static const unsigned ScaleOne = 20; 396static const unsigned ScaleTwo = 10; 397static const unsigned ScaleThree = 5; 398static const unsigned FactorOne = 2; 399 400/// Returns single number reflecting benefit of scheduling SU 401/// in the current cycle. 402signed ResourcePriorityQueue::SUSchedulingCost(SUnit *SU) { 403 // Initial trivial priority. 404 signed ResCount = 1; 405 406 // Do not waste time on a node that is already scheduled. 407 if (SU->isScheduled) 408 return ResCount; 409 410 // Forced priority is high. 411 if (SU->isScheduleHigh) 412 ResCount += PriorityOne; 413 414 // Adaptable scheduling 415 // A small, but very parallel 416 // region, where reg pressure is an issue. 417 if (HorizontalVerticalBalance > RegPressureThreshold) { 418 // Critical path first 419 ResCount += (SU->getHeight() * ScaleTwo); 420 // If resources are available for it, multiply the 421 // chance of scheduling. 422 if (isResourceAvailable(SU)) 423 ResCount <<= FactorOne; 424 425 // Consider change to reg pressure from scheduling 426 // this SU. 427 ResCount -= (regPressureDelta(SU,true) * ScaleOne); 428 } 429 // Default heuristic, greeady and 430 // critical path driven. 431 else { 432 // Critical path first. 433 ResCount += (SU->getHeight() * ScaleTwo); 434 // Now see how many instructions is blocked by this SU. 435 ResCount += (NumNodesSolelyBlocking[SU->NodeNum] * ScaleTwo); 436 // If resources are available for it, multiply the 437 // chance of scheduling. 438 if (isResourceAvailable(SU)) 439 ResCount <<= FactorOne; 440 441 ResCount -= (regPressureDelta(SU) * ScaleTwo); 442 } 443 444 // These are platform specific things. 445 // Will need to go into the back end 446 // and accessed from here via a hook. 447 for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) { 448 if (N->isMachineOpcode()) { 449 const MCInstrDesc &TID = TII->get(N->getMachineOpcode()); 450 if (TID.isCall()) 451 ResCount += (PriorityTwo + (ScaleThree*N->getNumValues())); 452 } 453 else 454 switch (N->getOpcode()) { 455 default: break; 456 case ISD::TokenFactor: 457 case ISD::CopyFromReg: 458 case ISD::CopyToReg: 459 ResCount += PriorityFour; 460 break; 461 462 case ISD::INLINEASM: 463 ResCount += PriorityThree; 464 break; 465 } 466 } 467 return ResCount; 468} 469 470 471/// Main resource tracking point. 472void ResourcePriorityQueue::scheduledNode(SUnit *SU) { 473 // Use NULL entry as an event marker to reset 474 // the DFA state. 475 if (!SU) { 476 ResourcesModel->clearResources(); 477 Packet.clear(); 478 return; 479 } 480 481 const SDNode *ScegN = SU->getNode(); 482 // Update reg pressure tracking. 483 // First update current node. 484 if (ScegN->isMachineOpcode()) { 485 // Estimate generated regs. 486 for (unsigned i = 0, e = ScegN->getNumValues(); i != e; ++i) { 487 MVT VT = ScegN->getSimpleValueType(i); 488 489 if (TLI->isTypeLegal(VT)) { 490 const TargetRegisterClass *RC = TLI->getRegClassFor(VT); 491 if (RC) 492 RegPressure[RC->getID()] += numberRCValSuccInSU(SU, RC->getID()); 493 } 494 } 495 // Estimate killed regs. 496 for (unsigned i = 0, e = ScegN->getNumOperands(); i != e; ++i) { 497 const SDValue &Op = ScegN->getOperand(i); 498 MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo()); 499 500 if (TLI->isTypeLegal(VT)) { 501 const TargetRegisterClass *RC = TLI->getRegClassFor(VT); 502 if (RC) { 503 if (RegPressure[RC->getID()] > 504 (numberRCValPredInSU(SU, RC->getID()))) 505 RegPressure[RC->getID()] -= numberRCValPredInSU(SU, RC->getID()); 506 else RegPressure[RC->getID()] = 0; 507 } 508 } 509 } 510 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 511 I != E; ++I) { 512 if (I->isCtrl() || (I->getSUnit()->NumRegDefsLeft == 0)) 513 continue; 514 --I->getSUnit()->NumRegDefsLeft; 515 } 516 } 517 518 // Reserve resources for this SU. 519 reserveResources(SU); 520 521 // Adjust number of parallel live ranges. 522 // Heuristic is simple - node with no data successors reduces 523 // number of live ranges. All others, increase it. 524 unsigned NumberNonControlDeps = 0; 525 526 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 527 I != E; ++I) { 528 adjustPriorityOfUnscheduledPreds(I->getSUnit()); 529 if (!I->isCtrl()) 530 NumberNonControlDeps++; 531 } 532 533 if (!NumberNonControlDeps) { 534 if (ParallelLiveRanges >= SU->NumPreds) 535 ParallelLiveRanges -= SU->NumPreds; 536 else 537 ParallelLiveRanges = 0; 538 539 } 540 else 541 ParallelLiveRanges += SU->NumRegDefsLeft; 542 543 // Track parallel live chains. 544 HorizontalVerticalBalance += (SU->Succs.size() - numberCtrlDepsInSU(SU)); 545 HorizontalVerticalBalance -= (SU->Preds.size() - numberCtrlPredInSU(SU)); 546} 547 548void ResourcePriorityQueue::initNumRegDefsLeft(SUnit *SU) { 549 unsigned NodeNumDefs = 0; 550 for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) 551 if (N->isMachineOpcode()) { 552 const MCInstrDesc &TID = TII->get(N->getMachineOpcode()); 553 // No register need be allocated for this. 554 if (N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF) { 555 NodeNumDefs = 0; 556 break; 557 } 558 NodeNumDefs = std::min(N->getNumValues(), TID.getNumDefs()); 559 } 560 else 561 switch(N->getOpcode()) { 562 default: break; 563 case ISD::CopyFromReg: 564 NodeNumDefs++; 565 break; 566 case ISD::INLINEASM: 567 NodeNumDefs++; 568 break; 569 } 570 571 SU->NumRegDefsLeft = NodeNumDefs; 572} 573 574/// adjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just 575/// scheduled. If SU is not itself available, then there is at least one 576/// predecessor node that has not been scheduled yet. If SU has exactly ONE 577/// unscheduled predecessor, we want to increase its priority: it getting 578/// scheduled will make this node available, so it is better than some other 579/// node of the same priority that will not make a node available. 580void ResourcePriorityQueue::adjustPriorityOfUnscheduledPreds(SUnit *SU) { 581 if (SU->isAvailable) return; // All preds scheduled. 582 583 SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU); 584 if (OnlyAvailablePred == 0 || !OnlyAvailablePred->isAvailable) 585 return; 586 587 // Okay, we found a single predecessor that is available, but not scheduled. 588 // Since it is available, it must be in the priority queue. First remove it. 589 remove(OnlyAvailablePred); 590 591 // Reinsert the node into the priority queue, which recomputes its 592 // NumNodesSolelyBlocking value. 593 push(OnlyAvailablePred); 594} 595 596 597/// Main access point - returns next instructions 598/// to be placed in scheduling sequence. 599SUnit *ResourcePriorityQueue::pop() { 600 if (empty()) 601 return 0; 602 603 std::vector<SUnit *>::iterator Best = Queue.begin(); 604 if (!DisableDFASched) { 605 signed BestCost = SUSchedulingCost(*Best); 606 for (std::vector<SUnit *>::iterator I = llvm::next(Queue.begin()), 607 E = Queue.end(); I != E; ++I) { 608 609 if (SUSchedulingCost(*I) > BestCost) { 610 BestCost = SUSchedulingCost(*I); 611 Best = I; 612 } 613 } 614 } 615 // Use default TD scheduling mechanism. 616 else { 617 for (std::vector<SUnit *>::iterator I = llvm::next(Queue.begin()), 618 E = Queue.end(); I != E; ++I) 619 if (Picker(*Best, *I)) 620 Best = I; 621 } 622 623 SUnit *V = *Best; 624 if (Best != prior(Queue.end())) 625 std::swap(*Best, Queue.back()); 626 627 Queue.pop_back(); 628 629 return V; 630} 631 632 633void ResourcePriorityQueue::remove(SUnit *SU) { 634 assert(!Queue.empty() && "Queue is empty!"); 635 std::vector<SUnit *>::iterator I = std::find(Queue.begin(), Queue.end(), SU); 636 if (I != prior(Queue.end())) 637 std::swap(*I, Queue.back()); 638 639 Queue.pop_back(); 640} 641 642 643#ifdef NDEBUG 644void ResourcePriorityQueue::dump(ScheduleDAG *DAG) const {} 645#else 646void ResourcePriorityQueue::dump(ScheduleDAG *DAG) const { 647 ResourcePriorityQueue q = *this; 648 while (!q.empty()) { 649 SUnit *su = q.pop(); 650 dbgs() << "Height " << su->getHeight() << ": "; 651 su->dump(DAG); 652 } 653} 654#endif 655