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 84namespace llvm { 85 86extern cl::opt<bool> ForceTopDown; 87extern cl::opt<bool> ForceBottomUp; 88 89class AliasAnalysis; 90class LiveIntervals; 91class MachineDominatorTree; 92class MachineLoopInfo; 93class RegisterClassInfo; 94class ScheduleDAGInstrs; 95class SchedDFSResult; 96 97/// MachineSchedContext provides enough context from the MachineScheduler pass 98/// for the target to instantiate a scheduler. 99struct 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. 115class MachineSchedRegistry : public MachinePassRegistryNode { 116public: 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 143class 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. 148struct 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 166class MachineSchedStrategy { 167 virtual void anchor(); 168public: 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. 213class ReadyQueue { 214 unsigned ID; 215 std::string Name; 216 std::vector<SUnit*> Queue; 217 218public: 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. 265class ScheduleDAGMutation { 266 virtual void anchor(); 267public: 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. 275class ScheduleDAGMI : public ScheduleDAGInstrs { 276protected: 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 330public: 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 425protected: 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 476