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