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 //===----------------------------------------------------------------------===//
  37 // MachineSchedStrategy - Interface to a machine scheduling algorithm.
  38 //===----------------------------------------------------------------------===//
  39
  40 namespace llvm {
  41 class VLIWMachineScheduler;
  42
  43 /// MachineSchedStrategy - Interface used by VLIWMachineScheduler to drive the selected
  44 /// scheduling algorithm.
  45 ///
  46 /// If this works well and targets wish to reuse VLIWMachineScheduler, we may expose it
  47 /// in ScheduleDAGInstrs.h
  48 class MachineSchedStrategy {
  49 public:
  50   virtual ~MachineSchedStrategy() {}
  51
  52   /// Initialize the strategy after building the DAG for a new region.
  53   virtual void initialize(VLIWMachineScheduler *DAG) = 0;
  54
  55   /// Pick the next node to schedule, or return NULL. Set IsTopNode to true to
  56   /// schedule the node at the top of the unscheduled region. Otherwise it will
  57   /// be scheduled at the bottom.
  58   virtual SUnit *pickNode(bool &IsTopNode) = 0;
  59
  60   /// Notify MachineSchedStrategy that VLIWMachineScheduler has scheduled a node.
  61   virtual void schedNode(SUnit *SU, bool IsTopNode) = 0;
  62
  63   /// When all predecessor dependencies have been resolved, free this node for
  64   /// top-down scheduling.
  65   virtual void releaseTopNode(SUnit *SU) = 0;
  66   /// When all successor dependencies have been resolved, free this node for
  67   /// bottom-up scheduling.
  68   virtual void releaseBottomNode(SUnit *SU) = 0;
  69 };
  70
  71 //===----------------------------------------------------------------------===//
  72 // ConvergingVLIWScheduler - Implementation of the standard MachineSchedStrategy.
  73 //===----------------------------------------------------------------------===//
  74
  75 /// ReadyQueue encapsulates vector of "ready" SUnits with basic convenience
  76 /// methods for pushing and removing nodes. ReadyQueue's are uniquely identified
  77 /// by an ID. SUnit::NodeQueueId is a mask of the ReadyQueues the SUnit is in.
  78 class ReadyQueue {
  79   unsigned ID;
  80   std::string Name;
  81   std::vector<SUnit*> Queue;
  82
  83 public:
  84   ReadyQueue(unsigned id, const Twine &name): ID(id), Name(name.str()) {}
  85
  86   unsigned getID() const { return ID; }
  87
  88   StringRef getName() const { return Name; }
  89
  90   // SU is in this queue if it's NodeQueueID is a superset of this ID.
  91   bool isInQueue(SUnit *SU) const { return (SU->NodeQueueId & ID); }
  92
  93   bool empty() const { return Queue.empty(); }
  94
  95   unsigned size() const { return Queue.size(); }
  96
  97   typedef std::vector<SUnit*>::iterator iterator;
  98
  99   iterator begin() { return Queue.begin(); }
 100
 101   iterator end() { return Queue.end(); }
 102
 103   iterator find(SUnit *SU) {
 104     return std::find(Queue.begin(), Queue.end(), SU);
 105   }
 106
 107   void push(SUnit *SU) {
 108     Queue.push_back(SU);
 109     SU->NodeQueueId |= ID;
 110   }
 111
 112   void remove(iterator I) {
 113     (*I)->NodeQueueId &= ~ID;
 114     *I = Queue.back();
 115     Queue.pop_back();
 116   }
 117
 118   void dump() {
 119     dbgs() << Name << ": ";
 120     for (unsigned i = 0, e = Queue.size(); i < e; ++i)
 121       dbgs() << Queue[i]->NodeNum << " ";
 122     dbgs() << "\n";
 123   }
 124 };
 125
 126 /// ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics to balance
 127 /// the schedule.
 128 class ConvergingVLIWScheduler : public MachineSchedStrategy {
 129
 130   /// Store the state used by ConvergingVLIWScheduler heuristics, required for the
 131   /// lifetime of one invocation of pickNode().
 132   struct SchedCandidate {
 133     // The best SUnit candidate.
 134     SUnit *SU;
 135
 136     // Register pressure values for the best candidate.
 137     RegPressureDelta RPDelta;
 138
 139     // Best scheduling cost.
 140     int SCost;
 141
 142     SchedCandidate(): SU(NULL), SCost(0) {}
 143   };
 144   /// Represent the type of SchedCandidate found within a single queue.
 145   enum CandResult {
 146     NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure,
 147     BestCost};
 148
 149   /// Each Scheduling boundary is associated with ready queues. It tracks the
 150   /// current cycle in whichever direction at has moved, and maintains the state
 151   /// of "hazards" and other interlocks at the current cycle.
 152   struct SchedBoundary {
 153     VLIWMachineScheduler *DAG;
 154
 155     ReadyQueue Available;
 156     ReadyQueue Pending;
 157     bool CheckPending;
 158
 159     ScheduleHazardRecognizer *HazardRec;
 160
 161     unsigned CurrCycle;
 162     unsigned IssueCount;
 163
 164     /// MinReadyCycle - Cycle of the soonest available instruction.
 165     unsigned MinReadyCycle;
 166
 167     // Remember the greatest min operand latency.
 168     unsigned MaxMinLatency;
 169
 170     /// Pending queues extend the ready queues with the same ID and the
 171     /// PendingFlag set.
 172     SchedBoundary(unsigned ID, const Twine &Name):
 173       DAG(0), Available(ID, Name+".A"),
 174       Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name+".P"),
 175       CheckPending(false), HazardRec(0), CurrCycle(0), IssueCount(0),
 176       MinReadyCycle(UINT_MAX), MaxMinLatency(0) {}
 177
 178     ~SchedBoundary() { delete HazardRec; }
 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 TargetRegisterInfo *TRI;
 201
 202   // State of the top and bottom scheduled instruction boundaries.
 203   SchedBoundary Top;
 204   SchedBoundary 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(0), TRI(0), Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {}
 216
 217   virtual void initialize(VLIWMachineScheduler *dag);
 218
 219   virtual SUnit *pickNode(bool &IsTopNode);
 220
 221   virtual void schedNode(SUnit *SU, bool IsTopNode);
 222
 223   virtual void releaseTopNode(SUnit *SU);
 224
 225   virtual void releaseBottomNode(SUnit *SU);
 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                       PressureElement P = PressureElement());
 240 #endif
 241 };
 242
 243 class VLIWResourceModel {
 244   /// ResourcesModel - Represents VLIW state.
 245   /// Not limited to VLIW targets per say, but assumes
 246   /// definition of DFA by a target.
 247   DFAPacketizer *ResourcesModel;
 248
 249   const InstrItineraryData *InstrItins;
 250
 251   /// Local packet/bundle model. Purely
 252   /// internal to the MI schedulre at the time.
 253   std::vector<SUnit*> Packet;
 254
 255   /// Total packets created.
 256   unsigned TotalPackets;
 257
 258 public:
 259   VLIWResourceModel(MachineSchedContext *C, const InstrItineraryData *IID) :
 260     InstrItins(IID), TotalPackets(0) {
 261     const TargetMachine &TM = C->MF->getTarget();
 262     ResourcesModel = TM.getInstrInfo()->CreateTargetScheduleState(&TM,NULL);
 263
 264     // This hard requirement could be relaxed, but for now do not let it proceed.
 265     assert(ResourcesModel && "Unimplemented CreateTargetScheduleState.");
 266
 267     Packet.resize(InstrItins->SchedModel->IssueWidth);
 268     Packet.clear();
 269     ResourcesModel->clearResources();
 270   }
 271
 272   ~VLIWResourceModel() {
 273     delete ResourcesModel;
 274   }
 275
 276   void resetPacketState() {
 277     Packet.clear();
 278   }
 279
 280   void resetDFA() {
 281     ResourcesModel->clearResources();
 282   }
 283
 284   bool isResourceAvailable(SUnit *SU);
 285   void reserveResources(SUnit *SU);
 286   unsigned getTotalPackets() const { return TotalPackets; }
 287 };
 288
 289 class VLIWMachineScheduler : public ScheduleDAGInstrs {
 290   /// AA - AliasAnalysis for making memory reference queries.
 291   AliasAnalysis *AA;
 292
 293   RegisterClassInfo *RegClassInfo;
 294   MachineSchedStrategy *SchedImpl;
 295
 296   /// state separatly for top/bottom sectioins.
 297   VLIWResourceModel *TopResourceModel;
 298   VLIWResourceModel *BotResourceModel;
 299
 300   MachineBasicBlock::iterator LiveRegionEnd;
 301
 302   /// Register pressure in this region computed by buildSchedGraph.
 303   IntervalPressure RegPressure;
 304   RegPressureTracker RPTracker;
 305
 306   /// List of pressure sets that exceed the target's pressure limit before
 307   /// scheduling, listed in increasing set ID order. Each pressure set is paired
 308   /// with its max pressure in the currently scheduled regions.
 309   std::vector<PressureElement> RegionCriticalPSets;
 310
 311   /// The top of the unscheduled zone.
 312   MachineBasicBlock::iterator CurrentTop;
 313   IntervalPressure TopPressure;
 314   RegPressureTracker TopRPTracker;
 315
 316   /// The bottom of the unscheduled zone.
 317   MachineBasicBlock::iterator CurrentBottom;
 318   IntervalPressure BotPressure;
 319   RegPressureTracker BotRPTracker;
 320
 321 #ifndef NDEBUG
 322   /// The number of instructions scheduled so far. Used to cut off the
 323   /// scheduler at the point determined by misched-cutoff.
 324   unsigned NumInstrsScheduled;
 325 #endif
 326
 327   /// Total packets in the region.
 328   unsigned TotalPackets;
 329
 330   const MachineLoopInfo *MLI;
 331 public:
 332   VLIWMachineScheduler(MachineSchedContext *C, MachineSchedStrategy *S):
 333     ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS),
 334     AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S),
 335     RPTracker(RegPressure), CurrentTop(), TopRPTracker(TopPressure),
 336     CurrentBottom(), BotRPTracker(BotPressure), MLI(C->MLI) {
 337
 338     TopResourceModel = new VLIWResourceModel(C, InstrItins);
 339     BotResourceModel = new VLIWResourceModel(C, InstrItins);
 340
 341 #ifndef NDEBUG
 342     NumInstrsScheduled = 0;
 343 #endif
 344     TotalPackets = 0;
 345   }
 346
 347   virtual ~VLIWMachineScheduler() {
 348     delete SchedImpl;
 349     delete TopResourceModel;
 350     delete BotResourceModel;
 351   }
 352
 353   MachineBasicBlock::iterator top() const { return CurrentTop; }
 354   MachineBasicBlock::iterator bottom() const { return CurrentBottom; }
 355
 356   /// Implement the ScheduleDAGInstrs interface for handling the next scheduling
 357   /// region. This covers all instructions in a block, while schedule() may only
 358   /// cover a subset.
 359   void enterRegion(MachineBasicBlock *bb,
 360                    MachineBasicBlock::iterator begin,
 361                    MachineBasicBlock::iterator end,
 362                    unsigned endcount);
 363
 364   /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's
 365   /// time to do some work.
 366   void schedule();
 367
 368   unsigned CurCycle;
 369
 370   /// Get current register pressure for the top scheduled instructions.
 371   const IntervalPressure &getTopPressure() const { return TopPressure; }
 372   const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; }
 373
 374   /// Get current register pressure for the bottom scheduled instructions.
 375   const IntervalPressure &getBotPressure() const { return BotPressure; }
 376   const RegPressureTracker &getBotRPTracker() const { return BotRPTracker; }
 377
 378   /// Get register pressure for the entire scheduling region before scheduling.
 379   const IntervalPressure &getRegPressure() const { return RegPressure; }
 380
 381   const std::vector<PressureElement> &getRegionCriticalPSets() const {
 382     return RegionCriticalPSets;
 383   }
 384
 385   VLIWResourceModel *getTopResourceModel() { return TopResourceModel; }
 386   VLIWResourceModel *getBotResourceModel() { return BotResourceModel; }
 387
 388   /// getIssueWidth - Return the max instructions per scheduling group.
 389   unsigned getIssueWidth() const {
 390     return (InstrItins && InstrItins->SchedModel)
 391       ? InstrItins->SchedModel->IssueWidth : 1;
 392   }
 393
 394   /// getNumMicroOps - Return the number of issue slots required for this MI.
 395   unsigned getNumMicroOps(MachineInstr *MI) const {
 396     if (!InstrItins) return 1;
 397     int UOps = InstrItins->getNumMicroOps(MI->getDesc().getSchedClass());
 398     return (UOps >= 0) ? UOps : TII->getNumMicroOps(InstrItins, MI);
 399   }
 400
 401 private:
 402   void scheduleNodeTopDown(SUnit *SU);
 403   void listScheduleTopDown();
 404
 405   void initRegPressure();
 406   void updateScheduledPressure(std::vector<unsigned> NewMaxPressure);
 407
 408   void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos);
 409   bool checkSchedLimit();
 410
 411   void releaseRoots();
 412
 413   void releaseSucc(SUnit *SU, SDep *SuccEdge);
 414   void releaseSuccessors(SUnit *SU);
 415   void releasePred(SUnit *SU, SDep *PredEdge);
 416   void releasePredecessors(SUnit *SU);
 417
 418   void placeDebugValues();
 419 };
 420 } // namespace
 421
 422
 423 #endif