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   /// True if disconnected subregister components are already renamed.
 429   /// The renaming is only done on demand if lane masks are tracked.
 430   bool DisconnectedComponentsRenamed = false;
 431
 432 public:
 433   ScheduleDAGMILive(MachineSchedContext *C,
 434                     std::unique_ptr<MachineSchedStrategy> S)
 435       : ScheduleDAGMI(C, std::move(S), /*RemoveKillFlags=*/false),
 436         RegClassInfo(C->RegClassInfo), RPTracker(RegPressure),
 437         TopRPTracker(TopPressure), BotRPTracker(BotPressure) {}
 438
 439   ~ScheduleDAGMILive() override;
 440
 441   /// Return true if this DAG supports VReg liveness and RegPressure.
 442   bool hasVRegLiveness() const override { return true; }
 443
 444   /// Return true if register pressure tracking is enabled.
 445   bool isTrackingPressure() const { return ShouldTrackPressure; }
 446
 447   /// Get current register pressure for the top scheduled instructions.
 448   const IntervalPressure &getTopPressure() const { return TopPressure; }
 449   const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; }
 450
 451   /// Get current register pressure for the bottom scheduled instructions.
 452   const IntervalPressure &getBotPressure() const { return BotPressure; }
 453   const RegPressureTracker &getBotRPTracker() const { return BotRPTracker; }
 454
 455   /// Get register pressure for the entire scheduling region before scheduling.
 456   const IntervalPressure &getRegPressure() const { return RegPressure; }
 457
 458   const std::vector<PressureChange> &getRegionCriticalPSets() const {
 459     return RegionCriticalPSets;
 460   }
 461
 462   PressureDiff &getPressureDiff(const SUnit *SU) {
 463     return SUPressureDiffs[SU->NodeNum];
 464   }
 465   const PressureDiff &getPressureDiff(const SUnit *SU) const {
 466     return SUPressureDiffs[SU->NodeNum];
 467   }
 468
 469   /// Compute a DFSResult after DAG building is complete, and before any
 470   /// queue comparisons.
 471   void computeDFSResult();
 472
 473   /// Return a non-null DFS result if the scheduling strategy initialized it.
 474   const SchedDFSResult *getDFSResult() const { return DFSResult; }
 475
 476   BitVector &getScheduledTrees() { return ScheduledTrees; }
 477
 478   /// Implement the ScheduleDAGInstrs interface for handling the next scheduling
 479   /// region. This covers all instructions in a block, while schedule() may only
 480   /// cover a subset.
 481   void enterRegion(MachineBasicBlock *bb,
 482                    MachineBasicBlock::iterator begin,
 483                    MachineBasicBlock::iterator end,
 484                    unsigned regioninstrs) override;
 485
 486   /// Implement ScheduleDAGInstrs interface for scheduling a sequence of
 487   /// reorderable instructions.
 488   void schedule() override;
 489
 490   /// Compute the cyclic critical path through the DAG.
 491   unsigned computeCyclicCriticalPath();
 492
 493   void dump() const override;
 494
 495 protected:
 496   // Top-Level entry points for the schedule() driver...
 497
 498   /// Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking
 499   /// enabled. This sets up three trackers. RPTracker will cover the entire DAG
 500   /// region, TopTracker and BottomTracker will be initialized to the top and
 501   /// bottom of the DAG region without covereing any unscheduled instruction.
 502   void buildDAGWithRegPressure();
 503
 504   /// Release ExitSU predecessors and setup scheduler queues. Re-position
 505   /// the Top RP tracker in case the region beginning has changed.
 506   void initQueues(ArrayRef<SUnit*> TopRoots, ArrayRef<SUnit*> BotRoots);
 507
 508   /// Move an instruction and update register pressure.
 509   void scheduleMI(SUnit *SU, bool IsTopNode);
 510
 511   // Lesser helpers...
 512
 513   void initRegPressure();
 514
 515   void updatePressureDiffs(ArrayRef<RegisterMaskPair> LiveUses);
 516
 517   void updateScheduledPressure(const SUnit *SU,
 518                                const std::vector<unsigned> &NewMaxPressure);
 519
 520   void collectVRegUses(SUnit &SU);
 521 };
 522
 523 //===----------------------------------------------------------------------===//
 524 ///
 525 /// Helpers for implementing custom MachineSchedStrategy classes. These take
 526 /// care of the book-keeping associated with list scheduling heuristics.
 527 ///
 528 //===----------------------------------------------------------------------===//
 529
 530 /// ReadyQueue encapsulates vector of "ready" SUnits with basic convenience
 531 /// methods for pushing and removing nodes. ReadyQueue's are uniquely identified
 532 /// by an ID. SUnit::NodeQueueId is a mask of the ReadyQueues the SUnit is in.
 533 ///
 534 /// This is a convenience class that may be used by implementations of
 535 /// MachineSchedStrategy.
 536 class ReadyQueue {
 537   unsigned ID;
 538   std::string Name;
 539   std::vector<SUnit*> Queue;
 540
 541 public:
 542   ReadyQueue(unsigned id, const Twine &name): ID(id), Name(name.str()) {}
 543
 544   unsigned getID() const { return ID; }
 545
 546   StringRef getName() const { return Name; }
 547
 548   // SU is in this queue if it's NodeQueueID is a superset of this ID.
 549   bool isInQueue(SUnit *SU) const { return (SU->NodeQueueId & ID); }
 550
 551   bool empty() const { return Queue.empty(); }
 552
 553   void clear() { Queue.clear(); }
 554
 555   unsigned size() const { return Queue.size(); }
 556
 557   using iterator = std::vector<SUnit*>::iterator;
 558
 559   iterator begin() { return Queue.begin(); }
 560
 561   iterator end() { return Queue.end(); }
 562
 563   ArrayRef<SUnit*> elements() { return Queue; }
 564
 565   iterator find(SUnit *SU) { return llvm::find(Queue, SU); }
 566
 567   void push(SUnit *SU) {
 568     Queue.push_back(SU);
 569     SU->NodeQueueId |= ID;
 570   }
 571
 572   iterator remove(iterator I) {
 573     (*I)->NodeQueueId &= ~ID;
 574     *I = Queue.back();
 575     unsigned idx = I - Queue.begin();
 576     Queue.pop_back();
 577     return Queue.begin() + idx;
 578   }
 579
 580   void dump() const;
 581 };
 582
 583 /// Summarize the unscheduled region.
 584 struct SchedRemainder {
 585   // Critical path through the DAG in expected latency.
 586   unsigned CriticalPath;
 587   unsigned CyclicCritPath;
 588
 589   // Scaled count of micro-ops left to schedule.
 590   unsigned RemIssueCount;
 591
 592   bool IsAcyclicLatencyLimited;
 593
 594   // Unscheduled resources
 595   SmallVector<unsigned, 16> RemainingCounts;
 596
 597   SchedRemainder() { reset(); }
 598
 599   void reset() {
 600     CriticalPath = 0;
 601     CyclicCritPath = 0;
 602     RemIssueCount = 0;
 603     IsAcyclicLatencyLimited = false;
 604     RemainingCounts.clear();
 605   }
 606
 607   void init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel);
 608 };
 609
 610 /// Each Scheduling boundary is associated with ready queues. It tracks the
 611 /// current cycle in the direction of movement, and maintains the state
 612 /// of "hazards" and other interlocks at the current cycle.
 613 class SchedBoundary {
 614 public:
 615   /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
 616   enum {
 617     TopQID = 1,
 618     BotQID = 2,
 619     LogMaxQID = 2
 620   };
 621
 622   ScheduleDAGMI *DAG = nullptr;
 623   const TargetSchedModel *SchedModel = nullptr;
 624   SchedRemainder *Rem = nullptr;
 625
 626   ReadyQueue Available;
 627   ReadyQueue Pending;
 628
 629   ScheduleHazardRecognizer *HazardRec = nullptr;
 630
 631 private:
 632   /// True if the pending Q should be checked/updated before scheduling another
 633   /// instruction.
 634   bool CheckPending;
 635
 636   /// Number of cycles it takes to issue the instructions scheduled in this
 637   /// zone. It is defined as: scheduled-micro-ops / issue-width + stalls.
 638   /// See getStalls().
 639   unsigned CurrCycle;
 640
 641   /// Micro-ops issued in the current cycle
 642   unsigned CurrMOps;
 643
 644   /// MinReadyCycle - Cycle of the soonest available instruction.
 645   unsigned MinReadyCycle;
 646
 647   // The expected latency of the critical path in this scheduled zone.
 648   unsigned ExpectedLatency;
 649
 650   // The latency of dependence chains leading into this zone.
 651   // For each node scheduled bottom-up: DLat = max DLat, N.Depth.
 652   // For each cycle scheduled: DLat -= 1.
 653   unsigned DependentLatency;
 654
 655   /// Count the scheduled (issued) micro-ops that can be retired by
 656   /// time=CurrCycle assuming the first scheduled instr is retired at time=0.
 657   unsigned RetiredMOps;
 658
 659   // Count scheduled resources that have been executed. Resources are
 660   // considered executed if they become ready in the time that it takes to
 661   // saturate any resource including the one in question. Counts are scaled
 662   // for direct comparison with other resources. Counts can be compared with
 663   // MOps * getMicroOpFactor and Latency * getLatencyFactor.
 664   SmallVector<unsigned, 16> ExecutedResCounts;
 665
 666   /// Cache the max count for a single resource.
 667   unsigned MaxExecutedResCount;
 668
 669   // Cache the critical resources ID in this scheduled zone.
 670   unsigned ZoneCritResIdx;
 671
 672   // Is the scheduled region resource limited vs. latency limited.
 673   bool IsResourceLimited;
 674
 675   // Record the highest cycle at which each resource has been reserved by a
 676   // scheduled instruction.
 677   SmallVector<unsigned, 16> ReservedCycles;
 678
 679   // For each PIdx, stores first index into ReservedCycles that corresponds to
 680   // it.
 681   SmallVector<unsigned, 16> ReservedCyclesIndex;
 682
 683   // For each PIdx, stores the resource group IDs of its subunits
 684   SmallVector<APInt, 16> ResourceGroupSubUnitMasks;
 685
 686 #ifndef NDEBUG
 687   // Remember the greatest possible stall as an upper bound on the number of
 688   // times we should retry the pending queue because of a hazard.
 689   unsigned MaxObservedStall;
 690 #endif
 691
 692 public:
 693   /// Pending queues extend the ready queues with the same ID and the
 694   /// PendingFlag set.
 695   SchedBoundary(unsigned ID, const Twine &Name):
 696     Available(ID, Name+".A"), Pending(ID << LogMaxQID, Name+".P") {
 697     reset();
 698   }
 699
 700   ~SchedBoundary();
 701
 702   void reset();
 703
 704   void init(ScheduleDAGMI *dag, const TargetSchedModel *smodel,
 705             SchedRemainder *rem);
 706
 707   bool isTop() const {
 708     return Available.getID() == TopQID;
 709   }
 710
 711   /// Number of cycles to issue the instructions scheduled in this zone.
 712   unsigned getCurrCycle() const { return CurrCycle; }
 713
 714   /// Micro-ops issued in the current cycle
 715   unsigned getCurrMOps() const { return CurrMOps; }
 716
 717   // The latency of dependence chains leading into this zone.
 718   unsigned getDependentLatency() const { return DependentLatency; }
 719
 720   /// Get the number of latency cycles "covered" by the scheduled
 721   /// instructions. This is the larger of the critical path within the zone
 722   /// and the number of cycles required to issue the instructions.
 723   unsigned getScheduledLatency() const {
 724     return std::max(ExpectedLatency, CurrCycle);
 725   }
 726
 727   unsigned getUnscheduledLatency(SUnit *SU) const {
 728     return isTop() ? SU->getHeight() : SU->getDepth();
 729   }
 730
 731   unsigned getResourceCount(unsigned ResIdx) const {
 732     return ExecutedResCounts[ResIdx];
 733   }
 734
 735   /// Get the scaled count of scheduled micro-ops and resources, including
 736   /// executed resources.
 737   unsigned getCriticalCount() const {
 738     if (!ZoneCritResIdx)
 739       return RetiredMOps * SchedModel->getMicroOpFactor();
 740     return getResourceCount(ZoneCritResIdx);
 741   }
 742
 743   /// Get a scaled count for the minimum execution time of the scheduled
 744   /// micro-ops that are ready to execute by getExecutedCount. Notice the
 745   /// feedback loop.
 746   unsigned getExecutedCount() const {
 747     return std::max(CurrCycle * SchedModel->getLatencyFactor(),
 748                     MaxExecutedResCount);
 749   }
 750
 751   unsigned getZoneCritResIdx() const { return ZoneCritResIdx; }
 752
 753   // Is the scheduled region resource limited vs. latency limited.
 754   bool isResourceLimited() const { return IsResourceLimited; }
 755
 756   /// Get the difference between the given SUnit's ready time and the current
 757   /// cycle.
 758   unsigned getLatencyStallCycles(SUnit *SU);
 759
 760   unsigned getNextResourceCycleByInstance(unsigned InstanceIndex,
 761                                           unsigned Cycles);
 762
 763   std::pair<unsigned, unsigned> getNextResourceCycle(const MCSchedClassDesc *SC,
 764                                                      unsigned PIdx,
 765                                                      unsigned Cycles);
 766
 767   bool isUnbufferedGroup(unsigned PIdx) const {
 768     return SchedModel->getProcResource(PIdx)->SubUnitsIdxBegin &&
 769            !SchedModel->getProcResource(PIdx)->BufferSize;
 770   }
 771
 772   bool checkHazard(SUnit *SU);
 773
 774   unsigned findMaxLatency(ArrayRef<SUnit*> ReadySUs);
 775
 776   unsigned getOtherResourceCount(unsigned &OtherCritIdx);
 777
 778   /// Release SU to make it ready. If it's not in hazard, remove it from
 779   /// pending queue (if already in) and push into available queue.
 780   /// Otherwise, push the SU into pending queue.
 781   ///
 782   /// @param SU The unit to be released.
 783   /// @param ReadyCycle Until which cycle the unit is ready.
 784   /// @param InPQueue Whether SU is already in pending queue.
 785   /// @param Idx Position offset in pending queue (if in it).
 786   void releaseNode(SUnit *SU, unsigned ReadyCycle, bool InPQueue,
 787                    unsigned Idx = 0);
 788
 789   void bumpCycle(unsigned NextCycle);
 790
 791   void incExecutedResources(unsigned PIdx, unsigned Count);
 792
 793   unsigned countResource(const MCSchedClassDesc *SC, unsigned PIdx,
 794                          unsigned Cycles, unsigned ReadyCycle);
 795
 796   void bumpNode(SUnit *SU);
 797
 798   void releasePending();
 799
 800   void removeReady(SUnit *SU);
 801
 802   /// Call this before applying any other heuristics to the Available queue.
 803   /// Updates the Available/Pending Q's if necessary and returns the single
 804   /// available instruction, or NULL if there are multiple candidates.
 805   SUnit *pickOnlyChoice();
 806
 807   void dumpScheduledState() const;
 808 };
 809
 810 /// Base class for GenericScheduler. This class maintains information about
 811 /// scheduling candidates based on TargetSchedModel making it easy to implement
 812 /// heuristics for either preRA or postRA scheduling.
 813 class GenericSchedulerBase : public MachineSchedStrategy {
 814 public:
 815   /// Represent the type of SchedCandidate found within a single queue.
 816   /// pickNodeBidirectional depends on these listed by decreasing priority.
 817   enum CandReason : uint8_t {
 818     NoCand, Only1, PhysReg, RegExcess, RegCritical, Stall, Cluster, Weak,
 819     RegMax, ResourceReduce, ResourceDemand, BotHeightReduce, BotPathReduce,
 820     TopDepthReduce, TopPathReduce, NextDefUse, NodeOrder};
 821
 822 #ifndef NDEBUG
 823   static const char *getReasonStr(GenericSchedulerBase::CandReason Reason);
 824 #endif
 825
 826   /// Policy for scheduling the next instruction in the candidate's zone.
 827   struct CandPolicy {
 828     bool ReduceLatency = false;
 829     unsigned ReduceResIdx = 0;
 830     unsigned DemandResIdx = 0;
 831
 832     CandPolicy() = default;
 833
 834     bool operator==(const CandPolicy &RHS) const {
 835       return ReduceLatency == RHS.ReduceLatency &&
 836              ReduceResIdx == RHS.ReduceResIdx &&
 837              DemandResIdx == RHS.DemandResIdx;
 838     }
 839     bool operator!=(const CandPolicy &RHS) const {
 840       return !(*this == RHS);
 841     }
 842   };
 843
 844   /// Status of an instruction's critical resource consumption.
 845   struct SchedResourceDelta {
 846     // Count critical resources in the scheduled region required by SU.
 847     unsigned CritResources = 0;
 848
 849     // Count critical resources from another region consumed by SU.
 850     unsigned DemandedResources = 0;
 851
 852     SchedResourceDelta() = default;
 853
 854     bool operator==(const SchedResourceDelta &RHS) const {
 855       return CritResources == RHS.CritResources
 856         && DemandedResources == RHS.DemandedResources;
 857     }
 858     bool operator!=(const SchedResourceDelta &RHS) const {
 859       return !operator==(RHS);
 860     }
 861   };
 862
 863   /// Store the state used by GenericScheduler heuristics, required for the
 864   /// lifetime of one invocation of pickNode().
 865   struct SchedCandidate {
 866     CandPolicy Policy;
 867
 868     // The best SUnit candidate.
 869     SUnit *SU;
 870
 871     // The reason for this candidate.
 872     CandReason Reason;
 873
 874     // Whether this candidate should be scheduled at top/bottom.
 875     bool AtTop;
 876
 877     // Register pressure values for the best candidate.
 878     RegPressureDelta RPDelta;
 879
 880     // Critical resource consumption of the best candidate.
 881     SchedResourceDelta ResDelta;
 882
 883     SchedCandidate() { reset(CandPolicy()); }
 884     SchedCandidate(const CandPolicy &Policy) { reset(Policy); }
 885
 886     void reset(const CandPolicy &NewPolicy) {
 887       Policy = NewPolicy;
 888       SU = nullptr;
 889       Reason = NoCand;
 890       AtTop = false;
 891       RPDelta = RegPressureDelta();
 892       ResDelta = SchedResourceDelta();
 893     }
 894
 895     bool isValid() const { return SU; }
 896
 897     // Copy the status of another candidate without changing policy.
 898     void setBest(SchedCandidate &Best) {
 899       assert(Best.Reason != NoCand && "uninitialized Sched candidate");
 900       SU = Best.SU;
 901       Reason = Best.Reason;
 902       AtTop = Best.AtTop;
 903       RPDelta = Best.RPDelta;
 904       ResDelta = Best.ResDelta;
 905     }
 906
 907     void initResourceDelta(const ScheduleDAGMI *DAG,
 908                            const TargetSchedModel *SchedModel);
 909   };
 910
 911 protected:
 912   const MachineSchedContext *Context;
 913   const TargetSchedModel *SchedModel = nullptr;
 914   const TargetRegisterInfo *TRI = nullptr;
 915
 916   SchedRemainder Rem;
 917
 918   GenericSchedulerBase(const MachineSchedContext *C) : Context(C) {}
 919
 920   void setPolicy(CandPolicy &Policy, bool IsPostRA, SchedBoundary &CurrZone,
 921                  SchedBoundary *OtherZone);
 922
 923 #ifndef NDEBUG
 924   void traceCandidate(const SchedCandidate &Cand);
 925 #endif
 926
 927 private:
 928   bool shouldReduceLatency(const CandPolicy &Policy, SchedBoundary &CurrZone,
 929                            bool ComputeRemLatency, unsigned &RemLatency) const;
 930 };
 931
 932 // Utility functions used by heuristics in tryCandidate().
 933 bool tryLess(int TryVal, int CandVal,
 934              GenericSchedulerBase::SchedCandidate &TryCand,
 935              GenericSchedulerBase::SchedCandidate &Cand,
 936              GenericSchedulerBase::CandReason Reason);
 937 bool tryGreater(int TryVal, int CandVal,
 938                 GenericSchedulerBase::SchedCandidate &TryCand,
 939                 GenericSchedulerBase::SchedCandidate &Cand,
 940                 GenericSchedulerBase::CandReason Reason);
 941 bool tryLatency(GenericSchedulerBase::SchedCandidate &TryCand,
 942                 GenericSchedulerBase::SchedCandidate &Cand,
 943                 SchedBoundary &Zone);
 944 bool tryPressure(const PressureChange &TryP,
 945                  const PressureChange &CandP,
 946                  GenericSchedulerBase::SchedCandidate &TryCand,
 947                  GenericSchedulerBase::SchedCandidate &Cand,
 948                  GenericSchedulerBase::CandReason Reason,
 949                  const TargetRegisterInfo *TRI,
 950                  const MachineFunction &MF);
 951 unsigned getWeakLeft(const SUnit *SU, bool isTop);
 952 int biasPhysReg(const SUnit *SU, bool isTop);
 953
 954 /// GenericScheduler shrinks the unscheduled zone using heuristics to balance
 955 /// the schedule.
 956 class GenericScheduler : public GenericSchedulerBase {
 957 public:
 958   GenericScheduler(const MachineSchedContext *C):
 959     GenericSchedulerBase(C), Top(SchedBoundary::TopQID, "TopQ"),
 960     Bot(SchedBoundary::BotQID, "BotQ") {}
 961
 962   void initPolicy(MachineBasicBlock::iterator Begin,
 963                   MachineBasicBlock::iterator End,
 964                   unsigned NumRegionInstrs) override;
 965
 966   void dumpPolicy() const override;
 967
 968   bool shouldTrackPressure() const override {
 969     return RegionPolicy.ShouldTrackPressure;
 970   }
 971
 972   bool shouldTrackLaneMasks() const override {
 973     return RegionPolicy.ShouldTrackLaneMasks;
 974   }
 975
 976   void initialize(ScheduleDAGMI *dag) override;
 977
 978   SUnit *pickNode(bool &IsTopNode) override;
 979
 980   void schedNode(SUnit *SU, bool IsTopNode) override;
 981
 982   void releaseTopNode(SUnit *SU) override {
 983     if (SU->isScheduled)
 984       return;
 985
 986     Top.releaseNode(SU, SU->TopReadyCycle, false);
 987     TopCand.SU = nullptr;
 988   }
 989
 990   void releaseBottomNode(SUnit *SU) override {
 991     if (SU->isScheduled)
 992       return;
 993
 994     Bot.releaseNode(SU, SU->BotReadyCycle, false);
 995     BotCand.SU = nullptr;
 996   }
 997
 998   void registerRoots() override;
 999
1000 protected:
1001   ScheduleDAGMILive *DAG = nullptr;
1002
1003   MachineSchedPolicy RegionPolicy;
1004
1005   // State of the top and bottom scheduled instruction boundaries.
1006   SchedBoundary Top;
1007   SchedBoundary Bot;
1008
1009   /// Candidate last picked from Top boundary.
1010   SchedCandidate TopCand;
1011   /// Candidate last picked from Bot boundary.
1012   SchedCandidate BotCand;
1013
1014   void checkAcyclicLatency();
1015
1016   void initCandidate(SchedCandidate &Cand, SUnit *SU, bool AtTop,
1017                      const RegPressureTracker &RPTracker,
1018                      RegPressureTracker &TempTracker);
1019
1020   virtual bool tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand,
1021                             SchedBoundary *Zone) const;
1022
1023   SUnit *pickNodeBidirectional(bool &IsTopNode);
1024
1025   void pickNodeFromQueue(SchedBoundary &Zone,
1026                          const CandPolicy &ZonePolicy,
1027                          const RegPressureTracker &RPTracker,
1028                          SchedCandidate &Candidate);
1029
1030   void reschedulePhysReg(SUnit *SU, bool isTop);
1031 };
1032
1033 /// PostGenericScheduler - Interface to the scheduling algorithm used by
1034 /// ScheduleDAGMI.
1035 ///
1036 /// Callbacks from ScheduleDAGMI:
1037 ///   initPolicy -> initialize(DAG) -> registerRoots -> pickNode ...
1038 class PostGenericScheduler : public GenericSchedulerBase {
1039 protected:
1040   ScheduleDAGMI *DAG = nullptr;
1041   SchedBoundary Top;
1042   SmallVector<SUnit*, 8> BotRoots;
1043
1044 public:
1045   PostGenericScheduler(const MachineSchedContext *C):
1046     GenericSchedulerBase(C), Top(SchedBoundary::TopQID, "TopQ") {}
1047
1048   ~PostGenericScheduler() override = default;
1049
1050   void initPolicy(MachineBasicBlock::iterator Begin,
1051                   MachineBasicBlock::iterator End,
1052                   unsigned NumRegionInstrs) override {
1053     /* no configurable policy */
1054   }
1055
1056   /// PostRA scheduling does not track pressure.
1057   bool shouldTrackPressure() const override { return false; }
1058
1059   void initialize(ScheduleDAGMI *Dag) override;
1060
1061   void registerRoots() override;
1062
1063   SUnit *pickNode(bool &IsTopNode) override;
1064
1065   void scheduleTree(unsigned SubtreeID) override {
1066     llvm_unreachable("PostRA scheduler does not support subtree analysis.");
1067   }
1068
1069   void schedNode(SUnit *SU, bool IsTopNode) override;
1070
1071   void releaseTopNode(SUnit *SU) override {
1072     if (SU->isScheduled)
1073       return;
1074     Top.releaseNode(SU, SU->TopReadyCycle, false);
1075   }
1076
1077   // Only called for roots.
1078   void releaseBottomNode(SUnit *SU) override {
1079     BotRoots.push_back(SU);
1080   }
1081
1082 protected:
1083   virtual bool tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand);
1084
1085   void pickNodeFromQueue(SchedCandidate &Cand);
1086 };
1087
1088 /// Create the standard converging machine scheduler. This will be used as the
1089 /// default scheduler if the target does not set a default.
1090 /// Adds default DAG mutations.
1091 ScheduleDAGMILive *createGenericSchedLive(MachineSchedContext *C);
1092
1093 /// Create a generic scheduler with no vreg liveness or DAG mutation passes.
1094 ScheduleDAGMI *createGenericSchedPostRA(MachineSchedContext *C);
1095
1096 std::unique_ptr<ScheduleDAGMutation>
1097 createLoadClusterDAGMutation(const TargetInstrInfo *TII,
1098                              const TargetRegisterInfo *TRI);
1099
1100 std::unique_ptr<ScheduleDAGMutation>
1101 createStoreClusterDAGMutation(const TargetInstrInfo *TII,
1102                               const TargetRegisterInfo *TRI);
1103
1104 std::unique_ptr<ScheduleDAGMutation>
1105 createCopyConstrainDAGMutation(const TargetInstrInfo *TII,
1106                                const TargetRegisterInfo *TRI);
1107
1108 } // end namespace llvm
1109
1110 #endif // LLVM_CODEGEN_MACHINESCHEDULER_H