//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "critical-antidep"
+#define DEBUG_TYPE "post-RA-sched"
#include "CriticalAntiDepBreaker.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
using namespace llvm;
CriticalAntiDepBreaker::
-CriticalAntiDepBreaker(MachineFunction& MFi) :
+CriticalAntiDepBreaker(MachineFunction& MFi) :
AntiDepBreaker(), MF(MFi),
MRI(MF.getRegInfo()),
TRI(MF.getTarget().getRegisterInfo()),
static_cast<const TargetRegisterClass *>(0));
// Initialize the indices to indicate that no registers are live.
- std::fill(KillIndices, array_endof(KillIndices), ~0u);
- std::fill(DefIndices, array_endof(DefIndices), BB->size());
+ const unsigned BBSize = BB->size();
+ for (unsigned i = 0; i < TRI->getNumRegs(); ++i) {
+ KillIndices[i] = ~0u;
+ DefIndices[i] = BBSize;
+ }
// Clear "do not change" set.
KeepRegs.clear();
void CriticalAntiDepBreaker::Observe(MachineInstr *MI, unsigned Count,
unsigned InsertPosIndex) {
+ if (MI->isDebugValue())
+ return;
assert(Count < InsertPosIndex && "Instruction index out of expected range!");
// Any register which was defined within the previous scheduling region
// may have been rescheduled and its lifetime may overlap with registers
// in ways not reflected in our current liveness state. For each such
// register, adjust the liveness state to be conservatively correct.
- for (unsigned Reg = 0; Reg != TargetRegisterInfo::FirstVirtualRegister; ++Reg)
+ for (unsigned Reg = 0; Reg != TRI->getNumRegs(); ++Reg)
if (DefIndices[Reg] < InsertPosIndex && DefIndices[Reg] >= Count) {
assert(KillIndices[Reg] == ~0u && "Clobbered register is live!");
// Mark this register to be non-renamable.
/// CriticalPathStep - Return the next SUnit after SU on the bottom-up
/// critical path.
-static SDep *CriticalPathStep(SUnit *SU) {
- SDep *Next = 0;
+static const SDep *CriticalPathStep(const SUnit *SU) {
+ const SDep *Next = 0;
unsigned NextDepth = 0;
// Find the predecessor edge with the greatest depth.
- 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) {
- 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
unsigned Reg = MO.getReg();
if (Reg == 0) continue;
const TargetRegisterClass *NewRC = 0;
-
+
if (i < MI->getDesc().getNumOperands())
NewRC = MI->getDesc().OpInfo[i].getRegClass(TRI);
}
unsigned
-CriticalAntiDepBreaker::findSuitableFreeRegister(unsigned AntiDepReg,
+CriticalAntiDepBreaker::findSuitableFreeRegister(MachineInstr *MI,
+ unsigned AntiDepReg,
unsigned LastNewReg,
- const TargetRegisterClass *RC) {
+ const TargetRegisterClass *RC)
+{
for (TargetRegisterClass::iterator R = RC->allocation_order_begin(MF),
RE = RC->allocation_order_end(MF); R != RE; ++R) {
unsigned NewReg = *R;
// an anti-dependence with this AntiDepReg, because that would
// re-introduce that anti-dependence.
if (NewReg == LastNewReg) continue;
+ // If the instruction already has a def of the NewReg, it's not suitable.
+ // For example, Instruction with multiple definitions can result in this
+ // condition.
+ if (MI->modifiesRegister(NewReg, TRI)) continue;
// If NewReg is dead and NewReg's most recent def is not before
// AntiDepReg's kill, it's safe to replace AntiDepReg with NewReg.
- assert(((KillIndices[AntiDepReg] == ~0u) != (DefIndices[AntiDepReg] == ~0u)) &&
- "Kill and Def maps aren't consistent for AntiDepReg!");
- assert(((KillIndices[NewReg] == ~0u) != (DefIndices[NewReg] == ~0u)) &&
- "Kill and Def maps aren't consistent for NewReg!");
+ assert(((KillIndices[AntiDepReg] == ~0u) != (DefIndices[AntiDepReg] == ~0u))
+ && "Kill and Def maps aren't consistent for AntiDepReg!");
+ assert(((KillIndices[NewReg] == ~0u) != (DefIndices[NewReg] == ~0u))
+ && "Kill and Def maps aren't consistent for NewReg!");
if (KillIndices[NewReg] != ~0u ||
Classes[NewReg] == reinterpret_cast<TargetRegisterClass *>(-1) ||
KillIndices[AntiDepReg] > DefIndices[NewReg])
}
unsigned CriticalAntiDepBreaker::
-BreakAntiDependencies(std::vector<SUnit>& SUnits,
- MachineBasicBlock::iterator& Begin,
- MachineBasicBlock::iterator& End,
+BreakAntiDependencies(const std::vector<SUnit>& SUnits,
+ MachineBasicBlock::iterator Begin,
+ MachineBasicBlock::iterator End,
unsigned InsertPosIndex) {
// The code below assumes that there is at least one instruction,
// so just duck out immediately if the block is empty.
if (SUnits.empty()) return 0;
// Find the node at the bottom of the critical path.
- SUnit *Max = 0;
+ const SUnit *Max = 0;
for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
- SUnit *SU = &SUnits[i];
+ const SUnit *SU = &SUnits[i];
if (!Max || SU->getDepth() + SU->Latency > Max->getDepth() + Max->Latency)
Max = SU;
}
#ifndef NDEBUG
{
- DEBUG(errs() << "Critical path has total latency "
+ DEBUG(dbgs() << "Critical path has total latency "
<< (Max->getDepth() + Max->Latency) << "\n");
- DEBUG(errs() << "Available regs:");
+ DEBUG(dbgs() << "Available regs:");
for (unsigned Reg = 0; Reg < TRI->getNumRegs(); ++Reg) {
if (KillIndices[Reg] == ~0u)
- DEBUG(errs() << " " << TRI->getName(Reg));
+ DEBUG(dbgs() << " " << TRI->getName(Reg));
}
- DEBUG(errs() << '\n');
+ DEBUG(dbgs() << '\n');
}
#endif
// Track progress along the critical path through the SUnit graph as we walk
// the instructions.
- SUnit *CriticalPathSU = Max;
+ const SUnit *CriticalPathSU = Max;
MachineInstr *CriticalPathMI = CriticalPathSU->getInstr();
// Consider this pattern:
for (MachineBasicBlock::iterator I = End, E = Begin;
I != E; --Count) {
MachineInstr *MI = --I;
+ if (MI->isDebugValue())
+ continue;
// Check if this instruction has a dependence on the critical path that
// is an anti-dependence that we may be able to break. If it is, set
// breaking anti-dependence edges that aren't going to significantly
// impact the overall schedule. There are a limited number of registers
// and we want to save them for the important edges.
- //
+ //
// TODO: Instructions with multiple defs could have multiple
// anti-dependencies. The current code here only knows how to break one
// edge per instruction. Note that we'd have to be able to break all of
// the anti-dependencies in an instruction in order to be effective.
unsigned AntiDepReg = 0;
if (MI == CriticalPathMI) {
- if (SDep *Edge = CriticalPathStep(CriticalPathSU)) {
- SUnit *NextSU = Edge->getSUnit();
+ if (const SDep *Edge = CriticalPathStep(CriticalPathSU)) {
+ const SUnit *NextSU = Edge->getSUnit();
// Only consider anti-dependence edges.
if (Edge->getKind() == SDep::Anti) {
// 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 = CriticalPathSU->Preds.begin(),
+ for (SUnit::const_pred_iterator P = CriticalPathSU->Preds.begin(),
PE = CriticalPathSU->Preds.end(); P != PE; ++P)
if (P->getSUnit() == NextSU ?
(P->getKind() != SDep::Anti || P->getReg() != AntiDepReg) :
// TODO: Instead of picking the first free register, consider which might
// be the best.
if (AntiDepReg != 0) {
- if (unsigned NewReg = findSuitableFreeRegister(AntiDepReg,
+ if (unsigned NewReg = findSuitableFreeRegister(MI, AntiDepReg,
LastNewReg[AntiDepReg],
RC)) {
- DEBUG(errs() << "Breaking anti-dependence edge on "
+ DEBUG(dbgs() << "Breaking anti-dependence edge on "
<< TRI->getName(AntiDepReg)
<< " with " << RegRefs.count(AntiDepReg) << " references"
<< " using " << TRI->getName(NewReg) << "!\n");