Home | History | Annotate | Download | only in Hexagon 
      1 //===- HexagonMachineScheduler.h - Custom Hexagon MI scheduler --*- C++ -*-===//
      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/STLExtras.h"
     18 #include "llvm/ADT/Twine.h"
     19 #include "llvm/CodeGen/DFAPacketizer.h"
     20 #include "llvm/CodeGen/MachineScheduler.h"
     21 #include "llvm/CodeGen/RegisterPressure.h"
     22 #include "llvm/CodeGen/ScheduleHazardRecognizer.h"
     23 #include "llvm/CodeGen/TargetInstrInfo.h"
     24 #include "llvm/CodeGen/TargetSchedule.h"
     25 #include "llvm/CodeGen/TargetSubtargetInfo.h"
     26 #include <algorithm>
     27 #include <cassert>
     28 #include <limits>
     29 #include <memory>
     30 #include <vector>
     31 
     32 namespace llvm {
     33 
     34 class SUnit;
     35 
     36 class VLIWResourceModel {
     37   /// ResourcesModel - Represents VLIW state.
     38   /// Not limited to VLIW targets per se, but assumes
     39   /// definition of DFA by a target.
     40   DFAPacketizer *ResourcesModel;
     41 
     42   const TargetSchedModel *SchedModel;
     43 
     44   /// Local packet/bundle model. Purely
     45   /// internal to the MI schedulre at the time.
     46   std::vector<SUnit *> Packet;
     47 
     48   /// Total packets created.
     49   unsigned TotalPackets = 0;
     50 
     51 public:
     52   VLIWResourceModel(const TargetSubtargetInfo &STI, const TargetSchedModel *SM)
     53       : SchedModel(SM) {
     54     ResourcesModel = STI.getInstrInfo()->CreateTargetScheduleState(STI);
     55 
     56     // This hard requirement could be relaxed,
     57     // but for now do not let it proceed.
     58     assert(ResourcesModel && "Unimplemented CreateTargetScheduleState.");
     59 
     60     Packet.resize(SchedModel->getIssueWidth());
     61     Packet.clear();
     62     ResourcesModel->clearResources();
     63   }
     64 
     65   ~VLIWResourceModel() {
     66     delete ResourcesModel;
     67   }
     68 
     69   void resetPacketState() {
     70     Packet.clear();
     71   }
     72 
     73   void resetDFA() {
     74     ResourcesModel->clearResources();
     75   }
     76 
     77   void reset() {
     78     Packet.clear();
     79     ResourcesModel->clearResources();
     80   }
     81 
     82   bool isResourceAvailable(SUnit *SU, bool IsTop);
     83   bool reserveResources(SUnit *SU, bool IsTop);
     84   unsigned getTotalPackets() const { return TotalPackets; }
     85   bool isInPacket(SUnit *SU) const { return is_contained(Packet, SU); }
     86 };
     87 
     88 /// Extend the standard ScheduleDAGMI to provide more context and override the
     89 /// top-level schedule() driver.
     90 class VLIWMachineScheduler : public ScheduleDAGMILive {
     91 public:
     92   VLIWMachineScheduler(MachineSchedContext *C,
     93                        std::unique_ptr<MachineSchedStrategy> S)
     94       : ScheduleDAGMILive(C, std::move(S)) {}
     95 
     96   /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's
     97   /// time to do some work.
     98   void schedule() override;
     99 
    100   RegisterClassInfo *getRegClassInfo() { return RegClassInfo; }
    101   int getBBSize() { return BB->size(); }
    102 };
    103 
    104 //===----------------------------------------------------------------------===//
    105 // ConvergingVLIWScheduler - Implementation of the standard
    106 // MachineSchedStrategy.
    107 //===----------------------------------------------------------------------===//
    108 
    109 /// ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics
    110 /// to balance the schedule.
    111 class ConvergingVLIWScheduler : public MachineSchedStrategy {
    112   /// Store the state used by ConvergingVLIWScheduler heuristics, required
    113   ///  for the lifetime of one invocation of pickNode().
    114   struct SchedCandidate {
    115     // The best SUnit candidate.
    116     SUnit *SU = nullptr;
    117 
    118     // Register pressure values for the best candidate.
    119     RegPressureDelta RPDelta;
    120 
    121     // Best scheduling cost.
    122     int SCost = 0;
    123 
    124     SchedCandidate() = default;
    125   };
    126   /// Represent the type of SchedCandidate found within a single queue.
    127   enum CandResult {
    128     NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure,
    129     BestCost, Weak};
    130 
    131   /// Each Scheduling boundary is associated with ready queues. It tracks the
    132   /// current cycle in whichever direction at has moved, and maintains the state
    133   /// of "hazards" and other interlocks at the current cycle.
    134   struct VLIWSchedBoundary {
    135     VLIWMachineScheduler *DAG = nullptr;
    136     const TargetSchedModel *SchedModel = nullptr;
    137 
    138     ReadyQueue Available;
    139     ReadyQueue Pending;
    140     bool CheckPending = false;
    141 
    142     ScheduleHazardRecognizer *HazardRec = nullptr;
    143     VLIWResourceModel *ResourceModel = nullptr;
    144 
    145     unsigned CurrCycle = 0;
    146     unsigned IssueCount = 0;
    147     unsigned CriticalPathLength = 0;
    148 
    149     /// MinReadyCycle - Cycle of the soonest available instruction.
    150     unsigned MinReadyCycle = std::numeric_limits<unsigned>::max();
    151 
    152     // Remember the greatest min operand latency.
    153     unsigned MaxMinLatency = 0;
    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         : Available(ID, Name+".A"),
    159           Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name+".P") {}
    160 
    161     ~VLIWSchedBoundary() {
    162       delete ResourceModel;
    163       delete HazardRec;
    164     }
    165 
    166     void init(VLIWMachineScheduler *dag, const TargetSchedModel *smodel) {
    167       DAG = dag;
    168       SchedModel = smodel;
    169       CurrCycle = 0;
    170       IssueCount = 0;
    171       // Initialize the critical path length limit, which used by the scheduling
    172       // cost model to determine the value for scheduling an instruction. We use
    173       // a slightly different heuristic for small and large functions. For small
    174       // functions, it's important to use the height/depth of the instruction.
    175       // For large functions, prioritizing by height or depth increases spills.
    176       CriticalPathLength = DAG->getBBSize() / SchedModel->getIssueWidth();
    177       if (DAG->getBBSize() < 50)
    178         // We divide by two as a cheap and simple heuristic to reduce the
    179         // critcal path length, which increases the priority of using the graph
    180         // height/depth in the scheduler's cost computation.
    181         CriticalPathLength >>= 1;
    182       else {
    183         // For large basic blocks, we prefer a larger critical path length to
    184         // decrease the priority of using the graph height/depth.
    185         unsigned MaxPath = 0;
    186         for (auto &SU : DAG->SUnits)
    187           MaxPath = std::max(MaxPath, isTop() ? SU.getHeight() : SU.getDepth());
    188         CriticalPathLength = std::max(CriticalPathLength, MaxPath) + 1;
    189       }
    190     }
    191 
    192     bool isTop() const {
    193       return Available.getID() == ConvergingVLIWScheduler::TopQID;
    194     }
    195 
    196     bool checkHazard(SUnit *SU);
    197 
    198     void releaseNode(SUnit *SU, unsigned ReadyCycle);
    199 
    200     void bumpCycle();
    201 
    202     void bumpNode(SUnit *SU);
    203 
    204     void releasePending();
    205 
    206     void removeReady(SUnit *SU);
    207 
    208     SUnit *pickOnlyChoice();
    209 
    210     bool isLatencyBound(SUnit *SU) {
    211       if (CurrCycle >= CriticalPathLength)
    212         return true;
    213       unsigned PathLength = isTop() ? SU->getHeight() : SU->getDepth();
    214       return CriticalPathLength - CurrCycle <= PathLength;
    215     }
    216   };
    217 
    218   VLIWMachineScheduler *DAG = nullptr;
    219   const TargetSchedModel *SchedModel = nullptr;
    220 
    221   // State of the top and bottom scheduled instruction boundaries.
    222   VLIWSchedBoundary Top;
    223   VLIWSchedBoundary Bot;
    224 
    225   /// List of pressure sets that have a high pressure level in the region.
    226   std::vector<bool> HighPressureSets;
    227 
    228 public:
    229   /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
    230   enum {
    231     TopQID = 1,
    232     BotQID = 2,
    233     LogMaxQID = 2
    234   };
    235 
    236   ConvergingVLIWScheduler() : Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {}
    237 
    238   void initialize(ScheduleDAGMI *dag) override;
    239 
    240   SUnit *pickNode(bool &IsTopNode) override;
    241 
    242   void schedNode(SUnit *SU, bool IsTopNode) override;
    243 
    244   void releaseTopNode(SUnit *SU) override;
    245 
    246   void releaseBottomNode(SUnit *SU) override;
    247 
    248   unsigned reportPackets() {
    249     return Top.ResourceModel->getTotalPackets() +
    250            Bot.ResourceModel->getTotalPackets();
    251   }
    252 
    253 protected:
    254   SUnit *pickNodeBidrectional(bool &IsTopNode);
    255 
    256   int pressureChange(const SUnit *SU, bool isBotUp);
    257 
    258   int SchedulingCost(ReadyQueue &Q,
    259                      SUnit *SU, SchedCandidate &Candidate,
    260                      RegPressureDelta &Delta, bool verbose);
    261 
    262   CandResult pickNodeFromQueue(VLIWSchedBoundary &Zone,
    263                                const RegPressureTracker &RPTracker,
    264                                SchedCandidate &Candidate);
    265 #ifndef NDEBUG
    266   void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU,
    267                       int Cost, PressureChange P = PressureChange());
    268 
    269   void readyQueueVerboseDump(const RegPressureTracker &RPTracker,
    270                              SchedCandidate &Candidate, ReadyQueue &Q);
    271 #endif
    272 };
    273 
    274 } // end namespace llvm
    275 
    276 #endif // LLVM_LIB_TARGET_HEXAGON_HEXAGONMACHINESCHEDULER_H
    277