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