1 //===- MachineScheduler.h - MachineInstr Scheduling Pass --------*- C++ -*-===// 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 // This file provides an interface for customizing the standard MachineScheduler 10 // pass. Note that the entire pass may be replaced as follows: 11 // 12 // <Target>TargetMachine::createPassConfig(PassManagerBase &PM) { 13 // PM.substitutePass(&MachineSchedulerID, &CustomSchedulerPassID); 14 // ...} 15 // 16 // The MachineScheduler pass is only responsible for choosing the regions to be 17 // scheduled. Targets can override the DAG builder and scheduler without 18 // replacing the pass as follows: 19 // 20 // ScheduleDAGInstrs *<Target>PassConfig:: 21 // createMachineScheduler(MachineSchedContext *C) { 22 // return new CustomMachineScheduler(C); 23 // } 24 // 25 // The default scheduler, ScheduleDAGMILive, builds the DAG and drives list 26 // scheduling while updating the instruction stream, register pressure, and live 27 // intervals. Most targets don't need to override the DAG builder and list 28 // scheduler, but subtargets that require custom scheduling heuristics may 29 // plugin an alternate MachineSchedStrategy. The strategy is responsible for 30 // selecting the highest priority node from the list: 31 // 32 // ScheduleDAGInstrs *<Target>PassConfig:: 33 // createMachineScheduler(MachineSchedContext *C) { 34 // return new ScheduleDAGMILive(C, CustomStrategy(C)); 35 // } 36 // 37 // The DAG builder can also be customized in a sense by adding DAG mutations 38 // that will run after DAG building and before list scheduling. DAG mutations 39 // can adjust dependencies based on target-specific knowledge or add weak edges 40 // to aid heuristics: 41 // 42 // ScheduleDAGInstrs *<Target>PassConfig:: 43 // createMachineScheduler(MachineSchedContext *C) { 44 // ScheduleDAGMI *DAG = createGenericSchedLive(C); 45 // DAG->addMutation(new CustomDAGMutation(...)); 46 // return DAG; 47 // } 48 // 49 // A target that supports alternative schedulers can use the 50 // MachineSchedRegistry to allow command line selection. This can be done by 51 // implementing the following boilerplate: 52 // 53 // static ScheduleDAGInstrs *createCustomMachineSched(MachineSchedContext *C) { 54 // return new CustomMachineScheduler(C); 55 // } 56 // static MachineSchedRegistry 57 // SchedCustomRegistry("custom", "Run my target's custom scheduler", 58 // createCustomMachineSched); 59 // 60 // 61 // Finally, subtargets that don't need to implement custom heuristics but would 62 // like to configure the GenericScheduler's policy for a given scheduler region, 63 // including scheduling direction and register pressure tracking policy, can do 64 // this: 65 // 66 // void <SubTarget>Subtarget:: 67 // overrideSchedPolicy(MachineSchedPolicy &Policy, 68 // unsigned NumRegionInstrs) const { 69 // Policy.<Flag> = true; 70 // } 71 // 72 //===----------------------------------------------------------------------===// 73 74 #ifndef LLVM_CODEGEN_MACHINESCHEDULER_H 75 #define LLVM_CODEGEN_MACHINESCHEDULER_H 76 77 #include "llvm/ADT/APInt.h" 78 #include "llvm/ADT/ArrayRef.h" 79 #include "llvm/ADT/BitVector.h" 80 #include "llvm/ADT/STLExtras.h" 81 #include "llvm/ADT/SmallVector.h" 82 #include "llvm/ADT/StringRef.h" 83 #include "llvm/ADT/Twine.h" 84 #include "llvm/CodeGen/MachineBasicBlock.h" 85 #include "llvm/CodeGen/MachinePassRegistry.h" 86 #include "llvm/CodeGen/RegisterPressure.h" 87 #include "llvm/CodeGen/ScheduleDAG.h" 88 #include "llvm/CodeGen/ScheduleDAGInstrs.h" 89 #include "llvm/CodeGen/ScheduleDAGMutation.h" 90 #include "llvm/CodeGen/TargetSchedule.h" 91 #include "llvm/Support/CommandLine.h" 92 #include "llvm/Support/ErrorHandling.h" 93 #include <algorithm> 94 #include <cassert> 95 #include <memory> 96 #include <string> 97 #include <vector> 98 99 namespace llvm { 100 101 extern cl::opt<bool> ForceTopDown; 102 extern cl::opt<bool> ForceBottomUp; 103 extern cl::opt<bool> VerifyScheduling; 104 #ifndef NDEBUG 105 extern cl::opt<bool> ViewMISchedDAGs; 106 extern cl::opt<bool> PrintDAGs; 107 #else 108 extern const bool ViewMISchedDAGs; 109 extern const bool PrintDAGs; 110 #endif 111 112 class AAResults; 113 class LiveIntervals; 114 class MachineDominatorTree; 115 class MachineFunction; 116 class MachineInstr; 117 class MachineLoopInfo; 118 class RegisterClassInfo; 119 class SchedDFSResult; 120 class ScheduleHazardRecognizer; 121 class TargetInstrInfo; 122 class TargetPassConfig; 123 class TargetRegisterInfo; 124 125 /// MachineSchedContext provides enough context from the MachineScheduler pass 126 /// for the target to instantiate a scheduler. 127 struct MachineSchedContext { 128 MachineFunction *MF = nullptr; 129 const MachineLoopInfo *MLI = nullptr; 130 const MachineDominatorTree *MDT = nullptr; 131 const TargetPassConfig *PassConfig = nullptr; 132 AAResults *AA = nullptr; 133 LiveIntervals *LIS = nullptr; 134 135 RegisterClassInfo *RegClassInfo; 136 137 MachineSchedContext(); 138 virtual ~MachineSchedContext(); 139 }; 140 141 /// MachineSchedRegistry provides a selection of available machine instruction 142 /// schedulers. 143 class MachineSchedRegistry 144 : public MachinePassRegistryNode< 145 ScheduleDAGInstrs *(*)(MachineSchedContext *)> { 146 public: 147 using ScheduleDAGCtor = ScheduleDAGInstrs *(*)(MachineSchedContext *); 148 149 // RegisterPassParser requires a (misnamed) FunctionPassCtor type. 150 using FunctionPassCtor = ScheduleDAGCtor; 151 152 static MachinePassRegistry<ScheduleDAGCtor> Registry; 153 154 MachineSchedRegistry(const char *N, const char *D, ScheduleDAGCtor C) 155 : MachinePassRegistryNode(N, D, C) { 156 Registry.Add(this); 157 } 158 159 ~MachineSchedRegistry() { Registry.Remove(this); } 160 161 // Accessors. 162 // 163 MachineSchedRegistry *getNext() const { 164 return (MachineSchedRegistry *)MachinePassRegistryNode::getNext(); 165 } 166 167 static MachineSchedRegistry *getList() { 168 return (MachineSchedRegistry *)Registry.getList(); 169 } 170 171 static void setListener(MachinePassRegistryListener<FunctionPassCtor> *L) { 172 Registry.setListener(L); 173 } 174 }; 175 176 class ScheduleDAGMI; 177 178 /// Define a generic scheduling policy for targets that don't provide their own 179 /// MachineSchedStrategy. This can be overriden for each scheduling region 180 /// before building the DAG. 181 struct MachineSchedPolicy { 182 // Allow the scheduler to disable register pressure tracking. 183 bool ShouldTrackPressure = false; 184 /// Track LaneMasks to allow reordering of independent subregister writes 185 /// of the same vreg. \sa MachineSchedStrategy::shouldTrackLaneMasks() 186 bool ShouldTrackLaneMasks = false; 187 188 // Allow the scheduler to force top-down or bottom-up scheduling. If neither 189 // is true, the scheduler runs in both directions and converges. 190 bool OnlyTopDown = false; 191 bool OnlyBottomUp = false; 192 193 // Disable heuristic that tries to fetch nodes from long dependency chains 194 // first. 195 bool DisableLatencyHeuristic = false; 196 197 // Compute DFSResult for use in scheduling heuristics. 198 bool ComputeDFSResult = false; 199 200 MachineSchedPolicy() = default; 201 }; 202 203 /// MachineSchedStrategy - Interface to the scheduling algorithm used by 204 /// ScheduleDAGMI. 205 /// 206 /// Initialization sequence: 207 /// initPolicy -> shouldTrackPressure -> initialize(DAG) -> registerRoots 208 class MachineSchedStrategy { 209 virtual void anchor(); 210 211 public: 212 virtual ~MachineSchedStrategy() = default; 213 214 /// Optionally override the per-region scheduling policy. 215 virtual void initPolicy(MachineBasicBlock::iterator Begin, 216 MachineBasicBlock::iterator End, 217 unsigned NumRegionInstrs) {} 218 219 virtual void dumpPolicy() const {} 220 221 /// Check if pressure tracking is needed before building the DAG and 222 /// initializing this strategy. Called after initPolicy. 223 virtual bool shouldTrackPressure() const { return true; } 224 225 /// Returns true if lanemasks should be tracked. LaneMask tracking is 226 /// necessary to reorder independent subregister defs for the same vreg. 227 /// This has to be enabled in combination with shouldTrackPressure(). 228 virtual bool shouldTrackLaneMasks() const { return false; } 229 230 // If this method returns true, handling of the scheduling regions 231 // themselves (in case of a scheduling boundary in MBB) will be done 232 // beginning with the topmost region of MBB. 233 virtual bool doMBBSchedRegionsTopDown() const { return false; } 234 235 /// Initialize the strategy after building the DAG for a new region. 236 virtual void initialize(ScheduleDAGMI *DAG) = 0; 237 238 /// Tell the strategy that MBB is about to be processed. 239 virtual void enterMBB(MachineBasicBlock *MBB) {}; 240 241 /// Tell the strategy that current MBB is done. 242 virtual void leaveMBB() {}; 243 244 /// Notify this strategy that all roots have been released (including those 245 /// that depend on EntrySU or ExitSU). 246 virtual void registerRoots() {} 247 248 /// Pick the next node to schedule, or return NULL. Set IsTopNode to true to 249 /// schedule the node at the top of the unscheduled region. Otherwise it will 250 /// be scheduled at the bottom. 251 virtual SUnit *pickNode(bool &IsTopNode) = 0; 252 253 /// Scheduler callback to notify that a new subtree is scheduled. 254 virtual void scheduleTree(unsigned SubtreeID) {} 255 256 /// Notify MachineSchedStrategy that ScheduleDAGMI has scheduled an 257 /// instruction and updated scheduled/remaining flags in the DAG nodes. 258 virtual void schedNode(SUnit *SU, bool IsTopNode) = 0; 259 260 /// When all predecessor dependencies have been resolved, free this node for 261 /// top-down scheduling. 262 virtual void releaseTopNode(SUnit *SU) = 0; 263 264 /// When all successor dependencies have been resolved, free this node for 265 /// bottom-up scheduling. 266 virtual void releaseBottomNode(SUnit *SU) = 0; 267 }; 268 269 /// ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply 270 /// schedules machine instructions according to the given MachineSchedStrategy 271 /// without much extra book-keeping. This is the common functionality between 272 /// PreRA and PostRA MachineScheduler. 273 class ScheduleDAGMI : public ScheduleDAGInstrs { 274 protected: 275 AAResults *AA; 276 LiveIntervals *LIS; 277 std::unique_ptr<MachineSchedStrategy> SchedImpl; 278 279 /// Ordered list of DAG postprocessing steps. 280 std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations; 281 282 /// The top of the unscheduled zone. 283 MachineBasicBlock::iterator CurrentTop; 284 285 /// The bottom of the unscheduled zone. 286 MachineBasicBlock::iterator CurrentBottom; 287 288 /// Record the next node in a scheduled cluster. 289 const SUnit *NextClusterPred = nullptr; 290 const SUnit *NextClusterSucc = nullptr; 291 292 #if LLVM_ENABLE_ABI_BREAKING_CHECKS 293 /// The number of instructions scheduled so far. Used to cut off the 294 /// scheduler at the point determined by misched-cutoff. 295 unsigned NumInstrsScheduled = 0; 296 #endif 297 298 public: 299 ScheduleDAGMI(MachineSchedContext *C, std::unique_ptr<MachineSchedStrategy> S, 300 bool RemoveKillFlags) 301 : ScheduleDAGInstrs(*C->MF, C->MLI, RemoveKillFlags), AA(C->AA), 302 LIS(C->LIS), SchedImpl(std::move(S)) {} 303 304 // Provide a vtable anchor 305 ~ScheduleDAGMI() override; 306 307 /// If this method returns true, handling of the scheduling regions 308 /// themselves (in case of a scheduling boundary in MBB) will be done 309 /// beginning with the topmost region of MBB. 310 bool doMBBSchedRegionsTopDown() const override { 311 return SchedImpl->doMBBSchedRegionsTopDown(); 312 } 313 314 // Returns LiveIntervals instance for use in DAG mutators and such. 315 LiveIntervals *getLIS() const { return LIS; } 316 317 /// Return true if this DAG supports VReg liveness and RegPressure. 318 virtual bool hasVRegLiveness() const { return false; } 319 320 /// Add a postprocessing step to the DAG builder. 321 /// Mutations are applied in the order that they are added after normal DAG 322 /// building and before MachineSchedStrategy initialization. 323 /// 324 /// ScheduleDAGMI takes ownership of the Mutation object. 325 void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) { 326 if (Mutation) 327 Mutations.push_back(std::move(Mutation)); 328 } 329 330 MachineBasicBlock::iterator top() const { return CurrentTop; } 331 MachineBasicBlock::iterator bottom() const { return CurrentBottom; } 332 333 /// Implement the ScheduleDAGInstrs interface for handling the next scheduling 334 /// region. This covers all instructions in a block, while schedule() may only 335 /// cover a subset. 336 void enterRegion(MachineBasicBlock *bb, 337 MachineBasicBlock::iterator begin, 338 MachineBasicBlock::iterator end, 339 unsigned regioninstrs) override; 340 341 /// Implement ScheduleDAGInstrs interface for scheduling a sequence of 342 /// reorderable instructions. 343 void schedule() override; 344 345 void startBlock(MachineBasicBlock *bb) override; 346 void finishBlock() override; 347 348 /// Change the position of an instruction within the basic block and update 349 /// live ranges and region boundary iterators. 350 void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos); 351 352 const SUnit *getNextClusterPred() const { return NextClusterPred; } 353 354 const SUnit *getNextClusterSucc() const { return NextClusterSucc; } 355 356 void viewGraph(const Twine &Name, const Twine &Title) override; 357 void viewGraph() override; 358 359 protected: 360 // Top-Level entry points for the schedule() driver... 361 362 /// Apply each ScheduleDAGMutation step in order. This allows different 363 /// instances of ScheduleDAGMI to perform custom DAG postprocessing. 364 void postprocessDAG(); 365 366 /// Release ExitSU predecessors and setup scheduler queues. 367 void initQueues(ArrayRef<SUnit*> TopRoots, ArrayRef<SUnit*> BotRoots); 368 369 /// Update scheduler DAG and queues after scheduling an instruction. 370 void updateQueues(SUnit *SU, bool IsTopNode); 371 372 /// Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues. 373 void placeDebugValues(); 374 375 /// dump the scheduled Sequence. 376 void dumpSchedule() const; 377 378 // Lesser helpers... 379 bool checkSchedLimit(); 380 381 void findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots, 382 SmallVectorImpl<SUnit*> &BotRoots); 383 384 void releaseSucc(SUnit *SU, SDep *SuccEdge); 385 void releaseSuccessors(SUnit *SU); 386 void releasePred(SUnit *SU, SDep *PredEdge); 387 void releasePredecessors(SUnit *SU); 388 }; 389 390 /// ScheduleDAGMILive is an implementation of ScheduleDAGInstrs that schedules 391 /// machine instructions while updating LiveIntervals and tracking regpressure. 392 class ScheduleDAGMILive : public ScheduleDAGMI { 393 protected: 394 RegisterClassInfo *RegClassInfo; 395 396 /// Information about DAG subtrees. If DFSResult is NULL, then SchedulerTrees 397 /// will be empty. 398 SchedDFSResult *DFSResult = nullptr; 399 BitVector ScheduledTrees; 400 401 MachineBasicBlock::iterator LiveRegionEnd; 402 403 /// Maps vregs to the SUnits of their uses in the current scheduling region. 404 VReg2SUnitMultiMap VRegUses; 405 406 // Map each SU to its summary of pressure changes. This array is updated for 407 // liveness during bottom-up scheduling. Top-down scheduling may proceed but 408 // has no affect on the pressure diffs. 409 PressureDiffs SUPressureDiffs; 410 411 /// Register pressure in this region computed by initRegPressure. 412 bool ShouldTrackPressure = false; 413 bool ShouldTrackLaneMasks = false; 414 IntervalPressure RegPressure; 415 RegPressureTracker RPTracker; 416 417 /// List of pressure sets that exceed the target's pressure limit before 418 /// scheduling, listed in increasing set ID order. Each pressure set is paired 419 /// with its max pressure in the currently scheduled regions. 420 std::vector<PressureChange> RegionCriticalPSets; 421 422 /// The top of the unscheduled zone. 423 IntervalPressure TopPressure; 424 RegPressureTracker TopRPTracker; 425 426 /// The bottom of the unscheduled zone. 427 IntervalPressure BotPressure; 428 RegPressureTracker BotRPTracker; 429 430 public: 431 ScheduleDAGMILive(MachineSchedContext *C, 432 std::unique_ptr<MachineSchedStrategy> S) 433 : ScheduleDAGMI(C, std::move(S), /*RemoveKillFlags=*/false), 434 RegClassInfo(C->RegClassInfo), RPTracker(RegPressure), 435 TopRPTracker(TopPressure), BotRPTracker(BotPressure) {} 436 437 ~ScheduleDAGMILive() override; 438 439 /// Return true if this DAG supports VReg liveness and RegPressure. 440 bool hasVRegLiveness() const override { return true; } 441 442 /// Return true if register pressure tracking is enabled. 443 bool isTrackingPressure() const { return ShouldTrackPressure; } 444 445 /// Get current register pressure for the top scheduled instructions. 446 const IntervalPressure &getTopPressure() const { return TopPressure; } 447 const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; } 448 449 /// Get current register pressure for the bottom scheduled instructions. 450 const IntervalPressure &getBotPressure() const { return BotPressure; } 451 const RegPressureTracker &getBotRPTracker() const { return BotRPTracker; } 452 453 /// Get register pressure for the entire scheduling region before scheduling. 454 const IntervalPressure &getRegPressure() const { return RegPressure; } 455 456 const std::vector<PressureChange> &getRegionCriticalPSets() const { 457 return RegionCriticalPSets; 458 } 459 460 PressureDiff &getPressureDiff(const SUnit *SU) { 461 return SUPressureDiffs[SU->NodeNum]; 462 } 463 const PressureDiff &getPressureDiff(const SUnit *SU) const { 464 return SUPressureDiffs[SU->NodeNum]; 465 } 466 467 /// Compute a DFSResult after DAG building is complete, and before any 468 /// queue comparisons. 469 void computeDFSResult(); 470 471 /// Return a non-null DFS result if the scheduling strategy initialized it. 472 const SchedDFSResult *getDFSResult() const { return DFSResult; } 473 474 BitVector &getScheduledTrees() { return ScheduledTrees; } 475 476 /// Implement the ScheduleDAGInstrs interface for handling the next scheduling 477 /// region. This covers all instructions in a block, while schedule() may only 478 /// cover a subset. 479 void enterRegion(MachineBasicBlock *bb, 480 MachineBasicBlock::iterator begin, 481 MachineBasicBlock::iterator end, 482 unsigned regioninstrs) override; 483 484 /// Implement ScheduleDAGInstrs interface for scheduling a sequence of 485 /// reorderable instructions. 486 void schedule() override; 487 488 /// Compute the cyclic critical path through the DAG. 489 unsigned computeCyclicCriticalPath(); 490 491 void dump() const override; 492 493 protected: 494 // Top-Level entry points for the schedule() driver... 495 496 /// Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking 497 /// enabled. This sets up three trackers. RPTracker will cover the entire DAG 498 /// region, TopTracker and BottomTracker will be initialized to the top and 499 /// bottom of the DAG region without covereing any unscheduled instruction. 500 void buildDAGWithRegPressure(); 501 502 /// Release ExitSU predecessors and setup scheduler queues. Re-position 503 /// the Top RP tracker in case the region beginning has changed. 504 void initQueues(ArrayRef<SUnit*> TopRoots, ArrayRef<SUnit*> BotRoots); 505 506 /// Move an instruction and update register pressure. 507 void scheduleMI(SUnit *SU, bool IsTopNode); 508 509 // Lesser helpers... 510 511 void initRegPressure(); 512 513 void updatePressureDiffs(ArrayRef<RegisterMaskPair> LiveUses); 514 515 void updateScheduledPressure(const SUnit *SU, 516 const std::vector<unsigned> &NewMaxPressure); 517 518 void collectVRegUses(SUnit &SU); 519 }; 520 521 //===----------------------------------------------------------------------===// 522 /// 523 /// Helpers for implementing custom MachineSchedStrategy classes. These take 524 /// care of the book-keeping associated with list scheduling heuristics. 525 /// 526 //===----------------------------------------------------------------------===// 527 528 /// ReadyQueue encapsulates vector of "ready" SUnits with basic convenience 529 /// methods for pushing and removing nodes. ReadyQueue's are uniquely identified 530 /// by an ID. SUnit::NodeQueueId is a mask of the ReadyQueues the SUnit is in. 531 /// 532 /// This is a convenience class that may be used by implementations of 533 /// MachineSchedStrategy. 534 class ReadyQueue { 535 unsigned ID; 536 std::string Name; 537 std::vector<SUnit*> Queue; 538 539 public: 540 ReadyQueue(unsigned id, const Twine &name): ID(id), Name(name.str()) {} 541 542 unsigned getID() const { return ID; } 543 544 StringRef getName() const { return Name; } 545 546 // SU is in this queue if it's NodeQueueID is a superset of this ID. 547 bool isInQueue(SUnit *SU) const { return (SU->NodeQueueId & ID); } 548 549 bool empty() const { return Queue.empty(); } 550 551 void clear() { Queue.clear(); } 552 553 unsigned size() const { return Queue.size(); } 554 555 using iterator = std::vector<SUnit*>::iterator; 556 557 iterator begin() { return Queue.begin(); } 558 559 iterator end() { return Queue.end(); } 560 561 ArrayRef<SUnit*> elements() { return Queue; } 562 563 iterator find(SUnit *SU) { return llvm::find(Queue, SU); } 564 565 void push(SUnit *SU) { 566 Queue.push_back(SU); 567 SU->NodeQueueId |= ID; 568 } 569 570 iterator remove(iterator I) { 571 (*I)->NodeQueueId &= ~ID; 572 *I = Queue.back(); 573 unsigned idx = I - Queue.begin(); 574 Queue.pop_back(); 575 return Queue.begin() + idx; 576 } 577 578 void dump() const; 579 }; 580 581 /// Summarize the unscheduled region. 582 struct SchedRemainder { 583 // Critical path through the DAG in expected latency. 584 unsigned CriticalPath; 585 unsigned CyclicCritPath; 586 587 // Scaled count of micro-ops left to schedule. 588 unsigned RemIssueCount; 589 590 bool IsAcyclicLatencyLimited; 591 592 // Unscheduled resources 593 SmallVector<unsigned, 16> RemainingCounts; 594 595 SchedRemainder() { reset(); } 596 597 void reset() { 598 CriticalPath = 0; 599 CyclicCritPath = 0; 600 RemIssueCount = 0; 601 IsAcyclicLatencyLimited = false; 602 RemainingCounts.clear(); 603 } 604 605 void init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel); 606 }; 607 608 /// Each Scheduling boundary is associated with ready queues. It tracks the 609 /// current cycle in the direction of movement, and maintains the state 610 /// of "hazards" and other interlocks at the current cycle. 611 class SchedBoundary { 612 public: 613 /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both) 614 enum { 615 TopQID = 1, 616 BotQID = 2, 617 LogMaxQID = 2 618 }; 619 620 ScheduleDAGMI *DAG = nullptr; 621 const TargetSchedModel *SchedModel = nullptr; 622 SchedRemainder *Rem = nullptr; 623 624 ReadyQueue Available; 625 ReadyQueue Pending; 626 627 ScheduleHazardRecognizer *HazardRec = nullptr; 628 629 private: 630 /// True if the pending Q should be checked/updated before scheduling another 631 /// instruction. 632 bool CheckPending; 633 634 /// Number of cycles it takes to issue the instructions scheduled in this 635 /// zone. It is defined as: scheduled-micro-ops / issue-width + stalls. 636 /// See getStalls(). 637 unsigned CurrCycle; 638 639 /// Micro-ops issued in the current cycle 640 unsigned CurrMOps; 641 642 /// MinReadyCycle - Cycle of the soonest available instruction. 643 unsigned MinReadyCycle; 644 645 // The expected latency of the critical path in this scheduled zone. 646 unsigned ExpectedLatency; 647 648 // The latency of dependence chains leading into this zone. 649 // For each node scheduled bottom-up: DLat = max DLat, N.Depth. 650 // For each cycle scheduled: DLat -= 1. 651 unsigned DependentLatency; 652 653 /// Count the scheduled (issued) micro-ops that can be retired by 654 /// time=CurrCycle assuming the first scheduled instr is retired at time=0. 655 unsigned RetiredMOps; 656 657 // Count scheduled resources that have been executed. Resources are 658 // considered executed if they become ready in the time that it takes to 659 // saturate any resource including the one in question. Counts are scaled 660 // for direct comparison with other resources. Counts can be compared with 661 // MOps * getMicroOpFactor and Latency * getLatencyFactor. 662 SmallVector<unsigned, 16> ExecutedResCounts; 663 664 /// Cache the max count for a single resource. 665 unsigned MaxExecutedResCount; 666 667 // Cache the critical resources ID in this scheduled zone. 668 unsigned ZoneCritResIdx; 669 670 // Is the scheduled region resource limited vs. latency limited. 671 bool IsResourceLimited; 672 673 // Record the highest cycle at which each resource has been reserved by a 674 // scheduled instruction. 675 SmallVector<unsigned, 16> ReservedCycles; 676 677 // For each PIdx, stores first index into ReservedCycles that corresponds to 678 // it. 679 SmallVector<unsigned, 16> ReservedCyclesIndex; 680 681 // For each PIdx, stores the resource group IDs of its subunits 682 SmallVector<APInt, 16> ResourceGroupSubUnitMasks; 683 684 #if LLVM_ENABLE_ABI_BREAKING_CHECKS 685 // Remember the greatest possible stall as an upper bound on the number of 686 // times we should retry the pending queue because of a hazard. 687 unsigned MaxObservedStall; 688 #endif 689 690 public: 691 /// Pending queues extend the ready queues with the same ID and the 692 /// PendingFlag set. 693 SchedBoundary(unsigned ID, const Twine &Name): 694 Available(ID, Name+".A"), Pending(ID << LogMaxQID, Name+".P") { 695 reset(); 696 } 697 698 ~SchedBoundary(); 699 700 void reset(); 701 702 void init(ScheduleDAGMI *dag, const TargetSchedModel *smodel, 703 SchedRemainder *rem); 704 705 bool isTop() const { 706 return Available.getID() == TopQID; 707 } 708 709 /// Number of cycles to issue the instructions scheduled in this zone. 710 unsigned getCurrCycle() const { return CurrCycle; } 711 712 /// Micro-ops issued in the current cycle 713 unsigned getCurrMOps() const { return CurrMOps; } 714 715 // The latency of dependence chains leading into this zone. 716 unsigned getDependentLatency() const { return DependentLatency; } 717 718 /// Get the number of latency cycles "covered" by the scheduled 719 /// instructions. This is the larger of the critical path within the zone 720 /// and the number of cycles required to issue the instructions. 721 unsigned getScheduledLatency() const { 722 return std::max(ExpectedLatency, CurrCycle); 723 } 724 725 unsigned getUnscheduledLatency(SUnit *SU) const { 726 return isTop() ? SU->getHeight() : SU->getDepth(); 727 } 728 729 unsigned getResourceCount(unsigned ResIdx) const { 730 return ExecutedResCounts[ResIdx]; 731 } 732 733 /// Get the scaled count of scheduled micro-ops and resources, including 734 /// executed resources. 735 unsigned getCriticalCount() const { 736 if (!ZoneCritResIdx) 737 return RetiredMOps * SchedModel->getMicroOpFactor(); 738 return getResourceCount(ZoneCritResIdx); 739 } 740 741 /// Get a scaled count for the minimum execution time of the scheduled 742 /// micro-ops that are ready to execute by getExecutedCount. Notice the 743 /// feedback loop. 744 unsigned getExecutedCount() const { 745 return std::max(CurrCycle * SchedModel->getLatencyFactor(), 746 MaxExecutedResCount); 747 } 748 749 unsigned getZoneCritResIdx() const { return ZoneCritResIdx; } 750 751 // Is the scheduled region resource limited vs. latency limited. 752 bool isResourceLimited() const { return IsResourceLimited; } 753 754 /// Get the difference between the given SUnit's ready time and the current 755 /// cycle. 756 unsigned getLatencyStallCycles(SUnit *SU); 757 758 unsigned getNextResourceCycleByInstance(unsigned InstanceIndex, 759 unsigned Cycles); 760 761 std::pair<unsigned, unsigned> getNextResourceCycle(const MCSchedClassDesc *SC, 762 unsigned PIdx, 763 unsigned Cycles); 764 765 bool isUnbufferedGroup(unsigned PIdx) const { 766 return SchedModel->getProcResource(PIdx)->SubUnitsIdxBegin && 767 !SchedModel->getProcResource(PIdx)->BufferSize; 768 } 769 770 bool checkHazard(SUnit *SU); 771 772 unsigned findMaxLatency(ArrayRef<SUnit*> ReadySUs); 773 774 unsigned getOtherResourceCount(unsigned &OtherCritIdx); 775 776 /// Release SU to make it ready. If it's not in hazard, remove it from 777 /// pending queue (if already in) and push into available queue. 778 /// Otherwise, push the SU into pending queue. 779 /// 780 /// @param SU The unit to be released. 781 /// @param ReadyCycle Until which cycle the unit is ready. 782 /// @param InPQueue Whether SU is already in pending queue. 783 /// @param Idx Position offset in pending queue (if in it). 784 void releaseNode(SUnit *SU, unsigned ReadyCycle, bool InPQueue, 785 unsigned Idx = 0); 786 787 void bumpCycle(unsigned NextCycle); 788 789 void incExecutedResources(unsigned PIdx, unsigned Count); 790 791 unsigned countResource(const MCSchedClassDesc *SC, unsigned PIdx, 792 unsigned Cycles, unsigned ReadyCycle); 793 794 void bumpNode(SUnit *SU); 795 796 void releasePending(); 797 798 void removeReady(SUnit *SU); 799 800 /// Call this before applying any other heuristics to the Available queue. 801 /// Updates the Available/Pending Q's if necessary and returns the single 802 /// available instruction, or NULL if there are multiple candidates. 803 SUnit *pickOnlyChoice(); 804 805 void dumpScheduledState() const; 806 }; 807 808 /// Base class for GenericScheduler. This class maintains information about 809 /// scheduling candidates based on TargetSchedModel making it easy to implement 810 /// heuristics for either preRA or postRA scheduling. 811 class GenericSchedulerBase : public MachineSchedStrategy { 812 public: 813 /// Represent the type of SchedCandidate found within a single queue. 814 /// pickNodeBidirectional depends on these listed by decreasing priority. 815 enum CandReason : uint8_t { 816 NoCand, Only1, PhysReg, RegExcess, RegCritical, Stall, Cluster, Weak, 817 RegMax, ResourceReduce, ResourceDemand, BotHeightReduce, BotPathReduce, 818 TopDepthReduce, TopPathReduce, NextDefUse, NodeOrder}; 819 820 #ifndef NDEBUG 821 static const char *getReasonStr(GenericSchedulerBase::CandReason Reason); 822 #endif 823 824 /// Policy for scheduling the next instruction in the candidate's zone. 825 struct CandPolicy { 826 bool ReduceLatency = false; 827 unsigned ReduceResIdx = 0; 828 unsigned DemandResIdx = 0; 829 830 CandPolicy() = default; 831 832 bool operator==(const CandPolicy &RHS) const { 833 return ReduceLatency == RHS.ReduceLatency && 834 ReduceResIdx == RHS.ReduceResIdx && 835 DemandResIdx == RHS.DemandResIdx; 836 } 837 bool operator!=(const CandPolicy &RHS) const { 838 return !(*this == RHS); 839 } 840 }; 841 842 /// Status of an instruction's critical resource consumption. 843 struct SchedResourceDelta { 844 // Count critical resources in the scheduled region required by SU. 845 unsigned CritResources = 0; 846 847 // Count critical resources from another region consumed by SU. 848 unsigned DemandedResources = 0; 849 850 SchedResourceDelta() = default; 851 852 bool operator==(const SchedResourceDelta &RHS) const { 853 return CritResources == RHS.CritResources 854 && DemandedResources == RHS.DemandedResources; 855 } 856 bool operator!=(const SchedResourceDelta &RHS) const { 857 return !operator==(RHS); 858 } 859 }; 860 861 /// Store the state used by GenericScheduler heuristics, required for the 862 /// lifetime of one invocation of pickNode(). 863 struct SchedCandidate { 864 CandPolicy Policy; 865 866 // The best SUnit candidate. 867 SUnit *SU; 868 869 // The reason for this candidate. 870 CandReason Reason; 871 872 // Whether this candidate should be scheduled at top/bottom. 873 bool AtTop; 874 875 // Register pressure values for the best candidate. 876 RegPressureDelta RPDelta; 877 878 // Critical resource consumption of the best candidate. 879 SchedResourceDelta ResDelta; 880 881 SchedCandidate() { reset(CandPolicy()); } 882 SchedCandidate(const CandPolicy &Policy) { reset(Policy); } 883 884 void reset(const CandPolicy &NewPolicy) { 885 Policy = NewPolicy; 886 SU = nullptr; 887 Reason = NoCand; 888 AtTop = false; 889 RPDelta = RegPressureDelta(); 890 ResDelta = SchedResourceDelta(); 891 } 892 893 bool isValid() const { return SU; } 894 895 // Copy the status of another candidate without changing policy. 896 void setBest(SchedCandidate &Best) { 897 assert(Best.Reason != NoCand && "uninitialized Sched candidate"); 898 SU = Best.SU; 899 Reason = Best.Reason; 900 AtTop = Best.AtTop; 901 RPDelta = Best.RPDelta; 902 ResDelta = Best.ResDelta; 903 } 904 905 void initResourceDelta(const ScheduleDAGMI *DAG, 906 const TargetSchedModel *SchedModel); 907 }; 908 909 protected: 910 const MachineSchedContext *Context; 911 const TargetSchedModel *SchedModel = nullptr; 912 const TargetRegisterInfo *TRI = nullptr; 913 914 SchedRemainder Rem; 915 916 GenericSchedulerBase(const MachineSchedContext *C) : Context(C) {} 917 918 void setPolicy(CandPolicy &Policy, bool IsPostRA, SchedBoundary &CurrZone, 919 SchedBoundary *OtherZone); 920 921 #ifndef NDEBUG 922 void traceCandidate(const SchedCandidate &Cand); 923 #endif 924 925 private: 926 bool shouldReduceLatency(const CandPolicy &Policy, SchedBoundary &CurrZone, 927 bool ComputeRemLatency, unsigned &RemLatency) const; 928 }; 929 930 // Utility functions used by heuristics in tryCandidate(). 931 bool tryLess(int TryVal, int CandVal, 932 GenericSchedulerBase::SchedCandidate &TryCand, 933 GenericSchedulerBase::SchedCandidate &Cand, 934 GenericSchedulerBase::CandReason Reason); 935 bool tryGreater(int TryVal, int CandVal, 936 GenericSchedulerBase::SchedCandidate &TryCand, 937 GenericSchedulerBase::SchedCandidate &Cand, 938 GenericSchedulerBase::CandReason Reason); 939 bool tryLatency(GenericSchedulerBase::SchedCandidate &TryCand, 940 GenericSchedulerBase::SchedCandidate &Cand, 941 SchedBoundary &Zone); 942 bool tryPressure(const PressureChange &TryP, 943 const PressureChange &CandP, 944 GenericSchedulerBase::SchedCandidate &TryCand, 945 GenericSchedulerBase::SchedCandidate &Cand, 946 GenericSchedulerBase::CandReason Reason, 947 const TargetRegisterInfo *TRI, 948 const MachineFunction &MF); 949 unsigned getWeakLeft(const SUnit *SU, bool isTop); 950 int biasPhysReg(const SUnit *SU, bool isTop); 951 952 /// GenericScheduler shrinks the unscheduled zone using heuristics to balance 953 /// the schedule. 954 class GenericScheduler : public GenericSchedulerBase { 955 public: 956 GenericScheduler(const MachineSchedContext *C): 957 GenericSchedulerBase(C), Top(SchedBoundary::TopQID, "TopQ"), 958 Bot(SchedBoundary::BotQID, "BotQ") {} 959 960 void initPolicy(MachineBasicBlock::iterator Begin, 961 MachineBasicBlock::iterator End, 962 unsigned NumRegionInstrs) override; 963 964 void dumpPolicy() const override; 965 966 bool shouldTrackPressure() const override { 967 return RegionPolicy.ShouldTrackPressure; 968 } 969 970 bool shouldTrackLaneMasks() const override { 971 return RegionPolicy.ShouldTrackLaneMasks; 972 } 973 974 void initialize(ScheduleDAGMI *dag) override; 975 976 SUnit *pickNode(bool &IsTopNode) override; 977 978 void schedNode(SUnit *SU, bool IsTopNode) override; 979 980 void releaseTopNode(SUnit *SU) override { 981 if (SU->isScheduled) 982 return; 983 984 Top.releaseNode(SU, SU->TopReadyCycle, false); 985 TopCand.SU = nullptr; 986 } 987 988 void releaseBottomNode(SUnit *SU) override { 989 if (SU->isScheduled) 990 return; 991 992 Bot.releaseNode(SU, SU->BotReadyCycle, false); 993 BotCand.SU = nullptr; 994 } 995 996 void registerRoots() override; 997 998 protected: 999 ScheduleDAGMILive *DAG = nullptr; 1000 1001 MachineSchedPolicy RegionPolicy; 1002 1003 // State of the top and bottom scheduled instruction boundaries. 1004 SchedBoundary Top; 1005 SchedBoundary Bot; 1006 1007 /// Candidate last picked from Top boundary. 1008 SchedCandidate TopCand; 1009 /// Candidate last picked from Bot boundary. 1010 SchedCandidate BotCand; 1011 1012 void checkAcyclicLatency(); 1013 1014 void initCandidate(SchedCandidate &Cand, SUnit *SU, bool AtTop, 1015 const RegPressureTracker &RPTracker, 1016 RegPressureTracker &TempTracker); 1017 1018 virtual bool tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand, 1019 SchedBoundary *Zone) const; 1020 1021 SUnit *pickNodeBidirectional(bool &IsTopNode); 1022 1023 void pickNodeFromQueue(SchedBoundary &Zone, 1024 const CandPolicy &ZonePolicy, 1025 const RegPressureTracker &RPTracker, 1026 SchedCandidate &Candidate); 1027 1028 void reschedulePhysReg(SUnit *SU, bool isTop); 1029 }; 1030 1031 /// PostGenericScheduler - Interface to the scheduling algorithm used by 1032 /// ScheduleDAGMI. 1033 /// 1034 /// Callbacks from ScheduleDAGMI: 1035 /// initPolicy -> initialize(DAG) -> registerRoots -> pickNode ... 1036 class PostGenericScheduler : public GenericSchedulerBase { 1037 protected: 1038 ScheduleDAGMI *DAG = nullptr; 1039 SchedBoundary Top; 1040 SmallVector<SUnit*, 8> BotRoots; 1041 1042 public: 1043 PostGenericScheduler(const MachineSchedContext *C): 1044 GenericSchedulerBase(C), Top(SchedBoundary::TopQID, "TopQ") {} 1045 1046 ~PostGenericScheduler() override = default; 1047 1048 void initPolicy(MachineBasicBlock::iterator Begin, 1049 MachineBasicBlock::iterator End, 1050 unsigned NumRegionInstrs) override { 1051 /* no configurable policy */ 1052 } 1053 1054 /// PostRA scheduling does not track pressure. 1055 bool shouldTrackPressure() const override { return false; } 1056 1057 void initialize(ScheduleDAGMI *Dag) override; 1058 1059 void registerRoots() override; 1060 1061 SUnit *pickNode(bool &IsTopNode) override; 1062 1063 void scheduleTree(unsigned SubtreeID) override { 1064 llvm_unreachable("PostRA scheduler does not support subtree analysis."); 1065 } 1066 1067 void schedNode(SUnit *SU, bool IsTopNode) override; 1068 1069 void releaseTopNode(SUnit *SU) override { 1070 if (SU->isScheduled) 1071 return; 1072 Top.releaseNode(SU, SU->TopReadyCycle, false); 1073 } 1074 1075 // Only called for roots. 1076 void releaseBottomNode(SUnit *SU) override { 1077 BotRoots.push_back(SU); 1078 } 1079 1080 protected: 1081 virtual bool tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand); 1082 1083 void pickNodeFromQueue(SchedCandidate &Cand); 1084 }; 1085 1086 /// Create the standard converging machine scheduler. This will be used as the 1087 /// default scheduler if the target does not set a default. 1088 /// Adds default DAG mutations. 1089 ScheduleDAGMILive *createGenericSchedLive(MachineSchedContext *C); 1090 1091 /// Create a generic scheduler with no vreg liveness or DAG mutation passes. 1092 ScheduleDAGMI *createGenericSchedPostRA(MachineSchedContext *C); 1093 1094 std::unique_ptr<ScheduleDAGMutation> 1095 createLoadClusterDAGMutation(const TargetInstrInfo *TII, 1096 const TargetRegisterInfo *TRI); 1097 1098 std::unique_ptr<ScheduleDAGMutation> 1099 createStoreClusterDAGMutation(const TargetInstrInfo *TII, 1100 const TargetRegisterInfo *TRI); 1101 1102 std::unique_ptr<ScheduleDAGMutation> 1103 createCopyConstrainDAGMutation(const TargetInstrInfo *TII, 1104 const TargetRegisterInfo *TRI); 1105 1106 } // end namespace llvm 1107 1108 #endif // LLVM_CODEGEN_MACHINESCHEDULER_H 1109