39#define DEBUG_TYPE "post-RA-sched"
43 : MF(MFi),
MRI(MF.getRegInfo()),
TII(MF.getSubtarget().getInstrInfo()),
44 TRI(MF.getSubtarget().getRegisterInfo()), RegClassInfo(RCI),
45 Classes(
TRI->getNumRegs(), nullptr), KillIndices(
TRI->getNumRegs(), 0),
46 DefIndices(
TRI->getNumRegs(), 0), KeepRegs(
TRI->getNumRegs(),
false) {}
51 const unsigned BBSize = BB->
size();
52 for (
unsigned i = 0, e = TRI->
getNumRegs(); i != e; ++i) {
58 DefIndices[i] = BBSize;
68 for (
const auto &LI : Succ->liveins()) {
72 KillIndices[Reg] = BBSize;
73 DefIndices[Reg] = ~0u;
85 if (!IsReturnBlock && !Pristine.
test(Reg))
90 KillIndices[Reg] = BBSize;
91 DefIndices[Reg] = ~0u;
102 unsigned InsertPosIndex) {
110 if (
MI.isDebugInstr() ||
MI.isKill())
112 assert(Count < InsertPosIndex &&
"Instruction index out of expected range!");
114 for (
unsigned Reg = 0; Reg != TRI->
getNumRegs(); ++Reg) {
115 if (KillIndices[Reg] != ~0u) {
120 KillIndices[Reg] = Count;
121 }
else if (DefIndices[Reg] < InsertPosIndex && DefIndices[Reg] >= Count) {
130 DefIndices[Reg] = InsertPosIndex;
134 PrescanInstruction(
MI);
135 ScanInstruction(
MI, Count);
141 const SDep *Next =
nullptr;
142 unsigned NextDepth = 0;
145 const SUnit *PredSU =
P.getSUnit();
146 unsigned PredLatency =
P.getLatency();
147 unsigned PredTotalLatency = PredSU->
getDepth() + PredLatency;
150 if (NextDepth < PredTotalLatency ||
151 (NextDepth == PredTotalLatency &&
P.getKind() ==
SDep::Anti)) {
152 NextDepth = PredTotalLatency;
159void CriticalAntiDepBreaker::PrescanInstruction(
MachineInstr &
MI) {
181 for (
unsigned i = 0, e =
MI.getNumOperands(); i != e; ++i) {
183 if (!MO.
isReg())
continue;
185 if (Reg == 0)
continue;
188 if (i <
MI.getDesc().getNumOperands())
193 if (!Classes[Reg] && NewRC)
194 Classes[
Reg] = NewRC;
195 else if (!NewRC || Classes[Reg] != NewRC)
203 unsigned AliasReg = *AI;
204 if (Classes[AliasReg]) {
212 RegRefs.insert(std::make_pair(Reg, &MO));
214 if (MO.
isUse() && Special) {
215 if (!KeepRegs.
test(Reg)) {
218 KeepRegs.
set(*SubRegs);
223 for (
unsigned I = 0,
E =
MI.getNumOperands();
I !=
E; ++
I) {
225 if (!MO.
isReg())
continue;
239 if (
MI.isRegTiedToUseOperand(
I) &&
242 SubRegs.
isValid(); ++SubRegs) {
243 KeepRegs.
set(*SubRegs);
246 SuperRegs.
isValid(); ++SuperRegs) {
247 KeepRegs.
set(*SuperRegs);
253void CriticalAntiDepBreaker::ScanInstruction(
MachineInstr &
MI,
unsigned Count) {
257 assert(!
MI.isKill() &&
"Attempting to scan a kill instruction");
262 for (
unsigned i = 0, e =
MI.getNumOperands(); i != e; ++i) {
266 auto ClobbersPhysRegAndSubRegs = [&](
unsigned PhysReg) {
274 for (
unsigned i = 0, e = TRI->
getNumRegs(); i !=
e; ++i) {
275 if (ClobbersPhysRegAndSubRegs(i)) {
276 DefIndices[i] = Count;
277 KillIndices[i] = ~0
u;
279 Classes[i] =
nullptr;
285 if (!MO.
isReg())
continue;
287 if (Reg == 0)
continue;
288 if (!MO.
isDef())
continue;
291 if (
MI.isRegTiedToUseOperand(i))
301 unsigned SubregReg = *SRI;
302 DefIndices[SubregReg] = Count;
303 KillIndices[SubregReg] = ~0
u;
304 Classes[SubregReg] =
nullptr;
305 RegRefs.erase(SubregReg);
307 KeepRegs.
reset(SubregReg);
314 for (
unsigned i = 0, e =
MI.getNumOperands(); i !=
e; ++i) {
316 if (!MO.
isReg())
continue;
318 if (Reg == 0)
continue;
319 if (!MO.
isUse())
continue;
322 if (i <
MI.getDesc().getNumOperands())
327 if (!Classes[Reg] && NewRC)
328 Classes[
Reg] = NewRC;
329 else if (!NewRC || Classes[Reg] != NewRC)
332 RegRefs.insert(std::make_pair(Reg, &MO));
337 unsigned AliasReg = *AI;
338 if (KillIndices[AliasReg] == ~0u) {
339 KillIndices[AliasReg] = Count;
340 DefIndices[AliasReg] = ~0
u;
358CriticalAntiDepBreaker::isNewRegClobberedByRefs(RegRefIter RegRefBegin,
359 RegRefIter RegRefEnd,
361 for (RegRefIter
I = RegRefBegin;
I != RegRefEnd; ++
I ) {
373 if (CheckOper.isRegMask() && CheckOper.clobbersPhysReg(NewReg))
376 if (!CheckOper.isReg() || !CheckOper.isDef() ||
377 CheckOper.getReg() != NewReg)
382 if (RefOper->
isDef())
387 if (CheckOper.isEarlyClobber())
392 if (
MI->isInlineAsm())
399unsigned CriticalAntiDepBreaker::
400findSuitableFreeRegister(RegRefIter RegRefBegin,
401 RegRefIter RegRefEnd,
407 for (
unsigned NewReg : Order) {
409 if (NewReg == AntiDepReg)
continue;
413 if (NewReg == LastNewReg)
continue;
417 if (isNewRegClobberedByRefs(RegRefBegin, RegRefEnd, NewReg))
continue;
420 assert(((KillIndices[AntiDepReg] == ~0u) != (DefIndices[AntiDepReg] == ~0u))
421 &&
"Kill and Def maps aren't consistent for AntiDepReg!");
422 assert(((KillIndices[NewReg] == ~0u) != (DefIndices[NewReg] == ~0u))
423 &&
"Kill and Def maps aren't consistent for NewReg!");
424 if (KillIndices[NewReg] != ~0u ||
426 KillIndices[AntiDepReg] > DefIndices[NewReg])
429 bool Forbidden =
false;
430 for (
unsigned R : Forbid)
431 if (
TRI->regsOverlap(NewReg, R)) {
435 if (Forbidden)
continue;
447 unsigned InsertPosIndex,
451 if (SUnits.empty())
return 0;
460 const SUnit *Max =
nullptr;
461 for (
const SUnit &SU : SUnits) {
462 MISUnitMap[SU.getInstr()] = &SU;
463 if (!Max || SU.getDepth() + SU.Latency > Max->getDepth() + Max->Latency)
466 assert(Max &&
"Failed to find bottom of the critical path");
471 << (Max->getDepth() + Max->Latency) <<
"\n");
473 for (
unsigned Reg = 0; Reg <
TRI->getNumRegs(); ++Reg) {
474 if (KillIndices[Reg] == ~0u)
483 const SUnit *CriticalPathSU = Max;
527 std::vector<unsigned> LastNewReg(
TRI->getNumRegs(), 0);
533 unsigned Count = InsertPosIndex - 1;
543 if (
MI.isDebugInstr() ||
MI.isKill())
559 unsigned AntiDepReg = 0;
560 if (&
MI == CriticalPathMI) {
562 const SUnit *NextSU = Edge->getSUnit();
566 AntiDepReg = Edge->getReg();
567 assert(AntiDepReg != 0 &&
"Anti-dependence on reg0?");
571 else if (KeepRegs.
test(AntiDepReg))
585 if (
P.getSUnit() == NextSU
586 ? (
P.getKind() !=
SDep::Anti ||
P.getReg() != AntiDepReg)
588 P.getReg() == AntiDepReg)) {
594 CriticalPathSU = NextSU;
595 CriticalPathMI = CriticalPathSU->
getInstr();
598 CriticalPathSU =
nullptr;
599 CriticalPathMI =
nullptr;
603 PrescanInstruction(
MI);
614 else if (AntiDepReg) {
620 if (!MO.
isReg())
continue;
622 if (Reg == 0)
continue;
623 if (MO.
isUse() &&
TRI->regsOverlap(AntiDepReg, Reg)) {
627 if (MO.
isDef() && Reg != AntiDepReg)
636 assert((AntiDepReg == 0 || RC !=
nullptr) &&
637 "Register should be live if it's causing an anti-dependence!");
645 if (AntiDepReg != 0) {
646 std::pair<std::multimap<unsigned, MachineOperand *>::iterator,
647 std::multimap<unsigned, MachineOperand *>::iterator>
648 Range = RegRefs.equal_range(AntiDepReg);
649 if (
unsigned NewReg = findSuitableFreeRegister(Range.first, Range.second,
651 LastNewReg[AntiDepReg],
655 << RegRefs.count(AntiDepReg) <<
" references"
660 for (std::multimap<unsigned, MachineOperand *>::iterator
661 Q = Range.first, QE = Range.second; Q != QE; ++Q) {
662 Q->second->setReg(NewReg);
666 const SUnit *SU = MISUnitMap[Q->second->getParent()];
675 Classes[NewReg] = Classes[AntiDepReg];
676 DefIndices[NewReg] = DefIndices[AntiDepReg];
677 KillIndices[NewReg] = KillIndices[AntiDepReg];
678 assert(((KillIndices[NewReg] == ~0u) !=
679 (DefIndices[NewReg] == ~0u)) &&
680 "Kill and Def maps aren't consistent for NewReg!");
682 Classes[AntiDepReg] =
nullptr;
683 DefIndices[AntiDepReg] = KillIndices[AntiDepReg];
684 KillIndices[AntiDepReg] = ~0u;
685 assert(((KillIndices[AntiDepReg] == ~0u) !=
686 (DefIndices[AntiDepReg] == ~0u)) &&
687 "Kill and Def maps aren't consistent for AntiDepReg!");
689 RegRefs.erase(AntiDepReg);
690 LastNewReg[AntiDepReg] = NewReg;
695 ScanInstruction(
MI, Count);
unsigned const MachineRegisterInfo * MRI
static const SUnit * CriticalPathStep(const SUnit *SU)
CriticalPathStep - Return the next SUnit after SU on the bottom-up critical path.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the DenseMap class.
const HexagonInstrInfo * TII
unsigned const TargetRegisterInfo * TRI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
This class works in conjunction with the post-RA scheduler to rename registers to break register anti...
void UpdateDbgValues(const DbgValueVector &DbgValues, MachineInstr *ParentMI, unsigned OldReg, unsigned NewReg)
Update all DBG_VALUE instructions that may be affected by the dependency breaker's update of ParentMI...
std::vector< std::pair< MachineInstr *, MachineInstr * > > DbgValueVector
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
bool test(unsigned Idx) const
~CriticalAntiDepBreaker() override
unsigned BreakAntiDependencies(const std::vector< SUnit > &SUnits, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned InsertPosIndex, DbgValueVector &DbgValues) override
Identifiy anti-dependencies along the critical path of the ScheduleDAG and break them by renaming reg...
void FinishBlock() override
Finish anti-dep breaking for a basic block.
void Observe(MachineInstr &MI, unsigned Count, unsigned InsertPosIndex) override
Update liveness information to account for the current instruction, which will not be scheduled.
void StartBlock(MachineBasicBlock *BB) override
Initialize anti-dep breaking for a new basic block.
CriticalAntiDepBreaker(MachineFunction &MFi, const RegisterClassInfo &RCI)
MCRegAliasIterator enumerates all registers aliasing Reg.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
MCSubRegIterator enumerates all sub-registers of Reg.
MCSuperRegIterator enumerates all super-registers of Reg.
bool isReturnBlock() const
Convenience function that returns true if the block ends in a return instruction.
iterator_range< succ_iterator > successors()
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
BitVector getPristineRegs(const MachineFunction &MF) const
Return a set of physical registers that are pristine.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Representation of each machine instruction.
MachineOperand class - Representation of each machine instruction operand.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
bool isEarlyClobber() const
Register getReg() const
getReg - Returns the register number.
static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
bool isAllocatable(MCRegister PhysReg) const
isAllocatable - Returns true when PhysReg belongs to an allocatable register class and it hasn't been...
const MCPhysReg * getCalleeSavedRegs() const
Returns list of callee saved registers.
ArrayRef< MCPhysReg > getOrder(const TargetRegisterClass *RC) const
getOrder - Returns the preferred allocation order for RC.
Wrapper class representing virtual and physical registers.
@ Anti
A register anti-dependence (aka WAR).
@ Data
Regular data dependence (aka true-dependence).
Scheduling unit. This is a node in the scheduling DAG.
unsigned getDepth() const
Returns the depth of this node, which is the length of the maximum path up to any node which has no p...
SmallVector< SDep, 4 > Preds
All sunit predecessors.
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
virtual bool isPredicated(const MachineInstr &MI) const
Returns true if the instruction is already predicated.
virtual const TargetRegisterClass * getRegClass(const MCInstrDesc &MCID, unsigned OpNum, const TargetRegisterInfo *TRI, const MachineFunction &MF) const
Given a machine instruction descriptor, returns the register class constraint for OpNum,...
Reg
All possible values of the reg field in the ModR/M byte.
This is an optimization pass for GlobalISel generic memory operations.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
AntiDepBreaker * createCriticalAntiDepBreaker(MachineFunction &MFi, const RegisterClassInfo &RCI)
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
@ Keep
No function return thunk.