From 7ae51be2a3a56be5cf0ee4557aa13a069c96a241 Mon Sep 17 00:00:00 2001 From: Sergei Larin Date: Mon, 10 Sep 2012 17:31:34 +0000 Subject: Add "blocked" heuristic to the Hexagon MI scheduler. Improve AQ instruction selection in the Hexagon MI scheduler. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163523 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Target/Hexagon/HexagonMachineScheduler.h | 296 ++++++++++++++------------- 1 file changed, 155 insertions(+), 141 deletions(-) (limited to 'lib/Target/Hexagon/HexagonMachineScheduler.h') diff --git a/lib/Target/Hexagon/HexagonMachineScheduler.h b/lib/Target/Hexagon/HexagonMachineScheduler.h index 7d8cc3d..f3643d6 100644 --- a/lib/Target/Hexagon/HexagonMachineScheduler.h +++ b/lib/Target/Hexagon/HexagonMachineScheduler.h @@ -40,11 +40,10 @@ using namespace llvm; namespace llvm { class VLIWMachineScheduler; -/// MachineSchedStrategy - Interface used by VLIWMachineScheduler to drive the selected -/// scheduling algorithm. +/// MachineSchedStrategy - Interface used by VLIWMachineScheduler to drive +/// the selected scheduling algorithm. /// -/// If this works well and targets wish to reuse VLIWMachineScheduler, we may expose it -/// in ScheduleDAGInstrs.h +/// TODO: Move this to ScheduleDAGInstrs.h class MachineSchedStrategy { public: virtual ~MachineSchedStrategy() {} @@ -57,7 +56,8 @@ public: /// be scheduled at the bottom. virtual SUnit *pickNode(bool &IsTopNode) = 0; - /// Notify MachineSchedStrategy that VLIWMachineScheduler has scheduled a node. + /// 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 @@ -69,7 +69,8 @@ public: }; //===----------------------------------------------------------------------===// -// ConvergingVLIWScheduler - Implementation of the standard MachineSchedStrategy. +// ConvergingVLIWScheduler - Implementation of the standard +// MachineSchedStrategy. //===----------------------------------------------------------------------===// /// ReadyQueue encapsulates vector of "ready" SUnits with basic convenience @@ -123,123 +124,6 @@ public: } }; -/// ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics to balance -/// the schedule. -class ConvergingVLIWScheduler : public MachineSchedStrategy { - - /// Store the state used by ConvergingVLIWScheduler heuristics, required for the - /// lifetime of one invocation of pickNode(). - struct SchedCandidate { - // The best SUnit candidate. - SUnit *SU; - - // Register pressure values for the best candidate. - RegPressureDelta RPDelta; - - // Best scheduling cost. - int SCost; - - SchedCandidate(): SU(NULL), SCost(0) {} - }; - /// Represent the type of SchedCandidate found within a single queue. - enum CandResult { - NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure, - BestCost}; - - /// Each Scheduling boundary is associated with ready queues. It tracks the - /// current cycle in whichever direction at has moved, and maintains the state - /// of "hazards" and other interlocks at the current cycle. - struct SchedBoundary { - VLIWMachineScheduler *DAG; - - ReadyQueue Available; - ReadyQueue Pending; - bool CheckPending; - - ScheduleHazardRecognizer *HazardRec; - - unsigned CurrCycle; - unsigned IssueCount; - - /// MinReadyCycle - Cycle of the soonest available instruction. - unsigned MinReadyCycle; - - // Remember the greatest min operand latency. - unsigned MaxMinLatency; - - /// Pending queues extend the ready queues with the same ID and the - /// PendingFlag set. - SchedBoundary(unsigned ID, const Twine &Name): - DAG(0), Available(ID, Name+".A"), - Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name+".P"), - CheckPending(false), HazardRec(0), CurrCycle(0), IssueCount(0), - MinReadyCycle(UINT_MAX), MaxMinLatency(0) {} - - ~SchedBoundary() { delete HazardRec; } - - bool isTop() const { - return Available.getID() == ConvergingVLIWScheduler::TopQID; - } - - bool checkHazard(SUnit *SU); - - void releaseNode(SUnit *SU, unsigned ReadyCycle); - - void bumpCycle(); - - void bumpNode(SUnit *SU); - - void releasePending(); - - void removeReady(SUnit *SU); - - SUnit *pickOnlyChoice(); - }; - - VLIWMachineScheduler *DAG; - const TargetRegisterInfo *TRI; - - // State of the top and bottom scheduled instruction boundaries. - SchedBoundary Top; - SchedBoundary Bot; - -public: - /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both) - enum { - TopQID = 1, - BotQID = 2, - LogMaxQID = 2 - }; - - ConvergingVLIWScheduler(): - DAG(0), TRI(0), Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {} - - virtual void initialize(VLIWMachineScheduler *dag); - - virtual SUnit *pickNode(bool &IsTopNode); - - virtual void schedNode(SUnit *SU, bool IsTopNode); - - virtual void releaseTopNode(SUnit *SU); - - virtual void releaseBottomNode(SUnit *SU); - -protected: - SUnit *pickNodeBidrectional(bool &IsTopNode); - - int SchedulingCost(ReadyQueue &Q, - SUnit *SU, SchedCandidate &Candidate, - RegPressureDelta &Delta, bool verbose); - - CandResult pickNodeFromQueue(ReadyQueue &Q, - const RegPressureTracker &RPTracker, - SchedCandidate &Candidate); -#ifndef NDEBUG - void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU, - PressureElement P = PressureElement()); -#endif -}; - class VLIWResourceModel { /// ResourcesModel - Represents VLIW state. /// Not limited to VLIW targets per say, but assumes @@ -261,7 +145,21 @@ public: const TargetMachine &TM = C->MF->getTarget(); ResourcesModel = TM.getInstrInfo()->CreateTargetScheduleState(&TM,NULL); - // This hard requirement could be relaxed, but for now do not let it proceed. + // This hard requirement could be relaxed, + // but for now do not let it proceed. + assert(ResourcesModel && "Unimplemented CreateTargetScheduleState."); + + Packet.resize(InstrItins->SchedModel->IssueWidth); + Packet.clear(); + ResourcesModel->clearResources(); + } + + VLIWResourceModel(const TargetMachine &TM) : + InstrItins(TM.getInstrItineraryData()), TotalPackets(0) { + ResourcesModel = TM.getInstrInfo()->CreateTargetScheduleState(&TM,NULL); + + // This hard requirement could be relaxed, + // but for now do not let it proceed. assert(ResourcesModel && "Unimplemented CreateTargetScheduleState."); Packet.resize(InstrItins->SchedModel->IssueWidth); @@ -281,8 +179,13 @@ public: ResourcesModel->clearResources(); } + void reset() { + Packet.clear(); + ResourcesModel->clearResources(); + } + bool isResourceAvailable(SUnit *SU); - void reserveResources(SUnit *SU); + bool reserveResources(SUnit *SU); unsigned getTotalPackets() const { return TotalPackets; } }; @@ -293,10 +196,6 @@ class VLIWMachineScheduler : public ScheduleDAGInstrs { RegisterClassInfo *RegClassInfo; MachineSchedStrategy *SchedImpl; - /// state separatly for top/bottom sectioins. - VLIWResourceModel *TopResourceModel; - VLIWResourceModel *BotResourceModel; - MachineBasicBlock::iterator LiveRegionEnd; /// Register pressure in this region computed by buildSchedGraph. @@ -334,10 +233,6 @@ public: AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S), RPTracker(RegPressure), CurrentTop(), TopRPTracker(TopPressure), CurrentBottom(), BotRPTracker(BotPressure), MLI(C->MLI) { - - TopResourceModel = new VLIWResourceModel(C, InstrItins); - BotResourceModel = new VLIWResourceModel(C, InstrItins); - #ifndef NDEBUG NumInstrsScheduled = 0; #endif @@ -346,8 +241,6 @@ public: virtual ~VLIWMachineScheduler() { delete SchedImpl; - delete TopResourceModel; - delete BotResourceModel; } MachineBasicBlock::iterator top() const { return CurrentTop; } @@ -382,9 +275,6 @@ public: return RegionCriticalPSets; } - VLIWResourceModel *getTopResourceModel() { return TopResourceModel; } - VLIWResourceModel *getBotResourceModel() { return BotResourceModel; } - /// getIssueWidth - Return the max instructions per scheduling group. unsigned getIssueWidth() const { return (InstrItins && InstrItins->SchedModel) @@ -393,9 +283,10 @@ public: /// 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); + return 1; + //if (!InstrItins) return 1; + //int UOps = InstrItins->getNumMicroOps(MI->getDesc().getSchedClass()); + //return (UOps >= 0) ? UOps : TII->getNumMicroOps(InstrItins, MI); } private: @@ -417,6 +308,129 @@ private: void placeDebugValues(); }; + +/// ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics +/// to balance the schedule. +class ConvergingVLIWScheduler : public MachineSchedStrategy { + + /// Store the state used by ConvergingVLIWScheduler heuristics, required + /// for the lifetime of one invocation of pickNode(). + struct SchedCandidate { + // The best SUnit candidate. + SUnit *SU; + + // Register pressure values for the best candidate. + RegPressureDelta RPDelta; + + // Best scheduling cost. + int SCost; + + SchedCandidate(): SU(NULL), SCost(0) {} + }; + /// Represent the type of SchedCandidate found within a single queue. + enum CandResult { + NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure, + BestCost}; + + /// Each Scheduling boundary is associated with ready queues. It tracks the + /// current cycle in whichever direction at has moved, and maintains the state + /// of "hazards" and other interlocks at the current cycle. + struct SchedBoundary { + VLIWMachineScheduler *DAG; + + ReadyQueue Available; + ReadyQueue Pending; + bool CheckPending; + + ScheduleHazardRecognizer *HazardRec; + VLIWResourceModel *ResourceModel; + + unsigned CurrCycle; + unsigned IssueCount; + + /// MinReadyCycle - Cycle of the soonest available instruction. + unsigned MinReadyCycle; + + // Remember the greatest min operand latency. + unsigned MaxMinLatency; + + /// Pending queues extend the ready queues with the same ID and the + /// PendingFlag set. + SchedBoundary(unsigned ID, const Twine &Name): + DAG(0), Available(ID, Name+".A"), + Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name+".P"), + CheckPending(false), HazardRec(0), ResourceModel(0), + CurrCycle(0), IssueCount(0), + MinReadyCycle(UINT_MAX), MaxMinLatency(0) {} + + ~SchedBoundary() { + delete ResourceModel; + delete HazardRec; + } + + bool isTop() const { + return Available.getID() == ConvergingVLIWScheduler::TopQID; + } + + bool checkHazard(SUnit *SU); + + void releaseNode(SUnit *SU, unsigned ReadyCycle); + + void bumpCycle(); + + void bumpNode(SUnit *SU); + + void releasePending(); + + void removeReady(SUnit *SU); + + SUnit *pickOnlyChoice(); + }; + + VLIWMachineScheduler *DAG; + const TargetRegisterInfo *TRI; + + // State of the top and bottom scheduled instruction boundaries. + SchedBoundary Top; + SchedBoundary Bot; + +public: + /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both) + enum { + TopQID = 1, + BotQID = 2, + LogMaxQID = 2 + }; + + ConvergingVLIWScheduler(): + DAG(0), TRI(0), Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {} + + virtual void initialize(VLIWMachineScheduler *dag); + + virtual SUnit *pickNode(bool &IsTopNode); + + virtual void schedNode(SUnit *SU, bool IsTopNode); + + virtual void releaseTopNode(SUnit *SU); + + virtual void releaseBottomNode(SUnit *SU); + +protected: + SUnit *pickNodeBidrectional(bool &IsTopNode); + + int SchedulingCost(ReadyQueue &Q, + SUnit *SU, SchedCandidate &Candidate, + RegPressureDelta &Delta, bool verbose); + + CandResult pickNodeFromQueue(ReadyQueue &Q, + const RegPressureTracker &RPTracker, + SchedCandidate &Candidate); +#ifndef NDEBUG + void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU, + PressureElement P = PressureElement()); +#endif +}; + } // namespace -- cgit v1.1