/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/AggressiveAntiDepBreaker.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- AggressiveAntiDepBreaker.cpp - Anti-dep breaker --------------------===// |
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 | | // This file implements the AggressiveAntiDepBreaker class, which |
10 | | // implements register anti-dependence breaking during post-RA |
11 | | // scheduling. It attempts to break all anti-dependencies within a |
12 | | // block. |
13 | | // |
14 | | //===----------------------------------------------------------------------===// |
15 | | |
16 | | #include "AggressiveAntiDepBreaker.h" |
17 | | #include "llvm/ADT/ArrayRef.h" |
18 | | #include "llvm/ADT/BitVector.h" |
19 | | #include "llvm/ADT/SmallSet.h" |
20 | | #include "llvm/ADT/iterator_range.h" |
21 | | #include "llvm/CodeGen/MachineBasicBlock.h" |
22 | | #include "llvm/CodeGen/MachineFrameInfo.h" |
23 | | #include "llvm/CodeGen/MachineFunction.h" |
24 | | #include "llvm/CodeGen/MachineInstr.h" |
25 | | #include "llvm/CodeGen/MachineOperand.h" |
26 | | #include "llvm/CodeGen/MachineRegisterInfo.h" |
27 | | #include "llvm/CodeGen/RegisterClassInfo.h" |
28 | | #include "llvm/CodeGen/ScheduleDAG.h" |
29 | | #include "llvm/CodeGen/TargetInstrInfo.h" |
30 | | #include "llvm/CodeGen/TargetRegisterInfo.h" |
31 | | #include "llvm/CodeGen/TargetSubtargetInfo.h" |
32 | | #include "llvm/MC/MCInstrDesc.h" |
33 | | #include "llvm/MC/MCRegisterInfo.h" |
34 | | #include "llvm/Support/CommandLine.h" |
35 | | #include "llvm/Support/Debug.h" |
36 | | #include "llvm/Support/MachineValueType.h" |
37 | | #include "llvm/Support/raw_ostream.h" |
38 | | #include <cassert> |
39 | | #include <map> |
40 | | #include <set> |
41 | | #include <utility> |
42 | | #include <vector> |
43 | | |
44 | | using namespace llvm; |
45 | | |
46 | | #define DEBUG_TYPE "post-RA-sched" |
47 | | |
48 | | // If DebugDiv > 0 then only break antidep with (ID % DebugDiv) == DebugMod |
49 | | static cl::opt<int> |
50 | | DebugDiv("agg-antidep-debugdiv", |
51 | | cl::desc("Debug control for aggressive anti-dep breaker"), |
52 | | cl::init(0), cl::Hidden); |
53 | | |
54 | | static cl::opt<int> |
55 | | DebugMod("agg-antidep-debugmod", |
56 | | cl::desc("Debug control for aggressive anti-dep breaker"), |
57 | | cl::init(0), cl::Hidden); |
58 | | |
59 | | AggressiveAntiDepState::AggressiveAntiDepState(const unsigned TargetRegs, |
60 | | MachineBasicBlock *BB) |
61 | | : NumTargetRegs(TargetRegs), GroupNodes(TargetRegs, 0), |
62 | | GroupNodeIndices(TargetRegs, 0), KillIndices(TargetRegs, 0), |
63 | 5.01k | DefIndices(TargetRegs, 0) { |
64 | 5.01k | const unsigned BBSize = BB->size(); |
65 | 991k | for (unsigned i = 0; i < NumTargetRegs; ++i986k ) { |
66 | 986k | // Initialize all registers to be in their own group. Initially we |
67 | 986k | // assign the register to the same-indexed GroupNode. |
68 | 986k | GroupNodeIndices[i] = i; |
69 | 986k | // Initialize the indices to indicate that no registers are live. |
70 | 986k | KillIndices[i] = ~0u; |
71 | 986k | DefIndices[i] = BBSize; |
72 | 986k | } |
73 | 5.01k | } |
74 | | |
75 | 771k | unsigned AggressiveAntiDepState::GetGroup(unsigned Reg) { |
76 | 771k | unsigned Node = GroupNodeIndices[Reg]; |
77 | 1.24M | while (GroupNodes[Node] != Node) |
78 | 470k | Node = GroupNodes[Node]; |
79 | 771k | |
80 | 771k | return Node; |
81 | 771k | } |
82 | | |
83 | | void AggressiveAntiDepState::GetGroupRegs( |
84 | | unsigned Group, |
85 | | std::vector<unsigned> &Regs, |
86 | | std::multimap<unsigned, AggressiveAntiDepState::RegisterReference> *RegRefs) |
87 | 968 | { |
88 | 191k | for (unsigned Reg = 0; Reg != NumTargetRegs; ++Reg190k ) { |
89 | 190k | if ((GetGroup(Reg) == Group) && (RegRefs->count(Reg) > 0)1.44k ) |
90 | 1.08k | Regs.push_back(Reg); |
91 | 190k | } |
92 | 968 | } |
93 | | |
94 | 288k | unsigned AggressiveAntiDepState::UnionGroups(unsigned Reg1, unsigned Reg2) { |
95 | 288k | assert(GroupNodes[0] == 0 && "GroupNode 0 not parent!"); |
96 | 288k | assert(GroupNodeIndices[0] == 0 && "Reg 0 not in Group 0!"); |
97 | 288k | |
98 | 288k | // find group for each register |
99 | 288k | unsigned Group1 = GetGroup(Reg1); |
100 | 288k | unsigned Group2 = GetGroup(Reg2); |
101 | 288k | |
102 | 288k | // if either group is 0, then that must become the parent |
103 | 288k | unsigned Parent = (Group1 == 0) ? Group1271k : Group217.9k ; |
104 | 288k | unsigned Other = (Parent == Group1) ? Group2271k : Group117.6k ; |
105 | 288k | GroupNodes.at(Other) = Parent; |
106 | 288k | return Parent; |
107 | 288k | } |
108 | | |
109 | 36.9k | unsigned AggressiveAntiDepState::LeaveGroup(unsigned Reg) { |
110 | 36.9k | // Create a new GroupNode for Reg. Reg's existing GroupNode must |
111 | 36.9k | // stay as is because there could be other GroupNodes referring to |
112 | 36.9k | // it. |
113 | 36.9k | unsigned idx = GroupNodes.size(); |
114 | 36.9k | GroupNodes.push_back(idx); |
115 | 36.9k | GroupNodeIndices[Reg] = idx; |
116 | 36.9k | return idx; |
117 | 36.9k | } |
118 | | |
119 | 1.21M | bool AggressiveAntiDepState::IsLive(unsigned Reg) { |
120 | 1.21M | // KillIndex must be defined and DefIndex not defined for a register |
121 | 1.21M | // to be live. |
122 | 1.21M | return((KillIndices[Reg] != ~0u) && (DefIndices[Reg] == ~0u)206k ); |
123 | 1.21M | } |
124 | | |
125 | | AggressiveAntiDepBreaker::AggressiveAntiDepBreaker( |
126 | | MachineFunction &MFi, const RegisterClassInfo &RCI, |
127 | | TargetSubtargetInfo::RegClassVector &CriticalPathRCs) |
128 | | : AntiDepBreaker(), MF(MFi), MRI(MF.getRegInfo()), |
129 | | TII(MF.getSubtarget().getInstrInfo()), |
130 | 3.35k | TRI(MF.getSubtarget().getRegisterInfo()), RegClassInfo(RCI) { |
131 | 3.35k | /* Collect a bitset of all registers that are only broken if they |
132 | 3.35k | are on the critical path. */ |
133 | 3.35k | for (unsigned i = 0, e = CriticalPathRCs.size(); i < e; ++i0 ) { |
134 | 0 | BitVector CPSet = TRI->getAllocatableSet(MF, CriticalPathRCs[i]); |
135 | 0 | if (CriticalPathSet.none()) |
136 | 0 | CriticalPathSet = CPSet; |
137 | 0 | else |
138 | 0 | CriticalPathSet |= CPSet; |
139 | 0 | } |
140 | 3.35k | |
141 | 3.35k | LLVM_DEBUG(dbgs() << "AntiDep Critical-Path Registers:"); |
142 | 3.35k | LLVM_DEBUG(for (unsigned r |
143 | 3.35k | : CriticalPathSet.set_bits()) dbgs() |
144 | 3.35k | << " " << printReg(r, TRI)); |
145 | 3.35k | LLVM_DEBUG(dbgs() << '\n'); |
146 | 3.35k | } |
147 | | |
148 | 3.35k | AggressiveAntiDepBreaker::~AggressiveAntiDepBreaker() { |
149 | 3.35k | delete State; |
150 | 3.35k | } |
151 | | |
152 | 5.01k | void AggressiveAntiDepBreaker::StartBlock(MachineBasicBlock *BB) { |
153 | 5.01k | assert(!State); |
154 | 5.01k | State = new AggressiveAntiDepState(TRI->getNumRegs(), BB); |
155 | 5.01k | |
156 | 5.01k | bool IsReturnBlock = BB->isReturnBlock(); |
157 | 5.01k | std::vector<unsigned> &KillIndices = State->GetKillIndices(); |
158 | 5.01k | std::vector<unsigned> &DefIndices = State->GetDefIndices(); |
159 | 5.01k | |
160 | 5.01k | // Examine the live-in regs of all successors. |
161 | 5.01k | for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), |
162 | 7.51k | SE = BB->succ_end(); SI != SE; ++SI2.50k ) |
163 | 16.5k | for (const auto &LI : (*SI)->liveins())2.50k { |
164 | 51.9k | for (MCRegAliasIterator AI(LI.PhysReg, TRI, true); AI.isValid(); ++AI35.4k ) { |
165 | 35.4k | unsigned Reg = *AI; |
166 | 35.4k | State->UnionGroups(Reg, 0); |
167 | 35.4k | KillIndices[Reg] = BB->size(); |
168 | 35.4k | DefIndices[Reg] = ~0u; |
169 | 35.4k | } |
170 | 16.5k | } |
171 | 5.01k | |
172 | 5.01k | // Mark live-out callee-saved registers. In a return block this is |
173 | 5.01k | // all callee-saved registers. In non-return this is any |
174 | 5.01k | // callee-saved register that is not saved in the prolog. |
175 | 5.01k | const MachineFrameInfo &MFI = MF.getFrameInfo(); |
176 | 5.01k | BitVector Pristine = MFI.getPristineRegs(MF); |
177 | 65.1k | for (const MCPhysReg *I = MF.getRegInfo().getCalleeSavedRegs(); *I; |
178 | 60.1k | ++I) { |
179 | 60.1k | unsigned Reg = *I; |
180 | 60.1k | if (!IsReturnBlock && !Pristine.test(Reg)19.1k ) |
181 | 3.48k | continue; |
182 | 169k | for (MCRegAliasIterator AI(Reg, TRI, true); 56.6k AI.isValid(); ++AI113k ) { |
183 | 113k | unsigned AliasReg = *AI; |
184 | 113k | State->UnionGroups(AliasReg, 0); |
185 | 113k | KillIndices[AliasReg] = BB->size(); |
186 | 113k | DefIndices[AliasReg] = ~0u; |
187 | 113k | } |
188 | 56.6k | } |
189 | 5.01k | } |
190 | | |
191 | 5.01k | void AggressiveAntiDepBreaker::FinishBlock() { |
192 | 5.01k | delete State; |
193 | 5.01k | State = nullptr; |
194 | 5.01k | } |
195 | | |
196 | | void AggressiveAntiDepBreaker::Observe(MachineInstr &MI, unsigned Count, |
197 | 5.19k | unsigned InsertPosIndex) { |
198 | 5.19k | assert(Count < InsertPosIndex && "Instruction index out of expected range!"); |
199 | 5.19k | |
200 | 5.19k | std::set<unsigned> PassthruRegs; |
201 | 5.19k | GetPassthruRegs(MI, PassthruRegs); |
202 | 5.19k | PrescanInstruction(MI, Count, PassthruRegs); |
203 | 5.19k | ScanInstruction(MI, Count); |
204 | 5.19k | |
205 | 5.19k | LLVM_DEBUG(dbgs() << "Observe: "); |
206 | 5.19k | LLVM_DEBUG(MI.dump()); |
207 | 5.19k | LLVM_DEBUG(dbgs() << "\tRegs:"); |
208 | 5.19k | |
209 | 5.19k | std::vector<unsigned> &DefIndices = State->GetDefIndices(); |
210 | 1.02M | for (unsigned Reg = 0; Reg != TRI->getNumRegs(); ++Reg1.02M ) { |
211 | 1.02M | // If Reg is current live, then mark that it can't be renamed as |
212 | 1.02M | // we don't know the extent of its live-range anymore (now that it |
213 | 1.02M | // has been scheduled). If it is not live but was defined in the |
214 | 1.02M | // previous schedule region, then set its def index to the most |
215 | 1.02M | // conservative location (i.e. the beginning of the previous |
216 | 1.02M | // schedule region). |
217 | 1.02M | if (State->IsLive(Reg)) { |
218 | 114k | LLVM_DEBUG(if (State->GetGroup(Reg) != 0) dbgs() |
219 | 114k | << " " << printReg(Reg, TRI) << "=g" << State->GetGroup(Reg) |
220 | 114k | << "->g0(region live-out)"); |
221 | 114k | State->UnionGroups(Reg, 0); |
222 | 908k | } else if ((DefIndices[Reg] < InsertPosIndex) |
223 | 908k | && (DefIndices[Reg] >= Count)14.1k ) { |
224 | 14.1k | DefIndices[Reg] = Count; |
225 | 14.1k | } |
226 | 1.02M | } |
227 | 5.19k | LLVM_DEBUG(dbgs() << '\n'); |
228 | 5.19k | } |
229 | | |
230 | | bool AggressiveAntiDepBreaker::IsImplicitDefUse(MachineInstr &MI, |
231 | 66.7k | MachineOperand &MO) { |
232 | 66.7k | if (!MO.isReg() || !MO.isImplicit()) |
233 | 50.1k | return false; |
234 | 16.5k | |
235 | 16.5k | unsigned Reg = MO.getReg(); |
236 | 16.5k | if (Reg == 0) |
237 | 0 | return false; |
238 | 16.5k | |
239 | 16.5k | MachineOperand *Op = nullptr; |
240 | 16.5k | if (MO.isDef()) |
241 | 9.06k | Op = MI.findRegisterUseOperand(Reg, true); |
242 | 7.48k | else |
243 | 7.48k | Op = MI.findRegisterDefOperand(Reg); |
244 | 16.5k | |
245 | 16.5k | return(Op && Op->isImplicit()2.02k ); |
246 | 16.5k | } |
247 | | |
248 | | void AggressiveAntiDepBreaker::GetPassthruRegs( |
249 | 26.6k | MachineInstr &MI, std::set<unsigned> &PassthruRegs) { |
250 | 112k | for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i85.5k ) { |
251 | 85.5k | MachineOperand &MO = MI.getOperand(i); |
252 | 85.5k | if (!MO.isReg()) continue16.6k ; |
253 | 68.9k | if ((MO.isDef() && MI.isRegTiedToUseOperand(i)28.2k ) || |
254 | 68.9k | IsImplicitDefUse(MI, MO)66.7k ) { |
255 | 3.81k | const unsigned Reg = MO.getReg(); |
256 | 3.81k | for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); |
257 | 8.51k | SubRegs.isValid(); ++SubRegs4.69k ) |
258 | 4.69k | PassthruRegs.insert(*SubRegs); |
259 | 3.81k | } |
260 | 68.9k | } |
261 | 26.6k | } |
262 | | |
263 | | /// AntiDepEdges - Return in Edges the anti- and output- dependencies |
264 | | /// in SU that we want to consider for breaking. |
265 | 21.4k | static void AntiDepEdges(const SUnit *SU, std::vector<const SDep *> &Edges) { |
266 | 21.4k | SmallSet<unsigned, 4> RegSet; |
267 | 21.4k | for (SUnit::const_pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end(); |
268 | 51.9k | P != PE; ++P30.4k ) { |
269 | 30.4k | if ((P->getKind() == SDep::Anti) || (P->getKind() == SDep::Output)23.5k ) { |
270 | 12.6k | if (RegSet.insert(P->getReg()).second) |
271 | 7.57k | Edges.push_back(&*P); |
272 | 12.6k | } |
273 | 30.4k | } |
274 | 21.4k | } |
275 | | |
276 | | /// CriticalPathStep - Return the next SUnit after SU on the bottom-up |
277 | | /// critical path. |
278 | 0 | static const SUnit *CriticalPathStep(const SUnit *SU) { |
279 | 0 | const SDep *Next = nullptr; |
280 | 0 | unsigned NextDepth = 0; |
281 | 0 | // Find the predecessor edge with the greatest depth. |
282 | 0 | if (SU) { |
283 | 0 | for (SUnit::const_pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end(); |
284 | 0 | P != PE; ++P) { |
285 | 0 | const SUnit *PredSU = P->getSUnit(); |
286 | 0 | unsigned PredLatency = P->getLatency(); |
287 | 0 | unsigned PredTotalLatency = PredSU->getDepth() + PredLatency; |
288 | 0 | // In the case of a latency tie, prefer an anti-dependency edge over |
289 | 0 | // other types of edges. |
290 | 0 | if (NextDepth < PredTotalLatency || |
291 | 0 | (NextDepth == PredTotalLatency && P->getKind() == SDep::Anti)) { |
292 | 0 | NextDepth = PredTotalLatency; |
293 | 0 | Next = &*P; |
294 | 0 | } |
295 | 0 | } |
296 | 0 | } |
297 | 0 |
|
298 | 0 | return (Next) ? Next->getSUnit() : nullptr; |
299 | 0 | } |
300 | | |
301 | | void AggressiveAntiDepBreaker::HandleLastUse(unsigned Reg, unsigned KillIdx, |
302 | | const char *tag, |
303 | | const char *header, |
304 | 68.9k | const char *footer) { |
305 | 68.9k | std::vector<unsigned> &KillIndices = State->GetKillIndices(); |
306 | 68.9k | std::vector<unsigned> &DefIndices = State->GetDefIndices(); |
307 | 68.9k | std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& |
308 | 68.9k | RegRefs = State->GetRegRefs(); |
309 | 68.9k | |
310 | 68.9k | // FIXME: We must leave subregisters of live super registers as live, so that |
311 | 68.9k | // we don't clear out the register tracking information for subregisters of |
312 | 68.9k | // super registers we're still tracking (and with which we're unioning |
313 | 68.9k | // subregister definitions). |
314 | 220k | for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI151k ) |
315 | 168k | if (TRI->isSuperRegister(Reg, *AI) && State->IsLive(*AI)68.6k ) { |
316 | 17.0k | LLVM_DEBUG(if (!header && footer) dbgs() << footer); |
317 | 17.0k | return; |
318 | 17.0k | } |
319 | 68.9k | |
320 | 68.9k | if (51.8k !State->IsLive(Reg)51.8k ) { |
321 | 30.0k | KillIndices[Reg] = KillIdx; |
322 | 30.0k | DefIndices[Reg] = ~0u; |
323 | 30.0k | RegRefs.erase(Reg); |
324 | 30.0k | State->LeaveGroup(Reg); |
325 | 30.0k | LLVM_DEBUG(if (header) { |
326 | 30.0k | dbgs() << header << printReg(Reg, TRI); |
327 | 30.0k | header = nullptr; |
328 | 30.0k | }); |
329 | 30.0k | LLVM_DEBUG(dbgs() << "->g" << State->GetGroup(Reg) << tag); |
330 | 30.0k | // Repeat for subregisters. Note that we only do this if the superregister |
331 | 30.0k | // was not live because otherwise, regardless whether we have an explicit |
332 | 30.0k | // use of the subregister, the subregister's contents are needed for the |
333 | 30.0k | // uses of the superregister. |
334 | 37.8k | for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs7.76k ) { |
335 | 7.76k | unsigned SubregReg = *SubRegs; |
336 | 7.76k | if (!State->IsLive(SubregReg)) { |
337 | 6.83k | KillIndices[SubregReg] = KillIdx; |
338 | 6.83k | DefIndices[SubregReg] = ~0u; |
339 | 6.83k | RegRefs.erase(SubregReg); |
340 | 6.83k | State->LeaveGroup(SubregReg); |
341 | 6.83k | LLVM_DEBUG(if (header) { |
342 | 6.83k | dbgs() << header << printReg(Reg, TRI); |
343 | 6.83k | header = nullptr; |
344 | 6.83k | }); |
345 | 6.83k | LLVM_DEBUG(dbgs() << " " << printReg(SubregReg, TRI) << "->g" |
346 | 6.83k | << State->GetGroup(SubregReg) << tag); |
347 | 6.83k | } |
348 | 7.76k | } |
349 | 30.0k | } |
350 | 51.8k | |
351 | 51.8k | LLVM_DEBUG(if (!header && footer) dbgs() << footer); |
352 | 51.8k | } |
353 | | |
354 | | void AggressiveAntiDepBreaker::PrescanInstruction( |
355 | 26.6k | MachineInstr &MI, unsigned Count, std::set<unsigned> &PassthruRegs) { |
356 | 26.6k | std::vector<unsigned> &DefIndices = State->GetDefIndices(); |
357 | 26.6k | std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& |
358 | 26.6k | RegRefs = State->GetRegRefs(); |
359 | 26.6k | |
360 | 26.6k | // Handle dead defs by simulating a last-use of the register just |
361 | 26.6k | // after the def. A dead def can occur because the def is truly |
362 | 26.6k | // dead, or because only a subregister is live at the def. If we |
363 | 26.6k | // don't do this the dead def will be incorrectly merged into the |
364 | 26.6k | // previous def. |
365 | 112k | for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i85.5k ) { |
366 | 85.5k | MachineOperand &MO = MI.getOperand(i); |
367 | 85.5k | if (!MO.isReg() || !MO.isDef()68.9k ) continue57.3k ; |
368 | 28.2k | unsigned Reg = MO.getReg(); |
369 | 28.2k | if (Reg == 0) continue0 ; |
370 | 28.2k | |
371 | 28.2k | HandleLastUse(Reg, Count + 1, "", "\tDead Def: ", "\n"); |
372 | 28.2k | } |
373 | 26.6k | |
374 | 26.6k | LLVM_DEBUG(dbgs() << "\tDef Groups:"); |
375 | 112k | for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i85.5k ) { |
376 | 85.5k | MachineOperand &MO = MI.getOperand(i); |
377 | 85.5k | if (!MO.isReg() || !MO.isDef()68.9k ) continue57.3k ; |
378 | 28.2k | unsigned Reg = MO.getReg(); |
379 | 28.2k | if (Reg == 0) continue0 ; |
380 | 28.2k | |
381 | 28.2k | LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI) << "=g" |
382 | 28.2k | << State->GetGroup(Reg)); |
383 | 28.2k | |
384 | 28.2k | // If MI's defs have a special allocation requirement, don't allow |
385 | 28.2k | // any def registers to be changed. Also assume all registers |
386 | 28.2k | // defined in a call must not be changed (ABI). Inline assembly may |
387 | 28.2k | // reference either system calls or the register directly. Skip it until we |
388 | 28.2k | // can tell user specified registers from compiler-specified. |
389 | 28.2k | if (MI.isCall() || MI.hasExtraDefRegAllocReq()25.7k || TII->isPredicated(MI)25.7k || |
390 | 28.2k | MI.isInlineAsm()24.0k ) { |
391 | 4.23k | LLVM_DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)"); |
392 | 4.23k | State->UnionGroups(Reg, 0); |
393 | 4.23k | } |
394 | 28.2k | |
395 | 28.2k | // Any aliased that are live at this point are completely or |
396 | 28.2k | // partially defined here, so group those aliases with Reg. |
397 | 66.8k | for (MCRegAliasIterator AI(Reg, TRI, false); AI.isValid(); ++AI38.6k ) { |
398 | 38.6k | unsigned AliasReg = *AI; |
399 | 38.6k | if (State->IsLive(AliasReg)) { |
400 | 15.6k | State->UnionGroups(Reg, AliasReg); |
401 | 15.6k | LLVM_DEBUG(dbgs() << "->g" << State->GetGroup(Reg) << "(via " |
402 | 15.6k | << printReg(AliasReg, TRI) << ")"); |
403 | 15.6k | } |
404 | 38.6k | } |
405 | 28.2k | |
406 | 28.2k | // Note register reference... |
407 | 28.2k | const TargetRegisterClass *RC = nullptr; |
408 | 28.2k | if (i < MI.getDesc().getNumOperands()) |
409 | 19.1k | RC = TII->getRegClass(MI.getDesc(), i, TRI, MF); |
410 | 28.2k | AggressiveAntiDepState::RegisterReference RR = { &MO, RC }; |
411 | 28.2k | RegRefs.insert(std::make_pair(Reg, RR)); |
412 | 28.2k | } |
413 | 26.6k | |
414 | 26.6k | LLVM_DEBUG(dbgs() << '\n'); |
415 | 26.6k | |
416 | 26.6k | // Scan the register defs for this instruction and update |
417 | 26.6k | // live-ranges. |
418 | 112k | for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i85.5k ) { |
419 | 85.5k | MachineOperand &MO = MI.getOperand(i); |
420 | 85.5k | if (!MO.isReg() || !MO.isDef()68.9k ) continue57.3k ; |
421 | 28.2k | unsigned Reg = MO.getReg(); |
422 | 28.2k | if (Reg == 0) continue0 ; |
423 | 28.2k | // Ignore KILLs and passthru registers for liveness... |
424 | 28.2k | if (MI.isKill() || (PassthruRegs.count(Reg) != 0)) |
425 | 3.76k | continue; |
426 | 24.4k | |
427 | 24.4k | // Update def for Reg and aliases. |
428 | 86.3k | for (MCRegAliasIterator AI(Reg, TRI, true); 24.4k AI.isValid(); ++AI61.9k ) { |
429 | 61.9k | // We need to be careful here not to define already-live super registers. |
430 | 61.9k | // If the super register is already live, then this definition is not |
431 | 61.9k | // a definition of the whole super register (just a partial insertion |
432 | 61.9k | // into it). Earlier subregister definitions (which we've not yet visited |
433 | 61.9k | // because we're iterating bottom-up) need to be linked to the same group |
434 | 61.9k | // as this definition. |
435 | 61.9k | if (TRI->isSuperRegister(Reg, *AI) && State->IsLive(*AI)24.1k ) |
436 | 6.53k | continue; |
437 | 55.4k | |
438 | 55.4k | DefIndices[*AI] = Count; |
439 | 55.4k | } |
440 | 24.4k | } |
441 | 26.6k | } |
442 | | |
443 | | void AggressiveAntiDepBreaker::ScanInstruction(MachineInstr &MI, |
444 | 26.6k | unsigned Count) { |
445 | 26.6k | LLVM_DEBUG(dbgs() << "\tUse Groups:"); |
446 | 26.6k | std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& |
447 | 26.6k | RegRefs = State->GetRegRefs(); |
448 | 26.6k | |
449 | 26.6k | // If MI's uses have special allocation requirement, don't allow |
450 | 26.6k | // any use registers to be changed. Also assume all registers |
451 | 26.6k | // used in a call must not be changed (ABI). |
452 | 26.6k | // Inline Assembly register uses also cannot be safely changed. |
453 | 26.6k | // FIXME: The issue with predicated instruction is more complex. We are being |
454 | 26.6k | // conservatively here because the kill markers cannot be trusted after |
455 | 26.6k | // if-conversion: |
456 | 26.6k | // %r6 = LDR %sp, %reg0, 92, 14, %reg0; mem:LD4[FixedStack14] |
457 | 26.6k | // ... |
458 | 26.6k | // STR %r0, killed %r6, %reg0, 0, 0, %cpsr; mem:ST4[%395] |
459 | 26.6k | // %r6 = LDR %sp, %reg0, 100, 0, %cpsr; mem:LD4[FixedStack12] |
460 | 26.6k | // STR %r0, killed %r6, %reg0, 0, 14, %reg0; mem:ST4[%396](align=8) |
461 | 26.6k | // |
462 | 26.6k | // The first R6 kill is not really a kill since it's killed by a predicated |
463 | 26.6k | // instruction which may not be executed. The second R6 def may or may not |
464 | 26.6k | // re-define R6 so it's not safe to change it since the last R6 use cannot be |
465 | 26.6k | // changed. |
466 | 26.6k | bool Special = MI.isCall() || MI.hasExtraSrcRegAllocReq()25.9k || |
467 | 26.6k | TII->isPredicated(MI)25.9k || MI.isInlineAsm()24.5k ; |
468 | 26.6k | |
469 | 26.6k | // Scan the register uses for this instruction and update |
470 | 26.6k | // live-ranges, groups and RegRefs. |
471 | 112k | for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i85.5k ) { |
472 | 85.5k | MachineOperand &MO = MI.getOperand(i); |
473 | 85.5k | if (!MO.isReg() || !MO.isUse()68.9k ) continue44.8k ; |
474 | 40.7k | unsigned Reg = MO.getReg(); |
475 | 40.7k | if (Reg == 0) continue0 ; |
476 | 40.7k | |
477 | 40.7k | LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI) << "=g" |
478 | 40.7k | << State->GetGroup(Reg)); |
479 | 40.7k | |
480 | 40.7k | // It wasn't previously live but now it is, this is a kill. Forget |
481 | 40.7k | // the previous live-range information and start a new live-range |
482 | 40.7k | // for the register. |
483 | 40.7k | HandleLastUse(Reg, Count, "(last-use)"); |
484 | 40.7k | |
485 | 40.7k | if (Special) { |
486 | 4.37k | LLVM_DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)"); |
487 | 4.37k | State->UnionGroups(Reg, 0); |
488 | 4.37k | } |
489 | 40.7k | |
490 | 40.7k | // Note register reference... |
491 | 40.7k | const TargetRegisterClass *RC = nullptr; |
492 | 40.7k | if (i < MI.getDesc().getNumOperands()) |
493 | 33.1k | RC = TII->getRegClass(MI.getDesc(), i, TRI, MF); |
494 | 40.7k | AggressiveAntiDepState::RegisterReference RR = { &MO, RC }; |
495 | 40.7k | RegRefs.insert(std::make_pair(Reg, RR)); |
496 | 40.7k | } |
497 | 26.6k | |
498 | 26.6k | LLVM_DEBUG(dbgs() << '\n'); |
499 | 26.6k | |
500 | 26.6k | // Form a group of all defs and uses of a KILL instruction to ensure |
501 | 26.6k | // that all registers are renamed as a group. |
502 | 26.6k | if (MI.isKill()) { |
503 | 0 | LLVM_DEBUG(dbgs() << "\tKill Group:"); |
504 | 0 |
|
505 | 0 | unsigned FirstReg = 0; |
506 | 0 | for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { |
507 | 0 | MachineOperand &MO = MI.getOperand(i); |
508 | 0 | if (!MO.isReg()) continue; |
509 | 0 | unsigned Reg = MO.getReg(); |
510 | 0 | if (Reg == 0) continue; |
511 | 0 | |
512 | 0 | if (FirstReg != 0) { |
513 | 0 | LLVM_DEBUG(dbgs() << "=" << printReg(Reg, TRI)); |
514 | 0 | State->UnionGroups(FirstReg, Reg); |
515 | 0 | } else { |
516 | 0 | LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI)); |
517 | 0 | FirstReg = Reg; |
518 | 0 | } |
519 | 0 | } |
520 | 0 |
|
521 | 0 | LLVM_DEBUG(dbgs() << "->g" << State->GetGroup(FirstReg) << '\n'); |
522 | 0 | } |
523 | 26.6k | } |
524 | | |
525 | 1.08k | BitVector AggressiveAntiDepBreaker::GetRenameRegisters(unsigned Reg) { |
526 | 1.08k | BitVector BV(TRI->getNumRegs(), false); |
527 | 1.08k | bool first = true; |
528 | 1.08k | |
529 | 1.08k | // Check all references that need rewriting for Reg. For each, use |
530 | 1.08k | // the corresponding register class to narrow the set of registers |
531 | 1.08k | // that are appropriate for renaming. |
532 | 2.37k | for (const auto &Q : make_range(State->GetRegRefs().equal_range(Reg))) { |
533 | 2.37k | const TargetRegisterClass *RC = Q.second.RC; |
534 | 2.37k | if (!RC) continue0 ; |
535 | 2.37k | |
536 | 2.37k | BitVector RCBV = TRI->getAllocatableSet(MF, RC); |
537 | 2.37k | if (first) { |
538 | 1.08k | BV |= RCBV; |
539 | 1.08k | first = false; |
540 | 1.29k | } else { |
541 | 1.29k | BV &= RCBV; |
542 | 1.29k | } |
543 | 2.37k | |
544 | 2.37k | LLVM_DEBUG(dbgs() << " " << TRI->getRegClassName(RC)); |
545 | 2.37k | } |
546 | 1.08k | |
547 | 1.08k | return BV; |
548 | 1.08k | } |
549 | | |
550 | | bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters( |
551 | | unsigned AntiDepGroupIndex, |
552 | | RenameOrderType& RenameOrder, |
553 | 968 | std::map<unsigned, unsigned> &RenameMap) { |
554 | 968 | std::vector<unsigned> &KillIndices = State->GetKillIndices(); |
555 | 968 | std::vector<unsigned> &DefIndices = State->GetDefIndices(); |
556 | 968 | std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& |
557 | 968 | RegRefs = State->GetRegRefs(); |
558 | 968 | |
559 | 968 | // Collect all referenced registers in the same group as |
560 | 968 | // AntiDepReg. These all need to be renamed together if we are to |
561 | 968 | // break the anti-dependence. |
562 | 968 | std::vector<unsigned> Regs; |
563 | 968 | State->GetGroupRegs(AntiDepGroupIndex, Regs, &RegRefs); |
564 | 968 | assert(!Regs.empty() && "Empty register group!"); |
565 | 968 | if (Regs.empty()) |
566 | 0 | return false; |
567 | 968 | |
568 | 968 | // Find the "superest" register in the group. At the same time, |
569 | 968 | // collect the BitVector of registers that can be used to rename |
570 | 968 | // each register. |
571 | 968 | LLVM_DEBUG(dbgs() << "\tRename Candidates for Group g" << AntiDepGroupIndex |
572 | 968 | << ":\n"); |
573 | 968 | std::map<unsigned, BitVector> RenameRegisterMap; |
574 | 968 | unsigned SuperReg = 0; |
575 | 2.05k | for (unsigned i = 0, e = Regs.size(); i != e; ++i1.08k ) { |
576 | 1.08k | unsigned Reg = Regs[i]; |
577 | 1.08k | if ((SuperReg == 0) || TRI->isSuperRegister(SuperReg, Reg)114 ) |
578 | 987 | SuperReg = Reg; |
579 | 1.08k | |
580 | 1.08k | // If Reg has any references, then collect possible rename regs |
581 | 1.08k | if (RegRefs.count(Reg) > 0) { |
582 | 1.08k | LLVM_DEBUG(dbgs() << "\t\t" << printReg(Reg, TRI) << ":"); |
583 | 1.08k | |
584 | 1.08k | BitVector &BV = RenameRegisterMap[Reg]; |
585 | 1.08k | assert(BV.empty()); |
586 | 1.08k | BV = GetRenameRegisters(Reg); |
587 | 1.08k | |
588 | 1.08k | LLVM_DEBUG({ |
589 | 1.08k | dbgs() << " ::"; |
590 | 1.08k | for (unsigned r : BV.set_bits()) |
591 | 1.08k | dbgs() << " " << printReg(r, TRI); |
592 | 1.08k | dbgs() << "\n"; |
593 | 1.08k | }); |
594 | 1.08k | } |
595 | 1.08k | } |
596 | 968 | |
597 | 968 | // All group registers should be a subreg of SuperReg. |
598 | 2.05k | for (unsigned i = 0, e = Regs.size(); i != e; ++i1.08k ) { |
599 | 1.08k | unsigned Reg = Regs[i]; |
600 | 1.08k | if (Reg == SuperReg) continue968 ; |
601 | 114 | bool IsSub = TRI->isSubRegister(SuperReg, Reg); |
602 | 114 | // FIXME: remove this once PR18663 has been properly fixed. For now, |
603 | 114 | // return a conservative answer: |
604 | 114 | // assert(IsSub && "Expecting group subregister"); |
605 | 114 | if (!IsSub) |
606 | 0 | return false; |
607 | 114 | } |
608 | 968 | |
609 | | #ifndef NDEBUG |
610 | | // If DebugDiv > 0 then only rename (renamecnt % DebugDiv) == DebugMod |
611 | | if (DebugDiv > 0) { |
612 | | static int renamecnt = 0; |
613 | | if (renamecnt++ % DebugDiv != DebugMod) |
614 | | return false; |
615 | | |
616 | | dbgs() << "*** Performing rename " << printReg(SuperReg, TRI) |
617 | | << " for debug ***\n"; |
618 | | } |
619 | | #endif |
620 | | |
621 | 968 | // Check each possible rename register for SuperReg in round-robin |
622 | 968 | // order. If that register is available, and the corresponding |
623 | 968 | // registers are available for the other group subregisters, then we |
624 | 968 | // can use those registers to rename. |
625 | 968 | |
626 | 968 | // FIXME: Using getMinimalPhysRegClass is very conservative. We should |
627 | 968 | // check every use of the register and find the largest register class |
628 | 968 | // that can be used in all of them. |
629 | 968 | const TargetRegisterClass *SuperRC = |
630 | 968 | TRI->getMinimalPhysRegClass(SuperReg, MVT::Other); |
631 | 968 | |
632 | 968 | ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(SuperRC); |
633 | 968 | if (Order.empty()) { |
634 | 0 | LLVM_DEBUG(dbgs() << "\tEmpty Super Regclass!!\n"); |
635 | 0 | return false; |
636 | 0 | } |
637 | 968 | |
638 | 968 | LLVM_DEBUG(dbgs() << "\tFind Registers:"); |
639 | 968 | |
640 | 968 | RenameOrder.insert(RenameOrderType::value_type(SuperRC, Order.size())); |
641 | 968 | |
642 | 968 | unsigned OrigR = RenameOrder[SuperRC]; |
643 | 968 | unsigned EndR = ((OrigR == Order.size()) ? 0505 : OrigR463 ); |
644 | 968 | unsigned R = OrigR; |
645 | 3.74k | do { |
646 | 3.74k | if (R == 0) R = Order.size()169 ; |
647 | 3.74k | --R; |
648 | 3.74k | const unsigned NewSuperReg = Order[R]; |
649 | 3.74k | // Don't consider non-allocatable registers |
650 | 3.74k | if (!MRI.isAllocatable(NewSuperReg)) continue0 ; |
651 | 3.74k | // Don't replace a register with itself. |
652 | 3.74k | if (NewSuperReg == SuperReg) continue507 ; |
653 | 3.24k | |
654 | 3.24k | LLVM_DEBUG(dbgs() << " [" << printReg(NewSuperReg, TRI) << ':'); |
655 | 3.24k | RenameMap.clear(); |
656 | 3.24k | |
657 | 3.24k | // For each referenced group register (which must be a SuperReg or |
658 | 3.24k | // a subregister of SuperReg), find the corresponding subregister |
659 | 3.24k | // of NewSuperReg and make sure it is free to be renamed. |
660 | 4.06k | for (unsigned i = 0, e = Regs.size(); i != e; ++i819 ) { |
661 | 3.30k | unsigned Reg = Regs[i]; |
662 | 3.30k | unsigned NewReg = 0; |
663 | 3.30k | if (Reg == SuperReg) { |
664 | 3.23k | NewReg = NewSuperReg; |
665 | 3.23k | } else { |
666 | 71 | unsigned NewSubRegIdx = TRI->getSubRegIndex(SuperReg, Reg); |
667 | 71 | if (NewSubRegIdx != 0) |
668 | 71 | NewReg = TRI->getSubReg(NewSuperReg, NewSubRegIdx); |
669 | 71 | } |
670 | 3.30k | |
671 | 3.30k | LLVM_DEBUG(dbgs() << " " << printReg(NewReg, TRI)); |
672 | 3.30k | |
673 | 3.30k | // Check if Reg can be renamed to NewReg. |
674 | 3.30k | if (!RenameRegisterMap[Reg].test(NewReg)) { |
675 | 0 | LLVM_DEBUG(dbgs() << "(no rename)"); |
676 | 0 | goto next_super_reg; |
677 | 0 | } |
678 | 3.30k | |
679 | 3.30k | // If NewReg is dead and NewReg's most recent def is not before |
680 | 3.30k | // Regs's kill, it's safe to replace Reg with NewReg. We |
681 | 3.30k | // must also check all aliases of NewReg, because we can't define a |
682 | 3.30k | // register when any sub or super is already live. |
683 | 3.30k | if (State->IsLive(NewReg) || (KillIndices[Reg] > DefIndices[NewReg])1.46k ) { |
684 | 2.19k | LLVM_DEBUG(dbgs() << "(live)"); |
685 | 2.19k | goto next_super_reg; |
686 | 2.19k | } else { |
687 | 1.11k | bool found = false; |
688 | 2.31k | for (MCRegAliasIterator AI(NewReg, TRI, false); AI.isValid(); ++AI1.20k ) { |
689 | 1.49k | unsigned AliasReg = *AI; |
690 | 1.49k | if (State->IsLive(AliasReg) || |
691 | 1.49k | (KillIndices[Reg] > DefIndices[AliasReg])1.33k ) { |
692 | 292 | LLVM_DEBUG(dbgs() |
693 | 292 | << "(alias " << printReg(AliasReg, TRI) << " live)"); |
694 | 292 | found = true; |
695 | 292 | break; |
696 | 292 | } |
697 | 1.49k | } |
698 | 1.11k | if (found) |
699 | 292 | goto next_super_reg; |
700 | 819 | } |
701 | 819 | |
702 | 819 | // We cannot rename 'Reg' to 'NewReg' if one of the uses of 'Reg' also |
703 | 819 | // defines 'NewReg' via an early-clobber operand. |
704 | 1.73k | for (const auto &Q : make_range(RegRefs.equal_range(Reg)))819 { |
705 | 1.73k | MachineInstr *UseMI = Q.second.Operand->getParent(); |
706 | 1.73k | int Idx = UseMI->findRegisterDefOperandIdx(NewReg, false, true, TRI); |
707 | 1.73k | if (Idx == -1) |
708 | 1.72k | continue; |
709 | 3 | |
710 | 3 | if (UseMI->getOperand(Idx).isEarlyClobber()) { |
711 | 0 | LLVM_DEBUG(dbgs() << "(ec)"); |
712 | 0 | goto next_super_reg; |
713 | 0 | } |
714 | 3 | } |
715 | 819 | |
716 | 819 | // Also, we cannot rename 'Reg' to 'NewReg' if the instruction defining |
717 | 819 | // 'Reg' is an early-clobber define and that instruction also uses |
718 | 819 | // 'NewReg'. |
719 | 1.73k | for (const auto &Q : make_range(RegRefs.equal_range(Reg)))819 { |
720 | 1.73k | if (!Q.second.Operand->isDef() || !Q.second.Operand->isEarlyClobber()817 ) |
721 | 1.73k | continue; |
722 | 0 | |
723 | 0 | MachineInstr *DefMI = Q.second.Operand->getParent(); |
724 | 0 | if (DefMI->readsRegister(NewReg, TRI)) { |
725 | 0 | LLVM_DEBUG(dbgs() << "(ec)"); |
726 | 0 | goto next_super_reg; |
727 | 0 | } |
728 | 0 | } |
729 | 819 | |
730 | 819 | // Record that 'Reg' can be renamed to 'NewReg'. |
731 | 819 | RenameMap.insert(std::pair<unsigned, unsigned>(Reg, NewReg)); |
732 | 819 | } |
733 | 3.24k | |
734 | 3.24k | // If we fall-out here, then every register in the group can be |
735 | 3.24k | // renamed, as recorded in RenameMap. |
736 | 3.24k | RenameOrder.erase(SuperRC); |
737 | 752 | RenameOrder.insert(RenameOrderType::value_type(SuperRC, R)); |
738 | 752 | LLVM_DEBUG(dbgs() << "]\n"); |
739 | 752 | return true; |
740 | 2.48k | |
741 | 2.48k | next_super_reg: |
742 | 2.48k | LLVM_DEBUG(dbgs() << ']'); |
743 | 2.99k | } while (R != EndR); |
744 | 968 | |
745 | 968 | LLVM_DEBUG216 (dbgs() << '\n'); |
746 | 216 | |
747 | 216 | // No registers are free and available! |
748 | 216 | return false; |
749 | 968 | } |
750 | | |
751 | | /// BreakAntiDependencies - Identifiy anti-dependencies within the |
752 | | /// ScheduleDAG and break them by renaming registers. |
753 | | unsigned AggressiveAntiDepBreaker::BreakAntiDependencies( |
754 | | const std::vector<SUnit> &SUnits, |
755 | | MachineBasicBlock::iterator Begin, |
756 | | MachineBasicBlock::iterator End, |
757 | | unsigned InsertPosIndex, |
758 | 10.2k | DbgValueVector &DbgValues) { |
759 | 10.2k | std::vector<unsigned> &KillIndices = State->GetKillIndices(); |
760 | 10.2k | std::vector<unsigned> &DefIndices = State->GetDefIndices(); |
761 | 10.2k | std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& |
762 | 10.2k | RegRefs = State->GetRegRefs(); |
763 | 10.2k | |
764 | 10.2k | // The code below assumes that there is at least one instruction, |
765 | 10.2k | // so just duck out immediately if the block is empty. |
766 | 10.2k | if (SUnits.empty()) return 04.89k ; |
767 | 5.30k | |
768 | 5.30k | // For each regclass the next register to use for renaming. |
769 | 5.30k | RenameOrderType RenameOrder; |
770 | 5.30k | |
771 | 5.30k | // ...need a map from MI to SUnit. |
772 | 5.30k | std::map<MachineInstr *, const SUnit *> MISUnitMap; |
773 | 26.7k | for (unsigned i = 0, e = SUnits.size(); i != e; ++i21.4k ) { |
774 | 21.4k | const SUnit *SU = &SUnits[i]; |
775 | 21.4k | MISUnitMap.insert(std::pair<MachineInstr *, const SUnit *>(SU->getInstr(), |
776 | 21.4k | SU)); |
777 | 21.4k | } |
778 | 5.30k | |
779 | 5.30k | // Track progress along the critical path through the SUnit graph as |
780 | 5.30k | // we walk the instructions. This is needed for regclasses that only |
781 | 5.30k | // break critical-path anti-dependencies. |
782 | 5.30k | const SUnit *CriticalPathSU = nullptr; |
783 | 5.30k | MachineInstr *CriticalPathMI = nullptr; |
784 | 5.30k | if (CriticalPathSet.any()) { |
785 | 0 | for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { |
786 | 0 | const SUnit *SU = &SUnits[i]; |
787 | 0 | if (!CriticalPathSU || |
788 | 0 | ((SU->getDepth() + SU->Latency) > |
789 | 0 | (CriticalPathSU->getDepth() + CriticalPathSU->Latency))) { |
790 | 0 | CriticalPathSU = SU; |
791 | 0 | } |
792 | 0 | } |
793 | 0 |
|
794 | 0 | CriticalPathMI = CriticalPathSU->getInstr(); |
795 | 0 | } |
796 | 5.30k | |
797 | | #ifndef NDEBUG |
798 | | LLVM_DEBUG(dbgs() << "\n===== Aggressive anti-dependency breaking\n"); |
799 | | LLVM_DEBUG(dbgs() << "Available regs:"); |
800 | | for (unsigned Reg = 0; Reg < TRI->getNumRegs(); ++Reg) { |
801 | | if (!State->IsLive(Reg)) |
802 | | LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI)); |
803 | | } |
804 | | LLVM_DEBUG(dbgs() << '\n'); |
805 | | #endif |
806 | | |
807 | 5.30k | BitVector RegAliases(TRI->getNumRegs()); |
808 | 5.30k | |
809 | 5.30k | // Attempt to break anti-dependence edges. Walk the instructions |
810 | 5.30k | // from the bottom up, tracking information about liveness as we go |
811 | 5.30k | // to help determine which registers are available. |
812 | 5.30k | unsigned Broken = 0; |
813 | 5.30k | unsigned Count = InsertPosIndex - 1; |
814 | 5.30k | for (MachineBasicBlock::iterator I = End, E = Begin; |
815 | 26.7k | I != E; --Count21.4k ) { |
816 | 21.4k | MachineInstr &MI = *--I; |
817 | 21.4k | |
818 | 21.4k | if (MI.isDebugInstr()) |
819 | 20 | continue; |
820 | 21.4k | |
821 | 21.4k | LLVM_DEBUG(dbgs() << "Anti: "); |
822 | 21.4k | LLVM_DEBUG(MI.dump()); |
823 | 21.4k | |
824 | 21.4k | std::set<unsigned> PassthruRegs; |
825 | 21.4k | GetPassthruRegs(MI, PassthruRegs); |
826 | 21.4k | |
827 | 21.4k | // Process the defs in MI... |
828 | 21.4k | PrescanInstruction(MI, Count, PassthruRegs); |
829 | 21.4k | |
830 | 21.4k | // The dependence edges that represent anti- and output- |
831 | 21.4k | // dependencies that are candidates for breaking. |
832 | 21.4k | std::vector<const SDep *> Edges; |
833 | 21.4k | const SUnit *PathSU = MISUnitMap[&MI]; |
834 | 21.4k | AntiDepEdges(PathSU, Edges); |
835 | 21.4k | |
836 | 21.4k | // If MI is not on the critical path, then we don't rename |
837 | 21.4k | // registers in the CriticalPathSet. |
838 | 21.4k | BitVector *ExcludeRegs = nullptr; |
839 | 21.4k | if (&MI == CriticalPathMI) { |
840 | 0 | CriticalPathSU = CriticalPathStep(CriticalPathSU); |
841 | 0 | CriticalPathMI = (CriticalPathSU) ? CriticalPathSU->getInstr() : nullptr; |
842 | 21.4k | } else if (CriticalPathSet.any()) { |
843 | 0 | ExcludeRegs = &CriticalPathSet; |
844 | 0 | } |
845 | 21.4k | |
846 | 21.4k | // Ignore KILL instructions (they form a group in ScanInstruction |
847 | 21.4k | // but don't cause any anti-dependence breaking themselves) |
848 | 21.4k | if (!MI.isKill()) { |
849 | 21.4k | // Attempt to break each anti-dependency... |
850 | 29.0k | for (unsigned i = 0, e = Edges.size(); i != e; ++i7.57k ) { |
851 | 7.57k | const SDep *Edge = Edges[i]; |
852 | 7.57k | SUnit *NextSU = Edge->getSUnit(); |
853 | 7.57k | |
854 | 7.57k | if ((Edge->getKind() != SDep::Anti) && |
855 | 7.57k | (Edge->getKind() != SDep::Output)2.86k ) continue0 ; |
856 | 7.57k | |
857 | 7.57k | unsigned AntiDepReg = Edge->getReg(); |
858 | 7.57k | LLVM_DEBUG(dbgs() << "\tAntidep reg: " << printReg(AntiDepReg, TRI)); |
859 | 7.57k | assert(AntiDepReg != 0 && "Anti-dependence on reg0?"); |
860 | 7.57k | |
861 | 7.57k | if (!MRI.isAllocatable(AntiDepReg)) { |
862 | 208 | // Don't break anti-dependencies on non-allocatable registers. |
863 | 208 | LLVM_DEBUG(dbgs() << " (non-allocatable)\n"); |
864 | 208 | continue; |
865 | 7.37k | } else if (ExcludeRegs && ExcludeRegs->test(AntiDepReg)0 ) { |
866 | 0 | // Don't break anti-dependencies for critical path registers |
867 | 0 | // if not on the critical path |
868 | 0 | LLVM_DEBUG(dbgs() << " (not critical-path)\n"); |
869 | 0 | continue; |
870 | 7.37k | } else if (PassthruRegs.count(AntiDepReg) != 0) { |
871 | 1.39k | // If the anti-dep register liveness "passes-thru", then |
872 | 1.39k | // don't try to change it. It will be changed along with |
873 | 1.39k | // the use if required to break an earlier antidep. |
874 | 1.39k | LLVM_DEBUG(dbgs() << " (passthru)\n"); |
875 | 1.39k | continue; |
876 | 5.97k | } else { |
877 | 5.97k | // No anti-dep breaking for implicit deps |
878 | 5.97k | MachineOperand *AntiDepOp = MI.findRegisterDefOperand(AntiDepReg); |
879 | 5.97k | assert(AntiDepOp && "Can't find index for defined register operand"); |
880 | 5.97k | if (!AntiDepOp || AntiDepOp->isImplicit()) { |
881 | 0 | LLVM_DEBUG(dbgs() << " (implicit)\n"); |
882 | 0 | continue; |
883 | 0 | } |
884 | 5.97k | |
885 | 5.97k | // If the SUnit has other dependencies on the SUnit that |
886 | 5.97k | // it anti-depends on, don't bother breaking the |
887 | 5.97k | // anti-dependency since those edges would prevent such |
888 | 5.97k | // units from being scheduled past each other |
889 | 5.97k | // regardless. |
890 | 5.97k | // |
891 | 5.97k | // Also, if there are dependencies on other SUnits with the |
892 | 5.97k | // same register as the anti-dependency, don't attempt to |
893 | 5.97k | // break it. |
894 | 5.97k | for (SUnit::const_pred_iterator P = PathSU->Preds.begin(), |
895 | 16.0k | PE = PathSU->Preds.end(); P != PE; ++P10.0k ) { |
896 | 12.6k | if (P->getSUnit() == NextSU ? |
897 | 6.05k | (P->getKind() != SDep::Anti || P->getReg() != AntiDepReg3.59k ) : |
898 | 12.6k | (6.63k P->getKind() == SDep::Data6.63k && P->getReg() == AntiDepReg2.63k )) { |
899 | 2.66k | AntiDepReg = 0; |
900 | 2.66k | break; |
901 | 2.66k | } |
902 | 12.6k | } |
903 | 5.97k | for (SUnit::const_pred_iterator P = PathSU->Preds.begin(), |
904 | 17.9k | PE = PathSU->Preds.end(); P != PE; ++P11.9k ) { |
905 | 14.3k | if ((P->getSUnit() == NextSU) && (P->getKind() != SDep::Anti)7.57k && |
906 | 14.3k | (P->getKind() != SDep::Output)3.97k ) { |
907 | 2.40k | LLVM_DEBUG(dbgs() << " (real dependency)\n"); |
908 | 2.40k | AntiDepReg = 0; |
909 | 2.40k | break; |
910 | 11.9k | } else if ((P->getSUnit() != NextSU) && |
911 | 11.9k | (P->getKind() == SDep::Data)6.79k && |
912 | 11.9k | (P->getReg() == AntiDepReg)2.70k ) { |
913 | 0 | LLVM_DEBUG(dbgs() << " (other dependency)\n"); |
914 | 0 | AntiDepReg = 0; |
915 | 0 | break; |
916 | 0 | } |
917 | 14.3k | } |
918 | 5.97k | |
919 | 5.97k | if (AntiDepReg == 0) continue2.66k ; |
920 | 3.31k | |
921 | 3.31k | // If the definition of the anti-dependency register does not start |
922 | 3.31k | // a new live range, bail out. This can happen if the anti-dep |
923 | 3.31k | // register is a sub-register of another register whose live range |
924 | 3.31k | // spans over PathSU. In such case, PathSU defines only a part of |
925 | 3.31k | // the larger register. |
926 | 3.31k | RegAliases.reset(); |
927 | 12.0k | for (MCRegAliasIterator AI(AntiDepReg, TRI, true); AI.isValid(); ++AI8.71k ) |
928 | 8.71k | RegAliases.set(*AI); |
929 | 6.48k | for (SDep S : PathSU->Succs) { |
930 | 6.48k | SDep::Kind K = S.getKind(); |
931 | 6.48k | if (K != SDep::Data && K != SDep::Output4.02k && K != SDep::Anti2.64k ) |
932 | 1.60k | continue; |
933 | 4.88k | unsigned R = S.getReg(); |
934 | 4.88k | if (!RegAliases[R]) |
935 | 1.06k | continue; |
936 | 3.81k | if (R == AntiDepReg || TRI->isSubRegister(AntiDepReg, R)587 ) |
937 | 3.50k | continue; |
938 | 310 | AntiDepReg = 0; |
939 | 310 | break; |
940 | 310 | } |
941 | 3.31k | |
942 | 3.31k | if (AntiDepReg == 0) continue310 ; |
943 | 3.00k | } |
944 | 3.00k | |
945 | 3.00k | assert(AntiDepReg != 0); |
946 | 3.00k | if (AntiDepReg == 0) continue0 ; |
947 | 3.00k | |
948 | 3.00k | // Determine AntiDepReg's register group. |
949 | 3.00k | const unsigned GroupIndex = State->GetGroup(AntiDepReg); |
950 | 3.00k | if (GroupIndex == 0) { |
951 | 2.04k | LLVM_DEBUG(dbgs() << " (zero group)\n"); |
952 | 2.04k | continue; |
953 | 2.04k | } |
954 | 968 | |
955 | 968 | LLVM_DEBUG(dbgs() << '\n'); |
956 | 968 | |
957 | 968 | // Look for a suitable register to use to break the anti-dependence. |
958 | 968 | std::map<unsigned, unsigned> RenameMap; |
959 | 968 | if (FindSuitableFreeRegisters(GroupIndex, RenameOrder, RenameMap)) { |
960 | 752 | LLVM_DEBUG(dbgs() << "\tBreaking anti-dependence edge on " |
961 | 752 | << printReg(AntiDepReg, TRI) << ":"); |
962 | 752 | |
963 | 752 | // Handle each group register... |
964 | 752 | for (std::map<unsigned, unsigned>::iterator |
965 | 1.55k | S = RenameMap.begin(), E = RenameMap.end(); S != E; ++S807 ) { |
966 | 807 | unsigned CurrReg = S->first; |
967 | 807 | unsigned NewReg = S->second; |
968 | 807 | |
969 | 807 | LLVM_DEBUG(dbgs() << " " << printReg(CurrReg, TRI) << "->" |
970 | 807 | << printReg(NewReg, TRI) << "(" |
971 | 807 | << RegRefs.count(CurrReg) << " refs)"); |
972 | 807 | |
973 | 807 | // Update the references to the old register CurrReg to |
974 | 807 | // refer to the new register NewReg. |
975 | 1.71k | for (const auto &Q : make_range(RegRefs.equal_range(CurrReg))) { |
976 | 1.71k | Q.second.Operand->setReg(NewReg); |
977 | 1.71k | // If the SU for the instruction being updated has debug |
978 | 1.71k | // information related to the anti-dependency register, make |
979 | 1.71k | // sure to update that as well. |
980 | 1.71k | const SUnit *SU = MISUnitMap[Q.second.Operand->getParent()]; |
981 | 1.71k | if (!SU) continue0 ; |
982 | 1.71k | UpdateDbgValues(DbgValues, Q.second.Operand->getParent(), |
983 | 1.71k | AntiDepReg, NewReg); |
984 | 1.71k | } |
985 | 807 | |
986 | 807 | // We just went back in time and modified history; the |
987 | 807 | // liveness information for CurrReg is now inconsistent. Set |
988 | 807 | // the state as if it were dead. |
989 | 807 | State->UnionGroups(NewReg, 0); |
990 | 807 | RegRefs.erase(NewReg); |
991 | 807 | DefIndices[NewReg] = DefIndices[CurrReg]; |
992 | 807 | KillIndices[NewReg] = KillIndices[CurrReg]; |
993 | 807 | |
994 | 807 | State->UnionGroups(CurrReg, 0); |
995 | 807 | RegRefs.erase(CurrReg); |
996 | 807 | DefIndices[CurrReg] = KillIndices[CurrReg]; |
997 | 807 | KillIndices[CurrReg] = ~0u; |
998 | 807 | assert(((KillIndices[CurrReg] == ~0u) != |
999 | 807 | (DefIndices[CurrReg] == ~0u)) && |
1000 | 807 | "Kill and Def maps aren't consistent for AntiDepReg!"); |
1001 | 807 | } |
1002 | 752 | |
1003 | 752 | ++Broken; |
1004 | 752 | LLVM_DEBUG(dbgs() << '\n'); |
1005 | 752 | } |
1006 | 968 | } |
1007 | 21.4k | } |
1008 | 21.4k | |
1009 | 21.4k | ScanInstruction(MI, Count); |
1010 | 21.4k | } |
1011 | 5.30k | |
1012 | 5.30k | return Broken; |
1013 | 5.30k | } |