#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"
#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/OwningPtr.h"
+#include <queue>
+
using namespace llvm;
+#ifndef NDEBUG
+static cl::opt<bool> 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;
};
} // 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<MachineLoopInfo>();
AU.addRequired<AliasAnalysis>();
- AU.addPreserved<AliasAnalysis>();
+ AU.addRequired<TargetPassConfig>();
AU.addRequired<SlotIndexes>();
AU.addPreserved<SlotIndexes>();
AU.addRequired<LiveIntervals>();
AU.addPreserved<LiveIntervals>();
- AU.addRequired<LiveDebugVariables>();
- AU.addPreserved<LiveDebugVariables>();
- 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<MachineSchedRegistry::ScheduleDAGCtor, false,
RegisterPassParser<MachineSchedRegistry> >
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<AliasAnalysis>());
+/// 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<MachineLoopInfo>();
MDT = &getAnalysis<MachineDominatorTree>();
- TII = MF->getTarget().getInstrInfo();
+ PassConfig = &getAnalysis<TargetPassConfig>();
+ AA = &getAnalysis<AliasAnalysis>();
+
+ LIS = &getAnalysis<LiveIntervals>();
+ 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<ScheduleDAGInstrs> Scheduler(Ctor(this));
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<SUnit>::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<SUnit*, std::vector<SUnit*>, 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",