40#define DEBUG_TYPE "post-RA-sched"
44 : NumTargetRegs(TargetRegs), GroupNodes(TargetRegs, 0),
45 GroupNodeIndices(TargetRegs, 0), KillIndices(TargetRegs, 0),
46 DefIndices(TargetRegs, 0) {
47 const unsigned BBSize = BB->
size();
48 for (
unsigned i = 0; i < NumTargetRegs; ++i) {
51 GroupNodeIndices[i] = i;
54 DefIndices[i] = BBSize;
59 unsigned Node = GroupNodeIndices[Reg.id()];
67 unsigned Group, std::vector<MCRegister> &Regs,
68 std::multimap<MCRegister, AggressiveAntiDepState::RegisterReference>
70 for (
unsigned Reg = 0; Reg != NumTargetRegs; ++Reg) {
71 if ((
GetGroup(Reg) == Group) && (RegRefs->count(Reg) > 0))
77 assert(GroupNodes[0] == 0 &&
"GroupNode 0 not parent!");
78 assert(GroupNodeIndices[0] == 0 &&
"Reg 0 not in Group 0!");
85 unsigned Parent = (Group1 == 0) ? Group1 : Group2;
86 unsigned Other = (Parent == Group1) ? Group2 : Group1;
87 GroupNodes.at(
Other) = Parent;
95 unsigned idx = GroupNodes.size();
96 GroupNodes.push_back(idx);
97 GroupNodeIndices[Reg.id()] = idx;
104 return ((KillIndices[Reg.id()] != ~0u) && (DefIndices[Reg.id()] == ~0u));
110 : MF(MFi), MRI(MF.getRegInfo()), TII(MF.getSubtarget().getInstrInfo()),
111 TRI(MF.getSubtarget().getRegisterInfo()), RegClassInfo(RCI) {
115 BitVector CPSet = TRI->getAllocatableSet(MF, RC);
116 if (CriticalPathSet.none())
117 CriticalPathSet = CPSet;
119 CriticalPathSet |= CPSet;
124 : CriticalPathSet.set_bits())
dbgs()
137 std::vector<unsigned> &KillIndices = State->GetKillIndices();
138 std::vector<unsigned> &DefIndices = State->GetDefIndices();
151 for (
unsigned R = 1, E = TRI->getNumRegs(); R != E; ++R) {
153 if (!
all_of(TRI->regunits(Reg), [&](MCRegUnit Unit) {
154 return LiveOutUnits.test(static_cast<unsigned>(Unit));
157 State->UnionGroups(Reg, 0);
158 KillIndices[Reg.id()] = BB->
size();
159 DefIndices[Reg.id()] = ~0u;
169 unsigned InsertPosIndex) {
170 assert(
Count < InsertPosIndex &&
"Instruction index out of expected range!");
172 std::set<MCRegister> PassthruRegs;
173 GetPassthruRegs(
MI, PassthruRegs);
174 PrescanInstruction(
MI,
Count, PassthruRegs);
181 std::vector<unsigned> &DefIndices = State->GetDefIndices();
182 for (
unsigned Reg = 1; Reg != TRI->getNumRegs(); ++Reg) {
189 if (State->IsLive(Reg)) {
191 <<
" " <<
printReg(Reg, TRI) <<
"=g" << State->GetGroup(Reg)
192 <<
"->g0(region live-out)");
193 State->UnionGroups(Reg, 0);
194 }
else if ((DefIndices[Reg] < InsertPosIndex)
195 && (DefIndices[Reg] >=
Count)) {
196 DefIndices[Reg] =
Count;
213 Op =
MI.findRegisterUseOperand(Reg,
nullptr,
true);
215 Op =
MI.findRegisterDefOperand(Reg,
nullptr);
217 return(
Op &&
Op->isImplicit());
220void AggressiveAntiDepBreaker::GetPassthruRegs(
222 for (
unsigned i = 0, e =
MI.getNumOperands(); i != e; ++i) {
224 if (!MO.
isReg())
continue;
225 if ((MO.
isDef() &&
MI.isRegTiedToUseOperand(i)) ||
226 IsImplicitDefUse(
MI, MO)) {
229 PassthruRegs.insert(SubReg);
241 Edges.push_back(&
Pred);
250 unsigned NextDepth = 0;
255 unsigned PredLatency =
Pred.getLatency();
256 unsigned PredTotalLatency = PredSU->
getDepth() + PredLatency;
259 if (NextDepth < PredTotalLatency ||
260 (NextDepth == PredTotalLatency &&
Pred.getKind() ==
SDep::Anti)) {
261 NextDepth = PredTotalLatency;
267 return (
Next) ?
Next->getSUnit() :
nullptr;
270void AggressiveAntiDepBreaker::HandleLastUse(
MCRegister Reg,
unsigned KillIdx,
273 const char *footer) {
274 std::vector<unsigned> &KillIndices = State->GetKillIndices();
275 std::vector<unsigned> &DefIndices = State->GetDefIndices();
276 std::multimap<MCRegister, AggressiveAntiDepState::RegisterReference>
277 &RegRefs = State->GetRegRefs();
283 for (MCRegAliasIterator AI(
Reg, TRI,
true); AI.isValid(); ++AI)
284 if (TRI->isSuperRegister(
Reg, *AI) && State->IsLive(*AI)) {
289 if (!State->IsLive(
Reg)) {
290 KillIndices[
Reg.
id()] = KillIdx;
291 DefIndices[
Reg.
id()] = ~0
u;
293 State->LeaveGroup(
Reg);
304 if (!State->IsLive(SubregReg)) {
305 KillIndices[SubregReg] = KillIdx;
306 DefIndices[SubregReg] = ~0
u;
307 RegRefs.erase(SubregReg);
308 State->LeaveGroup(SubregReg);
314 << State->GetGroup(SubregReg) << tag);
322void AggressiveAntiDepBreaker::PrescanInstruction(
324 const std::set<MCRegister> &PassthruRegs) {
325 std::vector<unsigned> &DefIndices = State->GetDefIndices();
326 std::multimap<MCRegister, AggressiveAntiDepState::RegisterReference>
327 &RegRefs = State->GetRegRefs();
334 for (
const MachineOperand &MO :
MI.all_defs()) {
343 for (
unsigned i = 0, e =
MI.getNumOperands(); i != e; ++i) {
344 MachineOperand &MO =
MI.getOperand(i);
351 << State->GetGroup(
Reg));
358 if (
MI.isCall() ||
MI.hasExtraDefRegAllocReq() || TII->isPredicated(
MI) ||
361 State->UnionGroups(
Reg, 0);
366 for (MCRegAliasIterator AI(
Reg, TRI,
false); AI.isValid(); ++AI) {
367 MCRegister AliasReg = *AI;
368 if (State->IsLive(AliasReg)) {
369 State->UnionGroups(
Reg, AliasReg);
377 if (i <
MI.getDesc().getNumOperands())
378 RC = TII->getRegClass(
MI.getDesc(), i);
379 AggressiveAntiDepState::RegisterReference RR = { &MO, RC };
387 for (
const MachineOperand &MO :
MI.all_defs()) {
392 if (
MI.isKill() || (PassthruRegs.count(
Reg) != 0))
396 for (MCRegAliasIterator AI(
Reg, TRI,
true); AI.isValid(); ++AI) {
403 if (TRI->isSuperRegister(
Reg, *AI) && State->IsLive(*AI))
406 DefIndices[(*AI).id()] =
Count;
414 std::multimap<MCRegister, AggressiveAntiDepState::RegisterReference>
415 &RegRefs = State->GetRegRefs();
434 bool Special =
MI.isCall() ||
MI.hasExtraSrcRegAllocReq() ||
435 TII->isPredicated(
MI) ||
MI.isInlineAsm();
439 for (
unsigned i = 0, e =
MI.getNumOperands(); i != e; ++i) {
440 MachineOperand &MO =
MI.getOperand(i);
447 << State->GetGroup(
Reg));
456 State->UnionGroups(
Reg, 0);
461 if (i <
MI.getDesc().getNumOperands())
462 RC = TII->getRegClass(
MI.getDesc(), i);
463 AggressiveAntiDepState::RegisterReference RR = { &MO, RC };
475 for (
const MachineOperand &MO :
MI.operands()) {
476 if (!MO.
isReg())
continue;
483 State->UnionGroups(FirstReg,
Reg);
495 BitVector BV(TRI->getNumRegs(),
false);
501 for (
const auto &Q :
make_range(State->GetRegRefs().equal_range(
Reg))) {
505 BitVector RCBV = TRI->getAllocatableSet(MF, RC);
519bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters(
520 MCRegister SuperReg,
unsigned AntiDepGroupIndex,
521 RenameOrderType &RenameOrder, std::map<MCRegister, MCRegister> &RenameMap) {
522 std::vector<unsigned> &KillIndices = State->GetKillIndices();
523 std::vector<unsigned> &DefIndices = State->GetDefIndices();
524 std::multimap<MCRegister, AggressiveAntiDepState::RegisterReference>
525 &RegRefs = State->GetRegRefs();
530 std::vector<MCRegister> Regs;
531 State->GetGroupRegs(AntiDepGroupIndex, Regs, &RegRefs);
532 assert(!Regs.empty() &&
"Empty register group!");
538 LLVM_DEBUG(
dbgs() <<
"\tRename Candidates for Group g" << AntiDepGroupIndex
540 std::map<MCRegister, BitVector> RenameRegisterMap;
541 for (MCRegister
Reg : Regs) {
543 if (RegRefs.count(
Reg) > 0) {
546 BitVector &BV = RenameRegisterMap[
Reg];
548 BV = GetRenameRegisters(
Reg);
560 for (MCRegister
Reg : Regs) {
561 if (
Reg == SuperReg)
continue;
562 bool IsSub = TRI->isSubRegister(SuperReg,
Reg);
574 if (Opts.agg_antidep_debugdiv > 0) {
575 static int renamecnt = 0;
576 if (renamecnt++ % Opts.agg_antidep_debugdiv != Opts.agg_antidep_debugmod)
579 dbgs() <<
"*** Performing rename " <<
printReg(SuperReg, TRI)
580 <<
" for debug ***\n";
602 RenameOrder.insert(RenameOrderType::value_type(SuperRC, Order.
size()));
604 unsigned OrigR = RenameOrder[SuperRC];
605 unsigned EndR = ((OrigR == Order.
size()) ? 0 : OrigR);
608 if (R == 0)
R = Order.
size();
610 const MCRegister NewSuperReg = Order[
R];
612 if (!MRI.isAllocatable(NewSuperReg))
continue;
614 if (NewSuperReg == SuperReg)
continue;
622 for (MCRegister
Reg : Regs) {
624 if (
Reg == SuperReg) {
625 NewReg = NewSuperReg;
627 unsigned NewSubRegIdx = TRI->getSubRegIndex(SuperReg,
Reg);
628 if (NewSubRegIdx != 0)
629 NewReg = TRI->getSubReg(NewSuperReg, NewSubRegIdx);
635 if (!RenameRegisterMap[
Reg].
test(NewReg.
id())) {
644 if (State->IsLive(NewReg) ||
645 (KillIndices[
Reg.
id()] > DefIndices[NewReg.
id()])) {
650 for (MCRegAliasIterator AI(NewReg, TRI,
false); AI.isValid(); ++AI) {
651 MCRegister AliasReg = *AI;
652 if (State->IsLive(AliasReg) ||
653 (KillIndices[
Reg.
id()] > DefIndices[AliasReg.
id()])) {
655 <<
"(alias " <<
printReg(AliasReg, TRI) <<
" live)");
682 if (!Q.second.Operand->isDef() || !Q.second.Operand->isEarlyClobber())
693 RenameMap.insert(std::make_pair(
Reg, NewReg));
698 RenameOrder.erase(SuperRC);
699 RenameOrder.insert(RenameOrderType::value_type(SuperRC, R));
716 const std::vector<SUnit> &SUnits,
719 unsigned InsertPosIndex,
721 std::vector<unsigned> &KillIndices = State->GetKillIndices();
722 std::vector<unsigned> &DefIndices = State->GetDefIndices();
723 std::multimap<MCRegister, AggressiveAntiDepState::RegisterReference>
724 &RegRefs = State->GetRegRefs();
728 if (SUnits.empty())
return 0;
731 RenameOrderType RenameOrder;
734 std::map<MachineInstr *, const SUnit *> MISUnitMap;
735 for (
const SUnit &SU : SUnits)
736 MISUnitMap.insert(std::make_pair(SU.getInstr(), &SU));
741 const SUnit *CriticalPathSU =
nullptr;
743 if (CriticalPathSet.any()) {
744 for (
const SUnit &SU : SUnits) {
745 if (!CriticalPathSU ||
746 ((SU.getDepth() + SU.Latency) >
748 CriticalPathSU = &SU;
751 assert(CriticalPathSU &&
"Failed to find SUnit critical path");
752 CriticalPathMI = CriticalPathSU->
getInstr();
756 LLVM_DEBUG(
dbgs() <<
"\n===== Aggressive anti-dependency breaking\n");
758 for (
unsigned Reg = 1; Reg < TRI->getNumRegs(); ++Reg) {
759 if (!State->IsLive(Reg))
769 unsigned Count = InsertPosIndex - 1;
774 if (
MI.isDebugOrPseudoInstr())
780 std::set<MCRegister> PassthruRegs;
781 GetPassthruRegs(
MI, PassthruRegs);
784 PrescanInstruction(
MI,
Count, PassthruRegs);
788 std::vector<const SDep *> Edges;
789 const SUnit *PathSU = MISUnitMap[&
MI];
795 if (&
MI == CriticalPathMI) {
797 CriticalPathMI = (CriticalPathSU) ? CriticalPathSU->
getInstr() :
nullptr;
798 }
else if (CriticalPathSet.any()) {
799 ExcludeRegs = &CriticalPathSet;
806 for (
const SDep *Edge : Edges) {
807 SUnit *NextSU = Edge->getSUnit();
812 MCRegister AntiDepReg = Edge->getReg().asMCReg();
814 assert(AntiDepReg &&
"Anti-dependence on reg0?");
816 if (!MRI.isAllocatable(AntiDepReg)) {
820 }
else if (ExcludeRegs && ExcludeRegs->
test(AntiDepReg.
id())) {
825 }
else if (PassthruRegs.count(AntiDepReg) != 0) {
834 MI.findRegisterDefOperand(AntiDepReg,
nullptr);
835 assert(AntiDepOp &&
"Can't find index for defined register operand");
851 if (Pred.getSUnit() == NextSU ? (Pred.getKind() !=
SDep::Anti ||
852 Pred.getReg() != AntiDepReg)
854 Pred.getReg() == AntiDepReg)) {
860 if ((Pred.getSUnit() == NextSU) && (Pred.getKind() !=
SDep::Anti) &&
865 }
else if ((Pred.getSUnit() != NextSU) &&
867 (Pred.getReg() == AntiDepReg)) {
881 const unsigned GroupIndex = State->GetGroup(AntiDepReg);
882 if (GroupIndex == 0) {
890 std::map<MCRegister, MCRegister> RenameMap;
891 if (FindSuitableFreeRegisters(AntiDepReg, GroupIndex, RenameOrder,
894 <<
printReg(AntiDepReg, TRI) <<
":");
897 for (
const auto &
P : RenameMap) {
903 << RegRefs.count(CurrReg) <<
" refs)");
907 for (
const auto &Q :
make_range(RegRefs.equal_range(CurrReg))) {
908 Q.second.Operand->setReg(NewReg);
912 const SUnit *SU = MISUnitMap[Q.second.Operand->getParent()];
921 State->UnionGroups(NewReg, 0);
922 RegRefs.erase(NewReg);
923 DefIndices[NewReg.
id()] = DefIndices[CurrReg.
id()];
924 KillIndices[NewReg.
id()] = KillIndices[CurrReg.
id()];
926 State->UnionGroups(CurrReg, 0);
927 RegRefs.erase(CurrReg);
928 DefIndices[CurrReg.
id()] = KillIndices[CurrReg.
id()];
929 KillIndices[CurrReg.
id()] = ~0u;
930 assert(((KillIndices[CurrReg.
id()] == ~0u) !=
931 (DefIndices[CurrReg.
id()] == ~0u)) &&
932 "Kill and Def maps aren't consistent for AntiDepReg!");
MachineInstrBuilder & UseMI
MachineInstrBuilder MachineInstrBuilder & DefMI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
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.
Register const TargetRegisterInfo * TRI
Promote Memory to Register
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< MCRegister > &Regs, std::multimap< MCRegister, AggressiveAntiDepState::RegisterReference > *RegRefs)
unsigned LeaveGroup(MCRegister Reg)
bool IsLive(MCRegister Reg)
Return true if Reg is live.
unsigned GetGroup(MCRegister Reg)
unsigned UnionGroups(MCRegister Reg1, MCRegister Reg2)
This class works in conjunction with the post-RA scheduler to rename registers to break register anti...
void UpdateDbgValues(const DbgValueVector &DbgValues, MachineInstr *ParentMI, MCRegister OldReg, MCRegister 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
size_t size() const
Get the array size.
bool empty() const
Check if the array is empty.
bool test(unsigned Idx) const
Returns true if bit Idx is set.
iterator_range< const_set_bits_iterator > set_bits() const
bool empty() const
Returns whether there are no bits in this bitvector.
A set of register units used to track register liveness.
const BitVector & getBitVector() const
Return the internal bitvector representation of the set.
LLVM_ABI void addLiveOuts(const MachineBasicBlock &MBB)
Adds registers living out of block MBB.
Wrapper class representing physical registers. Should be passed by value.
constexpr unsigned id() const
MachineInstrBundleIterator< MachineInstr > iterator
Representation of each machine instruction.
const MachineBasicBlock * getParent() const
bool readsRegister(Register Reg, const TargetRegisterInfo *TRI) const
Return true if the MachineInstr reads the specified register.
const MachineOperand & getOperand(unsigned i) const
LLVM_ABI int findRegisterDefOperandIdx(Register Reg, const TargetRegisterInfo *TRI, bool isDead=false, bool Overlap=false) const
Returns the operand index that is a def of the specified register or -1 if it is not found.
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.
Wrapper class representing virtual and physical registers.
MCRegister asMCReg() const
Utility to check-convert this value to a MCRegister.
constexpr unsigned id() const
@ Output
A register output-dependence (aka WAW).
@ Anti
A register anti-dependence (aka WAR).
@ Data
Regular data dependence (aka true-dependence).
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 > 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.
SmallVectorImpl< const TargetRegisterClass * > RegClassVector
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
This is an optimization pass for GlobalISel generic memory operations.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI 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.
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
DWARFExpression::Operation Op
ArrayRef(const T &OneElt) -> ArrayRef< T >
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Next
@ End
Run the machine verifier once, at the end of the pipeline.
LLVM_ABI 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.
const CodeGenOptions & getCodeGenOptions(const LLVMContext &C)
MCRegisterClass TargetRegisterClass