1 //===- MachineScheduler.cpp - Machine Instruction 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 // MachineScheduler schedules machine instructions after phi elimination. It 11 // preserves LiveIntervals so it can be invoked before register allocation. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #define DEBUG_TYPE "misched" 16 17 #include "llvm/CodeGen/MachineScheduler.h" 18 #include "llvm/ADT/OwningPtr.h" 19 #include "llvm/ADT/PriorityQueue.h" 20 #include "llvm/Analysis/AliasAnalysis.h" 21 #include "llvm/CodeGen/LiveIntervalAnalysis.h" 22 #include "llvm/CodeGen/MachineDominators.h" 23 #include "llvm/CodeGen/MachineLoopInfo.h" 24 #include "llvm/CodeGen/Passes.h" 25 #include "llvm/CodeGen/RegisterClassInfo.h" 26 #include "llvm/CodeGen/ScheduleDFS.h" 27 #include "llvm/CodeGen/ScheduleHazardRecognizer.h" 28 #include "llvm/Support/CommandLine.h" 29 #include "llvm/Support/Debug.h" 30 #include "llvm/Support/ErrorHandling.h" 31 #include "llvm/Support/GraphWriter.h" 32 #include "llvm/Support/raw_ostream.h" 33 #include "llvm/Target/TargetInstrInfo.h" 34 #include <queue> 35 36 using namespace llvm; 37 38 namespace llvm { 39 cl::opt<bool> ForceTopDown("misched-topdown", cl::Hidden, 40 cl::desc("Force top-down list scheduling")); 41 cl::opt<bool> ForceBottomUp("misched-bottomup", cl::Hidden, 42 cl::desc("Force bottom-up list scheduling")); 43 } 44 45 #ifndef NDEBUG 46 static cl::opt<bool> ViewMISchedDAGs("view-misched-dags", cl::Hidden, 47 cl::desc("Pop up a window to show MISched dags after they are processed")); 48 49 static cl::opt<unsigned> MISchedCutoff("misched-cutoff", cl::Hidden, 50 cl::desc("Stop scheduling after N instructions"), cl::init(~0U)); 51 #else 52 static bool ViewMISchedDAGs = false; 53 #endif // NDEBUG 54 55 static cl::opt<bool> EnableLoadCluster("misched-cluster", cl::Hidden, 56 cl::desc("Enable load clustering."), cl::init(true)); 57 58 // Experimental heuristics 59 static cl::opt<bool> EnableMacroFusion("misched-fusion", cl::Hidden, 60 cl::desc("Enable scheduling for macro fusion."), cl::init(true)); 61 62 static cl::opt<bool> VerifyScheduling("verify-misched", cl::Hidden, 63 cl::desc("Verify machine instrs before and after machine scheduling")); 64 65 // DAG subtrees must have at least this many nodes. 66 static const unsigned MinSubtreeSize = 8; 67 68 //===----------------------------------------------------------------------===// 69 // Machine Instruction Scheduling Pass and Registry 70 //===----------------------------------------------------------------------===// 71 72 MachineSchedContext::MachineSchedContext(): 73 MF(0), MLI(0), MDT(0), PassConfig(0), AA(0), LIS(0) { 74 RegClassInfo = new RegisterClassInfo(); 75 } 76 77 MachineSchedContext::~MachineSchedContext() { 78 delete RegClassInfo; 79 } 80 81 namespace { 82 /// MachineScheduler runs after coalescing and before register allocation. 83 class MachineScheduler : public MachineSchedContext, 84 public MachineFunctionPass { 85 public: 86 MachineScheduler(); 87 88 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 89 90 virtual void releaseMemory() {} 91 92 virtual bool runOnMachineFunction(MachineFunction&); 93 94 virtual void print(raw_ostream &O, const Module* = 0) const; 95 96 static char ID; // Class identification, replacement for typeinfo 97 }; 98 } // namespace 99 100 char MachineScheduler::ID = 0; 101 102 char &llvm::MachineSchedulerID = MachineScheduler::ID; 103 104 INITIALIZE_PASS_BEGIN(MachineScheduler, "misched", 105 "Machine Instruction Scheduler", false, false) 106 INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 107 INITIALIZE_PASS_DEPENDENCY(SlotIndexes) 108 INITIALIZE_PASS_DEPENDENCY(LiveIntervals) 109 INITIALIZE_PASS_END(MachineScheduler, "misched", 110 "Machine Instruction Scheduler", false, false) 111 112 MachineScheduler::MachineScheduler() 113 : MachineFunctionPass(ID) { 114 initializeMachineSchedulerPass(*PassRegistry::getPassRegistry()); 115 } 116 117 void MachineScheduler::getAnalysisUsage(AnalysisUsage &AU) const { 118 AU.setPreservesCFG(); 119 AU.addRequiredID(MachineDominatorsID); 120 AU.addRequired<MachineLoopInfo>(); 121 AU.addRequired<AliasAnalysis>(); 122 AU.addRequired<TargetPassConfig>(); 123 AU.addRequired<SlotIndexes>(); 124 AU.addPreserved<SlotIndexes>(); 125 AU.addRequired<LiveIntervals>(); 126 AU.addPreserved<LiveIntervals>(); 127 MachineFunctionPass::getAnalysisUsage(AU); 128 } 129 130 MachinePassRegistry MachineSchedRegistry::Registry; 131 132 /// A dummy default scheduler factory indicates whether the scheduler 133 /// is overridden on the command line. 134 static ScheduleDAGInstrs *useDefaultMachineSched(MachineSchedContext *C) { 135 return 0; 136 } 137 138 /// MachineSchedOpt allows command line selection of the scheduler. 139 static cl::opt<MachineSchedRegistry::ScheduleDAGCtor, false, 140 RegisterPassParser<MachineSchedRegistry> > 141 MachineSchedOpt("misched", 142 cl::init(&useDefaultMachineSched), cl::Hidden, 143 cl::desc("Machine instruction scheduler to use")); 144 145 static MachineSchedRegistry 146 DefaultSchedRegistry("default", "Use the target's default scheduler choice.", 147 useDefaultMachineSched); 148 149 /// Forward declare the standard machine scheduler. This will be used as the 150 /// default scheduler if the target does not set a default. 151 static ScheduleDAGInstrs *createConvergingSched(MachineSchedContext *C); 152 153 154 /// Decrement this iterator until reaching the top or a non-debug instr. 155 static MachineBasicBlock::iterator 156 priorNonDebug(MachineBasicBlock::iterator I, MachineBasicBlock::iterator Beg) { 157 assert(I != Beg && "reached the top of the region, cannot decrement"); 158 while (--I != Beg) { 159 if (!I->isDebugValue()) 160 break; 161 } 162 return I; 163 } 164 165 /// If this iterator is a debug value, increment until reaching the End or a 166 /// non-debug instruction. 167 static MachineBasicBlock::iterator 168 nextIfDebug(MachineBasicBlock::iterator I, MachineBasicBlock::iterator End) { 169 for(; I != End; ++I) { 170 if (!I->isDebugValue()) 171 break; 172 } 173 return I; 174 } 175 176 /// Top-level MachineScheduler pass driver. 177 /// 178 /// Visit blocks in function order. Divide each block into scheduling regions 179 /// and visit them bottom-up. Visiting regions bottom-up is not required, but is 180 /// consistent with the DAG builder, which traverses the interior of the 181 /// scheduling regions bottom-up. 182 /// 183 /// This design avoids exposing scheduling boundaries to the DAG builder, 184 /// simplifying the DAG builder's support for "special" target instructions. 185 /// At the same time the design allows target schedulers to operate across 186 /// scheduling boundaries, for example to bundle the boudary instructions 187 /// without reordering them. This creates complexity, because the target 188 /// scheduler must update the RegionBegin and RegionEnd positions cached by 189 /// ScheduleDAGInstrs whenever adding or removing instructions. A much simpler 190 /// design would be to split blocks at scheduling boundaries, but LLVM has a 191 /// general bias against block splitting purely for implementation simplicity. 192 bool MachineScheduler::runOnMachineFunction(MachineFunction &mf) { 193 DEBUG(dbgs() << "Before MISsched:\n"; mf.print(dbgs())); 194 195 // Initialize the context of the pass. 196 MF = &mf; 197 MLI = &getAnalysis<MachineLoopInfo>(); 198 MDT = &getAnalysis<MachineDominatorTree>(); 199 PassConfig = &getAnalysis<TargetPassConfig>(); 200 AA = &getAnalysis<AliasAnalysis>(); 201 202 LIS = &getAnalysis<LiveIntervals>(); 203 const TargetInstrInfo *TII = MF->getTarget().getInstrInfo(); 204 205 if (VerifyScheduling) { 206 DEBUG(LIS->print(dbgs())); 207 MF->verify(this, "Before machine scheduling."); 208 } 209 RegClassInfo->runOnMachineFunction(*MF); 210 211 // Select the scheduler, or set the default. 212 MachineSchedRegistry::ScheduleDAGCtor Ctor = MachineSchedOpt; 213 if (Ctor == useDefaultMachineSched) { 214 // Get the default scheduler set by the target. 215 Ctor = MachineSchedRegistry::getDefault(); 216 if (!Ctor) { 217 Ctor = createConvergingSched; 218 MachineSchedRegistry::setDefault(Ctor); 219 } 220 } 221 // Instantiate the selected scheduler. 222 OwningPtr<ScheduleDAGInstrs> Scheduler(Ctor(this)); 223 224 // Visit all machine basic blocks. 225 // 226 // TODO: Visit blocks in global postorder or postorder within the bottom-up 227 // loop tree. Then we can optionally compute global RegPressure. 228 for (MachineFunction::iterator MBB = MF->begin(), MBBEnd = MF->end(); 229 MBB != MBBEnd; ++MBB) { 230 231 Scheduler->startBlock(MBB); 232 233 // Break the block into scheduling regions [I, RegionEnd), and schedule each 234 // region as soon as it is discovered. RegionEnd points the scheduling 235 // boundary at the bottom of the region. The DAG does not include RegionEnd, 236 // but the region does (i.e. the next RegionEnd is above the previous 237 // RegionBegin). If the current block has no terminator then RegionEnd == 238 // MBB->end() for the bottom region. 239 // 240 // The Scheduler may insert instructions during either schedule() or 241 // exitRegion(), even for empty regions. So the local iterators 'I' and 242 // 'RegionEnd' are invalid across these calls. 243 unsigned RemainingInstrs = MBB->size(); 244 for(MachineBasicBlock::iterator RegionEnd = MBB->end(); 245 RegionEnd != MBB->begin(); RegionEnd = Scheduler->begin()) { 246 247 // Avoid decrementing RegionEnd for blocks with no terminator. 248 if (RegionEnd != MBB->end() 249 || TII->isSchedulingBoundary(llvm::prior(RegionEnd), MBB, *MF)) { 250 --RegionEnd; 251 // Count the boundary instruction. 252 --RemainingInstrs; 253 } 254 255 // The next region starts above the previous region. Look backward in the 256 // instruction stream until we find the nearest boundary. 257 MachineBasicBlock::iterator I = RegionEnd; 258 for(;I != MBB->begin(); --I, --RemainingInstrs) { 259 if (TII->isSchedulingBoundary(llvm::prior(I), MBB, *MF)) 260 break; 261 } 262 // Notify the scheduler of the region, even if we may skip scheduling 263 // it. Perhaps it still needs to be bundled. 264 Scheduler->enterRegion(MBB, I, RegionEnd, RemainingInstrs); 265 266 // Skip empty scheduling regions (0 or 1 schedulable instructions). 267 if (I == RegionEnd || I == llvm::prior(RegionEnd)) { 268 // Close the current region. Bundle the terminator if needed. 269 // This invalidates 'RegionEnd' and 'I'. 270 Scheduler->exitRegion(); 271 continue; 272 } 273 DEBUG(dbgs() << "********** MI Scheduling **********\n"); 274 DEBUG(dbgs() << MF->getName() 275 << ":BB#" << MBB->getNumber() << " " << MBB->getName() 276 << "\n From: " << *I << " To: "; 277 if (RegionEnd != MBB->end()) dbgs() << *RegionEnd; 278 else dbgs() << "End"; 279 dbgs() << " Remaining: " << RemainingInstrs << "\n"); 280 281 // Schedule a region: possibly reorder instructions. 282 // This invalidates 'RegionEnd' and 'I'. 283 Scheduler->schedule(); 284 285 // Close the current region. 286 Scheduler->exitRegion(); 287 288 // Scheduling has invalidated the current iterator 'I'. Ask the 289 // scheduler for the top of it's scheduled region. 290 RegionEnd = Scheduler->begin(); 291 } 292 assert(RemainingInstrs == 0 && "Instruction count mismatch!"); 293 Scheduler->finishBlock(); 294 } 295 Scheduler->finalizeSchedule(); 296 DEBUG(LIS->print(dbgs())); 297 if (VerifyScheduling) 298 MF->verify(this, "After machine scheduling."); 299 return true; 300 } 301 302 void MachineScheduler::print(raw_ostream &O, const Module* m) const { 303 // unimplemented 304 } 305 306 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 307 void ReadyQueue::dump() { 308 dbgs() << Name << ": "; 309 for (unsigned i = 0, e = Queue.size(); i < e; ++i) 310 dbgs() << Queue[i]->NodeNum << " "; 311 dbgs() << "\n"; 312 } 313 #endif 314 315 //===----------------------------------------------------------------------===// 316 // ScheduleDAGMI - Base class for MachineInstr scheduling with LiveIntervals 317 // preservation. 318 //===----------------------------------------------------------------------===// 319 320 ScheduleDAGMI::~ScheduleDAGMI() { 321 delete DFSResult; 322 DeleteContainerPointers(Mutations); 323 delete SchedImpl; 324 } 325 326 bool ScheduleDAGMI::canAddEdge(SUnit *SuccSU, SUnit *PredSU) { 327 return SuccSU == &ExitSU || !Topo.IsReachable(PredSU, SuccSU); 328 } 329 330 bool ScheduleDAGMI::addEdge(SUnit *SuccSU, const SDep &PredDep) { 331 if (SuccSU != &ExitSU) { 332 // Do not use WillCreateCycle, it assumes SD scheduling. 333 // If Pred is reachable from Succ, then the edge creates a cycle. 334 if (Topo.IsReachable(PredDep.getSUnit(), SuccSU)) 335 return false; 336 Topo.AddPred(SuccSU, PredDep.getSUnit()); 337 } 338 SuccSU->addPred(PredDep, /*Required=*/!PredDep.isArtificial()); 339 // Return true regardless of whether a new edge needed to be inserted. 340 return true; 341 } 342 343 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. When 344 /// NumPredsLeft reaches zero, release the successor node. 345 /// 346 /// FIXME: Adjust SuccSU height based on MinLatency. 347 void ScheduleDAGMI::releaseSucc(SUnit *SU, SDep *SuccEdge) { 348 SUnit *SuccSU = SuccEdge->getSUnit(); 349 350 if (SuccEdge->isWeak()) { 351 --SuccSU->WeakPredsLeft; 352 if (SuccEdge->isCluster()) 353 NextClusterSucc = SuccSU; 354 return; 355 } 356 #ifndef NDEBUG 357 if (SuccSU->NumPredsLeft == 0) { 358 dbgs() << "*** Scheduling failed! ***\n"; 359 SuccSU->dump(this); 360 dbgs() << " has been released too many times!\n"; 361 llvm_unreachable(0); 362 } 363 #endif 364 --SuccSU->NumPredsLeft; 365 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) 366 SchedImpl->releaseTopNode(SuccSU); 367 } 368 369 /// releaseSuccessors - Call releaseSucc on each of SU's successors. 370 void ScheduleDAGMI::releaseSuccessors(SUnit *SU) { 371 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 372 I != E; ++I) { 373 releaseSucc(SU, &*I); 374 } 375 } 376 377 /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. When 378 /// NumSuccsLeft reaches zero, release the predecessor node. 379 /// 380 /// FIXME: Adjust PredSU height based on MinLatency. 381 void ScheduleDAGMI::releasePred(SUnit *SU, SDep *PredEdge) { 382 SUnit *PredSU = PredEdge->getSUnit(); 383 384 if (PredEdge->isWeak()) { 385 --PredSU->WeakSuccsLeft; 386 if (PredEdge->isCluster()) 387 NextClusterPred = PredSU; 388 return; 389 } 390 #ifndef NDEBUG 391 if (PredSU->NumSuccsLeft == 0) { 392 dbgs() << "*** Scheduling failed! ***\n"; 393 PredSU->dump(this); 394 dbgs() << " has been released too many times!\n"; 395 llvm_unreachable(0); 396 } 397 #endif 398 --PredSU->NumSuccsLeft; 399 if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) 400 SchedImpl->releaseBottomNode(PredSU); 401 } 402 403 /// releasePredecessors - Call releasePred on each of SU's predecessors. 404 void ScheduleDAGMI::releasePredecessors(SUnit *SU) { 405 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 406 I != E; ++I) { 407 releasePred(SU, &*I); 408 } 409 } 410 411 /// This is normally called from the main scheduler loop but may also be invoked 412 /// by the scheduling strategy to perform additional code motion. 413 void ScheduleDAGMI::moveInstruction(MachineInstr *MI, 414 MachineBasicBlock::iterator InsertPos) { 415 // Advance RegionBegin if the first instruction moves down. 416 if (&*RegionBegin == MI) 417 ++RegionBegin; 418 419 // Update the instruction stream. 420 BB->splice(InsertPos, BB, MI); 421 422 // Update LiveIntervals 423 LIS->handleMove(MI, /*UpdateFlags=*/true); 424 425 // Recede RegionBegin if an instruction moves above the first. 426 if (RegionBegin == InsertPos) 427 RegionBegin = MI; 428 } 429 430 bool ScheduleDAGMI::checkSchedLimit() { 431 #ifndef NDEBUG 432 if (NumInstrsScheduled == MISchedCutoff && MISchedCutoff != ~0U) { 433 CurrentTop = CurrentBottom; 434 return false; 435 } 436 ++NumInstrsScheduled; 437 #endif 438 return true; 439 } 440 441 /// enterRegion - Called back from MachineScheduler::runOnMachineFunction after 442 /// crossing a scheduling boundary. [begin, end) includes all instructions in 443 /// the region, including the boundary itself and single-instruction regions 444 /// that don't get scheduled. 445 void ScheduleDAGMI::enterRegion(MachineBasicBlock *bb, 446 MachineBasicBlock::iterator begin, 447 MachineBasicBlock::iterator end, 448 unsigned endcount) 449 { 450 ScheduleDAGInstrs::enterRegion(bb, begin, end, endcount); 451 452 // For convenience remember the end of the liveness region. 453 LiveRegionEnd = 454 (RegionEnd == bb->end()) ? RegionEnd : llvm::next(RegionEnd); 455 } 456 457 // Setup the register pressure trackers for the top scheduled top and bottom 458 // scheduled regions. 459 void ScheduleDAGMI::initRegPressure() { 460 TopRPTracker.init(&MF, RegClassInfo, LIS, BB, RegionBegin); 461 BotRPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd); 462 463 // Close the RPTracker to finalize live ins. 464 RPTracker.closeRegion(); 465 466 DEBUG(RPTracker.getPressure().dump(TRI)); 467 468 // Initialize the live ins and live outs. 469 TopRPTracker.addLiveRegs(RPTracker.getPressure().LiveInRegs); 470 BotRPTracker.addLiveRegs(RPTracker.getPressure().LiveOutRegs); 471 472 // Close one end of the tracker so we can call 473 // getMaxUpward/DownwardPressureDelta before advancing across any 474 // instructions. This converts currently live regs into live ins/outs. 475 TopRPTracker.closeTop(); 476 BotRPTracker.closeBottom(); 477 478 // Account for liveness generated by the region boundary. 479 if (LiveRegionEnd != RegionEnd) 480 BotRPTracker.recede(); 481 482 assert(BotRPTracker.getPos() == RegionEnd && "Can't find the region bottom"); 483 484 // Cache the list of excess pressure sets in this region. This will also track 485 // the max pressure in the scheduled code for these sets. 486 RegionCriticalPSets.clear(); 487 const std::vector<unsigned> &RegionPressure = 488 RPTracker.getPressure().MaxSetPressure; 489 for (unsigned i = 0, e = RegionPressure.size(); i < e; ++i) { 490 unsigned Limit = TRI->getRegPressureSetLimit(i); 491 DEBUG(dbgs() << TRI->getRegPressureSetName(i) 492 << "Limit " << Limit 493 << " Actual " << RegionPressure[i] << "\n"); 494 if (RegionPressure[i] > Limit) 495 RegionCriticalPSets.push_back(PressureElement(i, 0)); 496 } 497 DEBUG(dbgs() << "Excess PSets: "; 498 for (unsigned i = 0, e = RegionCriticalPSets.size(); i != e; ++i) 499 dbgs() << TRI->getRegPressureSetName( 500 RegionCriticalPSets[i].PSetID) << " "; 501 dbgs() << "\n"); 502 } 503 504 // FIXME: When the pressure tracker deals in pressure differences then we won't 505 // iterate over all RegionCriticalPSets[i]. 506 void ScheduleDAGMI:: 507 updateScheduledPressure(const std::vector<unsigned> &NewMaxPressure) { 508 for (unsigned i = 0, e = RegionCriticalPSets.size(); i < e; ++i) { 509 unsigned ID = RegionCriticalPSets[i].PSetID; 510 int &MaxUnits = RegionCriticalPSets[i].UnitIncrease; 511 if ((int)NewMaxPressure[ID] > MaxUnits) 512 MaxUnits = NewMaxPressure[ID]; 513 } 514 DEBUG( 515 for (unsigned i = 0, e = NewMaxPressure.size(); i < e; ++i) { 516 unsigned Limit = TRI->getRegPressureSetLimit(i); 517 if (NewMaxPressure[i] > Limit ) { 518 dbgs() << " " << TRI->getRegPressureSetName(i) << ": " 519 << NewMaxPressure[i] << " > " << Limit << "\n"; 520 } 521 }); 522 } 523 524 /// schedule - Called back from MachineScheduler::runOnMachineFunction 525 /// after setting up the current scheduling region. [RegionBegin, RegionEnd) 526 /// only includes instructions that have DAG nodes, not scheduling boundaries. 527 /// 528 /// This is a skeletal driver, with all the functionality pushed into helpers, 529 /// so that it can be easilly extended by experimental schedulers. Generally, 530 /// implementing MachineSchedStrategy should be sufficient to implement a new 531 /// scheduling algorithm. However, if a scheduler further subclasses 532 /// ScheduleDAGMI then it will want to override this virtual method in order to 533 /// update any specialized state. 534 void ScheduleDAGMI::schedule() { 535 buildDAGWithRegPressure(); 536 537 Topo.InitDAGTopologicalSorting(); 538 539 postprocessDAG(); 540 541 SmallVector<SUnit*, 8> TopRoots, BotRoots; 542 findRootsAndBiasEdges(TopRoots, BotRoots); 543 544 // Initialize the strategy before modifying the DAG. 545 // This may initialize a DFSResult to be used for queue priority. 546 SchedImpl->initialize(this); 547 548 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 549 SUnits[su].dumpAll(this)); 550 if (ViewMISchedDAGs) viewGraph(); 551 552 // Initialize ready queues now that the DAG and priority data are finalized. 553 initQueues(TopRoots, BotRoots); 554 555 bool IsTopNode = false; 556 while (SUnit *SU = SchedImpl->pickNode(IsTopNode)) { 557 assert(!SU->isScheduled && "Node already scheduled"); 558 if (!checkSchedLimit()) 559 break; 560 561 scheduleMI(SU, IsTopNode); 562 563 updateQueues(SU, IsTopNode); 564 } 565 assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone."); 566 567 placeDebugValues(); 568 569 DEBUG({ 570 unsigned BBNum = begin()->getParent()->getNumber(); 571 dbgs() << "*** Final schedule for BB#" << BBNum << " ***\n"; 572 dumpSchedule(); 573 dbgs() << '\n'; 574 }); 575 } 576 577 /// Build the DAG and setup three register pressure trackers. 578 void ScheduleDAGMI::buildDAGWithRegPressure() { 579 // Initialize the register pressure tracker used by buildSchedGraph. 580 RPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd); 581 582 // Account for liveness generate by the region boundary. 583 if (LiveRegionEnd != RegionEnd) 584 RPTracker.recede(); 585 586 // Build the DAG, and compute current register pressure. 587 buildSchedGraph(AA, &RPTracker); 588 589 // Initialize top/bottom trackers after computing region pressure. 590 initRegPressure(); 591 } 592 593 /// Apply each ScheduleDAGMutation step in order. 594 void ScheduleDAGMI::postprocessDAG() { 595 for (unsigned i = 0, e = Mutations.size(); i < e; ++i) { 596 Mutations[i]->apply(this); 597 } 598 } 599 600 void ScheduleDAGMI::computeDFSResult() { 601 if (!DFSResult) 602 DFSResult = new SchedDFSResult(/*BottomU*/true, MinSubtreeSize); 603 DFSResult->clear(); 604 ScheduledTrees.clear(); 605 DFSResult->resize(SUnits.size()); 606 DFSResult->compute(SUnits); 607 ScheduledTrees.resize(DFSResult->getNumSubtrees()); 608 } 609 610 void ScheduleDAGMI::findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots, 611 SmallVectorImpl<SUnit*> &BotRoots) { 612 for (std::vector<SUnit>::iterator 613 I = SUnits.begin(), E = SUnits.end(); I != E; ++I) { 614 SUnit *SU = &(*I); 615 assert(!SU->isBoundaryNode() && "Boundary node should not be in SUnits"); 616 617 // Order predecessors so DFSResult follows the critical path. 618 SU->biasCriticalPath(); 619 620 // A SUnit is ready to top schedule if it has no predecessors. 621 if (!I->NumPredsLeft) 622 TopRoots.push_back(SU); 623 // A SUnit is ready to bottom schedule if it has no successors. 624 if (!I->NumSuccsLeft) 625 BotRoots.push_back(SU); 626 } 627 ExitSU.biasCriticalPath(); 628 } 629 630 /// Identify DAG roots and setup scheduler queues. 631 void ScheduleDAGMI::initQueues(ArrayRef<SUnit*> TopRoots, 632 ArrayRef<SUnit*> BotRoots) { 633 NextClusterSucc = NULL; 634 NextClusterPred = NULL; 635 636 // Release all DAG roots for scheduling, not including EntrySU/ExitSU. 637 // 638 // Nodes with unreleased weak edges can still be roots. 639 // Release top roots in forward order. 640 for (SmallVectorImpl<SUnit*>::const_iterator 641 I = TopRoots.begin(), E = TopRoots.end(); I != E; ++I) { 642 SchedImpl->releaseTopNode(*I); 643 } 644 // Release bottom roots in reverse order so the higher priority nodes appear 645 // first. This is more natural and slightly more efficient. 646 for (SmallVectorImpl<SUnit*>::const_reverse_iterator 647 I = BotRoots.rbegin(), E = BotRoots.rend(); I != E; ++I) { 648 SchedImpl->releaseBottomNode(*I); 649 } 650 651 releaseSuccessors(&EntrySU); 652 releasePredecessors(&ExitSU); 653 654 SchedImpl->registerRoots(); 655 656 // Advance past initial DebugValues. 657 assert(TopRPTracker.getPos() == RegionBegin && "bad initial Top tracker"); 658 CurrentTop = nextIfDebug(RegionBegin, RegionEnd); 659 TopRPTracker.setPos(CurrentTop); 660 661 CurrentBottom = RegionEnd; 662 } 663 664 /// Move an instruction and update register pressure. 665 void ScheduleDAGMI::scheduleMI(SUnit *SU, bool IsTopNode) { 666 // Move the instruction to its new location in the instruction stream. 667 MachineInstr *MI = SU->getInstr(); 668 669 if (IsTopNode) { 670 assert(SU->isTopReady() && "node still has unscheduled dependencies"); 671 if (&*CurrentTop == MI) 672 CurrentTop = nextIfDebug(++CurrentTop, CurrentBottom); 673 else { 674 moveInstruction(MI, CurrentTop); 675 TopRPTracker.setPos(MI); 676 } 677 678 // Update top scheduled pressure. 679 TopRPTracker.advance(); 680 assert(TopRPTracker.getPos() == CurrentTop && "out of sync"); 681 updateScheduledPressure(TopRPTracker.getPressure().MaxSetPressure); 682 } 683 else { 684 assert(SU->isBottomReady() && "node still has unscheduled dependencies"); 685 MachineBasicBlock::iterator priorII = 686 priorNonDebug(CurrentBottom, CurrentTop); 687 if (&*priorII == MI) 688 CurrentBottom = priorII; 689 else { 690 if (&*CurrentTop == MI) { 691 CurrentTop = nextIfDebug(++CurrentTop, priorII); 692 TopRPTracker.setPos(CurrentTop); 693 } 694 moveInstruction(MI, CurrentBottom); 695 CurrentBottom = MI; 696 } 697 // Update bottom scheduled pressure. 698 BotRPTracker.recede(); 699 assert(BotRPTracker.getPos() == CurrentBottom && "out of sync"); 700 updateScheduledPressure(BotRPTracker.getPressure().MaxSetPressure); 701 } 702 } 703 704 /// Update scheduler queues after scheduling an instruction. 705 void ScheduleDAGMI::updateQueues(SUnit *SU, bool IsTopNode) { 706 // Release dependent instructions for scheduling. 707 if (IsTopNode) 708 releaseSuccessors(SU); 709 else 710 releasePredecessors(SU); 711 712 SU->isScheduled = true; 713 714 if (DFSResult) { 715 unsigned SubtreeID = DFSResult->getSubtreeID(SU); 716 if (!ScheduledTrees.test(SubtreeID)) { 717 ScheduledTrees.set(SubtreeID); 718 DFSResult->scheduleTree(SubtreeID); 719 SchedImpl->scheduleTree(SubtreeID); 720 } 721 } 722 723 // Notify the scheduling strategy after updating the DAG. 724 SchedImpl->schedNode(SU, IsTopNode); 725 } 726 727 /// Reinsert any remaining debug_values, just like the PostRA scheduler. 728 void ScheduleDAGMI::placeDebugValues() { 729 // If first instruction was a DBG_VALUE then put it back. 730 if (FirstDbgValue) { 731 BB->splice(RegionBegin, BB, FirstDbgValue); 732 RegionBegin = FirstDbgValue; 733 } 734 735 for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator 736 DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) { 737 std::pair<MachineInstr *, MachineInstr *> P = *prior(DI); 738 MachineInstr *DbgValue = P.first; 739 MachineBasicBlock::iterator OrigPrevMI = P.second; 740 if (&*RegionBegin == DbgValue) 741 ++RegionBegin; 742 BB->splice(++OrigPrevMI, BB, DbgValue); 743 if (OrigPrevMI == llvm::prior(RegionEnd)) 744 RegionEnd = DbgValue; 745 } 746 DbgValues.clear(); 747 FirstDbgValue = NULL; 748 } 749 750 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 751 void ScheduleDAGMI::dumpSchedule() const { 752 for (MachineBasicBlock::iterator MI = begin(), ME = end(); MI != ME; ++MI) { 753 if (SUnit *SU = getSUnit(&(*MI))) 754 SU->dump(this); 755 else 756 dbgs() << "Missing SUnit\n"; 757 } 758 } 759 #endif 760 761 //===----------------------------------------------------------------------===// 762 // LoadClusterMutation - DAG post-processing to cluster loads. 763 //===----------------------------------------------------------------------===// 764 765 namespace { 766 /// \brief Post-process the DAG to create cluster edges between neighboring 767 /// loads. 768 class LoadClusterMutation : public ScheduleDAGMutation { 769 struct LoadInfo { 770 SUnit *SU; 771 unsigned BaseReg; 772 unsigned Offset; 773 LoadInfo(SUnit *su, unsigned reg, unsigned ofs) 774 : SU(su), BaseReg(reg), Offset(ofs) {} 775 }; 776 static bool LoadInfoLess(const LoadClusterMutation::LoadInfo &LHS, 777 const LoadClusterMutation::LoadInfo &RHS); 778 779 const TargetInstrInfo *TII; 780 const TargetRegisterInfo *TRI; 781 public: 782 LoadClusterMutation(const TargetInstrInfo *tii, 783 const TargetRegisterInfo *tri) 784 : TII(tii), TRI(tri) {} 785 786 virtual void apply(ScheduleDAGMI *DAG); 787 protected: 788 void clusterNeighboringLoads(ArrayRef<SUnit*> Loads, ScheduleDAGMI *DAG); 789 }; 790 } // anonymous 791 792 bool LoadClusterMutation::LoadInfoLess( 793 const LoadClusterMutation::LoadInfo &LHS, 794 const LoadClusterMutation::LoadInfo &RHS) { 795 if (LHS.BaseReg != RHS.BaseReg) 796 return LHS.BaseReg < RHS.BaseReg; 797 return LHS.Offset < RHS.Offset; 798 } 799 800 void LoadClusterMutation::clusterNeighboringLoads(ArrayRef<SUnit*> Loads, 801 ScheduleDAGMI *DAG) { 802 SmallVector<LoadClusterMutation::LoadInfo,32> LoadRecords; 803 for (unsigned Idx = 0, End = Loads.size(); Idx != End; ++Idx) { 804 SUnit *SU = Loads[Idx]; 805 unsigned BaseReg; 806 unsigned Offset; 807 if (TII->getLdStBaseRegImmOfs(SU->getInstr(), BaseReg, Offset, TRI)) 808 LoadRecords.push_back(LoadInfo(SU, BaseReg, Offset)); 809 } 810 if (LoadRecords.size() < 2) 811 return; 812 std::sort(LoadRecords.begin(), LoadRecords.end(), LoadInfoLess); 813 unsigned ClusterLength = 1; 814 for (unsigned Idx = 0, End = LoadRecords.size(); Idx < (End - 1); ++Idx) { 815 if (LoadRecords[Idx].BaseReg != LoadRecords[Idx+1].BaseReg) { 816 ClusterLength = 1; 817 continue; 818 } 819 820 SUnit *SUa = LoadRecords[Idx].SU; 821 SUnit *SUb = LoadRecords[Idx+1].SU; 822 if (TII->shouldClusterLoads(SUa->getInstr(), SUb->getInstr(), ClusterLength) 823 && DAG->addEdge(SUb, SDep(SUa, SDep::Cluster))) { 824 825 DEBUG(dbgs() << "Cluster loads SU(" << SUa->NodeNum << ") - SU(" 826 << SUb->NodeNum << ")\n"); 827 // Copy successor edges from SUa to SUb. Interleaving computation 828 // dependent on SUa can prevent load combining due to register reuse. 829 // Predecessor edges do not need to be copied from SUb to SUa since nearby 830 // loads should have effectively the same inputs. 831 for (SUnit::const_succ_iterator 832 SI = SUa->Succs.begin(), SE = SUa->Succs.end(); SI != SE; ++SI) { 833 if (SI->getSUnit() == SUb) 834 continue; 835 DEBUG(dbgs() << " Copy Succ SU(" << SI->getSUnit()->NodeNum << ")\n"); 836 DAG->addEdge(SI->getSUnit(), SDep(SUb, SDep::Artificial)); 837 } 838 ++ClusterLength; 839 } 840 else 841 ClusterLength = 1; 842 } 843 } 844 845 /// \brief Callback from DAG postProcessing to create cluster edges for loads. 846 void LoadClusterMutation::apply(ScheduleDAGMI *DAG) { 847 // Map DAG NodeNum to store chain ID. 848 DenseMap<unsigned, unsigned> StoreChainIDs; 849 // Map each store chain to a set of dependent loads. 850 SmallVector<SmallVector<SUnit*,4>, 32> StoreChainDependents; 851 for (unsigned Idx = 0, End = DAG->SUnits.size(); Idx != End; ++Idx) { 852 SUnit *SU = &DAG->SUnits[Idx]; 853 if (!SU->getInstr()->mayLoad()) 854 continue; 855 unsigned ChainPredID = DAG->SUnits.size(); 856 for (SUnit::const_pred_iterator 857 PI = SU->Preds.begin(), PE = SU->Preds.end(); PI != PE; ++PI) { 858 if (PI->isCtrl()) { 859 ChainPredID = PI->getSUnit()->NodeNum; 860 break; 861 } 862 } 863 // Check if this chain-like pred has been seen 864 // before. ChainPredID==MaxNodeID for loads at the top of the schedule. 865 unsigned NumChains = StoreChainDependents.size(); 866 std::pair<DenseMap<unsigned, unsigned>::iterator, bool> Result = 867 StoreChainIDs.insert(std::make_pair(ChainPredID, NumChains)); 868 if (Result.second) 869 StoreChainDependents.resize(NumChains + 1); 870 StoreChainDependents[Result.first->second].push_back(SU); 871 } 872 // Iterate over the store chains. 873 for (unsigned Idx = 0, End = StoreChainDependents.size(); Idx != End; ++Idx) 874 clusterNeighboringLoads(StoreChainDependents[Idx], DAG); 875 } 876 877 //===----------------------------------------------------------------------===// 878 // MacroFusion - DAG post-processing to encourage fusion of macro ops. 879 //===----------------------------------------------------------------------===// 880 881 namespace { 882 /// \brief Post-process the DAG to create cluster edges between instructions 883 /// that may be fused by the processor into a single operation. 884 class MacroFusion : public ScheduleDAGMutation { 885 const TargetInstrInfo *TII; 886 public: 887 MacroFusion(const TargetInstrInfo *tii): TII(tii) {} 888 889 virtual void apply(ScheduleDAGMI *DAG); 890 }; 891 } // anonymous 892 893 /// \brief Callback from DAG postProcessing to create cluster edges to encourage 894 /// fused operations. 895 void MacroFusion::apply(ScheduleDAGMI *DAG) { 896 // For now, assume targets can only fuse with the branch. 897 MachineInstr *Branch = DAG->ExitSU.getInstr(); 898 if (!Branch) 899 return; 900 901 for (unsigned Idx = DAG->SUnits.size(); Idx > 0;) { 902 SUnit *SU = &DAG->SUnits[--Idx]; 903 if (!TII->shouldScheduleAdjacent(SU->getInstr(), Branch)) 904 continue; 905 906 // Create a single weak edge from SU to ExitSU. The only effect is to cause 907 // bottom-up scheduling to heavily prioritize the clustered SU. There is no 908 // need to copy predecessor edges from ExitSU to SU, since top-down 909 // scheduling cannot prioritize ExitSU anyway. To defer top-down scheduling 910 // of SU, we could create an artificial edge from the deepest root, but it 911 // hasn't been needed yet. 912 bool Success = DAG->addEdge(&DAG->ExitSU, SDep(SU, SDep::Cluster)); 913 (void)Success; 914 assert(Success && "No DAG nodes should be reachable from ExitSU"); 915 916 DEBUG(dbgs() << "Macro Fuse SU(" << SU->NodeNum << ")\n"); 917 break; 918 } 919 } 920 921 //===----------------------------------------------------------------------===// 922 // CopyConstrain - DAG post-processing to encourage copy elimination. 923 //===----------------------------------------------------------------------===// 924 925 namespace { 926 /// \brief Post-process the DAG to create weak edges from all uses of a copy to 927 /// the one use that defines the copy's source vreg, most likely an induction 928 /// variable increment. 929 class CopyConstrain : public ScheduleDAGMutation { 930 // Transient state. 931 SlotIndex RegionBeginIdx; 932 // RegionEndIdx is the slot index of the last non-debug instruction in the 933 // scheduling region. So we may have RegionBeginIdx == RegionEndIdx. 934 SlotIndex RegionEndIdx; 935 public: 936 CopyConstrain(const TargetInstrInfo *, const TargetRegisterInfo *) {} 937 938 virtual void apply(ScheduleDAGMI *DAG); 939 940 protected: 941 void constrainLocalCopy(SUnit *CopySU, ScheduleDAGMI *DAG); 942 }; 943 } // anonymous 944 945 /// constrainLocalCopy handles two possibilities: 946 /// 1) Local src: 947 /// I0: = dst 948 /// I1: src = ... 949 /// I2: = dst 950 /// I3: dst = src (copy) 951 /// (create pred->succ edges I0->I1, I2->I1) 952 /// 953 /// 2) Local copy: 954 /// I0: dst = src (copy) 955 /// I1: = dst 956 /// I2: src = ... 957 /// I3: = dst 958 /// (create pred->succ edges I1->I2, I3->I2) 959 /// 960 /// Although the MachineScheduler is currently constrained to single blocks, 961 /// this algorithm should handle extended blocks. An EBB is a set of 962 /// contiguously numbered blocks such that the previous block in the EBB is 963 /// always the single predecessor. 964 void CopyConstrain::constrainLocalCopy(SUnit *CopySU, ScheduleDAGMI *DAG) { 965 LiveIntervals *LIS = DAG->getLIS(); 966 MachineInstr *Copy = CopySU->getInstr(); 967 968 // Check for pure vreg copies. 969 unsigned SrcReg = Copy->getOperand(1).getReg(); 970 if (!TargetRegisterInfo::isVirtualRegister(SrcReg)) 971 return; 972 973 unsigned DstReg = Copy->getOperand(0).getReg(); 974 if (!TargetRegisterInfo::isVirtualRegister(DstReg)) 975 return; 976 977 // Check if either the dest or source is local. If it's live across a back 978 // edge, it's not local. Note that if both vregs are live across the back 979 // edge, we cannot successfully contrain the copy without cyclic scheduling. 980 unsigned LocalReg = DstReg; 981 unsigned GlobalReg = SrcReg; 982 LiveInterval *LocalLI = &LIS->getInterval(LocalReg); 983 if (!LocalLI->isLocal(RegionBeginIdx, RegionEndIdx)) { 984 LocalReg = SrcReg; 985 GlobalReg = DstReg; 986 LocalLI = &LIS->getInterval(LocalReg); 987 if (!LocalLI->isLocal(RegionBeginIdx, RegionEndIdx)) 988 return; 989 } 990 LiveInterval *GlobalLI = &LIS->getInterval(GlobalReg); 991 992 // Find the global segment after the start of the local LI. 993 LiveInterval::iterator GlobalSegment = GlobalLI->find(LocalLI->beginIndex()); 994 // If GlobalLI does not overlap LocalLI->start, then a copy directly feeds a 995 // local live range. We could create edges from other global uses to the local 996 // start, but the coalescer should have already eliminated these cases, so 997 // don't bother dealing with it. 998 if (GlobalSegment == GlobalLI->end()) 999 return; 1000 1001 // If GlobalSegment is killed at the LocalLI->start, the call to find() 1002 // returned the next global segment. But if GlobalSegment overlaps with 1003 // LocalLI->start, then advance to the next segement. If a hole in GlobalLI 1004 // exists in LocalLI's vicinity, GlobalSegment will be the end of the hole. 1005 if (GlobalSegment->contains(LocalLI->beginIndex())) 1006 ++GlobalSegment; 1007 1008 if (GlobalSegment == GlobalLI->end()) 1009 return; 1010 1011 // Check if GlobalLI contains a hole in the vicinity of LocalLI. 1012 if (GlobalSegment != GlobalLI->begin()) { 1013 // Two address defs have no hole. 1014 if (SlotIndex::isSameInstr(llvm::prior(GlobalSegment)->end, 1015 GlobalSegment->start)) { 1016 return; 1017 } 1018 // If GlobalLI has a prior segment, it must be live into the EBB. Otherwise 1019 // it would be a disconnected component in the live range. 1020 assert(llvm::prior(GlobalSegment)->start < LocalLI->beginIndex() && 1021 "Disconnected LRG within the scheduling region."); 1022 } 1023 MachineInstr *GlobalDef = LIS->getInstructionFromIndex(GlobalSegment->start); 1024 if (!GlobalDef) 1025 return; 1026 1027 SUnit *GlobalSU = DAG->getSUnit(GlobalDef); 1028 if (!GlobalSU) 1029 return; 1030 1031 // GlobalDef is the bottom of the GlobalLI hole. Open the hole by 1032 // constraining the uses of the last local def to precede GlobalDef. 1033 SmallVector<SUnit*,8> LocalUses; 1034 const VNInfo *LastLocalVN = LocalLI->getVNInfoBefore(LocalLI->endIndex()); 1035 MachineInstr *LastLocalDef = LIS->getInstructionFromIndex(LastLocalVN->def); 1036 SUnit *LastLocalSU = DAG->getSUnit(LastLocalDef); 1037 for (SUnit::const_succ_iterator 1038 I = LastLocalSU->Succs.begin(), E = LastLocalSU->Succs.end(); 1039 I != E; ++I) { 1040 if (I->getKind() != SDep::Data || I->getReg() != LocalReg) 1041 continue; 1042 if (I->getSUnit() == GlobalSU) 1043 continue; 1044 if (!DAG->canAddEdge(GlobalSU, I->getSUnit())) 1045 return; 1046 LocalUses.push_back(I->getSUnit()); 1047 } 1048 // Open the top of the GlobalLI hole by constraining any earlier global uses 1049 // to precede the start of LocalLI. 1050 SmallVector<SUnit*,8> GlobalUses; 1051 MachineInstr *FirstLocalDef = 1052 LIS->getInstructionFromIndex(LocalLI->beginIndex()); 1053 SUnit *FirstLocalSU = DAG->getSUnit(FirstLocalDef); 1054 for (SUnit::const_pred_iterator 1055 I = GlobalSU->Preds.begin(), E = GlobalSU->Preds.end(); I != E; ++I) { 1056 if (I->getKind() != SDep::Anti || I->getReg() != GlobalReg) 1057 continue; 1058 if (I->getSUnit() == FirstLocalSU) 1059 continue; 1060 if (!DAG->canAddEdge(FirstLocalSU, I->getSUnit())) 1061 return; 1062 GlobalUses.push_back(I->getSUnit()); 1063 } 1064 DEBUG(dbgs() << "Constraining copy SU(" << CopySU->NodeNum << ")\n"); 1065 // Add the weak edges. 1066 for (SmallVectorImpl<SUnit*>::const_iterator 1067 I = LocalUses.begin(), E = LocalUses.end(); I != E; ++I) { 1068 DEBUG(dbgs() << " Local use SU(" << (*I)->NodeNum << ") -> SU(" 1069 << GlobalSU->NodeNum << ")\n"); 1070 DAG->addEdge(GlobalSU, SDep(*I, SDep::Weak)); 1071 } 1072 for (SmallVectorImpl<SUnit*>::const_iterator 1073 I = GlobalUses.begin(), E = GlobalUses.end(); I != E; ++I) { 1074 DEBUG(dbgs() << " Global use SU(" << (*I)->NodeNum << ") -> SU(" 1075 << FirstLocalSU->NodeNum << ")\n"); 1076 DAG->addEdge(FirstLocalSU, SDep(*I, SDep::Weak)); 1077 } 1078 } 1079 1080 /// \brief Callback from DAG postProcessing to create weak edges to encourage 1081 /// copy elimination. 1082 void CopyConstrain::apply(ScheduleDAGMI *DAG) { 1083 MachineBasicBlock::iterator FirstPos = nextIfDebug(DAG->begin(), DAG->end()); 1084 if (FirstPos == DAG->end()) 1085 return; 1086 RegionBeginIdx = DAG->getLIS()->getInstructionIndex(&*FirstPos); 1087 RegionEndIdx = DAG->getLIS()->getInstructionIndex( 1088 &*priorNonDebug(DAG->end(), DAG->begin())); 1089 1090 for (unsigned Idx = 0, End = DAG->SUnits.size(); Idx != End; ++Idx) { 1091 SUnit *SU = &DAG->SUnits[Idx]; 1092 if (!SU->getInstr()->isCopy()) 1093 continue; 1094 1095 constrainLocalCopy(SU, DAG); 1096 } 1097 } 1098 1099 //===----------------------------------------------------------------------===// 1100 // ConvergingScheduler - Implementation of the generic MachineSchedStrategy. 1101 //===----------------------------------------------------------------------===// 1102 1103 namespace { 1104 /// ConvergingScheduler shrinks the unscheduled zone using heuristics to balance 1105 /// the schedule. 1106 class ConvergingScheduler : public MachineSchedStrategy { 1107 public: 1108 /// Represent the type of SchedCandidate found within a single queue. 1109 /// pickNodeBidirectional depends on these listed by decreasing priority. 1110 enum CandReason { 1111 NoCand, PhysRegCopy, RegExcess, RegCritical, Cluster, Weak, 1112 ResourceReduce, ResourceDemand, BotHeightReduce, BotPathReduce, 1113 TopDepthReduce, TopPathReduce, SingleMax, NextDefUse, NodeOrder}; 1114 1115 #ifndef NDEBUG 1116 static const char *getReasonStr(ConvergingScheduler::CandReason Reason); 1117 #endif 1118 1119 /// Policy for scheduling the next instruction in the candidate's zone. 1120 struct CandPolicy { 1121 bool ReduceLatency; 1122 unsigned ReduceResIdx; 1123 unsigned DemandResIdx; 1124 1125 CandPolicy(): ReduceLatency(false), ReduceResIdx(0), DemandResIdx(0) {} 1126 }; 1127 1128 /// Status of an instruction's critical resource consumption. 1129 struct SchedResourceDelta { 1130 // Count critical resources in the scheduled region required by SU. 1131 unsigned CritResources; 1132 1133 // Count critical resources from another region consumed by SU. 1134 unsigned DemandedResources; 1135 1136 SchedResourceDelta(): CritResources(0), DemandedResources(0) {} 1137 1138 bool operator==(const SchedResourceDelta &RHS) const { 1139 return CritResources == RHS.CritResources 1140 && DemandedResources == RHS.DemandedResources; 1141 } 1142 bool operator!=(const SchedResourceDelta &RHS) const { 1143 return !operator==(RHS); 1144 } 1145 }; 1146 1147 /// Store the state used by ConvergingScheduler heuristics, required for the 1148 /// lifetime of one invocation of pickNode(). 1149 struct SchedCandidate { 1150 CandPolicy Policy; 1151 1152 // The best SUnit candidate. 1153 SUnit *SU; 1154 1155 // The reason for this candidate. 1156 CandReason Reason; 1157 1158 // Set of reasons that apply to multiple candidates. 1159 uint32_t RepeatReasonSet; 1160 1161 // Register pressure values for the best candidate. 1162 RegPressureDelta RPDelta; 1163 1164 // Critical resource consumption of the best candidate. 1165 SchedResourceDelta ResDelta; 1166 1167 SchedCandidate(const CandPolicy &policy) 1168 : Policy(policy), SU(NULL), Reason(NoCand), RepeatReasonSet(0) {} 1169 1170 bool isValid() const { return SU; } 1171 1172 // Copy the status of another candidate without changing policy. 1173 void setBest(SchedCandidate &Best) { 1174 assert(Best.Reason != NoCand && "uninitialized Sched candidate"); 1175 SU = Best.SU; 1176 Reason = Best.Reason; 1177 RPDelta = Best.RPDelta; 1178 ResDelta = Best.ResDelta; 1179 } 1180 1181 bool isRepeat(CandReason R) { return RepeatReasonSet & (1 << R); } 1182 void setRepeat(CandReason R) { RepeatReasonSet |= (1 << R); } 1183 1184 void initResourceDelta(const ScheduleDAGMI *DAG, 1185 const TargetSchedModel *SchedModel); 1186 }; 1187 1188 /// Summarize the unscheduled region. 1189 struct SchedRemainder { 1190 // Critical path through the DAG in expected latency. 1191 unsigned CriticalPath; 1192 1193 // Scaled count of micro-ops left to schedule. 1194 unsigned RemIssueCount; 1195 1196 // Unscheduled resources 1197 SmallVector<unsigned, 16> RemainingCounts; 1198 1199 void reset() { 1200 CriticalPath = 0; 1201 RemIssueCount = 0; 1202 RemainingCounts.clear(); 1203 } 1204 1205 SchedRemainder() { reset(); } 1206 1207 void init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel); 1208 }; 1209 1210 /// Each Scheduling boundary is associated with ready queues. It tracks the 1211 /// current cycle in the direction of movement, and maintains the state 1212 /// of "hazards" and other interlocks at the current cycle. 1213 struct SchedBoundary { 1214 ScheduleDAGMI *DAG; 1215 const TargetSchedModel *SchedModel; 1216 SchedRemainder *Rem; 1217 1218 ReadyQueue Available; 1219 ReadyQueue Pending; 1220 bool CheckPending; 1221 1222 // For heuristics, keep a list of the nodes that immediately depend on the 1223 // most recently scheduled node. 1224 SmallPtrSet<const SUnit*, 8> NextSUs; 1225 1226 ScheduleHazardRecognizer *HazardRec; 1227 1228 /// Number of cycles it takes to issue the instructions scheduled in this 1229 /// zone. It is defined as: scheduled-micro-ops / issue-width + stalls. 1230 /// See getStalls(). 1231 unsigned CurrCycle; 1232 1233 /// Micro-ops issued in the current cycle 1234 unsigned CurrMOps; 1235 1236 /// MinReadyCycle - Cycle of the soonest available instruction. 1237 unsigned MinReadyCycle; 1238 1239 // The expected latency of the critical path in this scheduled zone. 1240 unsigned ExpectedLatency; 1241 1242 // The latency of dependence chains leading into this zone. 1243 // For each node scheduled top-down: DLat = max DLat, N.Depth. 1244 // For each cycle scheduled: DLat -= 1. 1245 unsigned DependentLatency; 1246 1247 /// Count the scheduled (issued) micro-ops that can be retired by 1248 /// time=CurrCycle assuming the first scheduled instr is retired at time=0. 1249 unsigned RetiredMOps; 1250 1251 // Count scheduled resources that have been executed. Resources are 1252 // considered executed if they become ready in the time that it takes to 1253 // saturate any resource including the one in question. Counts are scaled 1254 // for direct comparison with other resources. Counts ca be compared with 1255 // MOps * getMicroOpFactor and Latency * getLatencyFactor. 1256 SmallVector<unsigned, 16> ExecutedResCounts; 1257 1258 /// Cache the max count for a single resource. 1259 unsigned MaxExecutedResCount; 1260 1261 // Cache the critical resources ID in this scheduled zone. 1262 unsigned ZoneCritResIdx; 1263 1264 // Is the scheduled region resource limited vs. latency limited. 1265 bool IsResourceLimited; 1266 1267 #ifndef NDEBUG 1268 // Remember the greatest operand latency as an upper bound on the number of 1269 // times we should retry the pending queue because of a hazard. 1270 unsigned MaxObservedLatency; 1271 #endif 1272 1273 void reset() { 1274 // A new HazardRec is created for each DAG and owned by SchedBoundary. 1275 delete HazardRec; 1276 1277 Available.clear(); 1278 Pending.clear(); 1279 CheckPending = false; 1280 NextSUs.clear(); 1281 HazardRec = 0; 1282 CurrCycle = 0; 1283 CurrMOps = 0; 1284 MinReadyCycle = UINT_MAX; 1285 ExpectedLatency = 0; 1286 DependentLatency = 0; 1287 RetiredMOps = 0; 1288 MaxExecutedResCount = 0; 1289 ZoneCritResIdx = 0; 1290 IsResourceLimited = false; 1291 #ifndef NDEBUG 1292 MaxObservedLatency = 0; 1293 #endif 1294 // Reserve a zero-count for invalid CritResIdx. 1295 ExecutedResCounts.resize(1); 1296 assert(!ExecutedResCounts[0] && "nonzero count for bad resource"); 1297 } 1298 1299 /// Pending queues extend the ready queues with the same ID and the 1300 /// PendingFlag set. 1301 SchedBoundary(unsigned ID, const Twine &Name): 1302 DAG(0), SchedModel(0), Rem(0), Available(ID, Name+".A"), 1303 Pending(ID << ConvergingScheduler::LogMaxQID, Name+".P"), 1304 HazardRec(0) { 1305 reset(); 1306 } 1307 1308 ~SchedBoundary() { delete HazardRec; } 1309 1310 void init(ScheduleDAGMI *dag, const TargetSchedModel *smodel, 1311 SchedRemainder *rem); 1312 1313 bool isTop() const { 1314 return Available.getID() == ConvergingScheduler::TopQID; 1315 } 1316 1317 #ifndef NDEBUG 1318 const char *getResourceName(unsigned PIdx) { 1319 if (!PIdx) 1320 return "MOps"; 1321 return SchedModel->getProcResource(PIdx)->Name; 1322 } 1323 #endif 1324 1325 /// Get the number of latency cycles "covered" by the scheduled 1326 /// instructions. This is the larger of the critical path within the zone 1327 /// and the number of cycles required to issue the instructions. 1328 unsigned getScheduledLatency() const { 1329 return std::max(ExpectedLatency, CurrCycle); 1330 } 1331 1332 unsigned getUnscheduledLatency(SUnit *SU) const { 1333 return isTop() ? SU->getHeight() : SU->getDepth(); 1334 } 1335 1336 unsigned getResourceCount(unsigned ResIdx) const { 1337 return ExecutedResCounts[ResIdx]; 1338 } 1339 1340 /// Get the scaled count of scheduled micro-ops and resources, including 1341 /// executed resources. 1342 unsigned getCriticalCount() const { 1343 if (!ZoneCritResIdx) 1344 return RetiredMOps * SchedModel->getMicroOpFactor(); 1345 return getResourceCount(ZoneCritResIdx); 1346 } 1347 1348 /// Get a scaled count for the minimum execution time of the scheduled 1349 /// micro-ops that are ready to execute by getExecutedCount. Notice the 1350 /// feedback loop. 1351 unsigned getExecutedCount() const { 1352 return std::max(CurrCycle * SchedModel->getLatencyFactor(), 1353 MaxExecutedResCount); 1354 } 1355 1356 bool checkHazard(SUnit *SU); 1357 1358 unsigned findMaxLatency(ArrayRef<SUnit*> ReadySUs); 1359 1360 unsigned getOtherResourceCount(unsigned &OtherCritIdx); 1361 1362 void setPolicy(CandPolicy &Policy, SchedBoundary &OtherZone); 1363 1364 void releaseNode(SUnit *SU, unsigned ReadyCycle); 1365 1366 void bumpCycle(unsigned NextCycle); 1367 1368 void incExecutedResources(unsigned PIdx, unsigned Count); 1369 1370 unsigned countResource(unsigned PIdx, unsigned Cycles, unsigned ReadyCycle); 1371 1372 void bumpNode(SUnit *SU); 1373 1374 void releasePending(); 1375 1376 void removeReady(SUnit *SU); 1377 1378 SUnit *pickOnlyChoice(); 1379 1380 #ifndef NDEBUG 1381 void dumpScheduledState(); 1382 #endif 1383 }; 1384 1385 private: 1386 ScheduleDAGMI *DAG; 1387 const TargetSchedModel *SchedModel; 1388 const TargetRegisterInfo *TRI; 1389 1390 // State of the top and bottom scheduled instruction boundaries. 1391 SchedRemainder Rem; 1392 SchedBoundary Top; 1393 SchedBoundary Bot; 1394 1395 public: 1396 /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both) 1397 enum { 1398 TopQID = 1, 1399 BotQID = 2, 1400 LogMaxQID = 2 1401 }; 1402 1403 ConvergingScheduler(): 1404 DAG(0), SchedModel(0), TRI(0), Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {} 1405 1406 virtual void initialize(ScheduleDAGMI *dag); 1407 1408 virtual SUnit *pickNode(bool &IsTopNode); 1409 1410 virtual void schedNode(SUnit *SU, bool IsTopNode); 1411 1412 virtual void releaseTopNode(SUnit *SU); 1413 1414 virtual void releaseBottomNode(SUnit *SU); 1415 1416 virtual void registerRoots(); 1417 1418 protected: 1419 void tryCandidate(SchedCandidate &Cand, 1420 SchedCandidate &TryCand, 1421 SchedBoundary &Zone, 1422 const RegPressureTracker &RPTracker, 1423 RegPressureTracker &TempTracker); 1424 1425 SUnit *pickNodeBidirectional(bool &IsTopNode); 1426 1427 void pickNodeFromQueue(SchedBoundary &Zone, 1428 const RegPressureTracker &RPTracker, 1429 SchedCandidate &Candidate); 1430 1431 void reschedulePhysRegCopies(SUnit *SU, bool isTop); 1432 1433 #ifndef NDEBUG 1434 void traceCandidate(const SchedCandidate &Cand); 1435 #endif 1436 }; 1437 } // namespace 1438 1439 void ConvergingScheduler::SchedRemainder:: 1440 init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel) { 1441 reset(); 1442 if (!SchedModel->hasInstrSchedModel()) 1443 return; 1444 RemainingCounts.resize(SchedModel->getNumProcResourceKinds()); 1445 for (std::vector<SUnit>::iterator 1446 I = DAG->SUnits.begin(), E = DAG->SUnits.end(); I != E; ++I) { 1447 const MCSchedClassDesc *SC = DAG->getSchedClass(&*I); 1448 RemIssueCount += SchedModel->getNumMicroOps(I->getInstr(), SC) 1449 * SchedModel->getMicroOpFactor(); 1450 for (TargetSchedModel::ProcResIter 1451 PI = SchedModel->getWriteProcResBegin(SC), 1452 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) { 1453 unsigned PIdx = PI->ProcResourceIdx; 1454 unsigned Factor = SchedModel->getResourceFactor(PIdx); 1455 RemainingCounts[PIdx] += (Factor * PI->Cycles); 1456 } 1457 } 1458 } 1459 1460 void ConvergingScheduler::SchedBoundary:: 1461 init(ScheduleDAGMI *dag, const TargetSchedModel *smodel, SchedRemainder *rem) { 1462 reset(); 1463 DAG = dag; 1464 SchedModel = smodel; 1465 Rem = rem; 1466 if (SchedModel->hasInstrSchedModel()) 1467 ExecutedResCounts.resize(SchedModel->getNumProcResourceKinds()); 1468 } 1469 1470 void ConvergingScheduler::initialize(ScheduleDAGMI *dag) { 1471 DAG = dag; 1472 SchedModel = DAG->getSchedModel(); 1473 TRI = DAG->TRI; 1474 1475 Rem.init(DAG, SchedModel); 1476 Top.init(DAG, SchedModel, &Rem); 1477 Bot.init(DAG, SchedModel, &Rem); 1478 1479 // Initialize resource counts. 1480 1481 // Initialize the HazardRecognizers. If itineraries don't exist, are empty, or 1482 // are disabled, then these HazardRecs will be disabled. 1483 const InstrItineraryData *Itin = SchedModel->getInstrItineraries(); 1484 const TargetMachine &TM = DAG->MF.getTarget(); 1485 Top.HazardRec = TM.getInstrInfo()->CreateTargetMIHazardRecognizer(Itin, DAG); 1486 Bot.HazardRec = TM.getInstrInfo()->CreateTargetMIHazardRecognizer(Itin, DAG); 1487 1488 assert((!ForceTopDown || !ForceBottomUp) && 1489 "-misched-topdown incompatible with -misched-bottomup"); 1490 } 1491 1492 void ConvergingScheduler::releaseTopNode(SUnit *SU) { 1493 if (SU->isScheduled) 1494 return; 1495 1496 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 1497 I != E; ++I) { 1498 if (I->isWeak()) 1499 continue; 1500 unsigned PredReadyCycle = I->getSUnit()->TopReadyCycle; 1501 unsigned Latency = I->getLatency(); 1502 #ifndef NDEBUG 1503 Top.MaxObservedLatency = std::max(Latency, Top.MaxObservedLatency); 1504 #endif 1505 if (SU->TopReadyCycle < PredReadyCycle + Latency) 1506 SU->TopReadyCycle = PredReadyCycle + Latency; 1507 } 1508 Top.releaseNode(SU, SU->TopReadyCycle); 1509 } 1510 1511 void ConvergingScheduler::releaseBottomNode(SUnit *SU) { 1512 if (SU->isScheduled) 1513 return; 1514 1515 assert(SU->getInstr() && "Scheduled SUnit must have instr"); 1516 1517 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 1518 I != E; ++I) { 1519 if (I->isWeak()) 1520 continue; 1521 unsigned SuccReadyCycle = I->getSUnit()->BotReadyCycle; 1522 unsigned Latency = I->getLatency(); 1523 #ifndef NDEBUG 1524 Bot.MaxObservedLatency = std::max(Latency, Bot.MaxObservedLatency); 1525 #endif 1526 if (SU->BotReadyCycle < SuccReadyCycle + Latency) 1527 SU->BotReadyCycle = SuccReadyCycle + Latency; 1528 } 1529 Bot.releaseNode(SU, SU->BotReadyCycle); 1530 } 1531 1532 void ConvergingScheduler::registerRoots() { 1533 Rem.CriticalPath = DAG->ExitSU.getDepth(); 1534 // Some roots may not feed into ExitSU. Check all of them in case. 1535 for (std::vector<SUnit*>::const_iterator 1536 I = Bot.Available.begin(), E = Bot.Available.end(); I != E; ++I) { 1537 if ((*I)->getDepth() > Rem.CriticalPath) 1538 Rem.CriticalPath = (*I)->getDepth(); 1539 } 1540 DEBUG(dbgs() << "Critical Path: " << Rem.CriticalPath << '\n'); 1541 } 1542 1543 /// Does this SU have a hazard within the current instruction group. 1544 /// 1545 /// The scheduler supports two modes of hazard recognition. The first is the 1546 /// ScheduleHazardRecognizer API. It is a fully general hazard recognizer that 1547 /// supports highly complicated in-order reservation tables 1548 /// (ScoreboardHazardRecognizer) and arbitraty target-specific logic. 1549 /// 1550 /// The second is a streamlined mechanism that checks for hazards based on 1551 /// simple counters that the scheduler itself maintains. It explicitly checks 1552 /// for instruction dispatch limitations, including the number of micro-ops that 1553 /// can dispatch per cycle. 1554 /// 1555 /// TODO: Also check whether the SU must start a new group. 1556 bool ConvergingScheduler::SchedBoundary::checkHazard(SUnit *SU) { 1557 if (HazardRec->isEnabled()) 1558 return HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard; 1559 1560 unsigned uops = SchedModel->getNumMicroOps(SU->getInstr()); 1561 if ((CurrMOps > 0) && (CurrMOps + uops > SchedModel->getIssueWidth())) { 1562 DEBUG(dbgs() << " SU(" << SU->NodeNum << ") uops=" 1563 << SchedModel->getNumMicroOps(SU->getInstr()) << '\n'); 1564 return true; 1565 } 1566 return false; 1567 } 1568 1569 // Find the unscheduled node in ReadySUs with the highest latency. 1570 unsigned ConvergingScheduler::SchedBoundary:: 1571 findMaxLatency(ArrayRef<SUnit*> ReadySUs) { 1572 SUnit *LateSU = 0; 1573 unsigned RemLatency = 0; 1574 for (ArrayRef<SUnit*>::iterator I = ReadySUs.begin(), E = ReadySUs.end(); 1575 I != E; ++I) { 1576 unsigned L = getUnscheduledLatency(*I); 1577 if (L > RemLatency) { 1578 RemLatency = L; 1579 LateSU = *I; 1580 } 1581 } 1582 if (LateSU) { 1583 DEBUG(dbgs() << Available.getName() << " RemLatency SU(" 1584 << LateSU->NodeNum << ") " << RemLatency << "c\n"); 1585 } 1586 return RemLatency; 1587 } 1588 1589 // Count resources in this zone and the remaining unscheduled 1590 // instruction. Return the max count, scaled. Set OtherCritIdx to the critical 1591 // resource index, or zero if the zone is issue limited. 1592 unsigned ConvergingScheduler::SchedBoundary:: 1593 getOtherResourceCount(unsigned &OtherCritIdx) { 1594 if (!SchedModel->hasInstrSchedModel()) 1595 return 0; 1596 1597 unsigned OtherCritCount = Rem->RemIssueCount 1598 + (RetiredMOps * SchedModel->getMicroOpFactor()); 1599 DEBUG(dbgs() << " " << Available.getName() << " + Remain MOps: " 1600 << OtherCritCount / SchedModel->getMicroOpFactor() << '\n'); 1601 OtherCritIdx = 0; 1602 for (unsigned PIdx = 1, PEnd = SchedModel->getNumProcResourceKinds(); 1603 PIdx != PEnd; ++PIdx) { 1604 unsigned OtherCount = getResourceCount(PIdx) + Rem->RemainingCounts[PIdx]; 1605 if (OtherCount > OtherCritCount) { 1606 OtherCritCount = OtherCount; 1607 OtherCritIdx = PIdx; 1608 } 1609 } 1610 if (OtherCritIdx) { 1611 DEBUG(dbgs() << " " << Available.getName() << " + Remain CritRes: " 1612 << OtherCritCount / SchedModel->getResourceFactor(OtherCritIdx) 1613 << " " << getResourceName(OtherCritIdx) << "\n"); 1614 } 1615 return OtherCritCount; 1616 } 1617 1618 /// Set the CandPolicy for this zone given the current resources and latencies 1619 /// inside and outside the zone. 1620 void ConvergingScheduler::SchedBoundary::setPolicy(CandPolicy &Policy, 1621 SchedBoundary &OtherZone) { 1622 // Now that potential stalls have been considered, apply preemptive heuristics 1623 // based on the the total latency and resources inside and outside this 1624 // zone. 1625 1626 // Compute remaining latency. We need this both to determine whether the 1627 // overall schedule has become latency-limited and whether the instructions 1628 // outside this zone are resource or latency limited. 1629 // 1630 // The "dependent" latency is updated incrementally during scheduling as the 1631 // max height/depth of scheduled nodes minus the cycles since it was 1632 // scheduled: 1633 // DLat = max (N.depth - (CurrCycle - N.ReadyCycle) for N in Zone 1634 // 1635 // The "independent" latency is the max ready queue depth: 1636 // ILat = max N.depth for N in Available|Pending 1637 // 1638 // RemainingLatency is the greater of independent and dependent latency. 1639 unsigned RemLatency = DependentLatency; 1640 RemLatency = std::max(RemLatency, findMaxLatency(Available.elements())); 1641 RemLatency = std::max(RemLatency, findMaxLatency(Pending.elements())); 1642 1643 // Compute the critical resource outside the zone. 1644 unsigned OtherCritIdx; 1645 unsigned OtherCount = OtherZone.getOtherResourceCount(OtherCritIdx); 1646 1647 bool OtherResLimited = false; 1648 if (SchedModel->hasInstrSchedModel()) { 1649 unsigned LFactor = SchedModel->getLatencyFactor(); 1650 OtherResLimited = (int)(OtherCount - (RemLatency * LFactor)) > (int)LFactor; 1651 } 1652 if (!OtherResLimited && (RemLatency + CurrCycle > Rem->CriticalPath)) { 1653 Policy.ReduceLatency |= true; 1654 DEBUG(dbgs() << " " << Available.getName() << " RemainingLatency " 1655 << RemLatency << " + " << CurrCycle << "c > CritPath " 1656 << Rem->CriticalPath << "\n"); 1657 } 1658 // If the same resource is limiting inside and outside the zone, do nothing. 1659 if (IsResourceLimited && OtherResLimited && (ZoneCritResIdx == OtherCritIdx)) 1660 return; 1661 1662 DEBUG( 1663 if (IsResourceLimited) { 1664 dbgs() << " " << Available.getName() << " ResourceLimited: " 1665 << getResourceName(ZoneCritResIdx) << "\n"; 1666 } 1667 if (OtherResLimited) 1668 dbgs() << " RemainingLimit: " << getResourceName(OtherCritIdx); 1669 if (!IsResourceLimited && !OtherResLimited) 1670 dbgs() << " Latency limited both directions.\n"); 1671 1672 if (IsResourceLimited && !Policy.ReduceResIdx) 1673 Policy.ReduceResIdx = ZoneCritResIdx; 1674 1675 if (OtherResLimited) 1676 Policy.DemandResIdx = OtherCritIdx; 1677 } 1678 1679 void ConvergingScheduler::SchedBoundary::releaseNode(SUnit *SU, 1680 unsigned ReadyCycle) { 1681 if (ReadyCycle < MinReadyCycle) 1682 MinReadyCycle = ReadyCycle; 1683 1684 // Check for interlocks first. For the purpose of other heuristics, an 1685 // instruction that cannot issue appears as if it's not in the ReadyQueue. 1686 bool IsBuffered = SchedModel->getMicroOpBufferSize() != 0; 1687 if ((!IsBuffered && ReadyCycle > CurrCycle) || checkHazard(SU)) 1688 Pending.push(SU); 1689 else 1690 Available.push(SU); 1691 1692 // Record this node as an immediate dependent of the scheduled node. 1693 NextSUs.insert(SU); 1694 } 1695 1696 /// Move the boundary of scheduled code by one cycle. 1697 void ConvergingScheduler::SchedBoundary::bumpCycle(unsigned NextCycle) { 1698 if (SchedModel->getMicroOpBufferSize() == 0) { 1699 assert(MinReadyCycle < UINT_MAX && "MinReadyCycle uninitialized"); 1700 if (MinReadyCycle > NextCycle) 1701 NextCycle = MinReadyCycle; 1702 } 1703 // Update the current micro-ops, which will issue in the next cycle. 1704 unsigned DecMOps = SchedModel->getIssueWidth() * (NextCycle - CurrCycle); 1705 CurrMOps = (CurrMOps <= DecMOps) ? 0 : CurrMOps - DecMOps; 1706 1707 // Decrement DependentLatency based on the next cycle. 1708 if ((NextCycle - CurrCycle) > DependentLatency) 1709 DependentLatency = 0; 1710 else 1711 DependentLatency -= (NextCycle - CurrCycle); 1712 1713 if (!HazardRec->isEnabled()) { 1714 // Bypass HazardRec virtual calls. 1715 CurrCycle = NextCycle; 1716 } 1717 else { 1718 // Bypass getHazardType calls in case of long latency. 1719 for (; CurrCycle != NextCycle; ++CurrCycle) { 1720 if (isTop()) 1721 HazardRec->AdvanceCycle(); 1722 else 1723 HazardRec->RecedeCycle(); 1724 } 1725 } 1726 CheckPending = true; 1727 unsigned LFactor = SchedModel->getLatencyFactor(); 1728 IsResourceLimited = 1729 (int)(getCriticalCount() - (getScheduledLatency() * LFactor)) 1730 > (int)LFactor; 1731 1732 DEBUG(dbgs() << "Cycle: " << CurrCycle << ' ' << Available.getName() << '\n'); 1733 } 1734 1735 void ConvergingScheduler::SchedBoundary::incExecutedResources(unsigned PIdx, 1736 unsigned Count) { 1737 ExecutedResCounts[PIdx] += Count; 1738 if (ExecutedResCounts[PIdx] > MaxExecutedResCount) 1739 MaxExecutedResCount = ExecutedResCounts[PIdx]; 1740 } 1741 1742 /// Add the given processor resource to this scheduled zone. 1743 /// 1744 /// \param Cycles indicates the number of consecutive (non-pipelined) cycles 1745 /// during which this resource is consumed. 1746 /// 1747 /// \return the next cycle at which the instruction may execute without 1748 /// oversubscribing resources. 1749 unsigned ConvergingScheduler::SchedBoundary:: 1750 countResource(unsigned PIdx, unsigned Cycles, unsigned ReadyCycle) { 1751 unsigned Factor = SchedModel->getResourceFactor(PIdx); 1752 unsigned Count = Factor * Cycles; 1753 DEBUG(dbgs() << " " << getResourceName(PIdx) 1754 << " +" << Cycles << "x" << Factor << "u\n"); 1755 1756 // Update Executed resources counts. 1757 incExecutedResources(PIdx, Count); 1758 assert(Rem->RemainingCounts[PIdx] >= Count && "resource double counted"); 1759 Rem->RemainingCounts[PIdx] -= Count; 1760 1761 // Check if this resource exceeds the current critical resource by a full 1762 // cycle. If so, it becomes the critical resource. 1763 if (ZoneCritResIdx != PIdx 1764 && ((int)(getResourceCount(PIdx) - getCriticalCount()) 1765 >= (int)SchedModel->getLatencyFactor())) { 1766 ZoneCritResIdx = PIdx; 1767 DEBUG(dbgs() << " *** Critical resource " 1768 << getResourceName(PIdx) << ": " 1769 << getResourceCount(PIdx) / SchedModel->getLatencyFactor() << "c\n"); 1770 } 1771 // TODO: We don't yet model reserved resources. It's not hard though. 1772 return CurrCycle; 1773 } 1774 1775 /// Move the boundary of scheduled code by one SUnit. 1776 void ConvergingScheduler::SchedBoundary::bumpNode(SUnit *SU) { 1777 // Update the reservation table. 1778 if (HazardRec->isEnabled()) { 1779 if (!isTop() && SU->isCall) { 1780 // Calls are scheduled with their preceding instructions. For bottom-up 1781 // scheduling, clear the pipeline state before emitting. 1782 HazardRec->Reset(); 1783 } 1784 HazardRec->EmitInstruction(SU); 1785 } 1786 const MCSchedClassDesc *SC = DAG->getSchedClass(SU); 1787 unsigned IncMOps = SchedModel->getNumMicroOps(SU->getInstr()); 1788 CurrMOps += IncMOps; 1789 // checkHazard prevents scheduling multiple instructions per cycle that exceed 1790 // issue width. However, we commonly reach the maximum. In this case 1791 // opportunistically bump the cycle to avoid uselessly checking everything in 1792 // the readyQ. Furthermore, a single instruction may produce more than one 1793 // cycle's worth of micro-ops. 1794 // 1795 // TODO: Also check if this SU must end a dispatch group. 1796 unsigned NextCycle = CurrCycle; 1797 if (CurrMOps >= SchedModel->getIssueWidth()) { 1798 ++NextCycle; 1799 DEBUG(dbgs() << " *** Max MOps " << CurrMOps 1800 << " at cycle " << CurrCycle << '\n'); 1801 } 1802 unsigned ReadyCycle = (isTop() ? SU->TopReadyCycle : SU->BotReadyCycle); 1803 DEBUG(dbgs() << " Ready @" << ReadyCycle << "c\n"); 1804 1805 switch (SchedModel->getMicroOpBufferSize()) { 1806 case 0: 1807 assert(ReadyCycle <= CurrCycle && "Broken PendingQueue"); 1808 break; 1809 case 1: 1810 if (ReadyCycle > NextCycle) { 1811 NextCycle = ReadyCycle; 1812 DEBUG(dbgs() << " *** Stall until: " << ReadyCycle << "\n"); 1813 } 1814 break; 1815 default: 1816 // We don't currently model the OOO reorder buffer, so consider all 1817 // scheduled MOps to be "retired". 1818 break; 1819 } 1820 RetiredMOps += IncMOps; 1821 1822 // Update resource counts and critical resource. 1823 if (SchedModel->hasInstrSchedModel()) { 1824 unsigned DecRemIssue = IncMOps * SchedModel->getMicroOpFactor(); 1825 assert(Rem->RemIssueCount >= DecRemIssue && "MOps double counted"); 1826 Rem->RemIssueCount -= DecRemIssue; 1827 if (ZoneCritResIdx) { 1828 // Scale scheduled micro-ops for comparing with the critical resource. 1829 unsigned ScaledMOps = 1830 RetiredMOps * SchedModel->getMicroOpFactor(); 1831 1832 // If scaled micro-ops are now more than the previous critical resource by 1833 // a full cycle, then micro-ops issue becomes critical. 1834 if ((int)(ScaledMOps - getResourceCount(ZoneCritResIdx)) 1835 >= (int)SchedModel->getLatencyFactor()) { 1836 ZoneCritResIdx = 0; 1837 DEBUG(dbgs() << " *** Critical resource NumMicroOps: " 1838 << ScaledMOps / SchedModel->getLatencyFactor() << "c\n"); 1839 } 1840 } 1841 for (TargetSchedModel::ProcResIter 1842 PI = SchedModel->getWriteProcResBegin(SC), 1843 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) { 1844 unsigned RCycle = 1845 countResource(PI->ProcResourceIdx, PI->Cycles, ReadyCycle); 1846 if (RCycle > NextCycle) 1847 NextCycle = RCycle; 1848 } 1849 } 1850 // Update ExpectedLatency and DependentLatency. 1851 unsigned &TopLatency = isTop() ? ExpectedLatency : DependentLatency; 1852 unsigned &BotLatency = isTop() ? DependentLatency : ExpectedLatency; 1853 if (SU->getDepth() > TopLatency) { 1854 TopLatency = SU->getDepth(); 1855 DEBUG(dbgs() << " " << Available.getName() 1856 << " TopLatency SU(" << SU->NodeNum << ") " << TopLatency << "c\n"); 1857 } 1858 if (SU->getHeight() > BotLatency) { 1859 BotLatency = SU->getHeight(); 1860 DEBUG(dbgs() << " " << Available.getName() 1861 << " BotLatency SU(" << SU->NodeNum << ") " << BotLatency << "c\n"); 1862 } 1863 // If we stall for any reason, bump the cycle. 1864 if (NextCycle > CurrCycle) { 1865 bumpCycle(NextCycle); 1866 } 1867 else { 1868 // After updating ZoneCritResIdx and ExpectedLatency, check if we're 1869 // resource limited. If a stall occured, bumpCycle does this. 1870 unsigned LFactor = SchedModel->getLatencyFactor(); 1871 IsResourceLimited = 1872 (int)(getCriticalCount() - (getScheduledLatency() * LFactor)) 1873 > (int)LFactor; 1874 } 1875 DEBUG(dumpScheduledState()); 1876 } 1877 1878 /// Release pending ready nodes in to the available queue. This makes them 1879 /// visible to heuristics. 1880 void ConvergingScheduler::SchedBoundary::releasePending() { 1881 // If the available queue is empty, it is safe to reset MinReadyCycle. 1882 if (Available.empty()) 1883 MinReadyCycle = UINT_MAX; 1884 1885 // Check to see if any of the pending instructions are ready to issue. If 1886 // so, add them to the available queue. 1887 bool IsBuffered = SchedModel->getMicroOpBufferSize() != 0; 1888 for (unsigned i = 0, e = Pending.size(); i != e; ++i) { 1889 SUnit *SU = *(Pending.begin()+i); 1890 unsigned ReadyCycle = isTop() ? SU->TopReadyCycle : SU->BotReadyCycle; 1891 1892 if (ReadyCycle < MinReadyCycle) 1893 MinReadyCycle = ReadyCycle; 1894 1895 if (!IsBuffered && ReadyCycle > CurrCycle) 1896 continue; 1897 1898 if (checkHazard(SU)) 1899 continue; 1900 1901 Available.push(SU); 1902 Pending.remove(Pending.begin()+i); 1903 --i; --e; 1904 } 1905 DEBUG(if (!Pending.empty()) Pending.dump()); 1906 CheckPending = false; 1907 } 1908 1909 /// Remove SU from the ready set for this boundary. 1910 void ConvergingScheduler::SchedBoundary::removeReady(SUnit *SU) { 1911 if (Available.isInQueue(SU)) 1912 Available.remove(Available.find(SU)); 1913 else { 1914 assert(Pending.isInQueue(SU) && "bad ready count"); 1915 Pending.remove(Pending.find(SU)); 1916 } 1917 } 1918 1919 /// If this queue only has one ready candidate, return it. As a side effect, 1920 /// defer any nodes that now hit a hazard, and advance the cycle until at least 1921 /// one node is ready. If multiple instructions are ready, return NULL. 1922 SUnit *ConvergingScheduler::SchedBoundary::pickOnlyChoice() { 1923 if (CheckPending) 1924 releasePending(); 1925 1926 if (CurrMOps > 0) { 1927 // Defer any ready instrs that now have a hazard. 1928 for (ReadyQueue::iterator I = Available.begin(); I != Available.end();) { 1929 if (checkHazard(*I)) { 1930 Pending.push(*I); 1931 I = Available.remove(I); 1932 continue; 1933 } 1934 ++I; 1935 } 1936 } 1937 for (unsigned i = 0; Available.empty(); ++i) { 1938 assert(i <= (HazardRec->getMaxLookAhead() + MaxObservedLatency) && 1939 "permanent hazard"); (void)i; 1940 bumpCycle(CurrCycle + 1); 1941 releasePending(); 1942 } 1943 if (Available.size() == 1) 1944 return *Available.begin(); 1945 return NULL; 1946 } 1947 1948 #ifndef NDEBUG 1949 // This is useful information to dump after bumpNode. 1950 // Note that the Queue contents are more useful before pickNodeFromQueue. 1951 void ConvergingScheduler::SchedBoundary::dumpScheduledState() { 1952 unsigned ResFactor; 1953 unsigned ResCount; 1954 if (ZoneCritResIdx) { 1955 ResFactor = SchedModel->getResourceFactor(ZoneCritResIdx); 1956 ResCount = getResourceCount(ZoneCritResIdx); 1957 } 1958 else { 1959 ResFactor = SchedModel->getMicroOpFactor(); 1960 ResCount = RetiredMOps * SchedModel->getMicroOpFactor(); 1961 } 1962 unsigned LFactor = SchedModel->getLatencyFactor(); 1963 dbgs() << Available.getName() << " @" << CurrCycle << "c\n" 1964 << " Retired: " << RetiredMOps; 1965 dbgs() << "\n Executed: " << getExecutedCount() / LFactor << "c"; 1966 dbgs() << "\n Critical: " << ResCount / LFactor << "c, " 1967 << ResCount / ResFactor << " " << getResourceName(ZoneCritResIdx) 1968 << "\n ExpectedLatency: " << ExpectedLatency << "c\n" 1969 << (IsResourceLimited ? " - Resource" : " - Latency") 1970 << " limited.\n"; 1971 } 1972 #endif 1973 1974 void ConvergingScheduler::SchedCandidate:: 1975 initResourceDelta(const ScheduleDAGMI *DAG, 1976 const TargetSchedModel *SchedModel) { 1977 if (!Policy.ReduceResIdx && !Policy.DemandResIdx) 1978 return; 1979 1980 const MCSchedClassDesc *SC = DAG->getSchedClass(SU); 1981 for (TargetSchedModel::ProcResIter 1982 PI = SchedModel->getWriteProcResBegin(SC), 1983 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) { 1984 if (PI->ProcResourceIdx == Policy.ReduceResIdx) 1985 ResDelta.CritResources += PI->Cycles; 1986 if (PI->ProcResourceIdx == Policy.DemandResIdx) 1987 ResDelta.DemandedResources += PI->Cycles; 1988 } 1989 } 1990 1991 1992 /// Return true if this heuristic determines order. 1993 static bool tryLess(int TryVal, int CandVal, 1994 ConvergingScheduler::SchedCandidate &TryCand, 1995 ConvergingScheduler::SchedCandidate &Cand, 1996 ConvergingScheduler::CandReason Reason) { 1997 if (TryVal < CandVal) { 1998 TryCand.Reason = Reason; 1999 return true; 2000 } 2001 if (TryVal > CandVal) { 2002 if (Cand.Reason > Reason) 2003 Cand.Reason = Reason; 2004 return true; 2005 } 2006 Cand.setRepeat(Reason); 2007 return false; 2008 } 2009 2010 static bool tryGreater(int TryVal, int CandVal, 2011 ConvergingScheduler::SchedCandidate &TryCand, 2012 ConvergingScheduler::SchedCandidate &Cand, 2013 ConvergingScheduler::CandReason Reason) { 2014 if (TryVal > CandVal) { 2015 TryCand.Reason = Reason; 2016 return true; 2017 } 2018 if (TryVal < CandVal) { 2019 if (Cand.Reason > Reason) 2020 Cand.Reason = Reason; 2021 return true; 2022 } 2023 Cand.setRepeat(Reason); 2024 return false; 2025 } 2026 2027 static unsigned getWeakLeft(const SUnit *SU, bool isTop) { 2028 return (isTop) ? SU->WeakPredsLeft : SU->WeakSuccsLeft; 2029 } 2030 2031 /// Minimize physical register live ranges. Regalloc wants them adjacent to 2032 /// their physreg def/use. 2033 /// 2034 /// FIXME: This is an unnecessary check on the critical path. Most are root/leaf 2035 /// copies which can be prescheduled. The rest (e.g. x86 MUL) could be bundled 2036 /// with the operation that produces or consumes the physreg. We'll do this when 2037 /// regalloc has support for parallel copies. 2038 static int biasPhysRegCopy(const SUnit *SU, bool isTop) { 2039 const MachineInstr *MI = SU->getInstr(); 2040 if (!MI->isCopy()) 2041 return 0; 2042 2043 unsigned ScheduledOper = isTop ? 1 : 0; 2044 unsigned UnscheduledOper = isTop ? 0 : 1; 2045 // If we have already scheduled the physreg produce/consumer, immediately 2046 // schedule the copy. 2047 if (TargetRegisterInfo::isPhysicalRegister( 2048 MI->getOperand(ScheduledOper).getReg())) 2049 return 1; 2050 // If the physreg is at the boundary, defer it. Otherwise schedule it 2051 // immediately to free the dependent. We can hoist the copy later. 2052 bool AtBoundary = isTop ? !SU->NumSuccsLeft : !SU->NumPredsLeft; 2053 if (TargetRegisterInfo::isPhysicalRegister( 2054 MI->getOperand(UnscheduledOper).getReg())) 2055 return AtBoundary ? -1 : 1; 2056 return 0; 2057 } 2058 2059 /// Apply a set of heursitics to a new candidate. Heuristics are currently 2060 /// hierarchical. This may be more efficient than a graduated cost model because 2061 /// we don't need to evaluate all aspects of the model for each node in the 2062 /// queue. But it's really done to make the heuristics easier to debug and 2063 /// statistically analyze. 2064 /// 2065 /// \param Cand provides the policy and current best candidate. 2066 /// \param TryCand refers to the next SUnit candidate, otherwise uninitialized. 2067 /// \param Zone describes the scheduled zone that we are extending. 2068 /// \param RPTracker describes reg pressure within the scheduled zone. 2069 /// \param TempTracker is a scratch pressure tracker to reuse in queries. 2070 void ConvergingScheduler::tryCandidate(SchedCandidate &Cand, 2071 SchedCandidate &TryCand, 2072 SchedBoundary &Zone, 2073 const RegPressureTracker &RPTracker, 2074 RegPressureTracker &TempTracker) { 2075 2076 // Always initialize TryCand's RPDelta. 2077 TempTracker.getMaxPressureDelta(TryCand.SU->getInstr(), TryCand.RPDelta, 2078 DAG->getRegionCriticalPSets(), 2079 DAG->getRegPressure().MaxSetPressure); 2080 2081 // Initialize the candidate if needed. 2082 if (!Cand.isValid()) { 2083 TryCand.Reason = NodeOrder; 2084 return; 2085 } 2086 2087 if (tryGreater(biasPhysRegCopy(TryCand.SU, Zone.isTop()), 2088 biasPhysRegCopy(Cand.SU, Zone.isTop()), 2089 TryCand, Cand, PhysRegCopy)) 2090 return; 2091 2092 // Avoid exceeding the target's limit. 2093 if (tryLess(TryCand.RPDelta.Excess.UnitIncrease, 2094 Cand.RPDelta.Excess.UnitIncrease, TryCand, Cand, RegExcess)) 2095 return; 2096 2097 // Avoid increasing the max critical pressure in the scheduled region. 2098 if (tryLess(TryCand.RPDelta.CriticalMax.UnitIncrease, 2099 Cand.RPDelta.CriticalMax.UnitIncrease, 2100 TryCand, Cand, RegCritical)) 2101 return; 2102 2103 // Keep clustered nodes together to encourage downstream peephole 2104 // optimizations which may reduce resource requirements. 2105 // 2106 // This is a best effort to set things up for a post-RA pass. Optimizations 2107 // like generating loads of multiple registers should ideally be done within 2108 // the scheduler pass by combining the loads during DAG postprocessing. 2109 const SUnit *NextClusterSU = 2110 Zone.isTop() ? DAG->getNextClusterSucc() : DAG->getNextClusterPred(); 2111 if (tryGreater(TryCand.SU == NextClusterSU, Cand.SU == NextClusterSU, 2112 TryCand, Cand, Cluster)) 2113 return; 2114 2115 // Weak edges are for clustering and other constraints. 2116 // 2117 // Deferring TryCand here does not change Cand's reason. This is good in the 2118 // sense that a bad candidate shouldn't affect a previous candidate's 2119 // goodness, but bad in that it is assymetric and depends on queue order. 2120 CandReason OrigReason = Cand.Reason; 2121 if (tryLess(getWeakLeft(TryCand.SU, Zone.isTop()), 2122 getWeakLeft(Cand.SU, Zone.isTop()), 2123 TryCand, Cand, Weak)) { 2124 Cand.Reason = OrigReason; 2125 return; 2126 } 2127 // Avoid critical resource consumption and balance the schedule. 2128 TryCand.initResourceDelta(DAG, SchedModel); 2129 if (tryLess(TryCand.ResDelta.CritResources, Cand.ResDelta.CritResources, 2130 TryCand, Cand, ResourceReduce)) 2131 return; 2132 if (tryGreater(TryCand.ResDelta.DemandedResources, 2133 Cand.ResDelta.DemandedResources, 2134 TryCand, Cand, ResourceDemand)) 2135 return; 2136 2137 // Avoid serializing long latency dependence chains. 2138 if (Cand.Policy.ReduceLatency) { 2139 if (Zone.isTop()) { 2140 if (Cand.SU->getDepth() > Zone.getScheduledLatency()) { 2141 if (tryLess(TryCand.SU->getDepth(), Cand.SU->getDepth(), 2142 TryCand, Cand, TopDepthReduce)) 2143 return; 2144 } 2145 if (tryGreater(TryCand.SU->getHeight(), Cand.SU->getHeight(), 2146 TryCand, Cand, TopPathReduce)) 2147 return; 2148 } 2149 else { 2150 if (Cand.SU->getHeight() > Zone.getScheduledLatency()) { 2151 if (tryLess(TryCand.SU->getHeight(), Cand.SU->getHeight(), 2152 TryCand, Cand, BotHeightReduce)) 2153 return; 2154 } 2155 if (tryGreater(TryCand.SU->getDepth(), Cand.SU->getDepth(), 2156 TryCand, Cand, BotPathReduce)) 2157 return; 2158 } 2159 } 2160 2161 // Avoid increasing the max pressure of the entire region. 2162 if (tryLess(TryCand.RPDelta.CurrentMax.UnitIncrease, 2163 Cand.RPDelta.CurrentMax.UnitIncrease, TryCand, Cand, SingleMax)) 2164 return; 2165 2166 // Prefer immediate defs/users of the last scheduled instruction. This is a 2167 // local pressure avoidance strategy that also makes the machine code 2168 // readable. 2169 if (tryGreater(Zone.NextSUs.count(TryCand.SU), Zone.NextSUs.count(Cand.SU), 2170 TryCand, Cand, NextDefUse)) 2171 return; 2172 2173 // Fall through to original instruction order. 2174 if ((Zone.isTop() && TryCand.SU->NodeNum < Cand.SU->NodeNum) 2175 || (!Zone.isTop() && TryCand.SU->NodeNum > Cand.SU->NodeNum)) { 2176 TryCand.Reason = NodeOrder; 2177 } 2178 } 2179 2180 /// pickNodeFromQueue helper that returns true if the LHS reg pressure effect is 2181 /// more desirable than RHS from scheduling standpoint. 2182 static bool compareRPDelta(const RegPressureDelta &LHS, 2183 const RegPressureDelta &RHS) { 2184 // Compare each component of pressure in decreasing order of importance 2185 // without checking if any are valid. Invalid PressureElements are assumed to 2186 // have UnitIncrease==0, so are neutral. 2187 2188 // Avoid increasing the max critical pressure in the scheduled region. 2189 if (LHS.Excess.UnitIncrease != RHS.Excess.UnitIncrease) { 2190 DEBUG(dbgs() << " RP excess top - bot: " 2191 << (LHS.Excess.UnitIncrease - RHS.Excess.UnitIncrease) << '\n'); 2192 return LHS.Excess.UnitIncrease < RHS.Excess.UnitIncrease; 2193 } 2194 // Avoid increasing the max critical pressure in the scheduled region. 2195 if (LHS.CriticalMax.UnitIncrease != RHS.CriticalMax.UnitIncrease) { 2196 DEBUG(dbgs() << " RP critical top - bot: " 2197 << (LHS.CriticalMax.UnitIncrease - RHS.CriticalMax.UnitIncrease) 2198 << '\n'); 2199 return LHS.CriticalMax.UnitIncrease < RHS.CriticalMax.UnitIncrease; 2200 } 2201 // Avoid increasing the max pressure of the entire region. 2202 if (LHS.CurrentMax.UnitIncrease != RHS.CurrentMax.UnitIncrease) { 2203 DEBUG(dbgs() << " RP current top - bot: " 2204 << (LHS.CurrentMax.UnitIncrease - RHS.CurrentMax.UnitIncrease) 2205 << '\n'); 2206 return LHS.CurrentMax.UnitIncrease < RHS.CurrentMax.UnitIncrease; 2207 } 2208 return false; 2209 } 2210 2211 #ifndef NDEBUG 2212 const char *ConvergingScheduler::getReasonStr( 2213 ConvergingScheduler::CandReason Reason) { 2214 switch (Reason) { 2215 case NoCand: return "NOCAND "; 2216 case PhysRegCopy: return "PREG-COPY"; 2217 case RegExcess: return "REG-EXCESS"; 2218 case RegCritical: return "REG-CRIT "; 2219 case Cluster: return "CLUSTER "; 2220 case Weak: return "WEAK "; 2221 case SingleMax: return "REG-MAX "; 2222 case ResourceReduce: return "RES-REDUCE"; 2223 case ResourceDemand: return "RES-DEMAND"; 2224 case TopDepthReduce: return "TOP-DEPTH "; 2225 case TopPathReduce: return "TOP-PATH "; 2226 case BotHeightReduce:return "BOT-HEIGHT"; 2227 case BotPathReduce: return "BOT-PATH "; 2228 case NextDefUse: return "DEF-USE "; 2229 case NodeOrder: return "ORDER "; 2230 }; 2231 llvm_unreachable("Unknown reason!"); 2232 } 2233 2234 void ConvergingScheduler::traceCandidate(const SchedCandidate &Cand) { 2235 PressureElement P; 2236 unsigned ResIdx = 0; 2237 unsigned Latency = 0; 2238 switch (Cand.Reason) { 2239 default: 2240 break; 2241 case RegExcess: 2242 P = Cand.RPDelta.Excess; 2243 break; 2244 case RegCritical: 2245 P = Cand.RPDelta.CriticalMax; 2246 break; 2247 case SingleMax: 2248 P = Cand.RPDelta.CurrentMax; 2249 break; 2250 case ResourceReduce: 2251 ResIdx = Cand.Policy.ReduceResIdx; 2252 break; 2253 case ResourceDemand: 2254 ResIdx = Cand.Policy.DemandResIdx; 2255 break; 2256 case TopDepthReduce: 2257 Latency = Cand.SU->getDepth(); 2258 break; 2259 case TopPathReduce: 2260 Latency = Cand.SU->getHeight(); 2261 break; 2262 case BotHeightReduce: 2263 Latency = Cand.SU->getHeight(); 2264 break; 2265 case BotPathReduce: 2266 Latency = Cand.SU->getDepth(); 2267 break; 2268 } 2269 dbgs() << " SU(" << Cand.SU->NodeNum << ") " << getReasonStr(Cand.Reason); 2270 if (P.isValid()) 2271 dbgs() << " " << TRI->getRegPressureSetName(P.PSetID) 2272 << ":" << P.UnitIncrease << " "; 2273 else 2274 dbgs() << " "; 2275 if (ResIdx) 2276 dbgs() << " " << SchedModel->getProcResource(ResIdx)->Name << " "; 2277 else 2278 dbgs() << " "; 2279 if (Latency) 2280 dbgs() << " " << Latency << " cycles "; 2281 else 2282 dbgs() << " "; 2283 dbgs() << '\n'; 2284 } 2285 #endif 2286 2287 /// Pick the best candidate from the top queue. 2288 /// 2289 /// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during 2290 /// DAG building. To adjust for the current scheduling location we need to 2291 /// maintain the number of vreg uses remaining to be top-scheduled. 2292 void ConvergingScheduler::pickNodeFromQueue(SchedBoundary &Zone, 2293 const RegPressureTracker &RPTracker, 2294 SchedCandidate &Cand) { 2295 ReadyQueue &Q = Zone.Available; 2296 2297 DEBUG(Q.dump()); 2298 2299 // getMaxPressureDelta temporarily modifies the tracker. 2300 RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker); 2301 2302 for (ReadyQueue::iterator I = Q.begin(), E = Q.end(); I != E; ++I) { 2303 2304 SchedCandidate TryCand(Cand.Policy); 2305 TryCand.SU = *I; 2306 tryCandidate(Cand, TryCand, Zone, RPTracker, TempTracker); 2307 if (TryCand.Reason != NoCand) { 2308 // Initialize resource delta if needed in case future heuristics query it. 2309 if (TryCand.ResDelta == SchedResourceDelta()) 2310 TryCand.initResourceDelta(DAG, SchedModel); 2311 Cand.setBest(TryCand); 2312 DEBUG(traceCandidate(Cand)); 2313 } 2314 } 2315 } 2316 2317 static void tracePick(const ConvergingScheduler::SchedCandidate &Cand, 2318 bool IsTop) { 2319 DEBUG(dbgs() << "Pick " << (IsTop ? "Top " : "Bot ") 2320 << ConvergingScheduler::getReasonStr(Cand.Reason) << '\n'); 2321 } 2322 2323 /// Pick the best candidate node from either the top or bottom queue. 2324 SUnit *ConvergingScheduler::pickNodeBidirectional(bool &IsTopNode) { 2325 // Schedule as far as possible in the direction of no choice. This is most 2326 // efficient, but also provides the best heuristics for CriticalPSets. 2327 if (SUnit *SU = Bot.pickOnlyChoice()) { 2328 IsTopNode = false; 2329 DEBUG(dbgs() << "Pick Bot NOCAND\n"); 2330 return SU; 2331 } 2332 if (SUnit *SU = Top.pickOnlyChoice()) { 2333 IsTopNode = true; 2334 DEBUG(dbgs() << "Pick Top NOCAND\n"); 2335 return SU; 2336 } 2337 CandPolicy NoPolicy; 2338 SchedCandidate BotCand(NoPolicy); 2339 SchedCandidate TopCand(NoPolicy); 2340 Bot.setPolicy(BotCand.Policy, Top); 2341 Top.setPolicy(TopCand.Policy, Bot); 2342 2343 // Prefer bottom scheduling when heuristics are silent. 2344 pickNodeFromQueue(Bot, DAG->getBotRPTracker(), BotCand); 2345 assert(BotCand.Reason != NoCand && "failed to find the first candidate"); 2346 2347 // If either Q has a single candidate that provides the least increase in 2348 // Excess pressure, we can immediately schedule from that Q. 2349 // 2350 // RegionCriticalPSets summarizes the pressure within the scheduled region and 2351 // affects picking from either Q. If scheduling in one direction must 2352 // increase pressure for one of the excess PSets, then schedule in that 2353 // direction first to provide more freedom in the other direction. 2354 if ((BotCand.Reason == RegExcess && !BotCand.isRepeat(RegExcess)) 2355 || (BotCand.Reason == RegCritical 2356 && !BotCand.isRepeat(RegCritical))) 2357 { 2358 IsTopNode = false; 2359 tracePick(BotCand, IsTopNode); 2360 return BotCand.SU; 2361 } 2362 // Check if the top Q has a better candidate. 2363 pickNodeFromQueue(Top, DAG->getTopRPTracker(), TopCand); 2364 assert(TopCand.Reason != NoCand && "failed to find the first candidate"); 2365 2366 // Check for a salient pressure difference and pick the best from either side. 2367 if (compareRPDelta(TopCand.RPDelta, BotCand.RPDelta)) { 2368 IsTopNode = true; 2369 tracePick(TopCand, IsTopNode); 2370 return TopCand.SU; 2371 } 2372 // Choose the queue with the most important (lowest enum) reason. 2373 if (TopCand.Reason < BotCand.Reason) { 2374 IsTopNode = true; 2375 tracePick(TopCand, IsTopNode); 2376 return TopCand.SU; 2377 } 2378 // Otherwise prefer the bottom candidate, in node order if all else failed. 2379 IsTopNode = false; 2380 tracePick(BotCand, IsTopNode); 2381 return BotCand.SU; 2382 } 2383 2384 /// Pick the best node to balance the schedule. Implements MachineSchedStrategy. 2385 SUnit *ConvergingScheduler::pickNode(bool &IsTopNode) { 2386 if (DAG->top() == DAG->bottom()) { 2387 assert(Top.Available.empty() && Top.Pending.empty() && 2388 Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage"); 2389 return NULL; 2390 } 2391 SUnit *SU; 2392 do { 2393 if (ForceTopDown) { 2394 SU = Top.pickOnlyChoice(); 2395 if (!SU) { 2396 CandPolicy NoPolicy; 2397 SchedCandidate TopCand(NoPolicy); 2398 pickNodeFromQueue(Top, DAG->getTopRPTracker(), TopCand); 2399 assert(TopCand.Reason != NoCand && "failed to find the first candidate"); 2400 SU = TopCand.SU; 2401 } 2402 IsTopNode = true; 2403 } 2404 else if (ForceBottomUp) { 2405 SU = Bot.pickOnlyChoice(); 2406 if (!SU) { 2407 CandPolicy NoPolicy; 2408 SchedCandidate BotCand(NoPolicy); 2409 pickNodeFromQueue(Bot, DAG->getBotRPTracker(), BotCand); 2410 assert(BotCand.Reason != NoCand && "failed to find the first candidate"); 2411 SU = BotCand.SU; 2412 } 2413 IsTopNode = false; 2414 } 2415 else { 2416 SU = pickNodeBidirectional(IsTopNode); 2417 } 2418 } while (SU->isScheduled); 2419 2420 if (SU->isTopReady()) 2421 Top.removeReady(SU); 2422 if (SU->isBottomReady()) 2423 Bot.removeReady(SU); 2424 2425 DEBUG(dbgs() << "Scheduling SU(" << SU->NodeNum << ") " << *SU->getInstr()); 2426 return SU; 2427 } 2428 2429 void ConvergingScheduler::reschedulePhysRegCopies(SUnit *SU, bool isTop) { 2430 2431 MachineBasicBlock::iterator InsertPos = SU->getInstr(); 2432 if (!isTop) 2433 ++InsertPos; 2434 SmallVectorImpl<SDep> &Deps = isTop ? SU->Preds : SU->Succs; 2435 2436 // Find already scheduled copies with a single physreg dependence and move 2437 // them just above the scheduled instruction. 2438 for (SmallVectorImpl<SDep>::iterator I = Deps.begin(), E = Deps.end(); 2439 I != E; ++I) { 2440 if (I->getKind() != SDep::Data || !TRI->isPhysicalRegister(I->getReg())) 2441 continue; 2442 SUnit *DepSU = I->getSUnit(); 2443 if (isTop ? DepSU->Succs.size() > 1 : DepSU->Preds.size() > 1) 2444 continue; 2445 MachineInstr *Copy = DepSU->getInstr(); 2446 if (!Copy->isCopy()) 2447 continue; 2448 DEBUG(dbgs() << " Rescheduling physreg copy "; 2449 I->getSUnit()->dump(DAG)); 2450 DAG->moveInstruction(Copy, InsertPos); 2451 } 2452 } 2453 2454 /// Update the scheduler's state after scheduling a node. This is the same node 2455 /// that was just returned by pickNode(). However, ScheduleDAGMI needs to update 2456 /// it's state based on the current cycle before MachineSchedStrategy does. 2457 /// 2458 /// FIXME: Eventually, we may bundle physreg copies rather than rescheduling 2459 /// them here. See comments in biasPhysRegCopy. 2460 void ConvergingScheduler::schedNode(SUnit *SU, bool IsTopNode) { 2461 if (IsTopNode) { 2462 SU->TopReadyCycle = std::max(SU->TopReadyCycle, Top.CurrCycle); 2463 Top.bumpNode(SU); 2464 if (SU->hasPhysRegUses) 2465 reschedulePhysRegCopies(SU, true); 2466 } 2467 else { 2468 SU->BotReadyCycle = std::max(SU->BotReadyCycle, Bot.CurrCycle); 2469 Bot.bumpNode(SU); 2470 if (SU->hasPhysRegDefs) 2471 reschedulePhysRegCopies(SU, false); 2472 } 2473 } 2474 2475 /// Create the standard converging machine scheduler. This will be used as the 2476 /// default scheduler if the target does not set a default. 2477 static ScheduleDAGInstrs *createConvergingSched(MachineSchedContext *C) { 2478 assert((!ForceTopDown || !ForceBottomUp) && 2479 "-misched-topdown incompatible with -misched-bottomup"); 2480 ScheduleDAGMI *DAG = new ScheduleDAGMI(C, new ConvergingScheduler()); 2481 // Register DAG post-processors. 2482 // 2483 // FIXME: extend the mutation API to allow earlier mutations to instantiate 2484 // data and pass it to later mutations. Have a single mutation that gathers 2485 // the interesting nodes in one pass. 2486 DAG->addMutation(new CopyConstrain(DAG->TII, DAG->TRI)); 2487 if (EnableLoadCluster) 2488 DAG->addMutation(new LoadClusterMutation(DAG->TII, DAG->TRI)); 2489 if (EnableMacroFusion) 2490 DAG->addMutation(new MacroFusion(DAG->TII)); 2491 return DAG; 2492 } 2493 static MachineSchedRegistry 2494 ConvergingSchedRegistry("converge", "Standard converging scheduler.", 2495 createConvergingSched); 2496 2497 //===----------------------------------------------------------------------===// 2498 // ILP Scheduler. Currently for experimental analysis of heuristics. 2499 //===----------------------------------------------------------------------===// 2500 2501 namespace { 2502 /// \brief Order nodes by the ILP metric. 2503 struct ILPOrder { 2504 const SchedDFSResult *DFSResult; 2505 const BitVector *ScheduledTrees; 2506 bool MaximizeILP; 2507 2508 ILPOrder(bool MaxILP): DFSResult(0), ScheduledTrees(0), MaximizeILP(MaxILP) {} 2509 2510 /// \brief Apply a less-than relation on node priority. 2511 /// 2512 /// (Return true if A comes after B in the Q.) 2513 bool operator()(const SUnit *A, const SUnit *B) const { 2514 unsigned SchedTreeA = DFSResult->getSubtreeID(A); 2515 unsigned SchedTreeB = DFSResult->getSubtreeID(B); 2516 if (SchedTreeA != SchedTreeB) { 2517 // Unscheduled trees have lower priority. 2518 if (ScheduledTrees->test(SchedTreeA) != ScheduledTrees->test(SchedTreeB)) 2519 return ScheduledTrees->test(SchedTreeB); 2520 2521 // Trees with shallower connections have have lower priority. 2522 if (DFSResult->getSubtreeLevel(SchedTreeA) 2523 != DFSResult->getSubtreeLevel(SchedTreeB)) { 2524 return DFSResult->getSubtreeLevel(SchedTreeA) 2525 < DFSResult->getSubtreeLevel(SchedTreeB); 2526 } 2527 } 2528 if (MaximizeILP) 2529 return DFSResult->getILP(A) < DFSResult->getILP(B); 2530 else 2531 return DFSResult->getILP(A) > DFSResult->getILP(B); 2532 } 2533 }; 2534 2535 /// \brief Schedule based on the ILP metric. 2536 class ILPScheduler : public MachineSchedStrategy { 2537 /// In case all subtrees are eventually connected to a common root through 2538 /// data dependence (e.g. reduction), place an upper limit on their size. 2539 /// 2540 /// FIXME: A subtree limit is generally good, but in the situation commented 2541 /// above, where multiple similar subtrees feed a common root, we should 2542 /// only split at a point where the resulting subtrees will be balanced. 2543 /// (a motivating test case must be found). 2544 static const unsigned SubtreeLimit = 16; 2545 2546 ScheduleDAGMI *DAG; 2547 ILPOrder Cmp; 2548 2549 std::vector<SUnit*> ReadyQ; 2550 public: 2551 ILPScheduler(bool MaximizeILP): DAG(0), Cmp(MaximizeILP) {} 2552 2553 virtual void initialize(ScheduleDAGMI *dag) { 2554 DAG = dag; 2555 DAG->computeDFSResult(); 2556 Cmp.DFSResult = DAG->getDFSResult(); 2557 Cmp.ScheduledTrees = &DAG->getScheduledTrees(); 2558 ReadyQ.clear(); 2559 } 2560 2561 virtual void registerRoots() { 2562 // Restore the heap in ReadyQ with the updated DFS results. 2563 std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp); 2564 } 2565 2566 /// Implement MachineSchedStrategy interface. 2567 /// ----------------------------------------- 2568 2569 /// Callback to select the highest priority node from the ready Q. 2570 virtual SUnit *pickNode(bool &IsTopNode) { 2571 if (ReadyQ.empty()) return NULL; 2572 std::pop_heap(ReadyQ.begin(), ReadyQ.end(), Cmp); 2573 SUnit *SU = ReadyQ.back(); 2574 ReadyQ.pop_back(); 2575 IsTopNode = false; 2576 DEBUG(dbgs() << "Pick node " << "SU(" << SU->NodeNum << ") " 2577 << " ILP: " << DAG->getDFSResult()->getILP(SU) 2578 << " Tree: " << DAG->getDFSResult()->getSubtreeID(SU) << " @" 2579 << DAG->getDFSResult()->getSubtreeLevel( 2580 DAG->getDFSResult()->getSubtreeID(SU)) << '\n' 2581 << "Scheduling " << *SU->getInstr()); 2582 return SU; 2583 } 2584 2585 /// \brief Scheduler callback to notify that a new subtree is scheduled. 2586 virtual void scheduleTree(unsigned SubtreeID) { 2587 std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp); 2588 } 2589 2590 /// Callback after a node is scheduled. Mark a newly scheduled tree, notify 2591 /// DFSResults, and resort the priority Q. 2592 virtual void schedNode(SUnit *SU, bool IsTopNode) { 2593 assert(!IsTopNode && "SchedDFSResult needs bottom-up"); 2594 } 2595 2596 virtual void releaseTopNode(SUnit *) { /*only called for top roots*/ } 2597 2598 virtual void releaseBottomNode(SUnit *SU) { 2599 ReadyQ.push_back(SU); 2600 std::push_heap(ReadyQ.begin(), ReadyQ.end(), Cmp); 2601 } 2602 }; 2603 } // namespace 2604 2605 static ScheduleDAGInstrs *createILPMaxScheduler(MachineSchedContext *C) { 2606 return new ScheduleDAGMI(C, new ILPScheduler(true)); 2607 } 2608 static ScheduleDAGInstrs *createILPMinScheduler(MachineSchedContext *C) { 2609 return new ScheduleDAGMI(C, new ILPScheduler(false)); 2610 } 2611 static MachineSchedRegistry ILPMaxRegistry( 2612 "ilpmax", "Schedule bottom-up for max ILP", createILPMaxScheduler); 2613 static MachineSchedRegistry ILPMinRegistry( 2614 "ilpmin", "Schedule bottom-up for min ILP", createILPMinScheduler); 2615 2616 //===----------------------------------------------------------------------===// 2617 // Machine Instruction Shuffler for Correctness Testing 2618 //===----------------------------------------------------------------------===// 2619 2620 #ifndef NDEBUG 2621 namespace { 2622 /// Apply a less-than relation on the node order, which corresponds to the 2623 /// instruction order prior to scheduling. IsReverse implements greater-than. 2624 template<bool IsReverse> 2625 struct SUnitOrder { 2626 bool operator()(SUnit *A, SUnit *B) const { 2627 if (IsReverse) 2628 return A->NodeNum > B->NodeNum; 2629 else 2630 return A->NodeNum < B->NodeNum; 2631 } 2632 }; 2633 2634 /// Reorder instructions as much as possible. 2635 class InstructionShuffler : public MachineSchedStrategy { 2636 bool IsAlternating; 2637 bool IsTopDown; 2638 2639 // Using a less-than relation (SUnitOrder<false>) for the TopQ priority 2640 // gives nodes with a higher number higher priority causing the latest 2641 // instructions to be scheduled first. 2642 PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<false> > 2643 TopQ; 2644 // When scheduling bottom-up, use greater-than as the queue priority. 2645 PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<true> > 2646 BottomQ; 2647 public: 2648 InstructionShuffler(bool alternate, bool topdown) 2649 : IsAlternating(alternate), IsTopDown(topdown) {} 2650 2651 virtual void initialize(ScheduleDAGMI *) { 2652 TopQ.clear(); 2653 BottomQ.clear(); 2654 } 2655 2656 /// Implement MachineSchedStrategy interface. 2657 /// ----------------------------------------- 2658 2659 virtual SUnit *pickNode(bool &IsTopNode) { 2660 SUnit *SU; 2661 if (IsTopDown) { 2662 do { 2663 if (TopQ.empty()) return NULL; 2664 SU = TopQ.top(); 2665 TopQ.pop(); 2666 } while (SU->isScheduled); 2667 IsTopNode = true; 2668 } 2669 else { 2670 do { 2671 if (BottomQ.empty()) return NULL; 2672 SU = BottomQ.top(); 2673 BottomQ.pop(); 2674 } while (SU->isScheduled); 2675 IsTopNode = false; 2676 } 2677 if (IsAlternating) 2678 IsTopDown = !IsTopDown; 2679 return SU; 2680 } 2681 2682 virtual void schedNode(SUnit *SU, bool IsTopNode) {} 2683 2684 virtual void releaseTopNode(SUnit *SU) { 2685 TopQ.push(SU); 2686 } 2687 virtual void releaseBottomNode(SUnit *SU) { 2688 BottomQ.push(SU); 2689 } 2690 }; 2691 } // namespace 2692 2693 static ScheduleDAGInstrs *createInstructionShuffler(MachineSchedContext *C) { 2694 bool Alternate = !ForceTopDown && !ForceBottomUp; 2695 bool TopDown = !ForceBottomUp; 2696 assert((TopDown || !ForceTopDown) && 2697 "-misched-topdown incompatible with -misched-bottomup"); 2698 return new ScheduleDAGMI(C, new InstructionShuffler(Alternate, TopDown)); 2699 } 2700 static MachineSchedRegistry ShufflerRegistry( 2701 "shuffle", "Shuffle machine instructions alternating directions", 2702 createInstructionShuffler); 2703 #endif // !NDEBUG 2704 2705 //===----------------------------------------------------------------------===// 2706 // GraphWriter support for ScheduleDAGMI. 2707 //===----------------------------------------------------------------------===// 2708 2709 #ifndef NDEBUG 2710 namespace llvm { 2711 2712 template<> struct GraphTraits< 2713 ScheduleDAGMI*> : public GraphTraits<ScheduleDAG*> {}; 2714 2715 template<> 2716 struct DOTGraphTraits<ScheduleDAGMI*> : public DefaultDOTGraphTraits { 2717 2718 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} 2719 2720 static std::string getGraphName(const ScheduleDAG *G) { 2721 return G->MF.getName(); 2722 } 2723 2724 static bool renderGraphFromBottomUp() { 2725 return true; 2726 } 2727 2728 static bool isNodeHidden(const SUnit *Node) { 2729 return (Node->NumPreds > 10 || Node->NumSuccs > 10); 2730 } 2731 2732 static bool hasNodeAddressLabel(const SUnit *Node, 2733 const ScheduleDAG *Graph) { 2734 return false; 2735 } 2736 2737 /// If you want to override the dot attributes printed for a particular 2738 /// edge, override this method. 2739 static std::string getEdgeAttributes(const SUnit *Node, 2740 SUnitIterator EI, 2741 const ScheduleDAG *Graph) { 2742 if (EI.isArtificialDep()) 2743 return "color=cyan,style=dashed"; 2744 if (EI.isCtrlDep()) 2745 return "color=blue,style=dashed"; 2746 return ""; 2747 } 2748 2749 static std::string getNodeLabel(const SUnit *SU, const ScheduleDAG *G) { 2750 std::string Str; 2751 raw_string_ostream SS(Str); 2752 SS << "SU(" << SU->NodeNum << ')'; 2753 return SS.str(); 2754 } 2755 static std::string getNodeDescription(const SUnit *SU, const ScheduleDAG *G) { 2756 return G->getGraphNodeLabel(SU); 2757 } 2758 2759 static std::string getNodeAttributes(const SUnit *N, 2760 const ScheduleDAG *Graph) { 2761 std::string Str("shape=Mrecord"); 2762 const SchedDFSResult *DFS = 2763 static_cast<const ScheduleDAGMI*>(Graph)->getDFSResult(); 2764 if (DFS) { 2765 Str += ",style=filled,fillcolor=\"#"; 2766 Str += DOT::getColorString(DFS->getSubtreeID(N)); 2767 Str += '"'; 2768 } 2769 return Str; 2770 } 2771 }; 2772 } // namespace llvm 2773 #endif // NDEBUG 2774 2775 /// viewGraph - Pop up a ghostview window with the reachable parts of the DAG 2776 /// rendered using 'dot'. 2777 /// 2778 void ScheduleDAGMI::viewGraph(const Twine &Name, const Twine &Title) { 2779 #ifndef NDEBUG 2780 ViewGraph(this, Name, false, Title); 2781 #else 2782 errs() << "ScheduleDAGMI::viewGraph is only available in debug builds on " 2783 << "systems with Graphviz or gv!\n"; 2784 #endif // NDEBUG 2785 } 2786 2787 /// Out-of-line implementation with no arguments is handy for gdb. 2788 void ScheduleDAGMI::viewGraph() { 2789 viewGraph(getDAGName(), "Scheduling-Units Graph for " + getDAGName()); 2790 } 2791