/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Target/SystemZ/SystemZMachineScheduler.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //-- SystemZMachineScheduler.cpp - SystemZ Scheduler Interface -*- C++ -*---==// |
2 | | // |
3 | | // The LLVM Compiler Infrastructure |
4 | | // |
5 | | // This file is distributed under the University of Illinois Open Source |
6 | | // License. See LICENSE.TXT for details. |
7 | | // |
8 | | //===----------------------------------------------------------------------===// |
9 | | // |
10 | | // -------------------------- Post RA scheduling ---------------------------- // |
11 | | // SystemZPostRASchedStrategy is a scheduling strategy which is plugged into |
12 | | // the MachineScheduler. It has a sorted Available set of SUs and a pickNode() |
13 | | // implementation that looks to optimize decoder grouping and balance the |
14 | | // usage of processor resources. Scheduler states are saved for the end |
15 | | // region of each MBB, so that a successor block can learn from it. |
16 | | //===----------------------------------------------------------------------===// |
17 | | |
18 | | #include "SystemZMachineScheduler.h" |
19 | | |
20 | | using namespace llvm; |
21 | | |
22 | | #define DEBUG_TYPE "machine-scheduler" |
23 | | |
24 | | #ifndef NDEBUG |
25 | | // Print the set of SUs |
26 | | void SystemZPostRASchedStrategy::SUSet:: |
27 | | dump(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. |
40 | | static MachineBasicBlock *getSingleSchedPred(MachineBasicBlock *MBB, |
41 | 3.25k | const MachineLoop *Loop) { |
42 | 3.25k | MachineBasicBlock *PredMBB = nullptr; |
43 | 3.25k | if (MBB->pred_size() == 1) |
44 | 243 | PredMBB = *MBB->pred_begin(); |
45 | 3.25k | |
46 | 3.25k | // The loop header has two predecessors, return the latch, but not for a |
47 | 3.25k | // single block loop. |
48 | 3.25k | if (MBB->pred_size() == 2 && 3.25k Loop != nullptr124 && Loop->getHeader() == MBB63 ) { |
49 | 177 | for (auto I = MBB->pred_begin(); I != MBB->pred_end()177 ; ++I118 ) |
50 | 118 | if (118 Loop->contains(*I)118 ) |
51 | 118 | PredMBB = (*I == MBB ? 59 nullptr52 : *I7 ); |
52 | 59 | } |
53 | 3.25k | |
54 | 3.25k | assert ((PredMBB == nullptr || !Loop || Loop->contains(PredMBB)) |
55 | 3.25k | && "Loop MBB should not consider predecessor outside of loop."); |
56 | 3.25k | |
57 | 3.25k | return PredMBB; |
58 | 3.25k | } |
59 | | |
60 | | void SystemZPostRASchedStrategy:: |
61 | 7.02k | advanceTo(MachineBasicBlock::iterator NextBegin) { |
62 | 7.02k | MachineBasicBlock::iterator LastEmittedMI = HazardRec->getLastEmittedMI(); |
63 | 7.02k | MachineBasicBlock::iterator I = |
64 | 2.41k | ((LastEmittedMI != nullptr && LastEmittedMI->getParent() == MBB) ? |
65 | 7.02k | std::next(LastEmittedMI)2.07k : MBB->begin()4.95k ); |
66 | 7.02k | |
67 | 11.1k | for (; I != NextBegin11.1k ; ++I4.08k ) { |
68 | 4.08k | if (I->isPosition() || 4.08k I->isDebugValue()1.88k ) |
69 | 2.19k | continue; |
70 | 1.88k | HazardRec->emitInstruction(&*I); |
71 | 1.88k | } |
72 | 7.02k | } |
73 | | |
74 | 3.25k | void SystemZPostRASchedStrategy::enterMBB(MachineBasicBlock *NextMBB) { |
75 | 3.25k | assert ((SchedStates.find(NextMBB) == SchedStates.end()) && |
76 | 3.25k | "Entering MBB twice?"); |
77 | 3.25k | DEBUG (dbgs() << "+++ Entering MBB#" << NextMBB->getNumber()); |
78 | 3.25k | |
79 | 3.25k | MBB = NextMBB; |
80 | 3.25k | /// Create a HazardRec for MBB, save it in SchedStates and set HazardRec to |
81 | 3.25k | /// point to it. |
82 | 3.25k | HazardRec = SchedStates[MBB] = new SystemZHazardRecognizer(TII, &SchedModel); |
83 | 3.25k | DEBUG (const MachineLoop *Loop = MLI->getLoopFor(MBB); |
84 | 3.25k | if(Loop && Loop->getHeader() == MBB) |
85 | 3.25k | dbgs() << " (Loop header)"; |
86 | 3.25k | dbgs() << ":\n";); |
87 | 3.25k | |
88 | 3.25k | // Try to take over the state from a single predecessor, if it has been |
89 | 3.25k | // scheduled. If this is not possible, we are done. |
90 | 3.25k | MachineBasicBlock *SinglePredMBB = |
91 | 3.25k | getSingleSchedPred(MBB, MLI->getLoopFor(MBB)); |
92 | 3.25k | if (SinglePredMBB == nullptr || |
93 | 250 | SchedStates.find(SinglePredMBB) == SchedStates.end()) |
94 | 3.00k | return; |
95 | 243 | |
96 | 243 | DEBUG243 (dbgs() << "+++ Continued scheduling from MBB#" |
97 | 243 | << SinglePredMBB->getNumber() << "\n";); |
98 | 243 | |
99 | 243 | HazardRec->copyState(SchedStates[SinglePredMBB]); |
100 | 243 | |
101 | 243 | // Emit incoming terminator(s). Be optimistic and assume that branch |
102 | 243 | // prediction will generally do "the right thing". |
103 | 243 | for (MachineBasicBlock::iterator I = SinglePredMBB->getFirstTerminator(); |
104 | 469 | I != SinglePredMBB->end()469 ; I++226 ) { |
105 | 243 | DEBUG (dbgs() << "+++ Emitting incoming branch: "; I->dump();); |
106 | 243 | bool TakenBranch = (I->isBranch() && |
107 | 146 | (TII->getBranchInfo(*I).Target->isReg() || // Relative branch |
108 | 146 | TII->getBranchInfo(*I).Target->getMBB() == MBB)); |
109 | 243 | HazardRec->emitInstruction(&*I, TakenBranch); |
110 | 243 | if (TakenBranch) |
111 | 17 | break; |
112 | 243 | } |
113 | 3.25k | } |
114 | | |
115 | 3.25k | void SystemZPostRASchedStrategy::leaveMBB() { |
116 | 3.25k | DEBUG (dbgs() << "+++ Leaving MBB#" << MBB->getNumber() << "\n";); |
117 | 3.25k | |
118 | 3.25k | // Advance to first terminator. The successor block will handle terminators |
119 | 3.25k | // dependent on CFG layout (T/NT branch etc). |
120 | 3.25k | advanceTo(MBB->getFirstTerminator()); |
121 | 3.25k | } |
122 | | |
123 | | SystemZPostRASchedStrategy:: |
124 | | SystemZPostRASchedStrategy(const MachineSchedContext *C) |
125 | | : MLI(C->MLI), |
126 | | TII(static_cast<const SystemZInstrInfo *> |
127 | | (C->MF->getSubtarget().getInstrInfo())), |
128 | 2.85k | MBB(nullptr), HazardRec(nullptr) { |
129 | 2.85k | const TargetSubtargetInfo *ST = &C->MF->getSubtarget(); |
130 | 2.85k | SchedModel.init(ST->getSchedModel(), ST, TII); |
131 | 2.85k | } |
132 | | |
133 | 2.85k | SystemZPostRASchedStrategy::~SystemZPostRASchedStrategy() { |
134 | 2.85k | // Delete hazard recognizers kept around for each MBB. |
135 | 3.25k | for (auto I : SchedStates) { |
136 | 3.25k | SystemZHazardRecognizer *hazrec = I.second; |
137 | 3.25k | delete hazrec; |
138 | 3.25k | } |
139 | 2.85k | } |
140 | | |
141 | | void SystemZPostRASchedStrategy::initPolicy(MachineBasicBlock::iterator Begin, |
142 | | MachineBasicBlock::iterator End, |
143 | 3.90k | unsigned NumRegionInstrs) { |
144 | 3.90k | // Don't emit the terminators. |
145 | 3.90k | if (Begin->isTerminator()) |
146 | 125 | return; |
147 | 3.77k | |
148 | 3.77k | // Emit any instructions before start of region. |
149 | 3.77k | advanceTo(Begin); |
150 | 3.77k | } |
151 | | |
152 | | // Pick the next node to schedule. |
153 | 13.8k | SUnit *SystemZPostRASchedStrategy::pickNode(bool &IsTopNode) { |
154 | 13.8k | // Only scheduling top-down. |
155 | 13.8k | IsTopNode = true; |
156 | 13.8k | |
157 | 13.8k | if (Available.empty()) |
158 | 1.59k | return nullptr; |
159 | 12.2k | |
160 | 12.2k | // If only one choice, return it. |
161 | 12.2k | if (12.2k Available.size() == 112.2k ) { |
162 | 6.72k | DEBUG (dbgs() << "+++ Only one: "; |
163 | 6.72k | HazardRec->dumpSU(*Available.begin(), dbgs()); dbgs() << "\n";); |
164 | 6.72k | return *Available.begin(); |
165 | 6.72k | } |
166 | 5.56k | |
167 | 5.56k | // All nodes that are possible to schedule are stored by in the |
168 | 5.56k | // Available set. |
169 | 5.56k | DEBUG5.56k (dbgs() << "+++ Available: "; Available.dump(*HazardRec);); |
170 | 5.56k | |
171 | 5.56k | Candidate Best; |
172 | 8.03k | for (auto *SU : Available) { |
173 | 8.03k | |
174 | 8.03k | // SU is the next candidate to be compared against current Best. |
175 | 8.03k | Candidate c(SU, *HazardRec); |
176 | 8.03k | |
177 | 8.03k | // Remeber which SU is the best candidate. |
178 | 8.03k | if (Best.SU == nullptr || 8.03k c < Best2.46k ) { |
179 | 5.98k | Best = c; |
180 | 5.98k | DEBUG(dbgs() << "+++ Best sofar: "; |
181 | 5.98k | HazardRec->dumpSU(Best.SU, dbgs()); |
182 | 5.98k | if (Best.GroupingCost != 0) |
183 | 5.98k | dbgs() << "\tGrouping cost:" << Best.GroupingCost; |
184 | 5.98k | if (Best.ResourcesCost != 0) |
185 | 5.98k | dbgs() << " Resource cost:" << Best.ResourcesCost; |
186 | 5.98k | dbgs() << " Height:" << Best.SU->getHeight(); |
187 | 5.98k | dbgs() << "\n";); |
188 | 5.98k | } |
189 | 8.03k | |
190 | 8.03k | // Once we know we have seen all SUs that affect grouping or use unbuffered |
191 | 8.03k | // resources, we can stop iterating if Best looks good. |
192 | 8.03k | if (!SU->isScheduleHigh && 8.03k Best.noCost()7.96k ) |
193 | 4.40k | break; |
194 | 5.56k | } |
195 | 5.56k | |
196 | 5.56k | assert (Best.SU != nullptr); |
197 | 13.8k | return Best.SU; |
198 | 13.8k | } |
199 | | |
200 | | SystemZPostRASchedStrategy::Candidate:: |
201 | 8.03k | Candidate(SUnit *SU_, SystemZHazardRecognizer &HazardRec) : Candidate() { |
202 | 8.03k | SU = SU_; |
203 | 8.03k | |
204 | 8.03k | // Check the grouping cost. For a node that must begin / end a |
205 | 8.03k | // group, it is positive if it would do so prematurely, or negative |
206 | 8.03k | // if it would fit naturally into the schedule. |
207 | 8.03k | GroupingCost = HazardRec.groupingCost(SU); |
208 | 8.03k | |
209 | 8.03k | // Check the resources cost for this SU. |
210 | 8.03k | ResourcesCost = HazardRec.resourcesCost(SU); |
211 | 8.03k | } Unexecuted instantiation: llvm::SystemZPostRASchedStrategy::Candidate::Candidate(llvm::SUnit*, llvm::SystemZHazardRecognizer&) llvm::SystemZPostRASchedStrategy::Candidate::Candidate(llvm::SUnit*, llvm::SystemZHazardRecognizer&) Line | Count | Source | 201 | 8.03k | Candidate(SUnit *SU_, SystemZHazardRecognizer &HazardRec) : Candidate() { | 202 | 8.03k | SU = SU_; | 203 | 8.03k | | 204 | 8.03k | // Check the grouping cost. For a node that must begin / end a | 205 | 8.03k | // group, it is positive if it would do so prematurely, or negative | 206 | 8.03k | // if it would fit naturally into the schedule. | 207 | 8.03k | GroupingCost = HazardRec.groupingCost(SU); | 208 | 8.03k | | 209 | 8.03k | // Check the resources cost for this SU. | 210 | 8.03k | ResourcesCost = HazardRec.resourcesCost(SU); | 211 | 8.03k | } |
|
212 | | |
213 | | bool SystemZPostRASchedStrategy::Candidate:: |
214 | 2.46k | operator<(const Candidate &other) { |
215 | 2.46k | |
216 | 2.46k | // Check decoder grouping. |
217 | 2.46k | if (GroupingCost < other.GroupingCost) |
218 | 24 | return true; |
219 | 2.43k | if (2.43k GroupingCost > other.GroupingCost2.43k ) |
220 | 27 | return false; |
221 | 2.41k | |
222 | 2.41k | // Compare the use of resources. |
223 | 2.41k | if (2.41k ResourcesCost < other.ResourcesCost2.41k ) |
224 | 396 | return true; |
225 | 2.01k | if (2.01k ResourcesCost > other.ResourcesCost2.01k ) |
226 | 396 | return false; |
227 | 1.61k | |
228 | 1.61k | // Higher SU is otherwise generally better. |
229 | 1.61k | if (1.61k SU->getHeight() > other.SU->getHeight()1.61k ) |
230 | 0 | return true; |
231 | 1.61k | if (1.61k SU->getHeight() < other.SU->getHeight()1.61k ) |
232 | 904 | return false; |
233 | 715 | |
234 | 715 | // If all same, fall back to original order. |
235 | 715 | if (715 SU->NodeNum < other.SU->NodeNum715 ) |
236 | 0 | return true; |
237 | 715 | |
238 | 715 | return false; |
239 | 715 | } |
240 | | |
241 | 12.2k | void SystemZPostRASchedStrategy::schedNode(SUnit *SU, bool IsTopNode) { |
242 | 12.2k | DEBUG(dbgs() << "+++ Scheduling SU(" << SU->NodeNum << ")\n";); |
243 | 12.2k | |
244 | 12.2k | // Remove SU from Available set and update HazardRec. |
245 | 12.2k | Available.erase(SU); |
246 | 12.2k | HazardRec->EmitInstruction(SU); |
247 | 12.2k | } |
248 | | |
249 | 12.2k | void SystemZPostRASchedStrategy::releaseTopNode(SUnit *SU) { |
250 | 12.2k | // Set isScheduleHigh flag on all SUs that we want to consider first in |
251 | 12.2k | // pickNode(). |
252 | 12.2k | const MCSchedClassDesc *SC = HazardRec->getSchedClass(SU); |
253 | 12.0k | bool AffectsGrouping = (SC->isValid() && (SC->BeginGroup || 12.0k SC->EndGroup11.8k )); |
254 | 11.8k | SU->isScheduleHigh = (AffectsGrouping || SU->isUnbuffered); |
255 | 12.2k | |
256 | 12.2k | // Put all released SUs in the Available set. |
257 | 12.2k | Available.insert(SU); |
258 | 12.2k | } |