| //===- VLIWMachineScheduler.h - VLIW-Focused Scheduling Pass ----*- C++ -*-===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_CODEGEN_VLIWMACHINESCHEDULER_H |
| #define LLVM_CODEGEN_VLIWMACHINESCHEDULER_H |
| |
| #include "llvm/ADT/SmallVector.h" |
| #include "llvm/ADT/Twine.h" |
| #include "llvm/CodeGen/MachineScheduler.h" |
| #include "llvm/CodeGen/TargetSchedule.h" |
| #include <limits> |
| #include <memory> |
| #include <utility> |
| |
| namespace llvm { |
| |
| class DFAPacketizer; |
| class RegisterClassInfo; |
| class ScheduleHazardRecognizer; |
| class SUnit; |
| class TargetInstrInfo; |
| class TargetSubtargetInfo; |
| |
| class VLIWResourceModel { |
| protected: |
| const TargetInstrInfo *TII; |
| |
| /// ResourcesModel - Represents VLIW state. |
| /// Not limited to VLIW targets per se, but assumes definition of resource |
| /// model by a target. |
| DFAPacketizer *ResourcesModel; |
| |
| const TargetSchedModel *SchedModel; |
| |
| /// Local packet/bundle model. Purely |
| /// internal to the MI scheduler at the time. |
| SmallVector<SUnit *> Packet; |
| |
| /// Total packets created. |
| unsigned TotalPackets = 0; |
| |
| public: |
| VLIWResourceModel(const TargetSubtargetInfo &STI, const TargetSchedModel *SM); |
| |
| virtual ~VLIWResourceModel(); |
| |
| virtual void reset(); |
| |
| virtual bool hasDependence(const SUnit *SUd, const SUnit *SUu); |
| virtual bool isResourceAvailable(SUnit *SU, bool IsTop); |
| virtual bool reserveResources(SUnit *SU, bool IsTop); |
| unsigned getTotalPackets() const { return TotalPackets; } |
| size_t getPacketInstCount() const { return Packet.size(); } |
| bool isInPacket(SUnit *SU) const { return is_contained(Packet, SU); } |
| |
| protected: |
| virtual DFAPacketizer *createPacketizer(const TargetSubtargetInfo &STI) const; |
| }; |
| |
| /// Extend the standard ScheduleDAGMILive to provide more context and override |
| /// the top-level schedule() driver. |
| class VLIWMachineScheduler : public ScheduleDAGMILive { |
| public: |
| VLIWMachineScheduler(MachineSchedContext *C, |
| std::unique_ptr<MachineSchedStrategy> S) |
| : ScheduleDAGMILive(C, std::move(S)) {} |
| |
| /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's |
| /// time to do some work. |
| void schedule() override; |
| |
| RegisterClassInfo *getRegClassInfo() { return RegClassInfo; } |
| int getBBSize() { return BB->size(); } |
| }; |
| |
| //===----------------------------------------------------------------------===// |
| // ConvergingVLIWScheduler - Implementation of a VLIW-aware |
| // MachineSchedStrategy. |
| //===----------------------------------------------------------------------===// |
| |
| class ConvergingVLIWScheduler : public MachineSchedStrategy { |
| protected: |
| /// Store the state used by ConvergingVLIWScheduler heuristics, required |
| /// for the lifetime of one invocation of pickNode(). |
| struct SchedCandidate { |
| // The best SUnit candidate. |
| SUnit *SU = nullptr; |
| |
| // Register pressure values for the best candidate. |
| RegPressureDelta RPDelta; |
| |
| // Best scheduling cost. |
| int SCost = 0; |
| |
| SchedCandidate() = default; |
| }; |
| /// Represent the type of SchedCandidate found within a single queue. |
| enum CandResult { |
| NoCand, |
| NodeOrder, |
| SingleExcess, |
| SingleCritical, |
| SingleMax, |
| MultiPressure, |
| BestCost, |
| Weak |
| }; |
| |
| // Constants used to denote relative importance of |
| // heuristic components for cost computation. |
| static constexpr unsigned PriorityOne = 200; |
| static constexpr unsigned PriorityTwo = 50; |
| static constexpr unsigned PriorityThree = 75; |
| static constexpr unsigned ScaleTwo = 10; |
| |
| /// 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 VLIWSchedBoundary { |
| VLIWMachineScheduler *DAG = nullptr; |
| const TargetSchedModel *SchedModel = nullptr; |
| |
| ReadyQueue Available; |
| ReadyQueue Pending; |
| bool CheckPending = false; |
| |
| ScheduleHazardRecognizer *HazardRec = nullptr; |
| VLIWResourceModel *ResourceModel = nullptr; |
| |
| unsigned CurrCycle = 0; |
| unsigned IssueCount = 0; |
| unsigned CriticalPathLength = 0; |
| |
| /// MinReadyCycle - Cycle of the soonest available instruction. |
| unsigned MinReadyCycle = std::numeric_limits<unsigned>::max(); |
| |
| // Remember the greatest min operand latency. |
| unsigned MaxMinLatency = 0; |
| |
| /// Pending queues extend the ready queues with the same ID and the |
| /// PendingFlag set. |
| VLIWSchedBoundary(unsigned ID, const Twine &Name) |
| : Available(ID, Name + ".A"), |
| Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name + ".P") {} |
| |
| ~VLIWSchedBoundary(); |
| |
| void init(VLIWMachineScheduler *dag, const TargetSchedModel *smodel) { |
| DAG = dag; |
| SchedModel = smodel; |
| CurrCycle = 0; |
| IssueCount = 0; |
| // Initialize the critical path length limit, which used by the scheduling |
| // cost model to determine the value for scheduling an instruction. We use |
| // a slightly different heuristic for small and large functions. For small |
| // functions, it's important to use the height/depth of the instruction. |
| // For large functions, prioritizing by height or depth increases spills. |
| CriticalPathLength = DAG->getBBSize() / SchedModel->getIssueWidth(); |
| if (DAG->getBBSize() < 50) |
| // We divide by two as a cheap and simple heuristic to reduce the |
| // critcal path length, which increases the priority of using the graph |
| // height/depth in the scheduler's cost computation. |
| CriticalPathLength >>= 1; |
| else { |
| // For large basic blocks, we prefer a larger critical path length to |
| // decrease the priority of using the graph height/depth. |
| unsigned MaxPath = 0; |
| for (auto &SU : DAG->SUnits) |
| MaxPath = std::max(MaxPath, isTop() ? SU.getHeight() : SU.getDepth()); |
| CriticalPathLength = std::max(CriticalPathLength, MaxPath) + 1; |
| } |
| } |
| |
| 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(); |
| |
| bool isLatencyBound(SUnit *SU) { |
| if (CurrCycle >= CriticalPathLength) |
| return true; |
| unsigned PathLength = isTop() ? SU->getHeight() : SU->getDepth(); |
| return CriticalPathLength - CurrCycle <= PathLength; |
| } |
| }; |
| |
| VLIWMachineScheduler *DAG = nullptr; |
| const TargetSchedModel *SchedModel = nullptr; |
| |
| // State of the top and bottom scheduled instruction boundaries. |
| VLIWSchedBoundary Top; |
| VLIWSchedBoundary Bot; |
| |
| /// List of pressure sets that have a high pressure level in the region. |
| SmallVector<bool> HighPressureSets; |
| |
| public: |
| /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both) |
| enum { TopQID = 1, BotQID = 2, LogMaxQID = 2 }; |
| |
| ConvergingVLIWScheduler() : Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {} |
| virtual ~ConvergingVLIWScheduler() = default; |
| |
| void initialize(ScheduleDAGMI *dag) override; |
| |
| SUnit *pickNode(bool &IsTopNode) override; |
| |
| void schedNode(SUnit *SU, bool IsTopNode) override; |
| |
| void releaseTopNode(SUnit *SU) override; |
| |
| void releaseBottomNode(SUnit *SU) override; |
| |
| unsigned reportPackets() { |
| return Top.ResourceModel->getTotalPackets() + |
| Bot.ResourceModel->getTotalPackets(); |
| } |
| |
| protected: |
| virtual VLIWResourceModel * |
| createVLIWResourceModel(const TargetSubtargetInfo &STI, |
| const TargetSchedModel *SchedModel) const; |
| |
| SUnit *pickNodeBidrectional(bool &IsTopNode); |
| |
| int pressureChange(const SUnit *SU, bool isBotUp); |
| |
| virtual int SchedulingCost(ReadyQueue &Q, SUnit *SU, |
| SchedCandidate &Candidate, RegPressureDelta &Delta, |
| bool verbose); |
| |
| CandResult pickNodeFromQueue(VLIWSchedBoundary &Zone, |
| const RegPressureTracker &RPTracker, |
| SchedCandidate &Candidate); |
| #ifndef NDEBUG |
| void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU, |
| int Cost, PressureChange P = PressureChange()); |
| |
| void readyQueueVerboseDump(const RegPressureTracker &RPTracker, |
| SchedCandidate &Candidate, ReadyQueue &Q); |
| #endif |
| }; |
| |
| ScheduleDAGMILive *createVLIWSched(MachineSchedContext *C); |
| |
| } // end namespace llvm |
| |
| #endif // LLVM_CODEGEN_VLIWMACHINESCHEDULER_H |