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