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