1
//===----- CriticalAntiDepBreaker.cpp - Anti-dep breaker -------- ---------===//
3
// The LLVM Compiler Infrastructure
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
8
//===----------------------------------------------------------------------===//
10
// This file implements the CriticalAntiDepBreaker class, which
11
// implements register anti-dependence breaking along a blocks
12
// critical path during post-RA scheduler.
14
//===----------------------------------------------------------------------===//
16
#include "CriticalAntiDepBreaker.h"
17
#include "llvm/CodeGen/MachineBasicBlock.h"
18
#include "llvm/CodeGen/MachineFrameInfo.h"
19
#include "llvm/Support/Debug.h"
20
#include "llvm/Support/ErrorHandling.h"
21
#include "llvm/Support/raw_ostream.h"
22
#include "llvm/Target/TargetInstrInfo.h"
23
#include "llvm/Target/TargetRegisterInfo.h"
24
#include "llvm/Target/TargetSubtargetInfo.h"
28
#define DEBUG_TYPE "post-RA-sched"
30
CriticalAntiDepBreaker::CriticalAntiDepBreaker(MachineFunction &MFi,
31
const RegisterClassInfo &RCI)
32
: AntiDepBreaker(), MF(MFi), MRI(MF.getRegInfo()),
33
TII(MF.getSubtarget().getInstrInfo()),
34
TRI(MF.getSubtarget().getRegisterInfo()), RegClassInfo(RCI),
35
Classes(TRI->getNumRegs(), nullptr), KillIndices(TRI->getNumRegs(), 0),
36
DefIndices(TRI->getNumRegs(), 0), KeepRegs(TRI->getNumRegs(), false) {}
38
CriticalAntiDepBreaker::~CriticalAntiDepBreaker() {
41
void CriticalAntiDepBreaker::StartBlock(MachineBasicBlock *BB) {
42
const unsigned BBSize = BB->size();
43
for (unsigned i = 0, e = TRI->getNumRegs(); i != e; ++i) {
44
// Clear out the register class data.
47
// Initialize the indices to indicate that no registers are live.
49
DefIndices[i] = BBSize;
52
// Clear "do not change" set.
55
bool IsReturnBlock = (BBSize != 0 && BB->back().isReturn());
57
// Examine the live-in regs of all successors.
58
for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
59
SE = BB->succ_end(); SI != SE; ++SI)
60
for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(),
61
E = (*SI)->livein_end(); I != E; ++I) {
62
for (MCRegAliasIterator AI(*I, TRI, true); AI.isValid(); ++AI) {
64
Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
65
KillIndices[Reg] = BBSize;
66
DefIndices[Reg] = ~0u;
70
// Mark live-out callee-saved registers. In a return block this is
71
// all callee-saved registers. In non-return this is any
72
// callee-saved register that is not saved in the prolog.
73
const MachineFrameInfo *MFI = MF.getFrameInfo();
74
BitVector Pristine = MFI->getPristineRegs(MF);
75
for (const MCPhysReg *I = TRI->getCalleeSavedRegs(&MF); *I; ++I) {
76
if (!IsReturnBlock && !Pristine.test(*I)) continue;
77
for (MCRegAliasIterator AI(*I, TRI, true); AI.isValid(); ++AI) {
79
Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
80
KillIndices[Reg] = BBSize;
81
DefIndices[Reg] = ~0u;
86
void CriticalAntiDepBreaker::FinishBlock() {
91
void CriticalAntiDepBreaker::Observe(MachineInstr *MI, unsigned Count,
92
unsigned InsertPosIndex) {
93
// Kill instructions can define registers but are really nops, and there might
94
// be a real definition earlier that needs to be paired with uses dominated by
97
// FIXME: It may be possible to remove the isKill() restriction once PR18663
98
// has been properly fixed. There can be value in processing kills as seen in
99
// the AggressiveAntiDepBreaker class.
100
if (MI->isDebugValue() || MI->isKill())
102
assert(Count < InsertPosIndex && "Instruction index out of expected range!");
104
for (unsigned Reg = 0; Reg != TRI->getNumRegs(); ++Reg) {
105
if (KillIndices[Reg] != ~0u) {
106
// If Reg is currently live, then mark that it can't be renamed as
107
// we don't know the extent of its live-range anymore (now that it
108
// has been scheduled).
109
Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
110
KillIndices[Reg] = Count;
111
} else if (DefIndices[Reg] < InsertPosIndex && DefIndices[Reg] >= Count) {
112
// Any register which was defined within the previous scheduling region
113
// may have been rescheduled and its lifetime may overlap with registers
114
// in ways not reflected in our current liveness state. For each such
115
// register, adjust the liveness state to be conservatively correct.
116
Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
118
// Move the def index to the end of the previous region, to reflect
119
// that the def could theoretically have been scheduled at the end.
120
DefIndices[Reg] = InsertPosIndex;
124
PrescanInstruction(MI);
125
ScanInstruction(MI, Count);
128
/// CriticalPathStep - Return the next SUnit after SU on the bottom-up
130
static const SDep *CriticalPathStep(const SUnit *SU) {
131
const SDep *Next = nullptr;
132
unsigned NextDepth = 0;
133
// Find the predecessor edge with the greatest depth.
134
for (SUnit::const_pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end();
136
const SUnit *PredSU = P->getSUnit();
137
unsigned PredLatency = P->getLatency();
138
unsigned PredTotalLatency = PredSU->getDepth() + PredLatency;
139
// In the case of a latency tie, prefer an anti-dependency edge over
140
// other types of edges.
141
if (NextDepth < PredTotalLatency ||
142
(NextDepth == PredTotalLatency && P->getKind() == SDep::Anti)) {
143
NextDepth = PredTotalLatency;
150
void CriticalAntiDepBreaker::PrescanInstruction(MachineInstr *MI) {
151
// It's not safe to change register allocation for source operands of
152
// instructions that have special allocation requirements. Also assume all
153
// registers used in a call must not be changed (ABI).
154
// FIXME: The issue with predicated instruction is more complex. We are being
155
// conservative here because the kill markers cannot be trusted after
157
// %R6<def> = LDR %SP, %reg0, 92, pred:14, pred:%reg0; mem:LD4[FixedStack14]
159
// STR %R0, %R6<kill>, %reg0, 0, pred:0, pred:%CPSR; mem:ST4[%395]
160
// %R6<def> = LDR %SP, %reg0, 100, pred:0, pred:%CPSR; mem:LD4[FixedStack12]
161
// STR %R0, %R6<kill>, %reg0, 0, pred:14, pred:%reg0; mem:ST4[%396](align=8)
163
// The first R6 kill is not really a kill since it's killed by a predicated
164
// instruction which may not be executed. The second R6 def may or may not
165
// re-define R6 so it's not safe to change it since the last R6 use cannot be
167
bool Special = MI->isCall() ||
168
MI->hasExtraSrcRegAllocReq() ||
169
TII->isPredicated(MI);
171
// Scan the register operands for this instruction and update
172
// Classes and RegRefs.
173
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
174
MachineOperand &MO = MI->getOperand(i);
175
if (!MO.isReg()) continue;
176
unsigned Reg = MO.getReg();
177
if (Reg == 0) continue;
178
const TargetRegisterClass *NewRC = nullptr;
180
if (i < MI->getDesc().getNumOperands())
181
NewRC = TII->getRegClass(MI->getDesc(), i, TRI, MF);
183
// For now, only allow the register to be changed if its register
184
// class is consistent across all uses.
185
if (!Classes[Reg] && NewRC)
186
Classes[Reg] = NewRC;
187
else if (!NewRC || Classes[Reg] != NewRC)
188
Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
190
// Now check for aliases.
191
for (MCRegAliasIterator AI(Reg, TRI, false); AI.isValid(); ++AI) {
192
// If an alias of the reg is used during the live range, give up.
193
// Note that this allows us to skip checking if AntiDepReg
194
// overlaps with any of the aliases, among other things.
195
unsigned AliasReg = *AI;
196
if (Classes[AliasReg]) {
197
Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1);
198
Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
202
// If we're still willing to consider this register, note the reference.
203
if (Classes[Reg] != reinterpret_cast<TargetRegisterClass *>(-1))
204
RegRefs.insert(std::make_pair(Reg, &MO));
206
// If this reg is tied and live (Classes[Reg] is set to -1), we can't change
207
// it or any of its sub or super regs. We need to use KeepRegs to mark the
208
// reg because not all uses of the same reg within an instruction are
209
// necessarily tagged as tied.
210
// Example: an x86 "xor %eax, %eax" will have one source operand tied to the
211
// def register but not the second (see PR20020 for details).
212
// FIXME: can this check be relaxed to account for undef uses
213
// of a register? In the above 'xor' example, the uses of %eax are undef, so
214
// earlier instructions could still replace %eax even though the 'xor'
215
// itself can't be changed.
216
if (MI->isRegTiedToUseOperand(i) &&
217
Classes[Reg] == reinterpret_cast<TargetRegisterClass *>(-1)) {
218
for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
219
SubRegs.isValid(); ++SubRegs) {
220
KeepRegs.set(*SubRegs);
222
for (MCSuperRegIterator SuperRegs(Reg, TRI);
223
SuperRegs.isValid(); ++SuperRegs) {
224
KeepRegs.set(*SuperRegs);
228
if (MO.isUse() && Special) {
229
if (!KeepRegs.test(Reg)) {
230
for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
231
SubRegs.isValid(); ++SubRegs)
232
KeepRegs.set(*SubRegs);
238
void CriticalAntiDepBreaker::ScanInstruction(MachineInstr *MI,
241
// Proceeding upwards, registers that are defed but not used in this
242
// instruction are now dead.
243
assert(!MI->isKill() && "Attempting to scan a kill instruction");
245
if (!TII->isPredicated(MI)) {
246
// Predicated defs are modeled as read + write, i.e. similar to two
248
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
249
MachineOperand &MO = MI->getOperand(i);
252
for (unsigned i = 0, e = TRI->getNumRegs(); i != e; ++i)
253
if (MO.clobbersPhysReg(i)) {
254
DefIndices[i] = Count;
255
KillIndices[i] = ~0u;
257
Classes[i] = nullptr;
261
if (!MO.isReg()) continue;
262
unsigned Reg = MO.getReg();
263
if (Reg == 0) continue;
264
if (!MO.isDef()) continue;
266
// If we've already marked this reg as unchangeable, carry on.
267
if (KeepRegs.test(Reg)) continue;
269
// Ignore two-addr defs.
270
if (MI->isRegTiedToUseOperand(i)) continue;
272
// For the reg itself and all subregs: update the def to current;
273
// reset the kill state, any restrictions, and references.
274
for (MCSubRegIterator SRI(Reg, TRI, true); SRI.isValid(); ++SRI) {
275
unsigned SubregReg = *SRI;
276
DefIndices[SubregReg] = Count;
277
KillIndices[SubregReg] = ~0u;
278
KeepRegs.reset(SubregReg);
279
Classes[SubregReg] = nullptr;
280
RegRefs.erase(SubregReg);
282
// Conservatively mark super-registers as unusable.
283
for (MCSuperRegIterator SR(Reg, TRI); SR.isValid(); ++SR)
284
Classes[*SR] = reinterpret_cast<TargetRegisterClass *>(-1);
287
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
288
MachineOperand &MO = MI->getOperand(i);
289
if (!MO.isReg()) continue;
290
unsigned Reg = MO.getReg();
291
if (Reg == 0) continue;
292
if (!MO.isUse()) continue;
294
const TargetRegisterClass *NewRC = nullptr;
295
if (i < MI->getDesc().getNumOperands())
296
NewRC = TII->getRegClass(MI->getDesc(), i, TRI, MF);
298
// For now, only allow the register to be changed if its register
299
// class is consistent across all uses.
300
if (!Classes[Reg] && NewRC)
301
Classes[Reg] = NewRC;
302
else if (!NewRC || Classes[Reg] != NewRC)
303
Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
305
RegRefs.insert(std::make_pair(Reg, &MO));
307
// It wasn't previously live but now it is, this is a kill.
308
// Repeat for all aliases.
309
for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
310
unsigned AliasReg = *AI;
311
if (KillIndices[AliasReg] == ~0u) {
312
KillIndices[AliasReg] = Count;
313
DefIndices[AliasReg] = ~0u;
319
// Check all machine operands that reference the antidependent register and must
320
// be replaced by NewReg. Return true if any of their parent instructions may
321
// clobber the new register.
323
// Note: AntiDepReg may be referenced by a two-address instruction such that
324
// it's use operand is tied to a def operand. We guard against the case in which
325
// the two-address instruction also defines NewReg, as may happen with
326
// pre/postincrement loads. In this case, both the use and def operands are in
327
// RegRefs because the def is inserted by PrescanInstruction and not erased
328
// during ScanInstruction. So checking for an instruction with definitions of
329
// both NewReg and AntiDepReg covers it.
331
CriticalAntiDepBreaker::isNewRegClobberedByRefs(RegRefIter RegRefBegin,
332
RegRefIter RegRefEnd,
335
for (RegRefIter I = RegRefBegin; I != RegRefEnd; ++I ) {
336
MachineOperand *RefOper = I->second;
338
// Don't allow the instruction defining AntiDepReg to earlyclobber its
339
// operands, in case they may be assigned to NewReg. In this case antidep
340
// breaking must fail, but it's too rare to bother optimizing.
341
if (RefOper->isDef() && RefOper->isEarlyClobber())
344
// Handle cases in which this instruction defines NewReg.
345
MachineInstr *MI = RefOper->getParent();
346
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
347
const MachineOperand &CheckOper = MI->getOperand(i);
349
if (CheckOper.isRegMask() && CheckOper.clobbersPhysReg(NewReg))
352
if (!CheckOper.isReg() || !CheckOper.isDef() ||
353
CheckOper.getReg() != NewReg)
356
// Don't allow the instruction to define NewReg and AntiDepReg.
357
// When AntiDepReg is renamed it will be an illegal op.
358
if (RefOper->isDef())
361
// Don't allow an instruction using AntiDepReg to be earlyclobbered by
363
if (CheckOper.isEarlyClobber())
366
// Don't allow inline asm to define NewReg at all. Who knows what it's
368
if (MI->isInlineAsm())
375
unsigned CriticalAntiDepBreaker::
376
findSuitableFreeRegister(RegRefIter RegRefBegin,
377
RegRefIter RegRefEnd,
380
const TargetRegisterClass *RC,
381
SmallVectorImpl<unsigned> &Forbid)
383
ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(RC);
384
for (unsigned i = 0; i != Order.size(); ++i) {
385
unsigned NewReg = Order[i];
386
// Don't replace a register with itself.
387
if (NewReg == AntiDepReg) continue;
388
// Don't replace a register with one that was recently used to repair
389
// an anti-dependence with this AntiDepReg, because that would
390
// re-introduce that anti-dependence.
391
if (NewReg == LastNewReg) continue;
392
// If any instructions that define AntiDepReg also define the NewReg, it's
393
// not suitable. For example, Instruction with multiple definitions can
394
// result in this condition.
395
if (isNewRegClobberedByRefs(RegRefBegin, RegRefEnd, NewReg)) continue;
396
// If NewReg is dead and NewReg's most recent def is not before
397
// AntiDepReg's kill, it's safe to replace AntiDepReg with NewReg.
398
assert(((KillIndices[AntiDepReg] == ~0u) != (DefIndices[AntiDepReg] == ~0u))
399
&& "Kill and Def maps aren't consistent for AntiDepReg!");
400
assert(((KillIndices[NewReg] == ~0u) != (DefIndices[NewReg] == ~0u))
401
&& "Kill and Def maps aren't consistent for NewReg!");
402
if (KillIndices[NewReg] != ~0u ||
403
Classes[NewReg] == reinterpret_cast<TargetRegisterClass *>(-1) ||
404
KillIndices[AntiDepReg] > DefIndices[NewReg])
406
// If NewReg overlaps any of the forbidden registers, we can't use it.
407
bool Forbidden = false;
408
for (SmallVectorImpl<unsigned>::iterator it = Forbid.begin(),
409
ite = Forbid.end(); it != ite; ++it)
410
if (TRI->regsOverlap(NewReg, *it)) {
414
if (Forbidden) continue;
418
// No registers are free and available!
422
unsigned CriticalAntiDepBreaker::
423
BreakAntiDependencies(const std::vector<SUnit>& SUnits,
424
MachineBasicBlock::iterator Begin,
425
MachineBasicBlock::iterator End,
426
unsigned InsertPosIndex,
427
DbgValueVector &DbgValues) {
428
// The code below assumes that there is at least one instruction,
429
// so just duck out immediately if the block is empty.
430
if (SUnits.empty()) return 0;
432
// Keep a map of the MachineInstr*'s back to the SUnit representing them.
433
// This is used for updating debug information.
435
// FIXME: Replace this with the existing map in ScheduleDAGInstrs::MISUnitMap
436
DenseMap<MachineInstr*,const SUnit*> MISUnitMap;
438
// Find the node at the bottom of the critical path.
439
const SUnit *Max = nullptr;
440
for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
441
const SUnit *SU = &SUnits[i];
442
MISUnitMap[SU->getInstr()] = SU;
443
if (!Max || SU->getDepth() + SU->Latency > Max->getDepth() + Max->Latency)
449
DEBUG(dbgs() << "Critical path has total latency "
450
<< (Max->getDepth() + Max->Latency) << "\n");
451
DEBUG(dbgs() << "Available regs:");
452
for (unsigned Reg = 0; Reg < TRI->getNumRegs(); ++Reg) {
453
if (KillIndices[Reg] == ~0u)
454
DEBUG(dbgs() << " " << TRI->getName(Reg));
456
DEBUG(dbgs() << '\n');
460
// Track progress along the critical path through the SUnit graph as we walk
462
const SUnit *CriticalPathSU = Max;
463
MachineInstr *CriticalPathMI = CriticalPathSU->getInstr();
465
// Consider this pattern:
474
// There are three anti-dependencies here, and without special care,
475
// we'd break all of them using the same register:
484
// because at each anti-dependence, B is the first register that
485
// isn't A which is free. This re-introduces anti-dependencies
486
// at all but one of the original anti-dependencies that we were
487
// trying to break. To avoid this, keep track of the most recent
488
// register that each register was replaced with, avoid
489
// using it to repair an anti-dependence on the same register.
490
// This lets us produce this:
499
// This still has an anti-dependence on B, but at least it isn't on the
500
// original critical path.
502
// TODO: If we tracked more than one register here, we could potentially
503
// fix that remaining critical edge too. This is a little more involved,
504
// because unlike the most recent register, less recent registers should
505
// still be considered, though only if no other registers are available.
506
std::vector<unsigned> LastNewReg(TRI->getNumRegs(), 0);
508
// Attempt to break anti-dependence edges on the critical path. Walk the
509
// instructions from the bottom up, tracking information about liveness
510
// as we go to help determine which registers are available.
512
unsigned Count = InsertPosIndex - 1;
513
for (MachineBasicBlock::iterator I = End, E = Begin; I != E; --Count) {
514
MachineInstr *MI = --I;
515
// Kill instructions can define registers but are really nops, and there
516
// might be a real definition earlier that needs to be paired with uses
517
// dominated by this kill.
519
// FIXME: It may be possible to remove the isKill() restriction once PR18663
520
// has been properly fixed. There can be value in processing kills as seen
521
// in the AggressiveAntiDepBreaker class.
522
if (MI->isDebugValue() || MI->isKill())
525
// Check if this instruction has a dependence on the critical path that
526
// is an anti-dependence that we may be able to break. If it is, set
527
// AntiDepReg to the non-zero register associated with the anti-dependence.
529
// We limit our attention to the critical path as a heuristic to avoid
530
// breaking anti-dependence edges that aren't going to significantly
531
// impact the overall schedule. There are a limited number of registers
532
// and we want to save them for the important edges.
534
// TODO: Instructions with multiple defs could have multiple
535
// anti-dependencies. The current code here only knows how to break one
536
// edge per instruction. Note that we'd have to be able to break all of
537
// the anti-dependencies in an instruction in order to be effective.
538
unsigned AntiDepReg = 0;
539
if (MI == CriticalPathMI) {
540
if (const SDep *Edge = CriticalPathStep(CriticalPathSU)) {
541
const SUnit *NextSU = Edge->getSUnit();
543
// Only consider anti-dependence edges.
544
if (Edge->getKind() == SDep::Anti) {
545
AntiDepReg = Edge->getReg();
546
assert(AntiDepReg != 0 && "Anti-dependence on reg0?");
547
if (!MRI.isAllocatable(AntiDepReg))
548
// Don't break anti-dependencies on non-allocatable registers.
550
else if (KeepRegs.test(AntiDepReg))
551
// Don't break anti-dependencies if a use down below requires
552
// this exact register.
555
// If the SUnit has other dependencies on the SUnit that it
556
// anti-depends on, don't bother breaking the anti-dependency
557
// since those edges would prevent such units from being
558
// scheduled past each other regardless.
560
// Also, if there are dependencies on other SUnits with the
561
// same register as the anti-dependency, don't attempt to
563
for (SUnit::const_pred_iterator P = CriticalPathSU->Preds.begin(),
564
PE = CriticalPathSU->Preds.end(); P != PE; ++P)
565
if (P->getSUnit() == NextSU ?
566
(P->getKind() != SDep::Anti || P->getReg() != AntiDepReg) :
567
(P->getKind() == SDep::Data && P->getReg() == AntiDepReg)) {
573
CriticalPathSU = NextSU;
574
CriticalPathMI = CriticalPathSU->getInstr();
576
// We've reached the end of the critical path.
577
CriticalPathSU = nullptr;
578
CriticalPathMI = nullptr;
582
PrescanInstruction(MI);
584
SmallVector<unsigned, 2> ForbidRegs;
586
// If MI's defs have a special allocation requirement, don't allow
587
// any def registers to be changed. Also assume all registers
588
// defined in a call must not be changed (ABI).
589
if (MI->isCall() || MI->hasExtraDefRegAllocReq() || TII->isPredicated(MI))
590
// If this instruction's defs have special allocation requirement, don't
591
// break this anti-dependency.
593
else if (AntiDepReg) {
594
// If this instruction has a use of AntiDepReg, breaking it
595
// is invalid. If the instruction defines other registers,
596
// save a list of them so that we don't pick a new register
597
// that overlaps any of them.
598
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
599
MachineOperand &MO = MI->getOperand(i);
600
if (!MO.isReg()) continue;
601
unsigned Reg = MO.getReg();
602
if (Reg == 0) continue;
603
if (MO.isUse() && TRI->regsOverlap(AntiDepReg, Reg)) {
607
if (MO.isDef() && Reg != AntiDepReg)
608
ForbidRegs.push_back(Reg);
612
// Determine AntiDepReg's register class, if it is live and is
613
// consistently used within a single class.
614
const TargetRegisterClass *RC = AntiDepReg != 0 ? Classes[AntiDepReg]
616
assert((AntiDepReg == 0 || RC != nullptr) &&
617
"Register should be live if it's causing an anti-dependence!");
618
if (RC == reinterpret_cast<TargetRegisterClass *>(-1))
621
// Look for a suitable register to use to break the anti-dependence.
623
// TODO: Instead of picking the first free register, consider which might
625
if (AntiDepReg != 0) {
626
std::pair<std::multimap<unsigned, MachineOperand *>::iterator,
627
std::multimap<unsigned, MachineOperand *>::iterator>
628
Range = RegRefs.equal_range(AntiDepReg);
629
if (unsigned NewReg = findSuitableFreeRegister(Range.first, Range.second,
631
LastNewReg[AntiDepReg],
633
DEBUG(dbgs() << "Breaking anti-dependence edge on "
634
<< TRI->getName(AntiDepReg)
635
<< " with " << RegRefs.count(AntiDepReg) << " references"
636
<< " using " << TRI->getName(NewReg) << "!\n");
638
// Update the references to the old register to refer to the new
640
for (std::multimap<unsigned, MachineOperand *>::iterator
641
Q = Range.first, QE = Range.second; Q != QE; ++Q) {
642
Q->second->setReg(NewReg);
643
// If the SU for the instruction being updated has debug information
644
// related to the anti-dependency register, make sure to update that
646
const SUnit *SU = MISUnitMap[Q->second->getParent()];
648
for (DbgValueVector::iterator DVI = DbgValues.begin(),
649
DVE = DbgValues.end(); DVI != DVE; ++DVI)
650
if (DVI->second == Q->second->getParent())
651
UpdateDbgValue(DVI->first, AntiDepReg, NewReg);
654
// We just went back in time and modified history; the
655
// liveness information for the anti-dependence reg is now
656
// inconsistent. Set the state as if it were dead.
657
Classes[NewReg] = Classes[AntiDepReg];
658
DefIndices[NewReg] = DefIndices[AntiDepReg];
659
KillIndices[NewReg] = KillIndices[AntiDepReg];
660
assert(((KillIndices[NewReg] == ~0u) !=
661
(DefIndices[NewReg] == ~0u)) &&
662
"Kill and Def maps aren't consistent for NewReg!");
664
Classes[AntiDepReg] = nullptr;
665
DefIndices[AntiDepReg] = KillIndices[AntiDepReg];
666
KillIndices[AntiDepReg] = ~0u;
667
assert(((KillIndices[AntiDepReg] == ~0u) !=
668
(DefIndices[AntiDepReg] == ~0u)) &&
669
"Kill and Def maps aren't consistent for AntiDepReg!");
671
RegRefs.erase(AntiDepReg);
672
LastNewReg[AntiDepReg] = NewReg;
677
ScanInstruction(MI, Count);