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 = 1; 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)) {
250 PassthruRegs.insert(
SubReg);
262 Edges.push_back(&Pred);
270 const SDep *Next =
nullptr;
271 unsigned NextDepth = 0;
277 unsigned PredTotalLatency = PredSU->
getDepth() + PredLatency;
280 if (NextDepth < PredTotalLatency ||
282 NextDepth = PredTotalLatency;
288 return (Next) ? Next->
getSUnit() :
nullptr;
291void AggressiveAntiDepBreaker::HandleLastUse(
unsigned Reg,
unsigned KillIdx,
294 const char *footer) {
297 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
310 if (!State->
IsLive(Reg)) {
311 KillIndices[
Reg] = KillIdx;
312 DefIndices[
Reg] = ~0
u;
325 if (!State->
IsLive(SubregReg)) {
326 KillIndices[SubregReg] = KillIdx;
327 DefIndices[SubregReg] = ~0
u;
328 RegRefs.erase(SubregReg);
335 << State->
GetGroup(SubregReg) << tag);
343void AggressiveAntiDepBreaker::PrescanInstruction(
344 MachineInstr &
MI,
unsigned Count, std::set<unsigned> &PassthruRegs) {
346 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
356 if (Reg == 0)
continue;
358 HandleLastUse(Reg, Count + 1,
"",
"\tDead Def: ",
"\n");
362 for (
unsigned i = 0, e =
MI.getNumOperands(); i != e; ++i) {
366 if (Reg == 0)
continue;
385 unsigned AliasReg = *AI;
386 if (State->
IsLive(AliasReg)) {
395 if (i <
MI.getDesc().getNumOperands())
398 RegRefs.insert(std::make_pair(Reg, RR));
408 if (Reg == 0)
continue;
410 if (
MI.isKill() || (PassthruRegs.count(Reg) != 0))
424 DefIndices[*AI] = Count;
432 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
452 bool Special =
MI.isCall() ||
MI.hasExtraSrcRegAllocReq() ||
457 for (
unsigned i = 0, e =
MI.getNumOperands(); i != e; ++i) {
461 if (Reg == 0)
continue;
469 HandleLastUse(Reg, Count,
"(last-use)");
478 if (i <
MI.getDesc().getNumOperands())
481 RegRefs.insert(std::make_pair(Reg, RR));
491 unsigned FirstReg = 0;
493 if (!MO.
isReg())
continue;
495 if (Reg == 0)
continue;
510BitVector AggressiveAntiDepBreaker::GetRenameRegisters(
unsigned Reg) {
535bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters(
536 unsigned AntiDepGroupIndex,
537 RenameOrderType& RenameOrder,
538 std::map<unsigned, unsigned> &RenameMap) {
541 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
547 std::vector<unsigned> Regs;
549 assert(!Regs.empty() &&
"Empty register group!");
556 LLVM_DEBUG(
dbgs() <<
"\tRename Candidates for Group g" << AntiDepGroupIndex
558 std::map<unsigned, BitVector> RenameRegisterMap;
559 unsigned SuperReg = 0;
560 for (
unsigned Reg : Regs) {
565 if (RegRefs.count(Reg) > 0) {
570 BV = GetRenameRegisters(Reg);
582 for (
unsigned Reg : Regs) {
583 if (Reg == SuperReg)
continue;
595 static int renamecnt = 0;
599 dbgs() <<
"*** Performing rename " <<
printReg(SuperReg, TRI)
600 <<
" for debug ***\n";
623 RenameOrder.insert(RenameOrderType::value_type(SuperRC, Order.
size()));
625 unsigned OrigR = RenameOrder[SuperRC];
626 unsigned EndR = ((OrigR == Order.
size()) ? 0 : OrigR);
629 if (R == 0)
R = Order.
size();
631 const unsigned NewSuperReg = Order[
R];
635 if (NewSuperReg == SuperReg)
continue;
643 for (
unsigned Reg : Regs) {
645 if (Reg == SuperReg) {
646 NewReg = NewSuperReg;
649 if (NewSubRegIdx != 0)
650 NewReg = TRI->
getSubReg(NewSuperReg, NewSubRegIdx);
656 if (!RenameRegisterMap[Reg].
test(NewReg)) {
665 if (State->
IsLive(NewReg) || (KillIndices[Reg] > DefIndices[NewReg])) {
671 unsigned AliasReg = *AI;
672 if (State->
IsLive(AliasReg) ||
673 (KillIndices[Reg] > DefIndices[AliasReg])) {
675 <<
"(alias " <<
printReg(AliasReg, TRI) <<
" live)");
686 for (
const auto &Q :
make_range(RegRefs.equal_range(Reg))) {
701 for (
const auto &Q :
make_range(RegRefs.equal_range(Reg))) {
702 if (!Q.second.Operand->isDef() || !Q.second.Operand->isEarlyClobber())
713 RenameMap.insert(std::pair<unsigned, unsigned>(Reg, NewReg));
718 RenameOrder.erase(SuperRC);
719 RenameOrder.insert(RenameOrderType::value_type(SuperRC, R));
736 const std::vector<SUnit> &SUnits,
739 unsigned InsertPosIndex,
743 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
748 if (SUnits.empty())
return 0;
751 RenameOrderType RenameOrder;
754 std::map<MachineInstr *, const SUnit *> MISUnitMap;
755 for (
const SUnit &SU : SUnits)
756 MISUnitMap.insert(std::make_pair(SU.getInstr(), &SU));
761 const SUnit *CriticalPathSU =
nullptr;
763 if (CriticalPathSet.
any()) {
764 for (
const SUnit &SU : SUnits) {
765 if (!CriticalPathSU ||
766 ((SU.getDepth() + SU.Latency) >
768 CriticalPathSU = &SU;
771 assert(CriticalPathSU &&
"Failed to find SUnit critical path");
772 CriticalPathMI = CriticalPathSU->
getInstr();
776 LLVM_DEBUG(
dbgs() <<
"\n===== Aggressive anti-dependency breaking\n");
778 for (
unsigned Reg = 1; Reg < TRI->
getNumRegs(); ++Reg) {
791 unsigned Count = InsertPosIndex - 1;
796 if (
MI.isDebugInstr())
802 std::set<unsigned> PassthruRegs;
803 GetPassthruRegs(
MI, PassthruRegs);
806 PrescanInstruction(
MI, Count, PassthruRegs);
810 std::vector<const SDep *> Edges;
811 const SUnit *PathSU = MISUnitMap[&
MI];
817 if (&
MI == CriticalPathMI) {
819 CriticalPathMI = (CriticalPathSU) ? CriticalPathSU->
getInstr() :
nullptr;
820 }
else if (CriticalPathSet.
any()) {
821 ExcludeRegs = &CriticalPathSet;
828 for (
const SDep *Edge : Edges) {
829 SUnit *NextSU = Edge->getSUnit();
834 unsigned AntiDepReg = Edge->getReg();
836 assert(AntiDepReg != 0 &&
"Anti-dependence on reg0?");
842 }
else if (ExcludeRegs && ExcludeRegs->
test(AntiDepReg)) {
847 }
else if (PassthruRegs.count(AntiDepReg) != 0) {
856 assert(AntiDepOp &&
"Can't find index for defined register operand");
873 Pred.
getReg() != AntiDepReg)
875 Pred.
getReg() == AntiDepReg)) {
886 }
else if ((Pred.
getSUnit() != NextSU) &&
888 (Pred.
getReg() == AntiDepReg)) {
895 if (AntiDepReg == 0)
continue;
918 if (AntiDepReg == 0)
continue;
924 const unsigned GroupIndex = State->
GetGroup(AntiDepReg);
925 if (GroupIndex == 0) {
933 std::map<unsigned, unsigned> RenameMap;
934 if (FindSuitableFreeRegisters(GroupIndex, RenameOrder, RenameMap)) {
936 <<
printReg(AntiDepReg, TRI) <<
":");
939 for (
const auto &
P : RenameMap) {
940 unsigned CurrReg =
P.first;
941 unsigned NewReg =
P.second;
945 << RegRefs.count(CurrReg) <<
" refs)");
949 for (
const auto &Q :
make_range(RegRefs.equal_range(CurrReg))) {
950 Q.second.Operand->setReg(NewReg);
954 const SUnit *SU = MISUnitMap[Q.second.Operand->getParent()];
964 RegRefs.erase(NewReg);
965 DefIndices[NewReg] = DefIndices[CurrReg];
966 KillIndices[NewReg] = KillIndices[CurrReg];
969 RegRefs.erase(CurrReg);
970 DefIndices[CurrReg] = KillIndices[CurrReg];
971 KillIndices[CurrReg] = ~0u;
972 assert(((KillIndices[CurrReg] == ~0u) !=
973 (DefIndices[CurrReg] == ~0u)) &&
974 "Kill and Def maps aren't consistent for AntiDepReg!");
983 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 isSubRegister(MCRegister RegA, MCRegister RegB) const
Returns true if RegB is a sub-register of RegA.
iterator_range< mc_subreg_iterator > subregs(MCRegister Reg) const
Return an iterator range over all sub-registers of Reg, excluding Reg.
iterator_range< mc_subreg_iterator > subregs_inclusive(MCRegister Reg) const
Return an iterator range over all sub-registers of Reg, including Reg.
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...
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.