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