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