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