MachineScheduler.h revision 674be02d525d4e24bc6943ed9274958c580bcfbc
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; 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 /// Notify MachineSchedStrategy that ScheduleDAGMI has scheduled an 123 /// instruction and updated scheduled/remaining flags in the DAG nodes. 124 virtual void schedNode(SUnit *SU, bool IsTopNode) = 0; 125 126 /// When all predecessor dependencies have been resolved, free this node for 127 /// top-down scheduling. 128 virtual void releaseTopNode(SUnit *SU) = 0; 129 /// When all successor dependencies have been resolved, free this node for 130 /// bottom-up scheduling. 131 virtual void releaseBottomNode(SUnit *SU) = 0; 132}; 133 134/// ReadyQueue encapsulates vector of "ready" SUnits with basic convenience 135/// methods for pushing and removing nodes. ReadyQueue's are uniquely identified 136/// by an ID. SUnit::NodeQueueId is a mask of the ReadyQueues the SUnit is in. 137/// 138/// This is a convenience class that may be used by implementations of 139/// MachineSchedStrategy. 140class ReadyQueue { 141 unsigned ID; 142 std::string Name; 143 std::vector<SUnit*> Queue; 144 145public: 146 ReadyQueue(unsigned id, const Twine &name): ID(id), Name(name.str()) {} 147 148 unsigned getID() const { return ID; } 149 150 StringRef getName() const { return Name; } 151 152 // SU is in this queue if it's NodeQueueID is a superset of this ID. 153 bool isInQueue(SUnit *SU) const { return (SU->NodeQueueId & ID); } 154 155 bool empty() const { return Queue.empty(); } 156 157 void clear() { Queue.clear(); } 158 159 unsigned size() const { return Queue.size(); } 160 161 typedef std::vector<SUnit*>::iterator iterator; 162 163 iterator begin() { return Queue.begin(); } 164 165 iterator end() { return Queue.end(); } 166 167 iterator find(SUnit *SU) { 168 return std::find(Queue.begin(), Queue.end(), SU); 169 } 170 171 void push(SUnit *SU) { 172 Queue.push_back(SU); 173 SU->NodeQueueId |= ID; 174 } 175 176 iterator remove(iterator I) { 177 (*I)->NodeQueueId &= ~ID; 178 *I = Queue.back(); 179 unsigned idx = I - Queue.begin(); 180 Queue.pop_back(); 181 return Queue.begin() + idx; 182 } 183 184#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 185 void dump(); 186#endif 187}; 188 189/// Mutate the DAG as a postpass after normal DAG building. 190class ScheduleDAGMutation { 191public: 192 virtual ~ScheduleDAGMutation() {} 193 194 virtual void apply(ScheduleDAGMI *DAG) = 0; 195}; 196 197/// ScheduleDAGMI is an implementation of ScheduleDAGInstrs that schedules 198/// machine instructions while updating LiveIntervals and tracking regpressure. 199class ScheduleDAGMI : public ScheduleDAGInstrs { 200protected: 201 AliasAnalysis *AA; 202 RegisterClassInfo *RegClassInfo; 203 MachineSchedStrategy *SchedImpl; 204 205 /// Topo - A topological ordering for SUnits which permits fast IsReachable 206 /// and similar queries. 207 ScheduleDAGTopologicalSort Topo; 208 209 /// Ordered list of DAG postprocessing steps. 210 std::vector<ScheduleDAGMutation*> Mutations; 211 212 MachineBasicBlock::iterator LiveRegionEnd; 213 214 /// Register pressure in this region computed by buildSchedGraph. 215 IntervalPressure RegPressure; 216 RegPressureTracker RPTracker; 217 218 /// List of pressure sets that exceed the target's pressure limit before 219 /// scheduling, listed in increasing set ID order. Each pressure set is paired 220 /// with its max pressure in the currently scheduled regions. 221 std::vector<PressureElement> RegionCriticalPSets; 222 223 /// The top of the unscheduled zone. 224 MachineBasicBlock::iterator CurrentTop; 225 IntervalPressure TopPressure; 226 RegPressureTracker TopRPTracker; 227 228 /// The bottom of the unscheduled zone. 229 MachineBasicBlock::iterator CurrentBottom; 230 IntervalPressure BotPressure; 231 RegPressureTracker BotRPTracker; 232 233 /// Record the next node in a scheduled cluster. 234 const SUnit *NextClusterPred; 235 const SUnit *NextClusterSucc; 236 237#ifndef NDEBUG 238 /// The number of instructions scheduled so far. Used to cut off the 239 /// scheduler at the point determined by misched-cutoff. 240 unsigned NumInstrsScheduled; 241#endif 242 243public: 244 ScheduleDAGMI(MachineSchedContext *C, MachineSchedStrategy *S): 245 ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS), 246 AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S), 247 Topo(SUnits, &ExitSU), RPTracker(RegPressure), CurrentTop(), 248 TopRPTracker(TopPressure), CurrentBottom(), BotRPTracker(BotPressure), 249 NextClusterPred(NULL), NextClusterSucc(NULL) { 250#ifndef NDEBUG 251 NumInstrsScheduled = 0; 252#endif 253 } 254 255 virtual ~ScheduleDAGMI() { 256 DeleteContainerPointers(Mutations); 257 delete SchedImpl; 258 } 259 260 /// Add a postprocessing step to the DAG builder. 261 /// Mutations are applied in the order that they are added after normal DAG 262 /// building and before MachineSchedStrategy initialization. 263 /// 264 /// ScheduleDAGMI takes ownership of the Mutation object. 265 void addMutation(ScheduleDAGMutation *Mutation) { 266 Mutations.push_back(Mutation); 267 } 268 269 /// \brief Add a DAG edge to the given SU with the given predecessor 270 /// dependence data. 271 /// 272 /// \returns true if the edge may be added without creating a cycle OR if an 273 /// equivalent edge already existed (false indicates failure). 274 bool addEdge(SUnit *SuccSU, const SDep &PredDep); 275 276 MachineBasicBlock::iterator top() const { return CurrentTop; } 277 MachineBasicBlock::iterator bottom() const { return CurrentBottom; } 278 279 /// Implement the ScheduleDAGInstrs interface for handling the next scheduling 280 /// region. This covers all instructions in a block, while schedule() may only 281 /// cover a subset. 282 void enterRegion(MachineBasicBlock *bb, 283 MachineBasicBlock::iterator begin, 284 MachineBasicBlock::iterator end, 285 unsigned endcount); 286 287 288 /// Implement ScheduleDAGInstrs interface for scheduling a sequence of 289 /// reorderable instructions. 290 virtual void schedule(); 291 292 /// Get current register pressure for the top scheduled instructions. 293 const IntervalPressure &getTopPressure() const { return TopPressure; } 294 const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; } 295 296 /// Get current register pressure for the bottom scheduled instructions. 297 const IntervalPressure &getBotPressure() const { return BotPressure; } 298 const RegPressureTracker &getBotRPTracker() const { return BotRPTracker; } 299 300 /// Get register pressure for the entire scheduling region before scheduling. 301 const IntervalPressure &getRegPressure() const { return RegPressure; } 302 303 const std::vector<PressureElement> &getRegionCriticalPSets() const { 304 return RegionCriticalPSets; 305 } 306 307 const SUnit *getNextClusterPred() const { return NextClusterPred; } 308 309 const SUnit *getNextClusterSucc() const { return NextClusterSucc; } 310 311protected: 312 // Top-Level entry points for the schedule() driver... 313 314 /// Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking 315 /// enabled. This sets up three trackers. RPTracker will cover the entire DAG 316 /// region, TopTracker and BottomTracker will be initialized to the top and 317 /// bottom of the DAG region without covereing any unscheduled instruction. 318 void buildDAGWithRegPressure(); 319 320 /// Apply each ScheduleDAGMutation step in order. This allows different 321 /// instances of ScheduleDAGMI to perform custom DAG postprocessing. 322 void postprocessDAG(); 323 324 /// Identify DAG roots and setup scheduler queues. 325 void initQueues(); 326 327 /// Move an instruction and update register pressure. 328 void scheduleMI(SUnit *SU, bool IsTopNode); 329 330 /// Update scheduler DAG and queues after scheduling an instruction. 331 void updateQueues(SUnit *SU, bool IsTopNode); 332 333 /// Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues. 334 void placeDebugValues(); 335 336 /// \brief dump the scheduled Sequence. 337 void dumpSchedule() const; 338 339 // Lesser helpers... 340 341 void initRegPressure(); 342 343 void updateScheduledPressure(std::vector<unsigned> NewMaxPressure); 344 345 void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos); 346 bool checkSchedLimit(); 347 348 void releaseRoots(); 349 350 void releaseSucc(SUnit *SU, SDep *SuccEdge); 351 void releaseSuccessors(SUnit *SU); 352 void releasePred(SUnit *SU, SDep *PredEdge); 353 void releasePredecessors(SUnit *SU); 354}; 355 356} // namespace llvm 357 358#endif 359