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