LLVM 19.0.0git
SystemZMachineScheduler.cpp
Go to the documentation of this file.
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
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.
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(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();
64 ((LastEmittedMI != nullptr && LastEmittedMI->getParent() == MBB) ?
65 std::next(LastEmittedMI) : MBB->begin());
66
67 for (; I != NextBegin; ++I) {
68 if (I->isPosition() || I->isDebugInstr())
69 continue;
70 HazardRec->emitInstruction(&*I);
71 }
72}
73
75 Available.clear(); // -misched-cutoff.
76 LLVM_DEBUG(HazardRec->dumpState(););
77}
78
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, MLI->getLoopFor(MBB));
97 if (SinglePredMBB == nullptr ||
98 SchedStates.find(SinglePredMBB) == SchedStates.end())
99 return;
100
101 LLVM_DEBUG(dbgs() << "** Continued scheduling from "
102 << printMBBReference(*SinglePredMBB) << "\n";);
103
104 HazardRec->copyState(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, TakenBranch);
115 if (TakenBranch)
116 break;
117 }
118}
119
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(MBB->getFirstTerminator());
126}
127
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(ST);
136}
137
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
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(Begin);
155}
156
157// Pick the next node to schedule.
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
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(SU);
248 HazardRec->EmitInstruction(SU);
249}
250
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(SU);
260}
aarch64 promote const
MachineBasicBlock & MBB
#define LLVM_DEBUG(X)
Definition: Debug.h:101
bool End
Definition: ELF_riscv.cpp:480
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition: MD5.cpp:58
if(VerifyEach)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static MachineBasicBlock * getSingleSchedPred(MachineBasicBlock *MBB, const MachineLoop *Loop)
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
BlockT * getHeader() const
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
unsigned pred_size() const
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
iterator_range< pred_iterator > predecessors()
Representation of each machine instruction.
Definition: MachineInstr.h:68
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
void dump() const
Definition: Pass.cpp:136
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
unsigned NodeNum
Entry # of node in the node vector.
Definition: ScheduleDAG.h:264
bool isUnbuffered
Uses an unbuffered resource.
Definition: ScheduleDAG.h:288
bool isScheduleHigh
True if preferable to schedule high.
Definition: ScheduleDAG.h:285
ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply schedules machine instructions ac...
SystemZHazardRecognizer maintains the state for one MBB during scheduling.
int groupingCost(SUnit *SU) const
Return the cost of decoder grouping for SU.
void emitInstruction(MachineInstr *MI, bool TakenBranch=false)
Wrap a non-scheduled instruction in an SU and emit it.
const MCSchedClassDesc * getSchedClass(SUnit *SU) const
Resolves and cache a resolved scheduling class for an SUnit.
void copyState(SystemZHazardRecognizer *Incoming)
Copy counters from end of single predecessor.
void dumpSU(SUnit *SU, raw_ostream &OS) const
MachineBasicBlock::iterator getLastEmittedMI()
int resourcesCost(SUnit *SU)
Return the cost of SU in regards to processor resources usage.
void EmitInstruction(SUnit *SU) override
EmitInstruction - This callback is invoked when an instruction is emitted, to advance the hazard stat...
MachineBasicBlock * getMBBTarget()
SystemZII::Branch getBranchInfo(const MachineInstr &MI) const
SUnit * pickNode(bool &IsTopNode) override
Pick the next node to schedule, or return NULL.
void leaveMBB() override
Tell the strategy that current MBB is done.
void initPolicy(MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned NumRegionInstrs) override
Called for a region before scheduling.
void schedNode(SUnit *SU, bool IsTopNode) override
ScheduleDAGMI has scheduled an instruction - tell HazardRec about it.
void initialize(ScheduleDAGMI *dag) override
Initialize the strategy after building the DAG for a new region.
void enterMBB(MachineBasicBlock *NextMBB) override
Tell the strategy that MBB is about to be processed.
SystemZPostRASchedStrategy(const MachineSchedContext *C)
void releaseTopNode(SUnit *SU) override
SU has had all predecessor dependencies resolved.
void init(const TargetSubtargetInfo *TSInfo)
Initialize the machine model for instruction scheduling.
TargetSubtargetInfo - Generic base class for all target subtargets.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Summarize the scheduling resources required for an instruction of a particular scheduling class.
Definition: MCSchedule.h:118
MachineSchedContext provides enough context from the MachineScheduler pass for the target to instanti...