1//-- SystemZMachineScheduler.cpp - SystemZ Scheduler Interface -*- C++ -*---==//
2//
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
6//
7//===----------------------------------------------------------------------===//
8//
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//===----------------------------------------------------------------------===//
16
17#include "SystemZMachineScheduler.h"
18#include "llvm/CodeGen/MachineLoopInfo.h"
19
20using namespace llvm;
21
22#define DEBUG_TYPE "machine-scheduler"
23
24#ifndef NDEBUG
25// Print the set of SUs
26void SystemZPostRASchedStrategy::SUSet::
27dump(SystemZHazardRecognizer &HazardRec) const {
28 dbgs() << "{";
29 for (auto &SU : *this) {
30 HazardRec.dumpSU(SU, dbgs());
31 if (SU != *rbegin())
32 dbgs() << ", ";
33 }
34 dbgs() << "}\n";
35}
36#endif
37
38// Try to find a single predecessor that would be interesting for the
39// scheduler in the top-most region of MBB.
40static MachineBasicBlock *getSingleSchedPred(MachineBasicBlock *MBB,
41 const MachineLoop *Loop) {
42 MachineBasicBlock *PredMBB = nullptr;
43 if (MBB->pred_size() == 1)
44 PredMBB = *MBB->pred_begin();
45
46 // The loop header has two predecessors, return the latch, but not for a
47 // single block loop.
48 if (MBB->pred_size() == 2 && Loop != nullptr && Loop->getHeader() == MBB) {
49 for (MachineBasicBlock *Pred : MBB->predecessors())
50 if (Loop->contains(BB: Pred))
51 PredMBB = (Pred == MBB ? nullptr : Pred);
52 }
53
54 assert ((PredMBB == nullptr || !Loop || Loop->contains(PredMBB))
55 && "Loop MBB should not consider predecessor outside of loop.");
56
57 return PredMBB;
58}
59
60void SystemZPostRASchedStrategy::
61advanceTo(MachineBasicBlock::iterator NextBegin) {
62 MachineBasicBlock::iterator LastEmittedMI = HazardRec->getLastEmittedMI();
63 MachineBasicBlock::iterator I =
64 ((LastEmittedMI != nullptr && LastEmittedMI->getParent() == MBB) ?
65 std::next(x: LastEmittedMI) : MBB->begin());
66
67 for (; I != NextBegin; ++I) {
68 if (I->isPosition() || I->isDebugInstr())
69 continue;
70 HazardRec->emitInstruction(MI: &*I);
71 }
72}
73
74void SystemZPostRASchedStrategy::initialize(ScheduleDAGMI *dag) {
75 Available.clear(); // -misched-cutoff.
76 LLVM_DEBUG(HazardRec->dumpState(););
77}
78
79void SystemZPostRASchedStrategy::enterMBB(MachineBasicBlock *NextMBB) {
80 assert ((SchedStates.find(NextMBB) == SchedStates.end()) &&
81 "Entering MBB twice?");
82 LLVM_DEBUG(dbgs() << "** Entering " << printMBBReference(*NextMBB));
83
84 MBB = NextMBB;
85
86 /// Create a HazardRec for MBB, save it in SchedStates and set HazardRec to
87 /// point to it.
88 HazardRec = SchedStates[MBB] = new SystemZHazardRecognizer(TII, &SchedModel);
89 LLVM_DEBUG(const MachineLoop *Loop = MLI->getLoopFor(MBB);
90 if (Loop && Loop->getHeader() == MBB) dbgs() << " (Loop header)";
91 dbgs() << ":\n";);
92
93 // Try to take over the state from a single predecessor, if it has been
94 // scheduled. If this is not possible, we are done.
95 MachineBasicBlock *SinglePredMBB =
96 getSingleSchedPred(MBB, Loop: MLI->getLoopFor(BB: MBB));
97 if (SinglePredMBB == nullptr ||
98 SchedStates.find(x: SinglePredMBB) == SchedStates.end())
99 return;
100
101 LLVM_DEBUG(dbgs() << "** Continued scheduling from "
102 << printMBBReference(*SinglePredMBB) << "\n";);
103
104 HazardRec->copyState(Incoming: SchedStates[SinglePredMBB]);
105 LLVM_DEBUG(HazardRec->dumpState(););
106
107 // Emit incoming terminator(s). Be optimistic and assume that branch
108 // prediction will generally do "the right thing".
109 for (MachineInstr &MI : SinglePredMBB->terminators()) {
110 LLVM_DEBUG(dbgs() << "** Emitting incoming branch: "; MI.dump(););
111 bool TakenBranch = (MI.isBranch() &&
112 (TII->getBranchInfo(MI).isIndirect() ||
113 TII->getBranchInfo(MI).getMBBTarget() == MBB));
114 HazardRec->emitInstruction(MI: &MI, TakenBranch);
115 if (TakenBranch)
116 break;
117 }
118}
119
120void SystemZPostRASchedStrategy::leaveMBB() {
121 LLVM_DEBUG(dbgs() << "** Leaving " << printMBBReference(*MBB) << "\n";);
122
123 // Advance to first terminator. The successor block will handle terminators
124 // dependent on CFG layout (T/NT branch etc).
125 advanceTo(NextBegin: MBB->getFirstTerminator());
126}
127
128SystemZPostRASchedStrategy::
129SystemZPostRASchedStrategy(const MachineSchedContext *C)
130 : MLI(C->MLI),
131 TII(static_cast<const SystemZInstrInfo *>
132 (C->MF->getSubtarget().getInstrInfo())),
133 MBB(nullptr), HazardRec(nullptr) {
134 const TargetSubtargetInfo *ST = &C->MF->getSubtarget();
135 SchedModel.init(TSInfo: ST);
136}
137
138SystemZPostRASchedStrategy::~SystemZPostRASchedStrategy() {
139 // Delete hazard recognizers kept around for each MBB.
140 for (auto I : SchedStates) {
141 SystemZHazardRecognizer *hazrec = I.second;
142 delete hazrec;
143 }
144}
145
146void SystemZPostRASchedStrategy::initPolicy(MachineBasicBlock::iterator Begin,
147 MachineBasicBlock::iterator End,
148 unsigned NumRegionInstrs) {
149 // Don't emit the terminators.
150 if (Begin->isTerminator())
151 return;
152
153 // Emit any instructions before start of region.
154 advanceTo(NextBegin: Begin);
155}
156
157// Pick the next node to schedule.
158SUnit *SystemZPostRASchedStrategy::pickNode(bool &IsTopNode) {
159 // Only scheduling top-down.
160 IsTopNode = true;
161
162 if (Available.empty())
163 return nullptr;
164
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();
170 }
171
172 // All nodes that are possible to schedule are stored in the Available set.
173 LLVM_DEBUG(dbgs() << "** Available: "; Available.dump(*HazardRec););
174
175 Candidate Best;
176 for (auto *SU : Available) {
177
178 // SU is the next candidate to be compared against current Best.
179 Candidate c(SU, *HazardRec);
180
181 // Remeber which SU is the best candidate.
182 if (Best.SU == nullptr || c < Best) {
183 Best = c;
184 LLVM_DEBUG(dbgs() << "** Best so far: ";);
185 } else
186 LLVM_DEBUG(dbgs() << "** Tried : ";);
187 LLVM_DEBUG(HazardRec->dumpSU(c.SU, dbgs()); c.dumpCosts();
188 dbgs() << " Height:" << c.SU->getHeight(); dbgs() << "\n";);
189
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())
193 break;
194 }
195
196 assert (Best.SU != nullptr);
197 return Best.SU;
198}
199
200SystemZPostRASchedStrategy::Candidate::
201Candidate(SUnit *SU_, SystemZHazardRecognizer &HazardRec) : Candidate() {
202 SU = SU_;
203
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);
208
209 // Check the resources cost for this SU.
210 ResourcesCost = HazardRec.resourcesCost(SU);
211}
212
213bool SystemZPostRASchedStrategy::Candidate::
214operator<(const Candidate &other) {
215
216 // Check decoder grouping.
217 if (GroupingCost < other.GroupingCost)
218 return true;
219 if (GroupingCost > other.GroupingCost)
220 return false;
221
222 // Compare the use of resources.
223 if (ResourcesCost < other.ResourcesCost)
224 return true;
225 if (ResourcesCost > other.ResourcesCost)
226 return false;
227
228 // Higher SU is otherwise generally better.
229 if (SU->getHeight() > other.SU->getHeight())
230 return true;
231 if (SU->getHeight() < other.SU->getHeight())
232 return false;
233
234 // If all same, fall back to original order.
235 if (SU->NodeNum < other.SU->NodeNum)
236 return true;
237
238 return false;
239}
240
241void 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";);
245
246 // Remove SU from Available set and update HazardRec.
247 Available.erase(x: SU);
248 HazardRec->EmitInstruction(SU);
249}
250
251void SystemZPostRASchedStrategy::releaseTopNode(SUnit *SU) {
252 // Set isScheduleHigh flag on all SUs that we want to consider first in
253 // pickNode().
254 const MCSchedClassDesc *SC = HazardRec->getSchedClass(SU);
255 bool AffectsGrouping = (SC->isValid() && (SC->BeginGroup || SC->EndGroup));
256 SU->isScheduleHigh = (AffectsGrouping || SU->isUnbuffered);
257
258 // Put all released SUs in the Available set.
259 Available.insert(x: SU);
260}
261