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 return;
99 auto It = SchedStates.find(x: SinglePredMBB);
100 if (It == SchedStates.end())
101 return;
102
103 LLVM_DEBUG(dbgs() << "** Continued scheduling from "
104 << printMBBReference(*SinglePredMBB) << "\n";);
105
106 HazardRec->copyState(Incoming: It->second);
107 LLVM_DEBUG(HazardRec->dumpState(););
108
109 // Emit incoming terminator(s). Be optimistic and assume that branch
110 // prediction will generally do "the right thing".
111 for (MachineInstr &MI : SinglePredMBB->terminators()) {
112 LLVM_DEBUG(dbgs() << "** Emitting incoming branch: "; MI.dump(););
113 bool TakenBranch = (MI.isBranch() &&
114 (TII->getBranchInfo(MI).isIndirect() ||
115 TII->getBranchInfo(MI).getMBBTarget() == MBB));
116 HazardRec->emitInstruction(MI: &MI, TakenBranch);
117 if (TakenBranch)
118 break;
119 }
120}
121
122void SystemZPostRASchedStrategy::leaveMBB() {
123 LLVM_DEBUG(dbgs() << "** Leaving " << printMBBReference(*MBB) << "\n";);
124
125 // Advance to first terminator. The successor block will handle terminators
126 // dependent on CFG layout (T/NT branch etc).
127 advanceTo(NextBegin: MBB->getFirstTerminator());
128}
129
130SystemZPostRASchedStrategy::
131SystemZPostRASchedStrategy(const MachineSchedContext *C)
132 : MLI(C->MLI),
133 TII(static_cast<const SystemZInstrInfo *>
134 (C->MF->getSubtarget().getInstrInfo())),
135 MBB(nullptr), HazardRec(nullptr) {
136 const TargetSubtargetInfo *ST = &C->MF->getSubtarget();
137 SchedModel.init(TSInfo: ST);
138}
139
140SystemZPostRASchedStrategy::~SystemZPostRASchedStrategy() {
141 // Delete hazard recognizers kept around for each MBB.
142 for (auto I : SchedStates) {
143 SystemZHazardRecognizer *hazrec = I.second;
144 delete hazrec;
145 }
146}
147
148void SystemZPostRASchedStrategy::initPolicy(MachineBasicBlock::iterator Begin,
149 MachineBasicBlock::iterator End,
150 unsigned NumRegionInstrs) {
151 // Don't emit the terminators.
152 if (Begin->isTerminator())
153 return;
154
155 // Emit any instructions before start of region.
156 advanceTo(NextBegin: Begin);
157}
158
159// Pick the next node to schedule.
160SUnit *SystemZPostRASchedStrategy::pickNode(bool &IsTopNode) {
161 // Only scheduling top-down.
162 IsTopNode = true;
163
164 if (Available.empty())
165 return nullptr;
166
167 // If only one choice, return it.
168 if (Available.size() == 1) {
169 LLVM_DEBUG(dbgs() << "** Only one: ";
170 HazardRec->dumpSU(*Available.begin(), dbgs()); dbgs() << "\n";);
171 return *Available.begin();
172 }
173
174 // All nodes that are possible to schedule are stored in the Available set.
175 LLVM_DEBUG(dbgs() << "** Available: "; Available.dump(*HazardRec););
176
177 Candidate Best;
178 for (auto *SU : Available) {
179
180 // SU is the next candidate to be compared against current Best.
181 Candidate c(SU, *HazardRec);
182
183 // Remeber which SU is the best candidate.
184 if (Best.SU == nullptr || c < Best) {
185 Best = c;
186 LLVM_DEBUG(dbgs() << "** Best so far: ";);
187 } else
188 LLVM_DEBUG(dbgs() << "** Tried : ";);
189 LLVM_DEBUG(HazardRec->dumpSU(c.SU, dbgs()); c.dumpCosts();
190 dbgs() << " Height:" << c.SU->getHeight(); dbgs() << "\n";);
191
192 // Once we know we have seen all SUs that affect grouping or use unbuffered
193 // resources, we can stop iterating if Best looks good.
194 if (!SU->isScheduleHigh && Best.noCost())
195 break;
196 }
197
198 assert (Best.SU != nullptr);
199 return Best.SU;
200}
201
202SystemZPostRASchedStrategy::Candidate::
203Candidate(SUnit *SU_, SystemZHazardRecognizer &HazardRec) : Candidate() {
204 SU = SU_;
205
206 // Check the grouping cost. For a node that must begin / end a
207 // group, it is positive if it would do so prematurely, or negative
208 // if it would fit naturally into the schedule.
209 GroupingCost = HazardRec.groupingCost(SU);
210
211 // Check the resources cost for this SU.
212 ResourcesCost = HazardRec.resourcesCost(SU);
213}
214
215bool SystemZPostRASchedStrategy::Candidate::
216operator<(const Candidate &other) {
217
218 // Check decoder grouping.
219 if (GroupingCost < other.GroupingCost)
220 return true;
221 if (GroupingCost > other.GroupingCost)
222 return false;
223
224 // Compare the use of resources.
225 if (ResourcesCost < other.ResourcesCost)
226 return true;
227 if (ResourcesCost > other.ResourcesCost)
228 return false;
229
230 // Higher SU is otherwise generally better.
231 if (SU->getHeight() > other.SU->getHeight())
232 return true;
233 if (SU->getHeight() < other.SU->getHeight())
234 return false;
235
236 // If all same, fall back to original order.
237 if (SU->NodeNum < other.SU->NodeNum)
238 return true;
239
240 return false;
241}
242
243void SystemZPostRASchedStrategy::schedNode(SUnit *SU, bool IsTopNode) {
244 LLVM_DEBUG(dbgs() << "** Scheduling SU(" << SU->NodeNum << ") ";
245 if (Available.size() == 1) dbgs() << "(only one) ";
246 Candidate c(SU, *HazardRec); c.dumpCosts(); dbgs() << "\n";);
247
248 // Remove SU from Available set and update HazardRec.
249 Available.erase(x: SU);
250 HazardRec->EmitInstruction(SU);
251}
252
253void SystemZPostRASchedStrategy::releaseTopNode(SUnit *SU) {
254 // Set isScheduleHigh flag on all SUs that we want to consider first in
255 // pickNode().
256 const MCSchedClassDesc *SC = HazardRec->getSchedClass(SU);
257 bool AffectsGrouping = (SC->isValid() && (SC->BeginGroup || SC->EndGroup));
258 SU->isScheduleHigh = (AffectsGrouping || SU->isUnbuffered);
259
260 // Put all released SUs in the Available set.
261 Available.insert(x: SU);
262}
263