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 public:
 168   virtual ~MachineSchedStrategy() {}
 169
 170   /// Optionally override the per-region scheduling policy.
 171   virtual void initPolicy(MachineBasicBlock::iterator Begin,
 172                           MachineBasicBlock::iterator End,
 173                           unsigned NumRegionInstrs) {}
 174
 175   /// Check if pressure tracking is needed before building the DAG and
 176   /// initializing this strategy. Called after initPolicy.
 177   virtual bool shouldTrackPressure() const { return true; }
 178
 179   /// Initialize the strategy after building the DAG for a new region.
 180   virtual void initialize(ScheduleDAGMI *DAG) = 0;
 181
 182   /// Notify this strategy that all roots have been released (including those
 183   /// that depend on EntrySU or ExitSU).
 184   virtual void registerRoots() {}
 185
 186   /// Pick the next node to schedule, or return NULL. Set IsTopNode to true to
 187   /// schedule the node at the top of the unscheduled region. Otherwise it will
 188   /// be scheduled at the bottom.
 189   virtual SUnit *pickNode(bool &IsTopNode) = 0;
 190
 191   /// \brief Scheduler callback to notify that a new subtree is scheduled.
 192   virtual void scheduleTree(unsigned SubtreeID) {}
 193
 194   /// Notify MachineSchedStrategy that ScheduleDAGMI has scheduled an
 195   /// instruction and updated scheduled/remaining flags in the DAG nodes.
 196   virtual void schedNode(SUnit *SU, bool IsTopNode) = 0;
 197
 198   /// When all predecessor dependencies have been resolved, free this node for
 199   /// top-down scheduling.
 200   virtual void releaseTopNode(SUnit *SU) = 0;
 201   /// When all successor dependencies have been resolved, free this node for
 202   /// bottom-up scheduling.
 203   virtual void releaseBottomNode(SUnit *SU) = 0;
 204 };
 205
 206 /// ReadyQueue encapsulates vector of "ready" SUnits with basic convenience
 207 /// methods for pushing and removing nodes. ReadyQueue's are uniquely identified
 208 /// by an ID. SUnit::NodeQueueId is a mask of the ReadyQueues the SUnit is in.
 209 ///
 210 /// This is a convenience class that may be used by implementations of
 211 /// MachineSchedStrategy.
 212 class ReadyQueue {
 213   unsigned ID;
 214   std::string Name;
 215   std::vector<SUnit*> Queue;
 216
 217 public:
 218   ReadyQueue(unsigned id, const Twine &name): ID(id), Name(name.str()) {}
 219
 220   unsigned getID() const { return ID; }
 221
 222   StringRef getName() const { return Name; }
 223
 224   // SU is in this queue if it's NodeQueueID is a superset of this ID.
 225   bool isInQueue(SUnit *SU) const { return (SU->NodeQueueId & ID); }
 226
 227   bool empty() const { return Queue.empty(); }
 228
 229   void clear() { Queue.clear(); }
 230
 231   unsigned size() const { return Queue.size(); }
 232
 233   typedef std::vector<SUnit*>::iterator iterator;
 234
 235   iterator begin() { return Queue.begin(); }
 236
 237   iterator end() { return Queue.end(); }
 238
 239   ArrayRef<SUnit*> elements() { return Queue; }
 240
 241   iterator find(SUnit *SU) {
 242     return std::find(Queue.begin(), Queue.end(), SU);
 243   }
 244
 245   void push(SUnit *SU) {
 246     Queue.push_back(SU);
 247     SU->NodeQueueId |= ID;
 248   }
 249
 250   iterator remove(iterator I) {
 251     (*I)->NodeQueueId &= ~ID;
 252     *I = Queue.back();
 253     unsigned idx = I - Queue.begin();
 254     Queue.pop_back();
 255     return Queue.begin() + idx;
 256   }
 257
 258 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 259   void dump();
 260 #endif
 261 };
 262
 263 /// Mutate the DAG as a postpass after normal DAG building.
 264 class ScheduleDAGMutation {
 265 public:
 266   virtual ~ScheduleDAGMutation() {}
 267
 268   virtual void apply(ScheduleDAGMI *DAG) = 0;
 269 };
 270
 271 /// ScheduleDAGMI is an implementation of ScheduleDAGInstrs that schedules
 272 /// machine instructions while updating LiveIntervals and tracking regpressure.
 273 class ScheduleDAGMI : public ScheduleDAGInstrs {
 274 protected:
 275   AliasAnalysis *AA;
 276   RegisterClassInfo *RegClassInfo;
 277   MachineSchedStrategy *SchedImpl;
 278
 279   /// Information about DAG subtrees. If DFSResult is NULL, then SchedulerTrees
 280   /// will be empty.
 281   SchedDFSResult *DFSResult;
 282   BitVector ScheduledTrees;
 283
 284   /// Topo - A topological ordering for SUnits which permits fast IsReachable
 285   /// and similar queries.
 286   ScheduleDAGTopologicalSort Topo;
 287
 288   /// Ordered list of DAG postprocessing steps.
 289   std::vector<ScheduleDAGMutation*> Mutations;
 290
 291   MachineBasicBlock::iterator LiveRegionEnd;
 292
 293   // Map each SU to its summary of pressure changes. This array is updated for
 294   // liveness during bottom-up scheduling. Top-down scheduling may proceed but
 295   // has no affect on the pressure diffs.
 296   PressureDiffs SUPressureDiffs;
 297
 298   /// Register pressure in this region computed by initRegPressure.
 299   bool ShouldTrackPressure;
 300   IntervalPressure RegPressure;
 301   RegPressureTracker RPTracker;
 302
 303   /// List of pressure sets that exceed the target's pressure limit before
 304   /// scheduling, listed in increasing set ID order. Each pressure set is paired
 305   /// with its max pressure in the currently scheduled regions.
 306   std::vector<PressureChange> RegionCriticalPSets;
 307
 308   /// The top of the unscheduled zone.
 309   MachineBasicBlock::iterator CurrentTop;
 310   IntervalPressure TopPressure;
 311   RegPressureTracker TopRPTracker;
 312
 313   /// The bottom of the unscheduled zone.
 314   MachineBasicBlock::iterator CurrentBottom;
 315   IntervalPressure BotPressure;
 316   RegPressureTracker BotRPTracker;
 317
 318   /// Record the next node in a scheduled cluster.
 319   const SUnit *NextClusterPred;
 320   const SUnit *NextClusterSucc;
 321
 322 #ifndef NDEBUG
 323   /// The number of instructions scheduled so far. Used to cut off the
 324   /// scheduler at the point determined by misched-cutoff.
 325   unsigned NumInstrsScheduled;
 326 #endif
 327
 328 public:
 329   ScheduleDAGMI(MachineSchedContext *C, MachineSchedStrategy *S):
 330     ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS),
 331     AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S), DFSResult(0),
 332     Topo(SUnits, &ExitSU), ShouldTrackPressure(false),
 333     RPTracker(RegPressure), CurrentTop(), TopRPTracker(TopPressure),
 334     CurrentBottom(), BotRPTracker(BotPressure),
 335     NextClusterPred(NULL), NextClusterSucc(NULL) {
 336 #ifndef NDEBUG
 337     NumInstrsScheduled = 0;
 338 #endif
 339   }
 340
 341   virtual ~ScheduleDAGMI();
 342
 343   /// \brief Return true if register pressure tracking is enabled.
 344   bool isTrackingPressure() const { return ShouldTrackPressure; }
 345
 346   /// Add a postprocessing step to the DAG builder.
 347   /// Mutations are applied in the order that they are added after normal DAG
 348   /// building and before MachineSchedStrategy initialization.
 349   ///
 350   /// ScheduleDAGMI takes ownership of the Mutation object.
 351   void addMutation(ScheduleDAGMutation *Mutation) {
 352     Mutations.push_back(Mutation);
 353   }
 354
 355   /// \brief True if an edge can be added from PredSU to SuccSU without creating
 356   /// a cycle.
 357   bool canAddEdge(SUnit *SuccSU, SUnit *PredSU);
 358
 359   /// \brief Add a DAG edge to the given SU with the given predecessor
 360   /// dependence data.
 361   ///
 362   /// \returns true if the edge may be added without creating a cycle OR if an
 363   /// equivalent edge already existed (false indicates failure).
 364   bool addEdge(SUnit *SuccSU, const SDep &PredDep);
 365
 366   MachineBasicBlock::iterator top() const { return CurrentTop; }
 367   MachineBasicBlock::iterator bottom() const { return CurrentBottom; }
 368
 369   /// Implement the ScheduleDAGInstrs interface for handling the next scheduling
 370   /// region. This covers all instructions in a block, while schedule() may only
 371   /// cover a subset.
 372   void enterRegion(MachineBasicBlock *bb,
 373                    MachineBasicBlock::iterator begin,
 374                    MachineBasicBlock::iterator end,
 375                    unsigned regioninstrs) LLVM_OVERRIDE;
 376
 377   /// Implement ScheduleDAGInstrs interface for scheduling a sequence of
 378   /// reorderable instructions.
 379   virtual void schedule();
 380
 381   /// Change the position of an instruction within the basic block and update
 382   /// live ranges and region boundary iterators.
 383   void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos);
 384
 385   /// Get current register pressure for the top scheduled instructions.
 386   const IntervalPressure &getTopPressure() const { return TopPressure; }
 387   const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; }
 388
 389   /// Get current register pressure for the bottom scheduled instructions.
 390   const IntervalPressure &getBotPressure() const { return BotPressure; }
 391   const RegPressureTracker &getBotRPTracker() const { return BotRPTracker; }
 392
 393   /// Get register pressure for the entire scheduling region before scheduling.
 394   const IntervalPressure &getRegPressure() const { return RegPressure; }
 395
 396   const std::vector<PressureChange> &getRegionCriticalPSets() const {
 397     return RegionCriticalPSets;
 398   }
 399
 400   PressureDiff &getPressureDiff(const SUnit *SU) {
 401     return SUPressureDiffs[SU->NodeNum];
 402   }
 403
 404   const SUnit *getNextClusterPred() const { return NextClusterPred; }
 405
 406   const SUnit *getNextClusterSucc() const { return NextClusterSucc; }
 407
 408   /// Compute a DFSResult after DAG building is complete, and before any
 409   /// queue comparisons.
 410   void computeDFSResult();
 411
 412   /// Return a non-null DFS result if the scheduling strategy initialized it.
 413   const SchedDFSResult *getDFSResult() const { return DFSResult; }
 414
 415   BitVector &getScheduledTrees() { return ScheduledTrees; }
 416
 417   /// Compute the cyclic critical path through the DAG.
 418   unsigned computeCyclicCriticalPath();
 419
 420   void viewGraph(const Twine &Name, const Twine &Title) LLVM_OVERRIDE;
 421   void viewGraph() LLVM_OVERRIDE;
 422
 423 protected:
 424   // Top-Level entry points for the schedule() driver...
 425
 426   /// Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking
 427   /// enabled. This sets up three trackers. RPTracker will cover the entire DAG
 428   /// region, TopTracker and BottomTracker will be initialized to the top and
 429   /// bottom of the DAG region without covereing any unscheduled instruction.
 430   void buildDAGWithRegPressure();
 431
 432   /// Apply each ScheduleDAGMutation step in order. This allows different
 433   /// instances of ScheduleDAGMI to perform custom DAG postprocessing.
 434   void postprocessDAG();
 435
 436   /// Release ExitSU predecessors and setup scheduler queues.
 437   void initQueues(ArrayRef<SUnit*> TopRoots, ArrayRef<SUnit*> BotRoots);
 438
 439   /// Move an instruction and update register pressure.
 440   void scheduleMI(SUnit *SU, bool IsTopNode);
 441
 442   /// Update scheduler DAG and queues after scheduling an instruction.
 443   void updateQueues(SUnit *SU, bool IsTopNode);
 444
 445   /// Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues.
 446   void placeDebugValues();
 447
 448   /// \brief dump the scheduled Sequence.
 449   void dumpSchedule() const;
 450
 451   // Lesser helpers...
 452
 453   void initRegPressure();
 454
 455   void updatePressureDiffs(ArrayRef<unsigned> LiveUses);
 456
 457   void updateScheduledPressure(const SUnit *SU,
 458                                const std::vector<unsigned> &NewMaxPressure);
 459
 460   bool checkSchedLimit();
 461
 462   void findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots,
 463                              SmallVectorImpl<SUnit*> &BotRoots);
 464
 465   void releaseSucc(SUnit *SU, SDep *SuccEdge);
 466   void releaseSuccessors(SUnit *SU);
 467   void releasePred(SUnit *SU, SDep *PredEdge);
 468   void releasePredecessors(SUnit *SU);
 469 };
 470
 471 } // namespace llvm
 472
 473 #endif