Home | History | Annotate | Download | only in CodeGen
      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