File: | lib/CodeGen/CriticalAntiDepBreaker.cpp |
Warning: | line 477, column 34 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- CriticalAntiDepBreaker.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 CriticalAntiDepBreaker class, which | |||
10 | // implements register anti-dependence breaking along a blocks | |||
11 | // critical path during post-RA scheduler. | |||
12 | // | |||
13 | //===----------------------------------------------------------------------===// | |||
14 | ||||
15 | #include "CriticalAntiDepBreaker.h" | |||
16 | #include "llvm/ADT/ArrayRef.h" | |||
17 | #include "llvm/ADT/BitVector.h" | |||
18 | #include "llvm/ADT/DenseMap.h" | |||
19 | #include "llvm/ADT/SmallVector.h" | |||
20 | #include "llvm/CodeGen/MachineBasicBlock.h" | |||
21 | #include "llvm/CodeGen/MachineFrameInfo.h" | |||
22 | #include "llvm/CodeGen/MachineFunction.h" | |||
23 | #include "llvm/CodeGen/MachineInstr.h" | |||
24 | #include "llvm/CodeGen/MachineOperand.h" | |||
25 | #include "llvm/CodeGen/MachineRegisterInfo.h" | |||
26 | #include "llvm/CodeGen/RegisterClassInfo.h" | |||
27 | #include "llvm/CodeGen/ScheduleDAG.h" | |||
28 | #include "llvm/CodeGen/TargetInstrInfo.h" | |||
29 | #include "llvm/CodeGen/TargetRegisterInfo.h" | |||
30 | #include "llvm/CodeGen/TargetSubtargetInfo.h" | |||
31 | #include "llvm/MC/MCInstrDesc.h" | |||
32 | #include "llvm/MC/MCRegisterInfo.h" | |||
33 | #include "llvm/Support/Debug.h" | |||
34 | #include "llvm/Support/raw_ostream.h" | |||
35 | #include <cassert> | |||
36 | #include <map> | |||
37 | #include <utility> | |||
38 | #include <vector> | |||
39 | ||||
40 | using namespace llvm; | |||
41 | ||||
42 | #define DEBUG_TYPE"post-RA-sched" "post-RA-sched" | |||
43 | ||||
44 | CriticalAntiDepBreaker::CriticalAntiDepBreaker(MachineFunction &MFi, | |||
45 | const RegisterClassInfo &RCI) | |||
46 | : AntiDepBreaker(), MF(MFi), MRI(MF.getRegInfo()), | |||
47 | TII(MF.getSubtarget().getInstrInfo()), | |||
48 | TRI(MF.getSubtarget().getRegisterInfo()), RegClassInfo(RCI), | |||
49 | Classes(TRI->getNumRegs(), nullptr), KillIndices(TRI->getNumRegs(), 0), | |||
50 | DefIndices(TRI->getNumRegs(), 0), KeepRegs(TRI->getNumRegs(), false) {} | |||
51 | ||||
52 | CriticalAntiDepBreaker::~CriticalAntiDepBreaker() = default; | |||
53 | ||||
54 | void CriticalAntiDepBreaker::StartBlock(MachineBasicBlock *BB) { | |||
55 | const unsigned BBSize = BB->size(); | |||
56 | for (unsigned i = 0, e = TRI->getNumRegs(); i != e; ++i) { | |||
57 | // Clear out the register class data. | |||
58 | Classes[i] = nullptr; | |||
59 | ||||
60 | // Initialize the indices to indicate that no registers are live. | |||
61 | KillIndices[i] = ~0u; | |||
62 | DefIndices[i] = BBSize; | |||
63 | } | |||
64 | ||||
65 | // Clear "do not change" set. | |||
66 | KeepRegs.reset(); | |||
67 | ||||
68 | bool IsReturnBlock = BB->isReturnBlock(); | |||
69 | ||||
70 | // Examine the live-in regs of all successors. | |||
71 | for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), | |||
72 | SE = BB->succ_end(); SI != SE; ++SI) | |||
73 | for (const auto &LI : (*SI)->liveins()) { | |||
74 | for (MCRegAliasIterator AI(LI.PhysReg, TRI, true); AI.isValid(); ++AI) { | |||
75 | unsigned Reg = *AI; | |||
76 | Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); | |||
77 | KillIndices[Reg] = BBSize; | |||
78 | DefIndices[Reg] = ~0u; | |||
79 | } | |||
80 | } | |||
81 | ||||
82 | // Mark live-out callee-saved registers. In a return block this is | |||
83 | // all callee-saved registers. In non-return this is any | |||
84 | // callee-saved register that is not saved in the prolog. | |||
85 | const MachineFrameInfo &MFI = MF.getFrameInfo(); | |||
86 | BitVector Pristine = MFI.getPristineRegs(MF); | |||
87 | for (const MCPhysReg *I = MF.getRegInfo().getCalleeSavedRegs(); *I; | |||
88 | ++I) { | |||
89 | unsigned Reg = *I; | |||
90 | if (!IsReturnBlock && !Pristine.test(Reg)) | |||
91 | continue; | |||
92 | for (MCRegAliasIterator AI(*I, TRI, true); AI.isValid(); ++AI) { | |||
93 | unsigned Reg = *AI; | |||
94 | Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); | |||
95 | KillIndices[Reg] = BBSize; | |||
96 | DefIndices[Reg] = ~0u; | |||
97 | } | |||
98 | } | |||
99 | } | |||
100 | ||||
101 | void CriticalAntiDepBreaker::FinishBlock() { | |||
102 | RegRefs.clear(); | |||
103 | KeepRegs.reset(); | |||
104 | } | |||
105 | ||||
106 | void CriticalAntiDepBreaker::Observe(MachineInstr &MI, unsigned Count, | |||
107 | unsigned InsertPosIndex) { | |||
108 | // Kill instructions can define registers but are really nops, and there might | |||
109 | // be a real definition earlier that needs to be paired with uses dominated by | |||
110 | // this kill. | |||
111 | ||||
112 | // FIXME: It may be possible to remove the isKill() restriction once PR18663 | |||
113 | // has been properly fixed. There can be value in processing kills as seen in | |||
114 | // the AggressiveAntiDepBreaker class. | |||
115 | if (MI.isDebugInstr() || MI.isKill()) | |||
116 | return; | |||
117 | assert(Count < InsertPosIndex && "Instruction index out of expected range!")((Count < InsertPosIndex && "Instruction index out of expected range!" ) ? static_cast<void> (0) : __assert_fail ("Count < InsertPosIndex && \"Instruction index out of expected range!\"" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/CodeGen/CriticalAntiDepBreaker.cpp" , 117, __PRETTY_FUNCTION__)); | |||
118 | ||||
119 | for (unsigned Reg = 0; Reg != TRI->getNumRegs(); ++Reg) { | |||
120 | if (KillIndices[Reg] != ~0u) { | |||
121 | // If Reg is currently live, then mark that it can't be renamed as | |||
122 | // we don't know the extent of its live-range anymore (now that it | |||
123 | // has been scheduled). | |||
124 | Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); | |||
125 | KillIndices[Reg] = Count; | |||
126 | } else if (DefIndices[Reg] < InsertPosIndex && DefIndices[Reg] >= Count) { | |||
127 | // Any register which was defined within the previous scheduling region | |||
128 | // may have been rescheduled and its lifetime may overlap with registers | |||
129 | // in ways not reflected in our current liveness state. For each such | |||
130 | // register, adjust the liveness state to be conservatively correct. | |||
131 | Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); | |||
132 | ||||
133 | // Move the def index to the end of the previous region, to reflect | |||
134 | // that the def could theoretically have been scheduled at the end. | |||
135 | DefIndices[Reg] = InsertPosIndex; | |||
136 | } | |||
137 | } | |||
138 | ||||
139 | PrescanInstruction(MI); | |||
140 | ScanInstruction(MI, Count); | |||
141 | } | |||
142 | ||||
143 | /// CriticalPathStep - Return the next SUnit after SU on the bottom-up | |||
144 | /// critical path. | |||
145 | static const SDep *CriticalPathStep(const SUnit *SU) { | |||
146 | const SDep *Next = nullptr; | |||
147 | unsigned NextDepth = 0; | |||
148 | // Find the predecessor edge with the greatest depth. | |||
149 | for (SUnit::const_pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end(); | |||
150 | P != PE; ++P) { | |||
151 | const SUnit *PredSU = P->getSUnit(); | |||
152 | unsigned PredLatency = P->getLatency(); | |||
153 | unsigned PredTotalLatency = PredSU->getDepth() + PredLatency; | |||
154 | // In the case of a latency tie, prefer an anti-dependency edge over | |||
155 | // other types of edges. | |||
156 | if (NextDepth < PredTotalLatency || | |||
157 | (NextDepth == PredTotalLatency && P->getKind() == SDep::Anti)) { | |||
158 | NextDepth = PredTotalLatency; | |||
159 | Next = &*P; | |||
160 | } | |||
161 | } | |||
162 | return Next; | |||
163 | } | |||
164 | ||||
165 | void CriticalAntiDepBreaker::PrescanInstruction(MachineInstr &MI) { | |||
166 | // It's not safe to change register allocation for source operands of | |||
167 | // instructions that have special allocation requirements. Also assume all | |||
168 | // registers used in a call must not be changed (ABI). | |||
169 | // FIXME: The issue with predicated instruction is more complex. We are being | |||
170 | // conservative here because the kill markers cannot be trusted after | |||
171 | // if-conversion: | |||
172 | // %r6 = LDR %sp, %reg0, 92, 14, %reg0; mem:LD4[FixedStack14] | |||
173 | // ... | |||
174 | // STR %r0, killed %r6, %reg0, 0, 0, %cpsr; mem:ST4[%395] | |||
175 | // %r6 = LDR %sp, %reg0, 100, 0, %cpsr; mem:LD4[FixedStack12] | |||
176 | // STR %r0, killed %r6, %reg0, 0, 14, %reg0; mem:ST4[%396](align=8) | |||
177 | // | |||
178 | // The first R6 kill is not really a kill since it's killed by a predicated | |||
179 | // instruction which may not be executed. The second R6 def may or may not | |||
180 | // re-define R6 so it's not safe to change it since the last R6 use cannot be | |||
181 | // changed. | |||
182 | bool Special = | |||
183 | MI.isCall() || MI.hasExtraSrcRegAllocReq() || TII->isPredicated(MI); | |||
184 | ||||
185 | // Scan the register operands for this instruction and update | |||
186 | // Classes and RegRefs. | |||
187 | for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { | |||
188 | MachineOperand &MO = MI.getOperand(i); | |||
189 | if (!MO.isReg()) continue; | |||
190 | Register Reg = MO.getReg(); | |||
191 | if (Reg == 0) continue; | |||
192 | const TargetRegisterClass *NewRC = nullptr; | |||
193 | ||||
194 | if (i < MI.getDesc().getNumOperands()) | |||
195 | NewRC = TII->getRegClass(MI.getDesc(), i, TRI, MF); | |||
196 | ||||
197 | // For now, only allow the register to be changed if its register | |||
198 | // class is consistent across all uses. | |||
199 | if (!Classes[Reg] && NewRC) | |||
200 | Classes[Reg] = NewRC; | |||
201 | else if (!NewRC || Classes[Reg] != NewRC) | |||
202 | Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); | |||
203 | ||||
204 | // Now check for aliases. | |||
205 | for (MCRegAliasIterator AI(Reg, TRI, false); AI.isValid(); ++AI) { | |||
206 | // If an alias of the reg is used during the live range, give up. | |||
207 | // Note that this allows us to skip checking if AntiDepReg | |||
208 | // overlaps with any of the aliases, among other things. | |||
209 | unsigned AliasReg = *AI; | |||
210 | if (Classes[AliasReg]) { | |||
211 | Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1); | |||
212 | Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); | |||
213 | } | |||
214 | } | |||
215 | ||||
216 | // If we're still willing to consider this register, note the reference. | |||
217 | if (Classes[Reg] != reinterpret_cast<TargetRegisterClass *>(-1)) | |||
218 | RegRefs.insert(std::make_pair(Reg, &MO)); | |||
219 | ||||
220 | // If this reg is tied and live (Classes[Reg] is set to -1), we can't change | |||
221 | // it or any of its sub or super regs. We need to use KeepRegs to mark the | |||
222 | // reg because not all uses of the same reg within an instruction are | |||
223 | // necessarily tagged as tied. | |||
224 | // Example: an x86 "xor %eax, %eax" will have one source operand tied to the | |||
225 | // def register but not the second (see PR20020 for details). | |||
226 | // FIXME: can this check be relaxed to account for undef uses | |||
227 | // of a register? In the above 'xor' example, the uses of %eax are undef, so | |||
228 | // earlier instructions could still replace %eax even though the 'xor' | |||
229 | // itself can't be changed. | |||
230 | if (MI.isRegTiedToUseOperand(i) && | |||
231 | Classes[Reg] == reinterpret_cast<TargetRegisterClass *>(-1)) { | |||
232 | for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); | |||
233 | SubRegs.isValid(); ++SubRegs) { | |||
234 | KeepRegs.set(*SubRegs); | |||
235 | } | |||
236 | for (MCSuperRegIterator SuperRegs(Reg, TRI); | |||
237 | SuperRegs.isValid(); ++SuperRegs) { | |||
238 | KeepRegs.set(*SuperRegs); | |||
239 | } | |||
240 | } | |||
241 | ||||
242 | if (MO.isUse() && Special) { | |||
243 | if (!KeepRegs.test(Reg)) { | |||
244 | for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); | |||
245 | SubRegs.isValid(); ++SubRegs) | |||
246 | KeepRegs.set(*SubRegs); | |||
247 | } | |||
248 | } | |||
249 | } | |||
250 | } | |||
251 | ||||
252 | void CriticalAntiDepBreaker::ScanInstruction(MachineInstr &MI, unsigned Count) { | |||
253 | // Update liveness. | |||
254 | // Proceeding upwards, registers that are defed but not used in this | |||
255 | // instruction are now dead. | |||
256 | assert(!MI.isKill() && "Attempting to scan a kill instruction")((!MI.isKill() && "Attempting to scan a kill instruction" ) ? static_cast<void> (0) : __assert_fail ("!MI.isKill() && \"Attempting to scan a kill instruction\"" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/CodeGen/CriticalAntiDepBreaker.cpp" , 256, __PRETTY_FUNCTION__)); | |||
257 | ||||
258 | if (!TII->isPredicated(MI)) { | |||
259 | // Predicated defs are modeled as read + write, i.e. similar to two | |||
260 | // address updates. | |||
261 | for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { | |||
262 | MachineOperand &MO = MI.getOperand(i); | |||
263 | ||||
264 | if (MO.isRegMask()) | |||
265 | for (unsigned i = 0, e = TRI->getNumRegs(); i != e; ++i) | |||
266 | if (MO.clobbersPhysReg(i)) { | |||
267 | DefIndices[i] = Count; | |||
268 | KillIndices[i] = ~0u; | |||
269 | KeepRegs.reset(i); | |||
270 | Classes[i] = nullptr; | |||
271 | RegRefs.erase(i); | |||
272 | } | |||
273 | ||||
274 | if (!MO.isReg()) continue; | |||
275 | Register Reg = MO.getReg(); | |||
276 | if (Reg == 0) continue; | |||
277 | if (!MO.isDef()) continue; | |||
278 | ||||
279 | // Ignore two-addr defs. | |||
280 | if (MI.isRegTiedToUseOperand(i)) | |||
281 | continue; | |||
282 | ||||
283 | // If we've already marked this reg as unchangeable, don't remove | |||
284 | // it or any of its subregs from KeepRegs. | |||
285 | bool Keep = KeepRegs.test(Reg); | |||
286 | ||||
287 | // For the reg itself and all subregs: update the def to current; | |||
288 | // reset the kill state, any restrictions, and references. | |||
289 | for (MCSubRegIterator SRI(Reg, TRI, true); SRI.isValid(); ++SRI) { | |||
290 | unsigned SubregReg = *SRI; | |||
291 | DefIndices[SubregReg] = Count; | |||
292 | KillIndices[SubregReg] = ~0u; | |||
293 | Classes[SubregReg] = nullptr; | |||
294 | RegRefs.erase(SubregReg); | |||
295 | if (!Keep) | |||
296 | KeepRegs.reset(SubregReg); | |||
297 | } | |||
298 | // Conservatively mark super-registers as unusable. | |||
299 | for (MCSuperRegIterator SR(Reg, TRI); SR.isValid(); ++SR) | |||
300 | Classes[*SR] = reinterpret_cast<TargetRegisterClass *>(-1); | |||
301 | } | |||
302 | } | |||
303 | for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { | |||
304 | MachineOperand &MO = MI.getOperand(i); | |||
305 | if (!MO.isReg()) continue; | |||
306 | Register Reg = MO.getReg(); | |||
307 | if (Reg == 0) continue; | |||
308 | if (!MO.isUse()) continue; | |||
309 | ||||
310 | const TargetRegisterClass *NewRC = nullptr; | |||
311 | if (i < MI.getDesc().getNumOperands()) | |||
312 | NewRC = TII->getRegClass(MI.getDesc(), i, TRI, MF); | |||
313 | ||||
314 | // For now, only allow the register to be changed if its register | |||
315 | // class is consistent across all uses. | |||
316 | if (!Classes[Reg] && NewRC) | |||
317 | Classes[Reg] = NewRC; | |||
318 | else if (!NewRC || Classes[Reg] != NewRC) | |||
319 | Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); | |||
320 | ||||
321 | RegRefs.insert(std::make_pair(Reg, &MO)); | |||
322 | ||||
323 | // It wasn't previously live but now it is, this is a kill. | |||
324 | // Repeat for all aliases. | |||
325 | for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { | |||
326 | unsigned AliasReg = *AI; | |||
327 | if (KillIndices[AliasReg] == ~0u) { | |||
328 | KillIndices[AliasReg] = Count; | |||
329 | DefIndices[AliasReg] = ~0u; | |||
330 | } | |||
331 | } | |||
332 | } | |||
333 | } | |||
334 | ||||
335 | // Check all machine operands that reference the antidependent register and must | |||
336 | // be replaced by NewReg. Return true if any of their parent instructions may | |||
337 | // clobber the new register. | |||
338 | // | |||
339 | // Note: AntiDepReg may be referenced by a two-address instruction such that | |||
340 | // it's use operand is tied to a def operand. We guard against the case in which | |||
341 | // the two-address instruction also defines NewReg, as may happen with | |||
342 | // pre/postincrement loads. In this case, both the use and def operands are in | |||
343 | // RegRefs because the def is inserted by PrescanInstruction and not erased | |||
344 | // during ScanInstruction. So checking for an instruction with definitions of | |||
345 | // both NewReg and AntiDepReg covers it. | |||
346 | bool | |||
347 | CriticalAntiDepBreaker::isNewRegClobberedByRefs(RegRefIter RegRefBegin, | |||
348 | RegRefIter RegRefEnd, | |||
349 | unsigned NewReg) { | |||
350 | for (RegRefIter I = RegRefBegin; I != RegRefEnd; ++I ) { | |||
351 | MachineOperand *RefOper = I->second; | |||
352 | ||||
353 | // Don't allow the instruction defining AntiDepReg to earlyclobber its | |||
354 | // operands, in case they may be assigned to NewReg. In this case antidep | |||
355 | // breaking must fail, but it's too rare to bother optimizing. | |||
356 | if (RefOper->isDef() && RefOper->isEarlyClobber()) | |||
357 | return true; | |||
358 | ||||
359 | // Handle cases in which this instruction defines NewReg. | |||
360 | MachineInstr *MI = RefOper->getParent(); | |||
361 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { | |||
362 | const MachineOperand &CheckOper = MI->getOperand(i); | |||
363 | ||||
364 | if (CheckOper.isRegMask() && CheckOper.clobbersPhysReg(NewReg)) | |||
365 | return true; | |||
366 | ||||
367 | if (!CheckOper.isReg() || !CheckOper.isDef() || | |||
368 | CheckOper.getReg() != NewReg) | |||
369 | continue; | |||
370 | ||||
371 | // Don't allow the instruction to define NewReg and AntiDepReg. | |||
372 | // When AntiDepReg is renamed it will be an illegal op. | |||
373 | if (RefOper->isDef()) | |||
374 | return true; | |||
375 | ||||
376 | // Don't allow an instruction using AntiDepReg to be earlyclobbered by | |||
377 | // NewReg. | |||
378 | if (CheckOper.isEarlyClobber()) | |||
379 | return true; | |||
380 | ||||
381 | // Don't allow inline asm to define NewReg at all. Who knows what it's | |||
382 | // doing with it. | |||
383 | if (MI->isInlineAsm()) | |||
384 | return true; | |||
385 | } | |||
386 | } | |||
387 | return false; | |||
388 | } | |||
389 | ||||
390 | unsigned CriticalAntiDepBreaker:: | |||
391 | findSuitableFreeRegister(RegRefIter RegRefBegin, | |||
392 | RegRefIter RegRefEnd, | |||
393 | unsigned AntiDepReg, | |||
394 | unsigned LastNewReg, | |||
395 | const TargetRegisterClass *RC, | |||
396 | SmallVectorImpl<unsigned> &Forbid) { | |||
397 | ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(RC); | |||
398 | for (unsigned i = 0; i != Order.size(); ++i) { | |||
399 | unsigned NewReg = Order[i]; | |||
400 | // Don't replace a register with itself. | |||
401 | if (NewReg == AntiDepReg) continue; | |||
402 | // Don't replace a register with one that was recently used to repair | |||
403 | // an anti-dependence with this AntiDepReg, because that would | |||
404 | // re-introduce that anti-dependence. | |||
405 | if (NewReg == LastNewReg) continue; | |||
406 | // If any instructions that define AntiDepReg also define the NewReg, it's | |||
407 | // not suitable. For example, Instruction with multiple definitions can | |||
408 | // result in this condition. | |||
409 | if (isNewRegClobberedByRefs(RegRefBegin, RegRefEnd, NewReg)) continue; | |||
410 | // If NewReg is dead and NewReg's most recent def is not before | |||
411 | // AntiDepReg's kill, it's safe to replace AntiDepReg with NewReg. | |||
412 | assert(((KillIndices[AntiDepReg] == ~0u) != (DefIndices[AntiDepReg] == ~0u))((((KillIndices[AntiDepReg] == ~0u) != (DefIndices[AntiDepReg ] == ~0u)) && "Kill and Def maps aren't consistent for AntiDepReg!" ) ? static_cast<void> (0) : __assert_fail ("((KillIndices[AntiDepReg] == ~0u) != (DefIndices[AntiDepReg] == ~0u)) && \"Kill and Def maps aren't consistent for AntiDepReg!\"" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/CodeGen/CriticalAntiDepBreaker.cpp" , 413, __PRETTY_FUNCTION__)) | |||
413 | && "Kill and Def maps aren't consistent for AntiDepReg!")((((KillIndices[AntiDepReg] == ~0u) != (DefIndices[AntiDepReg ] == ~0u)) && "Kill and Def maps aren't consistent for AntiDepReg!" ) ? static_cast<void> (0) : __assert_fail ("((KillIndices[AntiDepReg] == ~0u) != (DefIndices[AntiDepReg] == ~0u)) && \"Kill and Def maps aren't consistent for AntiDepReg!\"" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/CodeGen/CriticalAntiDepBreaker.cpp" , 413, __PRETTY_FUNCTION__)); | |||
414 | assert(((KillIndices[NewReg] == ~0u) != (DefIndices[NewReg] == ~0u))((((KillIndices[NewReg] == ~0u) != (DefIndices[NewReg] == ~0u )) && "Kill and Def maps aren't consistent for NewReg!" ) ? static_cast<void> (0) : __assert_fail ("((KillIndices[NewReg] == ~0u) != (DefIndices[NewReg] == ~0u)) && \"Kill and Def maps aren't consistent for NewReg!\"" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/CodeGen/CriticalAntiDepBreaker.cpp" , 415, __PRETTY_FUNCTION__)) | |||
415 | && "Kill and Def maps aren't consistent for NewReg!")((((KillIndices[NewReg] == ~0u) != (DefIndices[NewReg] == ~0u )) && "Kill and Def maps aren't consistent for NewReg!" ) ? static_cast<void> (0) : __assert_fail ("((KillIndices[NewReg] == ~0u) != (DefIndices[NewReg] == ~0u)) && \"Kill and Def maps aren't consistent for NewReg!\"" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/CodeGen/CriticalAntiDepBreaker.cpp" , 415, __PRETTY_FUNCTION__)); | |||
416 | if (KillIndices[NewReg] != ~0u || | |||
417 | Classes[NewReg] == reinterpret_cast<TargetRegisterClass *>(-1) || | |||
418 | KillIndices[AntiDepReg] > DefIndices[NewReg]) | |||
419 | continue; | |||
420 | // If NewReg overlaps any of the forbidden registers, we can't use it. | |||
421 | bool Forbidden = false; | |||
422 | for (SmallVectorImpl<unsigned>::iterator it = Forbid.begin(), | |||
423 | ite = Forbid.end(); it != ite; ++it) | |||
424 | if (TRI->regsOverlap(NewReg, *it)) { | |||
425 | Forbidden = true; | |||
426 | break; | |||
427 | } | |||
428 | if (Forbidden) continue; | |||
429 | return NewReg; | |||
430 | } | |||
431 | ||||
432 | // No registers are free and available! | |||
433 | return 0; | |||
434 | } | |||
435 | ||||
436 | unsigned CriticalAntiDepBreaker:: | |||
437 | BreakAntiDependencies(const std::vector<SUnit> &SUnits, | |||
438 | MachineBasicBlock::iterator Begin, | |||
439 | MachineBasicBlock::iterator End, | |||
440 | unsigned InsertPosIndex, | |||
441 | DbgValueVector &DbgValues) { | |||
442 | // The code below assumes that there is at least one instruction, | |||
443 | // so just duck out immediately if the block is empty. | |||
444 | if (SUnits.empty()) return 0; | |||
| ||||
445 | ||||
446 | // Keep a map of the MachineInstr*'s back to the SUnit representing them. | |||
447 | // This is used for updating debug information. | |||
448 | // | |||
449 | // FIXME: Replace this with the existing map in ScheduleDAGInstrs::MISUnitMap | |||
450 | DenseMap<MachineInstr *, const SUnit *> MISUnitMap; | |||
451 | ||||
452 | // Find the node at the bottom of the critical path. | |||
453 | const SUnit *Max = nullptr; | |||
454 | for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { | |||
455 | const SUnit *SU = &SUnits[i]; | |||
456 | MISUnitMap[SU->getInstr()] = SU; | |||
457 | if (!Max || SU->getDepth() + SU->Latency > Max->getDepth() + Max->Latency) | |||
458 | Max = SU; | |||
459 | } | |||
460 | ||||
461 | #ifndef NDEBUG | |||
462 | { | |||
463 | LLVM_DEBUG(dbgs() << "Critical path has total latency "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("post-RA-sched")) { dbgs() << "Critical path has total latency " << (Max->getDepth() + Max->Latency) << "\n" ; } } while (false) | |||
464 | << (Max->getDepth() + Max->Latency) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("post-RA-sched")) { dbgs() << "Critical path has total latency " << (Max->getDepth() + Max->Latency) << "\n" ; } } while (false); | |||
465 | LLVM_DEBUG
("post-RA-sched")) { dbgs() << "Available regs:"; } } while (false); | |||
466 | for (unsigned Reg = 0; Reg < TRI->getNumRegs(); ++Reg) { | |||
467 | if (KillIndices[Reg] == ~0u) | |||
468 | LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("post-RA-sched")) { dbgs() << " " << printReg(Reg , TRI); } } while (false); | |||
469 | } | |||
470 | LLVM_DEBUG
("post-RA-sched")) { dbgs() << '\n'; } } while (false); | |||
471 | } | |||
472 | #endif | |||
473 | ||||
474 | // Track progress along the critical path through the SUnit graph as we walk | |||
475 | // the instructions. | |||
476 | const SUnit *CriticalPathSU = Max; | |||
477 | MachineInstr *CriticalPathMI = CriticalPathSU->getInstr(); | |||
| ||||
478 | ||||
479 | // Consider this pattern: | |||
480 | // A = ... | |||
481 | // ... = A | |||
482 | // A = ... | |||
483 | // ... = A | |||
484 | // A = ... | |||
485 | // ... = A | |||
486 | // A = ... | |||
487 | // ... = A | |||
488 | // There are three anti-dependencies here, and without special care, | |||
489 | // we'd break all of them using the same register: | |||
490 | // A = ... | |||
491 | // ... = A | |||
492 | // B = ... | |||
493 | // ... = B | |||
494 | // B = ... | |||
495 | // ... = B | |||
496 | // B = ... | |||
497 | // ... = B | |||
498 | // because at each anti-dependence, B is the first register that | |||
499 | // isn't A which is free. This re-introduces anti-dependencies | |||
500 | // at all but one of the original anti-dependencies that we were | |||
501 | // trying to break. To avoid this, keep track of the most recent | |||
502 | // register that each register was replaced with, avoid | |||
503 | // using it to repair an anti-dependence on the same register. | |||
504 | // This lets us produce this: | |||
505 | // A = ... | |||
506 | // ... = A | |||
507 | // B = ... | |||
508 | // ... = B | |||
509 | // C = ... | |||
510 | // ... = C | |||
511 | // B = ... | |||
512 | // ... = B | |||
513 | // This still has an anti-dependence on B, but at least it isn't on the | |||
514 | // original critical path. | |||
515 | // | |||
516 | // TODO: If we tracked more than one register here, we could potentially | |||
517 | // fix that remaining critical edge too. This is a little more involved, | |||
518 | // because unlike the most recent register, less recent registers should | |||
519 | // still be considered, though only if no other registers are available. | |||
520 | std::vector<unsigned> LastNewReg(TRI->getNumRegs(), 0); | |||
521 | ||||
522 | // Attempt to break anti-dependence edges on the critical path. Walk the | |||
523 | // instructions from the bottom up, tracking information about liveness | |||
524 | // as we go to help determine which registers are available. | |||
525 | unsigned Broken = 0; | |||
526 | unsigned Count = InsertPosIndex - 1; | |||
527 | for (MachineBasicBlock::iterator I = End, E = Begin; I != E; --Count) { | |||
528 | MachineInstr &MI = *--I; | |||
529 | // Kill instructions can define registers but are really nops, and there | |||
530 | // might be a real definition earlier that needs to be paired with uses | |||
531 | // dominated by this kill. | |||
532 | ||||
533 | // FIXME: It may be possible to remove the isKill() restriction once PR18663 | |||
534 | // has been properly fixed. There can be value in processing kills as seen | |||
535 | // in the AggressiveAntiDepBreaker class. | |||
536 | if (MI.isDebugInstr() || MI.isKill()) | |||
537 | continue; | |||
538 | ||||
539 | // Check if this instruction has a dependence on the critical path that | |||
540 | // is an anti-dependence that we may be able to break. If it is, set | |||
541 | // AntiDepReg to the non-zero register associated with the anti-dependence. | |||
542 | // | |||
543 | // We limit our attention to the critical path as a heuristic to avoid | |||
544 | // breaking anti-dependence edges that aren't going to significantly | |||
545 | // impact the overall schedule. There are a limited number of registers | |||
546 | // and we want to save them for the important edges. | |||
547 | // | |||
548 | // TODO: Instructions with multiple defs could have multiple | |||
549 | // anti-dependencies. The current code here only knows how to break one | |||
550 | // edge per instruction. Note that we'd have to be able to break all of | |||
551 | // the anti-dependencies in an instruction in order to be effective. | |||
552 | unsigned AntiDepReg = 0; | |||
553 | if (&MI == CriticalPathMI) { | |||
554 | if (const SDep *Edge = CriticalPathStep(CriticalPathSU)) { | |||
555 | const SUnit *NextSU = Edge->getSUnit(); | |||
556 | ||||
557 | // Only consider anti-dependence edges. | |||
558 | if (Edge->getKind() == SDep::Anti) { | |||
559 | AntiDepReg = Edge->getReg(); | |||
560 | assert(AntiDepReg != 0 && "Anti-dependence on reg0?")((AntiDepReg != 0 && "Anti-dependence on reg0?") ? static_cast <void> (0) : __assert_fail ("AntiDepReg != 0 && \"Anti-dependence on reg0?\"" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/CodeGen/CriticalAntiDepBreaker.cpp" , 560, __PRETTY_FUNCTION__)); | |||
561 | if (!MRI.isAllocatable(AntiDepReg)) | |||
562 | // Don't break anti-dependencies on non-allocatable registers. | |||
563 | AntiDepReg = 0; | |||
564 | else if (KeepRegs.test(AntiDepReg)) | |||
565 | // Don't break anti-dependencies if a use down below requires | |||
566 | // this exact register. | |||
567 | AntiDepReg = 0; | |||
568 | else { | |||
569 | // If the SUnit has other dependencies on the SUnit that it | |||
570 | // anti-depends on, don't bother breaking the anti-dependency | |||
571 | // since those edges would prevent such units from being | |||
572 | // scheduled past each other regardless. | |||
573 | // | |||
574 | // Also, if there are dependencies on other SUnits with the | |||
575 | // same register as the anti-dependency, don't attempt to | |||
576 | // break it. | |||
577 | for (SUnit::const_pred_iterator P = CriticalPathSU->Preds.begin(), | |||
578 | PE = CriticalPathSU->Preds.end(); P != PE; ++P) | |||
579 | if (P->getSUnit() == NextSU ? | |||
580 | (P->getKind() != SDep::Anti || P->getReg() != AntiDepReg) : | |||
581 | (P->getKind() == SDep::Data && P->getReg() == AntiDepReg)) { | |||
582 | AntiDepReg = 0; | |||
583 | break; | |||
584 | } | |||
585 | } | |||
586 | } | |||
587 | CriticalPathSU = NextSU; | |||
588 | CriticalPathMI = CriticalPathSU->getInstr(); | |||
589 | } else { | |||
590 | // We've reached the end of the critical path. | |||
591 | CriticalPathSU = nullptr; | |||
592 | CriticalPathMI = nullptr; | |||
593 | } | |||
594 | } | |||
595 | ||||
596 | PrescanInstruction(MI); | |||
597 | ||||
598 | SmallVector<unsigned, 2> ForbidRegs; | |||
599 | ||||
600 | // If MI's defs have a special allocation requirement, don't allow | |||
601 | // any def registers to be changed. Also assume all registers | |||
602 | // defined in a call must not be changed (ABI). | |||
603 | if (MI.isCall() || MI.hasExtraDefRegAllocReq() || TII->isPredicated(MI)) | |||
604 | // If this instruction's defs have special allocation requirement, don't | |||
605 | // break this anti-dependency. | |||
606 | AntiDepReg = 0; | |||
607 | else if (AntiDepReg) { | |||
608 | // If this instruction has a use of AntiDepReg, breaking it | |||
609 | // is invalid. If the instruction defines other registers, | |||
610 | // save a list of them so that we don't pick a new register | |||
611 | // that overlaps any of them. | |||
612 | for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { | |||
613 | MachineOperand &MO = MI.getOperand(i); | |||
614 | if (!MO.isReg()) continue; | |||
615 | Register Reg = MO.getReg(); | |||
616 | if (Reg == 0) continue; | |||
617 | if (MO.isUse() && TRI->regsOverlap(AntiDepReg, Reg)) { | |||
618 | AntiDepReg = 0; | |||
619 | break; | |||
620 | } | |||
621 | if (MO.isDef() && Reg != AntiDepReg) | |||
622 | ForbidRegs.push_back(Reg); | |||
623 | } | |||
624 | } | |||
625 | ||||
626 | // Determine AntiDepReg's register class, if it is live and is | |||
627 | // consistently used within a single class. | |||
628 | const TargetRegisterClass *RC = AntiDepReg != 0 ? Classes[AntiDepReg] | |||
629 | : nullptr; | |||
630 | assert((AntiDepReg == 0 || RC != nullptr) &&(((AntiDepReg == 0 || RC != nullptr) && "Register should be live if it's causing an anti-dependence!" ) ? static_cast<void> (0) : __assert_fail ("(AntiDepReg == 0 || RC != nullptr) && \"Register should be live if it's causing an anti-dependence!\"" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/CodeGen/CriticalAntiDepBreaker.cpp" , 631, __PRETTY_FUNCTION__)) | |||
631 | "Register should be live if it's causing an anti-dependence!")(((AntiDepReg == 0 || RC != nullptr) && "Register should be live if it's causing an anti-dependence!" ) ? static_cast<void> (0) : __assert_fail ("(AntiDepReg == 0 || RC != nullptr) && \"Register should be live if it's causing an anti-dependence!\"" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/CodeGen/CriticalAntiDepBreaker.cpp" , 631, __PRETTY_FUNCTION__)); | |||
632 | if (RC == reinterpret_cast<TargetRegisterClass *>(-1)) | |||
633 | AntiDepReg = 0; | |||
634 | ||||
635 | // Look for a suitable register to use to break the anti-dependence. | |||
636 | // | |||
637 | // TODO: Instead of picking the first free register, consider which might | |||
638 | // be the best. | |||
639 | if (AntiDepReg != 0) { | |||
640 | std::pair<std::multimap<unsigned, MachineOperand *>::iterator, | |||
641 | std::multimap<unsigned, MachineOperand *>::iterator> | |||
642 | Range = RegRefs.equal_range(AntiDepReg); | |||
643 | if (unsigned NewReg = findSuitableFreeRegister(Range.first, Range.second, | |||
644 | AntiDepReg, | |||
645 | LastNewReg[AntiDepReg], | |||
646 | RC, ForbidRegs)) { | |||
647 | LLVM_DEBUG(dbgs() << "Breaking anti-dependence edge on "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("post-RA-sched")) { dbgs() << "Breaking anti-dependence edge on " << printReg(AntiDepReg, TRI) << " with " << RegRefs.count(AntiDepReg) << " references" << " using " << printReg(NewReg, TRI) << "!\n"; } } while (false ) | |||
648 | << printReg(AntiDepReg, TRI) << " with "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("post-RA-sched")) { dbgs() << "Breaking anti-dependence edge on " << printReg(AntiDepReg, TRI) << " with " << RegRefs.count(AntiDepReg) << " references" << " using " << printReg(NewReg, TRI) << "!\n"; } } while (false ) | |||
649 | << RegRefs.count(AntiDepReg) << " references"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("post-RA-sched")) { dbgs() << "Breaking anti-dependence edge on " << printReg(AntiDepReg, TRI) << " with " << RegRefs.count(AntiDepReg) << " references" << " using " << printReg(NewReg, TRI) << "!\n"; } } while (false ) | |||
650 | << " using " << printReg(NewReg, TRI) << "!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("post-RA-sched")) { dbgs() << "Breaking anti-dependence edge on " << printReg(AntiDepReg, TRI) << " with " << RegRefs.count(AntiDepReg) << " references" << " using " << printReg(NewReg, TRI) << "!\n"; } } while (false ); | |||
651 | ||||
652 | // Update the references to the old register to refer to the new | |||
653 | // register. | |||
654 | for (std::multimap<unsigned, MachineOperand *>::iterator | |||
655 | Q = Range.first, QE = Range.second; Q != QE; ++Q) { | |||
656 | Q->second->setReg(NewReg); | |||
657 | // If the SU for the instruction being updated has debug information | |||
658 | // related to the anti-dependency register, make sure to update that | |||
659 | // as well. | |||
660 | const SUnit *SU = MISUnitMap[Q->second->getParent()]; | |||
661 | if (!SU) continue; | |||
662 | UpdateDbgValues(DbgValues, Q->second->getParent(), | |||
663 | AntiDepReg, NewReg); | |||
664 | } | |||
665 | ||||
666 | // We just went back in time and modified history; the | |||
667 | // liveness information for the anti-dependence reg is now | |||
668 | // inconsistent. Set the state as if it were dead. | |||
669 | Classes[NewReg] = Classes[AntiDepReg]; | |||
670 | DefIndices[NewReg] = DefIndices[AntiDepReg]; | |||
671 | KillIndices[NewReg] = KillIndices[AntiDepReg]; | |||
672 | assert(((KillIndices[NewReg] == ~0u) !=((((KillIndices[NewReg] == ~0u) != (DefIndices[NewReg] == ~0u )) && "Kill and Def maps aren't consistent for NewReg!" ) ? static_cast<void> (0) : __assert_fail ("((KillIndices[NewReg] == ~0u) != (DefIndices[NewReg] == ~0u)) && \"Kill and Def maps aren't consistent for NewReg!\"" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/CodeGen/CriticalAntiDepBreaker.cpp" , 674, __PRETTY_FUNCTION__)) | |||
673 | (DefIndices[NewReg] == ~0u)) &&((((KillIndices[NewReg] == ~0u) != (DefIndices[NewReg] == ~0u )) && "Kill and Def maps aren't consistent for NewReg!" ) ? static_cast<void> (0) : __assert_fail ("((KillIndices[NewReg] == ~0u) != (DefIndices[NewReg] == ~0u)) && \"Kill and Def maps aren't consistent for NewReg!\"" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/CodeGen/CriticalAntiDepBreaker.cpp" , 674, __PRETTY_FUNCTION__)) | |||
674 | "Kill and Def maps aren't consistent for NewReg!")((((KillIndices[NewReg] == ~0u) != (DefIndices[NewReg] == ~0u )) && "Kill and Def maps aren't consistent for NewReg!" ) ? static_cast<void> (0) : __assert_fail ("((KillIndices[NewReg] == ~0u) != (DefIndices[NewReg] == ~0u)) && \"Kill and Def maps aren't consistent for NewReg!\"" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/CodeGen/CriticalAntiDepBreaker.cpp" , 674, __PRETTY_FUNCTION__)); | |||
675 | ||||
676 | Classes[AntiDepReg] = nullptr; | |||
677 | DefIndices[AntiDepReg] = KillIndices[AntiDepReg]; | |||
678 | KillIndices[AntiDepReg] = ~0u; | |||
679 | assert(((KillIndices[AntiDepReg] == ~0u) !=((((KillIndices[AntiDepReg] == ~0u) != (DefIndices[AntiDepReg ] == ~0u)) && "Kill and Def maps aren't consistent for AntiDepReg!" ) ? static_cast<void> (0) : __assert_fail ("((KillIndices[AntiDepReg] == ~0u) != (DefIndices[AntiDepReg] == ~0u)) && \"Kill and Def maps aren't consistent for AntiDepReg!\"" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/CodeGen/CriticalAntiDepBreaker.cpp" , 681, __PRETTY_FUNCTION__)) | |||
680 | (DefIndices[AntiDepReg] == ~0u)) &&((((KillIndices[AntiDepReg] == ~0u) != (DefIndices[AntiDepReg ] == ~0u)) && "Kill and Def maps aren't consistent for AntiDepReg!" ) ? static_cast<void> (0) : __assert_fail ("((KillIndices[AntiDepReg] == ~0u) != (DefIndices[AntiDepReg] == ~0u)) && \"Kill and Def maps aren't consistent for AntiDepReg!\"" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/CodeGen/CriticalAntiDepBreaker.cpp" , 681, __PRETTY_FUNCTION__)) | |||
681 | "Kill and Def maps aren't consistent for AntiDepReg!")((((KillIndices[AntiDepReg] == ~0u) != (DefIndices[AntiDepReg ] == ~0u)) && "Kill and Def maps aren't consistent for AntiDepReg!" ) ? static_cast<void> (0) : __assert_fail ("((KillIndices[AntiDepReg] == ~0u) != (DefIndices[AntiDepReg] == ~0u)) && \"Kill and Def maps aren't consistent for AntiDepReg!\"" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/CodeGen/CriticalAntiDepBreaker.cpp" , 681, __PRETTY_FUNCTION__)); | |||
682 | ||||
683 | RegRefs.erase(AntiDepReg); | |||
684 | LastNewReg[AntiDepReg] = NewReg; | |||
685 | ++Broken; | |||
686 | } | |||
687 | } | |||
688 | ||||
689 | ScanInstruction(MI, Count); | |||
690 | } | |||
691 | ||||
692 | return Broken; | |||
693 | } |