MachineScheduler.h revision f45edcc3818757234c20d4d5975c0b992bf1f95e
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 { 167public: 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. 212class ReadyQueue { 213 unsigned ID; 214 std::string Name; 215 std::vector<SUnit*> Queue; 216 217public: 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. 264class ScheduleDAGMutation { 265public: 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. 273class ScheduleDAGMI : public ScheduleDAGInstrs { 274protected: 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 328public: 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 423protected: 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 474