47 #define DEBUG_TYPE "post-RA-sched" 52 cl::desc(
"Debug control for aggressive anti-dep breaker"),
57 cl::desc(
"Debug control for aggressive anti-dep breaker"),
62 : NumTargetRegs(TargetRegs), GroupNodes(TargetRegs, 0),
63 GroupNodeIndices(TargetRegs, 0), KillIndices(TargetRegs, 0),
64 DefIndices(TargetRegs, 0) {
65 const unsigned BBSize = BB->
size();
66 for (
unsigned i = 0; i < NumTargetRegs; ++i) {
69 GroupNodeIndices[i] = i;
72 DefIndices[i] = BBSize;
77 unsigned Node = GroupNodeIndices[
Reg];
78 while (GroupNodes[Node] != Node)
79 Node = GroupNodes[Node];
86 std::vector<unsigned> &Regs,
87 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference> *RegRefs)
89 for (
unsigned Reg = 0;
Reg != NumTargetRegs; ++
Reg) {
96 assert(GroupNodes[0] == 0 &&
"GroupNode 0 not parent!");
97 assert(GroupNodeIndices[0] == 0 &&
"Reg 0 not in Group 0!");
104 unsigned Parent = (Group1 == 0) ? Group1 : Group2;
105 unsigned Other = (Parent == Group1) ? Group2 : Group1;
106 GroupNodes.at(Other) = Parent;
114 unsigned idx = GroupNodes.size();
115 GroupNodes.push_back(idx);
116 GroupNodeIndices[
Reg] = idx;
123 return((KillIndices[Reg] != ~0u) && (DefIndices[Reg] == ~0u));
130 TII(MF.getSubtarget().getInstrInfo()),
131 TRI(MF.getSubtarget().getRegisterInfo()), RegClassInfo(RCI) {
134 for (
unsigned i = 0, e = CriticalPathRCs.
size(); i < e; ++i) {
136 if (CriticalPathSet.
none())
137 CriticalPathSet = CPSet;
139 CriticalPathSet |= CPSet;
164 for (
const auto &LI : (*SI)->liveins()) {
169 DefIndices[
Reg] = ~0u;
181 if (!IsReturnBlock && !Pristine.
test(Reg))
184 unsigned AliasReg = *AI;
186 KillIndices[AliasReg] = BB->
size();
187 DefIndices[AliasReg] = ~0u;
198 unsigned InsertPosIndex) {
199 assert(Count < InsertPosIndex &&
"Instruction index out of expected range!");
201 std::set<unsigned> PassthruRegs;
202 GetPassthruRegs(MI, PassthruRegs);
203 PrescanInstruction(MI, Count, PassthruRegs);
204 ScanInstruction(MI, Count);
221 <<
"->g0(region live-out)");
223 }
else if ((DefIndices[
Reg] < InsertPosIndex)
224 && (DefIndices[
Reg] >= Count)) {
225 DefIndices[
Reg] = Count;
249 void AggressiveAntiDepBreaker::GetPassthruRegs(
253 if (!MO.
isReg())
continue;
255 IsImplicitDefUse(MI, MO)) {
259 PassthruRegs.insert(*SubRegs);
272 Edges.push_back(&*
P);
280 const SDep *Next =
nullptr;
281 unsigned NextDepth = 0;
286 const SUnit *PredSU =
P->getSUnit();
287 unsigned PredLatency =
P->getLatency();
288 unsigned PredTotalLatency = PredSU->
getDepth() + PredLatency;
291 if (NextDepth < PredTotalLatency ||
292 (NextDepth == PredTotalLatency &&
P->getKind() ==
SDep::Anti)) {
293 NextDepth = PredTotalLatency;
299 return (Next) ? Next->
getSUnit() :
nullptr;
302 void AggressiveAntiDepBreaker::HandleLastUse(
unsigned Reg,
unsigned KillIdx,
305 const char *footer) {
308 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
321 if (!State->
IsLive(Reg)) {
322 KillIndices[
Reg] = KillIdx;
323 DefIndices[
Reg] = ~0u;
336 unsigned SubregReg = *SubRegs;
337 if (!State->
IsLive(SubregReg)) {
338 KillIndices[SubregReg] = KillIdx;
339 DefIndices[SubregReg] = ~0u;
340 RegRefs.erase(SubregReg);
347 << State->
GetGroup(SubregReg) << tag);
355 void AggressiveAntiDepBreaker::PrescanInstruction(
356 MachineInstr &MI,
unsigned Count, std::set<unsigned> &PassthruRegs) {
358 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
369 unsigned Reg = MO.
getReg();
370 if (Reg == 0)
continue;
372 HandleLastUse(Reg, Count + 1,
"",
"\tDead Def: ",
"\n");
379 unsigned Reg = MO.
getReg();
380 if (Reg == 0)
continue;
399 unsigned AliasReg = *AI;
400 if (State->
IsLive(AliasReg)) {
412 RegRefs.insert(std::make_pair(Reg, RR));
422 unsigned Reg = MO.
getReg();
423 if (Reg == 0)
continue;
425 if (MI.
isKill() || (PassthruRegs.count(Reg) != 0))
439 DefIndices[*AI] = Count;
444 void AggressiveAntiDepBreaker::ScanInstruction(
MachineInstr &MI,
447 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
475 unsigned Reg = MO.
getReg();
476 if (Reg == 0)
continue;
484 HandleLastUse(Reg, Count,
"(last-use)");
496 RegRefs.insert(std::make_pair(Reg, RR));
506 unsigned FirstReg = 0;
509 if (!MO.
isReg())
continue;
510 unsigned Reg = MO.
getReg();
511 if (Reg == 0)
continue;
526 BitVector AggressiveAntiDepBreaker::GetRenameRegisters(
unsigned Reg) {
551 bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters(
552 unsigned AntiDepGroupIndex,
553 RenameOrderType& RenameOrder,
554 std::map<unsigned, unsigned> &RenameMap) {
557 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
563 std::vector<unsigned> Regs;
565 assert(!Regs.empty() &&
"Empty register group!");
572 LLVM_DEBUG(
dbgs() <<
"\tRename Candidates for Group g" << AntiDepGroupIndex
574 std::map<unsigned, BitVector> RenameRegisterMap;
575 unsigned SuperReg = 0;
576 for (
unsigned i = 0, e = Regs.size(); i != e; ++i) {
577 unsigned Reg = Regs[i];
582 if (RegRefs.count(Reg) > 0) {
587 BV = GetRenameRegisters(Reg);
591 for (
unsigned r : BV.set_bits())
599 for (
unsigned i = 0, e = Regs.size(); i != e; ++i) {
600 unsigned Reg = Regs[i];
601 if (Reg == SuperReg)
continue;
613 static int renamecnt = 0;
617 dbgs() <<
"*** Performing rename " <<
printReg(SuperReg, TRI)
618 <<
" for debug ***\n";
641 RenameOrder.insert(RenameOrderType::value_type(SuperRC, Order.
size()));
643 unsigned OrigR = RenameOrder[SuperRC];
644 unsigned EndR = ((OrigR == Order.
size()) ? 0 : OrigR);
647 if (R == 0) R = Order.
size();
649 const unsigned NewSuperReg = Order[R];
653 if (NewSuperReg == SuperReg)
continue;
661 for (
unsigned i = 0, e = Regs.size(); i != e; ++i) {
662 unsigned Reg = Regs[i];
664 if (Reg == SuperReg) {
665 NewReg = NewSuperReg;
668 if (NewSubRegIdx != 0)
669 NewReg = TRI->
getSubReg(NewSuperReg, NewSubRegIdx);
675 if (!RenameRegisterMap[Reg].test(NewReg)) {
684 if (State->
IsLive(NewReg) || (KillIndices[
Reg] > DefIndices[NewReg])) {
690 unsigned AliasReg = *AI;
691 if (State->
IsLive(AliasReg) ||
692 (KillIndices[
Reg] > DefIndices[AliasReg])) {
694 <<
"(alias " <<
printReg(AliasReg, TRI) <<
" live)");
705 for (
const auto &Q :
make_range(RegRefs.equal_range(Reg))) {
720 for (
const auto &Q :
make_range(RegRefs.equal_range(Reg))) {
721 if (!Q.second.Operand->isDef() || !Q.second.Operand->isEarlyClobber())
732 RenameMap.insert(std::pair<unsigned, unsigned>(Reg, NewReg));
737 RenameOrder.erase(SuperRC);
738 RenameOrder.insert(RenameOrderType::value_type(SuperRC, R));
755 const std::vector<SUnit> &SUnits,
758 unsigned InsertPosIndex,
762 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
767 if (SUnits.empty())
return 0;
770 RenameOrderType RenameOrder;
773 std::map<MachineInstr *, const SUnit *> MISUnitMap;
774 for (
unsigned i = 0, e = SUnits.size(); i != e; ++i) {
775 const SUnit *SU = &SUnits[i];
776 MISUnitMap.insert(std::pair<MachineInstr *, const SUnit *>(SU->
getInstr(),
783 const SUnit *CriticalPathSU =
nullptr;
785 if (CriticalPathSet.
any()) {
786 for (
unsigned i = 0, e = SUnits.size(); i != e; ++i) {
787 const SUnit *SU = &SUnits[i];
788 if (!CriticalPathSU ||
795 CriticalPathMI = CriticalPathSU->
getInstr();
799 LLVM_DEBUG(
dbgs() <<
"\n===== Aggressive anti-dependency breaking\n");
814 unsigned Count = InsertPosIndex - 1;
825 std::set<unsigned> PassthruRegs;
826 GetPassthruRegs(MI, PassthruRegs);
829 PrescanInstruction(MI, Count, PassthruRegs);
833 std::vector<const SDep *> Edges;
834 const SUnit *PathSU = MISUnitMap[&
MI];
840 if (&MI == CriticalPathMI) {
842 CriticalPathMI = (CriticalPathSU) ? CriticalPathSU->
getInstr() :
nullptr;
843 }
else if (CriticalPathSet.
any()) {
844 ExcludeRegs = &CriticalPathSet;
851 for (
unsigned i = 0, e = Edges.size(); i != e; ++i) {
852 const SDep *Edge = Edges[i];
858 unsigned AntiDepReg = Edge->
getReg();
860 assert(AntiDepReg != 0 &&
"Anti-dependence on reg0?");
866 }
else if (ExcludeRegs && ExcludeRegs->
test(AntiDepReg)) {
871 }
else if (PassthruRegs.count(AntiDepReg) != 0) {
880 assert(AntiDepOp &&
"Can't find index for defined register operand");
896 PE = PathSU->
Preds.end();
P != PE; ++
P) {
897 if (
P->getSUnit() == NextSU ?
898 (
P->getKind() !=
SDep::Anti ||
P->getReg() != AntiDepReg) :
899 (
P->getKind() ==
SDep::Data &&
P->getReg() == AntiDepReg)) {
905 PE = PathSU->
Preds.end();
P != PE; ++
P) {
906 if ((
P->getSUnit() == NextSU) && (
P->getKind() !=
SDep::Anti) &&
911 }
else if ((
P->getSUnit() != NextSU) &&
913 (
P->getReg() == AntiDepReg)) {
920 if (AntiDepReg == 0)
continue;
943 if (AntiDepReg == 0)
continue;
947 if (AntiDepReg == 0)
continue;
950 const unsigned GroupIndex = State->
GetGroup(AntiDepReg);
951 if (GroupIndex == 0) {
959 std::map<unsigned, unsigned> RenameMap;
960 if (FindSuitableFreeRegisters(GroupIndex, RenameOrder, RenameMap)) {
962 <<
printReg(AntiDepReg, TRI) <<
":");
965 for (std::map<unsigned, unsigned>::iterator
966 S = RenameMap.begin(),
E = RenameMap.end(); S !=
E; ++S) {
967 unsigned CurrReg = S->first;
968 unsigned NewReg = S->second;
972 << RegRefs.count(CurrReg) <<
" refs)");
976 for (
const auto &Q :
make_range(RegRefs.equal_range(CurrReg))) {
977 Q.second.Operand->setReg(NewReg);
981 const SUnit *SU = MISUnitMap[Q.second.Operand->getParent()];
991 RegRefs.erase(NewReg);
992 DefIndices[NewReg] = DefIndices[CurrReg];
993 KillIndices[NewReg] = KillIndices[CurrReg];
996 RegRefs.erase(CurrReg);
997 DefIndices[CurrReg] = KillIndices[CurrReg];
998 KillIndices[CurrReg] = ~0u;
999 assert(((KillIndices[CurrReg] == ~0u) !=
1000 (DefIndices[CurrReg] == ~0u)) &&
1001 "Kill and Def maps aren't consistent for AntiDepReg!");
1010 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.
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.
MachineOperand * findRegisterDefOperand(unsigned Reg, bool isDead=false, const TargetRegisterInfo *TRI=nullptr)
Wrapper for findRegisterDefOperandIdx, it returns a pointer to the MachineOperand rather than an inde...
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 getSubRegIndex(unsigned RegNo, unsigned SubRegNo) const
For a given register pair, return the sub-register index if the second register is a sub-register of ...
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)
unsigned getReg() const
getReg - Returns the register number.
MachineOperand * findRegisterUseOperand(unsigned Reg, bool isKill=false, const TargetRegisterInfo *TRI=nullptr)
Wrapper for findRegisterUseOperandIdx, it returns a pointer to the MachineOperand rather than an inde...
bool test(unsigned Idx) const
unsigned const TargetRegisterInfo * TRI
unsigned getReg() const
Returns the register associated with this edge.
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.
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...
Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
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).
bool isSubRegister(unsigned RegA, unsigned RegB) const
Returns true if RegB is a sub-register of RegA.
~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.
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...
bool isSuperRegister(unsigned RegA, unsigned RegB) const
Returns true if RegB is a super-register of RegA.
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.
unsigned getSubReg(unsigned Reg, unsigned Idx) const
Returns the physical register number of sub-register "Index" for physical register RegNo...
void FinishBlock() override
Finish anti-dep breaking for a basic block.
MCRegAliasIterator enumerates all registers aliasing Reg.
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
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
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 isValid() const
isValid - returns true if this iterator is not yet at the end.
int findRegisterDefOperandIdx(unsigned 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...
bool readsRegister(unsigned Reg, const TargetRegisterInfo *TRI=nullptr) const
Return true if the MachineInstr reads the specified register.
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.
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.
bool empty() const
empty - Check if the array is empty.