//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "post-RA-sched"
#include "AggressiveAntiDepBreaker.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
-#include "llvm/Target/TargetMachine.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<int>
DebugDiv("agg-antidep-debugdiv",
return((KillIndices[Reg] != ~0u) && (DefIndices[Reg] == ~0u));
}
-
-
-AggressiveAntiDepBreaker::
-AggressiveAntiDepBreaker(MachineFunction& MFi,
- const RegisterClassInfo &RCI,
- TargetSubtargetInfo::RegClassVector& CriticalPathRCs) :
- AntiDepBreaker(), MF(MFi),
- MRI(MF.getRegInfo()),
- TII(MF.getTarget().getInstrInfo()),
- TRI(MF.getTarget().getRegisterInfo()),
- RegClassInfo(RCI),
- 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) {
}
void AggressiveAntiDepBreaker::StartBlock(MachineBasicBlock *BB) {
- assert(State == NULL);
+ assert(!State);
State = new AggressiveAntiDepState(TRI->getNumRegs(), BB);
- bool IsReturnBlock = (!BB->empty() && BB->back().isReturn());
+ bool IsReturnBlock = BB->isReturnBlock();
std::vector<unsigned> &KillIndices = State->GetKillIndices();
std::vector<unsigned> &DefIndices = State->GetDefIndices();
// 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) {
- for (MCRegAliasIterator AI(*I, TRI, true); AI.isValid(); ++AI) {
+ 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();
// 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 uint16_t *I = TRI->getCalleeSavedRegs(&MF); *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;
for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
void AggressiveAntiDepBreaker::FinishBlock() {
delete State;
- State = NULL;
+ State = nullptr;
}
void AggressiveAntiDepBreaker::Observe(MachineInstr *MI, unsigned Count,
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,
if ((MO.isDef() && MI->isRegTiedToUseOperand(i)) ||
IsImplicitDefUse(MI, MO)) {
const unsigned Reg = MO.getReg();
- PassthruRegs.insert(Reg);
- for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
+ for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
+ SubRegs.isValid(); ++SubRegs)
PassthruRegs.insert(*SubRegs);
}
}
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 const SUnit *CriticalPathStep(const SUnit *SU) {
- const SDep *Next = 0;
+ const SDep *Next = nullptr;
unsigned NextDepth = 0;
// Find the predecessor edge with the greatest depth.
- if (SU != 0) {
+ if (SU) {
for (SUnit::const_pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end();
P != PE; ++P) {
const SUnit *PredSU = P->getSUnit();
}
}
- return (Next) ? Next->getSUnit() : 0;
+ return (Next) ? Next->getSUnit() : nullptr;
}
void AggressiveAntiDepBreaker::HandleLastUse(unsigned Reg, unsigned KillIdx,
std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
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.
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,
// 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).
+ // 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)) {
+ TII->isPredicated(MI) || MI->isInlineAsm()) {
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 = TII->getRegClass(MI->getDesc(), i, TRI, MF);
AggressiveAntiDepState::RegisterReference RR = { &MO, RC };
continue;
// Update def for Reg and aliases.
- for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
+ 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;
+ }
}
}
// 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:
// changed.
bool Special = MI->isCall() ||
MI->hasExtraSrcRegAllocReq() ||
- TII->isPredicated(MI);
+ TII->isPredicated(MI) || MI->isInlineAsm();
// Scan the register uses for this instruction and update
// live-ranges, groups and RegRefs.
}
// Note register reference...
- const TargetRegisterClass *RC = NULL;
+ const TargetRegisterClass *RC = nullptr;
if (i < MI->getDesc().getNumOperands())
RC = TII->getRegClass(MI->getDesc(), i, TRI, MF);
AggressiveAntiDepState::RegisterReference RR = { &MO, RC };
// 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<std::multimap<unsigned,
- AggressiveAntiDepState::RegisterReference>::iterator,
- std::multimap<unsigned,
- AggressiveAntiDepState::RegisterReference>::iterator>
- Range = State->GetRegRefs().equal_range(Reg);
- for (std::multimap<unsigned,
- AggressiveAntiDepState::RegisterReference>::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) {
BV &= RCBV;
}
- DEBUG(dbgs() << " " << RC->getName());
+ DEBUG(dbgs() << " " << TRI->getRegClassName(RC));
}
return BV;
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;
}
DEBUG(dbgs() << "\tFind Registers:");
- if (RenameOrder.count(SuperRC) == 0)
- RenameOrder.insert(RenameOrderType::value_type(SuperRC, Order.size()));
+ RenameOrder.insert(RenameOrderType::value_type(SuperRC, Order.size()));
unsigned OrigR = RenameOrder[SuperRC];
unsigned EndR = ((OrigR == Order.size()) ? 0 : OrigR);
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<unsigned, unsigned>(Reg, NewReg));
}
// 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.
- const 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) {
const SUnit *SU = &SUnits[i];
// 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;
}
// 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");
} 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;
}
// Update the references to the old register CurrReg to
// refer to the new register NewReg.
- std::pair<std::multimap<unsigned,
- AggressiveAntiDepState::RegisterReference>::iterator,
- std::multimap<unsigned,
- AggressiveAntiDepState::RegisterReference>::iterator>
- Range = RegRefs.equal_range(CurrReg);
- for (std::multimap<unsigned,
- AggressiveAntiDepState::RegisterReference>::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()];
+ 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())
+ if (DVI->second == Q.second.Operand->getParent())
UpdateDbgValue(DVI->first, AntiDepReg, NewReg);
}