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

   1 //===-- HexagonMachineScheduler.h - Custom Hexagon MI scheduler.      ----===//
   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/PriorityQueue.h"
  18 #include "llvm/Analysis/AliasAnalysis.h"
  19 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  20 #include "llvm/CodeGen/MachineScheduler.h"
  21 #include "llvm/CodeGen/Passes.h"
  22 #include "llvm/CodeGen/RegisterClassInfo.h"
  23 #include "llvm/CodeGen/RegisterPressure.h"
  24 #include "llvm/CodeGen/ResourcePriorityQueue.h"
  25 #include "llvm/CodeGen/ScheduleDAGInstrs.h"
  26 #include "llvm/CodeGen/ScheduleHazardRecognizer.h"
  27 #include "llvm/Support/Debug.h"
  28 #include "llvm/Support/ErrorHandling.h"
  29 #include "llvm/Support/raw_ostream.h"
  30 #include "llvm/Target/TargetInstrInfo.h"
  31
  32 using namespace llvm;
  33
  34 namespace llvm {
  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;
  50
  51 public:
  52   /// Save the last formed packet.
  53   std::vector<SUnit*> OldPacket;
  54
  55 public:
  56   VLIWResourceModel(const TargetSubtargetInfo &STI, const TargetSchedModel *SM)
  57       : SchedModel(SM), TotalPackets(0) {
  58   ResourcesModel = STI.getInstrInfo()->CreateTargetScheduleState(STI);
  59
  60     // This hard requirement could be relaxed,
  61     // but for now do not let it proceed.
  62     assert(ResourcesModel && "Unimplemented CreateTargetScheduleState.");
  63
  64     Packet.resize(SchedModel->getIssueWidth());
  65     Packet.clear();
  66     OldPacket.resize(SchedModel->getIssueWidth());
  67     OldPacket.clear();
  68     ResourcesModel->clearResources();
  69   }
  70
  71   ~VLIWResourceModel() {
  72     delete ResourcesModel;
  73   }
  74
  75   void resetPacketState() {
  76     Packet.clear();
  77   }
  78
  79   void resetDFA() {
  80     ResourcesModel->clearResources();
  81   }
  82
  83   void reset() {
  84     Packet.clear();
  85     ResourcesModel->clearResources();
  86   }
  87
  88   bool isResourceAvailable(SUnit *SU);
  89   bool reserveResources(SUnit *SU);
  90   void savePacket();
  91   unsigned getTotalPackets() const { return TotalPackets; }
  92
  93   bool isInPacket(SUnit *SU) const { return is_contained(Packet, SU); }
  94 };
  95
  96 /// Extend the standard ScheduleDAGMI to provide more context and override the
  97 /// top-level schedule() driver.
  98 class VLIWMachineScheduler : public ScheduleDAGMILive {
  99 public:
 100   VLIWMachineScheduler(MachineSchedContext *C,
 101                        std::unique_ptr<MachineSchedStrategy> S)
 102       : ScheduleDAGMILive(C, std::move(S)) {}
 103
 104   /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's
 105   /// time to do some work.
 106   void schedule() override;
 107 };
 108
 109 //===----------------------------------------------------------------------===//
 110 // ConvergingVLIWScheduler - Implementation of the standard
 111 // MachineSchedStrategy.
 112 //===----------------------------------------------------------------------===//
 113
 114 /// ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics
 115 /// to balance the schedule.
 116 class ConvergingVLIWScheduler : public MachineSchedStrategy {
 117
 118   /// Store the state used by ConvergingVLIWScheduler heuristics, required
 119   ///  for the lifetime of one invocation of pickNode().
 120   struct SchedCandidate {
 121     // The best SUnit candidate.
 122     SUnit *SU;
 123
 124     // Register pressure values for the best candidate.
 125     RegPressureDelta RPDelta;
 126
 127     // Best scheduling cost.
 128     int SCost;
 129
 130     SchedCandidate(): SU(nullptr), SCost(0) {}
 131   };
 132   /// Represent the type of SchedCandidate found within a single queue.
 133   enum CandResult {
 134     NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure,
 135     BestCost};
 136
 137   /// Each Scheduling boundary is associated with ready queues. It tracks the
 138   /// current cycle in whichever direction at has moved, and maintains the state
 139   /// of "hazards" and other interlocks at the current cycle.
 140   struct VLIWSchedBoundary {
 141     VLIWMachineScheduler *DAG;
 142     const TargetSchedModel *SchedModel;
 143
 144     ReadyQueue Available;
 145     ReadyQueue Pending;
 146     bool CheckPending;
 147
 148     ScheduleHazardRecognizer *HazardRec;
 149     VLIWResourceModel *ResourceModel;
 150
 151     unsigned CurrCycle;
 152     unsigned IssueCount;
 153
 154     /// MinReadyCycle - Cycle of the soonest available instruction.
 155     unsigned MinReadyCycle;
 156
 157     // Remember the greatest min operand latency.
 158     unsigned MaxMinLatency;
 159
 160     /// Pending queues extend the ready queues with the same ID and the
 161     /// PendingFlag set.
 162     VLIWSchedBoundary(unsigned ID, const Twine &Name):
 163       DAG(nullptr), SchedModel(nullptr), Available(ID, Name+".A"),
 164       Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name+".P"),
 165       CheckPending(false), HazardRec(nullptr), ResourceModel(nullptr),
 166       CurrCycle(0), IssueCount(0),
 167       MinReadyCycle(UINT_MAX), MaxMinLatency(0) {}
 168
 169     ~VLIWSchedBoundary() {
 170       delete ResourceModel;
 171       delete HazardRec;
 172     }
 173
 174     void init(VLIWMachineScheduler *dag, const TargetSchedModel *smodel) {
 175       DAG = dag;
 176       SchedModel = smodel;
 177       IssueCount = 0;
 178     }
 179
 180     bool isTop() const {
 181       return Available.getID() == ConvergingVLIWScheduler::TopQID;
 182     }
 183
 184     bool checkHazard(SUnit *SU);
 185
 186     void releaseNode(SUnit *SU, unsigned ReadyCycle);
 187
 188     void bumpCycle();
 189
 190     void bumpNode(SUnit *SU);
 191
 192     void releasePending();
 193
 194     void removeReady(SUnit *SU);
 195
 196     SUnit *pickOnlyChoice();
 197   };
 198
 199   VLIWMachineScheduler *DAG;
 200   const TargetSchedModel *SchedModel;
 201
 202   // State of the top and bottom scheduled instruction boundaries.
 203   VLIWSchedBoundary Top;
 204   VLIWSchedBoundary Bot;
 205
 206 public:
 207   /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
 208   enum {
 209     TopQID = 1,
 210     BotQID = 2,
 211     LogMaxQID = 2
 212   };
 213
 214   ConvergingVLIWScheduler()
 215     : DAG(nullptr), SchedModel(nullptr), Top(TopQID, "TopQ"),
 216       Bot(BotQID, "BotQ") {}
 217
 218   void initialize(ScheduleDAGMI *dag) override;
 219
 220   SUnit *pickNode(bool &IsTopNode) override;
 221
 222   void schedNode(SUnit *SU, bool IsTopNode) override;
 223
 224   void releaseTopNode(SUnit *SU) override;
 225
 226   void releaseBottomNode(SUnit *SU) override;
 227
 228   unsigned ReportPackets() {
 229     return Top.ResourceModel->getTotalPackets() +
 230            Bot.ResourceModel->getTotalPackets();
 231   }
 232
 233 protected:
 234   SUnit *pickNodeBidrectional(bool &IsTopNode);
 235
 236   int SchedulingCost(ReadyQueue &Q,
 237                      SUnit *SU, SchedCandidate &Candidate,
 238                      RegPressureDelta &Delta, bool verbose);
 239
 240   CandResult pickNodeFromQueue(ReadyQueue &Q,
 241                                const RegPressureTracker &RPTracker,
 242                                SchedCandidate &Candidate);
 243 #ifndef NDEBUG
 244   void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU,
 245                       int Cost, PressureChange P = PressureChange());
 246
 247   void readyQueueVerboseDump(const RegPressureTracker &RPTracker,
 248                              SchedCandidate &Candidate, ReadyQueue &Q);
 249 #endif
 250 };
 251
 252 } // namespace
 253
 254
 255 #endif