MachineScheduler.h revision d2763f6ce62eaa497e944331668414e35f3712f3
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 /// Register pressure in this region computed by buildSchedGraph. 225 IntervalPressure RegPressure; 226 RegPressureTracker RPTracker; 227 228 /// List of pressure sets that exceed the target's pressure limit before 229 /// scheduling, listed in increasing set ID order. Each pressure set is paired 230 /// with its max pressure in the currently scheduled regions. 231 std::vector<PressureElement> RegionCriticalPSets; 232 233 /// The top of the unscheduled zone. 234 MachineBasicBlock::iterator CurrentTop; 235 IntervalPressure TopPressure; 236 RegPressureTracker TopRPTracker; 237 238 /// The bottom of the unscheduled zone. 239 MachineBasicBlock::iterator CurrentBottom; 240 IntervalPressure BotPressure; 241 RegPressureTracker BotRPTracker; 242 243 /// Record the next node in a scheduled cluster. 244 const SUnit *NextClusterPred; 245 const SUnit *NextClusterSucc; 246 247#ifndef NDEBUG 248 /// The number of instructions scheduled so far. Used to cut off the 249 /// scheduler at the point determined by misched-cutoff. 250 unsigned NumInstrsScheduled; 251#endif 252 253public: 254 ScheduleDAGMI(MachineSchedContext *C, MachineSchedStrategy *S): 255 ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS), 256 AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S), DFSResult(0), 257 Topo(SUnits, &ExitSU), RPTracker(RegPressure), CurrentTop(), 258 TopRPTracker(TopPressure), CurrentBottom(), BotRPTracker(BotPressure), 259 NextClusterPred(NULL), NextClusterSucc(NULL) { 260#ifndef NDEBUG 261 NumInstrsScheduled = 0; 262#endif 263 } 264 265 virtual ~ScheduleDAGMI(); 266 267 /// Add a postprocessing step to the DAG builder. 268 /// Mutations are applied in the order that they are added after normal DAG 269 /// building and before MachineSchedStrategy initialization. 270 /// 271 /// ScheduleDAGMI takes ownership of the Mutation object. 272 void addMutation(ScheduleDAGMutation *Mutation) { 273 Mutations.push_back(Mutation); 274 } 275 276 /// \brief True if an edge can be added from PredSU to SuccSU without creating 277 /// a cycle. 278 bool canAddEdge(SUnit *SuccSU, SUnit *PredSU); 279 280 /// \brief Add a DAG edge to the given SU with the given predecessor 281 /// dependence data. 282 /// 283 /// \returns true if the edge may be added without creating a cycle OR if an 284 /// equivalent edge already existed (false indicates failure). 285 bool addEdge(SUnit *SuccSU, const SDep &PredDep); 286 287 MachineBasicBlock::iterator top() const { return CurrentTop; } 288 MachineBasicBlock::iterator bottom() const { return CurrentBottom; } 289 290 /// Implement the ScheduleDAGInstrs interface for handling the next scheduling 291 /// region. This covers all instructions in a block, while schedule() may only 292 /// cover a subset. 293 void enterRegion(MachineBasicBlock *bb, 294 MachineBasicBlock::iterator begin, 295 MachineBasicBlock::iterator end, 296 unsigned regioninstrs) LLVM_OVERRIDE; 297 298 /// Implement ScheduleDAGInstrs interface for scheduling a sequence of 299 /// reorderable instructions. 300 virtual void schedule(); 301 302 /// Change the position of an instruction within the basic block and update 303 /// live ranges and region boundary iterators. 304 void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos); 305 306 /// Get current register pressure for the top scheduled instructions. 307 const IntervalPressure &getTopPressure() const { return TopPressure; } 308 const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; } 309 310 /// Get current register pressure for the bottom scheduled instructions. 311 const IntervalPressure &getBotPressure() const { return BotPressure; } 312 const RegPressureTracker &getBotRPTracker() const { return BotRPTracker; } 313 314 /// Get register pressure for the entire scheduling region before scheduling. 315 const IntervalPressure &getRegPressure() const { return RegPressure; } 316 317 const std::vector<PressureElement> &getRegionCriticalPSets() const { 318 return RegionCriticalPSets; 319 } 320 321 const SUnit *getNextClusterPred() const { return NextClusterPred; } 322 323 const SUnit *getNextClusterSucc() const { return NextClusterSucc; } 324 325 /// Compute a DFSResult after DAG building is complete, and before any 326 /// queue comparisons. 327 void computeDFSResult(); 328 329 /// Return a non-null DFS result if the scheduling strategy initialized it. 330 const SchedDFSResult *getDFSResult() const { return DFSResult; } 331 332 BitVector &getScheduledTrees() { return ScheduledTrees; } 333 334 void viewGraph(const Twine &Name, const Twine &Title) LLVM_OVERRIDE; 335 void viewGraph() LLVM_OVERRIDE; 336 337protected: 338 // Top-Level entry points for the schedule() driver... 339 340 /// Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking 341 /// enabled. This sets up three trackers. RPTracker will cover the entire DAG 342 /// region, TopTracker and BottomTracker will be initialized to the top and 343 /// bottom of the DAG region without covereing any unscheduled instruction. 344 void buildDAGWithRegPressure(); 345 346 /// Apply each ScheduleDAGMutation step in order. This allows different 347 /// instances of ScheduleDAGMI to perform custom DAG postprocessing. 348 void postprocessDAG(); 349 350 /// Release ExitSU predecessors and setup scheduler queues. 351 void initQueues(ArrayRef<SUnit*> TopRoots, ArrayRef<SUnit*> BotRoots); 352 353 /// Move an instruction and update register pressure. 354 void scheduleMI(SUnit *SU, bool IsTopNode); 355 356 /// Update scheduler DAG and queues after scheduling an instruction. 357 void updateQueues(SUnit *SU, bool IsTopNode); 358 359 /// Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues. 360 void placeDebugValues(); 361 362 /// \brief dump the scheduled Sequence. 363 void dumpSchedule() const; 364 365 // Lesser helpers... 366 367 void initRegPressure(); 368 369 void updateScheduledPressure(const std::vector<unsigned> &NewMaxPressure); 370 371 bool checkSchedLimit(); 372 373 void findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots, 374 SmallVectorImpl<SUnit*> &BotRoots); 375 376 void releaseSucc(SUnit *SU, SDep *SuccEdge); 377 void releaseSuccessors(SUnit *SU); 378 void releasePred(SUnit *SU, SDep *PredEdge); 379 void releasePredecessors(SUnit *SU); 380}; 381 382} // namespace llvm 383 384#endif 385