Go to the documentation of this file.
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) {
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;
150 bool IsReturnBlock =
BB->isReturnBlock();
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);
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());
241 void 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;
292 void AggressiveAntiDepBreaker::HandleLastUse(
unsigned Reg,
unsigned KillIdx,
295 const char *footer) {
298 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
312 KillIndices[
Reg] = KillIdx;
313 DefIndices[
Reg] = ~0u;
326 unsigned SubregReg = *SubRegs;
327 if (!State->
IsLive(SubregReg)) {
328 KillIndices[SubregReg] = KillIdx;
329 DefIndices[SubregReg] = ~0u;
330 RegRefs.erase(SubregReg);
337 << State->
GetGroup(SubregReg) << tag);
345 void 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;
513 BitVector AggressiveAntiDepBreaker::GetRenameRegisters(
unsigned Reg) {
538 bool 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)");
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");
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;
912 unsigned R =
S.getReg();
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);
static const SUnit * CriticalPathStep(const SUnit *SU)
CriticalPathStep - Return the next SUnit after SU on the bottom-up critical path.
This is an optimization pass for GlobalISel generic memory operations.
ArrayRef< MCPhysReg > getOrder(const TargetRegisterClass *RC) const
getOrder - Returns the preferred allocation order for RC.
MachineInstrBuilder & UseMI
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
std::multimap< unsigned, RegisterReference > & GetRegRefs()
Return the RegRefs map.
unsigned UnionGroups(unsigned Reg1, unsigned Reg2)
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
bool none() const
none - Returns true if none of the bits are set.
~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...
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
Reg
All possible values of the reg field in the ModR/M byte.
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.
iterator_range< const_set_bits_iterator > set_bits() const
@ Anti
A register anti-dependence (aka WAR).
Kind
These are the different kinds of scheduling dependencies.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
SmallVector< SDep, 4 > Succs
All sunit successors.
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...
unsigned const TargetRegisterInfo * TRI
bool empty() const
empty - Check if the array is empty.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Contains all the state necessary for anti-dep breaking.
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,...
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
unsigned short Latency
Node latency.
const MachineOperand & getOperand(unsigned i) const
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...
const HexagonInstrInfo * TII
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 ...
MachineOperand class - Representation of each machine instruction operand.
static cl::opt< int > DebugMod("agg-antidep-debugmod", cl::desc("Debug control for aggressive anti-dep breaker"), cl::init(0), cl::Hidden)
@ Output
A register output-dependence (aka WAW).
AggressiveAntiDepState(const unsigned TargetRegs, MachineBasicBlock *BB)
@ Data
Regular data dependence (aka true-dependence).
bool empty() const
empty - Tests whether there are no bits in this bitvector.
AggressiveAntiDepBreaker(MachineFunction &MFi, const RegisterClassInfo &RCI, TargetSubtargetInfo::RegClassVector &CriticalPathRCs)
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Representation of each machine instruction.
void FinishBlock() override
Finish anti-dep breaking for a basic block.
bool IsLive(unsigned Reg)
Return true if Reg is live.
bool any() const
any - Returns true if any bit is set.
const char * getRegClassName(const TargetRegisterClass *Class) const
Returns the name of the register class.
virtual bool isPredicated(const MachineInstr &MI) const
Returns true if the instruction is already predicated.
const MCPhysReg * getCalleeSavedRegs() const
Returns list of callee saved registers.
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
unsigned getReg() const
Returns the register associated with this edge.
initializer< Ty > init(const Ty &Val)
std::vector< unsigned > & GetKillIndices()
Return the kill indices.
bool isAllocatable(MCRegister PhysReg) const
isAllocatable - Returns true when PhysReg belongs to an allocatable register class and it hasn't been...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
bool isEarlyClobber() const
Register getReg() const
getReg - Returns the register number.
std::vector< unsigned > & GetDefIndices()
Return the define indices.
bool readsRegister(Register Reg, const TargetRegisterInfo *TRI=nullptr) const
Return true if the MachineInstr reads the specified register.
void GetGroupRegs(unsigned Group, std::vector< unsigned > &Regs, std::multimap< unsigned, AggressiveAntiDepState::RegisterReference > *RegRefs)
unsigned LeaveGroup(unsigned Reg)
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
BitVector getPristineRegs(const MachineFunction &MF) const
Return a set of physical registers that are pristine.
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
static cl::opt< int > DebugDiv("agg-antidep-debugdiv", cl::desc("Debug control for aggressive anti-dep breaker"), cl::init(0), cl::Hidden)
const MachineBasicBlock * getParent() const
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
unsigned const MachineRegisterInfo * MRI
Wrapper class representing virtual and physical registers.
Information about a register reference within a liverange.
bool test(unsigned Idx) const
void StartBlock(MachineBasicBlock *BB) override
Initialize anti-dep breaking for a new basic block.
This class works in conjunction with the post-RA scheduler to rename registers to break register anti...
void Observe(MachineInstr &MI, unsigned Count, unsigned InsertPosIndex) override
Update liveness information to account for the current instruction, which will not be scheduled.
bool isSubRegister(MCRegister RegA, MCRegister RegB) const
Returns true if RegB is a sub-register of RegA.
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 ...
Kind getKind() const
Returns an enum value representing the kind of the dependence.
MCSubRegIterator enumerates all sub-registers of Reg.
bool isSuperRegister(MCRegister RegA, MCRegister RegB) const
Returns true if RegB is a super-register of RegA.
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
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 isValid() const
isValid - returns true if this iterator is not yet at the end.
MachineInstrBuilder MachineInstrBuilder & DefMI
size_t size() const
size - Get the array size.
unsigned GetGroup(unsigned Reg)
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
MCRegister getSubReg(MCRegister Reg, unsigned Idx) const
Returns the physical register number of sub-register "Index" for physical register RegNo.
SmallVector< SDep, 4 > Preds
All sunit predecessors.
Scheduling unit. This is a node in the scheduling DAG.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
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...
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.
std::vector< std::pair< MachineInstr *, MachineInstr * > > DbgValueVector
unsigned getLatency() const
Returns the latency value for this edge, which roughly means the minimum number of cycles that must e...
MCRegAliasIterator enumerates all registers aliasing Reg.
Optional< std::vector< StOtherPiece > > Other
AntiDepBreaker * createAggressiveAntiDepBreaker(MachineFunction &MFi, const RegisterClassInfo &RCI, TargetSubtargetInfo::RegClassVector &CriticalPathRCs)