X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FCodeGen%2FMachineScheduler.cpp;h=4f27274796b472568be26827334770eaecc1ca28;hp=e6ca0e847a3b4b42410fb833641ff6734e1c9d55;hb=68675c6c5b173021807e4e12cd250eeba63f6d0d;hpb=5e920d7c83c20474fc3470209869978628ccf8da diff --git a/lib/CodeGen/MachineScheduler.cpp b/lib/CodeGen/MachineScheduler.cpp index e6ca0e847a3..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" @@ -27,22 +26,27 @@ #include "llvm/Support/raw_ostream.h" #include "llvm/ADT/OwningPtr.h" +#include + 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 { -/// MachineSchedulerPass runs after coalescing and before register allocation. -class MachineSchedulerPass : public MachineFunctionPass { +/// MachineScheduler runs after coalescing and before register allocation. +class MachineScheduler : public MachineSchedContext, + public MachineFunctionPass { public: - MachineFunction *MF; - const TargetInstrInfo *TII; - const MachineLoopInfo *MLI; - const MachineDominatorTree *MDT; - - MachineSchedulerPass(); + MachineScheduler(); virtual void getAnalysisUsage(AnalysisUsage &AU) const; @@ -56,148 +60,79 @@ public: }; } // namespace -char MachineSchedulerPass::ID = 0; +char MachineScheduler::ID = 0; -char &llvm::MachineSchedulerPassID = MachineSchedulerPass::ID; +char &llvm::MachineSchedulerID = MachineScheduler::ID; -INITIALIZE_PASS_BEGIN(MachineSchedulerPass, "misched", +INITIALIZE_PASS_BEGIN(MachineScheduler, "misched", "Machine Instruction Scheduler", false, false) 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(MachineSchedulerPass, "misched", +INITIALIZE_PASS_END(MachineScheduler, "misched", "Machine Instruction Scheduler", false, false) -MachineSchedulerPass::MachineSchedulerPass() -: MachineFunctionPass(ID), MF(0), MLI(0), MDT(0) { - initializeMachineSchedulerPassPass(*PassRegistry::getPassRegistry()); +MachineScheduler::MachineScheduler() +: MachineFunctionPass(ID) { + initializeMachineSchedulerPass(*PassRegistry::getPassRegistry()); } -void MachineSchedulerPass::getAnalysisUsage(AnalysisUsage &AU) const { +void MachineScheduler::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesCFG(); 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)(MachineSchedulerPass *); - - // 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(MachineSchedulerPass *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")); -//===----------------------------------------------------------------------===// -// Machine Instruction Scheduling Implementation -//===----------------------------------------------------------------------===// - -namespace { -/// MachineScheduler is an implementation of ScheduleDAGInstrs that schedules -/// machine instructions while updating LiveIntervals. -class MachineScheduler : public ScheduleDAGInstrs { - MachineSchedulerPass *Pass; -public: - MachineScheduler(MachineSchedulerPass *P): - ScheduleDAGInstrs(*P->MF, *P->MLI, *P->MDT, /*IsPostRA=*/false), Pass(P) {} - - /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's - /// time to do some work. - virtual void Schedule(); -}; -} // namespace - -static ScheduleDAGInstrs *createDefaultMachineSched(MachineSchedulerPass *P) { - return new MachineScheduler(P); -} static MachineSchedRegistry -SchedDefaultRegistry("default", "Activate the scheduler pass, " - "but don't reorder instructions", - createDefaultMachineSched); +SchedDefaultRegistry("default", "Use the target's default scheduler choice.", + useDefaultMachineSched); -/// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's -/// time to do some work. -void MachineScheduler::Schedule() { - BuildSchedGraph(&Pass->getAnalysis()); +/// 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); - DEBUG(dbgs() << "********** MI Scheduling **********\n"); - DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) - SUnits[su].dumpAll(this)); - - // TODO: Put interesting things here. -} - -bool MachineSchedulerPass::runOnMachineFunction(MachineFunction &mf) { +bool MachineScheduler::runOnMachineFunction(MachineFunction &mf) { // Initialize the context of the pass. MF = &mf; MLI = &getAnalysis(); MDT = &getAnalysis(); - TII = MF->getTarget().getInstrInfo(); + PassConfig = &getAnalysis(); + AA = &getAnalysis(); + + LIS = &getAnalysis(); + const TargetInstrInfo *TII = MF->getTarget().getInstrInfo(); // Select the scheduler, or set the default. - MachineSchedRegistry::ScheduleDAGCtor Ctor = - MachineSchedRegistry::getDefault(); - if (!Ctor) { - Ctor = MachineSchedOpt; - MachineSchedRegistry::setDefault(Ctor); + 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)); @@ -211,59 +146,238 @@ bool MachineSchedulerPass::runOnMachineFunction(MachineFunction &mf) { 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) { + 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)) { - // Skip empty or single instruction scheduling regions. 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: " - << *RegionEnd << " Remaining: " << RemainingCount << "\n"); + << ":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(); - // Inform ScheduleDAGInstrs of the region being scheduler. It calls back - // to our Schedule() method. - Scheduler->Run(MBB, I, RegionEnd, MBB->size()); - RegionEnd = I; + // 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 MachineSchedulerPass::print(raw_ostream &O, const Module* m) const { +void MachineScheduler::print(raw_ostream &O, const Module* m) const { // unimplemented } +//===----------------------------------------------------------------------===// +// ScheduleTopeDownLive - Base class for basic top-down scheduling with +// LiveIntervals preservation. +// ===----------------------------------------------------------------------===// + +namespace { +/// ScheduleTopDownLive is an implementation of ScheduleDAGInstrs that schedules +/// machine instructions while updating LiveIntervals. +class ScheduleTopDownLive : public ScheduleDAGInstrs { + AliasAnalysis *AA; +public: + ScheduleTopDownLive(MachineSchedContext *C): + ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS), + AA(C->AA) {} + + /// ScheduleDAGInstrs interface. + void schedule(); + + /// Interface implemented by the selected top-down liveinterval scheduler. + /// + /// Pick the next node to schedule, or return NULL. + virtual SUnit *pickNode() = 0; + + /// When all preceeding dependencies have been resolved, free this node for + /// scheduling. + virtual void releaseNode(SUnit *SU) = 0; + +protected: + void releaseSucc(SUnit *SU, SDep *SuccEdge); + void releaseSuccessors(SUnit *SU); +}; +} // namespace + +/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. When +/// NumPredsLeft reaches zero, release the successor node. +void ScheduleTopDownLive::releaseSucc(SUnit *SU, SDep *SuccEdge) { + SUnit *SuccSU = SuccEdge->getSUnit(); + +#ifndef NDEBUG + if (SuccSU->NumPredsLeft == 0) { + dbgs() << "*** Scheduling failed! ***\n"; + SuccSU->dump(this); + dbgs() << " has been released too many times!\n"; + llvm_unreachable(0); + } +#endif + --SuccSU->NumPredsLeft; + if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) + releaseNode(SuccSU); +} + +/// releaseSuccessors - Call releaseSucc on each of SU's successors. +void ScheduleTopDownLive::releaseSuccessors(SUnit *SU) { + for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); + I != E; ++I) { + releaseSucc(SU, &*I); + } +} + +/// schedule - This is called back from ScheduleDAGInstrs::Run() when it's +/// time to do some work. +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); + + // Release all DAG roots for scheduling. + for (std::vector::iterator I = SUnits.begin(), E = SUnits.end(); + I != E; ++I) { + // A SUnit is ready to schedule if it has no predecessors. + if (I->Preds.empty()) + releaseNode(&(*I)); + } + + MachineBasicBlock::iterator InsertPos = RegionBegin; + while (SUnit *SU = pickNode()) { + DEBUG(dbgs() << "*** Scheduling Instruction:\n"; SU->dump(this)); + + // Move the instruction to its new location in the instruction stream. + MachineInstr *MI = SU->getInstr(); + if (&*InsertPos == MI) + ++InsertPos; + else { + BB->splice(InsertPos, BB, MI); + LIS->handleMove(MI); + if (RegionBegin == InsertPos) + RegionBegin = MI; + } + + // Release dependent instructions for scheduling. + releaseSuccessors(SU); + } +} + +//===----------------------------------------------------------------------===// +// Placeholder for the default machine instruction scheduler. +//===----------------------------------------------------------------------===// + +namespace { +class CommonMachineScheduler : public ScheduleDAGInstrs { + AliasAnalysis *AA; +public: + 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 + /// time to do some work. + void schedule(); +}; +} // namespace + +/// 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 +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 CommonMachineScheduler::schedule() { + buildSchedGraph(AA); + + DEBUG(dbgs() << "********** MI Scheduling **********\n"); + DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) + SUnits[su].dumpAll(this)); + + // TODO: Put interesting things here. + // + // When this is fully implemented, it will become a subclass of + // ScheduleTopDownLive. So this driver will disappear. +} + //===----------------------------------------------------------------------===// // Machine Instruction Shuffler for Correctness Testing //===----------------------------------------------------------------------===// #ifndef NDEBUG namespace { +// 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 top-down. +struct ShuffleSUnitOrder { + bool operator()(SUnit *A, SUnit *B) const { + return A->NodeNum < B->NodeNum; + } +}; + /// Reorder instructions as much as possible. -class InstructionShuffler : public ScheduleDAGInstrs { - MachineSchedulerPass *Pass; +class InstructionShuffler : public ScheduleTopDownLive { + std::priority_queue, ShuffleSUnitOrder> Queue; public: - InstructionShuffler(MachineSchedulerPass *P): - ScheduleDAGInstrs(*P->MF, *P->MLI, *P->MDT, /*IsPostRA=*/false), Pass(P) {} + InstructionShuffler(MachineSchedContext *C): + ScheduleTopDownLive(C) {} - /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's - /// time to do some work. - virtual void Schedule() { - llvm_unreachable("unimplemented"); + /// ScheduleTopDownLive Interface + + virtual SUnit *pickNode() { + if (Queue.empty()) return NULL; + SUnit *SU = Queue.top(); + Queue.pop(); + return SU; + } + + virtual void releaseNode(SUnit *SU) { + Queue.push(SU); } }; } // namespace -static ScheduleDAGInstrs *createInstructionShuffler(MachineSchedulerPass *P) { - return new InstructionShuffler(P); +static ScheduleDAGInstrs *createInstructionShuffler(MachineSchedContext *C) { + return new InstructionShuffler(C); } static MachineSchedRegistry ShufflerRegistry("shuffle", "Shuffle machine instructions",