1 //===----- AggressiveAntiDepBreaker.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 AggressiveAntiDepBreaker class, which
11 // implements register anti-dependence breaking during post-RA
12 // scheduling. It attempts to break all anti-dependencies within a
15 //===----------------------------------------------------------------------===//
17 #include "AggressiveAntiDepBreaker.h"
18 #include "llvm/CodeGen/MachineBasicBlock.h"
19 #include "llvm/CodeGen/MachineFrameInfo.h"
20 #include "llvm/CodeGen/MachineInstr.h"
21 #include "llvm/CodeGen/RegisterClassInfo.h"
22 #include "llvm/Support/CommandLine.h"
23 #include "llvm/Support/Debug.h"
24 #include "llvm/Support/ErrorHandling.h"
25 #include "llvm/Support/raw_ostream.h"
26 #include "llvm/Target/TargetInstrInfo.h"
27 #include "llvm/Target/TargetRegisterInfo.h"
30 #define DEBUG_TYPE "post-RA-sched"
32 // If DebugDiv > 0 then only break antidep with (ID % DebugDiv) == DebugMod
34 DebugDiv("agg-antidep-debugdiv",
35 cl::desc("Debug control for aggressive anti-dep breaker"),
36 cl::init(0), cl::Hidden
);
38 DebugMod("agg-antidep-debugmod",
39 cl::desc("Debug control for aggressive anti-dep breaker"),
40 cl::init(0), cl::Hidden
);
42 AggressiveAntiDepState::AggressiveAntiDepState(const unsigned TargetRegs
,
43 MachineBasicBlock
*BB
) :
44 NumTargetRegs(TargetRegs
), GroupNodes(TargetRegs
, 0),
45 GroupNodeIndices(TargetRegs
, 0),
46 KillIndices(TargetRegs
, 0),
47 DefIndices(TargetRegs
, 0)
49 const unsigned BBSize
= BB
->size();
50 for (unsigned i
= 0; i
< NumTargetRegs
; ++i
) {
51 // Initialize all registers to be in their own group. Initially we
52 // assign the register to the same-indexed GroupNode.
53 GroupNodeIndices
[i
] = i
;
54 // Initialize the indices to indicate that no registers are live.
56 DefIndices
[i
] = BBSize
;
60 unsigned AggressiveAntiDepState::GetGroup(unsigned Reg
) {
61 unsigned Node
= GroupNodeIndices
[Reg
];
62 while (GroupNodes
[Node
] != Node
)
63 Node
= GroupNodes
[Node
];
68 void AggressiveAntiDepState::GetGroupRegs(
70 std::vector
<unsigned> &Regs
,
71 std::multimap
<unsigned, AggressiveAntiDepState::RegisterReference
> *RegRefs
)
73 for (unsigned Reg
= 0; Reg
!= NumTargetRegs
; ++Reg
) {
74 if ((GetGroup(Reg
) == Group
) && (RegRefs
->count(Reg
) > 0))
79 unsigned AggressiveAntiDepState::UnionGroups(unsigned Reg1
, unsigned Reg2
)
81 assert(GroupNodes
[0] == 0 && "GroupNode 0 not parent!");
82 assert(GroupNodeIndices
[0] == 0 && "Reg 0 not in Group 0!");
84 // find group for each register
85 unsigned Group1
= GetGroup(Reg1
);
86 unsigned Group2
= GetGroup(Reg2
);
88 // if either group is 0, then that must become the parent
89 unsigned Parent
= (Group1
== 0) ? Group1
: Group2
;
90 unsigned Other
= (Parent
== Group1
) ? Group2
: Group1
;
91 GroupNodes
.at(Other
) = Parent
;
95 unsigned AggressiveAntiDepState::LeaveGroup(unsigned Reg
)
97 // Create a new GroupNode for Reg. Reg's existing GroupNode must
98 // stay as is because there could be other GroupNodes referring to
100 unsigned idx
= GroupNodes
.size();
101 GroupNodes
.push_back(idx
);
102 GroupNodeIndices
[Reg
] = idx
;
106 bool AggressiveAntiDepState::IsLive(unsigned Reg
)
108 // KillIndex must be defined and DefIndex not defined for a register
110 return((KillIndices
[Reg
] != ~0u) && (DefIndices
[Reg
] == ~0u));
113 AggressiveAntiDepBreaker::AggressiveAntiDepBreaker(
114 MachineFunction
&MFi
, const RegisterClassInfo
&RCI
,
115 TargetSubtargetInfo::RegClassVector
&CriticalPathRCs
)
116 : AntiDepBreaker(), MF(MFi
), MRI(MF
.getRegInfo()),
117 TII(MF
.getSubtarget().getInstrInfo()),
118 TRI(MF
.getSubtarget().getRegisterInfo()), RegClassInfo(RCI
),
120 /* Collect a bitset of all registers that are only broken if they
121 are on the critical path. */
122 for (unsigned i
= 0, e
= CriticalPathRCs
.size(); i
< e
; ++i
) {
123 BitVector CPSet
= TRI
->getAllocatableSet(MF
, CriticalPathRCs
[i
]);
124 if (CriticalPathSet
.none())
125 CriticalPathSet
= CPSet
;
127 CriticalPathSet
|= CPSet
;
130 DEBUG(dbgs() << "AntiDep Critical-Path Registers:");
131 DEBUG(for (int r
= CriticalPathSet
.find_first(); r
!= -1;
132 r
= CriticalPathSet
.find_next(r
))
133 dbgs() << " " << TRI
->getName(r
));
134 DEBUG(dbgs() << '\n');
137 AggressiveAntiDepBreaker::~AggressiveAntiDepBreaker() {
141 void AggressiveAntiDepBreaker::StartBlock(MachineBasicBlock
*BB
) {
143 State
= new AggressiveAntiDepState(TRI
->getNumRegs(), BB
);
145 bool IsReturnBlock
= (!BB
->empty() && BB
->back().isReturn());
146 std::vector
<unsigned> &KillIndices
= State
->GetKillIndices();
147 std::vector
<unsigned> &DefIndices
= State
->GetDefIndices();
149 // Examine the live-in regs of all successors.
150 for (MachineBasicBlock::succ_iterator SI
= BB
->succ_begin(),
151 SE
= BB
->succ_end(); SI
!= SE
; ++SI
)
152 for (MachineBasicBlock::livein_iterator I
= (*SI
)->livein_begin(),
153 E
= (*SI
)->livein_end(); I
!= E
; ++I
) {
154 for (MCRegAliasIterator
AI(*I
, TRI
, true); AI
.isValid(); ++AI
) {
156 State
->UnionGroups(Reg
, 0);
157 KillIndices
[Reg
] = BB
->size();
158 DefIndices
[Reg
] = ~0u;
162 // Mark live-out callee-saved registers. In a return block this is
163 // all callee-saved registers. In non-return this is any
164 // callee-saved register that is not saved in the prolog.
165 const MachineFrameInfo
*MFI
= MF
.getFrameInfo();
166 BitVector Pristine
= MFI
->getPristineRegs(BB
);
167 for (const MCPhysReg
*I
= TRI
->getCalleeSavedRegs(&MF
); *I
; ++I
) {
169 if (!IsReturnBlock
&& !Pristine
.test(Reg
)) continue;
170 for (MCRegAliasIterator
AI(Reg
, TRI
, true); AI
.isValid(); ++AI
) {
171 unsigned AliasReg
= *AI
;
172 State
->UnionGroups(AliasReg
, 0);
173 KillIndices
[AliasReg
] = BB
->size();
174 DefIndices
[AliasReg
] = ~0u;
179 void AggressiveAntiDepBreaker::FinishBlock() {
184 void AggressiveAntiDepBreaker::Observe(MachineInstr
*MI
, unsigned Count
,
185 unsigned InsertPosIndex
) {
186 assert(Count
< InsertPosIndex
&& "Instruction index out of expected range!");
188 std::set
<unsigned> PassthruRegs
;
189 GetPassthruRegs(MI
, PassthruRegs
);
190 PrescanInstruction(MI
, Count
, PassthruRegs
);
191 ScanInstruction(MI
, Count
);
193 DEBUG(dbgs() << "Observe: ");
195 DEBUG(dbgs() << "\tRegs:");
197 std::vector
<unsigned> &DefIndices
= State
->GetDefIndices();
198 for (unsigned Reg
= 0; Reg
!= TRI
->getNumRegs(); ++Reg
) {
199 // If Reg is current live, then mark that it can't be renamed as
200 // we don't know the extent of its live-range anymore (now that it
201 // has been scheduled). If it is not live but was defined in the
202 // previous schedule region, then set its def index to the most
203 // conservative location (i.e. the beginning of the previous
205 if (State
->IsLive(Reg
)) {
206 DEBUG(if (State
->GetGroup(Reg
) != 0)
207 dbgs() << " " << TRI
->getName(Reg
) << "=g" <<
208 State
->GetGroup(Reg
) << "->g0(region live-out)");
209 State
->UnionGroups(Reg
, 0);
210 } else if ((DefIndices
[Reg
] < InsertPosIndex
)
211 && (DefIndices
[Reg
] >= Count
)) {
212 DefIndices
[Reg
] = Count
;
215 DEBUG(dbgs() << '\n');
218 bool AggressiveAntiDepBreaker::IsImplicitDefUse(MachineInstr
*MI
,
221 if (!MO
.isReg() || !MO
.isImplicit())
224 unsigned Reg
= MO
.getReg();
228 MachineOperand
*Op
= nullptr;
230 Op
= MI
->findRegisterUseOperand(Reg
, true);
232 Op
= MI
->findRegisterDefOperand(Reg
);
234 return(Op
&& Op
->isImplicit());
237 void AggressiveAntiDepBreaker::GetPassthruRegs(MachineInstr
*MI
,
238 std::set
<unsigned>& PassthruRegs
) {
239 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
240 MachineOperand
&MO
= MI
->getOperand(i
);
241 if (!MO
.isReg()) continue;
242 if ((MO
.isDef() && MI
->isRegTiedToUseOperand(i
)) ||
243 IsImplicitDefUse(MI
, MO
)) {
244 const unsigned Reg
= MO
.getReg();
245 for (MCSubRegIterator
SubRegs(Reg
, TRI
, /*IncludeSelf=*/true);
246 SubRegs
.isValid(); ++SubRegs
)
247 PassthruRegs
.insert(*SubRegs
);
252 /// AntiDepEdges - Return in Edges the anti- and output- dependencies
253 /// in SU that we want to consider for breaking.
254 static void AntiDepEdges(const SUnit
*SU
, std::vector
<const SDep
*>& Edges
) {
255 SmallSet
<unsigned, 4> RegSet
;
256 for (SUnit::const_pred_iterator P
= SU
->Preds
.begin(), PE
= SU
->Preds
.end();
258 if ((P
->getKind() == SDep::Anti
) || (P
->getKind() == SDep::Output
)) {
259 if (RegSet
.insert(P
->getReg()).second
)
260 Edges
.push_back(&*P
);
265 /// CriticalPathStep - Return the next SUnit after SU on the bottom-up
267 static const SUnit
*CriticalPathStep(const SUnit
*SU
) {
268 const SDep
*Next
= nullptr;
269 unsigned NextDepth
= 0;
270 // Find the predecessor edge with the greatest depth.
272 for (SUnit::const_pred_iterator P
= SU
->Preds
.begin(), PE
= SU
->Preds
.end();
274 const SUnit
*PredSU
= P
->getSUnit();
275 unsigned PredLatency
= P
->getLatency();
276 unsigned PredTotalLatency
= PredSU
->getDepth() + PredLatency
;
277 // In the case of a latency tie, prefer an anti-dependency edge over
278 // other types of edges.
279 if (NextDepth
< PredTotalLatency
||
280 (NextDepth
== PredTotalLatency
&& P
->getKind() == SDep::Anti
)) {
281 NextDepth
= PredTotalLatency
;
287 return (Next
) ? Next
->getSUnit() : nullptr;
290 void AggressiveAntiDepBreaker::HandleLastUse(unsigned Reg
, unsigned KillIdx
,
293 const char *footer
) {
294 std::vector
<unsigned> &KillIndices
= State
->GetKillIndices();
295 std::vector
<unsigned> &DefIndices
= State
->GetDefIndices();
296 std::multimap
<unsigned, AggressiveAntiDepState::RegisterReference
>&
297 RegRefs
= State
->GetRegRefs();
299 if (!State
->IsLive(Reg
)) {
300 KillIndices
[Reg
] = KillIdx
;
301 DefIndices
[Reg
] = ~0u;
303 State
->LeaveGroup(Reg
);
305 dbgs() << header
<< TRI
->getName(Reg
); header
= nullptr; });
306 DEBUG(dbgs() << "->g" << State
->GetGroup(Reg
) << tag
);
308 // Repeat for subregisters.
309 for (MCSubRegIterator
SubRegs(Reg
, TRI
); SubRegs
.isValid(); ++SubRegs
) {
310 unsigned SubregReg
= *SubRegs
;
311 if (!State
->IsLive(SubregReg
)) {
312 KillIndices
[SubregReg
] = KillIdx
;
313 DefIndices
[SubregReg
] = ~0u;
314 RegRefs
.erase(SubregReg
);
315 State
->LeaveGroup(SubregReg
);
317 dbgs() << header
<< TRI
->getName(Reg
); header
= nullptr; });
318 DEBUG(dbgs() << " " << TRI
->getName(SubregReg
) << "->g" <<
319 State
->GetGroup(SubregReg
) << tag
);
323 DEBUG(if (!header
&& footer
) dbgs() << footer
);
326 void AggressiveAntiDepBreaker::PrescanInstruction(MachineInstr
*MI
,
328 std::set
<unsigned>& PassthruRegs
) {
329 std::vector
<unsigned> &DefIndices
= State
->GetDefIndices();
330 std::multimap
<unsigned, AggressiveAntiDepState::RegisterReference
>&
331 RegRefs
= State
->GetRegRefs();
333 // Handle dead defs by simulating a last-use of the register just
334 // after the def. A dead def can occur because the def is truly
335 // dead, or because only a subregister is live at the def. If we
336 // don't do this the dead def will be incorrectly merged into the
338 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
339 MachineOperand
&MO
= MI
->getOperand(i
);
340 if (!MO
.isReg() || !MO
.isDef()) continue;
341 unsigned Reg
= MO
.getReg();
342 if (Reg
== 0) continue;
344 HandleLastUse(Reg
, Count
+ 1, "", "\tDead Def: ", "\n");
347 DEBUG(dbgs() << "\tDef Groups:");
348 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
349 MachineOperand
&MO
= MI
->getOperand(i
);
350 if (!MO
.isReg() || !MO
.isDef()) continue;
351 unsigned Reg
= MO
.getReg();
352 if (Reg
== 0) continue;
354 DEBUG(dbgs() << " " << TRI
->getName(Reg
) << "=g" << State
->GetGroup(Reg
));
356 // If MI's defs have a special allocation requirement, don't allow
357 // any def registers to be changed. Also assume all registers
358 // defined in a call must not be changed (ABI).
359 if (MI
->isCall() || MI
->hasExtraDefRegAllocReq() ||
360 TII
->isPredicated(MI
)) {
361 DEBUG(if (State
->GetGroup(Reg
) != 0) dbgs() << "->g0(alloc-req)");
362 State
->UnionGroups(Reg
, 0);
365 // Any aliased that are live at this point are completely or
366 // partially defined here, so group those aliases with Reg.
367 for (MCRegAliasIterator
AI(Reg
, TRI
, false); AI
.isValid(); ++AI
) {
368 unsigned AliasReg
= *AI
;
369 if (State
->IsLive(AliasReg
)) {
370 State
->UnionGroups(Reg
, AliasReg
);
371 DEBUG(dbgs() << "->g" << State
->GetGroup(Reg
) << "(via " <<
372 TRI
->getName(AliasReg
) << ")");
376 // Note register reference...
377 const TargetRegisterClass
*RC
= nullptr;
378 if (i
< MI
->getDesc().getNumOperands())
379 RC
= TII
->getRegClass(MI
->getDesc(), i
, TRI
, MF
);
380 AggressiveAntiDepState::RegisterReference RR
= { &MO
, RC
};
381 RegRefs
.insert(std::make_pair(Reg
, RR
));
384 DEBUG(dbgs() << '\n');
386 // Scan the register defs for this instruction and update
388 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
389 MachineOperand
&MO
= MI
->getOperand(i
);
390 if (!MO
.isReg() || !MO
.isDef()) continue;
391 unsigned Reg
= MO
.getReg();
392 if (Reg
== 0) continue;
393 // Ignore KILLs and passthru registers for liveness...
394 if (MI
->isKill() || (PassthruRegs
.count(Reg
) != 0))
397 // Update def for Reg and aliases.
398 for (MCRegAliasIterator
AI(Reg
, TRI
, true); AI
.isValid(); ++AI
) {
399 // We need to be careful here not to define already-live super registers.
400 // If the super register is already live, then this definition is not
401 // a definition of the whole super register (just a partial insertion
402 // into it). Earlier subregister definitions (which we've not yet visited
403 // because we're iterating bottom-up) need to be linked to the same group
404 // as this definition.
405 if (TRI
->isSuperRegister(Reg
, *AI
) && State
->IsLive(*AI
))
408 DefIndices
[*AI
] = Count
;
413 void AggressiveAntiDepBreaker::ScanInstruction(MachineInstr
*MI
,
415 DEBUG(dbgs() << "\tUse Groups:");
416 std::multimap
<unsigned, AggressiveAntiDepState::RegisterReference
>&
417 RegRefs
= State
->GetRegRefs();
419 // If MI's uses have special allocation requirement, don't allow
420 // any use registers to be changed. Also assume all registers
421 // used in a call must not be changed (ABI).
422 // FIXME: The issue with predicated instruction is more complex. We are being
423 // conservatively here because the kill markers cannot be trusted after
425 // %R6<def> = LDR %SP, %reg0, 92, pred:14, pred:%reg0; mem:LD4[FixedStack14]
427 // STR %R0, %R6<kill>, %reg0, 0, pred:0, pred:%CPSR; mem:ST4[%395]
428 // %R6<def> = LDR %SP, %reg0, 100, pred:0, pred:%CPSR; mem:LD4[FixedStack12]
429 // STR %R0, %R6<kill>, %reg0, 0, pred:14, pred:%reg0; mem:ST4[%396](align=8)
431 // The first R6 kill is not really a kill since it's killed by a predicated
432 // instruction which may not be executed. The second R6 def may or may not
433 // re-define R6 so it's not safe to change it since the last R6 use cannot be
435 bool Special
= MI
->isCall() ||
436 MI
->hasExtraSrcRegAllocReq() ||
437 TII
->isPredicated(MI
);
439 // Scan the register uses for this instruction and update
440 // live-ranges, groups and RegRefs.
441 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
442 MachineOperand
&MO
= MI
->getOperand(i
);
443 if (!MO
.isReg() || !MO
.isUse()) continue;
444 unsigned Reg
= MO
.getReg();
445 if (Reg
== 0) continue;
447 DEBUG(dbgs() << " " << TRI
->getName(Reg
) << "=g" <<
448 State
->GetGroup(Reg
));
450 // It wasn't previously live but now it is, this is a kill. Forget
451 // the previous live-range information and start a new live-range
453 HandleLastUse(Reg
, Count
, "(last-use)");
456 DEBUG(if (State
->GetGroup(Reg
) != 0) dbgs() << "->g0(alloc-req)");
457 State
->UnionGroups(Reg
, 0);
460 // Note register reference...
461 const TargetRegisterClass
*RC
= nullptr;
462 if (i
< MI
->getDesc().getNumOperands())
463 RC
= TII
->getRegClass(MI
->getDesc(), i
, TRI
, MF
);
464 AggressiveAntiDepState::RegisterReference RR
= { &MO
, RC
};
465 RegRefs
.insert(std::make_pair(Reg
, RR
));
468 DEBUG(dbgs() << '\n');
470 // Form a group of all defs and uses of a KILL instruction to ensure
471 // that all registers are renamed as a group.
473 DEBUG(dbgs() << "\tKill Group:");
475 unsigned FirstReg
= 0;
476 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
477 MachineOperand
&MO
= MI
->getOperand(i
);
478 if (!MO
.isReg()) continue;
479 unsigned Reg
= MO
.getReg();
480 if (Reg
== 0) continue;
483 DEBUG(dbgs() << "=" << TRI
->getName(Reg
));
484 State
->UnionGroups(FirstReg
, Reg
);
486 DEBUG(dbgs() << " " << TRI
->getName(Reg
));
491 DEBUG(dbgs() << "->g" << State
->GetGroup(FirstReg
) << '\n');
495 BitVector
AggressiveAntiDepBreaker::GetRenameRegisters(unsigned Reg
) {
496 BitVector
BV(TRI
->getNumRegs(), false);
499 // Check all references that need rewriting for Reg. For each, use
500 // the corresponding register class to narrow the set of registers
501 // that are appropriate for renaming.
502 std::pair
<std::multimap
<unsigned,
503 AggressiveAntiDepState::RegisterReference
>::iterator
,
504 std::multimap
<unsigned,
505 AggressiveAntiDepState::RegisterReference
>::iterator
>
506 Range
= State
->GetRegRefs().equal_range(Reg
);
507 for (std::multimap
<unsigned,
508 AggressiveAntiDepState::RegisterReference
>::iterator Q
= Range
.first
,
509 QE
= Range
.second
; Q
!= QE
; ++Q
) {
510 const TargetRegisterClass
*RC
= Q
->second
.RC
;
513 BitVector RCBV
= TRI
->getAllocatableSet(MF
, RC
);
521 DEBUG(dbgs() << " " << TRI
->getRegClassName(RC
));
527 bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters(
528 unsigned AntiDepGroupIndex
,
529 RenameOrderType
& RenameOrder
,
530 std::map
<unsigned, unsigned> &RenameMap
) {
531 std::vector
<unsigned> &KillIndices
= State
->GetKillIndices();
532 std::vector
<unsigned> &DefIndices
= State
->GetDefIndices();
533 std::multimap
<unsigned, AggressiveAntiDepState::RegisterReference
>&
534 RegRefs
= State
->GetRegRefs();
536 // Collect all referenced registers in the same group as
537 // AntiDepReg. These all need to be renamed together if we are to
538 // break the anti-dependence.
539 std::vector
<unsigned> Regs
;
540 State
->GetGroupRegs(AntiDepGroupIndex
, Regs
, &RegRefs
);
541 assert(Regs
.size() > 0 && "Empty register group!");
542 if (Regs
.size() == 0)
545 // Find the "superest" register in the group. At the same time,
546 // collect the BitVector of registers that can be used to rename
548 DEBUG(dbgs() << "\tRename Candidates for Group g" << AntiDepGroupIndex
550 std::map
<unsigned, BitVector
> RenameRegisterMap
;
551 unsigned SuperReg
= 0;
552 for (unsigned i
= 0, e
= Regs
.size(); i
!= e
; ++i
) {
553 unsigned Reg
= Regs
[i
];
554 if ((SuperReg
== 0) || TRI
->isSuperRegister(SuperReg
, Reg
))
557 // If Reg has any references, then collect possible rename regs
558 if (RegRefs
.count(Reg
) > 0) {
559 DEBUG(dbgs() << "\t\t" << TRI
->getName(Reg
) << ":");
561 BitVector BV
= GetRenameRegisters(Reg
);
562 RenameRegisterMap
.insert(std::pair
<unsigned, BitVector
>(Reg
, BV
));
564 DEBUG(dbgs() << " ::");
565 DEBUG(for (int r
= BV
.find_first(); r
!= -1; r
= BV
.find_next(r
))
566 dbgs() << " " << TRI
->getName(r
));
567 DEBUG(dbgs() << "\n");
571 // All group registers should be a subreg of SuperReg.
572 for (unsigned i
= 0, e
= Regs
.size(); i
!= e
; ++i
) {
573 unsigned Reg
= Regs
[i
];
574 if (Reg
== SuperReg
) continue;
575 bool IsSub
= TRI
->isSubRegister(SuperReg
, Reg
);
576 // FIXME: remove this once PR18663 has been properly fixed. For now,
577 // return a conservative answer:
578 // assert(IsSub && "Expecting group subregister");
584 // If DebugDiv > 0 then only rename (renamecnt % DebugDiv) == DebugMod
586 static int renamecnt
= 0;
587 if (renamecnt
++ % DebugDiv
!= DebugMod
)
590 dbgs() << "*** Performing rename " << TRI
->getName(SuperReg
) <<
595 // Check each possible rename register for SuperReg in round-robin
596 // order. If that register is available, and the corresponding
597 // registers are available for the other group subregisters, then we
598 // can use those registers to rename.
600 // FIXME: Using getMinimalPhysRegClass is very conservative. We should
601 // check every use of the register and find the largest register class
602 // that can be used in all of them.
603 const TargetRegisterClass
*SuperRC
=
604 TRI
->getMinimalPhysRegClass(SuperReg
, MVT::Other
);
606 ArrayRef
<MCPhysReg
> Order
= RegClassInfo
.getOrder(SuperRC
);
608 DEBUG(dbgs() << "\tEmpty Super Regclass!!\n");
612 DEBUG(dbgs() << "\tFind Registers:");
614 RenameOrder
.insert(RenameOrderType::value_type(SuperRC
, Order
.size()));
616 unsigned OrigR
= RenameOrder
[SuperRC
];
617 unsigned EndR
= ((OrigR
== Order
.size()) ? 0 : OrigR
);
620 if (R
== 0) R
= Order
.size();
622 const unsigned NewSuperReg
= Order
[R
];
623 // Don't consider non-allocatable registers
624 if (!MRI
.isAllocatable(NewSuperReg
)) continue;
625 // Don't replace a register with itself.
626 if (NewSuperReg
== SuperReg
) continue;
628 DEBUG(dbgs() << " [" << TRI
->getName(NewSuperReg
) << ':');
631 // For each referenced group register (which must be a SuperReg or
632 // a subregister of SuperReg), find the corresponding subregister
633 // of NewSuperReg and make sure it is free to be renamed.
634 for (unsigned i
= 0, e
= Regs
.size(); i
!= e
; ++i
) {
635 unsigned Reg
= Regs
[i
];
637 if (Reg
== SuperReg
) {
638 NewReg
= NewSuperReg
;
640 unsigned NewSubRegIdx
= TRI
->getSubRegIndex(SuperReg
, Reg
);
641 if (NewSubRegIdx
!= 0)
642 NewReg
= TRI
->getSubReg(NewSuperReg
, NewSubRegIdx
);
645 DEBUG(dbgs() << " " << TRI
->getName(NewReg
));
647 // Check if Reg can be renamed to NewReg.
648 BitVector BV
= RenameRegisterMap
[Reg
];
649 if (!BV
.test(NewReg
)) {
650 DEBUG(dbgs() << "(no rename)");
654 // If NewReg is dead and NewReg's most recent def is not before
655 // Regs's kill, it's safe to replace Reg with NewReg. We
656 // must also check all aliases of NewReg, because we can't define a
657 // register when any sub or super is already live.
658 if (State
->IsLive(NewReg
) || (KillIndices
[Reg
] > DefIndices
[NewReg
])) {
659 DEBUG(dbgs() << "(live)");
663 for (MCRegAliasIterator
AI(NewReg
, TRI
, false); AI
.isValid(); ++AI
) {
664 unsigned AliasReg
= *AI
;
665 if (State
->IsLive(AliasReg
) ||
666 (KillIndices
[Reg
] > DefIndices
[AliasReg
])) {
667 DEBUG(dbgs() << "(alias " << TRI
->getName(AliasReg
) << " live)");
676 // We cannot rename 'Reg' to 'NewReg' if one of the uses of 'Reg' also
677 // defines 'NewReg' via an early-clobber operand.
678 auto Range
= RegRefs
.equal_range(Reg
);
679 for (auto Q
= Range
.first
, QE
= Range
.second
; Q
!= QE
; ++Q
) {
680 auto UseMI
= Q
->second
.Operand
->getParent();
681 int Idx
= UseMI
->findRegisterDefOperandIdx(NewReg
, false, true, TRI
);
685 if (UseMI
->getOperand(Idx
).isEarlyClobber()) {
686 DEBUG(dbgs() << "(ec)");
691 // Record that 'Reg' can be renamed to 'NewReg'.
692 RenameMap
.insert(std::pair
<unsigned, unsigned>(Reg
, NewReg
));
695 // If we fall-out here, then every register in the group can be
696 // renamed, as recorded in RenameMap.
697 RenameOrder
.erase(SuperRC
);
698 RenameOrder
.insert(RenameOrderType::value_type(SuperRC
, R
));
699 DEBUG(dbgs() << "]\n");
703 DEBUG(dbgs() << ']');
706 DEBUG(dbgs() << '\n');
708 // No registers are free and available!
712 /// BreakAntiDependencies - Identifiy anti-dependencies within the
713 /// ScheduleDAG and break them by renaming registers.
715 unsigned AggressiveAntiDepBreaker::BreakAntiDependencies(
716 const std::vector
<SUnit
>& SUnits
,
717 MachineBasicBlock::iterator Begin
,
718 MachineBasicBlock::iterator End
,
719 unsigned InsertPosIndex
,
720 DbgValueVector
&DbgValues
) {
722 std::vector
<unsigned> &KillIndices
= State
->GetKillIndices();
723 std::vector
<unsigned> &DefIndices
= State
->GetDefIndices();
724 std::multimap
<unsigned, AggressiveAntiDepState::RegisterReference
>&
725 RegRefs
= State
->GetRegRefs();
727 // The code below assumes that there is at least one instruction,
728 // so just duck out immediately if the block is empty.
729 if (SUnits
.empty()) return 0;
731 // For each regclass the next register to use for renaming.
732 RenameOrderType RenameOrder
;
734 // ...need a map from MI to SUnit.
735 std::map
<MachineInstr
*, const SUnit
*> MISUnitMap
;
736 for (unsigned i
= 0, e
= SUnits
.size(); i
!= e
; ++i
) {
737 const SUnit
*SU
= &SUnits
[i
];
738 MISUnitMap
.insert(std::pair
<MachineInstr
*, const SUnit
*>(SU
->getInstr(),
742 // Track progress along the critical path through the SUnit graph as
743 // we walk the instructions. This is needed for regclasses that only
744 // break critical-path anti-dependencies.
745 const SUnit
*CriticalPathSU
= nullptr;
746 MachineInstr
*CriticalPathMI
= nullptr;
747 if (CriticalPathSet
.any()) {
748 for (unsigned i
= 0, e
= SUnits
.size(); i
!= e
; ++i
) {
749 const SUnit
*SU
= &SUnits
[i
];
750 if (!CriticalPathSU
||
751 ((SU
->getDepth() + SU
->Latency
) >
752 (CriticalPathSU
->getDepth() + CriticalPathSU
->Latency
))) {
757 CriticalPathMI
= CriticalPathSU
->getInstr();
761 DEBUG(dbgs() << "\n===== Aggressive anti-dependency breaking\n");
762 DEBUG(dbgs() << "Available regs:");
763 for (unsigned Reg
= 0; Reg
< TRI
->getNumRegs(); ++Reg
) {
764 if (!State
->IsLive(Reg
))
765 DEBUG(dbgs() << " " << TRI
->getName(Reg
));
767 DEBUG(dbgs() << '\n');
770 // Attempt to break anti-dependence edges. Walk the instructions
771 // from the bottom up, tracking information about liveness as we go
772 // to help determine which registers are available.
774 unsigned Count
= InsertPosIndex
- 1;
775 for (MachineBasicBlock::iterator I
= End
, E
= Begin
;
777 MachineInstr
*MI
= --I
;
779 if (MI
->isDebugValue())
782 DEBUG(dbgs() << "Anti: ");
785 std::set
<unsigned> PassthruRegs
;
786 GetPassthruRegs(MI
, PassthruRegs
);
788 // Process the defs in MI...
789 PrescanInstruction(MI
, Count
, PassthruRegs
);
791 // The dependence edges that represent anti- and output-
792 // dependencies that are candidates for breaking.
793 std::vector
<const SDep
*> Edges
;
794 const SUnit
*PathSU
= MISUnitMap
[MI
];
795 AntiDepEdges(PathSU
, Edges
);
797 // If MI is not on the critical path, then we don't rename
798 // registers in the CriticalPathSet.
799 BitVector
*ExcludeRegs
= nullptr;
800 if (MI
== CriticalPathMI
) {
801 CriticalPathSU
= CriticalPathStep(CriticalPathSU
);
802 CriticalPathMI
= (CriticalPathSU
) ? CriticalPathSU
->getInstr() : nullptr;
803 } else if (CriticalPathSet
.any()) {
804 ExcludeRegs
= &CriticalPathSet
;
807 // Ignore KILL instructions (they form a group in ScanInstruction
808 // but don't cause any anti-dependence breaking themselves)
810 // Attempt to break each anti-dependency...
811 for (unsigned i
= 0, e
= Edges
.size(); i
!= e
; ++i
) {
812 const SDep
*Edge
= Edges
[i
];
813 SUnit
*NextSU
= Edge
->getSUnit();
815 if ((Edge
->getKind() != SDep::Anti
) &&
816 (Edge
->getKind() != SDep::Output
)) continue;
818 unsigned AntiDepReg
= Edge
->getReg();
819 DEBUG(dbgs() << "\tAntidep reg: " << TRI
->getName(AntiDepReg
));
820 assert(AntiDepReg
!= 0 && "Anti-dependence on reg0?");
822 if (!MRI
.isAllocatable(AntiDepReg
)) {
823 // Don't break anti-dependencies on non-allocatable registers.
824 DEBUG(dbgs() << " (non-allocatable)\n");
826 } else if (ExcludeRegs
&& ExcludeRegs
->test(AntiDepReg
)) {
827 // Don't break anti-dependencies for critical path registers
828 // if not on the critical path
829 DEBUG(dbgs() << " (not critical-path)\n");
831 } else if (PassthruRegs
.count(AntiDepReg
) != 0) {
832 // If the anti-dep register liveness "passes-thru", then
833 // don't try to change it. It will be changed along with
834 // the use if required to break an earlier antidep.
835 DEBUG(dbgs() << " (passthru)\n");
838 // No anti-dep breaking for implicit deps
839 MachineOperand
*AntiDepOp
= MI
->findRegisterDefOperand(AntiDepReg
);
840 assert(AntiDepOp
&& "Can't find index for defined register operand");
841 if (!AntiDepOp
|| AntiDepOp
->isImplicit()) {
842 DEBUG(dbgs() << " (implicit)\n");
846 // If the SUnit has other dependencies on the SUnit that
847 // it anti-depends on, don't bother breaking the
848 // anti-dependency since those edges would prevent such
849 // units from being scheduled past each other
852 // Also, if there are dependencies on other SUnits with the
853 // same register as the anti-dependency, don't attempt to
855 for (SUnit::const_pred_iterator P
= PathSU
->Preds
.begin(),
856 PE
= PathSU
->Preds
.end(); P
!= PE
; ++P
) {
857 if (P
->getSUnit() == NextSU
?
858 (P
->getKind() != SDep::Anti
|| P
->getReg() != AntiDepReg
) :
859 (P
->getKind() == SDep::Data
&& P
->getReg() == AntiDepReg
)) {
864 for (SUnit::const_pred_iterator P
= PathSU
->Preds
.begin(),
865 PE
= PathSU
->Preds
.end(); P
!= PE
; ++P
) {
866 if ((P
->getSUnit() == NextSU
) && (P
->getKind() != SDep::Anti
) &&
867 (P
->getKind() != SDep::Output
)) {
868 DEBUG(dbgs() << " (real dependency)\n");
871 } else if ((P
->getSUnit() != NextSU
) &&
872 (P
->getKind() == SDep::Data
) &&
873 (P
->getReg() == AntiDepReg
)) {
874 DEBUG(dbgs() << " (other dependency)\n");
880 if (AntiDepReg
== 0) continue;
883 assert(AntiDepReg
!= 0);
884 if (AntiDepReg
== 0) continue;
886 // Determine AntiDepReg's register group.
887 const unsigned GroupIndex
= State
->GetGroup(AntiDepReg
);
888 if (GroupIndex
== 0) {
889 DEBUG(dbgs() << " (zero group)\n");
893 DEBUG(dbgs() << '\n');
895 // Look for a suitable register to use to break the anti-dependence.
896 std::map
<unsigned, unsigned> RenameMap
;
897 if (FindSuitableFreeRegisters(GroupIndex
, RenameOrder
, RenameMap
)) {
898 DEBUG(dbgs() << "\tBreaking anti-dependence edge on "
899 << TRI
->getName(AntiDepReg
) << ":");
901 // Handle each group register...
902 for (std::map
<unsigned, unsigned>::iterator
903 S
= RenameMap
.begin(), E
= RenameMap
.end(); S
!= E
; ++S
) {
904 unsigned CurrReg
= S
->first
;
905 unsigned NewReg
= S
->second
;
907 DEBUG(dbgs() << " " << TRI
->getName(CurrReg
) << "->" <<
908 TRI
->getName(NewReg
) << "(" <<
909 RegRefs
.count(CurrReg
) << " refs)");
911 // Update the references to the old register CurrReg to
912 // refer to the new register NewReg.
913 std::pair
<std::multimap
<unsigned,
914 AggressiveAntiDepState::RegisterReference
>::iterator
,
915 std::multimap
<unsigned,
916 AggressiveAntiDepState::RegisterReference
>::iterator
>
917 Range
= RegRefs
.equal_range(CurrReg
);
918 for (std::multimap
<unsigned,
919 AggressiveAntiDepState::RegisterReference
>::iterator
920 Q
= Range
.first
, QE
= Range
.second
; Q
!= QE
; ++Q
) {
921 Q
->second
.Operand
->setReg(NewReg
);
922 // If the SU for the instruction being updated has debug
923 // information related to the anti-dependency register, make
924 // sure to update that as well.
925 const SUnit
*SU
= MISUnitMap
[Q
->second
.Operand
->getParent()];
927 for (DbgValueVector::iterator DVI
= DbgValues
.begin(),
928 DVE
= DbgValues
.end(); DVI
!= DVE
; ++DVI
)
929 if (DVI
->second
== Q
->second
.Operand
->getParent())
930 UpdateDbgValue(DVI
->first
, AntiDepReg
, NewReg
);
933 // We just went back in time and modified history; the
934 // liveness information for CurrReg is now inconsistent. Set
935 // the state as if it were dead.
936 State
->UnionGroups(NewReg
, 0);
937 RegRefs
.erase(NewReg
);
938 DefIndices
[NewReg
] = DefIndices
[CurrReg
];
939 KillIndices
[NewReg
] = KillIndices
[CurrReg
];
941 State
->UnionGroups(CurrReg
, 0);
942 RegRefs
.erase(CurrReg
);
943 DefIndices
[CurrReg
] = KillIndices
[CurrReg
];
944 KillIndices
[CurrReg
] = ~0u;
945 assert(((KillIndices
[CurrReg
] == ~0u) !=
946 (DefIndices
[CurrReg
] == ~0u)) &&
947 "Kill and Def maps aren't consistent for AntiDepReg!");
951 DEBUG(dbgs() << '\n');
956 ScanInstruction(MI
, Count
);