diff options
Diffstat (limited to 'llvm/lib/CodeGen/AggressiveAntiDepBreaker.cpp')
| -rw-r--r-- | llvm/lib/CodeGen/AggressiveAntiDepBreaker.cpp | 1013 |
1 files changed, 1013 insertions, 0 deletions
diff --git a/llvm/lib/CodeGen/AggressiveAntiDepBreaker.cpp b/llvm/lib/CodeGen/AggressiveAntiDepBreaker.cpp new file mode 100644 index 000000000000..f64b775a8b77 --- /dev/null +++ b/llvm/lib/CodeGen/AggressiveAntiDepBreaker.cpp @@ -0,0 +1,1013 @@ +//===- AggressiveAntiDepBreaker.cpp - Anti-dep breaker --------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// 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; + + Register 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 Register 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; + Register 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; + Register 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; + Register 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; + Register 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; + Register 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; + } + } + assert(CriticalPathSU && "Failed to find SUnit critical path"); + 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; +} |