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 #define DEBUG_TYPE "post-RA-sched"
18 #include "AggressiveAntiDepBreaker.h"
19 #include "llvm/CodeGen/MachineBasicBlock.h"
20 #include "llvm/CodeGen/MachineFrameInfo.h"
21 #include "llvm/CodeGen/MachineInstr.h"
22 #include "llvm/Target/TargetInstrInfo.h"
23 #include "llvm/Target/TargetMachine.h"
24 #include "llvm/Target/TargetRegisterInfo.h"
25 #include "llvm/Support/CommandLine.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/ErrorHandling.h"
28 #include "llvm/Support/raw_ostream.h"
31 // If DebugDiv > 0 then only break antidep with (ID % DebugDiv) == DebugMod
33 DebugDiv("agg-antidep-debugdiv",
34 cl::desc("Debug control for aggressive anti-dep breaker"),
35 cl::init(0), cl::Hidden
);
37 DebugMod("agg-antidep-debugmod",
38 cl::desc("Debug control for aggressive anti-dep breaker"),
39 cl::init(0), cl::Hidden
);
41 AggressiveAntiDepState::AggressiveAntiDepState(const unsigned TargetRegs
,
42 MachineBasicBlock
*BB
) :
43 NumTargetRegs(TargetRegs
), GroupNodes(TargetRegs
, 0) {
45 const unsigned BBSize
= BB
->size();
46 for (unsigned i
= 0; i
< NumTargetRegs
; ++i
) {
47 // Initialize all registers to be in their own group. Initially we
48 // assign the register to the same-indexed GroupNode.
49 GroupNodeIndices
[i
] = i
;
50 // Initialize the indices to indicate that no registers are live.
52 DefIndices
[i
] = BBSize
;
56 unsigned AggressiveAntiDepState::GetGroup(unsigned Reg
)
58 unsigned Node
= GroupNodeIndices
[Reg
];
59 while (GroupNodes
[Node
] != Node
)
60 Node
= GroupNodes
[Node
];
65 void AggressiveAntiDepState::GetGroupRegs(
67 std::vector
<unsigned> &Regs
,
68 std::multimap
<unsigned, AggressiveAntiDepState::RegisterReference
> *RegRefs
)
70 for (unsigned Reg
= 0; Reg
!= NumTargetRegs
; ++Reg
) {
71 if ((GetGroup(Reg
) == Group
) && (RegRefs
->count(Reg
) > 0))
76 unsigned AggressiveAntiDepState::UnionGroups(unsigned Reg1
, unsigned Reg2
)
78 assert(GroupNodes
[0] == 0 && "GroupNode 0 not parent!");
79 assert(GroupNodeIndices
[0] == 0 && "Reg 0 not in Group 0!");
81 // find group for each register
82 unsigned Group1
= GetGroup(Reg1
);
83 unsigned Group2
= GetGroup(Reg2
);
85 // if either group is 0, then that must become the parent
86 unsigned Parent
= (Group1
== 0) ? Group1
: Group2
;
87 unsigned Other
= (Parent
== Group1
) ? Group2
: Group1
;
88 GroupNodes
.at(Other
) = Parent
;
92 unsigned AggressiveAntiDepState::LeaveGroup(unsigned Reg
)
94 // Create a new GroupNode for Reg. Reg's existing GroupNode must
95 // stay as is because there could be other GroupNodes referring to
97 unsigned idx
= GroupNodes
.size();
98 GroupNodes
.push_back(idx
);
99 GroupNodeIndices
[Reg
] = idx
;
103 bool AggressiveAntiDepState::IsLive(unsigned Reg
)
105 // KillIndex must be defined and DefIndex not defined for a register
107 return((KillIndices
[Reg
] != ~0u) && (DefIndices
[Reg
] == ~0u));
112 AggressiveAntiDepBreaker::
113 AggressiveAntiDepBreaker(MachineFunction
& MFi
,
114 TargetSubtarget::RegClassVector
& CriticalPathRCs
) :
115 AntiDepBreaker(), MF(MFi
),
116 MRI(MF
.getRegInfo()),
117 TRI(MF
.getTarget().getRegisterInfo()),
118 AllocatableSet(TRI
->getAllocatableSet(MF
)),
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
) {
142 assert(State
== NULL
);
143 State
= new AggressiveAntiDepState(TRI
->getNumRegs(), BB
);
145 bool IsReturnBlock
= (!BB
->empty() && BB
->back().getDesc().isReturn());
146 unsigned *KillIndices
= State
->GetKillIndices();
147 unsigned *DefIndices
= State
->GetDefIndices();
149 // Determine the live-out physregs for this block.
151 // In a return block, examine the function live-out regs.
152 for (MachineRegisterInfo::liveout_iterator I
= MRI
.liveout_begin(),
153 E
= MRI
.liveout_end(); I
!= E
; ++I
) {
155 State
->UnionGroups(Reg
, 0);
156 KillIndices
[Reg
] = BB
->size();
157 DefIndices
[Reg
] = ~0u;
158 // Repeat, for all aliases.
159 for (const unsigned *Alias
= TRI
->getAliasSet(Reg
); *Alias
; ++Alias
) {
160 unsigned AliasReg
= *Alias
;
161 State
->UnionGroups(AliasReg
, 0);
162 KillIndices
[AliasReg
] = BB
->size();
163 DefIndices
[AliasReg
] = ~0u;
167 // In a non-return block, examine the live-in regs of all successors.
168 for (MachineBasicBlock::succ_iterator SI
= BB
->succ_begin(),
169 SE
= BB
->succ_end(); SI
!= SE
; ++SI
)
170 for (MachineBasicBlock::livein_iterator I
= (*SI
)->livein_begin(),
171 E
= (*SI
)->livein_end(); I
!= E
; ++I
) {
173 State
->UnionGroups(Reg
, 0);
174 KillIndices
[Reg
] = BB
->size();
175 DefIndices
[Reg
] = ~0u;
176 // Repeat, for all aliases.
177 for (const unsigned *Alias
= TRI
->getAliasSet(Reg
); *Alias
; ++Alias
) {
178 unsigned AliasReg
= *Alias
;
179 State
->UnionGroups(AliasReg
, 0);
180 KillIndices
[AliasReg
] = BB
->size();
181 DefIndices
[AliasReg
] = ~0u;
186 // Mark live-out callee-saved registers. In a return block this is
187 // all callee-saved registers. In non-return this is any
188 // callee-saved register that is not saved in the prolog.
189 const MachineFrameInfo
*MFI
= MF
.getFrameInfo();
190 BitVector Pristine
= MFI
->getPristineRegs(BB
);
191 for (const unsigned *I
= TRI
->getCalleeSavedRegs(); *I
; ++I
) {
193 if (!IsReturnBlock
&& !Pristine
.test(Reg
)) continue;
194 State
->UnionGroups(Reg
, 0);
195 KillIndices
[Reg
] = BB
->size();
196 DefIndices
[Reg
] = ~0u;
197 // Repeat, for all aliases.
198 for (const unsigned *Alias
= TRI
->getAliasSet(Reg
); *Alias
; ++Alias
) {
199 unsigned AliasReg
= *Alias
;
200 State
->UnionGroups(AliasReg
, 0);
201 KillIndices
[AliasReg
] = BB
->size();
202 DefIndices
[AliasReg
] = ~0u;
207 void AggressiveAntiDepBreaker::FinishBlock() {
212 void AggressiveAntiDepBreaker::Observe(MachineInstr
*MI
, unsigned Count
,
213 unsigned InsertPosIndex
) {
214 assert(Count
< InsertPosIndex
&& "Instruction index out of expected range!");
216 std::set
<unsigned> PassthruRegs
;
217 GetPassthruRegs(MI
, PassthruRegs
);
218 PrescanInstruction(MI
, Count
, PassthruRegs
);
219 ScanInstruction(MI
, Count
);
221 DEBUG(dbgs() << "Observe: ");
223 DEBUG(dbgs() << "\tRegs:");
225 unsigned *DefIndices
= State
->GetDefIndices();
226 for (unsigned Reg
= 0; Reg
!= TRI
->getNumRegs(); ++Reg
) {
227 // If Reg is current live, then mark that it can't be renamed as
228 // we don't know the extent of its live-range anymore (now that it
229 // has been scheduled). If it is not live but was defined in the
230 // previous schedule region, then set its def index to the most
231 // conservative location (i.e. the beginning of the previous
233 if (State
->IsLive(Reg
)) {
234 DEBUG(if (State
->GetGroup(Reg
) != 0)
235 dbgs() << " " << TRI
->getName(Reg
) << "=g" <<
236 State
->GetGroup(Reg
) << "->g0(region live-out)");
237 State
->UnionGroups(Reg
, 0);
238 } else if ((DefIndices
[Reg
] < InsertPosIndex
)
239 && (DefIndices
[Reg
] >= Count
)) {
240 DefIndices
[Reg
] = Count
;
243 DEBUG(dbgs() << '\n');
246 bool AggressiveAntiDepBreaker::IsImplicitDefUse(MachineInstr
*MI
,
249 if (!MO
.isReg() || !MO
.isImplicit())
252 unsigned Reg
= MO
.getReg();
256 MachineOperand
*Op
= NULL
;
258 Op
= MI
->findRegisterUseOperand(Reg
, true);
260 Op
= MI
->findRegisterDefOperand(Reg
);
262 return((Op
!= NULL
) && Op
->isImplicit());
265 void AggressiveAntiDepBreaker::GetPassthruRegs(MachineInstr
*MI
,
266 std::set
<unsigned>& PassthruRegs
) {
267 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
268 MachineOperand
&MO
= MI
->getOperand(i
);
269 if (!MO
.isReg()) continue;
270 if ((MO
.isDef() && MI
->isRegTiedToUseOperand(i
)) ||
271 IsImplicitDefUse(MI
, MO
)) {
272 const unsigned Reg
= MO
.getReg();
273 PassthruRegs
.insert(Reg
);
274 for (const unsigned *Subreg
= TRI
->getSubRegisters(Reg
);
276 PassthruRegs
.insert(*Subreg
);
282 /// AntiDepEdges - Return in Edges the anti- and output- dependencies
283 /// in SU that we want to consider for breaking.
284 static void AntiDepEdges(const SUnit
*SU
, std::vector
<const SDep
*>& Edges
) {
285 SmallSet
<unsigned, 4> RegSet
;
286 for (SUnit::const_pred_iterator P
= SU
->Preds
.begin(), PE
= SU
->Preds
.end();
288 if ((P
->getKind() == SDep::Anti
) || (P
->getKind() == SDep::Output
)) {
289 unsigned Reg
= P
->getReg();
290 if (RegSet
.count(Reg
) == 0) {
291 Edges
.push_back(&*P
);
298 /// CriticalPathStep - Return the next SUnit after SU on the bottom-up
300 static const SUnit
*CriticalPathStep(const SUnit
*SU
) {
301 const SDep
*Next
= 0;
302 unsigned NextDepth
= 0;
303 // Find the predecessor edge with the greatest depth.
305 for (SUnit::const_pred_iterator P
= SU
->Preds
.begin(), PE
= SU
->Preds
.end();
307 const SUnit
*PredSU
= P
->getSUnit();
308 unsigned PredLatency
= P
->getLatency();
309 unsigned PredTotalLatency
= PredSU
->getDepth() + PredLatency
;
310 // In the case of a latency tie, prefer an anti-dependency edge over
311 // other types of edges.
312 if (NextDepth
< PredTotalLatency
||
313 (NextDepth
== PredTotalLatency
&& P
->getKind() == SDep::Anti
)) {
314 NextDepth
= PredTotalLatency
;
320 return (Next
) ? Next
->getSUnit() : 0;
323 void AggressiveAntiDepBreaker::HandleLastUse(unsigned Reg
, unsigned KillIdx
,
326 const char *footer
) {
327 unsigned *KillIndices
= State
->GetKillIndices();
328 unsigned *DefIndices
= State
->GetDefIndices();
329 std::multimap
<unsigned, AggressiveAntiDepState::RegisterReference
>&
330 RegRefs
= State
->GetRegRefs();
332 if (!State
->IsLive(Reg
)) {
333 KillIndices
[Reg
] = KillIdx
;
334 DefIndices
[Reg
] = ~0u;
336 State
->LeaveGroup(Reg
);
337 DEBUG(if (header
!= NULL
) {
338 dbgs() << header
<< TRI
->getName(Reg
); header
= NULL
; });
339 DEBUG(dbgs() << "->g" << State
->GetGroup(Reg
) << tag
);
341 // Repeat for subregisters.
342 for (const unsigned *Subreg
= TRI
->getSubRegisters(Reg
);
344 unsigned SubregReg
= *Subreg
;
345 if (!State
->IsLive(SubregReg
)) {
346 KillIndices
[SubregReg
] = KillIdx
;
347 DefIndices
[SubregReg
] = ~0u;
348 RegRefs
.erase(SubregReg
);
349 State
->LeaveGroup(SubregReg
);
350 DEBUG(if (header
!= NULL
) {
351 dbgs() << header
<< TRI
->getName(Reg
); header
= NULL
; });
352 DEBUG(dbgs() << " " << TRI
->getName(SubregReg
) << "->g" <<
353 State
->GetGroup(SubregReg
) << tag
);
357 DEBUG(if ((header
== NULL
) && (footer
!= NULL
)) dbgs() << footer
);
360 void AggressiveAntiDepBreaker::PrescanInstruction(MachineInstr
*MI
,
362 std::set
<unsigned>& PassthruRegs
) {
363 unsigned *DefIndices
= State
->GetDefIndices();
364 std::multimap
<unsigned, AggressiveAntiDepState::RegisterReference
>&
365 RegRefs
= State
->GetRegRefs();
367 // Handle dead defs by simulating a last-use of the register just
368 // after the def. A dead def can occur because the def is truely
369 // dead, or because only a subregister is live at the def. If we
370 // don't do this the dead def will be incorrectly merged into the
372 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
373 MachineOperand
&MO
= MI
->getOperand(i
);
374 if (!MO
.isReg() || !MO
.isDef()) continue;
375 unsigned Reg
= MO
.getReg();
376 if (Reg
== 0) continue;
378 HandleLastUse(Reg
, Count
+ 1, "", "\tDead Def: ", "\n");
381 DEBUG(dbgs() << "\tDef Groups:");
382 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
383 MachineOperand
&MO
= MI
->getOperand(i
);
384 if (!MO
.isReg() || !MO
.isDef()) continue;
385 unsigned Reg
= MO
.getReg();
386 if (Reg
== 0) continue;
388 DEBUG(dbgs() << " " << TRI
->getName(Reg
) << "=g" << State
->GetGroup(Reg
));
390 // If MI's defs have a special allocation requirement, don't allow
391 // any def registers to be changed. Also assume all registers
392 // defined in a call must not be changed (ABI).
393 if (MI
->getDesc().isCall() || MI
->getDesc().hasExtraDefRegAllocReq()) {
394 DEBUG(if (State
->GetGroup(Reg
) != 0) dbgs() << "->g0(alloc-req)");
395 State
->UnionGroups(Reg
, 0);
398 // Any aliased that are live at this point are completely or
399 // partially defined here, so group those aliases with Reg.
400 for (const unsigned *Alias
= TRI
->getAliasSet(Reg
); *Alias
; ++Alias
) {
401 unsigned AliasReg
= *Alias
;
402 if (State
->IsLive(AliasReg
)) {
403 State
->UnionGroups(Reg
, AliasReg
);
404 DEBUG(dbgs() << "->g" << State
->GetGroup(Reg
) << "(via " <<
405 TRI
->getName(AliasReg
) << ")");
409 // Note register reference...
410 const TargetRegisterClass
*RC
= NULL
;
411 if (i
< MI
->getDesc().getNumOperands())
412 RC
= MI
->getDesc().OpInfo
[i
].getRegClass(TRI
);
413 AggressiveAntiDepState::RegisterReference RR
= { &MO
, RC
};
414 RegRefs
.insert(std::make_pair(Reg
, RR
));
417 DEBUG(dbgs() << '\n');
419 // Scan the register defs for this instruction and update
421 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
422 MachineOperand
&MO
= MI
->getOperand(i
);
423 if (!MO
.isReg() || !MO
.isDef()) continue;
424 unsigned Reg
= MO
.getReg();
425 if (Reg
== 0) continue;
426 // Ignore KILLs and passthru registers for liveness...
427 if (MI
->isKill() || (PassthruRegs
.count(Reg
) != 0))
430 // Update def for Reg and aliases.
431 DefIndices
[Reg
] = Count
;
432 for (const unsigned *Alias
= TRI
->getAliasSet(Reg
);
434 unsigned AliasReg
= *Alias
;
435 DefIndices
[AliasReg
] = Count
;
440 void AggressiveAntiDepBreaker::ScanInstruction(MachineInstr
*MI
,
442 DEBUG(dbgs() << "\tUse Groups:");
443 std::multimap
<unsigned, AggressiveAntiDepState::RegisterReference
>&
444 RegRefs
= State
->GetRegRefs();
446 // Scan the register uses for this instruction and update
447 // live-ranges, groups and RegRefs.
448 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
449 MachineOperand
&MO
= MI
->getOperand(i
);
450 if (!MO
.isReg() || !MO
.isUse()) continue;
451 unsigned Reg
= MO
.getReg();
452 if (Reg
== 0) continue;
454 DEBUG(dbgs() << " " << TRI
->getName(Reg
) << "=g" <<
455 State
->GetGroup(Reg
));
457 // It wasn't previously live but now it is, this is a kill. Forget
458 // the previous live-range information and start a new live-range
460 HandleLastUse(Reg
, Count
, "(last-use)");
462 // If MI's uses have special allocation requirement, don't allow
463 // any use registers to be changed. Also assume all registers
464 // used in a call must not be changed (ABI).
465 if (MI
->getDesc().isCall() || MI
->getDesc().hasExtraSrcRegAllocReq()) {
466 DEBUG(if (State
->GetGroup(Reg
) != 0) dbgs() << "->g0(alloc-req)");
467 State
->UnionGroups(Reg
, 0);
470 // Note register reference...
471 const TargetRegisterClass
*RC
= NULL
;
472 if (i
< MI
->getDesc().getNumOperands())
473 RC
= MI
->getDesc().OpInfo
[i
].getRegClass(TRI
);
474 AggressiveAntiDepState::RegisterReference RR
= { &MO
, RC
};
475 RegRefs
.insert(std::make_pair(Reg
, RR
));
478 DEBUG(dbgs() << '\n');
480 // Form a group of all defs and uses of a KILL instruction to ensure
481 // that all registers are renamed as a group.
483 DEBUG(dbgs() << "\tKill Group:");
485 unsigned FirstReg
= 0;
486 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
487 MachineOperand
&MO
= MI
->getOperand(i
);
488 if (!MO
.isReg()) continue;
489 unsigned Reg
= MO
.getReg();
490 if (Reg
== 0) continue;
493 DEBUG(dbgs() << "=" << TRI
->getName(Reg
));
494 State
->UnionGroups(FirstReg
, Reg
);
496 DEBUG(dbgs() << " " << TRI
->getName(Reg
));
501 DEBUG(dbgs() << "->g" << State
->GetGroup(FirstReg
) << '\n');
505 BitVector
AggressiveAntiDepBreaker::GetRenameRegisters(unsigned Reg
) {
506 BitVector
BV(TRI
->getNumRegs(), false);
509 // Check all references that need rewriting for Reg. For each, use
510 // the corresponding register class to narrow the set of registers
511 // that are appropriate for renaming.
512 std::pair
<std::multimap
<unsigned,
513 AggressiveAntiDepState::RegisterReference
>::iterator
,
514 std::multimap
<unsigned,
515 AggressiveAntiDepState::RegisterReference
>::iterator
>
516 Range
= State
->GetRegRefs().equal_range(Reg
);
517 for (std::multimap
<unsigned,
518 AggressiveAntiDepState::RegisterReference
>::iterator Q
= Range
.first
,
519 QE
= Range
.second
; Q
!= QE
; ++Q
) {
520 const TargetRegisterClass
*RC
= Q
->second
.RC
;
521 if (RC
== NULL
) continue;
523 BitVector RCBV
= TRI
->getAllocatableSet(MF
, RC
);
531 DEBUG(dbgs() << " " << RC
->getName());
537 bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters(
538 unsigned AntiDepGroupIndex
,
539 RenameOrderType
& RenameOrder
,
540 std::map
<unsigned, unsigned> &RenameMap
) {
541 unsigned *KillIndices
= State
->GetKillIndices();
542 unsigned *DefIndices
= State
->GetDefIndices();
543 std::multimap
<unsigned, AggressiveAntiDepState::RegisterReference
>&
544 RegRefs
= State
->GetRegRefs();
546 // Collect all referenced registers in the same group as
547 // AntiDepReg. These all need to be renamed together if we are to
548 // break the anti-dependence.
549 std::vector
<unsigned> Regs
;
550 State
->GetGroupRegs(AntiDepGroupIndex
, Regs
, &RegRefs
);
551 assert(Regs
.size() > 0 && "Empty register group!");
552 if (Regs
.size() == 0)
555 // Find the "superest" register in the group. At the same time,
556 // collect the BitVector of registers that can be used to rename
558 DEBUG(dbgs() << "\tRename Candidates for Group g" << AntiDepGroupIndex
560 std::map
<unsigned, BitVector
> RenameRegisterMap
;
561 unsigned SuperReg
= 0;
562 for (unsigned i
= 0, e
= Regs
.size(); i
!= e
; ++i
) {
563 unsigned Reg
= Regs
[i
];
564 if ((SuperReg
== 0) || TRI
->isSuperRegister(SuperReg
, Reg
))
567 // If Reg has any references, then collect possible rename regs
568 if (RegRefs
.count(Reg
) > 0) {
569 DEBUG(dbgs() << "\t\t" << TRI
->getName(Reg
) << ":");
571 BitVector BV
= GetRenameRegisters(Reg
);
572 RenameRegisterMap
.insert(std::pair
<unsigned, BitVector
>(Reg
, BV
));
574 DEBUG(dbgs() << " ::");
575 DEBUG(for (int r
= BV
.find_first(); r
!= -1; r
= BV
.find_next(r
))
576 dbgs() << " " << TRI
->getName(r
));
577 DEBUG(dbgs() << "\n");
581 // All group registers should be a subreg of SuperReg.
582 for (unsigned i
= 0, e
= Regs
.size(); i
!= e
; ++i
) {
583 unsigned Reg
= Regs
[i
];
584 if (Reg
== SuperReg
) continue;
585 bool IsSub
= TRI
->isSubRegister(SuperReg
, Reg
);
586 assert(IsSub
&& "Expecting group subregister");
592 // If DebugDiv > 0 then only rename (renamecnt % DebugDiv) == DebugMod
594 static int renamecnt
= 0;
595 if (renamecnt
++ % DebugDiv
!= DebugMod
)
598 dbgs() << "*** Performing rename " << TRI
->getName(SuperReg
) <<
603 // Check each possible rename register for SuperReg in round-robin
604 // order. If that register is available, and the corresponding
605 // registers are available for the other group subregisters, then we
606 // can use those registers to rename.
607 const TargetRegisterClass
*SuperRC
=
608 TRI
->getPhysicalRegisterRegClass(SuperReg
, MVT::Other
);
610 const TargetRegisterClass::iterator RB
= SuperRC
->allocation_order_begin(MF
);
611 const TargetRegisterClass::iterator RE
= SuperRC
->allocation_order_end(MF
);
613 DEBUG(dbgs() << "\tEmpty Super Regclass!!\n");
617 DEBUG(dbgs() << "\tFind Registers:");
619 if (RenameOrder
.count(SuperRC
) == 0)
620 RenameOrder
.insert(RenameOrderType::value_type(SuperRC
, RE
));
622 const TargetRegisterClass::iterator OrigR
= RenameOrder
[SuperRC
];
623 const TargetRegisterClass::iterator EndR
= ((OrigR
== RE
) ? RB
: OrigR
);
624 TargetRegisterClass::iterator R
= OrigR
;
628 const unsigned NewSuperReg
= *R
;
629 // Don't replace a register with itself.
630 if (NewSuperReg
== SuperReg
) continue;
632 DEBUG(dbgs() << " [" << TRI
->getName(NewSuperReg
) << ':');
635 // For each referenced group register (which must be a SuperReg or
636 // a subregister of SuperReg), find the corresponding subregister
637 // of NewSuperReg and make sure it is free to be renamed.
638 for (unsigned i
= 0, e
= Regs
.size(); i
!= e
; ++i
) {
639 unsigned Reg
= Regs
[i
];
641 if (Reg
== SuperReg
) {
642 NewReg
= NewSuperReg
;
644 unsigned NewSubRegIdx
= TRI
->getSubRegIndex(SuperReg
, Reg
);
645 if (NewSubRegIdx
!= 0)
646 NewReg
= TRI
->getSubReg(NewSuperReg
, NewSubRegIdx
);
649 DEBUG(dbgs() << " " << TRI
->getName(NewReg
));
651 // Check if Reg can be renamed to NewReg.
652 BitVector BV
= RenameRegisterMap
[Reg
];
653 if (!BV
.test(NewReg
)) {
654 DEBUG(dbgs() << "(no rename)");
658 // If NewReg is dead and NewReg's most recent def is not before
659 // Regs's kill, it's safe to replace Reg with NewReg. We
660 // must also check all aliases of NewReg, because we can't define a
661 // register when any sub or super is already live.
662 if (State
->IsLive(NewReg
) || (KillIndices
[Reg
] > DefIndices
[NewReg
])) {
663 DEBUG(dbgs() << "(live)");
667 for (const unsigned *Alias
= TRI
->getAliasSet(NewReg
);
669 unsigned AliasReg
= *Alias
;
670 if (State
->IsLive(AliasReg
) ||
671 (KillIndices
[Reg
] > DefIndices
[AliasReg
])) {
672 DEBUG(dbgs() << "(alias " << TRI
->getName(AliasReg
) << " live)");
681 // Record that 'Reg' can be renamed to 'NewReg'.
682 RenameMap
.insert(std::pair
<unsigned, unsigned>(Reg
, NewReg
));
685 // If we fall-out here, then every register in the group can be
686 // renamed, as recorded in RenameMap.
687 RenameOrder
.erase(SuperRC
);
688 RenameOrder
.insert(RenameOrderType::value_type(SuperRC
, R
));
689 DEBUG(dbgs() << "]\n");
693 DEBUG(dbgs() << ']');
696 DEBUG(dbgs() << '\n');
698 // No registers are free and available!
702 /// BreakAntiDependencies - Identifiy anti-dependencies within the
703 /// ScheduleDAG and break them by renaming registers.
705 unsigned AggressiveAntiDepBreaker::BreakAntiDependencies(
706 const std::vector
<SUnit
>& SUnits
,
707 MachineBasicBlock::iterator Begin
,
708 MachineBasicBlock::iterator End
,
709 unsigned InsertPosIndex
) {
710 unsigned *KillIndices
= State
->GetKillIndices();
711 unsigned *DefIndices
= State
->GetDefIndices();
712 std::multimap
<unsigned, AggressiveAntiDepState::RegisterReference
>&
713 RegRefs
= State
->GetRegRefs();
715 // The code below assumes that there is at least one instruction,
716 // so just duck out immediately if the block is empty.
717 if (SUnits
.empty()) return 0;
719 // For each regclass the next register to use for renaming.
720 RenameOrderType RenameOrder
;
722 // ...need a map from MI to SUnit.
723 std::map
<MachineInstr
*, const SUnit
*> MISUnitMap
;
724 for (unsigned i
= 0, e
= SUnits
.size(); i
!= e
; ++i
) {
725 const SUnit
*SU
= &SUnits
[i
];
726 MISUnitMap
.insert(std::pair
<MachineInstr
*, const SUnit
*>(SU
->getInstr(),
730 // Track progress along the critical path through the SUnit graph as
731 // we walk the instructions. This is needed for regclasses that only
732 // break critical-path anti-dependencies.
733 const SUnit
*CriticalPathSU
= 0;
734 MachineInstr
*CriticalPathMI
= 0;
735 if (CriticalPathSet
.any()) {
736 for (unsigned i
= 0, e
= SUnits
.size(); i
!= e
; ++i
) {
737 const SUnit
*SU
= &SUnits
[i
];
738 if (!CriticalPathSU
||
739 ((SU
->getDepth() + SU
->Latency
) >
740 (CriticalPathSU
->getDepth() + CriticalPathSU
->Latency
))) {
745 CriticalPathMI
= CriticalPathSU
->getInstr();
749 DEBUG(dbgs() << "\n===== Aggressive anti-dependency breaking\n");
750 DEBUG(dbgs() << "Available regs:");
751 for (unsigned Reg
= 0; Reg
< TRI
->getNumRegs(); ++Reg
) {
752 if (!State
->IsLive(Reg
))
753 DEBUG(dbgs() << " " << TRI
->getName(Reg
));
755 DEBUG(dbgs() << '\n');
758 // Attempt to break anti-dependence edges. Walk the instructions
759 // from the bottom up, tracking information about liveness as we go
760 // to help determine which registers are available.
762 unsigned Count
= InsertPosIndex
- 1;
763 for (MachineBasicBlock::iterator I
= End
, E
= Begin
;
765 MachineInstr
*MI
= --I
;
767 DEBUG(dbgs() << "Anti: ");
770 std::set
<unsigned> PassthruRegs
;
771 GetPassthruRegs(MI
, PassthruRegs
);
773 // Process the defs in MI...
774 PrescanInstruction(MI
, Count
, PassthruRegs
);
776 // The dependence edges that represent anti- and output-
777 // dependencies that are candidates for breaking.
778 std::vector
<const SDep
*> Edges
;
779 const SUnit
*PathSU
= MISUnitMap
[MI
];
780 AntiDepEdges(PathSU
, Edges
);
782 // If MI is not on the critical path, then we don't rename
783 // registers in the CriticalPathSet.
784 BitVector
*ExcludeRegs
= NULL
;
785 if (MI
== CriticalPathMI
) {
786 CriticalPathSU
= CriticalPathStep(CriticalPathSU
);
787 CriticalPathMI
= (CriticalPathSU
) ? CriticalPathSU
->getInstr() : 0;
789 ExcludeRegs
= &CriticalPathSet
;
792 // Ignore KILL instructions (they form a group in ScanInstruction
793 // but don't cause any anti-dependence breaking themselves)
795 // Attempt to break each anti-dependency...
796 for (unsigned i
= 0, e
= Edges
.size(); i
!= e
; ++i
) {
797 const SDep
*Edge
= Edges
[i
];
798 SUnit
*NextSU
= Edge
->getSUnit();
800 if ((Edge
->getKind() != SDep::Anti
) &&
801 (Edge
->getKind() != SDep::Output
)) continue;
803 unsigned AntiDepReg
= Edge
->getReg();
804 DEBUG(dbgs() << "\tAntidep reg: " << TRI
->getName(AntiDepReg
));
805 assert(AntiDepReg
!= 0 && "Anti-dependence on reg0?");
807 if (!AllocatableSet
.test(AntiDepReg
)) {
808 // Don't break anti-dependencies on non-allocatable registers.
809 DEBUG(dbgs() << " (non-allocatable)\n");
811 } else if ((ExcludeRegs
!= NULL
) && ExcludeRegs
->test(AntiDepReg
)) {
812 // Don't break anti-dependencies for critical path registers
813 // if not on the critical path
814 DEBUG(dbgs() << " (not critical-path)\n");
816 } else if (PassthruRegs
.count(AntiDepReg
) != 0) {
817 // If the anti-dep register liveness "passes-thru", then
818 // don't try to change it. It will be changed along with
819 // the use if required to break an earlier antidep.
820 DEBUG(dbgs() << " (passthru)\n");
823 // No anti-dep breaking for implicit deps
824 MachineOperand
*AntiDepOp
= MI
->findRegisterDefOperand(AntiDepReg
);
825 assert(AntiDepOp
!= NULL
&&
826 "Can't find index for defined register operand");
827 if ((AntiDepOp
== NULL
) || AntiDepOp
->isImplicit()) {
828 DEBUG(dbgs() << " (implicit)\n");
832 // If the SUnit has other dependencies on the SUnit that
833 // it anti-depends on, don't bother breaking the
834 // anti-dependency since those edges would prevent such
835 // units from being scheduled past each other
838 // Also, if there are dependencies on other SUnits with the
839 // same register as the anti-dependency, don't attempt to
841 for (SUnit::const_pred_iterator P
= PathSU
->Preds
.begin(),
842 PE
= PathSU
->Preds
.end(); P
!= PE
; ++P
) {
843 if (P
->getSUnit() == NextSU
?
844 (P
->getKind() != SDep::Anti
|| P
->getReg() != AntiDepReg
) :
845 (P
->getKind() == SDep::Data
&& P
->getReg() == AntiDepReg
)) {
850 for (SUnit::const_pred_iterator P
= PathSU
->Preds
.begin(),
851 PE
= PathSU
->Preds
.end(); P
!= PE
; ++P
) {
852 if ((P
->getSUnit() == NextSU
) && (P
->getKind() != SDep::Anti
) &&
853 (P
->getKind() != SDep::Output
)) {
854 DEBUG(dbgs() << " (real dependency)\n");
857 } else if ((P
->getSUnit() != NextSU
) &&
858 (P
->getKind() == SDep::Data
) &&
859 (P
->getReg() == AntiDepReg
)) {
860 DEBUG(dbgs() << " (other dependency)\n");
866 if (AntiDepReg
== 0) continue;
869 assert(AntiDepReg
!= 0);
870 if (AntiDepReg
== 0) continue;
872 // Determine AntiDepReg's register group.
873 const unsigned GroupIndex
= State
->GetGroup(AntiDepReg
);
874 if (GroupIndex
== 0) {
875 DEBUG(dbgs() << " (zero group)\n");
879 DEBUG(dbgs() << '\n');
881 // Look for a suitable register to use to break the anti-dependence.
882 std::map
<unsigned, unsigned> RenameMap
;
883 if (FindSuitableFreeRegisters(GroupIndex
, RenameOrder
, RenameMap
)) {
884 DEBUG(dbgs() << "\tBreaking anti-dependence edge on "
885 << TRI
->getName(AntiDepReg
) << ":");
887 // Handle each group register...
888 for (std::map
<unsigned, unsigned>::iterator
889 S
= RenameMap
.begin(), E
= RenameMap
.end(); S
!= E
; ++S
) {
890 unsigned CurrReg
= S
->first
;
891 unsigned NewReg
= S
->second
;
893 DEBUG(dbgs() << " " << TRI
->getName(CurrReg
) << "->" <<
894 TRI
->getName(NewReg
) << "(" <<
895 RegRefs
.count(CurrReg
) << " refs)");
897 // Update the references to the old register CurrReg to
898 // refer to the new register NewReg.
899 std::pair
<std::multimap
<unsigned,
900 AggressiveAntiDepState::RegisterReference
>::iterator
,
901 std::multimap
<unsigned,
902 AggressiveAntiDepState::RegisterReference
>::iterator
>
903 Range
= RegRefs
.equal_range(CurrReg
);
904 for (std::multimap
<unsigned,
905 AggressiveAntiDepState::RegisterReference
>::iterator
906 Q
= Range
.first
, QE
= Range
.second
; Q
!= QE
; ++Q
) {
907 Q
->second
.Operand
->setReg(NewReg
);
910 // We just went back in time and modified history; the
911 // liveness information for CurrReg is now inconsistent. Set
912 // the state as if it were dead.
913 State
->UnionGroups(NewReg
, 0);
914 RegRefs
.erase(NewReg
);
915 DefIndices
[NewReg
] = DefIndices
[CurrReg
];
916 KillIndices
[NewReg
] = KillIndices
[CurrReg
];
918 State
->UnionGroups(CurrReg
, 0);
919 RegRefs
.erase(CurrReg
);
920 DefIndices
[CurrReg
] = KillIndices
[CurrReg
];
921 KillIndices
[CurrReg
] = ~0u;
922 assert(((KillIndices
[CurrReg
] == ~0u) !=
923 (DefIndices
[CurrReg
] == ~0u)) &&
924 "Kill and Def maps aren't consistent for AntiDepReg!");
928 DEBUG(dbgs() << '\n');
933 ScanInstruction(MI
, Count
);