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 "LiveDebugVariables.h" 19 #include "llvm/CodeGen/LiveIntervalAnalysis.h" 20 #include "llvm/CodeGen/MachinePassRegistry.h" 21 #include "llvm/CodeGen/Passes.h" 22 #include "llvm/Analysis/AliasAnalysis.h" 23 #include "llvm/Target/TargetInstrInfo.h" 24 #include "llvm/Support/CommandLine.h" 25 #include "llvm/Support/Debug.h" 26 #include "llvm/Support/ErrorHandling.h" 27 #include "llvm/Support/raw_ostream.h" 28 #include "llvm/ADT/OwningPtr.h" 29 30 using namespace llvm; 31 32 //===----------------------------------------------------------------------===// 33 // Machine Instruction Scheduling Pass and Registry 34 //===----------------------------------------------------------------------===// 35 36 namespace { 37 /// MachineScheduler runs after coalescing and before register allocation. 38 class MachineScheduler : public MachineFunctionPass { 39 public: 40 MachineFunction *MF; 41 const TargetInstrInfo *TII; 42 const MachineLoopInfo *MLI; 43 const MachineDominatorTree *MDT; 44 45 MachineScheduler(); 46 47 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 48 49 virtual void releaseMemory() {} 50 51 virtual bool runOnMachineFunction(MachineFunction&); 52 53 virtual void print(raw_ostream &O, const Module* = 0) const; 54 55 static char ID; // Class identification, replacement for typeinfo 56 }; 57 } // namespace 58 59 char MachineScheduler::ID = 0; 60 61 char &llvm::MachineSchedulerID = MachineScheduler::ID; 62 63 INITIALIZE_PASS_BEGIN(MachineScheduler, "misched", 64 "Machine Instruction Scheduler", false, false) 65 INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 66 INITIALIZE_PASS_DEPENDENCY(SlotIndexes) 67 INITIALIZE_PASS_DEPENDENCY(LiveIntervals) 68 INITIALIZE_PASS_DEPENDENCY(LiveDebugVariables) 69 INITIALIZE_PASS_DEPENDENCY(StrongPHIElimination) 70 INITIALIZE_PASS_DEPENDENCY(RegisterCoalescer) 71 INITIALIZE_PASS_END(MachineScheduler, "misched", 72 "Machine Instruction Scheduler", false, false) 73 74 MachineScheduler::MachineScheduler() 75 : MachineFunctionPass(ID), MF(0), MLI(0), MDT(0) { 76 initializeMachineSchedulerPass(*PassRegistry::getPassRegistry()); 77 } 78 79 void MachineScheduler::getAnalysisUsage(AnalysisUsage &AU) const { 80 AU.setPreservesCFG(); 81 AU.addRequiredID(MachineDominatorsID); 82 AU.addRequired<MachineLoopInfo>(); 83 AU.addRequired<AliasAnalysis>(); 84 AU.addPreserved<AliasAnalysis>(); 85 AU.addRequired<SlotIndexes>(); 86 AU.addPreserved<SlotIndexes>(); 87 AU.addRequired<LiveIntervals>(); 88 AU.addPreserved<LiveIntervals>(); 89 AU.addRequired<LiveDebugVariables>(); 90 AU.addPreserved<LiveDebugVariables>(); 91 if (StrongPHIElim) { 92 AU.addRequiredID(StrongPHIEliminationID); 93 AU.addPreservedID(StrongPHIEliminationID); 94 } 95 AU.addRequiredID(RegisterCoalescerPassID); 96 AU.addPreservedID(RegisterCoalescerPassID); 97 MachineFunctionPass::getAnalysisUsage(AU); 98 } 99 100 namespace { 101 /// MachineSchedRegistry provides a selection of available machine instruction 102 /// schedulers. 103 class MachineSchedRegistry : public MachinePassRegistryNode { 104 public: 105 typedef ScheduleDAGInstrs *(*ScheduleDAGCtor)(MachineScheduler *); 106 107 // RegisterPassParser requires a (misnamed) FunctionPassCtor type. 108 typedef ScheduleDAGCtor FunctionPassCtor; 109 110 static MachinePassRegistry Registry; 111 112 MachineSchedRegistry(const char *N, const char *D, ScheduleDAGCtor C) 113 : MachinePassRegistryNode(N, D, (MachinePassCtor)C) { 114 Registry.Add(this); 115 } 116 ~MachineSchedRegistry() { Registry.Remove(this); } 117 118 // Accessors. 119 // 120 MachineSchedRegistry *getNext() const { 121 return (MachineSchedRegistry *)MachinePassRegistryNode::getNext(); 122 } 123 static MachineSchedRegistry *getList() { 124 return (MachineSchedRegistry *)Registry.getList(); 125 } 126 static ScheduleDAGCtor getDefault() { 127 return (ScheduleDAGCtor)Registry.getDefault(); 128 } 129 static void setDefault(ScheduleDAGCtor C) { 130 Registry.setDefault((MachinePassCtor)C); 131 } 132 static void setListener(MachinePassRegistryListener *L) { 133 Registry.setListener(L); 134 } 135 }; 136 } // namespace 137 138 MachinePassRegistry MachineSchedRegistry::Registry; 139 140 static ScheduleDAGInstrs *createDefaultMachineSched(MachineScheduler *P); 141 142 /// MachineSchedOpt allows command line selection of the scheduler. 143 static cl::opt<MachineSchedRegistry::ScheduleDAGCtor, false, 144 RegisterPassParser<MachineSchedRegistry> > 145 MachineSchedOpt("misched", 146 cl::init(&createDefaultMachineSched), cl::Hidden, 147 cl::desc("Machine instruction scheduler to use")); 148 149 //===----------------------------------------------------------------------===// 150 // Machine Instruction Scheduling Common Implementation 151 //===----------------------------------------------------------------------===// 152 153 namespace { 154 /// MachineScheduler is an implementation of ScheduleDAGInstrs that schedules 155 /// machine instructions while updating LiveIntervals. 156 class ScheduleTopDownLive : public ScheduleDAGInstrs { 157 protected: 158 MachineScheduler *Pass; 159 public: 160 ScheduleTopDownLive(MachineScheduler *P): 161 ScheduleDAGInstrs(*P->MF, *P->MLI, *P->MDT, /*IsPostRA=*/false), Pass(P) {} 162 }; 163 } // namespace 164 165 bool MachineScheduler::runOnMachineFunction(MachineFunction &mf) { 166 // Initialize the context of the pass. 167 MF = &mf; 168 MLI = &getAnalysis<MachineLoopInfo>(); 169 MDT = &getAnalysis<MachineDominatorTree>(); 170 TII = MF->getTarget().getInstrInfo(); 171 172 // Select the scheduler, or set the default. 173 MachineSchedRegistry::ScheduleDAGCtor Ctor = 174 MachineSchedRegistry::getDefault(); 175 if (!Ctor) { 176 Ctor = MachineSchedOpt; 177 MachineSchedRegistry::setDefault(Ctor); 178 } 179 // Instantiate the selected scheduler. 180 OwningPtr<ScheduleDAGInstrs> Scheduler(Ctor(this)); 181 182 // Visit all machine basic blocks. 183 for (MachineFunction::iterator MBB = MF->begin(), MBBEnd = MF->end(); 184 MBB != MBBEnd; ++MBB) { 185 186 // Break the block into scheduling regions [I, RegionEnd), and schedule each 187 // region as soon as it is discovered. 188 unsigned RemainingCount = MBB->size(); 189 for(MachineBasicBlock::iterator RegionEnd = MBB->end(); 190 RegionEnd != MBB->begin();) { 191 // The next region starts above the previous region. Look backward in the 192 // instruction stream until we find the nearest boundary. 193 MachineBasicBlock::iterator I = RegionEnd; 194 for(;I != MBB->begin(); --I, --RemainingCount) { 195 if (TII->isSchedulingBoundary(llvm::prior(I), MBB, *MF)) 196 break; 197 } 198 if (I == RegionEnd) { 199 // Skip empty scheduling regions. 200 RegionEnd = llvm::prior(RegionEnd); 201 --RemainingCount; 202 continue; 203 } 204 // Schedule regions with more than one instruction. 205 if (I != llvm::prior(RegionEnd)) { 206 DEBUG(dbgs() << "MachineScheduling " << MF->getFunction()->getName() 207 << ":BB#" << MBB->getNumber() << "\n From: " << *I << " To: " 208 << *RegionEnd << " Remaining: " << RemainingCount << "\n"); 209 210 // Inform ScheduleDAGInstrs of the region being scheduled. It calls back 211 // to our Schedule() method. 212 Scheduler->Run(MBB, I, RegionEnd, MBB->size()); 213 } 214 RegionEnd = I; 215 } 216 assert(RemainingCount == 0 && "Instruction count mismatch!"); 217 } 218 return true; 219 } 220 221 void MachineScheduler::print(raw_ostream &O, const Module* m) const { 222 // unimplemented 223 } 224 225 //===----------------------------------------------------------------------===// 226 // Placeholder for extending the machine instruction scheduler. 227 //===----------------------------------------------------------------------===// 228 229 namespace { 230 class DefaultMachineScheduler : public ScheduleTopDownLive { 231 public: 232 DefaultMachineScheduler(MachineScheduler *P): 233 ScheduleTopDownLive(P) {} 234 235 void Schedule(); 236 }; 237 } // namespace 238 239 static ScheduleDAGInstrs *createDefaultMachineSched(MachineScheduler *P) { 240 return new DefaultMachineScheduler(P); 241 } 242 static MachineSchedRegistry 243 SchedDefaultRegistry("default", "Activate the scheduler pass, " 244 "but don't reorder instructions", 245 createDefaultMachineSched); 246 247 248 /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's 249 /// time to do some work. 250 void DefaultMachineScheduler::Schedule() { 251 BuildSchedGraph(&Pass->getAnalysis<AliasAnalysis>()); 252 253 DEBUG(dbgs() << "********** MI Scheduling **********\n"); 254 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 255 SUnits[su].dumpAll(this)); 256 257 // TODO: Put interesting things here. 258 } 259 260 //===----------------------------------------------------------------------===// 261 // Machine Instruction Shuffler for Correctness Testing 262 //===----------------------------------------------------------------------===// 263 264 #ifndef NDEBUG 265 namespace { 266 /// Reorder instructions as much as possible. 267 class InstructionShuffler : public ScheduleTopDownLive { 268 MachineScheduler *Pass; 269 public: 270 InstructionShuffler(MachineScheduler *P): 271 ScheduleTopDownLive(P) {} 272 273 /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's 274 /// time to do some work. 275 virtual void Schedule() { 276 llvm_unreachable("unimplemented"); 277 } 278 }; 279 } // namespace 280 281 static ScheduleDAGInstrs *createInstructionShuffler(MachineScheduler *P) { 282 return new InstructionShuffler(P); 283 } 284 static MachineSchedRegistry ShufflerRegistry("shuffle", 285 "Shuffle machine instructions", 286 createInstructionShuffler); 287 #endif // !NDEBUG 288