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/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
    245