lib/Target/Hexagon/HexagonMachineScheduler.h

   1 //===- HexagonMachineScheduler.h - Custom Hexagon MI scheduler --*- 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 // Custom Hexagon MI scheduler.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #ifndef LLVM_LIB_TARGET_HEXAGON_HEXAGONMACHINESCHEDULER_H
  14 #define LLVM_LIB_TARGET_HEXAGON_HEXAGONMACHINESCHEDULER_H
  15
  16 #include "llvm/ADT/STLExtras.h"
  17 #include "llvm/ADT/Twine.h"
  18 #include "llvm/CodeGen/DFAPacketizer.h"
  19 #include "llvm/CodeGen/MachineScheduler.h"
  20 #include "llvm/CodeGen/RegisterPressure.h"
  21 #include "llvm/CodeGen/ScheduleHazardRecognizer.h"
  22 #include "llvm/CodeGen/TargetInstrInfo.h"
  23 #include "llvm/CodeGen/TargetSchedule.h"
  24 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  25 #include <algorithm>
  26 #include <cassert>
  27 #include <limits>
  28 #include <memory>
  29 #include <vector>
  30
  31 namespace llvm {
  32
  33 class SUnit;
  34
  35 class VLIWResourceModel {
  36   /// ResourcesModel - Represents VLIW state.
  37   /// Not limited to VLIW targets per se, but assumes
  38   /// definition of DFA by a target.
  39   DFAPacketizer *ResourcesModel;
  40
  41   const TargetSchedModel *SchedModel;
  42
  43   /// Local packet/bundle model. Purely
  44   /// internal to the MI schedulre at the time.
  45   std::vector<SUnit *> Packet;
  46
  47   /// Total packets created.
  48   unsigned TotalPackets = 0;
  49
  50 public:
  51   VLIWResourceModel(const TargetSubtargetInfo &STI, const TargetSchedModel *SM)
  52       : SchedModel(SM) {
  53     ResourcesModel = STI.getInstrInfo()->CreateTargetScheduleState(STI);
  54
  55     // This hard requirement could be relaxed,
  56     // but for now do not let it proceed.
  57     assert(ResourcesModel && "Unimplemented CreateTargetScheduleState.");
  58
  59     Packet.resize(SchedModel->getIssueWidth());
  60     Packet.clear();
  61     ResourcesModel->clearResources();
  62   }
  63
  64   ~VLIWResourceModel() {
  65     delete ResourcesModel;
  66   }
  67
  68   void resetPacketState() {
  69     Packet.clear();
  70   }
  71
  72   void resetDFA() {
  73     ResourcesModel->clearResources();
  74   }
  75
  76   void reset() {
  77     Packet.clear();
  78     ResourcesModel->clearResources();
  79   }
  80
  81   bool isResourceAvailable(SUnit *SU, bool IsTop);
  82   bool reserveResources(SUnit *SU, bool IsTop);
  83   unsigned getTotalPackets() const { return TotalPackets; }
  84   bool isInPacket(SUnit *SU) const { return is_contained(Packet, SU); }
  85 };
  86
  87 /// Extend the standard ScheduleDAGMI to provide more context and override the
  88 /// top-level schedule() driver.
  89 class VLIWMachineScheduler : public ScheduleDAGMILive {
  90 public:
  91   VLIWMachineScheduler(MachineSchedContext *C,
  92                        std::unique_ptr<MachineSchedStrategy> S)
  93       : ScheduleDAGMILive(C, std::move(S)) {}
  94
  95   /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's
  96   /// time to do some work.
  97   void schedule() override;
  98
  99   RegisterClassInfo *getRegClassInfo() { return RegClassInfo; }
 100   int getBBSize() { return BB->size(); }
 101 };
 102
 103 //===----------------------------------------------------------------------===//
 104 // ConvergingVLIWScheduler - Implementation of the standard
 105 // MachineSchedStrategy.
 106 //===----------------------------------------------------------------------===//
 107
 108 /// ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics
 109 /// to balance the schedule.
 110 class ConvergingVLIWScheduler : public MachineSchedStrategy {
 111   /// Store the state used by ConvergingVLIWScheduler heuristics, required
 112   ///  for the lifetime of one invocation of pickNode().
 113   struct SchedCandidate {
 114     // The best SUnit candidate.
 115     SUnit *SU = nullptr;
 116
 117     // Register pressure values for the best candidate.
 118     RegPressureDelta RPDelta;
 119
 120     // Best scheduling cost.
 121     int SCost = 0;
 122
 123     SchedCandidate() = default;
 124   };
 125   /// Represent the type of SchedCandidate found within a single queue.
 126   enum CandResult {
 127     NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure,
 128     BestCost, Weak};
 129
 130   /// Each Scheduling boundary is associated with ready queues. It tracks the
 131   /// current cycle in whichever direction at has moved, and maintains the state
 132   /// of "hazards" and other interlocks at the current cycle.
 133   struct VLIWSchedBoundary {
 134     VLIWMachineScheduler *DAG = nullptr;
 135     const TargetSchedModel *SchedModel = nullptr;
 136
 137     ReadyQueue Available;
 138     ReadyQueue Pending;
 139     bool CheckPending = false;
 140
 141     ScheduleHazardRecognizer *HazardRec = nullptr;
 142     VLIWResourceModel *ResourceModel = nullptr;
 143
 144     unsigned CurrCycle = 0;
 145     unsigned IssueCount = 0;
 146     unsigned CriticalPathLength = 0;
 147
 148     /// MinReadyCycle - Cycle of the soonest available instruction.
 149     unsigned MinReadyCycle = std::numeric_limits<unsigned>::max();
 150
 151     // Remember the greatest min operand latency.
 152     unsigned MaxMinLatency = 0;
 153
 154     /// Pending queues extend the ready queues with the same ID and the
 155     /// PendingFlag set.
 156     VLIWSchedBoundary(unsigned ID, const Twine &Name)
 157         : Available(ID, Name+".A"),
 158           Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name+".P") {}
 159
 160     ~VLIWSchedBoundary() {
 161       delete ResourceModel;
 162       delete HazardRec;
 163     }
 164
 165     void init(VLIWMachineScheduler *dag, const TargetSchedModel *smodel) {
 166       DAG = dag;
 167       SchedModel = smodel;
 168       CurrCycle = 0;
 169       IssueCount = 0;
 170       // Initialize the critical path length limit, which used by the scheduling
 171       // cost model to determine the value for scheduling an instruction. We use
 172       // a slightly different heuristic for small and large functions. For small
 173       // functions, it's important to use the height/depth of the instruction.
 174       // For large functions, prioritizing by height or depth increases spills.
 175       CriticalPathLength = DAG->getBBSize() / SchedModel->getIssueWidth();
 176       if (DAG->getBBSize() < 50)
 177         // We divide by two as a cheap and simple heuristic to reduce the
 178         // critcal path length, which increases the priority of using the graph
 179         // height/depth in the scheduler's cost computation.
 180         CriticalPathLength >>= 1;
 181       else {
 182         // For large basic blocks, we prefer a larger critical path length to
 183         // decrease the priority of using the graph height/depth.
 184         unsigned MaxPath = 0;
 185         for (auto &SU : DAG->SUnits)
 186           MaxPath = std::max(MaxPath, isTop() ? SU.getHeight() : SU.getDepth());
 187         CriticalPathLength = std::max(CriticalPathLength, MaxPath) + 1;
 188       }
 189     }
 190
 191     bool isTop() const {
 192       return Available.getID() == ConvergingVLIWScheduler::TopQID;
 193     }
 194
 195     bool checkHazard(SUnit *SU);
 196
 197     void releaseNode(SUnit *SU, unsigned ReadyCycle);
 198
 199     void bumpCycle();
 200
 201     void bumpNode(SUnit *SU);
 202
 203     void releasePending();
 204
 205     void removeReady(SUnit *SU);
 206
 207     SUnit *pickOnlyChoice();
 208
 209     bool isLatencyBound(SUnit *SU) {
 210       if (CurrCycle >= CriticalPathLength)
 211         return true;
 212       unsigned PathLength = isTop() ? SU->getHeight() : SU->getDepth();
 213       return CriticalPathLength - CurrCycle <= PathLength;
 214     }
 215   };
 216
 217   VLIWMachineScheduler *DAG = nullptr;
 218   const TargetSchedModel *SchedModel = nullptr;
 219
 220   // State of the top and bottom scheduled instruction boundaries.
 221   VLIWSchedBoundary Top;
 222   VLIWSchedBoundary Bot;
 223
 224   /// List of pressure sets that have a high pressure level in the region.
 225   std::vector<bool> HighPressureSets;
 226
 227 public:
 228   /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
 229   enum {
 230     TopQID = 1,
 231     BotQID = 2,
 232     LogMaxQID = 2
 233   };
 234
 235   ConvergingVLIWScheduler() : Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {}
 236
 237   void initialize(ScheduleDAGMI *dag) override;
 238
 239   SUnit *pickNode(bool &IsTopNode) override;
 240
 241   void schedNode(SUnit *SU, bool IsTopNode) override;
 242
 243   void releaseTopNode(SUnit *SU) override;
 244
 245   void releaseBottomNode(SUnit *SU) override;
 246
 247   unsigned reportPackets() {
 248     return Top.ResourceModel->getTotalPackets() +
 249            Bot.ResourceModel->getTotalPackets();
 250   }
 251
 252 protected:
 253   SUnit *pickNodeBidrectional(bool &IsTopNode);
 254
 255   int pressureChange(const SUnit *SU, bool isBotUp);
 256
 257   int SchedulingCost(ReadyQueue &Q,
 258                      SUnit *SU, SchedCandidate &Candidate,
 259                      RegPressureDelta &Delta, bool verbose);
 260
 261   CandResult pickNodeFromQueue(VLIWSchedBoundary &Zone,
 262                                const RegPressureTracker &RPTracker,
 263                                SchedCandidate &Candidate);
 264 #ifndef NDEBUG
 265   void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU,
 266                       int Cost, PressureChange P = PressureChange());
 267
 268   void readyQueueVerboseDump(const RegPressureTracker &RPTracker,
 269                              SchedCandidate &Candidate, ReadyQueue &Q);
 270 #endif
 271 };
 272
 273 } // end namespace llvm
 274
 275 #endif // LLVM_LIB_TARGET_HEXAGON_HEXAGONMACHINESCHEDULER_H