//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "aggressive-antidep"
+#define DEBUG_TYPE "post-RA-sched"
#include "AggressiveAntiDepBreaker.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;
+// If DebugDiv > 0 then only break antidep with (ID % DebugDiv) == DebugMod
static cl::opt<int>
-AntiDepTrials("agg-antidep-trials",
- cl::desc("Maximum number of anti-dependency breaking passes"),
- cl::init(2), cl::Hidden);
-
-AggressiveAntiDepState::AggressiveAntiDepState(MachineBasicBlock *BB) :
- GroupNodes(TargetRegisterInfo::FirstVirtualRegister, 0) {
- // Initialize all registers to be in their own group. Initially we
- // assign the register to the same-indexed GroupNode.
- for (unsigned i = 0; i < TargetRegisterInfo::FirstVirtualRegister; ++i)
+DebugDiv("agg-antidep-debugdiv",
+ cl::desc("Debug control for aggressive anti-dep breaker"),
+ cl::init(0), cl::Hidden);
+static cl::opt<int>
+DebugMod("agg-antidep-debugmod",
+ 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) {
+
+ const unsigned BBSize = BB->size();
+ for (unsigned i = 0; i < NumTargetRegs; ++i) {
+ // Initialize all registers to be in their own group. Initially we
+ // assign the register to the same-indexed GroupNode.
GroupNodeIndices[i] = i;
-
- // 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());
+ // Initialize the indices to indicate that no registers are live.
+ KillIndices[i] = ~0u;
+ DefIndices[i] = BBSize;
+ }
}
unsigned AggressiveAntiDepState::GetGroup(unsigned Reg)
return Node;
}
-void AggressiveAntiDepState::GetGroupRegs(unsigned Group, std::vector<unsigned> &Regs)
+void AggressiveAntiDepState::GetGroupRegs(
+ unsigned Group,
+ std::vector<unsigned> &Regs,
+ std::multimap<unsigned, AggressiveAntiDepState::RegisterReference> *RegRefs)
{
- for (unsigned Reg = 0; Reg != TargetRegisterInfo::FirstVirtualRegister; ++Reg) {
- if (GetGroup(Reg) == Group)
+ for (unsigned Reg = 0; Reg != NumTargetRegs; ++Reg) {
+ if ((GetGroup(Reg) == Group) && (RegRefs->count(Reg) > 0))
Regs.push_back(Reg);
}
}
AggressiveAntiDepBreaker::
-AggressiveAntiDepBreaker(MachineFunction& MFi) :
+AggressiveAntiDepBreaker(MachineFunction& MFi,
+ TargetSubtarget::RegClassVector& CriticalPathRCs) :
AntiDepBreaker(), MF(MFi),
MRI(MF.getRegInfo()),
TRI(MF.getTarget().getRegisterInfo()),
AllocatableSet(TRI->getAllocatableSet(MF)),
- State(NULL), SavedState(NULL) {
+ State(NULL) {
+ /* 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) {
+ BitVector CPSet = TRI->getAllocatableSet(MF, CriticalPathRCs[i]);
+ if (CriticalPathSet.none())
+ CriticalPathSet = CPSet;
+ else
+ CriticalPathSet |= CPSet;
+ }
+
+ DEBUG(errs() << "AntiDep Critical-Path Registers:");
+ DEBUG(for (int r = CriticalPathSet.find_first(); r != -1;
+ r = CriticalPathSet.find_next(r))
+ errs() << " " << TRI->getName(r));
+ DEBUG(errs() << '\n');
}
AggressiveAntiDepBreaker::~AggressiveAntiDepBreaker() {
delete State;
- delete SavedState;
-}
-
-unsigned AggressiveAntiDepBreaker::GetMaxTrials() {
- if (AntiDepTrials <= 0)
- return 1;
- return AntiDepTrials;
}
void AggressiveAntiDepBreaker::StartBlock(MachineBasicBlock *BB) {
assert(State == NULL);
- State = new AggressiveAntiDepState(BB);
+ State = new AggressiveAntiDepState(TRI->getNumRegs(), BB);
bool IsReturnBlock = (!BB->empty() && BB->back().getDesc().isReturn());
unsigned *KillIndices = State->GetKillIndices();
void AggressiveAntiDepBreaker::FinishBlock() {
delete State;
State = NULL;
- delete SavedState;
- SavedState = NULL;
}
void AggressiveAntiDepBreaker::Observe(MachineInstr *MI, unsigned Count,
unsigned InsertPosIndex) {
assert(Count < InsertPosIndex && "Instruction index out of expected range!");
+ std::set<unsigned> PassthruRegs;
+ GetPassthruRegs(MI, PassthruRegs);
+ PrescanInstruction(MI, Count, PassthruRegs);
+ ScanInstruction(MI, Count);
+
DEBUG(errs() << "Observe: ");
DEBUG(MI->dump());
+ DEBUG(errs() << "\tRegs:");
unsigned *DefIndices = State->GetDefIndices();
- for (unsigned Reg = 0; Reg != TargetRegisterInfo::FirstVirtualRegister; ++Reg) {
+ 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
// has been scheduled). If it is not live but was defined in the
DefIndices[Reg] = Count;
}
}
-
- std::set<unsigned> PassthruRegs;
- GetPassthruRegs(MI, PassthruRegs);
- PrescanInstruction(MI, Count, PassthruRegs);
- ScanInstruction(MI, Count);
-
- // We're starting a new schedule region so forget any saved state.
- delete SavedState;
- SavedState = NULL;
+ DEBUG(errs() << '\n');
}
bool AggressiveAntiDepBreaker::IsImplicitDefUse(MachineInstr *MI,
}
}
-/// AntiDepPathStep - Return SUnit that SU has an anti-dependence on.
-static void AntiDepPathStep(SUnit *SU, std::vector<SDep*>& Edges) {
- SmallSet<unsigned, 8> Dups;
+/// 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<SDep*>& Edges) {
+ SmallSet<unsigned, 4> RegSet;
for (SUnit::pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end();
P != PE; ++P) {
- if (P->getKind() == SDep::Anti) {
+ if ((P->getKind() == SDep::Anti) || (P->getKind() == SDep::Output)) {
unsigned Reg = P->getReg();
- if (Dups.count(Reg) == 0) {
+ if (RegSet.count(Reg) == 0) {
Edges.push_back(&*P);
- Dups.insert(Reg);
+ RegSet.insert(Reg);
+ }
+ }
+ }
+}
+
+/// CriticalPathStep - Return the next SUnit after SU on the bottom-up
+/// critical path.
+static SUnit *CriticalPathStep(SUnit *SU) {
+ SDep *Next = 0;
+ 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();
+ P != PE; ++P) {
+ 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
+ // other types of edges.
+ if (NextDepth < PredTotalLatency ||
+ (NextDepth == PredTotalLatency && P->getKind() == SDep::Anti)) {
+ NextDepth = PredTotalLatency;
+ Next = &*P;
}
}
}
+
+ return (Next) ? Next->getSUnit() : 0;
}
void AggressiveAntiDepBreaker::HandleLastUse(unsigned Reg, unsigned KillIdx,
- const char *tag) {
+ const char *tag, const char *header,
+ const char *footer) {
unsigned *KillIndices = State->GetKillIndices();
unsigned *DefIndices = State->GetDefIndices();
std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
DefIndices[Reg] = ~0u;
RegRefs.erase(Reg);
State->LeaveGroup(Reg);
+ DEBUG(if (header != NULL) {
+ errs() << header << TRI->getName(Reg); header = NULL; });
DEBUG(errs() << "->g" << State->GetGroup(Reg) << tag);
}
// Repeat for subregisters.
DefIndices[SubregReg] = ~0u;
RegRefs.erase(SubregReg);
State->LeaveGroup(SubregReg);
+ DEBUG(if (header != NULL) {
+ errs() << header << TRI->getName(Reg); header = NULL; });
DEBUG(errs() << " " << TRI->getName(SubregReg) << "->g" <<
State->GetGroup(SubregReg) << tag);
}
}
+
+ DEBUG(if ((header == NULL) && (footer != NULL)) errs() << footer);
}
void AggressiveAntiDepBreaker::PrescanInstruction(MachineInstr *MI, unsigned Count,
unsigned Reg = MO.getReg();
if (Reg == 0) continue;
- DEBUG(errs() << "\tDead Def: " << TRI->getName(Reg));
- HandleLastUse(Reg, Count + 1, "");
- DEBUG(errs() << '\n');
+ HandleLastUse(Reg, Count + 1, "", "\tDead Def: ", "\n");
}
DEBUG(errs() << "\tDef Groups:");
if (!MO.isReg() || !MO.isDef()) continue;
unsigned Reg = MO.getReg();
if (Reg == 0) continue;
- // Ignore passthru registers for liveness...
- if (PassthruRegs.count(Reg) != 0) continue;
+ // Ignore KILLs and passthru registers for liveness...
+ if ((MI->getOpcode() == TargetInstrInfo::KILL) ||
+ (PassthruRegs.count(Reg) != 0))
+ continue;
- // Update def for Reg and subregs.
+ // Update def for Reg and aliases.
DefIndices[Reg] = Count;
- for (const unsigned *Subreg = TRI->getSubRegisters(Reg);
- *Subreg; ++Subreg) {
- unsigned SubregReg = *Subreg;
- DefIndices[SubregReg] = Count;
+ for (const unsigned *Alias = TRI->getAliasSet(Reg);
+ *Alias; ++Alias) {
+ unsigned AliasReg = *Alias;
+ DefIndices[AliasReg] = Count;
}
}
}
}
bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters(
- unsigned AntiDepGroupIndex,
- std::map<unsigned, unsigned> &RenameMap) {
+ unsigned AntiDepGroupIndex,
+ RenameOrderType& RenameOrder,
+ std::map<unsigned, unsigned> &RenameMap) {
unsigned *KillIndices = State->GetKillIndices();
unsigned *DefIndices = State->GetDefIndices();
std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
RegRefs = State->GetRegRefs();
- // Collect all registers in the same group as AntiDepReg. These all
- // need to be renamed together if we are to break the
- // anti-dependence.
+ // Collect all referenced registers in the same group as
+ // AntiDepReg. These all need to be renamed together if we are to
+ // break the anti-dependence.
std::vector<unsigned> Regs;
- State->GetGroupRegs(AntiDepGroupIndex, Regs);
+ State->GetGroupRegs(AntiDepGroupIndex, Regs, &RegRefs);
assert(Regs.size() > 0 && "Empty register group!");
if (Regs.size() == 0)
return false;
return false;
}
- // FIXME: for now just handle single register in group case...
- // FIXME: check only regs that have references...
- if (Regs.size() > 1)
+#ifndef NDEBUG
+ // If DebugDiv > 0 then only rename (renamecnt % DebugDiv) == DebugMod
+ if (DebugDiv > 0) {
+ static int renamecnt = 0;
+ if (renamecnt++ % DebugDiv != DebugMod)
+ return false;
+
+ errs() << "*** Performing rename " << TRI->getName(SuperReg) <<
+ " for debug ***\n";
+ }
+#endif
+
+ // Check each possible rename register for SuperReg in round-robin
+ // 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.
+ const TargetRegisterClass *SuperRC =
+ TRI->getPhysicalRegisterRegClass(SuperReg, MVT::Other);
+
+ const TargetRegisterClass::iterator RB = SuperRC->allocation_order_begin(MF);
+ const TargetRegisterClass::iterator RE = SuperRC->allocation_order_end(MF);
+ if (RB == RE) {
+ DEBUG(errs() << "\tEmpty Super Regclass!!\n");
return false;
+ }
+
+ DEBUG(errs() << "\tFind Registers:");
- // Check each possible rename register for SuperReg. If that register
- // is available, and the corresponding registers are available for
- // the other group subregisters, then we can use those registers to
- // rename.
- DEBUG(errs() << "\tFind Register:");
- BitVector SuperBV = RenameRegisterMap[SuperReg];
- for (int r = SuperBV.find_first(); r != -1; r = SuperBV.find_next(r)) {
- const unsigned Reg = (unsigned)r;
+ if (RenameOrder.count(SuperRC) == 0)
+ RenameOrder.insert(RenameOrderType::value_type(SuperRC, RE));
+
+ const TargetRegisterClass::iterator OrigR = RenameOrder[SuperRC];
+ const TargetRegisterClass::iterator EndR = ((OrigR == RE) ? RB : OrigR);
+ TargetRegisterClass::iterator R = OrigR;
+ do {
+ if (R == RB) R = RE;
+ --R;
+ const unsigned NewSuperReg = *R;
// Don't replace a register with itself.
- if (Reg == SuperReg) continue;
+ if (NewSuperReg == SuperReg) continue;
+
+ DEBUG(errs() << " [" << TRI->getName(NewSuperReg) << ':');
+ RenameMap.clear();
+
+ // For each referenced group register (which must be a SuperReg or
+ // a subregister of SuperReg), find the corresponding subregister
+ // of NewSuperReg and make sure it is free to be renamed.
+ for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
+ unsigned Reg = Regs[i];
+ unsigned NewReg = 0;
+ if (Reg == SuperReg) {
+ NewReg = NewSuperReg;
+ } else {
+ unsigned NewSubRegIdx = TRI->getSubRegIndex(SuperReg, Reg);
+ if (NewSubRegIdx != 0)
+ NewReg = TRI->getSubReg(NewSuperReg, NewSubRegIdx);
+ }
- DEBUG(errs() << " " << TRI->getName(Reg));
+ DEBUG(errs() << " " << TRI->getName(NewReg));
- // If Reg is dead and Reg's most recent def is not before
- // SuperRegs's kill, it's safe to replace SuperReg with
- // Reg. We must also check all subregisters of Reg.
- if (State->IsLive(Reg) || (KillIndices[SuperReg] > DefIndices[Reg])) {
- DEBUG(errs() << "(live)");
- continue;
- } else {
- bool found = false;
- for (const unsigned *Subreg = TRI->getSubRegisters(Reg);
- *Subreg; ++Subreg) {
- unsigned SubregReg = *Subreg;
- if (State->IsLive(SubregReg) || (KillIndices[SuperReg] > DefIndices[SubregReg])) {
- DEBUG(errs() << "(subreg " << TRI->getName(SubregReg) << " live)");
- found = true;
- break;
+ // Check if Reg can be renamed to NewReg.
+ BitVector BV = RenameRegisterMap[Reg];
+ if (!BV.test(NewReg)) {
+ DEBUG(errs() << "(no rename)");
+ goto next_super_reg;
+ }
+
+ // If NewReg is dead and NewReg's most recent def is not before
+ // Regs's kill, it's safe to replace Reg with NewReg. We
+ // must also check all aliases of NewReg, because we can't define a
+ // register when any sub or super is already live.
+ if (State->IsLive(NewReg) || (KillIndices[Reg] > DefIndices[NewReg])) {
+ DEBUG(errs() << "(live)");
+ goto next_super_reg;
+ } else {
+ bool found = false;
+ for (const unsigned *Alias = TRI->getAliasSet(NewReg);
+ *Alias; ++Alias) {
+ unsigned AliasReg = *Alias;
+ if (State->IsLive(AliasReg) || (KillIndices[Reg] > DefIndices[AliasReg])) {
+ DEBUG(errs() << "(alias " << TRI->getName(AliasReg) << " live)");
+ found = true;
+ break;
+ }
}
+ if (found)
+ goto next_super_reg;
}
- if (found)
- continue;
- }
- if (Reg != 0) {
- DEBUG(errs() << '\n');
- RenameMap.insert(std::pair<unsigned, unsigned>(SuperReg, Reg));
- return true;
+ // Record that 'Reg' can be renamed to 'NewReg'.
+ RenameMap.insert(std::pair<unsigned, unsigned>(Reg, NewReg));
}
- }
+
+ // If we fall-out here, then every register in the group can be
+ // renamed, as recorded in RenameMap.
+ RenameOrder.erase(SuperRC);
+ RenameOrder.insert(RenameOrderType::value_type(SuperRC, R));
+ DEBUG(errs() << "]\n");
+ return true;
+
+ next_super_reg:
+ DEBUG(errs() << ']');
+ } while (R != EndR);
DEBUG(errs() << '\n');
// 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 false;
+ if (SUnits.empty()) return 0;
- // Manage saved state to enable multiple passes...
- if (AntiDepTrials > 1) {
- if (SavedState == NULL) {
- SavedState = new AggressiveAntiDepState(*State);
- } else {
- delete State;
- State = new AggressiveAntiDepState(*SavedState);
- }
- }
+ // For each regclass the next register to use for renaming.
+ RenameOrderType RenameOrder;
// ...need a map from MI to SUnit.
std::map<MachineInstr *, SUnit *> MISUnitMap;
-
- DEBUG(errs() << "Breaking all anti-dependencies\n");
for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
SUnit *SU = &SUnits[i];
MISUnitMap.insert(std::pair<MachineInstr *, SUnit *>(SU->getInstr(), SU));
}
-#ifndef NDEBUG
- {
- DEBUG(errs() << "Available regs:");
- for (unsigned Reg = 0; Reg < TRI->getNumRegs(); ++Reg) {
- if (!State->IsLive(Reg))
- DEBUG(errs() << " " << TRI->getName(Reg));
+ // 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;
+ if (CriticalPathSet.any()) {
+ for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
+ SUnit *SU = &SUnits[i];
+ if (!CriticalPathSU ||
+ ((SU->getDepth() + SU->Latency) >
+ (CriticalPathSU->getDepth() + CriticalPathSU->Latency))) {
+ CriticalPathSU = SU;
+ }
}
- DEBUG(errs() << '\n');
+
+ CriticalPathMI = CriticalPathSU->getInstr();
}
+
+#ifndef NDEBUG
+ DEBUG(errs() << "\n===== Aggressive anti-dependency breaking\n");
+ DEBUG(errs() << "Available regs:");
+ for (unsigned Reg = 0; Reg < TRI->getNumRegs(); ++Reg) {
+ if (!State->IsLive(Reg))
+ DEBUG(errs() << " " << TRI->getName(Reg));
+ }
+ DEBUG(errs() << '\n');
#endif
// Attempt to break anti-dependence edges. Walk the instructions
// Process the defs in MI...
PrescanInstruction(MI, Count, PassthruRegs);
-
+
+ // The dependence edges that represent anti- and output-
+ // dependencies that are candidates for breaking.
std::vector<SDep*> Edges;
SUnit *PathSU = MISUnitMap[MI];
- if (PathSU)
- AntiDepPathStep(PathSU, Edges);
-
+ AntiDepEdges(PathSU, Edges);
+
+ // If MI is not on the critical path, then we don't rename
+ // registers in the CriticalPathSet.
+ BitVector *ExcludeRegs = NULL;
+ if (MI == CriticalPathMI) {
+ CriticalPathSU = CriticalPathStep(CriticalPathSU);
+ CriticalPathMI = (CriticalPathSU) ? CriticalPathSU->getInstr() : 0;
+ } else {
+ ExcludeRegs = &CriticalPathSet;
+ }
+
// Ignore KILL instructions (they form a group in ScanInstruction
// but don't cause any anti-dependence breaking themselves)
if (MI->getOpcode() != TargetInstrInfo::KILL) {
SDep *Edge = Edges[i];
SUnit *NextSU = Edge->getSUnit();
- if (Edge->getKind() != SDep::Anti) continue;
+ if ((Edge->getKind() != SDep::Anti) &&
+ (Edge->getKind() != SDep::Output)) continue;
unsigned AntiDepReg = Edge->getReg();
DEBUG(errs() << "\tAntidep reg: " << TRI->getName(AntiDepReg));
// Don't break anti-dependencies on non-allocatable registers.
DEBUG(errs() << " (non-allocatable)\n");
continue;
+ } else if ((ExcludeRegs != NULL) && ExcludeRegs->test(AntiDepReg)) {
+ // Don't break anti-dependencies for critical path registers
+ // if not on the critical path
+ DEBUG(errs() << " (not critical-path)\n");
+ continue;
} else if (PassthruRegs.count(AntiDepReg) != 0) {
// If the anti-dep register liveness "passes-thru", then
// don't try to change it. It will be changed along with
// anti-dependency since those edges would prevent such
// units from being scheduled past each other
// regardless.
+ //
+ // 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(),
PE = PathSU->Preds.end(); P != PE; ++P) {
- if ((P->getSUnit() == NextSU) && (P->getKind() != SDep::Anti)) {
+ if (P->getSUnit() == NextSU ?
+ (P->getKind() != SDep::Anti || P->getReg() != AntiDepReg) :
+ (P->getKind() == SDep::Data && P->getReg() == AntiDepReg)) {
+ AntiDepReg = 0;
+ break;
+ }
+ }
+ for (SUnit::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)) {
DEBUG(errs() << " (real dependency)\n");
AntiDepReg = 0;
break;
+ } else if ((P->getSUnit() != NextSU) &&
+ (P->getKind() == SDep::Data) &&
+ (P->getReg() == AntiDepReg)) {
+ DEBUG(errs() << " (other dependency)\n");
+ AntiDepReg = 0;
+ break;
}
}
// Look for a suitable register to use to break the anti-dependence.
std::map<unsigned, unsigned> RenameMap;
- if (FindSuitableFreeRegisters(GroupIndex, RenameMap)) {
+ if (FindSuitableFreeRegisters(GroupIndex, RenameOrder, RenameMap)) {
DEBUG(errs() << "\tBreaking anti-dependence edge on "
<< TRI->getName(AntiDepReg) << ":");
projects / oota-llvm.git / blobdiff