X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FCodeGen%2FMachineScheduler.cpp;h=4f27274796b472568be26827334770eaecc1ca28;hp=a14b3912236de6be3b1e8c91dbf7d1f4c42110cf;hb=68675c6c5b173021807e4e12cd250eeba63f6d0d;hpb=c6cf11b41243967b16211848b50876aab47e86df diff --git a/lib/CodeGen/MachineScheduler.cpp b/lib/CodeGen/MachineScheduler.cpp index a14b3912236..4f27274796b 100644 --- a/lib/CodeGen/MachineScheduler.cpp +++ b/lib/CodeGen/MachineScheduler.cpp @@ -14,11 +14,10 @@ #define DEBUG_TYPE "misched" -#include "ScheduleDAGInstrs.h" -#include "LiveDebugVariables.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" -#include "llvm/CodeGen/MachinePassRegistry.h" +#include "llvm/CodeGen/MachineScheduler.h" #include "llvm/CodeGen/Passes.h" +#include "llvm/CodeGen/ScheduleDAGInstrs.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Support/CommandLine.h" @@ -31,19 +30,22 @@ using namespace llvm; +#ifndef NDEBUG +static cl::opt ViewMISchedDAGs("view-misched-dags", cl::Hidden, + cl::desc("Pop up a window to show MISched dags after they are processed")); +#else +static bool ViewMISchedDAGs = false; +#endif // NDEBUG + //===----------------------------------------------------------------------===// // Machine Instruction Scheduling Pass and Registry //===----------------------------------------------------------------------===// namespace { /// MachineScheduler runs after coalescing and before register allocation. -class MachineScheduler : public MachineFunctionPass { +class MachineScheduler : public MachineSchedContext, + public MachineFunctionPass { public: - MachineFunction *MF; - const TargetInstrInfo *TII; - const MachineLoopInfo *MLI; - const MachineDominatorTree *MDT; - MachineScheduler(); virtual void getAnalysisUsage(AnalysisUsage &AU) const; @@ -67,14 +69,11 @@ INITIALIZE_PASS_BEGIN(MachineScheduler, "misched", INITIALIZE_AG_DEPENDENCY(AliasAnalysis) INITIALIZE_PASS_DEPENDENCY(SlotIndexes) INITIALIZE_PASS_DEPENDENCY(LiveIntervals) -INITIALIZE_PASS_DEPENDENCY(LiveDebugVariables) -INITIALIZE_PASS_DEPENDENCY(StrongPHIElimination) -INITIALIZE_PASS_DEPENDENCY(RegisterCoalescer) INITIALIZE_PASS_END(MachineScheduler, "misched", "Machine Instruction Scheduler", false, false) MachineScheduler::MachineScheduler() -: MachineFunctionPass(ID), MF(0), MLI(0), MDT(0) { +: MachineFunctionPass(ID) { initializeMachineSchedulerPass(*PassRegistry::getPassRegistry()); } @@ -83,87 +82,134 @@ void MachineScheduler::getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequiredID(MachineDominatorsID); AU.addRequired(); AU.addRequired(); - AU.addPreserved(); + AU.addRequired(); AU.addRequired(); AU.addPreserved(); AU.addRequired(); AU.addPreserved(); - AU.addRequired(); - AU.addPreserved(); - if (StrongPHIElim) { - AU.addRequiredID(StrongPHIEliminationID); - AU.addPreservedID(StrongPHIEliminationID); - } - AU.addRequiredID(RegisterCoalescerPassID); - AU.addPreservedID(RegisterCoalescerPassID); MachineFunctionPass::getAnalysisUsage(AU); } -namespace { -/// MachineSchedRegistry provides a selection of available machine instruction -/// schedulers. -class MachineSchedRegistry : public MachinePassRegistryNode { -public: - typedef ScheduleDAGInstrs *(*ScheduleDAGCtor)(MachineScheduler *); - - // RegisterPassParser requires a (misnamed) FunctionPassCtor type. - typedef ScheduleDAGCtor FunctionPassCtor; - - static MachinePassRegistry Registry; - - MachineSchedRegistry(const char *N, const char *D, ScheduleDAGCtor C) - : MachinePassRegistryNode(N, D, (MachinePassCtor)C) { - Registry.Add(this); - } - ~MachineSchedRegistry() { Registry.Remove(this); } - - // Accessors. - // - MachineSchedRegistry *getNext() const { - return (MachineSchedRegistry *)MachinePassRegistryNode::getNext(); - } - static MachineSchedRegistry *getList() { - return (MachineSchedRegistry *)Registry.getList(); - } - static ScheduleDAGCtor getDefault() { - return (ScheduleDAGCtor)Registry.getDefault(); - } - static void setDefault(ScheduleDAGCtor C) { - Registry.setDefault((MachinePassCtor)C); - } - static void setListener(MachinePassRegistryListener *L) { - Registry.setListener(L); - } -}; -} // namespace - MachinePassRegistry MachineSchedRegistry::Registry; -static ScheduleDAGInstrs *createDefaultMachineSched(MachineScheduler *P); +/// A dummy default scheduler factory indicates whether the scheduler +/// is overridden on the command line. +static ScheduleDAGInstrs *useDefaultMachineSched(MachineSchedContext *C) { + return 0; +} /// MachineSchedOpt allows command line selection of the scheduler. static cl::opt > MachineSchedOpt("misched", - cl::init(&createDefaultMachineSched), cl::Hidden, + cl::init(&useDefaultMachineSched), cl::Hidden, cl::desc("Machine instruction scheduler to use")); +static MachineSchedRegistry +SchedDefaultRegistry("default", "Use the target's default scheduler choice.", + useDefaultMachineSched); + +/// Forward declare the common machine scheduler. This will be used as the +/// default scheduler if the target does not set a default. +static ScheduleDAGInstrs *createCommonMachineSched(MachineSchedContext *C); + +bool MachineScheduler::runOnMachineFunction(MachineFunction &mf) { + // Initialize the context of the pass. + MF = &mf; + MLI = &getAnalysis(); + MDT = &getAnalysis(); + PassConfig = &getAnalysis(); + AA = &getAnalysis(); + + LIS = &getAnalysis(); + const TargetInstrInfo *TII = MF->getTarget().getInstrInfo(); + + // Select the scheduler, or set the default. + MachineSchedRegistry::ScheduleDAGCtor Ctor = MachineSchedOpt; + if (Ctor == useDefaultMachineSched) { + // Get the default scheduler set by the target. + Ctor = MachineSchedRegistry::getDefault(); + if (!Ctor) { + Ctor = createCommonMachineSched; + MachineSchedRegistry::setDefault(Ctor); + } + } + // Instantiate the selected scheduler. + OwningPtr Scheduler(Ctor(this)); + + // Visit all machine basic blocks. + for (MachineFunction::iterator MBB = MF->begin(), MBBEnd = MF->end(); + MBB != MBBEnd; ++MBB) { + + // Break the block into scheduling regions [I, RegionEnd), and schedule each + // region as soon as it is discovered. + unsigned RemainingCount = MBB->size(); + for(MachineBasicBlock::iterator RegionEnd = MBB->end(); + RegionEnd != MBB->begin();) { + Scheduler->startBlock(MBB); + // The next region starts above the previous region. Look backward in the + // instruction stream until we find the nearest boundary. + MachineBasicBlock::iterator I = RegionEnd; + for(;I != MBB->begin(); --I, --RemainingCount) { + if (TII->isSchedulingBoundary(llvm::prior(I), MBB, *MF)) + break; + } + // Notify the scheduler of the region, even if we may skip scheduling + // it. Perhaps it still needs to be bundled. + Scheduler->enterRegion(MBB, I, RegionEnd, RemainingCount); + + // Skip empty scheduling regions (0 or 1 schedulable instructions). + if (I == RegionEnd || I == llvm::prior(RegionEnd)) { + RegionEnd = llvm::prior(RegionEnd); + if (I != RegionEnd) + --RemainingCount; + // Close the current region. Bundle the terminator if needed. + Scheduler->exitRegion(); + continue; + } + DEBUG(dbgs() << "MachineScheduling " << MF->getFunction()->getName() + << ":BB#" << MBB->getNumber() << "\n From: " << *I << " To: "; + if (RegionEnd != MBB->end()) dbgs() << *RegionEnd; + else dbgs() << "End"; + dbgs() << " Remaining: " << RemainingCount << "\n"); + + // Schedule a region: possibly reorder instructions. + Scheduler->schedule(); + + // Close the current region. + Scheduler->exitRegion(); + + // Scheduling has invalidated the current iterator 'I'. Ask the + // scheduler for the top of it's scheduled region. + RegionEnd = Scheduler->begin(); + } + assert(RemainingCount == 0 && "Instruction count mismatch!"); + Scheduler->finishBlock(); + } + return true; +} + +void MachineScheduler::print(raw_ostream &O, const Module* m) const { + // unimplemented +} + //===----------------------------------------------------------------------===// -// Machine Instruction Scheduling Common Implementation -//===----------------------------------------------------------------------===// +// ScheduleTopeDownLive - Base class for basic top-down scheduling with +// LiveIntervals preservation. +// ===----------------------------------------------------------------------===// namespace { -/// MachineScheduler is an implementation of ScheduleDAGInstrs that schedules +/// ScheduleTopDownLive is an implementation of ScheduleDAGInstrs that schedules /// machine instructions while updating LiveIntervals. class ScheduleTopDownLive : public ScheduleDAGInstrs { -protected: - MachineScheduler *Pass; + AliasAnalysis *AA; public: - ScheduleTopDownLive(MachineScheduler *P): - ScheduleDAGInstrs(*P->MF, *P->MLI, *P->MDT, /*IsPostRA=*/false), Pass(P) {} + ScheduleTopDownLive(MachineSchedContext *C): + ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS), + AA(C->AA) {} - /// ScheduleDAGInstrs callback. - void Schedule(); + /// ScheduleDAGInstrs interface. + void schedule(); /// Interface implemented by the selected top-down liveinterval scheduler. /// @@ -206,15 +252,17 @@ void ScheduleTopDownLive::releaseSuccessors(SUnit *SU) { } } -/// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's +/// schedule - This is called back from ScheduleDAGInstrs::Run() when it's /// time to do some work. -void ScheduleTopDownLive::Schedule() { - BuildSchedGraph(&Pass->getAnalysis()); +void ScheduleTopDownLive::schedule() { + buildSchedGraph(AA); DEBUG(dbgs() << "********** MI Scheduling **********\n"); DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) SUnits[su].dumpAll(this)); + if (ViewMISchedDAGs) viewGraph(); + // Release any successors of the special Entry node. It is currently unused, // but we keep up appearances. releaseSuccessors(&EntrySU); @@ -227,7 +275,7 @@ void ScheduleTopDownLive::Schedule() { releaseNode(&(*I)); } - InsertPos = Begin; + MachineBasicBlock::iterator InsertPos = RegionBegin; while (SUnit *SU = pickNode()) { DEBUG(dbgs() << "*** Scheduling Instruction:\n"; SU->dump(this)); @@ -237,109 +285,47 @@ void ScheduleTopDownLive::Schedule() { ++InsertPos; else { BB->splice(InsertPos, BB, MI); - if (Begin == InsertPos) - Begin = MI; + LIS->handleMove(MI); + if (RegionBegin == InsertPos) + RegionBegin = MI; } - // TODO: Update live intervals. - // Release dependent instructions for scheduling. releaseSuccessors(SU); } } -bool MachineScheduler::runOnMachineFunction(MachineFunction &mf) { - // Initialize the context of the pass. - MF = &mf; - MLI = &getAnalysis(); - MDT = &getAnalysis(); - TII = MF->getTarget().getInstrInfo(); - - // Select the scheduler, or set the default. - MachineSchedRegistry::ScheduleDAGCtor Ctor = - MachineSchedRegistry::getDefault(); - if (!Ctor) { - Ctor = MachineSchedOpt; - MachineSchedRegistry::setDefault(Ctor); - } - // Instantiate the selected scheduler. - OwningPtr Scheduler(Ctor(this)); - - // Visit all machine basic blocks. - for (MachineFunction::iterator MBB = MF->begin(), MBBEnd = MF->end(); - MBB != MBBEnd; ++MBB) { - - // Break the block into scheduling regions [I, RegionEnd), and schedule each - // region as soon as it is discovered. - unsigned RemainingCount = MBB->size(); - for(MachineBasicBlock::iterator RegionEnd = MBB->end(); - RegionEnd != MBB->begin();) { - // The next region starts above the previous region. Look backward in the - // instruction stream until we find the nearest boundary. - MachineBasicBlock::iterator I = RegionEnd; - for(;I != MBB->begin(); --I, --RemainingCount) { - if (TII->isSchedulingBoundary(llvm::prior(I), MBB, *MF)) - break; - } - if (I == RegionEnd) { - // Skip empty scheduling regions. - RegionEnd = llvm::prior(RegionEnd); - --RemainingCount; - continue; - } - // Skip regions with one instruction. - if (I == llvm::prior(RegionEnd)) { - RegionEnd = llvm::prior(RegionEnd); - continue; - } - DEBUG(dbgs() << "MachineScheduling " << MF->getFunction()->getName() - << ":BB#" << MBB->getNumber() << "\n From: " << *I << " To: " - << *RegionEnd << " Remaining: " << RemainingCount << "\n"); - - // Inform ScheduleDAGInstrs of the region being scheduled. It calls back - // to our Schedule() method. - Scheduler->Run(MBB, I, RegionEnd, MBB->size()); - RegionEnd = Scheduler->Begin; - } - assert(RemainingCount == 0 && "Instruction count mismatch!"); - } - return true; -} - -void MachineScheduler::print(raw_ostream &O, const Module* m) const { - // unimplemented -} - //===----------------------------------------------------------------------===// -// Placeholder for extending the machine instruction scheduler. +// Placeholder for the default machine instruction scheduler. //===----------------------------------------------------------------------===// namespace { -class DefaultMachineScheduler : public ScheduleDAGInstrs { - MachineScheduler *Pass; +class CommonMachineScheduler : public ScheduleDAGInstrs { + AliasAnalysis *AA; public: - DefaultMachineScheduler(MachineScheduler *P): - ScheduleDAGInstrs(*P->MF, *P->MLI, *P->MDT, /*IsPostRA=*/false), Pass(P) {} + CommonMachineScheduler(MachineSchedContext *C): + ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS), + AA(C->AA) {} - /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's + /// schedule - This is called back from ScheduleDAGInstrs::Run() when it's /// time to do some work. - void Schedule(); + void schedule(); }; } // namespace -static ScheduleDAGInstrs *createDefaultMachineSched(MachineScheduler *P) { - return new DefaultMachineScheduler(P); +/// The common machine scheduler will be used as the default scheduler if the +/// target does not set a default. +static ScheduleDAGInstrs *createCommonMachineSched(MachineSchedContext *C) { + return new CommonMachineScheduler(C); } static MachineSchedRegistry -SchedDefaultRegistry("default", "Activate the scheduler pass, " - "but don't reorder instructions", - createDefaultMachineSched); - +SchedCommonRegistry("common", "Use the target's default scheduler choice.", + createCommonMachineSched); /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's /// time to do some work. -void DefaultMachineScheduler::Schedule() { - BuildSchedGraph(&Pass->getAnalysis()); +void CommonMachineScheduler::schedule() { + buildSchedGraph(AA); DEBUG(dbgs() << "********** MI Scheduling **********\n"); DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) @@ -357,15 +343,14 @@ void DefaultMachineScheduler::Schedule() { #ifndef NDEBUG namespace { -// Nodes with a higher number have lower priority. This way we attempt to +// Nodes with a higher number have higher priority. This way we attempt to // schedule the latest instructions earliest. // // TODO: Relies on the property of the BuildSchedGraph that results in SUnits -// being ordered in sequence bottom-up. This will be formalized, probably be -// constructing SUnits in a prepass. +// being ordered in sequence top-down. struct ShuffleSUnitOrder { bool operator()(SUnit *A, SUnit *B) const { - return A->NodeNum > B->NodeNum; + return A->NodeNum < B->NodeNum; } }; @@ -373,8 +358,8 @@ struct ShuffleSUnitOrder { class InstructionShuffler : public ScheduleTopDownLive { std::priority_queue, ShuffleSUnitOrder> Queue; public: - InstructionShuffler(MachineScheduler *P): - ScheduleTopDownLive(P) {} + InstructionShuffler(MachineSchedContext *C): + ScheduleTopDownLive(C) {} /// ScheduleTopDownLive Interface @@ -391,8 +376,8 @@ public: }; } // namespace -static ScheduleDAGInstrs *createInstructionShuffler(MachineScheduler *P) { - return new InstructionShuffler(P); +static ScheduleDAGInstrs *createInstructionShuffler(MachineSchedContext *C) { + return new InstructionShuffler(C); } static MachineSchedRegistry ShufflerRegistry("shuffle", "Shuffle machine instructions",