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 /// MachineSchedulerPass runs after coalescing and before register allocation. 38 class MachineSchedulerPass : public MachineFunctionPass { 39 public: 40 MachineFunction *MF; 41 const TargetInstrInfo *TII; 42 const MachineLoopInfo *MLI; 43 const MachineDominatorTree *MDT; 44 45 MachineSchedulerPass(); 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 MachineSchedulerPass::ID = 0; 60 61 char &llvm::MachineSchedulerPassID = MachineSchedulerPass::ID; 62 63 INITIALIZE_PASS_BEGIN(MachineSchedulerPass, "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(MachineSchedulerPass, "misched", 72 "Machine Instruction Scheduler", false, false) 73 74 MachineSchedulerPass::MachineSchedulerPass() 75 : MachineFunctionPass(ID), MF(0), MLI(0), MDT(0) { 76 initializeMachineSchedulerPassPass(*PassRegistry::getPassRegistry()); 77 } 78 79 void MachineSchedulerPass::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)(MachineSchedulerPass *); 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(MachineSchedulerPass *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 Implementation 151 //===----------------------------------------------------------------------===// 152 153 namespace { 154 /// MachineScheduler is an implementation of ScheduleDAGInstrs that schedules 155 /// machine instructions while updating LiveIntervals. 156 class MachineScheduler : public ScheduleDAGInstrs { 157 MachineSchedulerPass *Pass; 158 public: 159 MachineScheduler(MachineSchedulerPass *P): 160 ScheduleDAGInstrs(*P->MF, *P->MLI, *P->MDT, /*IsPostRA=*/false), Pass(P) {} 161 162 /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's 163 /// time to do some work. 164 virtual void Schedule(); 165 }; 166 } // namespace 167 168 static ScheduleDAGInstrs *createDefaultMachineSched(MachineSchedulerPass *P) { 169 return new MachineScheduler(P); 170 } 171 static MachineSchedRegistry 172 SchedDefaultRegistry("default", "Activate the scheduler pass, " 173 "but don't reorder instructions", 174 createDefaultMachineSched); 175 176 /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's 177 /// time to do some work. 178 void MachineScheduler::Schedule() { 179 BuildSchedGraph(&Pass->getAnalysis<AliasAnalysis>()); 180 181 DEBUG(dbgs() << "********** MI Scheduling **********\n"); 182 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 183 SUnits[su].dumpAll(this)); 184 185 // TODO: Put interesting things here. 186 } 187 188 bool MachineSchedulerPass::runOnMachineFunction(MachineFunction &mf) { 189 // Initialize the context of the pass. 190 MF = &mf; 191 MLI = &getAnalysis<MachineLoopInfo>(); 192 MDT = &getAnalysis<MachineDominatorTree>(); 193 TII = MF->getTarget().getInstrInfo(); 194 195 // Select the scheduler, or set the default. 196 MachineSchedRegistry::ScheduleDAGCtor Ctor = 197 MachineSchedRegistry::getDefault(); 198 if (!Ctor) { 199 Ctor = MachineSchedOpt; 200 MachineSchedRegistry::setDefault(Ctor); 201 } 202 // Instantiate the selected scheduler. 203 OwningPtr<ScheduleDAGInstrs> Scheduler(Ctor(this)); 204 205 // Visit all machine basic blocks. 206 for (MachineFunction::iterator MBB = MF->begin(), MBBEnd = MF->end(); 207 MBB != MBBEnd; ++MBB) { 208 209 // Break the block into scheduling regions [I, RegionEnd), and schedule each 210 // region as soon as it is discovered. 211 unsigned RemainingCount = MBB->size(); 212 for(MachineBasicBlock::iterator RegionEnd = MBB->end(); 213 RegionEnd != MBB->begin();) { 214 // The next region starts above the previous region. Look backward in the 215 // instruction stream until we find the nearest boundary. 216 MachineBasicBlock::iterator I = RegionEnd; 217 for(;I != MBB->begin(); --I) { 218 if (TII->isSchedulingBoundary(llvm::prior(I), MBB, *MF)) 219 break; 220 } 221 if (I == RegionEnd || I == llvm::prior(RegionEnd)) { 222 // Skip empty or single instruction scheduling regions. 223 RegionEnd = llvm::prior(RegionEnd); 224 continue; 225 } 226 DEBUG(dbgs() << "MachineScheduling " << MF->getFunction()->getName() 227 << ":BB#" << MBB->getNumber() << "\n From: " << *I << " To: " 228 << *RegionEnd << " Remaining: " << RemainingCount << "\n"); 229 230 // Inform ScheduleDAGInstrs of the region being scheduler. It calls back 231 // to our Schedule() method. 232 Scheduler->Run(MBB, I, RegionEnd, MBB->size()); 233 RegionEnd = I; 234 } 235 assert(RemainingCount == 0 && "Instruction count mismatch!"); 236 } 237 return true; 238 } 239 240 void MachineSchedulerPass::print(raw_ostream &O, const Module* m) const { 241 // unimplemented 242 } 243 244 //===----------------------------------------------------------------------===// 245 // Machine Instruction Shuffler for Correctness Testing 246 //===----------------------------------------------------------------------===// 247 248 #ifndef NDEBUG 249 namespace { 250 /// Reorder instructions as much as possible. 251 class InstructionShuffler : public ScheduleDAGInstrs { 252 MachineSchedulerPass *Pass; 253 public: 254 InstructionShuffler(MachineSchedulerPass *P): 255 ScheduleDAGInstrs(*P->MF, *P->MLI, *P->MDT, /*IsPostRA=*/false), Pass(P) {} 256 257 /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's 258 /// time to do some work. 259 virtual void Schedule() { 260 llvm_unreachable("unimplemented"); 261 } 262 }; 263 } // namespace 264 265 static ScheduleDAGInstrs *createInstructionShuffler(MachineSchedulerPass *P) { 266 return new InstructionShuffler(P); 267 } 268 static MachineSchedRegistry ShufflerRegistry("shuffle", 269 "Shuffle machine instructions", 270 createInstructionShuffler); 271 #endif // !NDEBUG 272