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