include/llvm/CodeGen/MachineScheduler.h

   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 an interface for customizing the standard MachineScheduler
  11 // pass. Note that the entire pass may be replaced as follows:
  12 //
  13 // <Target>TargetMachine::createPassConfig(PassManagerBase &PM) {
  14 //   PM.substitutePass(&MachineSchedulerID, &CustomSchedulerPassID);
  15 //   ...}
  16 //
  17 // The MachineScheduler pass is only responsible for choosing the regions to be
  18 // scheduled. Targets can override the DAG builder and scheduler without
  19 // replacing the pass as follows:
  20 //
  21 // ScheduleDAGInstrs *<Target>PassConfig::
  22 // createMachineScheduler(MachineSchedContext *C) {
  23 //   return new CustomMachineScheduler(C);
  24 // }
  25 //
  26 // The default scheduler, ScheduleDAGMI, builds the DAG and drives list
  27 // scheduling while updating the instruction stream, register pressure, and live
  28 // intervals. Most targets don't need to override the DAG builder and list
  29 // schedulier, but subtargets that require custom scheduling heuristics may
  30 // plugin an alternate MachineSchedStrategy. The strategy is responsible for
  31 // selecting the highest priority node from the list:
  32 //
  33 // ScheduleDAGInstrs *<Target>PassConfig::
  34 // createMachineScheduler(MachineSchedContext *C) {
  35 //   return new ScheduleDAGMI(C, CustomStrategy(C));
  36 // }
  37 //
  38 // The DAG builder can also be customized in a sense by adding DAG mutations
  39 // that will run after DAG building and before list scheduling. DAG mutations
  40 // can adjust dependencies based on target-specific knowledge or add weak edges
  41 // to aid heuristics:
  42 //
  43 // ScheduleDAGInstrs *<Target>PassConfig::
  44 // createMachineScheduler(MachineSchedContext *C) {
  45 //   ScheduleDAGMI *DAG = new ScheduleDAGMI(C, CustomStrategy(C));
  46 //   DAG->addMutation(new CustomDependencies(DAG->TII, DAG->TRI));
  47 //   return DAG;
  48 // }
  49 //
  50 // A target that supports alternative schedulers can use the
  51 // MachineSchedRegistry to allow command line selection. This can be done by
  52 // implementing the following boilerplate:
  53 //
  54 // static ScheduleDAGInstrs *createCustomMachineSched(MachineSchedContext *C) {
  55 //  return new CustomMachineScheduler(C);
  56 // }
  57 // static MachineSchedRegistry
  58 // SchedCustomRegistry("custom", "Run my target's custom scheduler",
  59 //                     createCustomMachineSched);
  60 //
  61 //
  62 // Finally, subtargets that don't need to implement custom heuristics but would
  63 // like to configure the GenericScheduler's policy for a given scheduler region,
  64 // including scheduling direction and register pressure tracking policy, can do
  65 // this:
  66 //
  67 // void <SubTarget>Subtarget::
  68 // overrideSchedPolicy(MachineSchedPolicy &Policy,
  69 //                     MachineInstr *begin,
  70 //                     MachineInstr *end,
  71 //                     unsigned NumRegionInstrs) const {
  72 //   Policy.<Flag> = true;
  73 // }
  74 //
  75 //===----------------------------------------------------------------------===//
  76
  77 #ifndef LLVM_CODEGEN_MACHINESCHEDULER_H
  78 #define LLVM_CODEGEN_MACHINESCHEDULER_H
  79
  80 #include "llvm/CodeGen/MachinePassRegistry.h"
  81 #include "llvm/CodeGen/RegisterPressure.h"
  82 #include "llvm/CodeGen/ScheduleDAGInstrs.h"
  83
  84 namespace llvm {
  85
  86 extern cl::opt<bool> ForceTopDown;
  87 extern cl::opt<bool> ForceBottomUp;
  88
  89 class AliasAnalysis;
  90 class LiveIntervals;
  91 class MachineDominatorTree;
  92 class MachineLoopInfo;
  93 class RegisterClassInfo;
  94 class ScheduleDAGInstrs;
  95 class SchedDFSResult;
  96
  97 /// MachineSchedContext provides enough context from the MachineScheduler pass
  98 /// for the target to instantiate a scheduler.
  99 struct MachineSchedContext {
 100   MachineFunction *MF;
 101   const MachineLoopInfo *MLI;
 102   const MachineDominatorTree *MDT;
 103   const TargetPassConfig *PassConfig;
 104   AliasAnalysis *AA;
 105   LiveIntervals *LIS;
 106
 107   RegisterClassInfo *RegClassInfo;
 108
 109   MachineSchedContext();
 110   virtual ~MachineSchedContext();
 111 };
 112
 113 /// MachineSchedRegistry provides a selection of available machine instruction
 114 /// schedulers.
 115 class MachineSchedRegistry : public MachinePassRegistryNode {
 116 public:
 117   typedef ScheduleDAGInstrs *(*ScheduleDAGCtor)(MachineSchedContext *);
 118
 119   // RegisterPassParser requires a (misnamed) FunctionPassCtor type.
 120   typedef ScheduleDAGCtor FunctionPassCtor;
 121
 122   static MachinePassRegistry Registry;
 123
 124   MachineSchedRegistry(const char *N, const char *D, ScheduleDAGCtor C)
 125     : MachinePassRegistryNode(N, D, (MachinePassCtor)C) {
 126     Registry.Add(this);
 127   }
 128   ~MachineSchedRegistry() { Registry.Remove(this); }
 129
 130   // Accessors.
 131   //
 132   MachineSchedRegistry *getNext() const {
 133     return (MachineSchedRegistry *)MachinePassRegistryNode::getNext();
 134   }
 135   static MachineSchedRegistry *getList() {
 136     return (MachineSchedRegistry *)Registry.getList();
 137   }
 138   static void setListener(MachinePassRegistryListener *L) {
 139     Registry.setListener(L);
 140   }
 141 };
 142
 143 class ScheduleDAGMI;
 144
 145 /// Define a generic scheduling policy for targets that don't provide their own
 146 /// MachineSchedStrategy. This can be overriden for each scheduling region
 147 /// before building the DAG.
 148 struct MachineSchedPolicy {
 149   // Allow the scheduler to disable register pressure tracking.
 150   bool ShouldTrackPressure;
 151
 152   // Allow the scheduler to force top-down or bottom-up scheduling. If neither
 153   // is true, the scheduler runs in both directions and converges.
 154   bool OnlyTopDown;
 155   bool OnlyBottomUp;
 156
 157   MachineSchedPolicy():
 158     ShouldTrackPressure(false), OnlyTopDown(false), OnlyBottomUp(false) {}
 159 };
 160
 161 /// MachineSchedStrategy - Interface to the scheduling algorithm used by
 162 /// ScheduleDAGMI.
 163 ///
 164 /// Initialization sequence:
 165 ///   initPolicy -> shouldTrackPressure -> initialize(DAG) -> registerRoots
 166 class MachineSchedStrategy {
 167   virtual void anchor();
 168 public:
 169   virtual ~MachineSchedStrategy() {}
 170
 171   /// Optionally override the per-region scheduling policy.
 172   virtual void initPolicy(MachineBasicBlock::iterator Begin,
 173                           MachineBasicBlock::iterator End,
 174                           unsigned NumRegionInstrs) {}
 175
 176   /// Check if pressure tracking is needed before building the DAG and
 177   /// initializing this strategy. Called after initPolicy.
 178   virtual bool shouldTrackPressure() const { return true; }
 179
 180   /// Initialize the strategy after building the DAG for a new region.
 181   virtual void initialize(ScheduleDAGMI *DAG) = 0;
 182
 183   /// Notify this strategy that all roots have been released (including those
 184   /// that depend on EntrySU or ExitSU).
 185   virtual void registerRoots() {}
 186
 187   /// Pick the next node to schedule, or return NULL. Set IsTopNode to true to
 188   /// schedule the node at the top of the unscheduled region. Otherwise it will
 189   /// be scheduled at the bottom.
 190   virtual SUnit *pickNode(bool &IsTopNode) = 0;
 191
 192   /// \brief Scheduler callback to notify that a new subtree is scheduled.
 193   virtual void scheduleTree(unsigned SubtreeID) {}
 194
 195   /// Notify MachineSchedStrategy that ScheduleDAGMI has scheduled an
 196   /// instruction and updated scheduled/remaining flags in the DAG nodes.
 197   virtual void schedNode(SUnit *SU, bool IsTopNode) = 0;
 198
 199   /// When all predecessor dependencies have been resolved, free this node for
 200   /// top-down scheduling.
 201   virtual void releaseTopNode(SUnit *SU) = 0;
 202   /// When all successor dependencies have been resolved, free this node for
 203   /// bottom-up scheduling.
 204   virtual void releaseBottomNode(SUnit *SU) = 0;
 205 };
 206
 207 /// ReadyQueue encapsulates vector of "ready" SUnits with basic convenience
 208 /// methods for pushing and removing nodes. ReadyQueue's are uniquely identified
 209 /// by an ID. SUnit::NodeQueueId is a mask of the ReadyQueues the SUnit is in.
 210 ///
 211 /// This is a convenience class that may be used by implementations of
 212 /// MachineSchedStrategy.
 213 class ReadyQueue {
 214   unsigned ID;
 215   std::string Name;
 216   std::vector<SUnit*> Queue;
 217
 218 public:
 219   ReadyQueue(unsigned id, const Twine &name): ID(id), Name(name.str()) {}
 220
 221   unsigned getID() const { return ID; }
 222
 223   StringRef getName() const { return Name; }
 224
 225   // SU is in this queue if it's NodeQueueID is a superset of this ID.
 226   bool isInQueue(SUnit *SU) const { return (SU->NodeQueueId & ID); }
 227
 228   bool empty() const { return Queue.empty(); }
 229
 230   void clear() { Queue.clear(); }
 231
 232   unsigned size() const { return Queue.size(); }
 233
 234   typedef std::vector<SUnit*>::iterator iterator;
 235
 236   iterator begin() { return Queue.begin(); }
 237
 238   iterator end() { return Queue.end(); }
 239
 240   ArrayRef<SUnit*> elements() { return Queue; }
 241
 242   iterator find(SUnit *SU) {
 243     return std::find(Queue.begin(), Queue.end(), SU);
 244   }
 245
 246   void push(SUnit *SU) {
 247     Queue.push_back(SU);
 248     SU->NodeQueueId |= ID;
 249   }
 250
 251   iterator remove(iterator I) {
 252     (*I)->NodeQueueId &= ~ID;
 253     *I = Queue.back();
 254     unsigned idx = I - Queue.begin();
 255     Queue.pop_back();
 256     return Queue.begin() + idx;
 257   }
 258
 259 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 260   void dump();
 261 #endif
 262 };
 263
 264 /// Mutate the DAG as a postpass after normal DAG building.
 265 class ScheduleDAGMutation {
 266   virtual void anchor();
 267 public:
 268   virtual ~ScheduleDAGMutation() {}
 269
 270   virtual void apply(ScheduleDAGMI *DAG) = 0;
 271 };
 272
 273 /// ScheduleDAGMI is an implementation of ScheduleDAGInstrs that schedules
 274 /// machine instructions while updating LiveIntervals and tracking regpressure.
 275 class ScheduleDAGMI : public ScheduleDAGInstrs {
 276 protected:
 277   AliasAnalysis *AA;
 278   RegisterClassInfo *RegClassInfo;
 279   MachineSchedStrategy *SchedImpl;
 280
 281   /// Information about DAG subtrees. If DFSResult is NULL, then SchedulerTrees
 282   /// will be empty.
 283   SchedDFSResult *DFSResult;
 284   BitVector ScheduledTrees;
 285
 286   /// Topo - A topological ordering for SUnits which permits fast IsReachable
 287   /// and similar queries.
 288   ScheduleDAGTopologicalSort Topo;
 289
 290   /// Ordered list of DAG postprocessing steps.
 291   std::vector<ScheduleDAGMutation*> Mutations;
 292
 293   MachineBasicBlock::iterator LiveRegionEnd;
 294
 295   // Map each SU to its summary of pressure changes. This array is updated for
 296   // liveness during bottom-up scheduling. Top-down scheduling may proceed but
 297   // has no affect on the pressure diffs.
 298   PressureDiffs SUPressureDiffs;
 299
 300   /// Register pressure in this region computed by initRegPressure.
 301   bool ShouldTrackPressure;
 302   IntervalPressure RegPressure;
 303   RegPressureTracker RPTracker;
 304
 305   /// List of pressure sets that exceed the target's pressure limit before
 306   /// scheduling, listed in increasing set ID order. Each pressure set is paired
 307   /// with its max pressure in the currently scheduled regions.
 308   std::vector<PressureChange> RegionCriticalPSets;
 309
 310   /// The top of the unscheduled zone.
 311   MachineBasicBlock::iterator CurrentTop;
 312   IntervalPressure TopPressure;
 313   RegPressureTracker TopRPTracker;
 314
 315   /// The bottom of the unscheduled zone.
 316   MachineBasicBlock::iterator CurrentBottom;
 317   IntervalPressure BotPressure;
 318   RegPressureTracker BotRPTracker;
 319
 320   /// Record the next node in a scheduled cluster.
 321   const SUnit *NextClusterPred;
 322   const SUnit *NextClusterSucc;
 323
 324 #ifndef NDEBUG
 325   /// The number of instructions scheduled so far. Used to cut off the
 326   /// scheduler at the point determined by misched-cutoff.
 327   unsigned NumInstrsScheduled;
 328 #endif
 329
 330 public:
 331   ScheduleDAGMI(MachineSchedContext *C, MachineSchedStrategy *S):
 332     ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS),
 333     AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S), DFSResult(0),
 334     Topo(SUnits, &ExitSU), ShouldTrackPressure(false),
 335     RPTracker(RegPressure), CurrentTop(), TopRPTracker(TopPressure),
 336     CurrentBottom(), BotRPTracker(BotPressure),
 337     NextClusterPred(NULL), NextClusterSucc(NULL) {
 338 #ifndef NDEBUG
 339     NumInstrsScheduled = 0;
 340 #endif
 341   }
 342
 343   virtual ~ScheduleDAGMI();
 344
 345   /// \brief Return true if register pressure tracking is enabled.
 346   bool isTrackingPressure() const { return ShouldTrackPressure; }
 347
 348   /// Add a postprocessing step to the DAG builder.
 349   /// Mutations are applied in the order that they are added after normal DAG
 350   /// building and before MachineSchedStrategy initialization.
 351   ///
 352   /// ScheduleDAGMI takes ownership of the Mutation object.
 353   void addMutation(ScheduleDAGMutation *Mutation) {
 354     Mutations.push_back(Mutation);
 355   }
 356
 357   /// \brief True if an edge can be added from PredSU to SuccSU without creating
 358   /// a cycle.
 359   bool canAddEdge(SUnit *SuccSU, SUnit *PredSU);
 360
 361   /// \brief Add a DAG edge to the given SU with the given predecessor
 362   /// dependence data.
 363   ///
 364   /// \returns true if the edge may be added without creating a cycle OR if an
 365   /// equivalent edge already existed (false indicates failure).
 366   bool addEdge(SUnit *SuccSU, const SDep &PredDep);
 367
 368   MachineBasicBlock::iterator top() const { return CurrentTop; }
 369   MachineBasicBlock::iterator bottom() const { return CurrentBottom; }
 370
 371   /// Implement the ScheduleDAGInstrs interface for handling the next scheduling
 372   /// region. This covers all instructions in a block, while schedule() may only
 373   /// cover a subset.
 374   void enterRegion(MachineBasicBlock *bb,
 375                    MachineBasicBlock::iterator begin,
 376                    MachineBasicBlock::iterator end,
 377                    unsigned regioninstrs) LLVM_OVERRIDE;
 378
 379   /// Implement ScheduleDAGInstrs interface for scheduling a sequence of
 380   /// reorderable instructions.
 381   virtual void schedule();
 382
 383   /// Change the position of an instruction within the basic block and update
 384   /// live ranges and region boundary iterators.
 385   void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos);
 386
 387   /// Get current register pressure for the top scheduled instructions.
 388   const IntervalPressure &getTopPressure() const { return TopPressure; }
 389   const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; }
 390
 391   /// Get current register pressure for the bottom scheduled instructions.
 392   const IntervalPressure &getBotPressure() const { return BotPressure; }
 393   const RegPressureTracker &getBotRPTracker() const { return BotRPTracker; }
 394
 395   /// Get register pressure for the entire scheduling region before scheduling.
 396   const IntervalPressure &getRegPressure() const { return RegPressure; }
 397
 398   const std::vector<PressureChange> &getRegionCriticalPSets() const {
 399     return RegionCriticalPSets;
 400   }
 401
 402   PressureDiff &getPressureDiff(const SUnit *SU) {
 403     return SUPressureDiffs[SU->NodeNum];
 404   }
 405
 406   const SUnit *getNextClusterPred() const { return NextClusterPred; }
 407
 408   const SUnit *getNextClusterSucc() const { return NextClusterSucc; }
 409
 410   /// Compute a DFSResult after DAG building is complete, and before any
 411   /// queue comparisons.
 412   void computeDFSResult();
 413
 414   /// Return a non-null DFS result if the scheduling strategy initialized it.
 415   const SchedDFSResult *getDFSResult() const { return DFSResult; }
 416
 417   BitVector &getScheduledTrees() { return ScheduledTrees; }
 418
 419   /// Compute the cyclic critical path through the DAG.
 420   unsigned computeCyclicCriticalPath();
 421
 422   void viewGraph(const Twine &Name, const Twine &Title) LLVM_OVERRIDE;
 423   void viewGraph() LLVM_OVERRIDE;
 424
 425 protected:
 426   // Top-Level entry points for the schedule() driver...
 427
 428   /// Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking
 429   /// enabled. This sets up three trackers. RPTracker will cover the entire DAG
 430   /// region, TopTracker and BottomTracker will be initialized to the top and
 431   /// bottom of the DAG region without covereing any unscheduled instruction.
 432   void buildDAGWithRegPressure();
 433
 434   /// Apply each ScheduleDAGMutation step in order. This allows different
 435   /// instances of ScheduleDAGMI to perform custom DAG postprocessing.
 436   void postprocessDAG();
 437
 438   /// Release ExitSU predecessors and setup scheduler queues.
 439   void initQueues(ArrayRef<SUnit*> TopRoots, ArrayRef<SUnit*> BotRoots);
 440
 441   /// Move an instruction and update register pressure.
 442   void scheduleMI(SUnit *SU, bool IsTopNode);
 443
 444   /// Update scheduler DAG and queues after scheduling an instruction.
 445   void updateQueues(SUnit *SU, bool IsTopNode);
 446
 447   /// Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues.
 448   void placeDebugValues();
 449
 450   /// \brief dump the scheduled Sequence.
 451   void dumpSchedule() const;
 452
 453   // Lesser helpers...
 454
 455   void initRegPressure();
 456
 457   void updatePressureDiffs(ArrayRef<unsigned> LiveUses);
 458
 459   void updateScheduledPressure(const SUnit *SU,
 460                                const std::vector<unsigned> &NewMaxPressure);
 461
 462   bool checkSchedLimit();
 463
 464   void findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots,
 465                              SmallVectorImpl<SUnit*> &BotRoots);
 466
 467   void releaseSucc(SUnit *SU, SDep *SuccEdge);
 468   void releaseSuccessors(SUnit *SU);
 469   void releasePred(SUnit *SU, SDep *PredEdge);
 470   void releasePredecessors(SUnit *SU);
 471 };
 472
 473 } // namespace llvm
 474
 475 #endif