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