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