From 87d21b92fc42f6b3bd8567a83fc5b5191c1205e5 Mon Sep 17 00:00:00 2001 From: David Goodwin Date: Fri, 13 Nov 2009 19:52:48 +0000 Subject: [PATCH] Allow target to specify regclass for which antideps will only be broken along the critical path. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@88682 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Target/TargetSubtarget.h | 8 +- lib/CodeGen/AggressiveAntiDepBreaker.cpp | 120 ++++++++++++++++++----- lib/CodeGen/AggressiveAntiDepBreaker.h | 15 ++- lib/CodeGen/PostRASchedulerList.cpp | 6 +- lib/Target/ARM/ARMSubtarget.cpp | 6 +- lib/Target/ARM/ARMSubtarget.h | 2 +- lib/Target/TargetSubtarget.cpp | 4 +- lib/Target/X86/X86Subtarget.cpp | 4 +- lib/Target/X86/X86Subtarget.h | 2 +- 9 files changed, 123 insertions(+), 44 deletions(-) diff --git a/include/llvm/Target/TargetSubtarget.h b/include/llvm/Target/TargetSubtarget.h index f16c9e4ae6d..22b09bac073 100644 --- a/include/llvm/Target/TargetSubtarget.h +++ b/include/llvm/Target/TargetSubtarget.h @@ -38,7 +38,7 @@ public: // AntiDepBreakMode - Type of anti-dependence breaking that should // be performed before post-RA scheduling. typedef enum { ANTIDEP_NONE, ANTIDEP_CRITICAL, ANTIDEP_ALL } AntiDepBreakMode; - typedef SmallVectorImpl ExcludedRCVector; + typedef SmallVectorImpl RegClassVector; virtual ~TargetSubtarget(); @@ -50,10 +50,12 @@ public: // enablePostRAScheduler - If the target can benefit from post-regalloc // scheduling and the specified optimization level meets the requirement - // return true to enable post-register-allocation scheduling. + // return true to enable post-register-allocation scheduling. In + // CriticalPathRCs return any register classes that should only be broken + // if on the critical path. virtual bool enablePostRAScheduler(CodeGenOpt::Level OptLevel, AntiDepBreakMode& Mode, - ExcludedRCVector& ExcludedRCs) const; + RegClassVector& CriticalPathRCs) const; // adjustSchedDependency - Perform target specific adjustments to // the latency of a schedule dependency. virtual void adjustSchedDependency(SUnit *def, SUnit *use, diff --git a/lib/CodeGen/AggressiveAntiDepBreaker.cpp b/lib/CodeGen/AggressiveAntiDepBreaker.cpp index b8cea27e515..c37c793b56d 100644 --- a/lib/CodeGen/AggressiveAntiDepBreaker.cpp +++ b/lib/CodeGen/AggressiveAntiDepBreaker.cpp @@ -54,10 +54,13 @@ unsigned AggressiveAntiDepState::GetGroup(unsigned Reg) return Node; } -void AggressiveAntiDepState::GetGroupRegs(unsigned Group, std::vector &Regs) +void AggressiveAntiDepState::GetGroupRegs( + unsigned Group, + std::vector &Regs, + std::multimap *RegRefs) { for (unsigned Reg = 0; Reg != TargetRegisterInfo::FirstVirtualRegister; ++Reg) { - if (GetGroup(Reg) == Group) + if ((GetGroup(Reg) == Group) && (RegRefs->count(Reg) > 0)) Regs.push_back(Reg); } } @@ -100,23 +103,27 @@ bool AggressiveAntiDepState::IsLive(unsigned Reg) AggressiveAntiDepBreaker:: AggressiveAntiDepBreaker(MachineFunction& MFi, - TargetSubtarget::ExcludedRCVector& ExcludedRCs) : + TargetSubtarget::RegClassVector& CriticalPathRCs) : AntiDepBreaker(), MF(MFi), MRI(MF.getRegInfo()), TRI(MF.getTarget().getRegisterInfo()), AllocatableSet(TRI->getAllocatableSet(MF)), State(NULL), SavedState(NULL) { - /* Remove all registers from excluded RCs from the allocatable - register set. */ - for (unsigned i = 0, e = ExcludedRCs.size(); i < e; ++i) { - BitVector NotRenameable = TRI->getAllocatableSet(MF, ExcludedRCs[i]).flip(); - AllocatableSet &= NotRenameable; - } - - DEBUG(errs() << "AntiDep Renameable Registers:"); - DEBUG(for (int r = AllocatableSet.find_first(); r != -1; - r = AllocatableSet.find_next(r)) + /* 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() { @@ -276,9 +283,11 @@ void AggressiveAntiDepBreaker::GetPassthruRegs(MachineInstr *MI, } } -/// AntiDepPathStep - Return SUnit that SU has an anti-dependence on. -static void AntiDepPathStep(SUnit *SU, AntiDepBreaker::AntiDepRegVector& Regs, - std::vector& Edges) { +/// AntiDepEdges - Return in Edges the anti- and output- +/// dependencies on Regs in SU that we want to consider for breaking. +static void AntiDepEdges(SUnit *SU, + const AntiDepBreaker::AntiDepRegVector& Regs, + std::vector& Edges) { AntiDepBreaker::AntiDepRegSet RegSet; for (unsigned i = 0, e = Regs.size(); i < e; ++i) RegSet.insert(Regs[i]); @@ -297,6 +306,31 @@ static void AntiDepPathStep(SUnit *SU, AntiDepBreaker::AntiDepRegVector& Regs, assert(RegSet.empty() && "Expected all antidep registers to be found"); } +/// 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) { unsigned *KillIndices = State->GetKillIndices(); @@ -511,11 +545,11 @@ bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters( std::multimap& 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 Regs; - State->GetGroupRegs(AntiDepGroupIndex, Regs); + State->GetGroupRegs(AntiDepGroupIndex, Regs, &RegRefs); assert(Regs.size() > 0 && "Empty register group!"); if (Regs.size() == 0) return false; @@ -556,9 +590,10 @@ bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters( } // FIXME: for now just handle single register in group case... - // FIXME: check only regs that have references... - if (Regs.size() > 1) + if (Regs.size() > 1) { + DEBUG(errs() << "\tMultiple rename registers in group\n"); return false; + } // Check each possible rename register for SuperReg in round-robin // order. If that register is available, and the corresponding @@ -666,6 +701,24 @@ unsigned AggressiveAntiDepBreaker::BreakAntiDependencies( 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; + 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; + } + } + + CriticalPathMI = CriticalPathSU->getInstr(); + } + // Even if there are no anti-dependencies we still need to go // through the instructions to update Def, Kills, etc. #ifndef NDEBUG @@ -700,14 +753,26 @@ unsigned AggressiveAntiDepBreaker::BreakAntiDependencies( // Process the defs in MI... PrescanInstruction(MI, Count, PassthruRegs); - + + // The the dependence edges that represent anti- and output- + // dependencies that are candidates for breaking. std::vector Edges; SUnit *PathSU = MISUnitMap[MI]; AntiDepBreaker::CandidateMap::iterator citer = Candidates.find(PathSU); if (citer != Candidates.end()) - AntiDepPathStep(PathSU, citer->second, Edges); - + AntiDepEdges(PathSU, citer->second, 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) { @@ -727,6 +792,11 @@ unsigned AggressiveAntiDepBreaker::BreakAntiDependencies( // 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 diff --git a/lib/CodeGen/AggressiveAntiDepBreaker.h b/lib/CodeGen/AggressiveAntiDepBreaker.h index fb5b869fcba..e5c9a7bb3ad 100644 --- a/lib/CodeGen/AggressiveAntiDepBreaker.h +++ b/lib/CodeGen/AggressiveAntiDepBreaker.h @@ -86,8 +86,11 @@ namespace llvm { unsigned GetGroup(unsigned Reg); // GetGroupRegs - Return a vector of the registers belonging to a - // group. - void GetGroupRegs(unsigned Group, std::vector &Regs); + // group. If RegRefs is non-NULL then only included referenced registers. + void GetGroupRegs( + unsigned Group, + std::vector &Regs, + std::multimap *RegRefs); // UnionGroups - Union Reg1's and Reg2's groups to form a new // group. Return the index of the GroupNode representing the @@ -113,7 +116,11 @@ namespace llvm { /// AllocatableSet - The set of allocatable registers. /// We'll be ignoring anti-dependencies on non-allocatable registers, /// because they may not be safe to break. - BitVector AllocatableSet; + const BitVector AllocatableSet; + + /// CriticalPathSet - The set of registers that should only be + /// renamed if they are on the critical path. + BitVector CriticalPathSet; /// State - The state used to identify and rename anti-dependence /// registers. @@ -126,7 +133,7 @@ namespace llvm { public: AggressiveAntiDepBreaker(MachineFunction& MFi, - TargetSubtarget::ExcludedRCVector& ExcludedRCs); + TargetSubtarget::RegClassVector& CriticalPathRCs); ~AggressiveAntiDepBreaker(); /// GetMaxTrials - As anti-dependencies are broken, additional diff --git a/lib/CodeGen/PostRASchedulerList.cpp b/lib/CodeGen/PostRASchedulerList.cpp index a29f349b0b5..5f1f1f3580c 100644 --- a/lib/CodeGen/PostRASchedulerList.cpp +++ b/lib/CodeGen/PostRASchedulerList.cpp @@ -216,14 +216,14 @@ bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { // Check for explicit enable/disable of post-ra scheduling. TargetSubtarget::AntiDepBreakMode AntiDepMode = TargetSubtarget::ANTIDEP_NONE; - SmallVector ExcludedRCs; + SmallVector CriticalPathRCs; if (EnablePostRAScheduler.getPosition() > 0) { if (!EnablePostRAScheduler) return false; } else { // Check that post-RA scheduling is enabled for this target. const TargetSubtarget &ST = Fn.getTarget().getSubtarget(); - if (!ST.enablePostRAScheduler(OptLevel, AntiDepMode, ExcludedRCs)) + if (!ST.enablePostRAScheduler(OptLevel, AntiDepMode, CriticalPathRCs)) return false; } @@ -244,7 +244,7 @@ bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { (ScheduleHazardRecognizer *)new SimpleHazardRecognizer(); AntiDepBreaker *ADB = ((AntiDepMode == TargetSubtarget::ANTIDEP_ALL) ? - (AntiDepBreaker *)new AggressiveAntiDepBreaker(Fn, ExcludedRCs) : + (AntiDepBreaker *)new AggressiveAntiDepBreaker(Fn, CriticalPathRCs) : ((AntiDepMode == TargetSubtarget::ANTIDEP_CRITICAL) ? (AntiDepBreaker *)new CriticalAntiDepBreaker(Fn) : NULL)); diff --git a/lib/Target/ARM/ARMSubtarget.cpp b/lib/Target/ARM/ARMSubtarget.cpp index dc813289e73..87b78a9ee5c 100644 --- a/lib/Target/ARM/ARMSubtarget.cpp +++ b/lib/Target/ARM/ARMSubtarget.cpp @@ -164,9 +164,9 @@ ARMSubtarget::GVIsIndirectSymbol(GlobalValue *GV, Reloc::Model RelocM) const { bool ARMSubtarget::enablePostRAScheduler( CodeGenOpt::Level OptLevel, TargetSubtarget::AntiDepBreakMode& Mode, - ExcludedRCVector& ExcludedRCs) const { + RegClassVector& CriticalPathRCs) const { Mode = TargetSubtarget::ANTIDEP_CRITICAL; - ExcludedRCs.clear(); - ExcludedRCs.push_back(&ARM::GPRRegClass); + CriticalPathRCs.clear(); + CriticalPathRCs.push_back(&ARM::GPRRegClass); return PostRAScheduler && OptLevel >= CodeGenOpt::Default; } diff --git a/lib/Target/ARM/ARMSubtarget.h b/lib/Target/ARM/ARMSubtarget.h index fd66693675a..a95c8a5ccff 100644 --- a/lib/Target/ARM/ARMSubtarget.h +++ b/lib/Target/ARM/ARMSubtarget.h @@ -130,7 +130,7 @@ protected: /// enablePostRAScheduler - True at 'More' optimization. bool enablePostRAScheduler(CodeGenOpt::Level OptLevel, TargetSubtarget::AntiDepBreakMode& Mode, - ExcludedRCVector& ExcludedRCs) const; + RegClassVector& CriticalPathRCs) const; /// getInstrItins - Return the instruction itineraies based on subtarget /// selection. diff --git a/lib/Target/TargetSubtarget.cpp b/lib/Target/TargetSubtarget.cpp index 696c09b52f8..edb76f97153 100644 --- a/lib/Target/TargetSubtarget.cpp +++ b/lib/Target/TargetSubtarget.cpp @@ -25,9 +25,9 @@ TargetSubtarget::~TargetSubtarget() {} bool TargetSubtarget::enablePostRAScheduler( CodeGenOpt::Level OptLevel, AntiDepBreakMode& Mode, - ExcludedRCVector& ExcludedRCs) const { + RegClassVector& CriticalPathRCs) const { Mode = ANTIDEP_NONE; - ExcludedRCs.clear(); + CriticalPathRCs.clear(); return false; } diff --git a/lib/Target/X86/X86Subtarget.cpp b/lib/Target/X86/X86Subtarget.cpp index a7233b52b24..893640561cd 100644 --- a/lib/Target/X86/X86Subtarget.cpp +++ b/lib/Target/X86/X86Subtarget.cpp @@ -460,8 +460,8 @@ X86Subtarget::X86Subtarget(const std::string &TT, const std::string &FS, bool X86Subtarget::enablePostRAScheduler( CodeGenOpt::Level OptLevel, TargetSubtarget::AntiDepBreakMode& Mode, - ExcludedRCVector& ExcludedRCs) const { + RegClassVector& CriticalPathRCs) const { Mode = TargetSubtarget::ANTIDEP_CRITICAL; - ExcludedRCs.clear(); + CriticalPathRCs.clear(); return OptLevel >= CodeGenOpt::Default; } diff --git a/lib/Target/X86/X86Subtarget.h b/lib/Target/X86/X86Subtarget.h index a0eef0551e5..23f2841a8c2 100644 --- a/lib/Target/X86/X86Subtarget.h +++ b/lib/Target/X86/X86Subtarget.h @@ -220,7 +220,7 @@ public: /// at 'More' optimization level. bool enablePostRAScheduler(CodeGenOpt::Level OptLevel, TargetSubtarget::AntiDepBreakMode& Mode, - ExcludedRCVector& ExcludedRCs) const; + RegClassVector& CriticalPathRCs) const; }; } // End llvm namespace -- 2.34.1