Go to the documentation of this file.
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();
58 DefIndices[
i] = BBSize;
64 bool IsReturnBlock =
BB->isReturnBlock();
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!");
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;
159 void 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) {
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);
253 void 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) {
275 if (ClobbersPhysRegAndSubRegs(
i)) {
276 DefIndices[
i] = Count;
277 KillIndices[
i] = ~0u;
279 Classes[
i] =
nullptr;
285 if (!MO.
isReg())
continue;
287 if (
Reg == 0)
continue;
288 if (!MO.
isDef())
continue;
291 if (
MI.isRegTiedToUseOperand(
i))
296 bool Keep = KeepRegs.
test(
Reg);
301 unsigned SubregReg = *SRI;
302 DefIndices[SubregReg] = Count;
303 KillIndices[SubregReg] = ~0u;
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] = ~0u;
358 CriticalAntiDepBreaker::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())
399 unsigned CriticalAntiDepBreaker::
400 findSuitableFreeRegister(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)
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");
474 if (KillIndices[
Reg] == ~0u)
483 const SUnit *CriticalPathSU = Max;
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;
627 if (MO.
isDef() &&
Reg != AntiDepReg)
628 ForbidRegs.push_back(
Reg);
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);
This is an optimization pass for GlobalISel generic memory operations.
ArrayRef< MCPhysReg > getOrder(const TargetRegisterClass *RC) const
getOrder - Returns the preferred allocation order for RC.
~CriticalAntiDepBreaker() override
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
Reg
All possible values of the reg field in the ModR/M byte.
@ Anti
A register anti-dependence (aka WAR).
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...
unsigned const TargetRegisterInfo * TRI
AntiDepBreaker * createCriticalAntiDepBreaker(MachineFunction &MFi, const RegisterClassInfo &RCI)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
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,...
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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...
const HexagonInstrInfo * TII
MachineOperand class - Representation of each machine instruction operand.
@ Data
Regular data dependence (aka true-dependence).
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
void StartBlock(MachineBasicBlock *BB) override
Initialize anti-dep breaking for a new basic block.
static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
bool regsOverlap(Register RegA, Register RegB) const
Returns true if the two registers are equal or alias each other.
void Observe(MachineInstr &MI, unsigned Count, unsigned InsertPosIndex) override
Update liveness information to account for the current instruction, which will not be scheduled.
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...
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Representation of each machine instruction.
virtual bool isPredicated(const MachineInstr &MI) const
Returns true if the instruction is already predicated.
const MCPhysReg * getCalleeSavedRegs() const
Returns list of callee saved registers.
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
static const SDep * CriticalPathStep(const SUnit *SU)
CriticalPathStep - Return the next SUnit after SU on the bottom-up critical path.
bool isAllocatable(MCRegister PhysReg) const
isAllocatable - Returns true when PhysReg belongs to an allocatable register class and it hasn't been...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
bool isEarlyClobber() const
MCSuperRegIterator enumerates all super-registers of Reg.
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
Register getReg() const
getReg - Returns the register number.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
BitVector getPristineRegs(const MachineFunction &MF) const
Return a set of physical registers that are pristine.
void FinishBlock() override
Finish anti-dep breaking for a basic block.
unsigned const MachineRegisterInfo * MRI
Wrapper class representing virtual and physical registers.
bool test(unsigned Idx) const
This class works in conjunction with the post-RA scheduler to rename registers to break register anti...
MCSubRegIterator enumerates all sub-registers of Reg.
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
CriticalAntiDepBreaker(MachineFunction &MFi, const RegisterClassInfo &RCI)
SmallVector< SDep, 4 > Preds
All sunit predecessors.
Scheduling unit. This is a node in the scheduling DAG.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
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.
std::vector< std::pair< MachineInstr *, MachineInstr * > > DbgValueVector
MCRegAliasIterator enumerates all registers aliasing Reg.