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