1 //-- SystemZMachineScheduler.cpp - SystemZ Scheduler Interface -*- C++ -*---==//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // -------------------------- Post RA scheduling ---------------------------- //
10 // SystemZPostRASchedStrategy is a scheduling strategy which is plugged into
11 // the MachineScheduler. It has a sorted Available set of SUs and a pickNode()
12 // implementation that looks to optimize decoder grouping and balance the
13 // usage of processor resources. Scheduler states are saved for the end
14 // region of each MBB, so that a successor block can learn from it.
15 //===----------------------------------------------------------------------===//
17 #include "SystemZMachineScheduler.h"
18 #include "llvm/CodeGen/MachineLoopInfo.h"
22 #define DEBUG_TYPE "machine-scheduler"
25 // Print the set of SUs
26 void SystemZPostRASchedStrategy::SUSet::
27 dump(SystemZHazardRecognizer &HazardRec) const {
29 for (auto &SU : *this) {
30 HazardRec.dumpSU(SU, dbgs());
38 // Try to find a single predecessor that would be interesting for the
39 // scheduler in the top-most region of MBB.
40 static MachineBasicBlock *getSingleSchedPred(MachineBasicBlock *MBB,
41 const MachineLoop *Loop) {
42 MachineBasicBlock *PredMBB = nullptr;
43 if (MBB->pred_size() == 1)
44 PredMBB = *MBB->pred_begin();
46 // The loop header has two predecessors, return the latch, but not for a
48 if (MBB->pred_size() == 2 && Loop != nullptr && Loop->getHeader() == MBB) {
49 for (auto I = MBB->pred_begin(); I != MBB->pred_end(); ++I)
50 if (Loop->contains(*I))
51 PredMBB = (*I == MBB ? nullptr : *I);
54 assert ((PredMBB == nullptr || !Loop || Loop->contains(PredMBB))
55 && "Loop MBB should not consider predecessor outside of loop.");
60 void SystemZPostRASchedStrategy::
61 advanceTo(MachineBasicBlock::iterator NextBegin) {
62 MachineBasicBlock::iterator LastEmittedMI = HazardRec->getLastEmittedMI();
63 MachineBasicBlock::iterator I =
64 ((LastEmittedMI != nullptr && LastEmittedMI->getParent() == MBB) ?
65 std::next(LastEmittedMI) : MBB->begin());
67 for (; I != NextBegin; ++I) {
68 if (I->isPosition() || I->isDebugInstr())
70 HazardRec->emitInstruction(&*I);
74 void SystemZPostRASchedStrategy::initialize(ScheduleDAGMI *dag) {
75 LLVM_DEBUG(HazardRec->dumpState(););
78 void SystemZPostRASchedStrategy::enterMBB(MachineBasicBlock *NextMBB) {
79 assert ((SchedStates.find(NextMBB) == SchedStates.end()) &&
80 "Entering MBB twice?");
81 LLVM_DEBUG(dbgs() << "** Entering " << printMBBReference(*NextMBB));
85 /// Create a HazardRec for MBB, save it in SchedStates and set HazardRec to
87 HazardRec = SchedStates[MBB] = new SystemZHazardRecognizer(TII, &SchedModel);
88 LLVM_DEBUG(const MachineLoop *Loop = MLI->getLoopFor(MBB);
89 if (Loop && Loop->getHeader() == MBB) dbgs() << " (Loop header)";
92 // Try to take over the state from a single predecessor, if it has been
93 // scheduled. If this is not possible, we are done.
94 MachineBasicBlock *SinglePredMBB =
95 getSingleSchedPred(MBB, MLI->getLoopFor(MBB));
96 if (SinglePredMBB == nullptr ||
97 SchedStates.find(SinglePredMBB) == SchedStates.end())
100 LLVM_DEBUG(dbgs() << "** Continued scheduling from "
101 << printMBBReference(*SinglePredMBB) << "\n";);
103 HazardRec->copyState(SchedStates[SinglePredMBB]);
104 LLVM_DEBUG(HazardRec->dumpState(););
106 // Emit incoming terminator(s). Be optimistic and assume that branch
107 // prediction will generally do "the right thing".
108 for (MachineBasicBlock::iterator I = SinglePredMBB->getFirstTerminator();
109 I != SinglePredMBB->end(); I++) {
110 LLVM_DEBUG(dbgs() << "** Emitting incoming branch: "; I->dump(););
111 bool TakenBranch = (I->isBranch() &&
112 (TII->getBranchInfo(*I).isIndirect() ||
113 TII->getBranchInfo(*I).getMBBTarget() == MBB));
114 HazardRec->emitInstruction(&*I, TakenBranch);
120 void SystemZPostRASchedStrategy::leaveMBB() {
121 LLVM_DEBUG(dbgs() << "** Leaving " << printMBBReference(*MBB) << "\n";);
123 // Advance to first terminator. The successor block will handle terminators
124 // dependent on CFG layout (T/NT branch etc).
125 advanceTo(MBB->getFirstTerminator());
128 SystemZPostRASchedStrategy::
129 SystemZPostRASchedStrategy(const MachineSchedContext *C)
131 TII(static_cast<const SystemZInstrInfo *>
132 (C->MF->getSubtarget().getInstrInfo())),
133 MBB(nullptr), HazardRec(nullptr) {
134 const TargetSubtargetInfo *ST = &C->MF->getSubtarget();
138 SystemZPostRASchedStrategy::~SystemZPostRASchedStrategy() {
139 // Delete hazard recognizers kept around for each MBB.
140 for (auto I : SchedStates) {
141 SystemZHazardRecognizer *hazrec = I.second;
146 void SystemZPostRASchedStrategy::initPolicy(MachineBasicBlock::iterator Begin,
147 MachineBasicBlock::iterator End,
148 unsigned NumRegionInstrs) {
149 // Don't emit the terminators.
150 if (Begin->isTerminator())
153 // Emit any instructions before start of region.
157 // Pick the next node to schedule.
158 SUnit *SystemZPostRASchedStrategy::pickNode(bool &IsTopNode) {
159 // Only scheduling top-down.
162 if (Available.empty())
165 // If only one choice, return it.
166 if (Available.size() == 1) {
167 LLVM_DEBUG(dbgs() << "** Only one: ";
168 HazardRec->dumpSU(*Available.begin(), dbgs()); dbgs() << "\n";);
169 return *Available.begin();
172 // All nodes that are possible to schedule are stored in the Available set.
173 LLVM_DEBUG(dbgs() << "** Available: "; Available.dump(*HazardRec););
176 for (auto *SU : Available) {
178 // SU is the next candidate to be compared against current Best.
179 Candidate c(SU, *HazardRec);
181 // Remeber which SU is the best candidate.
182 if (Best.SU == nullptr || c < Best) {
184 LLVM_DEBUG(dbgs() << "** Best so far: ";);
186 LLVM_DEBUG(dbgs() << "** Tried : ";);
187 LLVM_DEBUG(HazardRec->dumpSU(c.SU, dbgs()); c.dumpCosts();
188 dbgs() << " Height:" << c.SU->getHeight(); dbgs() << "\n";);
190 // Once we know we have seen all SUs that affect grouping or use unbuffered
191 // resources, we can stop iterating if Best looks good.
192 if (!SU->isScheduleHigh && Best.noCost())
196 assert (Best.SU != nullptr);
200 SystemZPostRASchedStrategy::Candidate::
201 Candidate(SUnit *SU_, SystemZHazardRecognizer &HazardRec) : Candidate() {
204 // Check the grouping cost. For a node that must begin / end a
205 // group, it is positive if it would do so prematurely, or negative
206 // if it would fit naturally into the schedule.
207 GroupingCost = HazardRec.groupingCost(SU);
209 // Check the resources cost for this SU.
210 ResourcesCost = HazardRec.resourcesCost(SU);
213 bool SystemZPostRASchedStrategy::Candidate::
214 operator<(const Candidate &other) {
216 // Check decoder grouping.
217 if (GroupingCost < other.GroupingCost)
219 if (GroupingCost > other.GroupingCost)
222 // Compare the use of resources.
223 if (ResourcesCost < other.ResourcesCost)
225 if (ResourcesCost > other.ResourcesCost)
228 // Higher SU is otherwise generally better.
229 if (SU->getHeight() > other.SU->getHeight())
231 if (SU->getHeight() < other.SU->getHeight())
234 // If all same, fall back to original order.
235 if (SU->NodeNum < other.SU->NodeNum)
241 void SystemZPostRASchedStrategy::schedNode(SUnit *SU, bool IsTopNode) {
242 LLVM_DEBUG(dbgs() << "** Scheduling SU(" << SU->NodeNum << ") ";
243 if (Available.size() == 1) dbgs() << "(only one) ";
244 Candidate c(SU, *HazardRec); c.dumpCosts(); dbgs() << "\n";);
246 // Remove SU from Available set and update HazardRec.
248 HazardRec->EmitInstruction(SU);
251 void SystemZPostRASchedStrategy::releaseTopNode(SUnit *SU) {
252 // Set isScheduleHigh flag on all SUs that we want to consider first in
254 const MCSchedClassDesc *SC = HazardRec->getSchedClass(SU);
255 bool AffectsGrouping = (SC->isValid() && (SC->BeginGroup || SC->EndGroup));
256 SU->isScheduleHigh = (AffectsGrouping || SU->isUnbuffered);
258 // Put all released SUs in the Available set.
259 Available.insert(SU);