MachineScheduler.cpp revision cf46b5acfd6e0ab5d21ec3160cec195d0eb77b0b
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 "ScheduleDAGInstrs.h" 18#include "llvm/CodeGen/LiveIntervalAnalysis.h" 19#include "llvm/CodeGen/MachinePassRegistry.h" 20#include "llvm/CodeGen/Passes.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 MachineFunctionPass { 47public: 48 MachineFunction *MF; 49 const TargetInstrInfo *TII; 50 const MachineLoopInfo *MLI; 51 const MachineDominatorTree *MDT; 52 LiveIntervals *LIS; 53 54 MachineScheduler(); 55 56 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 57 58 virtual void releaseMemory() {} 59 60 virtual bool runOnMachineFunction(MachineFunction&); 61 62 virtual void print(raw_ostream &O, const Module* = 0) const; 63 64 static char ID; // Class identification, replacement for typeinfo 65}; 66} // namespace 67 68char MachineScheduler::ID = 0; 69 70char &llvm::MachineSchedulerID = MachineScheduler::ID; 71 72INITIALIZE_PASS_BEGIN(MachineScheduler, "misched", 73 "Machine Instruction Scheduler", false, false) 74INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 75INITIALIZE_PASS_DEPENDENCY(SlotIndexes) 76INITIALIZE_PASS_DEPENDENCY(LiveIntervals) 77INITIALIZE_PASS_END(MachineScheduler, "misched", 78 "Machine Instruction Scheduler", false, false) 79 80MachineScheduler::MachineScheduler() 81: MachineFunctionPass(ID), MF(0), MLI(0), MDT(0) { 82 initializeMachineSchedulerPass(*PassRegistry::getPassRegistry()); 83} 84 85void MachineScheduler::getAnalysisUsage(AnalysisUsage &AU) const { 86 AU.setPreservesCFG(); 87 AU.addRequiredID(MachineDominatorsID); 88 AU.addRequired<MachineLoopInfo>(); 89 AU.addRequired<AliasAnalysis>(); 90 AU.addPreserved<AliasAnalysis>(); 91 AU.addRequired<SlotIndexes>(); 92 AU.addPreserved<SlotIndexes>(); 93 AU.addRequired<LiveIntervals>(); 94 AU.addPreserved<LiveIntervals>(); 95 MachineFunctionPass::getAnalysisUsage(AU); 96} 97 98namespace { 99/// MachineSchedRegistry provides a selection of available machine instruction 100/// schedulers. 101class MachineSchedRegistry : public MachinePassRegistryNode { 102public: 103 typedef ScheduleDAGInstrs *(*ScheduleDAGCtor)(MachineScheduler *); 104 105 // RegisterPassParser requires a (misnamed) FunctionPassCtor type. 106 typedef ScheduleDAGCtor FunctionPassCtor; 107 108 static MachinePassRegistry Registry; 109 110 MachineSchedRegistry(const char *N, const char *D, ScheduleDAGCtor C) 111 : MachinePassRegistryNode(N, D, (MachinePassCtor)C) { 112 Registry.Add(this); 113 } 114 ~MachineSchedRegistry() { Registry.Remove(this); } 115 116 // Accessors. 117 // 118 MachineSchedRegistry *getNext() const { 119 return (MachineSchedRegistry *)MachinePassRegistryNode::getNext(); 120 } 121 static MachineSchedRegistry *getList() { 122 return (MachineSchedRegistry *)Registry.getList(); 123 } 124 static ScheduleDAGCtor getDefault() { 125 return (ScheduleDAGCtor)Registry.getDefault(); 126 } 127 static void setDefault(ScheduleDAGCtor C) { 128 Registry.setDefault((MachinePassCtor)C); 129 } 130 static void setListener(MachinePassRegistryListener *L) { 131 Registry.setListener(L); 132 } 133}; 134} // namespace 135 136MachinePassRegistry MachineSchedRegistry::Registry; 137 138static ScheduleDAGInstrs *createDefaultMachineSched(MachineScheduler *P); 139 140/// MachineSchedOpt allows command line selection of the scheduler. 141static cl::opt<MachineSchedRegistry::ScheduleDAGCtor, false, 142 RegisterPassParser<MachineSchedRegistry> > 143MachineSchedOpt("misched", 144 cl::init(&createDefaultMachineSched), cl::Hidden, 145 cl::desc("Machine instruction scheduler to use")); 146 147//===----------------------------------------------------------------------===// 148// Machine Instruction Scheduling Common Implementation 149//===----------------------------------------------------------------------===// 150 151namespace { 152/// ScheduleTopDownLive is an implementation of ScheduleDAGInstrs that schedules 153/// machine instructions while updating LiveIntervals. 154class ScheduleTopDownLive : public ScheduleDAGInstrs { 155protected: 156 MachineScheduler *Pass; 157public: 158 ScheduleTopDownLive(MachineScheduler *P): 159 ScheduleDAGInstrs(*P->MF, *P->MLI, *P->MDT, /*IsPostRA=*/false, P->LIS), 160 Pass(P) {} 161 162 /// ScheduleDAGInstrs callback. 163 void schedule(); 164 165 /// Interface implemented by the selected top-down liveinterval scheduler. 166 /// 167 /// Pick the next node to schedule, or return NULL. 168 virtual SUnit *pickNode() = 0; 169 170 /// When all preceeding dependencies have been resolved, free this node for 171 /// scheduling. 172 virtual void releaseNode(SUnit *SU) = 0; 173 174protected: 175 void releaseSucc(SUnit *SU, SDep *SuccEdge); 176 void releaseSuccessors(SUnit *SU); 177}; 178} // namespace 179 180/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. When 181/// NumPredsLeft reaches zero, release the successor node. 182void ScheduleTopDownLive::releaseSucc(SUnit *SU, SDep *SuccEdge) { 183 SUnit *SuccSU = SuccEdge->getSUnit(); 184 185#ifndef NDEBUG 186 if (SuccSU->NumPredsLeft == 0) { 187 dbgs() << "*** Scheduling failed! ***\n"; 188 SuccSU->dump(this); 189 dbgs() << " has been released too many times!\n"; 190 llvm_unreachable(0); 191 } 192#endif 193 --SuccSU->NumPredsLeft; 194 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) 195 releaseNode(SuccSU); 196} 197 198/// releaseSuccessors - Call releaseSucc on each of SU's successors. 199void ScheduleTopDownLive::releaseSuccessors(SUnit *SU) { 200 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 201 I != E; ++I) { 202 releaseSucc(SU, &*I); 203 } 204} 205 206/// schedule - This is called back from ScheduleDAGInstrs::Run() when it's 207/// time to do some work. 208void ScheduleTopDownLive::schedule() { 209 buildSchedGraph(&Pass->getAnalysis<AliasAnalysis>()); 210 211 DEBUG(dbgs() << "********** MI Scheduling **********\n"); 212 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 213 SUnits[su].dumpAll(this)); 214 215 if (ViewMISchedDAGs) viewGraph(); 216 217 // Release any successors of the special Entry node. It is currently unused, 218 // but we keep up appearances. 219 releaseSuccessors(&EntrySU); 220 221 // Release all DAG roots for scheduling. 222 for (std::vector<SUnit>::iterator I = SUnits.begin(), E = SUnits.end(); 223 I != E; ++I) { 224 // A SUnit is ready to schedule if it has no predecessors. 225 if (I->Preds.empty()) 226 releaseNode(&(*I)); 227 } 228 229 MachineBasicBlock::iterator InsertPos = Begin; 230 while (SUnit *SU = pickNode()) { 231 DEBUG(dbgs() << "*** Scheduling Instruction:\n"; SU->dump(this)); 232 233 // Move the instruction to its new location in the instruction stream. 234 MachineInstr *MI = SU->getInstr(); 235 if (&*InsertPos == MI) 236 ++InsertPos; 237 else { 238 BB->splice(InsertPos, BB, MI); 239 Pass->LIS->handleMove(MI); 240 if (Begin == InsertPos) 241 Begin = MI; 242 } 243 244 // Release dependent instructions for scheduling. 245 releaseSuccessors(SU); 246 } 247} 248 249bool MachineScheduler::runOnMachineFunction(MachineFunction &mf) { 250 // Initialize the context of the pass. 251 MF = &mf; 252 MLI = &getAnalysis<MachineLoopInfo>(); 253 MDT = &getAnalysis<MachineDominatorTree>(); 254 LIS = &getAnalysis<LiveIntervals>(); 255 TII = MF->getTarget().getInstrInfo(); 256 257 // Select the scheduler, or set the default. 258 MachineSchedRegistry::ScheduleDAGCtor Ctor = 259 MachineSchedRegistry::getDefault(); 260 if (!Ctor) { 261 Ctor = MachineSchedOpt; 262 MachineSchedRegistry::setDefault(Ctor); 263 } 264 // Instantiate the selected scheduler. 265 OwningPtr<ScheduleDAGInstrs> Scheduler(Ctor(this)); 266 267 // Visit all machine basic blocks. 268 for (MachineFunction::iterator MBB = MF->begin(), MBBEnd = MF->end(); 269 MBB != MBBEnd; ++MBB) { 270 271 // Break the block into scheduling regions [I, RegionEnd), and schedule each 272 // region as soon as it is discovered. 273 unsigned RemainingCount = MBB->size(); 274 for(MachineBasicBlock::iterator RegionEnd = MBB->end(); 275 RegionEnd != MBB->begin();) { 276 Scheduler->startBlock(MBB); 277 // The next region starts above the previous region. Look backward in the 278 // instruction stream until we find the nearest boundary. 279 MachineBasicBlock::iterator I = RegionEnd; 280 for(;I != MBB->begin(); --I, --RemainingCount) { 281 if (TII->isSchedulingBoundary(llvm::prior(I), MBB, *MF)) 282 break; 283 } 284 // Notify the scheduler of the region, even if we may skip scheduling 285 // it. Perhaps it still needs to be bundled. 286 Scheduler->enterRegion(MBB, I, RegionEnd, RemainingCount); 287 288 // Skip empty scheduling regions (0 or 1 schedulable instructions). 289 if (I == RegionEnd || I == llvm::prior(RegionEnd)) { 290 RegionEnd = llvm::prior(RegionEnd); 291 if (I != RegionEnd) 292 --RemainingCount; 293 // Close the current region. Bundle the terminator if needed. 294 Scheduler->exitRegion(); 295 continue; 296 } 297 DEBUG(dbgs() << "MachineScheduling " << MF->getFunction()->getName() 298 << ":BB#" << MBB->getNumber() << "\n From: " << *I << " To: "; 299 if (RegionEnd != MBB->end()) dbgs() << *RegionEnd; 300 else dbgs() << "End"; 301 dbgs() << " Remaining: " << RemainingCount << "\n"); 302 303 // Inform ScheduleDAGInstrs of the region being scheduled. It calls back 304 // to our schedule() method. 305 Scheduler->schedule(); 306 Scheduler->exitRegion(); 307 308 // Scheduling has invalidated the current iterator 'I'. Ask the 309 // scheduler for the top of it's scheduled region. 310 RegionEnd = Scheduler->begin(); 311 } 312 assert(RemainingCount == 0 && "Instruction count mismatch!"); 313 Scheduler->finishBlock(); 314 } 315 return true; 316} 317 318void MachineScheduler::print(raw_ostream &O, const Module* m) const { 319 // unimplemented 320} 321 322//===----------------------------------------------------------------------===// 323// Placeholder for extending the machine instruction scheduler. 324//===----------------------------------------------------------------------===// 325 326namespace { 327class DefaultMachineScheduler : public ScheduleDAGInstrs { 328 MachineScheduler *Pass; 329public: 330 DefaultMachineScheduler(MachineScheduler *P): 331 ScheduleDAGInstrs(*P->MF, *P->MLI, *P->MDT, /*IsPostRA=*/false, P->LIS), 332 Pass(P) {} 333 334 /// schedule - This is called back from ScheduleDAGInstrs::Run() when it's 335 /// time to do some work. 336 void schedule(); 337}; 338} // namespace 339 340static ScheduleDAGInstrs *createDefaultMachineSched(MachineScheduler *P) { 341 return new DefaultMachineScheduler(P); 342} 343static MachineSchedRegistry 344SchedDefaultRegistry("default", "Activate the scheduler pass, " 345 "but don't reorder instructions", 346 createDefaultMachineSched); 347 348 349/// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's 350/// time to do some work. 351void DefaultMachineScheduler::schedule() { 352 buildSchedGraph(&Pass->getAnalysis<AliasAnalysis>()); 353 354 DEBUG(dbgs() << "********** MI Scheduling **********\n"); 355 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 356 SUnits[su].dumpAll(this)); 357 358 // TODO: Put interesting things here. 359 // 360 // When this is fully implemented, it will become a subclass of 361 // ScheduleTopDownLive. So this driver will disappear. 362} 363 364//===----------------------------------------------------------------------===// 365// Machine Instruction Shuffler for Correctness Testing 366//===----------------------------------------------------------------------===// 367 368#ifndef NDEBUG 369namespace { 370// Nodes with a higher number have higher priority. This way we attempt to 371// schedule the latest instructions earliest. 372// 373// TODO: Relies on the property of the BuildSchedGraph that results in SUnits 374// being ordered in sequence top-down. 375struct ShuffleSUnitOrder { 376 bool operator()(SUnit *A, SUnit *B) const { 377 return A->NodeNum < B->NodeNum; 378 } 379}; 380 381/// Reorder instructions as much as possible. 382class InstructionShuffler : public ScheduleTopDownLive { 383 std::priority_queue<SUnit*, std::vector<SUnit*>, ShuffleSUnitOrder> Queue; 384public: 385 InstructionShuffler(MachineScheduler *P): 386 ScheduleTopDownLive(P) {} 387 388 /// ScheduleTopDownLive Interface 389 390 virtual SUnit *pickNode() { 391 if (Queue.empty()) return NULL; 392 SUnit *SU = Queue.top(); 393 Queue.pop(); 394 return SU; 395 } 396 397 virtual void releaseNode(SUnit *SU) { 398 Queue.push(SU); 399 } 400}; 401} // namespace 402 403static ScheduleDAGInstrs *createInstructionShuffler(MachineScheduler *P) { 404 return new InstructionShuffler(P); 405} 406static MachineSchedRegistry ShufflerRegistry("shuffle", 407 "Shuffle machine instructions", 408 createInstructionShuffler); 409#endif // !NDEBUG 410