contrib/llvm/lib/Target/Hexagon/HexagonMachineScheduler.h

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