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