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/ADT/OwningPtr.h"
  18 #include "llvm/ADT/PriorityQueue.h"
  19 #include "llvm/Analysis/AliasAnalysis.h"
  20 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  21 #include "llvm/CodeGen/MachineScheduler.h"
  22 #include "llvm/CodeGen/Passes.h"
  23 #include "llvm/CodeGen/RegisterClassInfo.h"
  24 #include "llvm/CodeGen/RegisterPressure.h"
  25 #include "llvm/CodeGen/ResourcePriorityQueue.h"
  26 #include "llvm/CodeGen/ScheduleDAGInstrs.h"
  27 #include "llvm/CodeGen/ScheduleHazardRecognizer.h"
  28 #include "llvm/Support/CommandLine.h"
  29 #include "llvm/Support/Debug.h"
  30 #include "llvm/Support/ErrorHandling.h"
  31 #include "llvm/Support/raw_ostream.h"
  32 #include "llvm/Target/TargetInstrInfo.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 TargetSchedModel *SchedModel;
  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(const TargetMachine &TM, const TargetSchedModel *SM) :
  59     SchedModel(SM), TotalPackets(0) {
  60     ResourcesModel = TM.getInstrInfo()->CreateTargetScheduleState(&TM,NULL);
  61
  62     // This hard requirement could be relaxed,
  63     // but for now do not let it proceed.
  64     assert(ResourcesModel && "Unimplemented CreateTargetScheduleState.");
  65
  66     Packet.resize(SchedModel->getIssueWidth());
  67     Packet.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   unsigned getTotalPackets() const { return TotalPackets; }
  91 };
  92
  93 /// Extend the standard ScheduleDAGMI to provide more context and override the
  94 /// top-level schedule() driver.
  95 class VLIWMachineScheduler : public ScheduleDAGMI {
  96 public:
  97   VLIWMachineScheduler(MachineSchedContext *C, MachineSchedStrategy *S):
  98     ScheduleDAGMI(C, S) {}
  99
 100   /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's
 101   /// time to do some work.
 102   virtual void schedule();
 103   /// Perform platform specific DAG postprocessing.
 104   void postprocessDAG();
 105 };
 106
 107 /// ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics
 108 /// to balance the schedule.
 109 class ConvergingVLIWScheduler : public MachineSchedStrategy {
 110
 111   /// Store the state used by ConvergingVLIWScheduler heuristics, required
 112   ///  for the lifetime of one invocation of pickNode().
 113   struct SchedCandidate {
 114     // The best SUnit candidate.
 115     SUnit *SU;
 116
 117     // Register pressure values for the best candidate.
 118     RegPressureDelta RPDelta;
 119
 120     // Best scheduling cost.
 121     int SCost;
 122
 123     SchedCandidate(): SU(NULL), SCost(0) {}
 124   };
 125   /// Represent the type of SchedCandidate found within a single queue.
 126   enum CandResult {
 127     NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure,
 128     BestCost};
 129
 130   /// Each Scheduling boundary is associated with ready queues. It tracks the
 131   /// current cycle in whichever direction at has moved, and maintains the state
 132   /// of "hazards" and other interlocks at the current cycle.
 133   struct SchedBoundary {
 134     VLIWMachineScheduler *DAG;
 135     const TargetSchedModel *SchedModel;
 136
 137     ReadyQueue Available;
 138     ReadyQueue Pending;
 139     bool CheckPending;
 140
 141     ScheduleHazardRecognizer *HazardRec;
 142     VLIWResourceModel *ResourceModel;
 143
 144     unsigned CurrCycle;
 145     unsigned IssueCount;
 146
 147     /// MinReadyCycle - Cycle of the soonest available instruction.
 148     unsigned MinReadyCycle;
 149
 150     // Remember the greatest min operand latency.
 151     unsigned MaxMinLatency;
 152
 153     /// Pending queues extend the ready queues with the same ID and the
 154     /// PendingFlag set.
 155     SchedBoundary(unsigned ID, const Twine &Name):
 156       DAG(0), SchedModel(0), Available(ID, Name+".A"),
 157       Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name+".P"),
 158       CheckPending(false), HazardRec(0), ResourceModel(0),
 159       CurrCycle(0), IssueCount(0),
 160       MinReadyCycle(UINT_MAX), MaxMinLatency(0) {}
 161
 162     ~SchedBoundary() {
 163       delete ResourceModel;
 164       delete HazardRec;
 165     }
 166
 167     void init(VLIWMachineScheduler *dag, const TargetSchedModel *smodel) {
 168       DAG = dag;
 169       SchedModel = smodel;
 170     }
 171
 172     bool isTop() const {
 173       return Available.getID() == ConvergingVLIWScheduler::TopQID;
 174     }
 175
 176     bool checkHazard(SUnit *SU);
 177
 178     void releaseNode(SUnit *SU, unsigned ReadyCycle);
 179
 180     void bumpCycle();
 181
 182     void bumpNode(SUnit *SU);
 183
 184     void releasePending();
 185
 186     void removeReady(SUnit *SU);
 187
 188     SUnit *pickOnlyChoice();
 189   };
 190
 191   VLIWMachineScheduler *DAG;
 192   const TargetSchedModel *SchedModel;
 193   const TargetRegisterInfo *TRI;
 194
 195   // State of the top and bottom scheduled instruction boundaries.
 196   SchedBoundary Top;
 197   SchedBoundary Bot;
 198
 199 public:
 200   /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
 201   enum {
 202     TopQID = 1,
 203     BotQID = 2,
 204     LogMaxQID = 2
 205   };
 206
 207   ConvergingVLIWScheduler():
 208     DAG(0), SchedModel(0), TRI(0), Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {}
 209
 210   virtual void initialize(ScheduleDAGMI *dag);
 211
 212   virtual SUnit *pickNode(bool &IsTopNode);
 213
 214   virtual void schedNode(SUnit *SU, bool IsTopNode);
 215
 216   virtual void releaseTopNode(SUnit *SU);
 217
 218   virtual void releaseBottomNode(SUnit *SU);
 219
 220   unsigned ReportPackets() {
 221     return Top.ResourceModel->getTotalPackets() +
 222            Bot.ResourceModel->getTotalPackets();
 223   }
 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