llvm/CodeGen/VLIWMachineScheduler.h

0001 //===- VLIWMachineScheduler.h - VLIW-Focused Scheduling Pass ----*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //                                                                            //
0009 //===----------------------------------------------------------------------===//
0010
0011 #ifndef LLVM_CODEGEN_VLIWMACHINESCHEDULER_H
0012 #define LLVM_CODEGEN_VLIWMACHINESCHEDULER_H
0013
0014 #include "llvm/ADT/SmallVector.h"
0015 #include "llvm/ADT/Twine.h"
0016 #include "llvm/CodeGen/MachineScheduler.h"
0017 #include "llvm/CodeGen/TargetSchedule.h"
0018 #include <limits>
0019 #include <memory>
0020 #include <utility>
0021
0022 namespace llvm {
0023
0024 class DFAPacketizer;
0025 class RegisterClassInfo;
0026 class ScheduleHazardRecognizer;
0027 class SUnit;
0028 class TargetInstrInfo;
0029 class TargetSubtargetInfo;
0030
0031 class VLIWResourceModel {
0032 protected:
0033   const TargetInstrInfo *TII;
0034
0035   /// ResourcesModel - Represents VLIW state.
0036   /// Not limited to VLIW targets per se, but assumes definition of resource
0037   /// model by a target.
0038   DFAPacketizer *ResourcesModel;
0039
0040   const TargetSchedModel *SchedModel;
0041
0042   /// Local packet/bundle model. Purely
0043   /// internal to the MI scheduler at the time.
0044   SmallVector<SUnit *> Packet;
0045
0046   /// Total packets created.
0047   unsigned TotalPackets = 0;
0048
0049 public:
0050   VLIWResourceModel(const TargetSubtargetInfo &STI, const TargetSchedModel *SM);
0051   VLIWResourceModel &operator=(const VLIWResourceModel &other) = delete;
0052   VLIWResourceModel(const VLIWResourceModel &other) = delete;
0053   virtual ~VLIWResourceModel();
0054
0055   virtual void reset();
0056
0057   virtual bool hasDependence(const SUnit *SUd, const SUnit *SUu);
0058   virtual bool isResourceAvailable(SUnit *SU, bool IsTop);
0059   virtual bool reserveResources(SUnit *SU, bool IsTop);
0060   unsigned getTotalPackets() const { return TotalPackets; }
0061   size_t getPacketInstCount() const { return Packet.size(); }
0062   bool isInPacket(SUnit *SU) const { return is_contained(Packet, SU); }
0063
0064 protected:
0065   virtual DFAPacketizer *createPacketizer(const TargetSubtargetInfo &STI) const;
0066 };
0067
0068 /// Extend the standard ScheduleDAGMILive to provide more context and override
0069 /// the top-level schedule() driver.
0070 class VLIWMachineScheduler : public ScheduleDAGMILive {
0071 public:
0072   VLIWMachineScheduler(MachineSchedContext *C,
0073                        std::unique_ptr<MachineSchedStrategy> S)
0074       : ScheduleDAGMILive(C, std::move(S)) {}
0075
0076   /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's
0077   /// time to do some work.
0078   void schedule() override;
0079
0080   RegisterClassInfo *getRegClassInfo() { return RegClassInfo; }
0081   int getBBSize() { return BB->size(); }
0082 };
0083
0084 //===----------------------------------------------------------------------===//
0085 // ConvergingVLIWScheduler - Implementation of a VLIW-aware
0086 // MachineSchedStrategy.
0087 //===----------------------------------------------------------------------===//
0088
0089 class ConvergingVLIWScheduler : public MachineSchedStrategy {
0090 protected:
0091   /// Store the state used by ConvergingVLIWScheduler heuristics, required
0092   ///  for the lifetime of one invocation of pickNode().
0093   struct SchedCandidate {
0094     // The best SUnit candidate.
0095     SUnit *SU = nullptr;
0096
0097     // Register pressure values for the best candidate.
0098     RegPressureDelta RPDelta;
0099
0100     // Best scheduling cost.
0101     int SCost = 0;
0102
0103     SchedCandidate() = default;
0104   };
0105   /// Represent the type of SchedCandidate found within a single queue.
0106   enum CandResult {
0107     NoCand,
0108     NodeOrder,
0109     SingleExcess,
0110     SingleCritical,
0111     SingleMax,
0112     MultiPressure,
0113     BestCost,
0114     Weak
0115   };
0116
0117   // Constants used to denote relative importance of
0118   // heuristic components for cost computation.
0119   static constexpr unsigned PriorityOne = 200;
0120   static constexpr unsigned PriorityTwo = 50;
0121   static constexpr unsigned PriorityThree = 75;
0122   static constexpr unsigned ScaleTwo = 10;
0123
0124   /// Each Scheduling boundary is associated with ready queues. It tracks the
0125   /// current cycle in whichever direction at has moved, and maintains the state
0126   /// of "hazards" and other interlocks at the current cycle.
0127   struct VLIWSchedBoundary {
0128     VLIWMachineScheduler *DAG = nullptr;
0129     const TargetSchedModel *SchedModel = nullptr;
0130
0131     ReadyQueue Available;
0132     ReadyQueue Pending;
0133     bool CheckPending = false;
0134
0135     ScheduleHazardRecognizer *HazardRec = nullptr;
0136     VLIWResourceModel *ResourceModel = nullptr;
0137
0138     unsigned CurrCycle = 0;
0139     unsigned IssueCount = 0;
0140     unsigned CriticalPathLength = 0;
0141
0142     /// MinReadyCycle - Cycle of the soonest available instruction.
0143     unsigned MinReadyCycle = std::numeric_limits<unsigned>::max();
0144
0145     // Remember the greatest min operand latency.
0146     unsigned MaxMinLatency = 0;
0147
0148     /// Pending queues extend the ready queues with the same ID and the
0149     /// PendingFlag set.
0150     VLIWSchedBoundary(unsigned ID, const Twine &Name)
0151         : Available(ID, Name + ".A"),
0152           Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name + ".P") {}
0153
0154     ~VLIWSchedBoundary();
0155     VLIWSchedBoundary &operator=(const VLIWSchedBoundary &other) = delete;
0156     VLIWSchedBoundary(const VLIWSchedBoundary &other) = delete;
0157
0158     void init(VLIWMachineScheduler *dag, const TargetSchedModel *smodel) {
0159       DAG = dag;
0160       SchedModel = smodel;
0161       CurrCycle = 0;
0162       IssueCount = 0;
0163       // Initialize the critical path length limit, which used by the scheduling
0164       // cost model to determine the value for scheduling an instruction. We use
0165       // a slightly different heuristic for small and large functions. For small
0166       // functions, it's important to use the height/depth of the instruction.
0167       // For large functions, prioritizing by height or depth increases spills.
0168       const auto BBSize = DAG->getBBSize();
0169       CriticalPathLength = BBSize / SchedModel->getIssueWidth();
0170       if (BBSize < 50)
0171         // We divide by two as a cheap and simple heuristic to reduce the
0172         // critcal path length, which increases the priority of using the graph
0173         // height/depth in the scheduler's cost computation.
0174         CriticalPathLength >>= 1;
0175       else {
0176         // For large basic blocks, we prefer a larger critical path length to
0177         // decrease the priority of using the graph height/depth.
0178         unsigned MaxPath = 0;
0179         for (auto &SU : DAG->SUnits)
0180           MaxPath = std::max(MaxPath, isTop() ? SU.getHeight() : SU.getDepth());
0181         CriticalPathLength = std::max(CriticalPathLength, MaxPath) + 1;
0182       }
0183     }
0184
0185     bool isTop() const {
0186       return Available.getID() == ConvergingVLIWScheduler::TopQID;
0187     }
0188
0189     bool checkHazard(SUnit *SU);
0190
0191     void releaseNode(SUnit *SU, unsigned ReadyCycle);
0192
0193     void bumpCycle();
0194
0195     void bumpNode(SUnit *SU);
0196
0197     void releasePending();
0198
0199     void removeReady(SUnit *SU);
0200
0201     SUnit *pickOnlyChoice();
0202
0203     bool isLatencyBound(SUnit *SU) {
0204       if (CurrCycle >= CriticalPathLength)
0205         return true;
0206       unsigned PathLength = isTop() ? SU->getHeight() : SU->getDepth();
0207       return CriticalPathLength - CurrCycle <= PathLength;
0208     }
0209   };
0210
0211   VLIWMachineScheduler *DAG = nullptr;
0212   const TargetSchedModel *SchedModel = nullptr;
0213
0214   // State of the top and bottom scheduled instruction boundaries.
0215   VLIWSchedBoundary Top;
0216   VLIWSchedBoundary Bot;
0217
0218   /// List of pressure sets that have a high pressure level in the region.
0219   SmallVector<bool> HighPressureSets;
0220
0221 public:
0222   /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
0223   enum { TopQID = 1, BotQID = 2, LogMaxQID = 2 };
0224
0225   ConvergingVLIWScheduler() : Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {}
0226   virtual ~ConvergingVLIWScheduler() = default;
0227
0228   void initialize(ScheduleDAGMI *dag) override;
0229
0230   SUnit *pickNode(bool &IsTopNode) override;
0231
0232   void schedNode(SUnit *SU, bool IsTopNode) override;
0233
0234   void releaseTopNode(SUnit *SU) override;
0235
0236   void releaseBottomNode(SUnit *SU) override;
0237
0238   unsigned reportPackets() {
0239     return Top.ResourceModel->getTotalPackets() +
0240            Bot.ResourceModel->getTotalPackets();
0241   }
0242
0243 protected:
0244   virtual VLIWResourceModel *
0245   createVLIWResourceModel(const TargetSubtargetInfo &STI,
0246                           const TargetSchedModel *SchedModel) const;
0247
0248   SUnit *pickNodeBidrectional(bool &IsTopNode);
0249
0250   int pressureChange(const SUnit *SU, bool isBotUp);
0251
0252   virtual int SchedulingCost(ReadyQueue &Q, SUnit *SU,
0253                              SchedCandidate &Candidate, RegPressureDelta &Delta,
0254                              bool verbose);
0255
0256   CandResult pickNodeFromQueue(VLIWSchedBoundary &Zone,
0257                                const RegPressureTracker &RPTracker,
0258                                SchedCandidate &Candidate);
0259 #ifndef NDEBUG
0260   void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU,
0261                       int Cost, PressureChange P = PressureChange());
0262
0263   void readyQueueVerboseDump(const RegPressureTracker &RPTracker,
0264                              SchedCandidate &Candidate, ReadyQueue &Q);
0265 #endif
0266 };
0267
0268 } // end namespace llvm
0269
0270 #endif // LLVM_CODEGEN_VLIWMACHINESCHEDULER_H