diff options
Diffstat (limited to 'gnu/llvm/lib/CodeGen/AggressiveAntiDepBreaker.cpp')
| -rw-r--r-- | gnu/llvm/lib/CodeGen/AggressiveAntiDepBreaker.cpp | 1014 |
1 files changed, 0 insertions, 1014 deletions
diff --git a/gnu/llvm/lib/CodeGen/AggressiveAntiDepBreaker.cpp b/gnu/llvm/lib/CodeGen/AggressiveAntiDepBreaker.cpp deleted file mode 100644 index 632ea8e9cdc..00000000000 --- a/gnu/llvm/lib/CodeGen/AggressiveAntiDepBreaker.cpp +++ /dev/null @@ -1,1014 +0,0 @@ -//===- AggressiveAntiDepBreaker.cpp - Anti-dep breaker --------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements the AggressiveAntiDepBreaker class, which -// implements register anti-dependence breaking during post-RA -// scheduling. It attempts to break all anti-dependencies within a -// block. -// -//===----------------------------------------------------------------------===// - -#include "AggressiveAntiDepBreaker.h" -#include "llvm/ADT/ArrayRef.h" -#include "llvm/ADT/BitVector.h" -#include "llvm/ADT/SmallSet.h" -#include "llvm/ADT/iterator_range.h" -#include "llvm/CodeGen/MachineBasicBlock.h" -#include "llvm/CodeGen/MachineFrameInfo.h" -#include "llvm/CodeGen/MachineFunction.h" -#include "llvm/CodeGen/MachineInstr.h" -#include "llvm/CodeGen/MachineOperand.h" -#include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/CodeGen/RegisterClassInfo.h" -#include "llvm/CodeGen/ScheduleDAG.h" -#include "llvm/CodeGen/TargetInstrInfo.h" -#include "llvm/CodeGen/TargetRegisterInfo.h" -#include "llvm/CodeGen/TargetSubtargetInfo.h" -#include "llvm/MC/MCInstrDesc.h" -#include "llvm/MC/MCRegisterInfo.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/MachineValueType.h" -#include "llvm/Support/raw_ostream.h" -#include <cassert> -#include <map> -#include <set> -#include <utility> -#include <vector> - -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", - 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), - 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 - // assign the register to the same-indexed GroupNode. - GroupNodeIndices[i] = i; - // Initialize the indices to indicate that no registers are live. - KillIndices[i] = ~0u; - DefIndices[i] = BBSize; - } -} - -unsigned AggressiveAntiDepState::GetGroup(unsigned Reg) { - unsigned Node = GroupNodeIndices[Reg]; - while (GroupNodes[Node] != Node) - Node = GroupNodes[Node]; - - return Node; -} - -void AggressiveAntiDepState::GetGroupRegs( - unsigned Group, - std::vector<unsigned> &Regs, - std::multimap<unsigned, AggressiveAntiDepState::RegisterReference> *RegRefs) -{ - for (unsigned Reg = 0; Reg != NumTargetRegs; ++Reg) { - if ((GetGroup(Reg) == Group) && (RegRefs->count(Reg) > 0)) - Regs.push_back(Reg); - } -} - -unsigned AggressiveAntiDepState::UnionGroups(unsigned Reg1, unsigned Reg2) { - assert(GroupNodes[0] == 0 && "GroupNode 0 not parent!"); - assert(GroupNodeIndices[0] == 0 && "Reg 0 not in Group 0!"); - - // find group for each register - unsigned Group1 = GetGroup(Reg1); - unsigned Group2 = GetGroup(Reg2); - - // if either group is 0, then that must become the parent - unsigned Parent = (Group1 == 0) ? Group1 : Group2; - unsigned Other = (Parent == Group1) ? Group2 : Group1; - GroupNodes.at(Other) = Parent; - return Parent; -} - -unsigned AggressiveAntiDepState::LeaveGroup(unsigned Reg) { - // Create a new GroupNode for Reg. Reg's existing GroupNode must - // stay as is because there could be other GroupNodes referring to - // it. - unsigned idx = GroupNodes.size(); - GroupNodes.push_back(idx); - GroupNodeIndices[Reg] = idx; - return idx; -} - -bool AggressiveAntiDepState::IsLive(unsigned Reg) { - // KillIndex must be defined and DefIndex not defined for a register - // to be live. - 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.getSubtarget().getInstrInfo()), - TRI(MF.getSubtarget().getRegisterInfo()), RegClassInfo(RCI) { - /* 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; - } - - LLVM_DEBUG(dbgs() << "AntiDep Critical-Path Registers:"); - LLVM_DEBUG(for (unsigned r - : CriticalPathSet.set_bits()) dbgs() - << " " << printReg(r, TRI)); - LLVM_DEBUG(dbgs() << '\n'); -} - -AggressiveAntiDepBreaker::~AggressiveAntiDepBreaker() { - delete State; -} - -void AggressiveAntiDepBreaker::StartBlock(MachineBasicBlock *BB) { - assert(!State); - State = new AggressiveAntiDepState(TRI->getNumRegs(), BB); - - 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 (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; - } - } - - // 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(MF); - for (const MCPhysReg *I = MF.getRegInfo().getCalleeSavedRegs(); *I; - ++I) { - unsigned Reg = *I; - if (!IsReturnBlock && !Pristine.test(Reg)) - continue; - for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { - unsigned AliasReg = *AI; - State->UnionGroups(AliasReg, 0); - KillIndices[AliasReg] = BB->size(); - DefIndices[AliasReg] = ~0u; - } - } -} - -void AggressiveAntiDepBreaker::FinishBlock() { - delete State; - State = nullptr; -} - -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); - - LLVM_DEBUG(dbgs() << "Observe: "); - LLVM_DEBUG(MI.dump()); - LLVM_DEBUG(dbgs() << "\tRegs:"); - - std::vector<unsigned> &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 - // has been scheduled). If it is not live but was defined in the - // previous schedule region, then set its def index to the most - // conservative location (i.e. the beginning of the previous - // schedule region). - if (State->IsLive(Reg)) { - LLVM_DEBUG(if (State->GetGroup(Reg) != 0) dbgs() - << " " << printReg(Reg, TRI) << "=g" << State->GetGroup(Reg) - << "->g0(region live-out)"); - State->UnionGroups(Reg, 0); - } else if ((DefIndices[Reg] < InsertPosIndex) - && (DefIndices[Reg] >= Count)) { - DefIndices[Reg] = Count; - } - } - LLVM_DEBUG(dbgs() << '\n'); -} - -bool AggressiveAntiDepBreaker::IsImplicitDefUse(MachineInstr &MI, - MachineOperand &MO) { - if (!MO.isReg() || !MO.isImplicit()) - return false; - - unsigned Reg = MO.getReg(); - if (Reg == 0) - return false; - - MachineOperand *Op = nullptr; - if (MO.isDef()) - Op = MI.findRegisterUseOperand(Reg, true); - else - Op = MI.findRegisterDefOperand(Reg); - - return(Op && Op->isImplicit()); -} - -void AggressiveAntiDepBreaker::GetPassthruRegs( - MachineInstr &MI, std::set<unsigned> &PassthruRegs) { - for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { - MachineOperand &MO = MI.getOperand(i); - if (!MO.isReg()) continue; - if ((MO.isDef() && MI.isRegTiedToUseOperand(i)) || - IsImplicitDefUse(MI, MO)) { - const unsigned Reg = MO.getReg(); - 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(const SUnit *SU, std::vector<const SDep *> &Edges) { - SmallSet<unsigned, 4> RegSet; - 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)) { - if (RegSet.insert(P->getReg()).second) - Edges.push_back(&*P); - } - } -} - -/// CriticalPathStep - Return the next SUnit after SU on the bottom-up -/// critical path. -static const SUnit *CriticalPathStep(const SUnit *SU) { - const SDep *Next = nullptr; - unsigned NextDepth = 0; - // Find the predecessor edge with the greatest depth. - if (SU) { - for (SUnit::const_pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end(); - P != PE; ++P) { - 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 - // other types of edges. - if (NextDepth < PredTotalLatency || - (NextDepth == PredTotalLatency && P->getKind() == SDep::Anti)) { - NextDepth = PredTotalLatency; - Next = &*P; - } - } - } - - return (Next) ? Next->getSUnit() : nullptr; -} - -void AggressiveAntiDepBreaker::HandleLastUse(unsigned Reg, unsigned KillIdx, - const char *tag, - const char *header, - const char *footer) { - std::vector<unsigned> &KillIndices = State->GetKillIndices(); - std::vector<unsigned> &DefIndices = State->GetDefIndices(); - 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)) { - LLVM_DEBUG(if (!header && footer) dbgs() << footer); - return; - } - - if (!State->IsLive(Reg)) { - KillIndices[Reg] = KillIdx; - DefIndices[Reg] = ~0u; - RegRefs.erase(Reg); - State->LeaveGroup(Reg); - LLVM_DEBUG(if (header) { - dbgs() << header << printReg(Reg, TRI); - header = nullptr; - }); - LLVM_DEBUG(dbgs() << "->g" << State->GetGroup(Reg) << tag); - // Repeat for subregisters. Note that we only do this if the superregister - // was not live because otherwise, regardless whether we have an explicit - // use of the subregister, the subregister's contents are needed for the - // uses of the superregister. - 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); - LLVM_DEBUG(if (header) { - dbgs() << header << printReg(Reg, TRI); - header = nullptr; - }); - LLVM_DEBUG(dbgs() << " " << printReg(SubregReg, TRI) << "->g" - << State->GetGroup(SubregReg) << tag); - } - } - } - - LLVM_DEBUG(if (!header && footer) dbgs() << footer); -} - -void AggressiveAntiDepBreaker::PrescanInstruction( - MachineInstr &MI, unsigned Count, std::set<unsigned> &PassthruRegs) { - std::vector<unsigned> &DefIndices = State->GetDefIndices(); - std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& - 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 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. - for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { - MachineOperand &MO = MI.getOperand(i); - if (!MO.isReg() || !MO.isDef()) continue; - unsigned Reg = MO.getReg(); - if (Reg == 0) continue; - - HandleLastUse(Reg, Count + 1, "", "\tDead Def: ", "\n"); - } - - LLVM_DEBUG(dbgs() << "\tDef Groups:"); - for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { - MachineOperand &MO = MI.getOperand(i); - if (!MO.isReg() || !MO.isDef()) continue; - unsigned Reg = MO.getReg(); - if (Reg == 0) continue; - - LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI) << "=g" - << State->GetGroup(Reg)); - - // 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). 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()) { - LLVM_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 (MCRegAliasIterator AI(Reg, TRI, false); AI.isValid(); ++AI) { - unsigned AliasReg = *AI; - if (State->IsLive(AliasReg)) { - State->UnionGroups(Reg, AliasReg); - LLVM_DEBUG(dbgs() << "->g" << State->GetGroup(Reg) << "(via " - << printReg(AliasReg, TRI) << ")"); - } - } - - // Note register reference... - const TargetRegisterClass *RC = nullptr; - if (i < MI.getDesc().getNumOperands()) - RC = TII->getRegClass(MI.getDesc(), i, TRI, MF); - AggressiveAntiDepState::RegisterReference RR = { &MO, RC }; - RegRefs.insert(std::make_pair(Reg, RR)); - } - - LLVM_DEBUG(dbgs() << '\n'); - - // Scan the register defs for this instruction and update - // live-ranges. - for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { - MachineOperand &MO = MI.getOperand(i); - if (!MO.isReg() || !MO.isDef()) continue; - unsigned Reg = MO.getReg(); - if (Reg == 0) continue; - // Ignore KILLs and passthru registers for liveness... - if (MI.isKill() || (PassthruRegs.count(Reg) != 0)) - continue; - - // Update def for Reg and aliases. - 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) { - LLVM_DEBUG(dbgs() << "\tUse Groups:"); - std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& - 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, 14, %reg0; mem:LD4[FixedStack14] - // ... - // STR %r0, killed %r6, %reg0, 0, 0, %cpsr; mem:ST4[%395] - // %r6 = LDR %sp, %reg0, 100, 0, %cpsr; mem:LD4[FixedStack12] - // STR %r0, killed %r6, %reg0, 0, 14, %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) { - MachineOperand &MO = MI.getOperand(i); - if (!MO.isReg() || !MO.isUse()) continue; - unsigned Reg = MO.getReg(); - if (Reg == 0) continue; - - LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI) << "=g" - << State->GetGroup(Reg)); - - // It wasn't previously live but now it is, this is a kill. Forget - // the previous live-range information and start a new live-range - // for the register. - HandleLastUse(Reg, Count, "(last-use)"); - - if (Special) { - LLVM_DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)"); - State->UnionGroups(Reg, 0); - } - - // Note register reference... - const TargetRegisterClass *RC = nullptr; - if (i < MI.getDesc().getNumOperands()) - RC = TII->getRegClass(MI.getDesc(), i, TRI, MF); - AggressiveAntiDepState::RegisterReference RR = { &MO, RC }; - RegRefs.insert(std::make_pair(Reg, RR)); - } - - LLVM_DEBUG(dbgs() << '\n'); - - // Form a group of all defs and uses of a KILL instruction to ensure - // that all registers are renamed as a group. - if (MI.isKill()) { - LLVM_DEBUG(dbgs() << "\tKill Group:"); - - unsigned FirstReg = 0; - for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { - MachineOperand &MO = MI.getOperand(i); - if (!MO.isReg()) continue; - unsigned Reg = MO.getReg(); - if (Reg == 0) continue; - - if (FirstReg != 0) { - LLVM_DEBUG(dbgs() << "=" << printReg(Reg, TRI)); - State->UnionGroups(FirstReg, Reg); - } else { - LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI)); - FirstReg = Reg; - } - } - - LLVM_DEBUG(dbgs() << "->g" << State->GetGroup(FirstReg) << '\n'); - } -} - -BitVector AggressiveAntiDepBreaker::GetRenameRegisters(unsigned Reg) { - BitVector BV(TRI->getNumRegs(), false); - bool first = true; - - // 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. - 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; - first = false; - } else { - BV &= RCBV; - } - - LLVM_DEBUG(dbgs() << " " << TRI->getRegClassName(RC)); - } - - return BV; -} - -bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters( - unsigned AntiDepGroupIndex, - RenameOrderType& RenameOrder, - std::map<unsigned, unsigned> &RenameMap) { - std::vector<unsigned> &KillIndices = State->GetKillIndices(); - std::vector<unsigned> &DefIndices = State->GetDefIndices(); - std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& - RegRefs = State->GetRegRefs(); - - // 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, &RegRefs); - assert(!Regs.empty() && "Empty register group!"); - if (Regs.empty()) - return false; - - // Find the "superest" register in the group. At the same time, - // collect the BitVector of registers that can be used to rename - // each register. - LLVM_DEBUG(dbgs() << "\tRename Candidates for Group g" << AntiDepGroupIndex - << ":\n"); - std::map<unsigned, BitVector> RenameRegisterMap; - unsigned SuperReg = 0; - for (unsigned i = 0, e = Regs.size(); i != e; ++i) { - unsigned Reg = Regs[i]; - if ((SuperReg == 0) || TRI->isSuperRegister(SuperReg, Reg)) - SuperReg = Reg; - - // If Reg has any references, then collect possible rename regs - if (RegRefs.count(Reg) > 0) { - LLVM_DEBUG(dbgs() << "\t\t" << printReg(Reg, TRI) << ":"); - - BitVector &BV = RenameRegisterMap[Reg]; - assert(BV.empty()); - BV = GetRenameRegisters(Reg); - - LLVM_DEBUG({ - dbgs() << " ::"; - for (unsigned r : BV.set_bits()) - dbgs() << " " << printReg(r, TRI); - dbgs() << "\n"; - }); - } - } - - // All group registers should be a subreg of SuperReg. - for (unsigned i = 0, e = Regs.size(); i != e; ++i) { - unsigned Reg = Regs[i]; - if (Reg == SuperReg) continue; - bool IsSub = TRI->isSubRegister(SuperReg, Reg); - // FIXME: remove this once PR18663 has been properly fixed. For now, - // return a conservative answer: - // assert(IsSub && "Expecting group subregister"); - if (!IsSub) - return false; - } - -#ifndef NDEBUG - // If DebugDiv > 0 then only rename (renamecnt % DebugDiv) == DebugMod - if (DebugDiv > 0) { - static int renamecnt = 0; - if (renamecnt++ % DebugDiv != DebugMod) - return false; - - dbgs() << "*** Performing rename " << printReg(SuperReg, TRI) - << " 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. - - // 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->getMinimalPhysRegClass(SuperReg, MVT::Other); - - ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(SuperRC); - if (Order.empty()) { - LLVM_DEBUG(dbgs() << "\tEmpty Super Regclass!!\n"); - return false; - } - - LLVM_DEBUG(dbgs() << "\tFind Registers:"); - - RenameOrder.insert(RenameOrderType::value_type(SuperRC, Order.size())); - - unsigned OrigR = RenameOrder[SuperRC]; - unsigned EndR = ((OrigR == Order.size()) ? 0 : OrigR); - unsigned R = OrigR; - do { - if (R == 0) R = Order.size(); - --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; - - LLVM_DEBUG(dbgs() << " [" << printReg(NewSuperReg, TRI) << ':'); - 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); - } - - LLVM_DEBUG(dbgs() << " " << printReg(NewReg, TRI)); - - // Check if Reg can be renamed to NewReg. - if (!RenameRegisterMap[Reg].test(NewReg)) { - LLVM_DEBUG(dbgs() << "(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])) { - LLVM_DEBUG(dbgs() << "(live)"); - goto next_super_reg; - } else { - bool found = false; - for (MCRegAliasIterator AI(NewReg, TRI, false); AI.isValid(); ++AI) { - unsigned AliasReg = *AI; - if (State->IsLive(AliasReg) || - (KillIndices[Reg] > DefIndices[AliasReg])) { - LLVM_DEBUG(dbgs() - << "(alias " << printReg(AliasReg, TRI) << " live)"); - found = true; - break; - } - } - if (found) - 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()) { - LLVM_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)) { - LLVM_DEBUG(dbgs() << "(ec)"); - goto next_super_reg; - } - } - - // 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)); - LLVM_DEBUG(dbgs() << "]\n"); - return true; - - next_super_reg: - LLVM_DEBUG(dbgs() << ']'); - } while (R != EndR); - - LLVM_DEBUG(dbgs() << '\n'); - - // No registers are free and available! - return false; -} - -/// BreakAntiDependencies - Identifiy anti-dependencies within the -/// ScheduleDAG and break them by renaming registers. -unsigned AggressiveAntiDepBreaker::BreakAntiDependencies( - const std::vector<SUnit> &SUnits, - MachineBasicBlock::iterator Begin, - MachineBasicBlock::iterator End, - unsigned InsertPosIndex, - DbgValueVector &DbgValues) { - std::vector<unsigned> &KillIndices = State->GetKillIndices(); - std::vector<unsigned> &DefIndices = State->GetDefIndices(); - std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& - RegRefs = State->GetRegRefs(); - - // 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; - - // For each regclass the next register to use for renaming. - RenameOrderType RenameOrder; - - // ...need a map from MI to SUnit. - std::map<MachineInstr *, const SUnit *> MISUnitMap; - for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { - const SUnit *SU = &SUnits[i]; - MISUnitMap.insert(std::pair<MachineInstr *, const SUnit *>(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. - 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 (!CriticalPathSU || - ((SU->getDepth() + SU->Latency) > - (CriticalPathSU->getDepth() + CriticalPathSU->Latency))) { - CriticalPathSU = SU; - } - } - - CriticalPathMI = CriticalPathSU->getInstr(); - } - -#ifndef NDEBUG - LLVM_DEBUG(dbgs() << "\n===== Aggressive anti-dependency breaking\n"); - LLVM_DEBUG(dbgs() << "Available regs:"); - for (unsigned Reg = 0; Reg < TRI->getNumRegs(); ++Reg) { - if (!State->IsLive(Reg)) - LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI)); - } - LLVM_DEBUG(dbgs() << '\n'); -#endif - - BitVector RegAliases(TRI->getNumRegs()); - - // Attempt to break anti-dependence edges. Walk the instructions - // from the bottom up, tracking information about liveness as we go - // to help determine which registers are available. - unsigned Broken = 0; - unsigned Count = InsertPosIndex - 1; - for (MachineBasicBlock::iterator I = End, E = Begin; - I != E; --Count) { - MachineInstr &MI = *--I; - - if (MI.isDebugInstr()) - continue; - - LLVM_DEBUG(dbgs() << "Anti: "); - LLVM_DEBUG(MI.dump()); - - std::set<unsigned> PassthruRegs; - GetPassthruRegs(MI, PassthruRegs); - - // 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<const SDep *> 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 = nullptr; - if (&MI == CriticalPathMI) { - CriticalPathSU = CriticalPathStep(CriticalPathSU); - CriticalPathMI = (CriticalPathSU) ? CriticalPathSU->getInstr() : nullptr; - } else if (CriticalPathSet.any()) { - ExcludeRegs = &CriticalPathSet; - } - - // Ignore KILL instructions (they form a group in ScanInstruction - // but don't cause any anti-dependence breaking themselves) - if (!MI.isKill()) { - // Attempt to break each anti-dependency... - for (unsigned i = 0, e = Edges.size(); i != e; ++i) { - const SDep *Edge = Edges[i]; - SUnit *NextSU = Edge->getSUnit(); - - if ((Edge->getKind() != SDep::Anti) && - (Edge->getKind() != SDep::Output)) continue; - - unsigned AntiDepReg = Edge->getReg(); - LLVM_DEBUG(dbgs() << "\tAntidep reg: " << printReg(AntiDepReg, TRI)); - assert(AntiDepReg != 0 && "Anti-dependence on reg0?"); - - if (!MRI.isAllocatable(AntiDepReg)) { - // Don't break anti-dependencies on non-allocatable registers. - LLVM_DEBUG(dbgs() << " (non-allocatable)\n"); - continue; - } else if (ExcludeRegs && ExcludeRegs->test(AntiDepReg)) { - // Don't break anti-dependencies for critical path registers - // if not on the critical path - LLVM_DEBUG(dbgs() << " (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 - // the use if required to break an earlier antidep. - LLVM_DEBUG(dbgs() << " (passthru)\n"); - continue; - } else { - // No anti-dep breaking for implicit deps - MachineOperand *AntiDepOp = MI.findRegisterDefOperand(AntiDepReg); - assert(AntiDepOp && "Can't find index for defined register operand"); - if (!AntiDepOp || AntiDepOp->isImplicit()) { - LLVM_DEBUG(dbgs() << " (implicit)\n"); - continue; - } - - // If the SUnit has other dependencies on the SUnit that - // it anti-depends on, don't bother breaking the - // 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::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) : - (P->getKind() == SDep::Data && P->getReg() == AntiDepReg)) { - AntiDepReg = 0; - break; - } - } - 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)) { - LLVM_DEBUG(dbgs() << " (real dependency)\n"); - AntiDepReg = 0; - break; - } else if ((P->getSUnit() != NextSU) && - (P->getKind() == SDep::Data) && - (P->getReg() == AntiDepReg)) { - LLVM_DEBUG(dbgs() << " (other dependency)\n"); - AntiDepReg = 0; - break; - } - } - - if (AntiDepReg == 0) continue; - - // If the definition of the anti-dependency register does not start - // a new live range, bail out. This can happen if the anti-dep - // register is a sub-register of another register whose live range - // spans over PathSU. In such case, PathSU defines only a part of - // the larger register. - RegAliases.reset(); - for (MCRegAliasIterator AI(AntiDepReg, TRI, true); AI.isValid(); ++AI) - RegAliases.set(*AI); - for (SDep S : PathSU->Succs) { - SDep::Kind K = S.getKind(); - if (K != SDep::Data && K != SDep::Output && K != SDep::Anti) - continue; - unsigned R = S.getReg(); - if (!RegAliases[R]) - continue; - if (R == AntiDepReg || TRI->isSubRegister(AntiDepReg, R)) - continue; - AntiDepReg = 0; - break; - } - - if (AntiDepReg == 0) continue; - } - - assert(AntiDepReg != 0); - if (AntiDepReg == 0) continue; - - // Determine AntiDepReg's register group. - const unsigned GroupIndex = State->GetGroup(AntiDepReg); - if (GroupIndex == 0) { - LLVM_DEBUG(dbgs() << " (zero group)\n"); - continue; - } - - LLVM_DEBUG(dbgs() << '\n'); - - // Look for a suitable register to use to break the anti-dependence. - std::map<unsigned, unsigned> RenameMap; - if (FindSuitableFreeRegisters(GroupIndex, RenameOrder, RenameMap)) { - LLVM_DEBUG(dbgs() << "\tBreaking anti-dependence edge on " - << printReg(AntiDepReg, TRI) << ":"); - - // Handle each group register... - for (std::map<unsigned, unsigned>::iterator - S = RenameMap.begin(), E = RenameMap.end(); S != E; ++S) { - unsigned CurrReg = S->first; - unsigned NewReg = S->second; - - LLVM_DEBUG(dbgs() << " " << printReg(CurrReg, TRI) << "->" - << printReg(NewReg, TRI) << "(" - << RegRefs.count(CurrReg) << " refs)"); - - // Update the references to the old register CurrReg to - // refer to the new register 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; - UpdateDbgValues(DbgValues, Q.second.Operand->getParent(), - AntiDepReg, NewReg); - } - - // We just went back in time and modified history; the - // liveness information for CurrReg is now inconsistent. Set - // the state as if it were dead. - State->UnionGroups(NewReg, 0); - RegRefs.erase(NewReg); - DefIndices[NewReg] = DefIndices[CurrReg]; - KillIndices[NewReg] = KillIndices[CurrReg]; - - State->UnionGroups(CurrReg, 0); - RegRefs.erase(CurrReg); - DefIndices[CurrReg] = KillIndices[CurrReg]; - KillIndices[CurrReg] = ~0u; - assert(((KillIndices[CurrReg] == ~0u) != - (DefIndices[CurrReg] == ~0u)) && - "Kill and Def maps aren't consistent for AntiDepReg!"); - } - - ++Broken; - LLVM_DEBUG(dbgs() << '\n'); - } - } - } - - ScanInstruction(MI, Count); - } - - return Broken; -} |