MachineScheduler.cpp revision fe4d6df5c706c2ada666d95c25b8f460e30b1336
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 116bool MachineScheduler::runOnMachineFunction(MachineFunction &mf) { 117 // Initialize the context of the pass. 118 MF = &mf; 119 MLI = &getAnalysis<MachineLoopInfo>(); 120 MDT = &getAnalysis<MachineDominatorTree>(); 121 PassConfig = &getAnalysis<TargetPassConfig>(); 122 AA = &getAnalysis<AliasAnalysis>(); 123 124 LIS = &getAnalysis<LiveIntervals>(); 125 const TargetInstrInfo *TII = MF->getTarget().getInstrInfo(); 126 127 // Select the scheduler, or set the default. 128 MachineSchedRegistry::ScheduleDAGCtor Ctor = MachineSchedOpt; 129 if (Ctor == useDefaultMachineSched) { 130 // Get the default scheduler set by the target. 131 Ctor = MachineSchedRegistry::getDefault(); 132 if (!Ctor) { 133 Ctor = createCommonMachineSched; 134 MachineSchedRegistry::setDefault(Ctor); 135 } 136 } 137 // Instantiate the selected scheduler. 138 OwningPtr<ScheduleDAGInstrs> Scheduler(Ctor(this)); 139 140 // Visit all machine basic blocks. 141 for (MachineFunction::iterator MBB = MF->begin(), MBBEnd = MF->end(); 142 MBB != MBBEnd; ++MBB) { 143 144 Scheduler->startBlock(MBB); 145 146 // Break the block into scheduling regions [I, RegionEnd), and schedule each 147 // region as soon as it is discovered. RegionEnd points the the scheduling 148 // boundary at the bottom of the region. The DAG does not include RegionEnd, 149 // but the region does (i.e. the next RegionEnd is above the previous 150 // RegionBegin). If the current block has no terminator then RegionEnd == 151 // MBB->end() for the bottom region. 152 // 153 // The Scheduler may insert instructions during either schedule() or 154 // exitRegion(), even for empty regions. So the local iterators 'I' and 155 // 'RegionEnd' are invalid across these calls. 156 unsigned RemainingCount = MBB->size(); 157 for(MachineBasicBlock::iterator RegionEnd = MBB->end(); 158 RegionEnd != MBB->begin(); RegionEnd = Scheduler->begin()) { 159 // Avoid decrementing RegionEnd for blocks with no terminator. 160 if (RegionEnd != MBB->end() 161 || TII->isSchedulingBoundary(llvm::prior(RegionEnd), MBB, *MF)) { 162 --RegionEnd; 163 // Count the boundary instruction. 164 --RemainingCount; 165 } 166 167 // The next region starts above the previous region. Look backward in the 168 // instruction stream until we find the nearest boundary. 169 MachineBasicBlock::iterator I = RegionEnd; 170 for(;I != MBB->begin(); --I, --RemainingCount) { 171 if (TII->isSchedulingBoundary(llvm::prior(I), MBB, *MF)) 172 break; 173 } 174 // Notify the scheduler of the region, even if we may skip scheduling 175 // it. Perhaps it still needs to be bundled. 176 Scheduler->enterRegion(MBB, I, RegionEnd, RemainingCount); 177 178 // Skip empty scheduling regions (0 or 1 schedulable instructions). 179 if (I == RegionEnd || I == llvm::prior(RegionEnd)) { 180 // Close the current region. Bundle the terminator if needed. 181 // This invalidates 'RegionEnd' and 'I'. 182 Scheduler->exitRegion(); 183 continue; 184 } 185 DEBUG(dbgs() << "MachineScheduling " << MF->getFunction()->getName() 186 << ":BB#" << MBB->getNumber() << "\n From: " << *I << " To: "; 187 if (RegionEnd != MBB->end()) dbgs() << *RegionEnd; 188 else dbgs() << "End"; 189 dbgs() << " Remaining: " << RemainingCount << "\n"); 190 191 // Schedule a region: possibly reorder instructions. 192 // This invalidates 'RegionEnd' and 'I'. 193 Scheduler->schedule(); 194 195 // Close the current region. 196 Scheduler->exitRegion(); 197 198 // Scheduling has invalidated the current iterator 'I'. Ask the 199 // scheduler for the top of it's scheduled region. 200 RegionEnd = Scheduler->begin(); 201 } 202 assert(RemainingCount == 0 && "Instruction count mismatch!"); 203 Scheduler->finishBlock(); 204 } 205 return true; 206} 207 208void MachineScheduler::print(raw_ostream &O, const Module* m) const { 209 // unimplemented 210} 211 212//===----------------------------------------------------------------------===// 213// ScheduleTopeDownLive - Base class for basic top-down scheduling with 214// LiveIntervals preservation. 215// ===----------------------------------------------------------------------===// 216 217namespace { 218/// ScheduleTopDownLive is an implementation of ScheduleDAGInstrs that schedules 219/// machine instructions while updating LiveIntervals. 220class ScheduleTopDownLive : public ScheduleDAGInstrs { 221 AliasAnalysis *AA; 222public: 223 ScheduleTopDownLive(MachineSchedContext *C): 224 ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS), 225 AA(C->AA) {} 226 227 /// ScheduleDAGInstrs interface. 228 void schedule(); 229 230 /// Interface implemented by the selected top-down liveinterval scheduler. 231 /// 232 /// Pick the next node to schedule, or return NULL. 233 virtual SUnit *pickNode() = 0; 234 235 /// When all preceeding dependencies have been resolved, free this node for 236 /// scheduling. 237 virtual void releaseNode(SUnit *SU) = 0; 238 239protected: 240 void releaseSucc(SUnit *SU, SDep *SuccEdge); 241 void releaseSuccessors(SUnit *SU); 242}; 243} // namespace 244 245/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. When 246/// NumPredsLeft reaches zero, release the successor node. 247void ScheduleTopDownLive::releaseSucc(SUnit *SU, SDep *SuccEdge) { 248 SUnit *SuccSU = SuccEdge->getSUnit(); 249 250#ifndef NDEBUG 251 if (SuccSU->NumPredsLeft == 0) { 252 dbgs() << "*** Scheduling failed! ***\n"; 253 SuccSU->dump(this); 254 dbgs() << " has been released too many times!\n"; 255 llvm_unreachable(0); 256 } 257#endif 258 --SuccSU->NumPredsLeft; 259 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) 260 releaseNode(SuccSU); 261} 262 263/// releaseSuccessors - Call releaseSucc on each of SU's successors. 264void ScheduleTopDownLive::releaseSuccessors(SUnit *SU) { 265 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 266 I != E; ++I) { 267 releaseSucc(SU, &*I); 268 } 269} 270 271/// schedule - This is called back from ScheduleDAGInstrs::Run() when it's 272/// time to do some work. 273void ScheduleTopDownLive::schedule() { 274 buildSchedGraph(AA); 275 276 DEBUG(dbgs() << "********** MI Scheduling **********\n"); 277 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 278 SUnits[su].dumpAll(this)); 279 280 if (ViewMISchedDAGs) viewGraph(); 281 282 // Release any successors of the special Entry node. It is currently unused, 283 // but we keep up appearances. 284 releaseSuccessors(&EntrySU); 285 286 // Release all DAG roots for scheduling. 287 for (std::vector<SUnit>::iterator I = SUnits.begin(), E = SUnits.end(); 288 I != E; ++I) { 289 // A SUnit is ready to schedule if it has no predecessors. 290 if (I->Preds.empty()) 291 releaseNode(&(*I)); 292 } 293 294 MachineBasicBlock::iterator InsertPos = RegionBegin; 295 while (SUnit *SU = pickNode()) { 296 DEBUG(dbgs() << "*** Scheduling Instruction:\n"; SU->dump(this)); 297 298 // Move the instruction to its new location in the instruction stream. 299 MachineInstr *MI = SU->getInstr(); 300 if (&*InsertPos == MI) 301 ++InsertPos; 302 else { 303 BB->splice(InsertPos, BB, MI); 304 LIS->handleMove(MI); 305 if (RegionBegin == InsertPos) 306 RegionBegin = MI; 307 } 308 309 // Release dependent instructions for scheduling. 310 releaseSuccessors(SU); 311 } 312} 313 314//===----------------------------------------------------------------------===// 315// Placeholder for the default machine instruction scheduler. 316//===----------------------------------------------------------------------===// 317 318namespace { 319class CommonMachineScheduler : public ScheduleDAGInstrs { 320 AliasAnalysis *AA; 321public: 322 CommonMachineScheduler(MachineSchedContext *C): 323 ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS), 324 AA(C->AA) {} 325 326 /// schedule - This is called back from ScheduleDAGInstrs::Run() when it's 327 /// time to do some work. 328 void schedule(); 329}; 330} // namespace 331 332/// The common machine scheduler will be used as the default scheduler if the 333/// target does not set a default. 334static ScheduleDAGInstrs *createCommonMachineSched(MachineSchedContext *C) { 335 return new CommonMachineScheduler(C); 336} 337static MachineSchedRegistry 338SchedCommonRegistry("common", "Use the target's default scheduler choice.", 339 createCommonMachineSched); 340 341/// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's 342/// time to do some work. 343void CommonMachineScheduler::schedule() { 344 buildSchedGraph(AA); 345 346 DEBUG(dbgs() << "********** MI Scheduling **********\n"); 347 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 348 SUnits[su].dumpAll(this)); 349 350 // TODO: Put interesting things here. 351 // 352 // When this is fully implemented, it will become a subclass of 353 // ScheduleTopDownLive. So this driver will disappear. 354} 355 356//===----------------------------------------------------------------------===// 357// Machine Instruction Shuffler for Correctness Testing 358//===----------------------------------------------------------------------===// 359 360#ifndef NDEBUG 361namespace { 362// Nodes with a higher number have higher priority. This way we attempt to 363// schedule the latest instructions earliest. 364// 365// TODO: Relies on the property of the BuildSchedGraph that results in SUnits 366// being ordered in sequence top-down. 367struct ShuffleSUnitOrder { 368 bool operator()(SUnit *A, SUnit *B) const { 369 return A->NodeNum < B->NodeNum; 370 } 371}; 372 373/// Reorder instructions as much as possible. 374class InstructionShuffler : public ScheduleTopDownLive { 375 std::priority_queue<SUnit*, std::vector<SUnit*>, ShuffleSUnitOrder> Queue; 376public: 377 InstructionShuffler(MachineSchedContext *C): 378 ScheduleTopDownLive(C) {} 379 380 /// ScheduleTopDownLive Interface 381 382 virtual SUnit *pickNode() { 383 if (Queue.empty()) return NULL; 384 SUnit *SU = Queue.top(); 385 Queue.pop(); 386 return SU; 387 } 388 389 virtual void releaseNode(SUnit *SU) { 390 Queue.push(SU); 391 } 392}; 393} // namespace 394 395static ScheduleDAGInstrs *createInstructionShuffler(MachineSchedContext *C) { 396 return new InstructionShuffler(C); 397} 398static MachineSchedRegistry ShufflerRegistry("shuffle", 399 "Shuffle machine instructions", 400 createInstructionShuffler); 401#endif // !NDEBUG 402