#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"
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 {
/// 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;
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());
}
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)(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<MachineSchedRegistry::ScheduleDAGCtor, false,
RegisterPassParser<MachineSchedRegistry> >
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<MachineLoopInfo>();
+ MDT = &getAnalysis<MachineDominatorTree>();
+ 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 = 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));
+
+ // 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.
///
}
}
-/// 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<AliasAnalysis>());
+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);
releaseNode(&(*I));
}
- InsertPos = Begin;
+ MachineBasicBlock::iterator InsertPos = RegionBegin;
while (SUnit *SU = pickNode()) {
DEBUG(dbgs() << "*** Scheduling Instruction:\n"; SU->dump(this));
++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<MachineLoopInfo>();
- MDT = &getAnalysis<MachineDominatorTree>();
- 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<ScheduleDAGInstrs> 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<AliasAnalysis>());
+void CommonMachineScheduler::schedule() {
+ buildSchedGraph(AA);
DEBUG(dbgs() << "********** MI Scheduling **********\n");
DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
#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;
}
};
class InstructionShuffler : public ScheduleTopDownLive {
std::priority_queue<SUnit*, std::vector<SUnit*>, ShuffleSUnitOrder> Queue;
public:
- InstructionShuffler(MachineScheduler *P):
- ScheduleTopDownLive(P) {}
+ InstructionShuffler(MachineSchedContext *C):
+ ScheduleTopDownLive(C) {}
/// ScheduleTopDownLive Interface
};
} // 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",
projects / oota-llvm.git / blobdiff