X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FAggressiveAntiDepBreaker.cpp;h=4060db74a9b7274d8e80e404bdd5f43bf59921fa;hb=bfe2e58c93b89c4a71ba4c0396f5578f1a2f359e;hp=8840622f9ae5c74bdaff966743c1bbb694d1e323;hpb=518bb53485df640d7b7e3f6b0544099020c42aa7;p=oota-llvm.git diff --git a/lib/CodeGen/AggressiveAntiDepBreaker.cpp b/lib/CodeGen/AggressiveAntiDepBreaker.cpp index 8840622f9ae..4060db74a9b 100644 --- a/lib/CodeGen/AggressiveAntiDepBreaker.cpp +++ b/lib/CodeGen/AggressiveAntiDepBreaker.cpp @@ -14,34 +14,38 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "post-RA-sched" #include "AggressiveAntiDepBreaker.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineInstr.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetMachine.h" -#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/CodeGen/RegisterClassInfo.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetRegisterInfo.h" using namespace llvm; +#define DEBUG_TYPE "post-RA-sched" + // If DebugDiv > 0 then only break antidep with (ID % DebugDiv) == DebugMod static cl::opt DebugDiv("agg-antidep-debugdiv", - cl::desc("Debug control for aggressive anti-dep breaker"), - cl::init(0), cl::Hidden); + cl::desc("Debug control for aggressive anti-dep breaker"), + cl::init(0), cl::Hidden); static cl::opt DebugMod("agg-antidep-debugmod", - cl::desc("Debug control for aggressive anti-dep breaker"), - cl::init(0), cl::Hidden); + cl::desc("Debug control for aggressive anti-dep breaker"), + cl::init(0), cl::Hidden); AggressiveAntiDepState::AggressiveAntiDepState(const unsigned TargetRegs, MachineBasicBlock *BB) : - NumTargetRegs(TargetRegs), GroupNodes(TargetRegs, 0) { - + NumTargetRegs(TargetRegs), GroupNodes(TargetRegs, 0), + GroupNodeIndices(TargetRegs, 0), + KillIndices(TargetRegs, 0), + DefIndices(TargetRegs, 0) +{ const unsigned BBSize = BB->size(); for (unsigned i = 0; i < NumTargetRegs; ++i) { // Initialize all registers to be in their own group. Initially we @@ -53,8 +57,7 @@ AggressiveAntiDepState::AggressiveAntiDepState(const unsigned TargetRegs, } } -unsigned AggressiveAntiDepState::GetGroup(unsigned Reg) -{ +unsigned AggressiveAntiDepState::GetGroup(unsigned Reg) { unsigned Node = GroupNodeIndices[Reg]; while (GroupNodes[Node] != Node) Node = GroupNodes[Node]; @@ -107,16 +110,13 @@ bool AggressiveAntiDepState::IsLive(unsigned Reg) return((KillIndices[Reg] != ~0u) && (DefIndices[Reg] == ~0u)); } - - -AggressiveAntiDepBreaker:: -AggressiveAntiDepBreaker(MachineFunction& MFi, - TargetSubtarget::RegClassVector& CriticalPathRCs) : - AntiDepBreaker(), MF(MFi), - MRI(MF.getRegInfo()), - TRI(MF.getTarget().getRegisterInfo()), - AllocatableSet(TRI->getAllocatableSet(MF)), - State(NULL) { +AggressiveAntiDepBreaker::AggressiveAntiDepBreaker( + MachineFunction &MFi, const RegisterClassInfo &RCI, + TargetSubtargetInfo::RegClassVector &CriticalPathRCs) + : AntiDepBreaker(), MF(MFi), MRI(MF.getRegInfo()), + TII(MF.getSubtarget().getInstrInfo()), + TRI(MF.getSubtarget().getRegisterInfo()), RegClassInfo(RCI), + State(nullptr) { /* Collect a bitset of all registers that are only broken if they are on the critical path. */ for (unsigned i = 0, e = CriticalPathRCs.size(); i < e; ++i) { @@ -139,64 +139,35 @@ AggressiveAntiDepBreaker::~AggressiveAntiDepBreaker() { } void AggressiveAntiDepBreaker::StartBlock(MachineBasicBlock *BB) { - assert(State == NULL); + assert(!State); State = new AggressiveAntiDepState(TRI->getNumRegs(), BB); - bool IsReturnBlock = (!BB->empty() && BB->back().getDesc().isReturn()); - unsigned *KillIndices = State->GetKillIndices(); - unsigned *DefIndices = State->GetDefIndices(); + bool IsReturnBlock = BB->isReturnBlock(); + std::vector &KillIndices = State->GetKillIndices(); + std::vector &DefIndices = State->GetDefIndices(); - // Determine the live-out physregs for this block. - if (IsReturnBlock) { - // In a return block, examine the function live-out regs. - for (MachineRegisterInfo::liveout_iterator I = MRI.liveout_begin(), - E = MRI.liveout_end(); I != E; ++I) { - unsigned Reg = *I; - State->UnionGroups(Reg, 0); - KillIndices[Reg] = BB->size(); - DefIndices[Reg] = ~0u; - // Repeat, for all aliases. - for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { - unsigned AliasReg = *Alias; - State->UnionGroups(AliasReg, 0); - KillIndices[AliasReg] = BB->size(); - DefIndices[AliasReg] = ~0u; - } - } - } else { - // In a non-return block, examine the live-in regs of all successors. - for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), + // Examine the live-in regs of all successors. + for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), SE = BB->succ_end(); SI != SE; ++SI) - for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(), - E = (*SI)->livein_end(); I != E; ++I) { - unsigned Reg = *I; + for (const auto &LI : (*SI)->liveins()) { + for (MCRegAliasIterator AI(LI.PhysReg, TRI, true); AI.isValid(); ++AI) { + unsigned Reg = *AI; State->UnionGroups(Reg, 0); KillIndices[Reg] = BB->size(); DefIndices[Reg] = ~0u; - // Repeat, for all aliases. - for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { - unsigned AliasReg = *Alias; - State->UnionGroups(AliasReg, 0); - KillIndices[AliasReg] = BB->size(); - DefIndices[AliasReg] = ~0u; - } } - } + } // Mark live-out callee-saved registers. In a return block this is // all callee-saved registers. In non-return this is any // callee-saved register that is not saved in the prolog. const MachineFrameInfo *MFI = MF.getFrameInfo(); - BitVector Pristine = MFI->getPristineRegs(BB); - for (const unsigned *I = TRI->getCalleeSavedRegs(); *I; ++I) { + BitVector Pristine = MFI->getPristineRegs(MF); + for (const MCPhysReg *I = TRI->getCalleeSavedRegs(&MF); *I; ++I) { unsigned Reg = *I; if (!IsReturnBlock && !Pristine.test(Reg)) continue; - State->UnionGroups(Reg, 0); - KillIndices[Reg] = BB->size(); - DefIndices[Reg] = ~0u; - // Repeat, for all aliases. - for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { - unsigned AliasReg = *Alias; + for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { + unsigned AliasReg = *AI; State->UnionGroups(AliasReg, 0); KillIndices[AliasReg] = BB->size(); DefIndices[AliasReg] = ~0u; @@ -206,11 +177,11 @@ void AggressiveAntiDepBreaker::StartBlock(MachineBasicBlock *BB) { void AggressiveAntiDepBreaker::FinishBlock() { delete State; - State = NULL; + State = nullptr; } void AggressiveAntiDepBreaker::Observe(MachineInstr *MI, unsigned Count, - unsigned InsertPosIndex) { + unsigned InsertPosIndex) { assert(Count < InsertPosIndex && "Instruction index out of expected range!"); std::set PassthruRegs; @@ -222,7 +193,7 @@ void AggressiveAntiDepBreaker::Observe(MachineInstr *MI, unsigned Count, DEBUG(MI->dump()); DEBUG(dbgs() << "\tRegs:"); - unsigned *DefIndices = State->GetDefIndices(); + std::vector &DefIndices = State->GetDefIndices(); for (unsigned Reg = 0; Reg != TRI->getNumRegs(); ++Reg) { // If Reg is current live, then mark that it can't be renamed as // we don't know the extent of its live-range anymore (now that it @@ -244,7 +215,7 @@ void AggressiveAntiDepBreaker::Observe(MachineInstr *MI, unsigned Count, } bool AggressiveAntiDepBreaker::IsImplicitDefUse(MachineInstr *MI, - MachineOperand& MO) + MachineOperand& MO) { if (!MO.isReg() || !MO.isImplicit()) return false; @@ -253,13 +224,13 @@ bool AggressiveAntiDepBreaker::IsImplicitDefUse(MachineInstr *MI, if (Reg == 0) return false; - MachineOperand *Op = NULL; + MachineOperand *Op = nullptr; if (MO.isDef()) Op = MI->findRegisterUseOperand(Reg, true); else Op = MI->findRegisterDefOperand(Reg); - return((Op != NULL) && Op->isImplicit()); + return(Op && Op->isImplicit()); } void AggressiveAntiDepBreaker::GetPassthruRegs(MachineInstr *MI, @@ -270,41 +241,36 @@ void AggressiveAntiDepBreaker::GetPassthruRegs(MachineInstr *MI, if ((MO.isDef() && MI->isRegTiedToUseOperand(i)) || IsImplicitDefUse(MI, MO)) { const unsigned Reg = MO.getReg(); - PassthruRegs.insert(Reg); - for (const unsigned *Subreg = TRI->getSubRegisters(Reg); - *Subreg; ++Subreg) { - PassthruRegs.insert(*Subreg); - } + for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); + SubRegs.isValid(); ++SubRegs) + PassthruRegs.insert(*SubRegs); } } } /// AntiDepEdges - Return in Edges the anti- and output- dependencies /// in SU that we want to consider for breaking. -static void AntiDepEdges(SUnit *SU, std::vector& Edges) { +static void AntiDepEdges(const SUnit *SU, std::vector& Edges) { SmallSet RegSet; - for (SUnit::pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end(); + for (SUnit::const_pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end(); P != PE; ++P) { if ((P->getKind() == SDep::Anti) || (P->getKind() == SDep::Output)) { - unsigned Reg = P->getReg(); - if (RegSet.count(Reg) == 0) { + if (RegSet.insert(P->getReg()).second) Edges.push_back(&*P); - RegSet.insert(Reg); - } } } } /// CriticalPathStep - Return the next SUnit after SU on the bottom-up /// critical path. -static SUnit *CriticalPathStep(SUnit *SU) { - SDep *Next = 0; +static const SUnit *CriticalPathStep(const SUnit *SU) { + const SDep *Next = nullptr; unsigned NextDepth = 0; // Find the predecessor edge with the greatest depth. - if (SU != 0) { - for (SUnit::pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end(); + if (SU) { + for (SUnit::const_pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end(); P != PE; ++P) { - SUnit *PredSU = P->getSUnit(); + const SUnit *PredSU = P->getSUnit(); unsigned PredLatency = P->getLatency(); unsigned PredTotalLatency = PredSU->getDepth() + PredLatency; // In the case of a latency tie, prefer an anti-dependency edge over @@ -317,56 +283,64 @@ static SUnit *CriticalPathStep(SUnit *SU) { } } - return (Next) ? Next->getSUnit() : 0; + return (Next) ? Next->getSUnit() : nullptr; } void AggressiveAntiDepBreaker::HandleLastUse(unsigned Reg, unsigned KillIdx, const char *tag, const char *header, const char *footer) { - unsigned *KillIndices = State->GetKillIndices(); - unsigned *DefIndices = State->GetDefIndices(); + std::vector &KillIndices = State->GetKillIndices(); + std::vector &DefIndices = State->GetDefIndices(); std::multimap& RegRefs = State->GetRegRefs(); + // FIXME: We must leave subregisters of live super registers as live, so that + // we don't clear out the register tracking information for subregisters of + // super registers we're still tracking (and with which we're unioning + // subregister definitions). + for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) + if (TRI->isSuperRegister(Reg, *AI) && State->IsLive(*AI)) { + DEBUG(if (!header && footer) dbgs() << footer); + return; + } + if (!State->IsLive(Reg)) { KillIndices[Reg] = KillIdx; DefIndices[Reg] = ~0u; RegRefs.erase(Reg); State->LeaveGroup(Reg); - DEBUG(if (header != NULL) { - dbgs() << header << TRI->getName(Reg); header = NULL; }); + DEBUG(if (header) { + dbgs() << header << TRI->getName(Reg); header = nullptr; }); DEBUG(dbgs() << "->g" << State->GetGroup(Reg) << tag); } // Repeat for subregisters. - for (const unsigned *Subreg = TRI->getSubRegisters(Reg); - *Subreg; ++Subreg) { - unsigned SubregReg = *Subreg; + for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { + unsigned SubregReg = *SubRegs; if (!State->IsLive(SubregReg)) { KillIndices[SubregReg] = KillIdx; DefIndices[SubregReg] = ~0u; RegRefs.erase(SubregReg); State->LeaveGroup(SubregReg); - DEBUG(if (header != NULL) { - dbgs() << header << TRI->getName(Reg); header = NULL; }); + DEBUG(if (header) { + dbgs() << header << TRI->getName(Reg); header = nullptr; }); DEBUG(dbgs() << " " << TRI->getName(SubregReg) << "->g" << State->GetGroup(SubregReg) << tag); } } - DEBUG(if ((header == NULL) && (footer != NULL)) dbgs() << footer); + DEBUG(if (!header && footer) dbgs() << footer); } void AggressiveAntiDepBreaker::PrescanInstruction(MachineInstr *MI, unsigned Count, - std::set& PassthruRegs) -{ - unsigned *DefIndices = State->GetDefIndices(); + std::set& PassthruRegs) { + std::vector &DefIndices = State->GetDefIndices(); std::multimap& RegRefs = State->GetRegRefs(); // Handle dead defs by simulating a last-use of the register just - // after the def. A dead def can occur because the def is truely + // after the def. A dead def can occur because the def is truly // dead, or because only a subregister is live at the def. If we // don't do this the dead def will be incorrectly merged into the // previous def. @@ -390,16 +364,19 @@ void AggressiveAntiDepBreaker::PrescanInstruction(MachineInstr *MI, // If MI's defs have a special allocation requirement, don't allow // any def registers to be changed. Also assume all registers - // defined in a call must not be changed (ABI). - if (MI->getDesc().isCall() || MI->getDesc().hasExtraDefRegAllocReq()) { + // defined in a call must not be changed (ABI). Inline assembly may + // reference either system calls or the register directly. Skip it until we + // can tell user specified registers from compiler-specified. + if (MI->isCall() || MI->hasExtraDefRegAllocReq() || + TII->isPredicated(MI) || MI->isInlineAsm()) { DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)"); State->UnionGroups(Reg, 0); } // Any aliased that are live at this point are completely or // partially defined here, so group those aliases with Reg. - for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { - unsigned AliasReg = *Alias; + for (MCRegAliasIterator AI(Reg, TRI, false); AI.isValid(); ++AI) { + unsigned AliasReg = *AI; if (State->IsLive(AliasReg)) { State->UnionGroups(Reg, AliasReg); DEBUG(dbgs() << "->g" << State->GetGroup(Reg) << "(via " << @@ -408,9 +385,9 @@ void AggressiveAntiDepBreaker::PrescanInstruction(MachineInstr *MI, } // Note register reference... - const TargetRegisterClass *RC = NULL; + const TargetRegisterClass *RC = nullptr; if (i < MI->getDesc().getNumOperands()) - RC = MI->getDesc().OpInfo[i].getRegClass(TRI); + RC = TII->getRegClass(MI->getDesc(), i, TRI, MF); AggressiveAntiDepState::RegisterReference RR = { &MO, RC }; RegRefs.insert(std::make_pair(Reg, RR)); } @@ -429,21 +406,48 @@ void AggressiveAntiDepBreaker::PrescanInstruction(MachineInstr *MI, continue; // Update def for Reg and aliases. - DefIndices[Reg] = Count; - for (const unsigned *Alias = TRI->getAliasSet(Reg); - *Alias; ++Alias) { - unsigned AliasReg = *Alias; - DefIndices[AliasReg] = Count; + for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { + // We need to be careful here not to define already-live super registers. + // If the super register is already live, then this definition is not + // a definition of the whole super register (just a partial insertion + // into it). Earlier subregister definitions (which we've not yet visited + // because we're iterating bottom-up) need to be linked to the same group + // as this definition. + if (TRI->isSuperRegister(Reg, *AI) && State->IsLive(*AI)) + continue; + + DefIndices[*AI] = Count; } } } void AggressiveAntiDepBreaker::ScanInstruction(MachineInstr *MI, - unsigned Count) { + unsigned Count) { DEBUG(dbgs() << "\tUse Groups:"); std::multimap& RegRefs = State->GetRegRefs(); + // If MI's uses have special allocation requirement, don't allow + // any use registers to be changed. Also assume all registers + // used in a call must not be changed (ABI). + // Inline Assembly register uses also cannot be safely changed. + // FIXME: The issue with predicated instruction is more complex. We are being + // conservatively here because the kill markers cannot be trusted after + // if-conversion: + // %R6 = LDR %SP, %reg0, 92, pred:14, pred:%reg0; mem:LD4[FixedStack14] + // ... + // STR %R0, %R6, %reg0, 0, pred:0, pred:%CPSR; mem:ST4[%395] + // %R6 = LDR %SP, %reg0, 100, pred:0, pred:%CPSR; mem:LD4[FixedStack12] + // STR %R0, %R6, %reg0, 0, pred:14, pred:%reg0; mem:ST4[%396](align=8) + // + // The first R6 kill is not really a kill since it's killed by a predicated + // instruction which may not be executed. The second R6 def may or may not + // re-define R6 so it's not safe to change it since the last R6 use cannot be + // changed. + bool Special = MI->isCall() || + MI->hasExtraSrcRegAllocReq() || + TII->isPredicated(MI) || MI->isInlineAsm(); + // Scan the register uses for this instruction and update // live-ranges, groups and RegRefs. for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { @@ -460,18 +464,15 @@ void AggressiveAntiDepBreaker::ScanInstruction(MachineInstr *MI, // for the register. HandleLastUse(Reg, Count, "(last-use)"); - // If MI's uses have special allocation requirement, don't allow - // any use registers to be changed. Also assume all registers - // used in a call must not be changed (ABI). - if (MI->getDesc().isCall() || MI->getDesc().hasExtraSrcRegAllocReq()) { + if (Special) { DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)"); State->UnionGroups(Reg, 0); } // Note register reference... - const TargetRegisterClass *RC = NULL; + const TargetRegisterClass *RC = nullptr; if (i < MI->getDesc().getNumOperands()) - RC = MI->getDesc().OpInfo[i].getRegClass(TRI); + RC = TII->getRegClass(MI->getDesc(), i, TRI, MF); AggressiveAntiDepState::RegisterReference RR = { &MO, RC }; RegRefs.insert(std::make_pair(Reg, RR)); } @@ -510,16 +511,9 @@ BitVector AggressiveAntiDepBreaker::GetRenameRegisters(unsigned Reg) { // Check all references that need rewriting for Reg. For each, use // the corresponding register class to narrow the set of registers // that are appropriate for renaming. - std::pair::iterator, - std::multimap::iterator> - Range = State->GetRegRefs().equal_range(Reg); - for (std::multimap::iterator Q = Range.first, - QE = Range.second; Q != QE; ++Q) { - const TargetRegisterClass *RC = Q->second.RC; - if (RC == NULL) continue; + for (const auto &Q : make_range(State->GetRegRefs().equal_range(Reg))) { + const TargetRegisterClass *RC = Q.second.RC; + if (!RC) continue; BitVector RCBV = TRI->getAllocatableSet(MF, RC); if (first) { @@ -529,7 +523,7 @@ BitVector AggressiveAntiDepBreaker::GetRenameRegisters(unsigned Reg) { BV &= RCBV; } - DEBUG(dbgs() << " " << RC->getName()); + DEBUG(dbgs() << " " << TRI->getRegClassName(RC)); } return BV; @@ -539,8 +533,8 @@ bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters( unsigned AntiDepGroupIndex, RenameOrderType& RenameOrder, std::map &RenameMap) { - unsigned *KillIndices = State->GetKillIndices(); - unsigned *DefIndices = State->GetDefIndices(); + std::vector &KillIndices = State->GetKillIndices(); + std::vector &DefIndices = State->GetDefIndices(); std::multimap& RegRefs = State->GetRegRefs(); @@ -584,7 +578,9 @@ bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters( unsigned Reg = Regs[i]; if (Reg == SuperReg) continue; bool IsSub = TRI->isSubRegister(SuperReg, Reg); - assert(IsSub && "Expecting group subregister"); + // FIXME: remove this once PR18663 has been properly fixed. For now, + // return a conservative answer: + // assert(IsSub && "Expecting group subregister"); if (!IsSub) return false; } @@ -605,28 +601,32 @@ bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters( // order. If that register is available, and the corresponding // registers are available for the other group subregisters, then we // can use those registers to rename. + + // FIXME: Using getMinimalPhysRegClass is very conservative. We should + // check every use of the register and find the largest register class + // that can be used in all of them. const TargetRegisterClass *SuperRC = - TRI->getPhysicalRegisterRegClass(SuperReg, MVT::Other); + TRI->getMinimalPhysRegClass(SuperReg, MVT::Other); - const TargetRegisterClass::iterator RB = SuperRC->allocation_order_begin(MF); - const TargetRegisterClass::iterator RE = SuperRC->allocation_order_end(MF); - if (RB == RE) { + ArrayRef Order = RegClassInfo.getOrder(SuperRC); + if (Order.empty()) { DEBUG(dbgs() << "\tEmpty Super Regclass!!\n"); return false; } DEBUG(dbgs() << "\tFind Registers:"); - if (RenameOrder.count(SuperRC) == 0) - RenameOrder.insert(RenameOrderType::value_type(SuperRC, RE)); + RenameOrder.insert(RenameOrderType::value_type(SuperRC, Order.size())); - const TargetRegisterClass::iterator OrigR = RenameOrder[SuperRC]; - const TargetRegisterClass::iterator EndR = ((OrigR == RE) ? RB : OrigR); - TargetRegisterClass::iterator R = OrigR; + unsigned OrigR = RenameOrder[SuperRC]; + unsigned EndR = ((OrigR == Order.size()) ? 0 : OrigR); + unsigned R = OrigR; do { - if (R == RB) R = RE; + if (R == 0) R = Order.size(); --R; - const unsigned NewSuperReg = *R; + const unsigned NewSuperReg = Order[R]; + // Don't consider non-allocatable registers + if (!MRI.isAllocatable(NewSuperReg)) continue; // Don't replace a register with itself. if (NewSuperReg == SuperReg) continue; @@ -665,9 +665,8 @@ bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters( goto next_super_reg; } else { bool found = false; - for (const unsigned *Alias = TRI->getAliasSet(NewReg); - *Alias; ++Alias) { - unsigned AliasReg = *Alias; + for (MCRegAliasIterator AI(NewReg, TRI, false); AI.isValid(); ++AI) { + unsigned AliasReg = *AI; if (State->IsLive(AliasReg) || (KillIndices[Reg] > DefIndices[AliasReg])) { DEBUG(dbgs() << "(alias " << TRI->getName(AliasReg) << " live)"); @@ -679,6 +678,34 @@ bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters( goto next_super_reg; } + // We cannot rename 'Reg' to 'NewReg' if one of the uses of 'Reg' also + // defines 'NewReg' via an early-clobber operand. + for (const auto &Q : make_range(RegRefs.equal_range(Reg))) { + MachineInstr *UseMI = Q.second.Operand->getParent(); + int Idx = UseMI->findRegisterDefOperandIdx(NewReg, false, true, TRI); + if (Idx == -1) + continue; + + if (UseMI->getOperand(Idx).isEarlyClobber()) { + DEBUG(dbgs() << "(ec)"); + goto next_super_reg; + } + } + + // Also, we cannot rename 'Reg' to 'NewReg' if the instruction defining + // 'Reg' is an early-clobber define and that instruction also uses + // 'NewReg'. + for (const auto &Q : make_range(RegRefs.equal_range(Reg))) { + if (!Q.second.Operand->isDef() || !Q.second.Operand->isEarlyClobber()) + continue; + + MachineInstr *DefMI = Q.second.Operand->getParent(); + if (DefMI->readsRegister(NewReg, TRI)) { + DEBUG(dbgs() << "(ec)"); + goto next_super_reg; + } + } + // Record that 'Reg' can be renamed to 'NewReg'. RenameMap.insert(std::pair(Reg, NewReg)); } @@ -704,12 +731,14 @@ bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters( /// ScheduleDAG and break them by renaming registers. /// unsigned AggressiveAntiDepBreaker::BreakAntiDependencies( - std::vector& SUnits, - MachineBasicBlock::iterator& Begin, - MachineBasicBlock::iterator& End, - unsigned InsertPosIndex) { - unsigned *KillIndices = State->GetKillIndices(); - unsigned *DefIndices = State->GetDefIndices(); + const std::vector& SUnits, + MachineBasicBlock::iterator Begin, + MachineBasicBlock::iterator End, + unsigned InsertPosIndex, + DbgValueVector &DbgValues) { + + std::vector &KillIndices = State->GetKillIndices(); + std::vector &DefIndices = State->GetDefIndices(); std::multimap& RegRefs = State->GetRegRefs(); @@ -721,20 +750,21 @@ unsigned AggressiveAntiDepBreaker::BreakAntiDependencies( RenameOrderType RenameOrder; // ...need a map from MI to SUnit. - std::map MISUnitMap; + std::map MISUnitMap; for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { - SUnit *SU = &SUnits[i]; - MISUnitMap.insert(std::pair(SU->getInstr(), SU)); + const SUnit *SU = &SUnits[i]; + MISUnitMap.insert(std::pair(SU->getInstr(), + SU)); } // Track progress along the critical path through the SUnit graph as // we walk the instructions. This is needed for regclasses that only // break critical-path anti-dependencies. - SUnit *CriticalPathSU = 0; - MachineInstr *CriticalPathMI = 0; + const SUnit *CriticalPathSU = nullptr; + MachineInstr *CriticalPathMI = nullptr; if (CriticalPathSet.any()) { for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { - SUnit *SU = &SUnits[i]; + const SUnit *SU = &SUnits[i]; if (!CriticalPathSU || ((SU->getDepth() + SU->Latency) > (CriticalPathSU->getDepth() + CriticalPathSU->Latency))) { @@ -764,6 +794,9 @@ unsigned AggressiveAntiDepBreaker::BreakAntiDependencies( I != E; --Count) { MachineInstr *MI = --I; + if (MI->isDebugValue()) + continue; + DEBUG(dbgs() << "Anti: "); DEBUG(MI->dump()); @@ -775,17 +808,17 @@ unsigned AggressiveAntiDepBreaker::BreakAntiDependencies( // The dependence edges that represent anti- and output- // dependencies that are candidates for breaking. - std::vector Edges; - SUnit *PathSU = MISUnitMap[MI]; + std::vector Edges; + const SUnit *PathSU = MISUnitMap[MI]; AntiDepEdges(PathSU, Edges); // If MI is not on the critical path, then we don't rename // registers in the CriticalPathSet. - BitVector *ExcludeRegs = NULL; + BitVector *ExcludeRegs = nullptr; if (MI == CriticalPathMI) { CriticalPathSU = CriticalPathStep(CriticalPathSU); - CriticalPathMI = (CriticalPathSU) ? CriticalPathSU->getInstr() : 0; - } else { + CriticalPathMI = (CriticalPathSU) ? CriticalPathSU->getInstr() : nullptr; + } else if (CriticalPathSet.any()) { ExcludeRegs = &CriticalPathSet; } @@ -794,7 +827,7 @@ unsigned AggressiveAntiDepBreaker::BreakAntiDependencies( if (!MI->isKill()) { // Attempt to break each anti-dependency... for (unsigned i = 0, e = Edges.size(); i != e; ++i) { - SDep *Edge = Edges[i]; + const SDep *Edge = Edges[i]; SUnit *NextSU = Edge->getSUnit(); if ((Edge->getKind() != SDep::Anti) && @@ -804,11 +837,11 @@ unsigned AggressiveAntiDepBreaker::BreakAntiDependencies( DEBUG(dbgs() << "\tAntidep reg: " << TRI->getName(AntiDepReg)); assert(AntiDepReg != 0 && "Anti-dependence on reg0?"); - if (!AllocatableSet.test(AntiDepReg)) { + if (!MRI.isAllocatable(AntiDepReg)) { // Don't break anti-dependencies on non-allocatable registers. DEBUG(dbgs() << " (non-allocatable)\n"); continue; - } else if ((ExcludeRegs != NULL) && ExcludeRegs->test(AntiDepReg)) { + } else if (ExcludeRegs && ExcludeRegs->test(AntiDepReg)) { // Don't break anti-dependencies for critical path registers // if not on the critical path DEBUG(dbgs() << " (not critical-path)\n"); @@ -822,9 +855,8 @@ unsigned AggressiveAntiDepBreaker::BreakAntiDependencies( } else { // No anti-dep breaking for implicit deps MachineOperand *AntiDepOp = MI->findRegisterDefOperand(AntiDepReg); - assert(AntiDepOp != NULL && - "Can't find index for defined register operand"); - if ((AntiDepOp == NULL) || AntiDepOp->isImplicit()) { + assert(AntiDepOp && "Can't find index for defined register operand"); + if (!AntiDepOp || AntiDepOp->isImplicit()) { DEBUG(dbgs() << " (implicit)\n"); continue; } @@ -838,7 +870,7 @@ unsigned AggressiveAntiDepBreaker::BreakAntiDependencies( // Also, if there are dependencies on other SUnits with the // same register as the anti-dependency, don't attempt to // break it. - for (SUnit::pred_iterator P = PathSU->Preds.begin(), + for (SUnit::const_pred_iterator P = PathSU->Preds.begin(), PE = PathSU->Preds.end(); P != PE; ++P) { if (P->getSUnit() == NextSU ? (P->getKind() != SDep::Anti || P->getReg() != AntiDepReg) : @@ -847,7 +879,7 @@ unsigned AggressiveAntiDepBreaker::BreakAntiDependencies( break; } } - for (SUnit::pred_iterator P = PathSU->Preds.begin(), + for (SUnit::const_pred_iterator P = PathSU->Preds.begin(), PE = PathSU->Preds.end(); P != PE; ++P) { if ((P->getSUnit() == NextSU) && (P->getKind() != SDep::Anti) && (P->getKind() != SDep::Output)) { @@ -896,15 +928,17 @@ unsigned AggressiveAntiDepBreaker::BreakAntiDependencies( // Update the references to the old register CurrReg to // refer to the new register NewReg. - std::pair::iterator, - std::multimap::iterator> - Range = RegRefs.equal_range(CurrReg); - for (std::multimap::iterator - Q = Range.first, QE = Range.second; Q != QE; ++Q) { - Q->second.Operand->setReg(NewReg); + for (const auto &Q : make_range(RegRefs.equal_range(CurrReg))) { + Q.second.Operand->setReg(NewReg); + // If the SU for the instruction being updated has debug + // information related to the anti-dependency register, make + // sure to update that as well. + const SUnit *SU = MISUnitMap[Q.second.Operand->getParent()]; + if (!SU) continue; + for (DbgValueVector::iterator DVI = DbgValues.begin(), + DVE = DbgValues.end(); DVI != DVE; ++DVI) + if (DVI->second == Q.second.Operand->getParent()) + UpdateDbgValue(DVI->first, AntiDepReg, NewReg); } // We just went back in time and modified history; the