contrib/llvm-project/llvm/include/llvm/CodeGen/MachineScheduler.h

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