/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/SystemZ/SystemZMachineScheduler.cpp
Line | Count | Source (jump to first uncovered line) |
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 | | |
19 | | using namespace llvm; |
20 | | |
21 | | #define DEBUG_TYPE "machine-scheduler" |
22 | | |
23 | | #ifndef NDEBUG |
24 | | // Print the set of SUs |
25 | | void SystemZPostRASchedStrategy::SUSet:: |
26 | | dump(SystemZHazardRecognizer &HazardRec) const { |
27 | | dbgs() << "{"; |
28 | | for (auto &SU : *this) { |
29 | | HazardRec.dumpSU(SU, dbgs()); |
30 | | if (SU != *rbegin()) |
31 | | dbgs() << ", "; |
32 | | } |
33 | | dbgs() << "}\n"; |
34 | | } |
35 | | #endif |
36 | | |
37 | | // Try to find a single predecessor that would be interesting for the |
38 | | // scheduler in the top-most region of MBB. |
39 | | static MachineBasicBlock *getSingleSchedPred(MachineBasicBlock *MBB, |
40 | 4.17k | const MachineLoop *Loop) { |
41 | 4.17k | MachineBasicBlock *PredMBB = nullptr; |
42 | 4.17k | if (MBB->pred_size() == 1) |
43 | 311 | PredMBB = *MBB->pred_begin(); |
44 | 4.17k | |
45 | 4.17k | // The loop header has two predecessors, return the latch, but not for a |
46 | 4.17k | // single block loop. |
47 | 4.17k | if (MBB->pred_size() == 2 && Loop != nullptr155 && Loop->getHeader() == MBB83 ) { |
48 | 237 | for (auto I = MBB->pred_begin(); I != MBB->pred_end(); ++I158 ) |
49 | 158 | if (Loop->contains(*I)) |
50 | 79 | PredMBB = (*I == MBB ? nullptr67 : *I12 ); |
51 | 79 | } |
52 | 4.17k | |
53 | 4.17k | assert ((PredMBB == nullptr || !Loop || Loop->contains(PredMBB)) |
54 | 4.17k | && "Loop MBB should not consider predecessor outside of loop."); |
55 | 4.17k | |
56 | 4.17k | return PredMBB; |
57 | 4.17k | } |
58 | | |
59 | | void SystemZPostRASchedStrategy:: |
60 | 8.65k | advanceTo(MachineBasicBlock::iterator NextBegin) { |
61 | 8.65k | MachineBasicBlock::iterator LastEmittedMI = HazardRec->getLastEmittedMI(); |
62 | 8.65k | MachineBasicBlock::iterator I = |
63 | 8.65k | ((LastEmittedMI != nullptr && LastEmittedMI->getParent() == MBB2.75k ) ? |
64 | 6.33k | std::next(LastEmittedMI)2.32k : MBB->begin()); |
65 | 8.65k | |
66 | 12.4k | for (; I != NextBegin; ++I3.78k ) { |
67 | 3.78k | if (I->isPosition() || I->isDebugInstr()2.72k ) |
68 | 1.05k | continue; |
69 | 2.72k | HazardRec->emitInstruction(&*I); |
70 | 2.72k | } |
71 | 8.65k | } |
72 | | |
73 | 2.28k | void SystemZPostRASchedStrategy::initialize(ScheduleDAGMI *dag) { |
74 | 2.28k | LLVM_DEBUG(HazardRec->dumpState();); |
75 | 2.28k | } |
76 | | |
77 | 4.17k | void SystemZPostRASchedStrategy::enterMBB(MachineBasicBlock *NextMBB) { |
78 | 4.17k | assert ((SchedStates.find(NextMBB) == SchedStates.end()) && |
79 | 4.17k | "Entering MBB twice?"); |
80 | 4.17k | LLVM_DEBUG(dbgs() << "** Entering " << printMBBReference(*NextMBB)); |
81 | 4.17k | |
82 | 4.17k | MBB = NextMBB; |
83 | 4.17k | |
84 | 4.17k | /// Create a HazardRec for MBB, save it in SchedStates and set HazardRec to |
85 | 4.17k | /// point to it. |
86 | 4.17k | HazardRec = SchedStates[MBB] = new SystemZHazardRecognizer(TII, &SchedModel); |
87 | 4.17k | LLVM_DEBUG(const MachineLoop *Loop = MLI->getLoopFor(MBB); |
88 | 4.17k | if (Loop && Loop->getHeader() == MBB) dbgs() << " (Loop header)"; |
89 | 4.17k | dbgs() << ":\n";); |
90 | 4.17k | |
91 | 4.17k | // Try to take over the state from a single predecessor, if it has been |
92 | 4.17k | // scheduled. If this is not possible, we are done. |
93 | 4.17k | MachineBasicBlock *SinglePredMBB = |
94 | 4.17k | getSingleSchedPred(MBB, MLI->getLoopFor(MBB)); |
95 | 4.17k | if (SinglePredMBB == nullptr || |
96 | 4.17k | SchedStates.find(SinglePredMBB) == SchedStates.end()323 ) |
97 | 3.86k | return; |
98 | 311 | |
99 | 311 | LLVM_DEBUG(dbgs() << "** Continued scheduling from " |
100 | 311 | << printMBBReference(*SinglePredMBB) << "\n";); |
101 | 311 | |
102 | 311 | HazardRec->copyState(SchedStates[SinglePredMBB]); |
103 | 311 | LLVM_DEBUG(HazardRec->dumpState();); |
104 | 311 | |
105 | 311 | // Emit incoming terminator(s). Be optimistic and assume that branch |
106 | 311 | // prediction will generally do "the right thing". |
107 | 311 | for (MachineBasicBlock::iterator I = SinglePredMBB->getFirstTerminator(); |
108 | 598 | I != SinglePredMBB->end(); I++287 ) { |
109 | 310 | LLVM_DEBUG(dbgs() << "** Emitting incoming branch: "; I->dump();); |
110 | 310 | bool TakenBranch = (I->isBranch() && |
111 | 310 | (184 TII->getBranchInfo(*I).Target->isReg()184 || // Relative branch |
112 | 184 | TII->getBranchInfo(*I).Target->getMBB() == MBB173 )); |
113 | 310 | HazardRec->emitInstruction(&*I, TakenBranch); |
114 | 310 | if (TakenBranch) |
115 | 23 | break; |
116 | 310 | } |
117 | 311 | } |
118 | | |
119 | 4.17k | void SystemZPostRASchedStrategy::leaveMBB() { |
120 | 4.17k | LLVM_DEBUG(dbgs() << "** Leaving " << printMBBReference(*MBB) << "\n";); |
121 | 4.17k | |
122 | 4.17k | // Advance to first terminator. The successor block will handle terminators |
123 | 4.17k | // dependent on CFG layout (T/NT branch etc). |
124 | 4.17k | advanceTo(MBB->getFirstTerminator()); |
125 | 4.17k | } |
126 | | |
127 | | SystemZPostRASchedStrategy:: |
128 | | SystemZPostRASchedStrategy(const MachineSchedContext *C) |
129 | | : MLI(C->MLI), |
130 | | TII(static_cast<const SystemZInstrInfo *> |
131 | | (C->MF->getSubtarget().getInstrInfo())), |
132 | 3.68k | MBB(nullptr), HazardRec(nullptr) { |
133 | 3.68k | const TargetSubtargetInfo *ST = &C->MF->getSubtarget(); |
134 | 3.68k | SchedModel.init(ST); |
135 | 3.68k | } |
136 | | |
137 | 3.68k | SystemZPostRASchedStrategy::~SystemZPostRASchedStrategy() { |
138 | 3.68k | // Delete hazard recognizers kept around for each MBB. |
139 | 4.17k | for (auto I : SchedStates) { |
140 | 4.17k | SystemZHazardRecognizer *hazrec = I.second; |
141 | 4.17k | delete hazrec; |
142 | 4.17k | } |
143 | 3.68k | } |
144 | | |
145 | | void SystemZPostRASchedStrategy::initPolicy(MachineBasicBlock::iterator Begin, |
146 | | MachineBasicBlock::iterator End, |
147 | 4.47k | unsigned NumRegionInstrs) { |
148 | 4.47k | // Don't emit the terminators. |
149 | 4.47k | if (Begin->isTerminator()) |
150 | 0 | return; |
151 | 4.47k | |
152 | 4.47k | // Emit any instructions before start of region. |
153 | 4.47k | advanceTo(Begin); |
154 | 4.47k | } |
155 | | |
156 | | // Pick the next node to schedule. |
157 | 23.9k | SUnit *SystemZPostRASchedStrategy::pickNode(bool &IsTopNode) { |
158 | 23.9k | // Only scheduling top-down. |
159 | 23.9k | IsTopNode = true; |
160 | 23.9k | |
161 | 23.9k | if (Available.empty()) |
162 | 2.28k | return nullptr; |
163 | 21.6k | |
164 | 21.6k | // If only one choice, return it. |
165 | 21.6k | if (Available.size() == 1) { |
166 | 15.0k | LLVM_DEBUG(dbgs() << "** Only one: "; |
167 | 15.0k | HazardRec->dumpSU(*Available.begin(), dbgs()); dbgs() << "\n";); |
168 | 15.0k | return *Available.begin(); |
169 | 15.0k | } |
170 | 6.58k | |
171 | 6.58k | // All nodes that are possible to schedule are stored in the Available set. |
172 | 6.58k | LLVM_DEBUG(dbgs() << "** Available: "; Available.dump(*HazardRec);); |
173 | 6.58k | |
174 | 6.58k | Candidate Best; |
175 | 12.7k | for (auto *SU : Available) { |
176 | 12.7k | |
177 | 12.7k | // SU is the next candidate to be compared against current Best. |
178 | 12.7k | Candidate c(SU, *HazardRec); |
179 | 12.7k | |
180 | 12.7k | // Remeber which SU is the best candidate. |
181 | 12.7k | if (Best.SU == nullptr || c < Best6.15k ) { |
182 | 7.38k | Best = c; |
183 | 7.38k | LLVM_DEBUG(dbgs() << "** Best so far: ";); |
184 | 7.38k | } else |
185 | 12.7k | LLVM_DEBUG(dbgs() << "** Tried : ";); |
186 | 12.7k | LLVM_DEBUG(HazardRec->dumpSU(c.SU, dbgs()); c.dumpCosts(); |
187 | 12.7k | dbgs() << " Height:" << c.SU->getHeight(); dbgs() << "\n";); |
188 | 12.7k | |
189 | 12.7k | // Once we know we have seen all SUs that affect grouping or use unbuffered |
190 | 12.7k | // resources, we can stop iterating if Best looks good. |
191 | 12.7k | if (!SU->isScheduleHigh && Best.noCost()12.4k ) |
192 | 4.72k | break; |
193 | 12.7k | } |
194 | 6.58k | |
195 | 6.58k | assert (Best.SU != nullptr); |
196 | 6.58k | return Best.SU; |
197 | 6.58k | } |
198 | | |
199 | | SystemZPostRASchedStrategy::Candidate:: |
200 | 12.7k | Candidate(SUnit *SU_, SystemZHazardRecognizer &HazardRec) : Candidate() { |
201 | 12.7k | SU = SU_; |
202 | 12.7k | |
203 | 12.7k | // Check the grouping cost. For a node that must begin / end a |
204 | 12.7k | // group, it is positive if it would do so prematurely, or negative |
205 | 12.7k | // if it would fit naturally into the schedule. |
206 | 12.7k | GroupingCost = HazardRec.groupingCost(SU); |
207 | 12.7k | |
208 | 12.7k | // Check the resources cost for this SU. |
209 | 12.7k | ResourcesCost = HazardRec.resourcesCost(SU); |
210 | 12.7k | } Unexecuted instantiation: llvm::SystemZPostRASchedStrategy::Candidate::Candidate(llvm::SUnit*, llvm::SystemZHazardRecognizer&) llvm::SystemZPostRASchedStrategy::Candidate::Candidate(llvm::SUnit*, llvm::SystemZHazardRecognizer&) Line | Count | Source | 200 | 12.7k | Candidate(SUnit *SU_, SystemZHazardRecognizer &HazardRec) : Candidate() { | 201 | 12.7k | SU = SU_; | 202 | 12.7k | | 203 | 12.7k | // Check the grouping cost. For a node that must begin / end a | 204 | 12.7k | // group, it is positive if it would do so prematurely, or negative | 205 | 12.7k | // if it would fit naturally into the schedule. | 206 | 12.7k | GroupingCost = HazardRec.groupingCost(SU); | 207 | 12.7k | | 208 | 12.7k | // Check the resources cost for this SU. | 209 | 12.7k | ResourcesCost = HazardRec.resourcesCost(SU); | 210 | 12.7k | } |
|
211 | | |
212 | | bool SystemZPostRASchedStrategy::Candidate:: |
213 | 6.15k | operator<(const Candidate &other) { |
214 | 6.15k | |
215 | 6.15k | // Check decoder grouping. |
216 | 6.15k | if (GroupingCost < other.GroupingCost) |
217 | 132 | return true; |
218 | 6.02k | if (GroupingCost > other.GroupingCost) |
219 | 73 | return false; |
220 | 5.94k | |
221 | 5.94k | // Compare the use of resources. |
222 | 5.94k | if (ResourcesCost < other.ResourcesCost) |
223 | 671 | return true; |
224 | 5.27k | if (ResourcesCost > other.ResourcesCost) |
225 | 48 | return false; |
226 | 5.22k | |
227 | 5.22k | // Higher SU is otherwise generally better. |
228 | 5.22k | if (SU->getHeight() > other.SU->getHeight()) |
229 | 0 | return true; |
230 | 5.22k | if (SU->getHeight() < other.SU->getHeight()) |
231 | 3.72k | return false; |
232 | 1.50k | |
233 | 1.50k | // If all same, fall back to original order. |
234 | 1.50k | if (SU->NodeNum < other.SU->NodeNum) |
235 | 0 | return true; |
236 | 1.50k | |
237 | 1.50k | return false; |
238 | 1.50k | } |
239 | | |
240 | 21.6k | void SystemZPostRASchedStrategy::schedNode(SUnit *SU, bool IsTopNode) { |
241 | 21.6k | LLVM_DEBUG(dbgs() << "** Scheduling SU(" << SU->NodeNum << ") "; |
242 | 21.6k | if (Available.size() == 1) dbgs() << "(only one) "; |
243 | 21.6k | Candidate c(SU, *HazardRec); c.dumpCosts(); dbgs() << "\n";); |
244 | 21.6k | |
245 | 21.6k | // Remove SU from Available set and update HazardRec. |
246 | 21.6k | Available.erase(SU); |
247 | 21.6k | HazardRec->EmitInstruction(SU); |
248 | 21.6k | } |
249 | | |
250 | 21.6k | void SystemZPostRASchedStrategy::releaseTopNode(SUnit *SU) { |
251 | 21.6k | // Set isScheduleHigh flag on all SUs that we want to consider first in |
252 | 21.6k | // pickNode(). |
253 | 21.6k | const MCSchedClassDesc *SC = HazardRec->getSchedClass(SU); |
254 | 21.6k | bool AffectsGrouping = (SC->isValid() && (21.1k SC->BeginGroup21.1k || SC->EndGroup20.6k )); |
255 | 21.6k | SU->isScheduleHigh = (AffectsGrouping || SU->isUnbuffered21.0k ); |
256 | 21.6k | |
257 | 21.6k | // Put all released SUs in the Available set. |
258 | 21.6k | Available.insert(SU); |
259 | 21.6k | } |