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