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