MachineScheduler.cpp revision cb058d51db44d47b57fc4705fea00209174d6577
1//===- MachineScheduler.cpp - Machine Instruction Scheduler ---------------===// 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// MachineScheduler schedules machine instructions after phi elimination. It 11// preserves LiveIntervals so it can be invoked before register allocation. 12// 13//===----------------------------------------------------------------------===// 14 15#define DEBUG_TYPE "misched" 16 17#include "llvm/CodeGen/LiveIntervalAnalysis.h" 18#include "llvm/CodeGen/MachineScheduler.h" 19#include "llvm/CodeGen/Passes.h" 20#include "llvm/CodeGen/ScheduleDAGInstrs.h" 21#include "llvm/Analysis/AliasAnalysis.h" 22#include "llvm/Target/TargetInstrInfo.h" 23#include "llvm/Support/CommandLine.h" 24#include "llvm/Support/Debug.h" 25#include "llvm/Support/ErrorHandling.h" 26#include "llvm/Support/raw_ostream.h" 27#include "llvm/ADT/OwningPtr.h" 28 29#include <queue> 30 31using namespace llvm; 32 33#ifndef NDEBUG 34static cl::opt<bool> ViewMISchedDAGs("view-misched-dags", cl::Hidden, 35 cl::desc("Pop up a window to show MISched dags after they are processed")); 36#else 37static bool ViewMISchedDAGs = false; 38#endif // NDEBUG 39 40//===----------------------------------------------------------------------===// 41// Machine Instruction Scheduling Pass and Registry 42//===----------------------------------------------------------------------===// 43 44namespace { 45/// MachineScheduler runs after coalescing and before register allocation. 46class MachineScheduler : public MachineSchedContext, 47 public MachineFunctionPass { 48public: 49 MachineScheduler(); 50 51 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 52 53 virtual void releaseMemory() {} 54 55 virtual bool runOnMachineFunction(MachineFunction&); 56 57 virtual void print(raw_ostream &O, const Module* = 0) const; 58 59 static char ID; // Class identification, replacement for typeinfo 60}; 61} // namespace 62 63char MachineScheduler::ID = 0; 64 65char &llvm::MachineSchedulerID = MachineScheduler::ID; 66 67INITIALIZE_PASS_BEGIN(MachineScheduler, "misched", 68 "Machine Instruction Scheduler", false, false) 69INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 70INITIALIZE_PASS_DEPENDENCY(SlotIndexes) 71INITIALIZE_PASS_DEPENDENCY(LiveIntervals) 72INITIALIZE_PASS_END(MachineScheduler, "misched", 73 "Machine Instruction Scheduler", false, false) 74 75MachineScheduler::MachineScheduler() 76: MachineFunctionPass(ID) { 77 initializeMachineSchedulerPass(*PassRegistry::getPassRegistry()); 78} 79 80void MachineScheduler::getAnalysisUsage(AnalysisUsage &AU) const { 81 AU.setPreservesCFG(); 82 AU.addRequiredID(MachineDominatorsID); 83 AU.addRequired<MachineLoopInfo>(); 84 AU.addRequired<AliasAnalysis>(); 85 AU.addRequired<TargetPassConfig>(); 86 AU.addRequired<SlotIndexes>(); 87 AU.addPreserved<SlotIndexes>(); 88 AU.addRequired<LiveIntervals>(); 89 AU.addPreserved<LiveIntervals>(); 90 MachineFunctionPass::getAnalysisUsage(AU); 91} 92 93MachinePassRegistry MachineSchedRegistry::Registry; 94 95/// A dummy default scheduler factory indicates whether the scheduler 96/// is overridden on the command line. 97static ScheduleDAGInstrs *useDefaultMachineSched(MachineSchedContext *C) { 98 return 0; 99} 100 101/// MachineSchedOpt allows command line selection of the scheduler. 102static cl::opt<MachineSchedRegistry::ScheduleDAGCtor, false, 103 RegisterPassParser<MachineSchedRegistry> > 104MachineSchedOpt("misched", 105 cl::init(&useDefaultMachineSched), cl::Hidden, 106 cl::desc("Machine instruction scheduler to use")); 107 108static MachineSchedRegistry 109SchedDefaultRegistry("default", "Use the target's default scheduler choice.", 110 useDefaultMachineSched); 111 112/// Forward declare the common machine scheduler. This will be used as the 113/// default scheduler if the target does not set a default. 114static ScheduleDAGInstrs *createCommonMachineSched(MachineSchedContext *C); 115 116/// Top-level MachineScheduler pass driver. 117/// 118/// Visit blocks in function order. Divide each block into scheduling regions 119/// and visit them bottom-up. This is consistent with the DAG builder, which 120/// traverses scheduling regions bottom-up, but not essential. 121/// 122/// This design avoids exposing scheduling boundaries to the DAG builder, 123/// simplifying the DAG builder's support for "special" target instructions, 124/// while at the same time allowing target schedulers to operate across 125/// scheduling boundaries, for example to bundle the boudary instructions 126/// without reordering them. This creates complexity, because the target 127/// scheduler must update the RegionBegin and RegionEnd positions cached by 128/// ScheduleDAGInstrs whenever adding or removing instructions. A much simpler 129/// design would be to split blocks at scheduling boundaries, but LLVM has a 130/// general bias against block splitting purely for implementation simplicity. 131bool MachineScheduler::runOnMachineFunction(MachineFunction &mf) { 132 // Initialize the context of the pass. 133 MF = &mf; 134 MLI = &getAnalysis<MachineLoopInfo>(); 135 MDT = &getAnalysis<MachineDominatorTree>(); 136 PassConfig = &getAnalysis<TargetPassConfig>(); 137 AA = &getAnalysis<AliasAnalysis>(); 138 139 LIS = &getAnalysis<LiveIntervals>(); 140 const TargetInstrInfo *TII = MF->getTarget().getInstrInfo(); 141 142 // Select the scheduler, or set the default. 143 MachineSchedRegistry::ScheduleDAGCtor Ctor = MachineSchedOpt; 144 if (Ctor == useDefaultMachineSched) { 145 // Get the default scheduler set by the target. 146 Ctor = MachineSchedRegistry::getDefault(); 147 if (!Ctor) { 148 Ctor = createCommonMachineSched; 149 MachineSchedRegistry::setDefault(Ctor); 150 } 151 } 152 // Instantiate the selected scheduler. 153 OwningPtr<ScheduleDAGInstrs> Scheduler(Ctor(this)); 154 155 // Visit all machine basic blocks. 156 for (MachineFunction::iterator MBB = MF->begin(), MBBEnd = MF->end(); 157 MBB != MBBEnd; ++MBB) { 158 159 Scheduler->startBlock(MBB); 160 161 // Break the block into scheduling regions [I, RegionEnd), and schedule each 162 // region as soon as it is discovered. RegionEnd points the the scheduling 163 // boundary at the bottom of the region. The DAG does not include RegionEnd, 164 // but the region does (i.e. the next RegionEnd is above the previous 165 // RegionBegin). If the current block has no terminator then RegionEnd == 166 // MBB->end() for the bottom region. 167 // 168 // The Scheduler may insert instructions during either schedule() or 169 // exitRegion(), even for empty regions. So the local iterators 'I' and 170 // 'RegionEnd' are invalid across these calls. 171 unsigned RemainingCount = MBB->size(); 172 for(MachineBasicBlock::iterator RegionEnd = MBB->end(); 173 RegionEnd != MBB->begin(); RegionEnd = Scheduler->begin()) { 174 // Avoid decrementing RegionEnd for blocks with no terminator. 175 if (RegionEnd != MBB->end() 176 || TII->isSchedulingBoundary(llvm::prior(RegionEnd), MBB, *MF)) { 177 --RegionEnd; 178 // Count the boundary instruction. 179 --RemainingCount; 180 } 181 182 // The next region starts above the previous region. Look backward in the 183 // instruction stream until we find the nearest boundary. 184 MachineBasicBlock::iterator I = RegionEnd; 185 for(;I != MBB->begin(); --I, --RemainingCount) { 186 if (TII->isSchedulingBoundary(llvm::prior(I), MBB, *MF)) 187 break; 188 } 189 // Notify the scheduler of the region, even if we may skip scheduling 190 // it. Perhaps it still needs to be bundled. 191 Scheduler->enterRegion(MBB, I, RegionEnd, RemainingCount); 192 193 // Skip empty scheduling regions (0 or 1 schedulable instructions). 194 if (I == RegionEnd || I == llvm::prior(RegionEnd)) { 195 // Close the current region. Bundle the terminator if needed. 196 // This invalidates 'RegionEnd' and 'I'. 197 Scheduler->exitRegion(); 198 continue; 199 } 200 DEBUG(dbgs() << "MachineScheduling " << MF->getFunction()->getName() 201 << ":BB#" << MBB->getNumber() << "\n From: " << *I << " To: "; 202 if (RegionEnd != MBB->end()) dbgs() << *RegionEnd; 203 else dbgs() << "End"; 204 dbgs() << " Remaining: " << RemainingCount << "\n"); 205 206 // Schedule a region: possibly reorder instructions. 207 // This invalidates 'RegionEnd' and 'I'. 208 Scheduler->schedule(); 209 210 // Close the current region. 211 Scheduler->exitRegion(); 212 213 // Scheduling has invalidated the current iterator 'I'. Ask the 214 // scheduler for the top of it's scheduled region. 215 RegionEnd = Scheduler->begin(); 216 } 217 assert(RemainingCount == 0 && "Instruction count mismatch!"); 218 Scheduler->finishBlock(); 219 } 220 return true; 221} 222 223void MachineScheduler::print(raw_ostream &O, const Module* m) const { 224 // unimplemented 225} 226 227//===----------------------------------------------------------------------===// 228// ScheduleTopeDownLive - Base class for basic top-down scheduling with 229// LiveIntervals preservation. 230// ===----------------------------------------------------------------------===// 231 232namespace { 233/// ScheduleTopDownLive is an implementation of ScheduleDAGInstrs that schedules 234/// machine instructions while updating LiveIntervals. 235class ScheduleTopDownLive : public ScheduleDAGInstrs { 236 AliasAnalysis *AA; 237public: 238 ScheduleTopDownLive(MachineSchedContext *C): 239 ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS), 240 AA(C->AA) {} 241 242 /// ScheduleDAGInstrs interface. 243 void schedule(); 244 245 /// Interface implemented by the selected top-down liveinterval scheduler. 246 /// 247 /// Pick the next node to schedule, or return NULL. 248 virtual SUnit *pickNode() = 0; 249 250 /// When all preceeding dependencies have been resolved, free this node for 251 /// scheduling. 252 virtual void releaseNode(SUnit *SU) = 0; 253 254protected: 255 void releaseSucc(SUnit *SU, SDep *SuccEdge); 256 void releaseSuccessors(SUnit *SU); 257}; 258} // namespace 259 260/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. When 261/// NumPredsLeft reaches zero, release the successor node. 262void ScheduleTopDownLive::releaseSucc(SUnit *SU, SDep *SuccEdge) { 263 SUnit *SuccSU = SuccEdge->getSUnit(); 264 265#ifndef NDEBUG 266 if (SuccSU->NumPredsLeft == 0) { 267 dbgs() << "*** Scheduling failed! ***\n"; 268 SuccSU->dump(this); 269 dbgs() << " has been released too many times!\n"; 270 llvm_unreachable(0); 271 } 272#endif 273 --SuccSU->NumPredsLeft; 274 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) 275 releaseNode(SuccSU); 276} 277 278/// releaseSuccessors - Call releaseSucc on each of SU's successors. 279void ScheduleTopDownLive::releaseSuccessors(SUnit *SU) { 280 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 281 I != E; ++I) { 282 releaseSucc(SU, &*I); 283 } 284} 285 286/// schedule - This is called back from ScheduleDAGInstrs::Run() when it's 287/// time to do some work. 288void ScheduleTopDownLive::schedule() { 289 buildSchedGraph(AA); 290 291 DEBUG(dbgs() << "********** MI Scheduling **********\n"); 292 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 293 SUnits[su].dumpAll(this)); 294 295 if (ViewMISchedDAGs) viewGraph(); 296 297 // Release any successors of the special Entry node. It is currently unused, 298 // but we keep up appearances. 299 releaseSuccessors(&EntrySU); 300 301 // Release all DAG roots for scheduling. 302 for (std::vector<SUnit>::iterator I = SUnits.begin(), E = SUnits.end(); 303 I != E; ++I) { 304 // A SUnit is ready to schedule if it has no predecessors. 305 if (I->Preds.empty()) 306 releaseNode(&(*I)); 307 } 308 309 MachineBasicBlock::iterator InsertPos = RegionBegin; 310 while (SUnit *SU = pickNode()) { 311 DEBUG(dbgs() << "*** Scheduling Instruction:\n"; SU->dump(this)); 312 313 // Move the instruction to its new location in the instruction stream. 314 MachineInstr *MI = SU->getInstr(); 315 if (&*InsertPos == MI) 316 ++InsertPos; 317 else { 318 BB->splice(InsertPos, BB, MI); 319 LIS->handleMove(MI); 320 if (RegionBegin == InsertPos) 321 RegionBegin = MI; 322 } 323 324 // Release dependent instructions for scheduling. 325 releaseSuccessors(SU); 326 } 327} 328 329//===----------------------------------------------------------------------===// 330// Placeholder for the default machine instruction scheduler. 331//===----------------------------------------------------------------------===// 332 333namespace { 334class CommonMachineScheduler : public ScheduleDAGInstrs { 335 AliasAnalysis *AA; 336public: 337 CommonMachineScheduler(MachineSchedContext *C): 338 ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS), 339 AA(C->AA) {} 340 341 /// schedule - This is called back from ScheduleDAGInstrs::Run() when it's 342 /// time to do some work. 343 void schedule(); 344}; 345} // namespace 346 347/// The common machine scheduler will be used as the default scheduler if the 348/// target does not set a default. 349static ScheduleDAGInstrs *createCommonMachineSched(MachineSchedContext *C) { 350 return new CommonMachineScheduler(C); 351} 352static MachineSchedRegistry 353SchedCommonRegistry("common", "Use the target's default scheduler choice.", 354 createCommonMachineSched); 355 356/// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's 357/// time to do some work. 358void CommonMachineScheduler::schedule() { 359 buildSchedGraph(AA); 360 361 DEBUG(dbgs() << "********** MI Scheduling **********\n"); 362 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 363 SUnits[su].dumpAll(this)); 364 365 // TODO: Put interesting things here. 366 // 367 // When this is fully implemented, it will become a subclass of 368 // ScheduleTopDownLive. So this driver will disappear. 369} 370 371//===----------------------------------------------------------------------===// 372// Machine Instruction Shuffler for Correctness Testing 373//===----------------------------------------------------------------------===// 374 375#ifndef NDEBUG 376namespace { 377// Nodes with a higher number have higher priority. This way we attempt to 378// schedule the latest instructions earliest. 379// 380// TODO: Relies on the property of the BuildSchedGraph that results in SUnits 381// being ordered in sequence top-down. 382struct ShuffleSUnitOrder { 383 bool operator()(SUnit *A, SUnit *B) const { 384 return A->NodeNum < B->NodeNum; 385 } 386}; 387 388/// Reorder instructions as much as possible. 389class InstructionShuffler : public ScheduleTopDownLive { 390 std::priority_queue<SUnit*, std::vector<SUnit*>, ShuffleSUnitOrder> Queue; 391public: 392 InstructionShuffler(MachineSchedContext *C): 393 ScheduleTopDownLive(C) {} 394 395 /// ScheduleTopDownLive Interface 396 397 virtual SUnit *pickNode() { 398 if (Queue.empty()) return NULL; 399 SUnit *SU = Queue.top(); 400 Queue.pop(); 401 return SU; 402 } 403 404 virtual void releaseNode(SUnit *SU) { 405 Queue.push(SU); 406 } 407}; 408} // namespace 409 410static ScheduleDAGInstrs *createInstructionShuffler(MachineSchedContext *C) { 411 return new InstructionShuffler(C); 412} 413static MachineSchedRegistry ShufflerRegistry("shuffle", 414 "Shuffle machine instructions", 415 createInstructionShuffler); 416#endif // !NDEBUG 417