46 #define DEBUG_TYPE "post-RA-sched" 51 cl::desc(
"Debug control for aggressive anti-dep breaker"),
56 cl::desc(
"Debug control for aggressive anti-dep breaker"),
61 : NumTargetRegs(TargetRegs), GroupNodes(TargetRegs, 0),
62 GroupNodeIndices(TargetRegs, 0), KillIndices(TargetRegs, 0),
63 DefIndices(TargetRegs, 0) {
64 const unsigned BBSize = BB->
size();
65 for (
unsigned i = 0; i < NumTargetRegs; ++i) {
68 GroupNodeIndices[i] = i;
71 DefIndices[i] = BBSize;
76 unsigned Node = GroupNodeIndices[
Reg];
77 while (GroupNodes[Node] != Node)
78 Node = GroupNodes[Node];
85 std::vector<unsigned> &Regs,
86 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference> *RegRefs)
88 for (
unsigned Reg = 0;
Reg != NumTargetRegs; ++
Reg) {
95 assert(GroupNodes[0] == 0 &&
"GroupNode 0 not parent!");
96 assert(GroupNodeIndices[0] == 0 &&
"Reg 0 not in Group 0!");
103 unsigned Parent = (Group1 == 0) ? Group1 : Group2;
104 unsigned Other = (Parent == Group1) ? Group2 : Group1;
105 GroupNodes.at(Other) = Parent;
113 unsigned idx = GroupNodes.size();
114 GroupNodes.push_back(idx);
115 GroupNodeIndices[
Reg] = idx;
122 return((KillIndices[Reg] != ~0u) && (DefIndices[Reg] == ~0u));
129 TII(MF.getSubtarget().getInstrInfo()),
130 TRI(MF.getSubtarget().getRegisterInfo()), RegClassInfo(RCI) {
133 for (
unsigned i = 0,
e = CriticalPathRCs.
size(); i <
e; ++i) {
135 if (CriticalPathSet.
none())
136 CriticalPathSet = CPSet;
138 CriticalPathSet |= CPSet;
163 for (
const auto &LI : (*SI)->liveins()) {
168 DefIndices[
Reg] = ~0u;
180 if (!IsReturnBlock && !Pristine.
test(Reg))
183 unsigned AliasReg = *AI;
185 KillIndices[AliasReg] = BB->
size();
186 DefIndices[AliasReg] = ~0u;
197 unsigned InsertPosIndex) {
198 assert(Count < InsertPosIndex &&
"Instruction index out of expected range!");
200 std::set<unsigned> PassthruRegs;
201 GetPassthruRegs(MI, PassthruRegs);
202 PrescanInstruction(MI, Count, PassthruRegs);
203 ScanInstruction(MI, Count);
220 <<
"->g0(region live-out)");
222 }
else if ((DefIndices[
Reg] < InsertPosIndex)
223 && (DefIndices[
Reg] >= Count)) {
224 DefIndices[
Reg] = Count;
248 void AggressiveAntiDepBreaker::GetPassthruRegs(
252 if (!MO.
isReg())
continue;
254 IsImplicitDefUse(MI, MO)) {
258 PassthruRegs.insert(*SubRegs);
271 Edges.push_back(&*
P);
279 const SDep *Next =
nullptr;
280 unsigned NextDepth = 0;
285 const SUnit *PredSU =
P->getSUnit();
286 unsigned PredLatency =
P->getLatency();
287 unsigned PredTotalLatency = PredSU->
getDepth() + PredLatency;
290 if (NextDepth < PredTotalLatency ||
291 (NextDepth == PredTotalLatency &&
P->getKind() ==
SDep::Anti)) {
292 NextDepth = PredTotalLatency;
298 return (Next) ? Next->
getSUnit() :
nullptr;
301 void AggressiveAntiDepBreaker::HandleLastUse(
unsigned Reg,
unsigned KillIdx,
304 const char *footer) {
307 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
320 if (!State->
IsLive(Reg)) {
321 KillIndices[
Reg] = KillIdx;
322 DefIndices[
Reg] = ~0u;
335 unsigned SubregReg = *SubRegs;
336 if (!State->
IsLive(SubregReg)) {
337 KillIndices[SubregReg] = KillIdx;
338 DefIndices[SubregReg] = ~0u;
339 RegRefs.erase(SubregReg);
346 << State->
GetGroup(SubregReg) << tag);
354 void AggressiveAntiDepBreaker::PrescanInstruction(
355 MachineInstr &MI,
unsigned Count, std::set<unsigned> &PassthruRegs) {
357 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
369 if (Reg == 0)
continue;
371 HandleLastUse(Reg, Count + 1,
"",
"\tDead Def: ",
"\n");
379 if (Reg == 0)
continue;
398 unsigned AliasReg = *AI;
399 if (State->
IsLive(AliasReg)) {
411 RegRefs.insert(std::make_pair(Reg, RR));
422 if (Reg == 0)
continue;
424 if (MI.
isKill() || (PassthruRegs.count(Reg) != 0))
438 DefIndices[*AI] = Count;
443 void AggressiveAntiDepBreaker::ScanInstruction(
MachineInstr &MI,
446 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
475 if (Reg == 0)
continue;
483 HandleLastUse(Reg, Count,
"(last-use)");
495 RegRefs.insert(std::make_pair(Reg, RR));
505 unsigned FirstReg = 0;
508 if (!MO.
isReg())
continue;
510 if (Reg == 0)
continue;
525 BitVector AggressiveAntiDepBreaker::GetRenameRegisters(
unsigned Reg) {
550 bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters(
551 unsigned AntiDepGroupIndex,
552 RenameOrderType& RenameOrder,
553 std::map<unsigned, unsigned> &RenameMap) {
556 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
562 std::vector<unsigned> Regs;
564 assert(!Regs.empty() &&
"Empty register group!");
571 LLVM_DEBUG(
dbgs() <<
"\tRename Candidates for Group g" << AntiDepGroupIndex
573 std::map<unsigned, BitVector> RenameRegisterMap;
574 unsigned SuperReg = 0;
575 for (
unsigned i = 0,
e = Regs.size(); i !=
e; ++i) {
576 unsigned Reg = Regs[i];
581 if (RegRefs.count(Reg) > 0) {
586 BV = GetRenameRegisters(Reg);
590 for (
unsigned r : BV.set_bits())
598 for (
unsigned i = 0,
e = Regs.size(); i !=
e; ++i) {
599 unsigned Reg = Regs[i];
600 if (Reg == SuperReg)
continue;
612 static int renamecnt = 0;
616 dbgs() <<
"*** Performing rename " <<
printReg(SuperReg, TRI)
617 <<
" for debug ***\n";
640 RenameOrder.insert(RenameOrderType::value_type(SuperRC, Order.
size()));
642 unsigned OrigR = RenameOrder[SuperRC];
643 unsigned EndR = ((OrigR == Order.
size()) ? 0 : OrigR);
646 if (R == 0) R = Order.
size();
648 const unsigned NewSuperReg = Order[R];
652 if (NewSuperReg == SuperReg)
continue;
660 for (
unsigned i = 0,
e = Regs.size(); i !=
e; ++i) {
661 unsigned Reg = Regs[i];
663 if (Reg == SuperReg) {
664 NewReg = NewSuperReg;
667 if (NewSubRegIdx != 0)
668 NewReg = TRI->
getSubReg(NewSuperReg, NewSubRegIdx);
674 if (!RenameRegisterMap[Reg].
test(NewReg)) {
683 if (State->
IsLive(NewReg) || (KillIndices[
Reg] > DefIndices[NewReg])) {
689 unsigned AliasReg = *AI;
690 if (State->
IsLive(AliasReg) ||
691 (KillIndices[
Reg] > DefIndices[AliasReg])) {
693 <<
"(alias " <<
printReg(AliasReg, TRI) <<
" live)");
704 for (
const auto &Q :
make_range(RegRefs.equal_range(Reg))) {
719 for (
const auto &Q :
make_range(RegRefs.equal_range(Reg))) {
720 if (!Q.second.Operand->isDef() || !Q.second.Operand->isEarlyClobber())
731 RenameMap.insert(std::pair<unsigned, unsigned>(Reg, NewReg));
736 RenameOrder.erase(SuperRC);
737 RenameOrder.insert(RenameOrderType::value_type(SuperRC, R));
754 const std::vector<SUnit> &SUnits,
757 unsigned InsertPosIndex,
761 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
766 if (SUnits.empty())
return 0;
769 RenameOrderType RenameOrder;
772 std::map<MachineInstr *, const SUnit *> MISUnitMap;
773 for (
unsigned i = 0,
e = SUnits.size(); i !=
e; ++i) {
774 const SUnit *SU = &SUnits[i];
775 MISUnitMap.insert(std::pair<MachineInstr *, const SUnit *>(SU->
getInstr(),
782 const SUnit *CriticalPathSU =
nullptr;
784 if (CriticalPathSet.
any()) {
785 for (
unsigned i = 0,
e = SUnits.size(); i !=
e; ++i) {
786 const SUnit *SU = &SUnits[i];
787 if (!CriticalPathSU ||
793 assert(CriticalPathSU &&
"Failed to find SUnit critical path");
794 CriticalPathMI = CriticalPathSU->
getInstr();
798 LLVM_DEBUG(
dbgs() <<
"\n===== Aggressive anti-dependency breaking\n");
813 unsigned Count = InsertPosIndex - 1;
824 std::set<unsigned> PassthruRegs;
825 GetPassthruRegs(MI, PassthruRegs);
828 PrescanInstruction(MI, Count, PassthruRegs);
832 std::vector<const SDep *> Edges;
833 const SUnit *PathSU = MISUnitMap[&
MI];
839 if (&MI == CriticalPathMI) {
841 CriticalPathMI = (CriticalPathSU) ? CriticalPathSU->
getInstr() :
nullptr;
842 }
else if (CriticalPathSet.
any()) {
843 ExcludeRegs = &CriticalPathSet;
850 for (
unsigned i = 0,
e = Edges.size(); i !=
e; ++i) {
851 const SDep *Edge = Edges[i];
857 unsigned AntiDepReg = Edge->
getReg();
859 assert(AntiDepReg != 0 &&
"Anti-dependence on reg0?");
865 }
else if (ExcludeRegs && ExcludeRegs->
test(AntiDepReg)) {
870 }
else if (PassthruRegs.count(AntiDepReg) != 0) {
879 assert(AntiDepOp &&
"Can't find index for defined register operand");
895 PE = PathSU->
Preds.end();
P != PE; ++
P) {
896 if (
P->getSUnit() == NextSU ?
897 (
P->getKind() !=
SDep::Anti ||
P->getReg() != AntiDepReg) :
898 (
P->getKind() ==
SDep::Data &&
P->getReg() == AntiDepReg)) {
904 PE = PathSU->
Preds.end();
P != PE; ++
P) {
905 if ((
P->getSUnit() == NextSU) && (
P->getKind() !=
SDep::Anti) &&
910 }
else if ((
P->getSUnit() != NextSU) &&
912 (
P->getReg() == AntiDepReg)) {
919 if (AntiDepReg == 0)
continue;
942 if (AntiDepReg == 0)
continue;
946 if (AntiDepReg == 0)
continue;
949 const unsigned GroupIndex = State->
GetGroup(AntiDepReg);
950 if (GroupIndex == 0) {
958 std::map<unsigned, unsigned> RenameMap;
959 if (FindSuitableFreeRegisters(GroupIndex, RenameOrder, RenameMap)) {
961 <<
printReg(AntiDepReg, TRI) <<
":");
964 for (std::map<unsigned, unsigned>::iterator
965 S = RenameMap.begin(),
E = RenameMap.end(); S !=
E; ++S) {
966 unsigned CurrReg = S->first;
967 unsigned NewReg = S->second;
971 << RegRefs.count(CurrReg) <<
" refs)");
975 for (
const auto &Q :
make_range(RegRefs.equal_range(CurrReg))) {
976 Q.second.Operand->setReg(NewReg);
980 const SUnit *SU = MISUnitMap[Q.second.Operand->getParent()];
990 RegRefs.erase(NewReg);
991 DefIndices[NewReg] = DefIndices[CurrReg];
992 KillIndices[NewReg] = KillIndices[CurrReg];
995 RegRefs.erase(CurrReg);
996 DefIndices[CurrReg] = KillIndices[CurrReg];
997 KillIndices[CurrReg] = ~0u;
998 assert(((KillIndices[CurrReg] == ~0u) !=
999 (DefIndices[CurrReg] == ~0u)) &&
1000 "Kill and Def maps aren't consistent for AntiDepReg!");
1009 ScanInstruction(MI, Count);
BitVector getAllocatableSet(const MachineFunction &MF, const TargetRegisterClass *RC=nullptr) const
Returns a bitset indexed by register number indicating if a register is allocatable or not...
ArrayRef< MCPhysReg > getOrder(const TargetRegisterClass *RC) const
getOrder - Returns the preferred allocation order for RC.
MachineOperand * findRegisterUseOperand(Register Reg, bool isKill=false, const TargetRegisterInfo *TRI=nullptr)
Wrapper for findRegisterUseOperandIdx, it returns a pointer to the MachineOperand rather than an inde...
Information about a register reference within a liverange.
bool isCall(QueryType Type=AnyInBundle) const
bool isAllocatable(unsigned PhysReg) const
isAllocatable - Returns true when PhysReg belongs to an allocatable register class and it hasn't been...
This class represents lattice values for constants.
bool empty() const
empty - Tests whether there are no bits in this bitvector.
bool hasExtraDefRegAllocReq(QueryType Type=AnyInBundle) const
Returns true if this instruction def operands have special register allocation requirements that are ...
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...
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
AggressiveAntiDepState(const unsigned TargetRegs, MachineBasicBlock *BB)
int findRegisterDefOperandIdx(Register Reg, bool isDead=false, bool Overlap=false, const TargetRegisterInfo *TRI=nullptr) const
Returns the operand index that is a def of the specified register or -1 if it is not found...
Optional< std::vector< StOtherPiece > > Other
bool test(unsigned Idx) const
unsigned const TargetRegisterInfo * TRI
unsigned getReg() const
Returns the register associated with this edge.
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.
Kind
These are the different kinds of scheduling dependencies.
SmallVector< SDep, 4 > Preds
All sunit predecessors.
unsigned LeaveGroup(unsigned Reg)
A register anti-dependence (aka WAR).
void StartBlock(MachineBasicBlock *BB) override
Initialize anti-dep breaking for a new basic block.
bool isEarlyClobber() const
const char * getRegClassName(const TargetRegisterClass *Class) const
Returns the name of the register class.
AggressiveAntiDepBreaker(MachineFunction &MFi, const RegisterClassInfo &RCI, TargetSubtargetInfo::RegClassVector &CriticalPathRCs)
bool isReturnBlock() const
Convenience function that returns true if the block ends in a return instruction. ...
unsigned GetGroup(unsigned Reg)
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
const HexagonInstrInfo * TII
This class works in conjunction with the post-RA scheduler to rename registers to break register anti...
unsigned getNumOperands() const
Retuns the total number of operands.
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...
SmallVectorImpl< SDep >::const_iterator const_pred_iterator
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Regular data dependence (aka true-dependence).
~AggressiveAntiDepBreaker() override
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted...
A register output-dependence (aka WAW).
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
unsigned getSubRegIndex(MCRegister RegNo, MCRegister SubRegNo) const
For a given register pair, return the sub-register index if the second register is a sub-register of ...
Register getSubReg(MCRegister Reg, unsigned Idx) const
Returns the physical register number of sub-register "Index" for physical register RegNo...
void GetGroupRegs(unsigned Group, std::vector< unsigned > &Regs, std::multimap< unsigned, AggressiveAntiDepState::RegisterReference > *RegRefs)
unsigned UnionGroups(unsigned Reg1, unsigned Reg2)
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
initializer< Ty > init(const Ty &Val)
std::vector< std::pair< MachineInstr *, MachineInstr * > > DbgValueVector
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
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...
unsigned const MachineRegisterInfo * MRI
unsigned short Latency
Node latency.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
MachineInstrBuilder & UseMI
size_t size() const
size - Get the array size.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
bool any() const
any - Returns true if any bit is set.
void FinishBlock() override
Finish anti-dep breaking for a basic block.
MCRegAliasIterator enumerates all registers aliasing Reg.
bool isSuperRegister(MCRegister RegA, MCRegister RegB) const
Returns true if RegB is a super-register of RegA.
static const SUnit * CriticalPathStep(const SUnit *SU)
CriticalPathStep - Return the next SUnit after SU on the bottom-up critical path. ...
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
succ_iterator succ_begin()
void Observe(MachineInstr &MI, unsigned Count, unsigned InsertPosIndex) override
Update liveness information to account for the current instruction, which will not be scheduled...
MCSubRegIterator enumerates all sub-registers of Reg.
virtual bool isPredicated(const MachineInstr &MI) const
Returns true if the instruction is already predicated.
bool isDebugInstr() const
MachineOperand * findRegisterDefOperand(Register Reg, bool isDead=false, bool Overlap=false, const TargetRegisterInfo *TRI=nullptr)
Wrapper for findRegisterDefOperandIdx, it returns a pointer to the MachineOperand rather than an inde...
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
bool readsRegister(Register Reg, const TargetRegisterInfo *TRI=nullptr) const
Return true if the MachineInstr reads the specified register.
MachineOperand class - Representation of each machine instruction operand.
MachineInstrBuilder MachineInstrBuilder & DefMI
std::vector< unsigned > & GetDefIndices()
Return the define indices.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool isSubRegister(MCRegister RegA, MCRegister RegB) const
Returns true if RegB is a sub-register of RegA.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
const MachineBasicBlock * getParent() const
bool none() const
none - Returns true if none of the bits are set.
Representation of each machine instruction.
std::multimap< unsigned, RegisterReference > & GetRegRefs()
Return the RegRefs map.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
bool hasExtraSrcRegAllocReq(QueryType Type=AnyInBundle) const
Returns true if this instruction source operands have special register allocation requirements that a...
Kind getKind() const
Returns an enum value representing the kind of the dependence.
bool isRegTiedToUseOperand(unsigned DefOpIdx, unsigned *UseOpIdx=nullptr) const
Given the index of a register def operand, check if the register def is tied to a source operand...
static cl::opt< int > DebugDiv("agg-antidep-debugdiv", cl::desc("Debug control for aggressive anti-dep breaker"), cl::init(0), cl::Hidden)
const TargetRegisterClass * getMinimalPhysRegClass(unsigned Reg, MVT VT=MVT::Other) const
Returns the Register Class of a physical register of the given type, picking the most sub register cl...
bool isReg() const
isReg - Tests if this is a MO_Register operand.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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...
static void AntiDepEdges(const SUnit *SU, std::vector< const SDep *> &Edges)
AntiDepEdges - Return in Edges the anti- and output- dependencies in SU that we want to consider for ...
iterator_range< const_set_bits_iterator > set_bits() const
SmallVector< SDep, 4 > Succs
All sunit successors.
const MCPhysReg * getCalleeSavedRegs() const
Returns list of callee saved registers.
BitVector getPristineRegs(const MachineFunction &MF) const
Return a set of physical registers that are pristine.
Contains all the state necessary for anti-dep breaking.
Register getReg() const
getReg - Returns the register number.
static cl::opt< int > DebugMod("agg-antidep-debugmod", cl::desc("Debug control for aggressive anti-dep breaker"), cl::init(0), cl::Hidden)
const MachineOperand & getOperand(unsigned i) const
bool IsLive(unsigned Reg)
Return true if Reg is live.
std::vector< unsigned > & GetKillIndices()
Return the kill indices.
std::vector< MachineBasicBlock * >::iterator succ_iterator
Scheduling unit. This is a node in the scheduling DAG.
Wrapper class representing virtual and physical registers.
bool empty() const
empty - Check if the array is empty.