diff options
| -rw-r--r-- | include/llvm/CodeGen/MachineScheduler.h | 218 | ||||
| -rw-r--r-- | lib/CodeGen/MachineScheduler.cpp | 356 | ||||
| -rw-r--r-- | lib/Target/Hexagon/HexagonMachineScheduler.cpp | 324 | ||||
| -rw-r--r-- | lib/Target/Hexagon/HexagonMachineScheduler.h | 204 |
4 files changed, 336 insertions, 766 deletions
diff --git a/include/llvm/CodeGen/MachineScheduler.h b/include/llvm/CodeGen/MachineScheduler.h index 8da2045ad0..f87c2a5c40 100644 --- a/include/llvm/CodeGen/MachineScheduler.h +++ b/include/llvm/CodeGen/MachineScheduler.h @@ -28,9 +28,16 @@ #define MACHINESCHEDULER_H #include "llvm/CodeGen/MachinePassRegistry.h" +#include "llvm/CodeGen/RegisterPressure.h" +#include "llvm/CodeGen/ScheduleDAGInstrs.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/MC/MCInstrItineraries.h" namespace llvm { +extern cl::opt<bool> ForceTopDown; +extern cl::opt<bool> ForceBottomUp; + class AliasAnalysis; class LiveIntervals; class MachineDominatorTree; @@ -93,6 +100,217 @@ public: } }; +class ScheduleDAGMI; + +/// MachineSchedStrategy - Interface to the scheduling algorithm used by +/// ScheduleDAGMI. +class MachineSchedStrategy { +public: + virtual ~MachineSchedStrategy() {} + + /// Initialize the strategy after building the DAG for a new region. + virtual void initialize(ScheduleDAGMI *DAG) = 0; + + /// Pick the next node to schedule, or return NULL. Set IsTopNode to true to + /// schedule the node at the top of the unscheduled region. Otherwise it will + /// be scheduled at the bottom. + virtual SUnit *pickNode(bool &IsTopNode) = 0; + + /// Notify MachineSchedStrategy that ScheduleDAGMI has scheduled an + /// instruction and updated scheduled/remaining flags in the DAG nodes. + virtual void schedNode(SUnit *SU, bool IsTopNode) = 0; + + /// When all predecessor dependencies have been resolved, free this node for + /// top-down scheduling. + virtual void releaseTopNode(SUnit *SU) = 0; + /// When all successor dependencies have been resolved, free this node for + /// bottom-up scheduling. + virtual void releaseBottomNode(SUnit *SU) = 0; +}; + +/// ReadyQueue encapsulates vector of "ready" SUnits with basic convenience +/// methods for pushing and removing nodes. ReadyQueue's are uniquely identified +/// by an ID. SUnit::NodeQueueId is a mask of the ReadyQueues the SUnit is in. +/// +/// This is a convenience class that may be used by implementations of +/// MachineSchedStrategy. +class ReadyQueue { + unsigned ID; + std::string Name; + std::vector<SUnit*> Queue; + +public: + ReadyQueue(unsigned id, const Twine &name): ID(id), Name(name.str()) {} + + unsigned getID() const { return ID; } + + StringRef getName() const { return Name; } + + // SU is in this queue if it's NodeQueueID is a superset of this ID. + bool isInQueue(SUnit *SU) const { return (SU->NodeQueueId & ID); } + + bool empty() const { return Queue.empty(); } + + unsigned size() const { return Queue.size(); } + + typedef std::vector<SUnit*>::iterator iterator; + + iterator begin() { return Queue.begin(); } + + iterator end() { return Queue.end(); } + + iterator find(SUnit *SU) { + return std::find(Queue.begin(), Queue.end(), SU); + } + + void push(SUnit *SU) { + Queue.push_back(SU); + SU->NodeQueueId |= ID; + } + + void remove(iterator I) { + (*I)->NodeQueueId &= ~ID; + *I = Queue.back(); + Queue.pop_back(); + } + +#ifndef NDEBUG + void dump(); +#endif +}; + +/// ScheduleDAGMI is an implementation of ScheduleDAGInstrs that schedules +/// machine instructions while updating LiveIntervals and tracking regpressure. +class ScheduleDAGMI : public ScheduleDAGInstrs { +protected: + AliasAnalysis *AA; + RegisterClassInfo *RegClassInfo; + MachineSchedStrategy *SchedImpl; + + MachineBasicBlock::iterator LiveRegionEnd; + + /// Register pressure in this region computed by buildSchedGraph. + IntervalPressure RegPressure; + RegPressureTracker RPTracker; + + /// List of pressure sets that exceed the target's pressure limit before + /// scheduling, listed in increasing set ID order. Each pressure set is paired + /// with its max pressure in the currently scheduled regions. + std::vector<PressureElement> RegionCriticalPSets; + + /// The top of the unscheduled zone. + MachineBasicBlock::iterator CurrentTop; + IntervalPressure TopPressure; + RegPressureTracker TopRPTracker; + + /// The bottom of the unscheduled zone. + MachineBasicBlock::iterator CurrentBottom; + IntervalPressure BotPressure; + RegPressureTracker BotRPTracker; + +#ifndef NDEBUG + /// The number of instructions scheduled so far. Used to cut off the + /// scheduler at the point determined by misched-cutoff. + unsigned NumInstrsScheduled; +#endif + +public: + ScheduleDAGMI(MachineSchedContext *C, MachineSchedStrategy *S): + ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS), + AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S), + RPTracker(RegPressure), CurrentTop(), TopRPTracker(TopPressure), + CurrentBottom(), BotRPTracker(BotPressure) { +#ifndef NDEBUG + NumInstrsScheduled = 0; +#endif + } + + virtual ~ScheduleDAGMI() { + delete SchedImpl; + } + + MachineBasicBlock::iterator top() const { return CurrentTop; } + MachineBasicBlock::iterator bottom() const { return CurrentBottom; } + + /// Implement the ScheduleDAGInstrs interface for handling the next scheduling + /// region. This covers all instructions in a block, while schedule() may only + /// cover a subset. + void enterRegion(MachineBasicBlock *bb, + MachineBasicBlock::iterator begin, + MachineBasicBlock::iterator end, + unsigned endcount); + + + /// Implement ScheduleDAGInstrs interface for scheduling a sequence of + /// reorderable instructions. + virtual void schedule(); + + /// Get current register pressure for the top scheduled instructions. + const IntervalPressure &getTopPressure() const { return TopPressure; } + const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; } + + /// Get current register pressure for the bottom scheduled instructions. + const IntervalPressure &getBotPressure() const { return BotPressure; } + const RegPressureTracker &getBotRPTracker() const { return BotRPTracker; } + + /// Get register pressure for the entire scheduling region before scheduling. + const IntervalPressure &getRegPressure() const { return RegPressure; } + + const std::vector<PressureElement> &getRegionCriticalPSets() const { + return RegionCriticalPSets; + } + + /// getIssueWidth - Return the max instructions per scheduling group. + unsigned getIssueWidth() const { + return (InstrItins && InstrItins->SchedModel) + ? InstrItins->SchedModel->IssueWidth : 1; + } + + /// getNumMicroOps - Return the number of issue slots required for this MI. + unsigned getNumMicroOps(MachineInstr *MI) const { + if (!InstrItins) return 1; + int UOps = InstrItins->getNumMicroOps(MI->getDesc().getSchedClass()); + return (UOps >= 0) ? UOps : TII->getNumMicroOps(InstrItins, MI); + } + +protected: + // Top-Level entry points for the schedule() driver... + + /// Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking + /// enabled. This sets up three trackers. RPTracker will cover the entire DAG + /// region, TopTracker and BottomTracker will be initialized to the top and + /// bottom of the DAG region without covereing any unscheduled instruction. + void buildDAGWithRegPressure(); + + /// Identify DAG roots and setup scheduler queues. + void initQueues(); + + /// Move an instruction and update register pressure. + void scheduleMI(SUnit *SU, bool IsTopNode); + + /// Update scheduler DAG and queues after scheduling an instruction. + void updateQueues(SUnit *SU, bool IsTopNode); + + /// Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues. + void placeDebugValues(); + + // Lesser helpers... + + void initRegPressure(); + + void updateScheduledPressure(std::vector<unsigned> NewMaxPressure); + + void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos); + bool checkSchedLimit(); + + void releaseRoots(); + + void releaseSucc(SUnit *SU, SDep *SuccEdge); + void releaseSuccessors(SUnit *SU); + void releasePred(SUnit *SU, SDep *PredEdge); + void releasePredecessors(SUnit *SU); +}; + } // namespace llvm #endif diff --git a/lib/CodeGen/MachineScheduler.cpp b/lib/CodeGen/MachineScheduler.cpp index 4704daef02..e36c7d4315 100644 --- a/lib/CodeGen/MachineScheduler.cpp +++ b/lib/CodeGen/MachineScheduler.cpp @@ -18,11 +18,7 @@ #include "llvm/CodeGen/MachineScheduler.h" #include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/RegisterClassInfo.h" -#include "llvm/CodeGen/RegisterPressure.h" -#include "llvm/CodeGen/ScheduleDAGInstrs.h" #include "llvm/CodeGen/ScheduleHazardRecognizer.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "llvm/MC/MCInstrItineraries.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" @@ -35,10 +31,12 @@ using namespace llvm; -static cl::opt<bool> ForceTopDown("misched-topdown", cl::Hidden, - cl::desc("Force top-down list scheduling")); -static cl::opt<bool> ForceBottomUp("misched-bottomup", cl::Hidden, - cl::desc("Force bottom-up list scheduling")); +namespace llvm { +cl::opt<bool> ForceTopDown("misched-topdown", cl::Hidden, + cl::desc("Force top-down list scheduling")); +cl::opt<bool> ForceBottomUp("misched-bottomup", cl::Hidden, + cl::desc("Force bottom-up list scheduling")); +} #ifndef NDEBUG static cl::opt<bool> ViewMISchedDAGs("view-misched-dags", cl::Hidden, @@ -281,157 +279,20 @@ void MachineScheduler::print(raw_ostream &O, const Module* m) const { // unimplemented } -//===----------------------------------------------------------------------===// -// MachineSchedStrategy - Interface to a machine scheduling algorithm. -//===----------------------------------------------------------------------===// - -namespace { -class ScheduleDAGMI; - -/// MachineSchedStrategy - Interface used by ScheduleDAGMI to drive the selected -/// scheduling algorithm. -/// -/// If this works well and targets wish to reuse ScheduleDAGMI, we may expose it -/// in ScheduleDAGInstrs.h -class MachineSchedStrategy { -public: - virtual ~MachineSchedStrategy() {} - - /// Initialize the strategy after building the DAG for a new region. - virtual void initialize(ScheduleDAGMI *DAG) = 0; - - /// Pick the next node to schedule, or return NULL. Set IsTopNode to true to - /// schedule the node at the top of the unscheduled region. Otherwise it will - /// be scheduled at the bottom. - virtual SUnit *pickNode(bool &IsTopNode) = 0; - - /// Notify MachineSchedStrategy that ScheduleDAGMI has scheduled a node. - virtual void schedNode(SUnit *SU, bool IsTopNode) = 0; - - /// When all predecessor dependencies have been resolved, free this node for - /// top-down scheduling. - virtual void releaseTopNode(SUnit *SU) = 0; - /// When all successor dependencies have been resolved, free this node for - /// bottom-up scheduling. - virtual void releaseBottomNode(SUnit *SU) = 0; -}; -} // namespace +#ifndef NDEBUG +void ReadyQueue::dump() { + dbgs() << Name << ": "; + for (unsigned i = 0, e = Queue.size(); i < e; ++i) + dbgs() << Queue[i]->NodeNum << " "; + dbgs() << "\n"; +} +#endif //===----------------------------------------------------------------------===// // ScheduleDAGMI - Base class for MachineInstr scheduling with LiveIntervals // preservation. //===----------------------------------------------------------------------===// -namespace { -/// ScheduleDAGMI is an implementation of ScheduleDAGInstrs that schedules -/// machine instructions while updating LiveIntervals. -class ScheduleDAGMI : public ScheduleDAGInstrs { - AliasAnalysis *AA; - RegisterClassInfo *RegClassInfo; - MachineSchedStrategy *SchedImpl; - - MachineBasicBlock::iterator LiveRegionEnd; - - /// Register pressure in this region computed by buildSchedGraph. - IntervalPressure RegPressure; - RegPressureTracker RPTracker; - - /// List of pressure sets that exceed the target's pressure limit before - /// scheduling, listed in increasing set ID order. Each pressure set is paired - /// with its max pressure in the currently scheduled regions. - std::vector<PressureElement> RegionCriticalPSets; - - /// The top of the unscheduled zone. - MachineBasicBlock::iterator CurrentTop; - IntervalPressure TopPressure; - RegPressureTracker TopRPTracker; - - /// The bottom of the unscheduled zone. - MachineBasicBlock::iterator CurrentBottom; - IntervalPressure BotPressure; - RegPressureTracker BotRPTracker; - -#ifndef NDEBUG - /// The number of instructions scheduled so far. Used to cut off the - /// scheduler at the point determined by misched-cutoff. - unsigned NumInstrsScheduled; -#endif -public: - ScheduleDAGMI(MachineSchedContext *C, MachineSchedStrategy *S): - ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS), - AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S), - RPTracker(RegPressure), CurrentTop(), TopRPTracker(TopPressure), - CurrentBottom(), BotRPTracker(BotPressure) { -#ifndef NDEBUG - NumInstrsScheduled = 0; -#endif - } - - ~ScheduleDAGMI() { - delete SchedImpl; - } - - MachineBasicBlock::iterator top() const { return CurrentTop; } - MachineBasicBlock::iterator bottom() const { return CurrentBottom; } - - /// Implement the ScheduleDAGInstrs interface for handling the next scheduling - /// region. This covers all instructions in a block, while schedule() may only - /// cover a subset. - void enterRegion(MachineBasicBlock *bb, - MachineBasicBlock::iterator begin, - MachineBasicBlock::iterator end, - unsigned endcount); - - /// Implement ScheduleDAGInstrs interface for scheduling a sequence of - /// reorderable instructions. - void schedule(); - - /// Get current register pressure for the top scheduled instructions. - const IntervalPressure &getTopPressure() const { return TopPressure; } - const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; } - - /// Get current register pressure for the bottom scheduled instructions. - const IntervalPressure &getBotPressure() const { return BotPressure; } - const RegPressureTracker &getBotRPTracker() const { return BotRPTracker; } - - /// Get register pressure for the entire scheduling region before scheduling. - const IntervalPressure &getRegPressure() const { return RegPressure; } - - const std::vector<PressureElement> &getRegionCriticalPSets() const { - return RegionCriticalPSets; - } - - /// getIssueWidth - Return the max instructions per scheduling group. - unsigned getIssueWidth() const { - return (InstrItins && InstrItins->SchedModel) - ? InstrItins->SchedModel->IssueWidth : 1; - } - - /// getNumMicroOps - Return the number of issue slots required for this MI. - unsigned getNumMicroOps(MachineInstr *MI) const { - if (!InstrItins) return 1; - int UOps = InstrItins->getNumMicroOps(MI->getDesc().getSchedClass()); - return (UOps >= 0) ? UOps : TII->getNumMicroOps(InstrItins, MI); - } - -protected: - void initRegPressure(); - void updateScheduledPressure(std::vector<unsigned> NewMaxPressure); - - void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos); - bool checkSchedLimit(); - - void releaseRoots(); - - void releaseSucc(SUnit *SU, SDep *SuccEdge); - void releaseSuccessors(SUnit *SU); - void releasePred(SUnit *SU, SDep *PredEdge); - void releasePredecessors(SUnit *SU); - - void placeDebugValues(); -}; -} // namespace - /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. When /// NumPredsLeft reaches zero, release the successor node. /// @@ -565,6 +426,9 @@ void ScheduleDAGMI::initRegPressure() { std::vector<unsigned> RegionPressure = RPTracker.getPressure().MaxSetPressure; for (unsigned i = 0, e = RegionPressure.size(); i < e; ++i) { unsigned Limit = TRI->getRegPressureSetLimit(i); + DEBUG(dbgs() << TRI->getRegPressureSetName(i) + << "Limit " << Limit + << " Actual " << RegionPressure[i] << "\n"); if (RegionPressure[i] > Limit) RegionCriticalPSets.push_back(PressureElement(i, 0)); } @@ -610,7 +474,39 @@ void ScheduleDAGMI::releaseRoots() { /// schedule - Called back from MachineScheduler::runOnMachineFunction /// after setting up the current scheduling region. [RegionBegin, RegionEnd) /// only includes instructions that have DAG nodes, not scheduling boundaries. +/// +/// This is a skeletal driver, with all the functionality pushed into helpers, +/// so that it can be easilly extended by experimental schedulers. Generally, +/// implementing MachineSchedStrategy should be sufficient to implement a new +/// scheduling algorithm. However, if a scheduler further subclasses +/// ScheduleDAGMI then it will want to override this virtual method in order to +/// update any specialized state. void ScheduleDAGMI::schedule() { + buildDAGWithRegPressure(); + + DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) + SUnits[su].dumpAll(this)); + + if (ViewMISchedDAGs) viewGraph(); + + initQueues(); + + bool IsTopNode = false; + while (SUnit *SU = SchedImpl->pickNode(IsTopNode)) { + if (!checkSchedLimit()) + break; + + scheduleMI(SU, IsTopNode); + + updateQueues(SU, IsTopNode); + } + assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone."); + + placeDebugValues(); +} + +/// Build the DAG and setup three register pressure trackers. +void ScheduleDAGMI::buildDAGWithRegPressure() { // Initialize the register pressure tracker used by buildSchedGraph. RPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd); @@ -620,15 +516,15 @@ void ScheduleDAGMI::schedule() { // Build the DAG, and compute current register pressure. buildSchedGraph(AA, &RPTracker); + if (ViewMISchedDAGs) viewGraph(); // Initialize top/bottom trackers after computing region pressure. initRegPressure(); +} - DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) - SUnits[su].dumpAll(this)); - - if (ViewMISchedDAGs) viewGraph(); - +/// Identify DAG roots and setup scheduler queues. +void ScheduleDAGMI::initQueues() { + // Initialize the strategy before modifying the DAG. SchedImpl->initialize(this); // Release edges from the special Entry node or to the special Exit node. @@ -640,59 +536,60 @@ void ScheduleDAGMI::schedule() { CurrentTop = nextIfDebug(RegionBegin, RegionEnd); CurrentBottom = RegionEnd; - bool IsTopNode = false; - while (SUnit *SU = SchedImpl->pickNode(IsTopNode)) { - if (!checkSchedLimit()) - break; - - // Move the instruction to its new location in the instruction stream. - MachineInstr *MI = SU->getInstr(); - - if (IsTopNode) { - assert(SU->isTopReady() && "node still has unscheduled dependencies"); - if (&*CurrentTop == MI) - CurrentTop = nextIfDebug(++CurrentTop, CurrentBottom); - else { - moveInstruction(MI, CurrentTop); - TopRPTracker.setPos(MI); - } +} - // Update top scheduled pressure. - TopRPTracker.advance(); - assert(TopRPTracker.getPos() == CurrentTop && "out of sync"); - updateScheduledPressure(TopRPTracker.getPressure().MaxSetPressure); +/// Move an instruction and update register pressure. +void ScheduleDAGMI::scheduleMI(SUnit *SU, bool IsTopNode) { + // Move the instruction to its new location in the instruction stream. + MachineInstr *MI = SU->getInstr(); - // Release dependent instructions for scheduling. - releaseSuccessors(SU); + if (IsTopNode) { + assert(SU->isTopReady() && "node still has unscheduled dependencies"); + if (&*CurrentTop == MI) + CurrentTop = nextIfDebug(++CurrentTop, CurrentBottom); + else { + moveInstruction(MI, CurrentTop); + TopRPTracker.setPos(MI); } + + // Update top scheduled pressure. + TopRPTracker.advance(); + assert(TopRPTracker.getPos() == CurrentTop && "out of sync"); + updateScheduledPressure(TopRPTracker.getPressure().MaxSetPressure); + } + else { + assert(SU->isBottomReady() && "node still has unscheduled dependencies"); + MachineBasicBlock::iterator priorII = + priorNonDebug(CurrentBottom, CurrentTop); + if (&*priorII == MI) + CurrentBottom = priorII; else { - assert(SU->isBottomReady() && "node still has unscheduled dependencies"); - MachineBasicBlock::iterator priorII = - priorNonDebug(CurrentBottom, CurrentTop); - if (&*priorII == MI) - CurrentBottom = priorII; - else { - if (&*CurrentTop == MI) { - CurrentTop = nextIfDebug(++CurrentTop, priorII); - TopRPTracker.setPos(CurrentTop); - } - moveInstruction(MI, CurrentBottom); - CurrentBottom = MI; + if (&*CurrentTop == MI) { + CurrentTop = nextIfDebug(++CurrentTop, priorII); + TopRPTracker.setPos(CurrentTop); } - // Update bottom scheduled pressure. - BotRPTracker.recede(); - assert(BotRPTracker.getPos() == CurrentBottom && "out of sync"); - updateScheduledPressure(BotRPTracker.getPressure().MaxSetPressure); - - // Release dependent instructions for scheduling. - releasePredecessors(SU); + moveInstruction(MI, CurrentBottom); + CurrentBottom = MI; } - SU->isScheduled = true; - SchedImpl->schedNode(SU, IsTopNode); + // Update bottom scheduled pressure. + BotRPTracker.recede(); + assert(BotRPTracker.getPos() == CurrentBottom && "out of sync"); + updateScheduledPressure(BotRPTracker.getPressure().MaxSetPressure); } - assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone."); +} - placeDebugValues(); +/// Update scheduler queues after scheduling an instruction. +void ScheduleDAGMI::updateQueues(SUnit *SU, bool IsTopNode) { + // Release dependent instructions for scheduling. + if (IsTopNode) + releaseSuccessors(SU); + else + releasePredecessors(SU); + + SU->isScheduled = true; + + // Notify the scheduling strategy after updating the DAG. + SchedImpl->schedNode(SU, IsTopNode); } /// Reinsert any remaining debug_values, just like the PostRA scheduler. @@ -721,59 +618,6 @@ void ScheduleDAGMI::placeDebugValues() { //===----------------------------------------------------------------------===// namespace { -/// ReadyQueue encapsulates vector of "ready" SUnits with basic convenience -/// methods for pushing and removing nodes. ReadyQueue's are uniquely identified -/// by an ID. SUnit::NodeQueueId is a mask of the ReadyQueues the SUnit is in. -class ReadyQueue { - unsigned ID; - std::string Name; - std::vector<SUnit*> Queue; - -public: - ReadyQueue(unsigned id, const Twine &name): ID(id), Name(name.str()) {} - - unsigned getID() const { return ID; } - - StringRef getName() const { return Name; } - - // SU is in this queue if it's NodeQueueID is a superset of this ID. - bool isInQueue(SUnit *SU) const { return (SU->NodeQueueId & ID); } - - bool empty() const { return Queue.empty(); } - - unsigned size() const { return Queue.size(); } - - typedef std::vector<SUnit*>::iterator iterator; - - iterator begin() { return Queue.begin(); } - - iterator end() { return Queue.end(); } - - iterator find(SUnit *SU) { - return std::find(Queue.begin(), Queue.end(), SU); - } - - void push(SUnit *SU) { - Queue.push_back(SU); - SU->NodeQueueId |= ID; - } - - void remove(iterator I) { - (*I)->NodeQueueId &= ~ID; - *I = Queue.back(); - Queue.pop_back(); - } - -#ifndef NDEBUG - void dump() { - dbgs() << Name << ": "; - for (unsigned i = 0, e = Queue.size(); i < e; ++i) - dbgs() << Queue[i]->NodeNum << " "; - dbgs() << "\n"; - } -#endif -}; - /// ConvergingScheduler shrinks the unscheduled zone using heuristics to balance /// the schedule. class ConvergingScheduler : public MachineSchedStrategy { diff --git a/lib/Target/Hexagon/HexagonMachineScheduler.cpp b/lib/Target/Hexagon/HexagonMachineScheduler.cpp index b131a8f8d2..838f7b5ed7 100644 --- a/lib/Target/Hexagon/HexagonMachineScheduler.cpp +++ b/lib/Target/Hexagon/HexagonMachineScheduler.cpp @@ -20,203 +20,6 @@ using namespace llvm; -static cl::opt<bool> ForceTopDown("vliw-misched-topdown", cl::Hidden, - cl::desc("Force top-down list scheduling")); -static cl::opt<bool> ForceBottomUp("vliw-misched-bottomup", cl::Hidden, - cl::desc("Force bottom-up list scheduling")); - -#ifndef NDEBUG -static cl::opt<bool> ViewMISchedDAGs("vliw-view-misched-dags", cl::Hidden, - cl::desc("Pop up a window to show MISched dags after they are processed")); - -static cl::opt<unsigned> MISchedCutoff("vliw-misched-cutoff", cl::Hidden, - cl::desc("Stop scheduling after N instructions"), cl::init(~0U)); -#else -static bool ViewMISchedDAGs = false; -#endif // NDEBUG - -/// Decrement this iterator until reaching the top or a non-debug instr. -static MachineBasicBlock::iterator -priorNonDebug(MachineBasicBlock::iterator I, MachineBasicBlock::iterator Beg) { - assert(I != Beg && "reached the top of the region, cannot decrement"); - while (--I != Beg) { - if (!I->isDebugValue()) - break; - } - return I; -} - -/// If this iterator is a debug value, increment until reaching the End or a -/// non-debug instruction. -static MachineBasicBlock::iterator -nextIfDebug(MachineBasicBlock::iterator I, MachineBasicBlock::iterator End) { - for(; I != End; ++I) { - if (!I->isDebugValue()) - break; - } - return I; -} - -/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. When -/// NumPredsLeft reaches zero, release the successor node. -/// -/// FIXME: Adjust SuccSU height based on MinLatency. -void VLIWMachineScheduler::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) - SchedImpl->releaseTopNode(SuccSU); -} - -/// releaseSuccessors - Call releaseSucc on each of SU's successors. -void VLIWMachineScheduler::releaseSuccessors(SUnit *SU) { - for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); - I != E; ++I) { - releaseSucc(SU, &*I); - } -} - -/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. When -/// NumSuccsLeft reaches zero, release the predecessor node. -/// -/// FIXME: Adjust PredSU height based on MinLatency. -void VLIWMachineScheduler::releasePred(SUnit *SU, SDep *PredEdge) { - SUnit *PredSU = PredEdge->getSUnit(); - -#ifndef NDEBUG - if (PredSU->NumSuccsLeft == 0) { - dbgs() << "*** Scheduling failed! ***\n"; - PredSU->dump(this); - dbgs() << " has been released too many times!\n"; - llvm_unreachable(0); - } -#endif - --PredSU->NumSuccsLeft; - if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) - SchedImpl->releaseBottomNode(PredSU); -} - -/// releasePredecessors - Call releasePred on each of SU's predecessors. -void VLIWMachineScheduler::releasePredecessors(SUnit *SU) { - for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); - I != E; ++I) { - releasePred(SU, &*I); - } -} - -void VLIWMachineScheduler::moveInstruction(MachineInstr *MI, - MachineBasicBlock::iterator InsertPos) { - // Advance RegionBegin if the first instruction moves down. - if (&*RegionBegin == MI) - ++RegionBegin; - - // Update the instruction stream. - BB->splice(InsertPos, BB, MI); - - // Update LiveIntervals - LIS->handleMove(MI); - - // Recede RegionBegin if an instruction moves above the first. - if (RegionBegin == InsertPos) - RegionBegin = MI; -} - -bool VLIWMachineScheduler::checkSchedLimit() { -#ifndef NDEBUG - if (NumInstrsScheduled == MISchedCutoff && MISchedCutoff != ~0U) { - CurrentTop = CurrentBottom; - return false; - } - ++NumInstrsScheduled; -#endif - return true; -} - -/// enterRegion - Called back from MachineScheduler::runOnMachineFunction after -/// crossing a scheduling boundary. [begin, end) includes all instructions in -/// the region, including the boundary itself and single-instruction regions -/// that don't get scheduled. -void VLIWMachineScheduler::enterRegion(MachineBasicBlock *bb, - MachineBasicBlock::iterator begin, - MachineBasicBlock::iterator end, - unsigned endcount) -{ - ScheduleDAGInstrs::enterRegion(bb, begin, end, endcount); - - // For convenience remember the end of the liveness region. - LiveRegionEnd = - (RegionEnd == bb->end()) ? RegionEnd : llvm::next(RegionEnd); -} - -// Setup the register pressure trackers for the top scheduled top and bottom -// scheduled regions. -void VLIWMachineScheduler::initRegPressure() { - TopRPTracker.init(&MF, RegClassInfo, LIS, BB, RegionBegin); - BotRPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd); - - // Close the RPTracker to finalize live ins. - RPTracker.closeRegion(); - - DEBUG(RPTracker.getPressure().dump(TRI)); - - // Initialize the live ins and live outs. - TopRPTracker.addLiveRegs(RPTracker.getPressure().LiveInRegs); - BotRPTracker.addLiveRegs(RPTracker.getPressure().LiveOutRegs); - - // Close one end of the tracker so we can call - // getMaxUpward/DownwardPressureDelta before advancing across any - // instructions. This converts currently live regs into live ins/outs. - TopRPTracker.closeTop(); - BotRPTracker.closeBottom(); - - // Account for liveness generated by the region boundary. - if (LiveRegionEnd != RegionEnd) - BotRPTracker.recede(); - - assert(BotRPTracker.getPos() == RegionEnd && "Can't find the region bottom"); - - // Cache the list of excess pressure sets in this region. This will also track - // the max pressure in the scheduled code for these sets. - RegionCriticalPSets.clear(); - std::vector<unsigned> RegionPressure = RPTracker.getPressure().MaxSetPressure; - for (unsigned i = 0, e = RegionPressure.size(); i < e; ++i) { - unsigned Limit = TRI->getRegPressureSetLimit(i); - DEBUG(dbgs() << TRI->getRegPressureSetName(i) - << "Limit " << Limit - << " Actual " << RegionPressure[i] << "\n"); - if (RegionPressure[i] > Limit) - RegionCriticalPSets.push_back(PressureElement(i, 0)); - } - DEBUG(dbgs() << "Excess PSets: "; - for (unsigned i = 0, e = RegionCriticalPSets.size(); i != e; ++i) - dbgs() << TRI->getRegPressureSetName( - RegionCriticalPSets[i].PSetID) << " "; - dbgs() << "\n"); - - TotalPackets = 0; -} - -// FIXME: When the pressure tracker deals in pressure differences then we won't -// iterate over all RegionCriticalPSets[i]. -void VLIWMachineScheduler:: -updateScheduledPressure(std::vector<unsigned> NewMaxPressure) { - for (unsigned i = 0, e = RegionCriticalPSets.size(); i < e; ++i) { - unsigned ID = RegionCriticalPSets[i].PSetID; - int &MaxUnits = RegionCriticalPSets[i].UnitIncrease; - if ((int)NewMaxPressure[ID] > MaxUnits) - MaxUnits = NewMaxPressure[ID]; - } -} - /// Check if scheduling of this SU is possible /// in the current packet. /// It is _not_ precise (statefull), it is more like @@ -312,26 +115,6 @@ bool VLIWResourceModel::reserveResources(SUnit *SU) { return startNewCycle; } -// Release all DAG roots for scheduling. -void VLIWMachineScheduler::releaseRoots() { - SmallVector<SUnit*, 16> BotRoots; - - for (std::vector<SUnit>::iterator - I = SUnits.begin(), E = SUnits.end(); I != E; ++I) { - // A SUnit is ready to top schedule if it has no predecessors. - if (I->Preds.empty()) - SchedImpl->releaseTopNode(&(*I)); - // A SUnit is ready to bottom schedule if it has no successors. - if (I->Succs.empty()) - BotRoots.push_back(&(*I)); - } - // Release bottom roots in reverse order so the higher priority nodes appear - // first. This is more natural and slightly more efficient. - for (SmallVectorImpl<SUnit*>::const_reverse_iterator - I = BotRoots.rbegin(), E = BotRoots.rend(); I != E; ++I) - SchedImpl->releaseBottomNode(*I); -} - /// schedule - Called back from MachineScheduler::runOnMachineFunction /// after setting up the current scheduling region. [RegionBegin, RegionEnd) /// only includes instructions that have DAG nodes, not scheduling boundaries. @@ -343,18 +126,7 @@ void VLIWMachineScheduler::schedule() { << " at loop depth " << MLI->getLoopDepth(BB) << " \n"); - // Initialize the register pressure tracker used by buildSchedGraph. - RPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd); - - // Account for liveness generate by the region boundary. - if (LiveRegionEnd != RegionEnd) - RPTracker.recede(); - - // Build the DAG, and compute current register pressure. - buildSchedGraph(AA, &RPTracker); - - // Initialize top/bottom trackers after computing region pressure. - initRegPressure(); + buildDAGWithRegPressure(); // To view Height/Depth correctly, they should be accessed at least once. DEBUG(unsigned maxH = 0; @@ -370,99 +142,27 @@ void VLIWMachineScheduler::schedule() { DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) SUnits[su].dumpAll(this)); - if (ViewMISchedDAGs) viewGraph(); - - SchedImpl->initialize(this); - - // Release edges from the special Entry node or to the special Exit node. - releaseSuccessors(&EntrySU); - releasePredecessors(&ExitSU); + initQueues(); - // Release all DAG roots for scheduling. - releaseRoots(); - - CurrentTop = nextIfDebug(RegionBegin, RegionEnd); - CurrentBottom = RegionEnd; bool IsTopNode = false; while (SUnit *SU = SchedImpl->pickNode(IsTopNode)) { if (!checkSchedLimit()) break; - // Move the instruction to its new location in the instruction stream. - MachineInstr *MI = SU->getInstr(); - - if (IsTopNode) { - assert(SU->isTopReady() && "node still has unscheduled dependencies"); - if (&*CurrentTop == MI) - CurrentTop = nextIfDebug(++CurrentTop, CurrentBottom); - else { - moveInstruction(MI, CurrentTop); - TopRPTracker.setPos(MI); - } - - // Update top scheduled pressure. - TopRPTracker.advance(); - assert(TopRPTracker.getPos() == CurrentTop && "out of sync"); - updateScheduledPressure(TopRPTracker.getPressure().MaxSetPressure); - - // Release dependent instructions for scheduling. - releaseSuccessors(SU); - } else { - assert(SU->isBottomReady() && "node still has unscheduled dependencies"); - MachineBasicBlock::iterator priorII = - priorNonDebug(CurrentBottom, CurrentTop); - if (&*priorII == MI) - CurrentBottom = priorII; - else { - if (&*CurrentTop == MI) { - CurrentTop = nextIfDebug(++CurrentTop, priorII); - TopRPTracker.setPos(CurrentTop); - } - moveInstruction(MI, CurrentBottom); - CurrentBottom = MI; - } - // Update bottom scheduled pressure. - BotRPTracker.recede(); - assert(BotRPTracker.getPos() == CurrentBottom && "out of sync"); - updateScheduledPressure(BotRPTracker.getPressure().MaxSetPressure); - - // Release dependent instructions for scheduling. - releasePredecessors(SU); - } - SU->isScheduled = true; - SchedImpl->schedNode(SU, IsTopNode); + scheduleMI(SU, IsTopNode); + + updateQueues(SU, IsTopNode); } assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone."); placeDebugValues(); } -/// Reinsert any remaining debug_values, just like the PostRA scheduler. -void VLIWMachineScheduler::placeDebugValues() { - // If first instruction was a DBG_VALUE then put it back. - if (FirstDbgValue) { - BB->splice(RegionBegin, BB, FirstDbgValue); - RegionBegin = FirstDbgValue; - } - - for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator - DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) { - std::pair<MachineInstr *, MachineInstr *> P = *prior(DI); - MachineInstr *DbgValue = P.first; - MachineBasicBlock::iterator OrigPrevMI = P.second; - BB->splice(++OrigPrevMI, BB, DbgValue); - if (OrigPrevMI == llvm::prior(RegionEnd)) - RegionEnd = DbgValue; - } - DbgValues.clear(); - FirstDbgValue = NULL; -} - -void ConvergingVLIWScheduler::initialize(VLIWMachineScheduler *dag) { - DAG = dag; +void ConvergingVLIWScheduler::initialize(ScheduleDAGMI *dag) { + DAG = static_cast<VLIWMachineScheduler*>(dag); TRI = DAG->TRI; - Top.DAG = dag; - Bot.DAG = dag; + Top.DAG = DAG; + Bot.DAG = DAG; // Initialize the HazardRecognizers. const TargetMachine &TM = DAG->MF.getTarget(); @@ -473,7 +173,7 @@ void ConvergingVLIWScheduler::initialize(VLIWMachineScheduler *dag) { Top.ResourceModel = new VLIWResourceModel(TM); Bot.ResourceModel = new VLIWResourceModel(TM); - assert((!ForceTopDown || !ForceBottomUp) && + assert((!llvm::ForceTopDown || !llvm::ForceBottomUp) && "-misched-topdown incompatible with -misched-bottomup"); } @@ -899,7 +599,7 @@ SUnit *ConvergingVLIWScheduler::pickNode(bool &IsTopNode) { return NULL; } SUnit *SU; - if (ForceTopDown) { + if (llvm::ForceTopDown) { SU = Top.pickOnlyChoice(); if (!SU) { SchedCandidate TopCand; @@ -910,7 +610,7 @@ SUnit *ConvergingVLIWScheduler::pickNode(bool &IsTopNode) { SU = TopCand.SU; } IsTopNode = true; - } else if (ForceBottomUp) { + } else if (llvm::ForceBottomUp) { SU = Bot.pickOnlyChoice(); if (!SU) { SchedCandidate BotCand; diff --git a/lib/Target/Hexagon/HexagonMachineScheduler.h b/lib/Target/Hexagon/HexagonMachineScheduler.h index f3643d64f6..212cc9800b 100644 --- a/lib/Target/Hexagon/HexagonMachineScheduler.h +++ b/lib/Target/Hexagon/HexagonMachineScheduler.h @@ -33,97 +33,12 @@ using namespace llvm; -//===----------------------------------------------------------------------===// -// MachineSchedStrategy - Interface to a machine scheduling algorithm. -//===----------------------------------------------------------------------===// - namespace llvm { -class VLIWMachineScheduler; - -/// MachineSchedStrategy - Interface used by VLIWMachineScheduler to drive -/// the selected scheduling algorithm. -/// -/// TODO: Move this to ScheduleDAGInstrs.h -class MachineSchedStrategy { -public: - virtual ~MachineSchedStrategy() {} - - /// Initialize the strategy after building the DAG for a new region. - virtual void initialize(VLIWMachineScheduler *DAG) = 0; - - /// Pick the next node to schedule, or return NULL. Set IsTopNode to true to - /// schedule the node at the top of the unscheduled region. Otherwise it will - /// be scheduled at the bottom. - virtual SUnit *pickNode(bool &IsTopNode) = 0; - - /// Notify MachineSchedStrategy that VLIWMachineScheduler has - /// scheduled a node. - virtual void schedNode(SUnit *SU, bool IsTopNode) = 0; - - /// When all predecessor dependencies have been resolved, free this node for - /// top-down scheduling. - virtual void releaseTopNode(SUnit *SU) = 0; - /// When all successor dependencies have been resolved, free this node for - /// bottom-up scheduling. - virtual void releaseBottomNode(SUnit *SU) = 0; -}; - //===----------------------------------------------------------------------===// // ConvergingVLIWScheduler - Implementation of the standard // MachineSchedStrategy. //===----------------------------------------------------------------------===// -/// ReadyQueue encapsulates vector of "ready" SUnits with basic convenience -/// methods for pushing and removing nodes. ReadyQueue's are uniquely identified -/// by an ID. SUnit::NodeQueueId is a mask of the ReadyQueues the SUnit is in. -class ReadyQueue { - unsigned ID; - std::string Name; - std::vector<SUnit*> Queue; - -public: - ReadyQueue(unsigned id, const Twine &name): ID(id), Name(name.str()) {} - - unsigned getID() const { return ID; } - - StringRef getName() const { return Name; } - - // SU is in this queue if it's NodeQueueID is a superset of this ID. - bool isInQueue(SUnit *SU) const { return (SU->NodeQueueId & ID); } - - bool empty() const { return Queue.empty(); } - - unsigned size() const { return Queue.size(); } - - typedef std::vector<SUnit*>::iterator iterator; - - iterator begin() { return Queue.begin(); } - - iterator end() { return Queue.end(); } - - iterator find(SUnit *SU) { - return std::find(Queue.begin(), Queue.end(), SU); - } - - void push(SUnit *SU) { - Queue.push_back(SU); - SU->NodeQueueId |= ID; - } - - void remove(iterator I) { - (*I)->NodeQueueId &= ~ID; - *I = Queue.back(); - Queue.pop_back(); - } - - void dump() { - dbgs() << Name << ": "; - for (unsigned i = 0, e = Queue.size(); i < e; ++i) - dbgs() << Queue[i]->NodeNum << " "; - dbgs() << "\n"; - } -}; - class VLIWResourceModel { /// ResourcesModel - Represents VLIW state. /// Not limited to VLIW targets per say, but assumes @@ -189,124 +104,17 @@ public: unsigned getTotalPackets() const { return TotalPackets; } }; -class VLIWMachineScheduler : public ScheduleDAGInstrs { - /// AA - AliasAnalysis for making memory reference queries. - AliasAnalysis *AA; - - RegisterClassInfo *RegClassInfo; - MachineSchedStrategy *SchedImpl; - - MachineBasicBlock::iterator LiveRegionEnd; - - /// Register pressure in this region computed by buildSchedGraph. - IntervalPressure RegPressure; - RegPressureTracker RPTracker; - - /// List of pressure sets that exceed the target's pressure limit before - /// scheduling, listed in increasing set ID order. Each pressure set is paired - /// with its max pressure in the currently scheduled regions. - std::vector<PressureElement> RegionCriticalPSets; - - /// The top of the unscheduled zone. - MachineBasicBlock::iterator CurrentTop; - IntervalPressure TopPressure; - RegPressureTracker TopRPTracker; - - /// The bottom of the unscheduled zone. - MachineBasicBlock::iterator CurrentBottom; - IntervalPressure BotPressure; - RegPressureTracker BotRPTracker; - -#ifndef NDEBUG - /// The number of instructions scheduled so far. Used to cut off the - /// scheduler at the point determined by misched-cutoff. - unsigned NumInstrsScheduled; -#endif - - /// Total packets in the region. - unsigned TotalPackets; - +/// Extend the standard ScheduleDAGMI to provide more context and override the +/// top-level schedule() driver. +class VLIWMachineScheduler : public ScheduleDAGMI { const MachineLoopInfo *MLI; public: VLIWMachineScheduler(MachineSchedContext *C, MachineSchedStrategy *S): - ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS), - AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S), - RPTracker(RegPressure), CurrentTop(), TopRPTracker(TopPressure), - CurrentBottom(), BotRPTracker(BotPressure), MLI(C->MLI) { -#ifndef NDEBUG - NumInstrsScheduled = 0; -#endif - TotalPackets = 0; - } - - virtual ~VLIWMachineScheduler() { - delete SchedImpl; - } - - MachineBasicBlock::iterator top() const { return CurrentTop; } - MachineBasicBlock::iterator bottom() const { return CurrentBottom; } - - /// Implement the ScheduleDAGInstrs interface for handling the next scheduling - /// region. This covers all instructions in a block, while schedule() may only - /// cover a subset. - void enterRegion(MachineBasicBlock *bb, - MachineBasicBlock::iterator begin, - MachineBasicBlock::iterator end, - unsigned endcount); + ScheduleDAGMI(C, S), MLI(C->MLI) {} /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's /// time to do some work. - void schedule(); - - unsigned CurCycle; - - /// Get current register pressure for the top scheduled instructions. - const IntervalPressure &getTopPressure() const { return TopPressure; } - const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; } - - /// Get current register pressure for the bottom scheduled instructions. - const IntervalPressure &getBotPressure() const { return BotPressure; } - const RegPressureTracker &getBotRPTracker() const { return BotRPTracker; } - - /// Get register pressure for the entire scheduling region before scheduling. - const IntervalPressure &getRegPressure() const { return RegPressure; } - - const std::vector<PressureElement> &getRegionCriticalPSets() const { - return RegionCriticalPSets; - } - - /// getIssueWidth - Return the max instructions per scheduling group. - unsigned getIssueWidth() const { - return (InstrItins && InstrItins->SchedModel) - ? InstrItins->SchedModel->IssueWidth : 1; - } - - /// getNumMicroOps - Return the number of issue slots required for this MI. - unsigned getNumMicroOps(MachineInstr *MI) const { - return 1; - //if (!InstrItins) return 1; - //int UOps = InstrItins->getNumMicroOps(MI->getDesc().getSchedClass()); - //return (UOps >= 0) ? UOps : TII->getNumMicroOps(InstrItins, MI); - } - -private: - void scheduleNodeTopDown(SUnit *SU); - void listScheduleTopDown(); - - void initRegPressure(); - void updateScheduledPressure(std::vector<unsigned> NewMaxPressure); - - void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos); - bool checkSchedLimit(); - - void releaseRoots(); - - void releaseSucc(SUnit *SU, SDep *SuccEdge); - void releaseSuccessors(SUnit *SU); - void releasePred(SUnit *SU, SDep *PredEdge); - void releasePredecessors(SUnit *SU); - - void placeDebugValues(); + virtual void schedule(); }; /// ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics @@ -405,7 +213,7 @@ public: ConvergingVLIWScheduler(): DAG(0), TRI(0), Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {} - virtual void initialize(VLIWMachineScheduler *dag); + virtual void initialize(ScheduleDAGMI *dag); virtual SUnit *pickNode(bool &IsTopNode); |