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