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/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 using namespace llvm; 30 31 namespace { 32 /// MachineSchedulerPass runs after coalescing and before register allocation. 33 class MachineSchedulerPass : public MachineFunctionPass { 34 public: 35 MachineFunction *MF; 36 const MachineLoopInfo *MLI; 37 const MachineDominatorTree *MDT; 38 39 MachineSchedulerPass(); 40 41 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 42 43 virtual void releaseMemory() {} 44 45 virtual bool runOnMachineFunction(MachineFunction&); 46 47 virtual void print(raw_ostream &O, const Module* = 0) const; 48 49 static char ID; // Class identification, replacement for typeinfo 50 }; 51 } // namespace 52 53 char MachineSchedulerPass::ID = 0; 54 55 char &llvm::MachineSchedulerPassID = MachineSchedulerPass::ID; 56 57 INITIALIZE_PASS_BEGIN(MachineSchedulerPass, "misched", 58 "Machine Instruction Scheduler", false, false) 59 INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 60 INITIALIZE_PASS_DEPENDENCY(SlotIndexes) 61 INITIALIZE_PASS_DEPENDENCY(LiveIntervals) 62 INITIALIZE_PASS_DEPENDENCY(LiveDebugVariables) 63 INITIALIZE_PASS_DEPENDENCY(StrongPHIElimination) 64 INITIALIZE_PASS_DEPENDENCY(RegisterCoalescer) 65 INITIALIZE_PASS_END(MachineSchedulerPass, "misched", 66 "Machine Instruction Scheduler", false, false) 67 68 MachineSchedulerPass::MachineSchedulerPass() 69 : MachineFunctionPass(ID), MF(0), MLI(0), MDT(0) { 70 initializeMachineSchedulerPassPass(*PassRegistry::getPassRegistry()); 71 } 72 73 void MachineSchedulerPass::getAnalysisUsage(AnalysisUsage &AU) const { 74 AU.setPreservesCFG(); 75 AU.addRequiredID(MachineDominatorsID); 76 AU.addRequired<MachineLoopInfo>(); 77 AU.addRequired<AliasAnalysis>(); 78 AU.addPreserved<AliasAnalysis>(); 79 AU.addRequired<SlotIndexes>(); 80 AU.addPreserved<SlotIndexes>(); 81 AU.addRequired<LiveIntervals>(); 82 AU.addPreserved<LiveIntervals>(); 83 AU.addRequired<LiveDebugVariables>(); 84 AU.addPreserved<LiveDebugVariables>(); 85 if (StrongPHIElim) { 86 AU.addRequiredID(StrongPHIEliminationID); 87 AU.addPreservedID(StrongPHIEliminationID); 88 } 89 AU.addRequiredID(RegisterCoalescerPassID); 90 AU.addPreservedID(RegisterCoalescerPassID); 91 MachineFunctionPass::getAnalysisUsage(AU); 92 } 93 94 namespace { 95 /// Currently force DAG building but don't reschedule anything. This is a 96 /// temporarily useful framework that provides a place to hook in experimental 97 /// code that requires a dependence graph prior to register allocation. 98 class MachineScheduler : public ScheduleDAGInstrs { 99 public: 100 MachineScheduler(MachineSchedulerPass *P) 101 : ScheduleDAGInstrs(*P->MF, *P->MLI, *P->MDT) 102 {} 103 104 /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's 105 /// time to do some work. 106 virtual void Schedule(); 107 }; 108 } // namespace 109 110 namespace { 111 /// MachineSchedRegistry provides a selection of available machine instruction 112 /// schedulers. 113 class MachineSchedRegistry : public MachinePassRegistryNode { 114 public: 115 typedef ScheduleDAGInstrs *(*ScheduleDAGCtor)(MachineSchedulerPass *); 116 117 // RegisterPassParser requires a (misnamed) FunctionPassCtor type. 118 typedef ScheduleDAGCtor FunctionPassCtor; 119 120 static MachinePassRegistry Registry; 121 122 MachineSchedRegistry(const char *N, const char *D, ScheduleDAGCtor C) 123 : MachinePassRegistryNode(N, D, (MachinePassCtor)C) { 124 Registry.Add(this); 125 } 126 ~MachineSchedRegistry() { Registry.Remove(this); } 127 128 // Accessors. 129 // 130 MachineSchedRegistry *getNext() const { 131 return (MachineSchedRegistry *)MachinePassRegistryNode::getNext(); 132 } 133 static MachineSchedRegistry *getList() { 134 return (MachineSchedRegistry *)Registry.getList(); 135 } 136 static ScheduleDAGCtor getDefault() { 137 return (ScheduleDAGCtor)Registry.getDefault(); 138 } 139 static void setDefault(ScheduleDAGCtor C) { 140 Registry.setDefault((MachinePassCtor)C); 141 } 142 static void setListener(MachinePassRegistryListener *L) { 143 Registry.setListener(L); 144 } 145 }; 146 } // namespace 147 148 MachinePassRegistry MachineSchedRegistry::Registry; 149 150 static ScheduleDAGInstrs *createDefaultMachineSched(MachineSchedulerPass *P); 151 152 /// MachineSchedOpt allows command line selection of the scheduler. 153 static cl::opt<MachineSchedRegistry::ScheduleDAGCtor, false, 154 RegisterPassParser<MachineSchedRegistry> > 155 MachineSchedOpt("misched", 156 cl::init(&createDefaultMachineSched), cl::Hidden, 157 cl::desc("Machine instruction scheduler to use")); 158 159 static ScheduleDAGInstrs *createDefaultMachineSched(MachineSchedulerPass *P) { 160 return new MachineScheduler(P); 161 } 162 static MachineSchedRegistry 163 SchedDefaultRegistry("default", "Activate the scheduler pass, " 164 "but don't reorder instructions", 165 createDefaultMachineSched); 166 167 /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's 168 /// time to do some work. 169 void MachineScheduler::Schedule() { 170 DEBUG(dbgs() << "********** MI Scheduling **********\n"); 171 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 172 SUnits[su].dumpAll(this)); 173 // TODO: Put interesting things here. 174 } 175 176 bool MachineSchedulerPass::runOnMachineFunction(MachineFunction &mf) { 177 // Initialize the context of the pass. 178 MF = &mf; 179 MLI = &getAnalysis<MachineLoopInfo>(); 180 MDT = &getAnalysis<MachineDominatorTree>(); 181 182 // Select the scheduler, or set the default. 183 MachineSchedRegistry::ScheduleDAGCtor Ctor = 184 MachineSchedRegistry::getDefault(); 185 if (!Ctor) { 186 Ctor = MachineSchedOpt; 187 MachineSchedRegistry::setDefault(Ctor); 188 } 189 // Instantiate the selected scheduler. 190 OwningPtr<ScheduleDAGInstrs> Scheduler(Ctor(this)); 191 192 // Visit all machine basic blocks. 193 for (MachineFunction::iterator MBB = MF->begin(), MBBEnd = MF->end(); 194 MBB != MBBEnd; ++MBB) { 195 196 DEBUG(dbgs() << "MachineScheduling " << MF->getFunction()->getName() 197 << ":BB#" << MBB->getNumber() << "\n"); 198 199 // Inform ScheduleDAGInstrs of the region being scheduler. It calls back 200 // to our Schedule() method. 201 Scheduler->Run(MBB, MBB->begin(), MBB->end(), MBB->size()); 202 } 203 return true; 204 } 205 206 void MachineSchedulerPass::print(raw_ostream &O, const Module* m) const { 207 // unimplemented 208 } 209 210 #ifndef NDEBUG 211 namespace { 212 /// Reorder instructions as much as possible. 213 class InstructionShuffler : public ScheduleDAGInstrs { 214 public: 215 InstructionShuffler(MachineSchedulerPass *P) 216 : ScheduleDAGInstrs(*P->MF, *P->MLI, *P->MDT) 217 {} 218 219 /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's 220 /// time to do some work. 221 virtual void Schedule() { 222 llvm_unreachable("unimplemented"); 223 } 224 }; 225 } // namespace 226 227 static ScheduleDAGInstrs *createInstructionShuffler(MachineSchedulerPass *P) { 228 return new InstructionShuffler(P); 229 } 230 static MachineSchedRegistry ShufflerRegistry("shuffle", 231 "Shuffle machine instructions", 232 createInstructionShuffler); 233 #endif // !NDEBUG 234