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 HEXAGONASMPRINTER_H
     15 #define HEXAGONASMPRINTER_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/CommandLine.h"
     28 #include "llvm/Support/Debug.h"
     29 #include "llvm/Support/ErrorHandling.h"
     30 #include "llvm/Support/raw_ostream.h"
     31 #include "llvm/Target/TargetInstrInfo.h"
     32 
     33 using namespace llvm;
     34 
     35 namespace llvm {
     36 //===----------------------------------------------------------------------===//
     37 // ConvergingVLIWScheduler - Implementation of the standard
     38 // MachineSchedStrategy.
     39 //===----------------------------------------------------------------------===//
     40 
     41 class VLIWResourceModel {
     42   /// ResourcesModel - Represents VLIW state.
     43   /// Not limited to VLIW targets per say, but assumes
     44   /// definition of DFA by a target.
     45   DFAPacketizer *ResourcesModel;
     46 
     47   const TargetSchedModel *SchedModel;
     48 
     49   /// Local packet/bundle model. Purely
     50   /// internal to the MI schedulre at the time.
     51   std::vector<SUnit*> Packet;
     52 
     53   /// Total packets created.
     54   unsigned TotalPackets;
     55 
     56 public:
     57 VLIWResourceModel(const TargetMachine &TM, const TargetSchedModel *SM) :
     58     SchedModel(SM), TotalPackets(0) {
     59     ResourcesModel = TM.getInstrInfo()->CreateTargetScheduleState(&TM, nullptr);
     60 
     61     // This hard requirement could be relaxed,
     62     // but for now do not let it proceed.
     63     assert(ResourcesModel && "Unimplemented CreateTargetScheduleState.");
     64 
     65     Packet.resize(SchedModel->getIssueWidth());
     66     Packet.clear();
     67     ResourcesModel->clearResources();
     68   }
     69 
     70   ~VLIWResourceModel() {
     71     delete ResourcesModel;
     72   }
     73 
     74   void resetPacketState() {
     75     Packet.clear();
     76   }
     77 
     78   void resetDFA() {
     79     ResourcesModel->clearResources();
     80   }
     81 
     82   void reset() {
     83     Packet.clear();
     84     ResourcesModel->clearResources();
     85   }
     86 
     87   bool isResourceAvailable(SUnit *SU);
     88   bool reserveResources(SUnit *SU);
     89   unsigned getTotalPackets() const { return TotalPackets; }
     90 };
     91 
     92 /// Extend the standard ScheduleDAGMI to provide more context and override the
     93 /// top-level schedule() driver.
     94 class VLIWMachineScheduler : public ScheduleDAGMILive {
     95 public:
     96   VLIWMachineScheduler(MachineSchedContext *C,
     97                        std::unique_ptr<MachineSchedStrategy> S)
     98       : ScheduleDAGMILive(C, std::move(S)) {}
     99 
    100   /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's
    101   /// time to do some work.
    102   virtual void schedule() override;
    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(nullptr), 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 VLIWSchedBoundary {
    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     VLIWSchedBoundary(unsigned ID, const Twine &Name):
    156       DAG(nullptr), SchedModel(nullptr), Available(ID, Name+".A"),
    157       Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name+".P"),
    158       CheckPending(false), HazardRec(nullptr), ResourceModel(nullptr),
    159       CurrCycle(0), IssueCount(0),
    160       MinReadyCycle(UINT_MAX), MaxMinLatency(0) {}
    161 
    162     ~VLIWSchedBoundary() {
    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 
    194   // State of the top and bottom scheduled instruction boundaries.
    195   VLIWSchedBoundary Top;
    196   VLIWSchedBoundary Bot;
    197 
    198 public:
    199   /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
    200   enum {
    201     TopQID = 1,
    202     BotQID = 2,
    203     LogMaxQID = 2
    204   };
    205 
    206   ConvergingVLIWScheduler()
    207     : DAG(nullptr), SchedModel(nullptr), Top(TopQID, "TopQ"),
    208       Bot(BotQID, "BotQ") {}
    209 
    210   virtual void initialize(ScheduleDAGMI *dag) override;
    211 
    212   virtual SUnit *pickNode(bool &IsTopNode) override;
    213 
    214   virtual void schedNode(SUnit *SU, bool IsTopNode) override;
    215 
    216   virtual void releaseTopNode(SUnit *SU) override;
    217 
    218   virtual void releaseBottomNode(SUnit *SU) override;
    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                       PressureChange P = PressureChange());
    238 #endif
    239 };
    240 
    241 } // namespace
    242 
    243 
    244 #endif
    245