MachineScheduler.cpp revision 0df7f8821cc3ce26843b4fb63456cb4ccb7e4153
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 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 if (I == RegionEnd) { 285 // Skip empty scheduling regions. 286 RegionEnd = llvm::prior(RegionEnd); 287 --RemainingCount; 288 continue; 289 } 290 // Skip regions with one instruction. 291 if (I == llvm::prior(RegionEnd)) { 292 RegionEnd = llvm::prior(RegionEnd); 293 continue; 294 } 295 DEBUG(dbgs() << "MachineScheduling " << MF->getFunction()->getName() 296 << ":BB#" << MBB->getNumber() << "\n From: " << *I << " To: "; 297 if (RegionEnd != MBB->end()) dbgs() << *RegionEnd; 298 else dbgs() << "End"; 299 dbgs() << " Remaining: " << RemainingCount << "\n"); 300 301 // Inform ScheduleDAGInstrs of the region being scheduled. It calls back 302 // to our Schedule() method. 303 Scheduler->Run(MBB, I, RegionEnd, MBB->size()); 304 RegionEnd = Scheduler->Begin; 305 } 306 assert(RemainingCount == 0 && "Instruction count mismatch!"); 307 Scheduler->FinishBlock(); 308 } 309 return true; 310} 311 312void MachineScheduler::print(raw_ostream &O, const Module* m) const { 313 // unimplemented 314} 315 316//===----------------------------------------------------------------------===// 317// Placeholder for extending the machine instruction scheduler. 318//===----------------------------------------------------------------------===// 319 320namespace { 321class DefaultMachineScheduler : public ScheduleDAGInstrs { 322 MachineScheduler *Pass; 323public: 324 DefaultMachineScheduler(MachineScheduler *P): 325 ScheduleDAGInstrs(*P->MF, *P->MLI, *P->MDT, /*IsPostRA=*/false, P->LIS), 326 Pass(P) {} 327 328 /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's 329 /// time to do some work. 330 void Schedule(); 331}; 332} // namespace 333 334static ScheduleDAGInstrs *createDefaultMachineSched(MachineScheduler *P) { 335 return new DefaultMachineScheduler(P); 336} 337static MachineSchedRegistry 338SchedDefaultRegistry("default", "Activate the scheduler pass, " 339 "but don't reorder instructions", 340 createDefaultMachineSched); 341 342 343/// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's 344/// time to do some work. 345void DefaultMachineScheduler::Schedule() { 346 BuildSchedGraph(&Pass->getAnalysis<AliasAnalysis>()); 347 348 DEBUG(dbgs() << "********** MI Scheduling **********\n"); 349 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 350 SUnits[su].dumpAll(this)); 351 352 // TODO: Put interesting things here. 353 // 354 // When this is fully implemented, it will become a subclass of 355 // ScheduleTopDownLive. So this driver will disappear. 356} 357 358//===----------------------------------------------------------------------===// 359// Machine Instruction Shuffler for Correctness Testing 360//===----------------------------------------------------------------------===// 361 362#ifndef NDEBUG 363namespace { 364// Nodes with a higher number have higher priority. This way we attempt to 365// schedule the latest instructions earliest. 366// 367// TODO: Relies on the property of the BuildSchedGraph that results in SUnits 368// being ordered in sequence top-down. 369struct ShuffleSUnitOrder { 370 bool operator()(SUnit *A, SUnit *B) const { 371 return A->NodeNum < B->NodeNum; 372 } 373}; 374 375/// Reorder instructions as much as possible. 376class InstructionShuffler : public ScheduleTopDownLive { 377 std::priority_queue<SUnit*, std::vector<SUnit*>, ShuffleSUnitOrder> Queue; 378public: 379 InstructionShuffler(MachineScheduler *P): 380 ScheduleTopDownLive(P) {} 381 382 /// ScheduleTopDownLive Interface 383 384 virtual SUnit *pickNode() { 385 if (Queue.empty()) return NULL; 386 SUnit *SU = Queue.top(); 387 Queue.pop(); 388 return SU; 389 } 390 391 virtual void releaseNode(SUnit *SU) { 392 Queue.push(SU); 393 } 394}; 395} // namespace 396 397static ScheduleDAGInstrs *createInstructionShuffler(MachineScheduler *P) { 398 return new InstructionShuffler(P); 399} 400static MachineSchedRegistry ShufflerRegistry("shuffle", 401 "Shuffle machine instructions", 402 createInstructionShuffler); 403#endif // !NDEBUG 404