Home | History | Annotate | Download | only in CodeGen 
      1 //==- MachineScheduler.h - MachineInstr Scheduling Pass ----------*- 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 // This file provides a MachineSchedRegistry for registering alternative machine
     11 // schedulers. A Target may provide an alternative scheduler implementation by
     12 // implementing the following boilerplate:
     13 //
     14 // static ScheduleDAGInstrs *createCustomMachineSched(MachineSchedContext *C) {
     15 //  return new CustomMachineScheduler(C);
     16 // }
     17 // static MachineSchedRegistry
     18 // SchedCustomRegistry("custom", "Run my target's custom scheduler",
     19 //                     createCustomMachineSched);
     20 //
     21 // Inside <Target>PassConfig:
     22 //   enablePass(&MachineSchedulerID);
     23 //   MachineSchedRegistry::setDefault(createCustomMachineSched);
     24 //
     25 //===----------------------------------------------------------------------===//
     26 
     27 #ifndef LLVM_CODEGEN_MACHINESCHEDULER_H
     28 #define LLVM_CODEGEN_MACHINESCHEDULER_H
     29 
     30 #include "llvm/CodeGen/MachinePassRegistry.h"
     31 #include "llvm/CodeGen/RegisterPressure.h"
     32 #include "llvm/CodeGen/ScheduleDAGInstrs.h"
     33 
     34 namespace llvm {
     35 
     36 extern cl::opt<bool> ForceTopDown;
     37 extern cl::opt<bool> ForceBottomUp;
     38 
     39 class AliasAnalysis;
     40 class LiveIntervals;
     41 class MachineDominatorTree;
     42 class MachineLoopInfo;
     43 class RegisterClassInfo;
     44 class ScheduleDAGInstrs;
     45 class SchedDFSResult;
     46 
     47 /// MachineSchedContext provides enough context from the MachineScheduler pass
     48 /// for the target to instantiate a scheduler.
     49 struct MachineSchedContext {
     50   MachineFunction *MF;
     51   const MachineLoopInfo *MLI;
     52   const MachineDominatorTree *MDT;
     53   const TargetPassConfig *PassConfig;
     54   AliasAnalysis *AA;
     55   LiveIntervals *LIS;
     56 
     57   RegisterClassInfo *RegClassInfo;
     58 
     59   MachineSchedContext();
     60   virtual ~MachineSchedContext();
     61 };
     62 
     63 /// MachineSchedRegistry provides a selection of available machine instruction
     64 /// schedulers.
     65 class MachineSchedRegistry : public MachinePassRegistryNode {
     66 public:
     67   typedef ScheduleDAGInstrs *(*ScheduleDAGCtor)(MachineSchedContext *);
     68 
     69   // RegisterPassParser requires a (misnamed) FunctionPassCtor type.
     70   typedef ScheduleDAGCtor FunctionPassCtor;
     71 
     72   static MachinePassRegistry Registry;
     73 
     74   MachineSchedRegistry(const char *N, const char *D, ScheduleDAGCtor C)
     75     : MachinePassRegistryNode(N, D, (MachinePassCtor)C) {
     76     Registry.Add(this);
     77   }
     78   ~MachineSchedRegistry() { Registry.Remove(this); }
     79 
     80   // Accessors.
     81   //
     82   MachineSchedRegistry *getNext() const {
     83     return (MachineSchedRegistry *)MachinePassRegistryNode::getNext();
     84   }
     85   static MachineSchedRegistry *getList() {
     86     return (MachineSchedRegistry *)Registry.getList();
     87   }
     88   static ScheduleDAGCtor getDefault() {
     89     return (ScheduleDAGCtor)Registry.getDefault();
     90   }
     91   static void setDefault(ScheduleDAGCtor C) {
     92     Registry.setDefault((MachinePassCtor)C);
     93   }
     94   static void setDefault(StringRef Name) {
     95     Registry.setDefault(Name);
     96   }
     97   static void setListener(MachinePassRegistryListener *L) {
     98     Registry.setListener(L);
     99   }
    100 };
    101 
    102 class ScheduleDAGMI;
    103 
    104 /// MachineSchedStrategy - Interface to the scheduling algorithm used by
    105 /// ScheduleDAGMI.
    106 class MachineSchedStrategy {
    107 public:
    108   virtual ~MachineSchedStrategy() {}
    109 
    110   /// Initialize the strategy after building the DAG for a new region.
    111   virtual void initialize(ScheduleDAGMI *DAG) = 0;
    112 
    113   /// Notify this strategy that all roots have been released (including those
    114   /// that depend on EntrySU or ExitSU).
    115   virtual void registerRoots() {}
    116 
    117   /// Pick the next node to schedule, or return NULL. Set IsTopNode to true to
    118   /// schedule the node at the top of the unscheduled region. Otherwise it will
    119   /// be scheduled at the bottom.
    120   virtual SUnit *pickNode(bool &IsTopNode) = 0;
    121 
    122   /// \brief Scheduler callback to notify that a new subtree is scheduled.
    123   virtual void scheduleTree(unsigned SubtreeID) {}
    124 
    125   /// Notify MachineSchedStrategy that ScheduleDAGMI has scheduled an
    126   /// instruction and updated scheduled/remaining flags in the DAG nodes.
    127   virtual void schedNode(SUnit *SU, bool IsTopNode) = 0;
    128 
    129   /// When all predecessor dependencies have been resolved, free this node for
    130   /// top-down scheduling.
    131   virtual void releaseTopNode(SUnit *SU) = 0;
    132   /// When all successor dependencies have been resolved, free this node for
    133   /// bottom-up scheduling.
    134   virtual void releaseBottomNode(SUnit *SU) = 0;
    135 };
    136 
    137 /// ReadyQueue encapsulates vector of "ready" SUnits with basic convenience
    138 /// methods for pushing and removing nodes. ReadyQueue's are uniquely identified
    139 /// by an ID. SUnit::NodeQueueId is a mask of the ReadyQueues the SUnit is in.
    140 ///
    141 /// This is a convenience class that may be used by implementations of
    142 /// MachineSchedStrategy.
    143 class ReadyQueue {
    144   unsigned ID;
    145   std::string Name;
    146   std::vector<SUnit*> Queue;
    147 
    148 public:
    149   ReadyQueue(unsigned id, const Twine &name): ID(id), Name(name.str()) {}
    150 
    151   unsigned getID() const { return ID; }
    152 
    153   StringRef getName() const { return Name; }
    154 
    155   // SU is in this queue if it's NodeQueueID is a superset of this ID.
    156   bool isInQueue(SUnit *SU) const { return (SU->NodeQueueId & ID); }
    157 
    158   bool empty() const { return Queue.empty(); }
    159 
    160   void clear() { Queue.clear(); }
    161 
    162   unsigned size() const { return Queue.size(); }
    163 
    164   typedef std::vector<SUnit*>::iterator iterator;
    165 
    166   iterator begin() { return Queue.begin(); }
    167 
    168   iterator end() { return Queue.end(); }
    169 
    170   ArrayRef<SUnit*> elements() { return Queue; }
    171 
    172   iterator find(SUnit *SU) {
    173     return std::find(Queue.begin(), Queue.end(), SU);
    174   }
    175 
    176   void push(SUnit *SU) {
    177     Queue.push_back(SU);
    178     SU->NodeQueueId |= ID;
    179   }
    180 
    181   iterator remove(iterator I) {
    182     (*I)->NodeQueueId &= ~ID;
    183     *I = Queue.back();
    184     unsigned idx = I - Queue.begin();
    185     Queue.pop_back();
    186     return Queue.begin() + idx;
    187   }
    188 
    189 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
    190   void dump();
    191 #endif
    192 };
    193 
    194 /// Mutate the DAG as a postpass after normal DAG building.
    195 class ScheduleDAGMutation {
    196 public:
    197   virtual ~ScheduleDAGMutation() {}
    198 
    199   virtual void apply(ScheduleDAGMI *DAG) = 0;
    200 };
    201 
    202 /// ScheduleDAGMI is an implementation of ScheduleDAGInstrs that schedules
    203 /// machine instructions while updating LiveIntervals and tracking regpressure.
    204 class ScheduleDAGMI : public ScheduleDAGInstrs {
    205 protected:
    206   AliasAnalysis *AA;
    207   RegisterClassInfo *RegClassInfo;
    208   MachineSchedStrategy *SchedImpl;
    209 
    210   /// Information about DAG subtrees. If DFSResult is NULL, then SchedulerTrees
    211   /// will be empty.
    212   SchedDFSResult *DFSResult;
    213   BitVector ScheduledTrees;
    214 
    215   /// Topo - A topological ordering for SUnits which permits fast IsReachable
    216   /// and similar queries.
    217   ScheduleDAGTopologicalSort Topo;
    218 
    219   /// Ordered list of DAG postprocessing steps.
    220   std::vector<ScheduleDAGMutation*> Mutations;
    221 
    222   MachineBasicBlock::iterator LiveRegionEnd;
    223 
    224   /// Register pressure in this region computed by buildSchedGraph.
    225   IntervalPressure RegPressure;
    226   RegPressureTracker RPTracker;
    227 
    228   /// List of pressure sets that exceed the target's pressure limit before
    229   /// scheduling, listed in increasing set ID order. Each pressure set is paired
    230   /// with its max pressure in the currently scheduled regions.
    231   std::vector<PressureElement> RegionCriticalPSets;
    232 
    233   /// The top of the unscheduled zone.
    234   MachineBasicBlock::iterator CurrentTop;
    235   IntervalPressure TopPressure;
    236   RegPressureTracker TopRPTracker;
    237 
    238   /// The bottom of the unscheduled zone.
    239   MachineBasicBlock::iterator CurrentBottom;
    240   IntervalPressure BotPressure;
    241   RegPressureTracker BotRPTracker;
    242 
    243   /// Record the next node in a scheduled cluster.
    244   const SUnit *NextClusterPred;
    245   const SUnit *NextClusterSucc;
    246 
    247 #ifndef NDEBUG
    248   /// The number of instructions scheduled so far. Used to cut off the
    249   /// scheduler at the point determined by misched-cutoff.
    250   unsigned NumInstrsScheduled;
    251 #endif
    252 
    253 public:
    254   ScheduleDAGMI(MachineSchedContext *C, MachineSchedStrategy *S):
    255     ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS),
    256     AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S), DFSResult(0),
    257     Topo(SUnits, &ExitSU), RPTracker(RegPressure), CurrentTop(),
    258     TopRPTracker(TopPressure), CurrentBottom(), BotRPTracker(BotPressure),
    259     NextClusterPred(NULL), NextClusterSucc(NULL) {
    260 #ifndef NDEBUG
    261     NumInstrsScheduled = 0;
    262 #endif
    263   }
    264 
    265   virtual ~ScheduleDAGMI();
    266 
    267   /// Add a postprocessing step to the DAG builder.
    268   /// Mutations are applied in the order that they are added after normal DAG
    269   /// building and before MachineSchedStrategy initialization.
    270   ///
    271   /// ScheduleDAGMI takes ownership of the Mutation object.
    272   void addMutation(ScheduleDAGMutation *Mutation) {
    273     Mutations.push_back(Mutation);
    274   }
    275 
    276   /// \brief True if an edge can be added from PredSU to SuccSU without creating
    277   /// a cycle.
    278   bool canAddEdge(SUnit *SuccSU, SUnit *PredSU);
    279 
    280   /// \brief Add a DAG edge to the given SU with the given predecessor
    281   /// dependence data.
    282   ///
    283   /// \returns true if the edge may be added without creating a cycle OR if an
    284   /// equivalent edge already existed (false indicates failure).
    285   bool addEdge(SUnit *SuccSU, const SDep &PredDep);
    286 
    287   MachineBasicBlock::iterator top() const { return CurrentTop; }
    288   MachineBasicBlock::iterator bottom() const { return CurrentBottom; }
    289 
    290   /// Implement the ScheduleDAGInstrs interface for handling the next scheduling
    291   /// region. This covers all instructions in a block, while schedule() may only
    292   /// cover a subset.
    293   void enterRegion(MachineBasicBlock *bb,
    294                    MachineBasicBlock::iterator begin,
    295                    MachineBasicBlock::iterator end,
    296                    unsigned endcount);
    297 
    298 
    299   /// Implement ScheduleDAGInstrs interface for scheduling a sequence of
    300   /// reorderable instructions.
    301   virtual void schedule();
    302 
    303   /// Change the position of an instruction within the basic block and update
    304   /// live ranges and region boundary iterators.
    305   void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos);
    306 
    307   /// Get current register pressure for the top scheduled instructions.
    308   const IntervalPressure &getTopPressure() const { return TopPressure; }
    309   const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; }
    310 
    311   /// Get current register pressure for the bottom scheduled instructions.
    312   const IntervalPressure &getBotPressure() const { return BotPressure; }
    313   const RegPressureTracker &getBotRPTracker() const { return BotRPTracker; }
    314 
    315   /// Get register pressure for the entire scheduling region before scheduling.
    316   const IntervalPressure &getRegPressure() const { return RegPressure; }
    317 
    318   const std::vector<PressureElement> &getRegionCriticalPSets() const {
    319     return RegionCriticalPSets;
    320   }
    321 
    322   const SUnit *getNextClusterPred() const { return NextClusterPred; }
    323 
    324   const SUnit *getNextClusterSucc() const { return NextClusterSucc; }
    325 
    326   /// Compute a DFSResult after DAG building is complete, and before any
    327   /// queue comparisons.
    328   void computeDFSResult();
    329 
    330   /// Return a non-null DFS result if the scheduling strategy initialized it.
    331   const SchedDFSResult *getDFSResult() const { return DFSResult; }
    332 
    333   BitVector &getScheduledTrees() { return ScheduledTrees; }
    334 
    335   void viewGraph(const Twine &Name, const Twine &Title) LLVM_OVERRIDE;
    336   void viewGraph() LLVM_OVERRIDE;
    337 
    338 protected:
    339   // Top-Level entry points for the schedule() driver...
    340 
    341   /// Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking
    342   /// enabled. This sets up three trackers. RPTracker will cover the entire DAG
    343   /// region, TopTracker and BottomTracker will be initialized to the top and
    344   /// bottom of the DAG region without covereing any unscheduled instruction.
    345   void buildDAGWithRegPressure();
    346 
    347   /// Apply each ScheduleDAGMutation step in order. This allows different
    348   /// instances of ScheduleDAGMI to perform custom DAG postprocessing.
    349   void postprocessDAG();
    350 
    351   /// Release ExitSU predecessors and setup scheduler queues.
    352   void initQueues(ArrayRef<SUnit*> TopRoots, ArrayRef<SUnit*> BotRoots);
    353 
    354   /// Move an instruction and update register pressure.
    355   void scheduleMI(SUnit *SU, bool IsTopNode);
    356 
    357   /// Update scheduler DAG and queues after scheduling an instruction.
    358   void updateQueues(SUnit *SU, bool IsTopNode);
    359 
    360   /// Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues.
    361   void placeDebugValues();
    362 
    363   /// \brief dump the scheduled Sequence.
    364   void dumpSchedule() const;
    365 
    366   // Lesser helpers...
    367 
    368   void initRegPressure();
    369 
    370   void updateScheduledPressure(const std::vector<unsigned> &NewMaxPressure);
    371 
    372   bool checkSchedLimit();
    373 
    374   void findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots,
    375                              SmallVectorImpl<SUnit*> &BotRoots);
    376 
    377   void releaseSucc(SUnit *SU, SDep *SuccEdge);
    378   void releaseSuccessors(SUnit *SU);
    379   void releasePred(SUnit *SU, SDep *PredEdge);
    380   void releasePredecessors(SUnit *SU);
    381 };
    382 
    383 } // namespace llvm
    384 
    385 #endif
    386