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