41#define DEBUG_TYPE "post-RA-sched"
46 cl::desc(
"Debug control for aggressive anti-dep breaker"),
51 cl::desc(
"Debug control for aggressive anti-dep breaker"),
56 : NumTargetRegs(TargetRegs), GroupNodes(TargetRegs, 0),
57 GroupNodeIndices(TargetRegs, 0), KillIndices(TargetRegs, 0),
58 DefIndices(TargetRegs, 0) {
59 const unsigned BBSize = BB->
size();
60 for (
unsigned i = 0; i < NumTargetRegs; ++i) {
63 GroupNodeIndices[i] = i;
66 DefIndices[i] = BBSize;
71 unsigned Node = GroupNodeIndices[Reg];
72 while (GroupNodes[Node] != Node)
73 Node = GroupNodes[Node];
80 std::vector<unsigned> &Regs,
81 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference> *RegRefs)
83 for (
unsigned Reg = 0; Reg != NumTargetRegs; ++Reg) {
84 if ((
GetGroup(Reg) == Group) && (RegRefs->count(Reg) > 0))
90 assert(GroupNodes[0] == 0 &&
"GroupNode 0 not parent!");
91 assert(GroupNodeIndices[0] == 0 &&
"Reg 0 not in Group 0!");
98 unsigned Parent = (Group1 == 0) ? Group1 : Group2;
99 unsigned Other = (Parent == Group1) ? Group2 : Group1;
100 GroupNodes.at(
Other) = Parent;
108 unsigned idx = GroupNodes.size();
109 GroupNodes.push_back(idx);
110 GroupNodeIndices[Reg] = idx;
117 return((KillIndices[Reg] != ~0u) && (DefIndices[Reg] == ~0u));
123 : MF(MFi),
MRI(MF.getRegInfo()),
TII(MF.getSubtarget().getInstrInfo()),
124 TRI(MF.getSubtarget().getRegisterInfo()), RegClassInfo(RCI) {
127 for (
unsigned i = 0, e = CriticalPathRCs.
size(); i < e; ++i) {
129 if (CriticalPathSet.
none())
130 CriticalPathSet = CPSet;
132 CriticalPathSet |= CPSet;
156 for (
const auto &LI : Succ->liveins()) {
160 KillIndices[Reg] = BB->
size();
161 DefIndices[Reg] = ~0u;
173 if (!IsReturnBlock && !Pristine.
test(Reg))
176 unsigned AliasReg = *AI;
178 KillIndices[AliasReg] = BB->
size();
179 DefIndices[AliasReg] = ~0u;
190 unsigned InsertPosIndex) {
191 assert(Count < InsertPosIndex &&
"Instruction index out of expected range!");
193 std::set<unsigned> PassthruRegs;
194 GetPassthruRegs(
MI, PassthruRegs);
195 PrescanInstruction(
MI, Count, PassthruRegs);
196 ScanInstruction(
MI, Count);
203 for (
unsigned Reg = 0; Reg != TRI->
getNumRegs(); ++Reg) {
213 <<
"->g0(region live-out)");
215 }
else if ((DefIndices[Reg] < InsertPosIndex)
216 && (DefIndices[Reg] >= Count)) {
217 DefIndices[Reg] = Count;
234 Op =
MI.findRegisterUseOperand(Reg,
true);
236 Op =
MI.findRegisterDefOperand(Reg);
238 return(Op && Op->isImplicit());
241void AggressiveAntiDepBreaker::GetPassthruRegs(
243 for (
unsigned i = 0, e =
MI.getNumOperands(); i != e; ++i) {
245 if (!MO.
isReg())
continue;
246 if ((MO.
isDef() &&
MI.isRegTiedToUseOperand(i)) ||
247 IsImplicitDefUse(
MI, MO)) {
251 PassthruRegs.insert(*SubRegs);
263 Edges.push_back(&Pred);
271 const SDep *Next =
nullptr;
272 unsigned NextDepth = 0;
278 unsigned PredTotalLatency = PredSU->
getDepth() + PredLatency;
281 if (NextDepth < PredTotalLatency ||
283 NextDepth = PredTotalLatency;
289 return (Next) ? Next->
getSUnit() :
nullptr;
292void AggressiveAntiDepBreaker::HandleLastUse(
unsigned Reg,
unsigned KillIdx,
295 const char *footer) {
298 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
311 if (!State->
IsLive(Reg)) {
312 KillIndices[
Reg] = KillIdx;
313 DefIndices[
Reg] = ~0
u;
326 unsigned SubregReg = *SubRegs;
327 if (!State->
IsLive(SubregReg)) {
328 KillIndices[SubregReg] = KillIdx;
329 DefIndices[SubregReg] = ~0
u;
330 RegRefs.erase(SubregReg);
337 << State->
GetGroup(SubregReg) << tag);
345void AggressiveAntiDepBreaker::PrescanInstruction(
346 MachineInstr &
MI,
unsigned Count, std::set<unsigned> &PassthruRegs) {
348 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
359 if (Reg == 0)
continue;
361 HandleLastUse(Reg, Count + 1,
"",
"\tDead Def: ",
"\n");
365 for (
unsigned i = 0, e =
MI.getNumOperands(); i != e; ++i) {
369 if (Reg == 0)
continue;
388 unsigned AliasReg = *AI;
389 if (State->
IsLive(AliasReg)) {
398 if (i <
MI.getDesc().getNumOperands())
401 RegRefs.insert(std::make_pair(Reg, RR));
411 if (Reg == 0)
continue;
413 if (
MI.isKill() || (PassthruRegs.count(Reg) != 0))
427 DefIndices[*AI] = Count;
435 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
455 bool Special =
MI.isCall() ||
MI.hasExtraSrcRegAllocReq() ||
460 for (
unsigned i = 0, e =
MI.getNumOperands(); i != e; ++i) {
464 if (Reg == 0)
continue;
472 HandleLastUse(Reg, Count,
"(last-use)");
481 if (i <
MI.getDesc().getNumOperands())
484 RegRefs.insert(std::make_pair(Reg, RR));
494 unsigned FirstReg = 0;
496 if (!MO.
isReg())
continue;
498 if (Reg == 0)
continue;
513BitVector AggressiveAntiDepBreaker::GetRenameRegisters(
unsigned Reg) {
538bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters(
539 unsigned AntiDepGroupIndex,
540 RenameOrderType& RenameOrder,
541 std::map<unsigned, unsigned> &RenameMap) {
544 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
550 std::vector<unsigned> Regs;
552 assert(!Regs.empty() &&
"Empty register group!");
559 LLVM_DEBUG(
dbgs() <<
"\tRename Candidates for Group g" << AntiDepGroupIndex
561 std::map<unsigned, BitVector> RenameRegisterMap;
562 unsigned SuperReg = 0;
563 for (
unsigned Reg : Regs) {
568 if (RegRefs.count(Reg) > 0) {
573 BV = GetRenameRegisters(Reg);
585 for (
unsigned Reg : Regs) {
586 if (Reg == SuperReg)
continue;
598 static int renamecnt = 0;
602 dbgs() <<
"*** Performing rename " <<
printReg(SuperReg, TRI)
603 <<
" for debug ***\n";
626 RenameOrder.insert(RenameOrderType::value_type(SuperRC, Order.
size()));
628 unsigned OrigR = RenameOrder[SuperRC];
629 unsigned EndR = ((OrigR == Order.
size()) ? 0 : OrigR);
632 if (R == 0)
R = Order.
size();
634 const unsigned NewSuperReg = Order[
R];
638 if (NewSuperReg == SuperReg)
continue;
646 for (
unsigned Reg : Regs) {
648 if (Reg == SuperReg) {
649 NewReg = NewSuperReg;
652 if (NewSubRegIdx != 0)
653 NewReg = TRI->
getSubReg(NewSuperReg, NewSubRegIdx);
659 if (!RenameRegisterMap[Reg].
test(NewReg)) {
668 if (State->
IsLive(NewReg) || (KillIndices[Reg] > DefIndices[NewReg])) {
674 unsigned AliasReg = *AI;
675 if (State->
IsLive(AliasReg) ||
676 (KillIndices[Reg] > DefIndices[AliasReg])) {
678 <<
"(alias " <<
printReg(AliasReg, TRI) <<
" live)");
689 for (
const auto &Q :
make_range(RegRefs.equal_range(Reg))) {
704 for (
const auto &Q :
make_range(RegRefs.equal_range(Reg))) {
705 if (!Q.second.Operand->isDef() || !Q.second.Operand->isEarlyClobber())
716 RenameMap.insert(std::pair<unsigned, unsigned>(Reg, NewReg));
721 RenameOrder.erase(SuperRC);
722 RenameOrder.insert(RenameOrderType::value_type(SuperRC, R));
739 const std::vector<SUnit> &SUnits,
742 unsigned InsertPosIndex,
746 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
751 if (SUnits.empty())
return 0;
754 RenameOrderType RenameOrder;
757 std::map<MachineInstr *, const SUnit *> MISUnitMap;
758 for (
const SUnit &SU : SUnits)
759 MISUnitMap.insert(std::make_pair(SU.getInstr(), &SU));
764 const SUnit *CriticalPathSU =
nullptr;
766 if (CriticalPathSet.
any()) {
767 for (
const SUnit &SU : SUnits) {
768 if (!CriticalPathSU ||
769 ((SU.getDepth() + SU.Latency) >
771 CriticalPathSU = &SU;
774 assert(CriticalPathSU &&
"Failed to find SUnit critical path");
775 CriticalPathMI = CriticalPathSU->
getInstr();
779 LLVM_DEBUG(
dbgs() <<
"\n===== Aggressive anti-dependency breaking\n");
781 for (
unsigned Reg = 0; Reg < TRI->
getNumRegs(); ++Reg) {
794 unsigned Count = InsertPosIndex - 1;
799 if (
MI.isDebugInstr())
805 std::set<unsigned> PassthruRegs;
806 GetPassthruRegs(
MI, PassthruRegs);
809 PrescanInstruction(
MI, Count, PassthruRegs);
813 std::vector<const SDep *> Edges;
814 const SUnit *PathSU = MISUnitMap[&
MI];
820 if (&
MI == CriticalPathMI) {
822 CriticalPathMI = (CriticalPathSU) ? CriticalPathSU->
getInstr() :
nullptr;
823 }
else if (CriticalPathSet.
any()) {
824 ExcludeRegs = &CriticalPathSet;
831 for (
const SDep *Edge : Edges) {
832 SUnit *NextSU = Edge->getSUnit();
837 unsigned AntiDepReg = Edge->getReg();
839 assert(AntiDepReg != 0 &&
"Anti-dependence on reg0?");
845 }
else if (ExcludeRegs && ExcludeRegs->
test(AntiDepReg)) {
850 }
else if (PassthruRegs.count(AntiDepReg) != 0) {
859 assert(AntiDepOp &&
"Can't find index for defined register operand");
876 Pred.
getReg() != AntiDepReg)
878 Pred.
getReg() == AntiDepReg)) {
889 }
else if ((Pred.
getSUnit() != NextSU) &&
891 (Pred.
getReg() == AntiDepReg)) {
898 if (AntiDepReg == 0)
continue;
921 if (AntiDepReg == 0)
continue;
925 if (AntiDepReg == 0)
continue;
928 const unsigned GroupIndex = State->
GetGroup(AntiDepReg);
929 if (GroupIndex == 0) {
937 std::map<unsigned, unsigned> RenameMap;
938 if (FindSuitableFreeRegisters(GroupIndex, RenameOrder, RenameMap)) {
940 <<
printReg(AntiDepReg, TRI) <<
":");
943 for (
const auto &
P : RenameMap) {
944 unsigned CurrReg =
P.first;
945 unsigned NewReg =
P.second;
949 << RegRefs.count(CurrReg) <<
" refs)");
953 for (
const auto &Q :
make_range(RegRefs.equal_range(CurrReg))) {
954 Q.second.Operand->setReg(NewReg);
958 const SUnit *SU = MISUnitMap[Q.second.Operand->getParent()];
968 RegRefs.erase(NewReg);
969 DefIndices[NewReg] = DefIndices[CurrReg];
970 KillIndices[NewReg] = KillIndices[CurrReg];
973 RegRefs.erase(CurrReg);
974 DefIndices[CurrReg] = KillIndices[CurrReg];
975 KillIndices[CurrReg] = ~0u;
976 assert(((KillIndices[CurrReg] == ~0u) !=
977 (DefIndices[CurrReg] == ~0u)) &&
978 "Kill and Def maps aren't consistent for AntiDepReg!");
987 ScanInstruction(
MI, Count);
unsigned const MachineRegisterInfo * MRI
MachineInstrBuilder & UseMI
MachineInstrBuilder MachineInstrBuilder & DefMI
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 ...
static const SUnit * CriticalPathStep(const SUnit *SU)
CriticalPathStep - Return the next SUnit after SU on the bottom-up critical path.
static cl::opt< int > DebugDiv("agg-antidep-debugdiv", cl::desc("Debug control for aggressive anti-dep breaker"), cl::init(0), cl::Hidden)
static cl::opt< int > DebugMod("agg-antidep-debugmod", cl::desc("Debug control for aggressive anti-dep breaker"), cl::init(0), cl::Hidden)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
const HexagonInstrInfo * TII
unsigned const TargetRegisterInfo * TRI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallSet class.
void Observe(MachineInstr &MI, unsigned Count, unsigned InsertPosIndex) override
Update liveness information to account for the current instruction, which will not be scheduled.
void FinishBlock() override
Finish anti-dep breaking for a basic block.
~AggressiveAntiDepBreaker() 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 StartBlock(MachineBasicBlock *BB) override
Initialize anti-dep breaking for a new basic block.
AggressiveAntiDepBreaker(MachineFunction &MFi, const RegisterClassInfo &RCI, TargetSubtargetInfo::RegClassVector &CriticalPathRCs)
Contains all the state necessary for anti-dep breaking.
AggressiveAntiDepState(const unsigned TargetRegs, MachineBasicBlock *BB)
void GetGroupRegs(unsigned Group, std::vector< unsigned > &Regs, std::multimap< unsigned, AggressiveAntiDepState::RegisterReference > *RegRefs)
std::vector< unsigned > & GetDefIndices()
Return the define indices.
unsigned LeaveGroup(unsigned Reg)
unsigned GetGroup(unsigned Reg)
std::multimap< unsigned, RegisterReference > & GetRegRefs()
Return the RegRefs map.
bool IsLive(unsigned Reg)
Return true if Reg is live.
unsigned UnionGroups(unsigned Reg1, unsigned Reg2)
std::vector< unsigned > & GetKillIndices()
Return the kill indices.
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),...
size_t size() const
size - Get the array size.
bool empty() const
empty - Check if the array is empty.
bool test(unsigned Idx) const
bool any() const
any - Returns true if any bit is set.
bool none() const
none - Returns true if none of the bits are set.
iterator_range< const_set_bits_iterator > set_bits() const
bool empty() const
empty - Tests whether there are no bits in this bitvector.
MCRegAliasIterator enumerates all registers aliasing Reg.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
bool isSubRegister(MCRegister RegA, MCRegister RegB) const
Returns true if RegB is a sub-register of RegA.
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 ...
bool isSuperRegister(MCRegister RegA, MCRegister 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...
MCSubRegIterator enumerates all sub-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.
const MachineBasicBlock * getParent() const
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.
bool readsRegister(Register Reg, const TargetRegisterInfo *TRI=nullptr) const
Return true if the MachineInstr reads the specified register.
const MachineOperand & getOperand(unsigned i) const
MachineOperand class - Representation of each machine instruction operand.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool isEarlyClobber() const
Register getReg() const
getReg - Returns the register number.
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.
Kind getKind() const
Returns an enum value representing the kind of the dependence.
Kind
These are the different kinds of scheduling dependencies.
@ Output
A register output-dependence (aka WAW).
@ Anti
A register anti-dependence (aka WAR).
@ Data
Regular data dependence (aka true-dependence).
unsigned getLatency() const
Returns the latency value for this edge, which roughly means the minimum number of cycles that must e...
unsigned getReg() const
Returns the register associated with this edge.
Scheduling unit. This is a node in the scheduling DAG.
unsigned short Latency
Node latency.
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 > Succs
All sunit successors.
SmallVector< SDep, 4 > Preds
All sunit predecessors.
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
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,...
const TargetRegisterClass * getMinimalPhysRegClass(MCRegister Reg, MVT VT=MVT::Other) const
Returns the Register Class of a physical register of the given type, picking the most sub register cl...
MCRegister getSubReg(MCRegister Reg, unsigned Idx) const
Returns the physical register number of sub-register "Index" for physical register RegNo.
const char * getRegClassName(const TargetRegisterClass *Class) const
Returns the name of the register class.
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.
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
Reg
All possible values of the reg field in the ModR/M byte.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
AntiDepBreaker * createAggressiveAntiDepBreaker(MachineFunction &MFi, const RegisterClassInfo &RCI, TargetSubtargetInfo::RegClassVector &CriticalPathRCs)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
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.
Information about a register reference within a liverange.