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 MACHINESCHEDULER_H 28#define 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 unsigned size() const { return Queue.size(); } 158 159 typedef std::vector<SUnit*>::iterator iterator; 160 161 iterator begin() { return Queue.begin(); } 162 163 iterator end() { return Queue.end(); } 164 165 iterator find(SUnit *SU) { 166 return std::find(Queue.begin(), Queue.end(), SU); 167 } 168 169 void push(SUnit *SU) { 170 Queue.push_back(SU); 171 SU->NodeQueueId |= ID; 172 } 173 174 void remove(iterator I) { 175 (*I)->NodeQueueId &= ~ID; 176 *I = Queue.back(); 177 Queue.pop_back(); 178 } 179 180#ifndef NDEBUG 181 void dump(); 182#endif 183}; 184 185/// Mutate the DAG as a postpass after normal DAG building. 186class ScheduleDAGMutation { 187public: 188 virtual ~ScheduleDAGMutation() {} 189 190 virtual void apply(ScheduleDAGMI *DAG) = 0; 191}; 192 193/// ScheduleDAGMI is an implementation of ScheduleDAGInstrs that schedules 194/// machine instructions while updating LiveIntervals and tracking regpressure. 195class ScheduleDAGMI : public ScheduleDAGInstrs { 196protected: 197 AliasAnalysis *AA; 198 RegisterClassInfo *RegClassInfo; 199 MachineSchedStrategy *SchedImpl; 200 201 /// Ordered list of DAG postprocessing steps. 202 std::vector<ScheduleDAGMutation*> Mutations; 203 204 MachineBasicBlock::iterator LiveRegionEnd; 205 206 /// Register pressure in this region computed by buildSchedGraph. 207 IntervalPressure RegPressure; 208 RegPressureTracker RPTracker; 209 210 /// List of pressure sets that exceed the target's pressure limit before 211 /// scheduling, listed in increasing set ID order. Each pressure set is paired 212 /// with its max pressure in the currently scheduled regions. 213 std::vector<PressureElement> RegionCriticalPSets; 214 215 /// The top of the unscheduled zone. 216 MachineBasicBlock::iterator CurrentTop; 217 IntervalPressure TopPressure; 218 RegPressureTracker TopRPTracker; 219 220 /// The bottom of the unscheduled zone. 221 MachineBasicBlock::iterator CurrentBottom; 222 IntervalPressure BotPressure; 223 RegPressureTracker BotRPTracker; 224 225#ifndef NDEBUG 226 /// The number of instructions scheduled so far. Used to cut off the 227 /// scheduler at the point determined by misched-cutoff. 228 unsigned NumInstrsScheduled; 229#endif 230 231public: 232 ScheduleDAGMI(MachineSchedContext *C, MachineSchedStrategy *S): 233 ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS), 234 AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S), 235 RPTracker(RegPressure), CurrentTop(), TopRPTracker(TopPressure), 236 CurrentBottom(), BotRPTracker(BotPressure) { 237#ifndef NDEBUG 238 NumInstrsScheduled = 0; 239#endif 240 } 241 242 virtual ~ScheduleDAGMI() { 243 delete SchedImpl; 244 } 245 246 /// Add a postprocessing step to the DAG builder. 247 /// Mutations are applied in the order that they are added after normal DAG 248 /// building and before MachineSchedStrategy initialization. 249 void addMutation(ScheduleDAGMutation *Mutation) { 250 Mutations.push_back(Mutation); 251 } 252 253 MachineBasicBlock::iterator top() const { return CurrentTop; } 254 MachineBasicBlock::iterator bottom() const { return CurrentBottom; } 255 256 /// Implement the ScheduleDAGInstrs interface for handling the next scheduling 257 /// region. This covers all instructions in a block, while schedule() may only 258 /// cover a subset. 259 void enterRegion(MachineBasicBlock *bb, 260 MachineBasicBlock::iterator begin, 261 MachineBasicBlock::iterator end, 262 unsigned endcount); 263 264 265 /// Implement ScheduleDAGInstrs interface for scheduling a sequence of 266 /// reorderable instructions. 267 virtual void schedule(); 268 269 /// Get current register pressure for the top scheduled instructions. 270 const IntervalPressure &getTopPressure() const { return TopPressure; } 271 const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; } 272 273 /// Get current register pressure for the bottom scheduled instructions. 274 const IntervalPressure &getBotPressure() const { return BotPressure; } 275 const RegPressureTracker &getBotRPTracker() const { return BotRPTracker; } 276 277 /// Get register pressure for the entire scheduling region before scheduling. 278 const IntervalPressure &getRegPressure() const { return RegPressure; } 279 280 const std::vector<PressureElement> &getRegionCriticalPSets() const { 281 return RegionCriticalPSets; 282 } 283 284protected: 285 // Top-Level entry points for the schedule() driver... 286 287 /// Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking 288 /// enabled. This sets up three trackers. RPTracker will cover the entire DAG 289 /// region, TopTracker and BottomTracker will be initialized to the top and 290 /// bottom of the DAG region without covereing any unscheduled instruction. 291 void buildDAGWithRegPressure(); 292 293 /// Apply each ScheduleDAGMutation step in order. This allows different 294 /// instances of ScheduleDAGMI to perform custom DAG postprocessing. 295 void postprocessDAG(); 296 297 /// Identify DAG roots and setup scheduler queues. 298 void initQueues(); 299 300 /// Move an instruction and update register pressure. 301 void scheduleMI(SUnit *SU, bool IsTopNode); 302 303 /// Update scheduler DAG and queues after scheduling an instruction. 304 void updateQueues(SUnit *SU, bool IsTopNode); 305 306 /// Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues. 307 void placeDebugValues(); 308 309 // Lesser helpers... 310 311 void initRegPressure(); 312 313 void updateScheduledPressure(std::vector<unsigned> NewMaxPressure); 314 315 void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos); 316 bool checkSchedLimit(); 317 318 void releaseRoots(); 319 320 void releaseSucc(SUnit *SU, SDep *SuccEdge); 321 void releaseSuccessors(SUnit *SU); 322 void releasePred(SUnit *SU, SDep *PredEdge); 323 void releasePredecessors(SUnit *SU); 324}; 325 326} // namespace llvm 327 328#endif 329