972 lines · cpp
1//===- AggressiveAntiDepBreaker.cpp - Anti-dep breaker --------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the AggressiveAntiDepBreaker class, which10// implements register anti-dependence breaking during post-RA11// scheduling. It attempts to break all anti-dependencies within a12// block.13//14//===----------------------------------------------------------------------===//15 16#include "AggressiveAntiDepBreaker.h"17#include "llvm/ADT/ArrayRef.h"18#include "llvm/ADT/SmallSet.h"19#include "llvm/ADT/iterator_range.h"20#include "llvm/CodeGen/MachineBasicBlock.h"21#include "llvm/CodeGen/MachineFrameInfo.h"22#include "llvm/CodeGen/MachineFunction.h"23#include "llvm/CodeGen/MachineInstr.h"24#include "llvm/CodeGen/MachineOperand.h"25#include "llvm/CodeGen/MachineRegisterInfo.h"26#include "llvm/CodeGen/RegisterClassInfo.h"27#include "llvm/CodeGen/ScheduleDAG.h"28#include "llvm/CodeGen/TargetInstrInfo.h"29#include "llvm/CodeGen/TargetRegisterInfo.h"30#include "llvm/CodeGenTypes/MachineValueType.h"31#include "llvm/MC/MCInstrDesc.h"32#include "llvm/MC/MCRegisterInfo.h"33#include "llvm/Support/CommandLine.h"34#include "llvm/Support/Debug.h"35#include "llvm/Support/raw_ostream.h"36#include <cassert>37 38using namespace llvm;39 40#define DEBUG_TYPE "post-RA-sched"41 42// If DebugDiv > 0 then only break antidep with (ID % DebugDiv) == DebugMod43static cl::opt<int>44DebugDiv("agg-antidep-debugdiv",45 cl::desc("Debug control for aggressive anti-dep breaker"),46 cl::init(0), cl::Hidden);47 48static cl::opt<int>49DebugMod("agg-antidep-debugmod",50 cl::desc("Debug control for aggressive anti-dep breaker"),51 cl::init(0), cl::Hidden);52 53AggressiveAntiDepState::AggressiveAntiDepState(const unsigned TargetRegs,54 MachineBasicBlock *BB)55 : NumTargetRegs(TargetRegs), GroupNodes(TargetRegs, 0),56 GroupNodeIndices(TargetRegs, 0), KillIndices(TargetRegs, 0),57 DefIndices(TargetRegs, 0) {58 const unsigned BBSize = BB->size();59 for (unsigned i = 0; i < NumTargetRegs; ++i) {60 // Initialize all registers to be in their own group. Initially we61 // assign the register to the same-indexed GroupNode.62 GroupNodeIndices[i] = i;63 // Initialize the indices to indicate that no registers are live.64 KillIndices[i] = ~0u;65 DefIndices[i] = BBSize;66 }67}68 69unsigned AggressiveAntiDepState::GetGroup(MCRegister Reg) {70 unsigned Node = GroupNodeIndices[Reg.id()];71 while (GroupNodes[Node] != Node)72 Node = GroupNodes[Node];73 74 return Node;75}76 77void AggressiveAntiDepState::GetGroupRegs(78 unsigned Group, std::vector<MCRegister> &Regs,79 std::multimap<MCRegister, AggressiveAntiDepState::RegisterReference>80 *RegRefs) {81 for (unsigned Reg = 0; Reg != NumTargetRegs; ++Reg) {82 if ((GetGroup(Reg) == Group) && (RegRefs->count(Reg) > 0))83 Regs.push_back(Reg);84 }85}86 87unsigned AggressiveAntiDepState::UnionGroups(MCRegister Reg1, MCRegister Reg2) {88 assert(GroupNodes[0] == 0 && "GroupNode 0 not parent!");89 assert(GroupNodeIndices[0] == 0 && "Reg 0 not in Group 0!");90 91 // find group for each register92 unsigned Group1 = GetGroup(Reg1);93 unsigned Group2 = GetGroup(Reg2);94 95 // if either group is 0, then that must become the parent96 unsigned Parent = (Group1 == 0) ? Group1 : Group2;97 unsigned Other = (Parent == Group1) ? Group2 : Group1;98 GroupNodes.at(Other) = Parent;99 return Parent;100}101 102unsigned AggressiveAntiDepState::LeaveGroup(MCRegister Reg) {103 // Create a new GroupNode for Reg. Reg's existing GroupNode must104 // stay as is because there could be other GroupNodes referring to105 // it.106 unsigned idx = GroupNodes.size();107 GroupNodes.push_back(idx);108 GroupNodeIndices[Reg.id()] = idx;109 return idx;110}111 112bool AggressiveAntiDepState::IsLive(MCRegister Reg) {113 // KillIndex must be defined and DefIndex not defined for a register114 // to be live.115 return ((KillIndices[Reg.id()] != ~0u) && (DefIndices[Reg.id()] == ~0u));116}117 118AggressiveAntiDepBreaker::AggressiveAntiDepBreaker(119 MachineFunction &MFi, const RegisterClassInfo &RCI,120 TargetSubtargetInfo::RegClassVector &CriticalPathRCs)121 : MF(MFi), MRI(MF.getRegInfo()), TII(MF.getSubtarget().getInstrInfo()),122 TRI(MF.getSubtarget().getRegisterInfo()), RegClassInfo(RCI) {123 /* Collect a bitset of all registers that are only broken if they124 are on the critical path. */125 for (const TargetRegisterClass *RC : CriticalPathRCs) {126 BitVector CPSet = TRI->getAllocatableSet(MF, RC);127 if (CriticalPathSet.none())128 CriticalPathSet = CPSet;129 else130 CriticalPathSet |= CPSet;131 }132 133 LLVM_DEBUG(dbgs() << "AntiDep Critical-Path Registers:");134 LLVM_DEBUG(for (unsigned r135 : CriticalPathSet.set_bits()) dbgs()136 << " " << printReg(r, TRI));137 LLVM_DEBUG(dbgs() << '\n');138}139 140AggressiveAntiDepBreaker::~AggressiveAntiDepBreaker() {141 delete State;142}143 144void AggressiveAntiDepBreaker::StartBlock(MachineBasicBlock *BB) {145 assert(!State);146 State = new AggressiveAntiDepState(TRI->getNumRegs(), BB);147 148 bool IsReturnBlock = BB->isReturnBlock();149 std::vector<unsigned> &KillIndices = State->GetKillIndices();150 std::vector<unsigned> &DefIndices = State->GetDefIndices();151 152 // Examine the live-in regs of all successors.153 for (MachineBasicBlock *Succ : BB->successors())154 for (const auto &LI : Succ->liveins()) {155 for (MCRegAliasIterator AI(LI.PhysReg, TRI, true); AI.isValid(); ++AI) {156 MCRegister Reg = *AI;157 State->UnionGroups(Reg, 0);158 KillIndices[Reg.id()] = BB->size();159 DefIndices[Reg.id()] = ~0u;160 }161 }162 163 // Mark live-out callee-saved registers. In a return block this is164 // all callee-saved registers. In non-return this is any165 // callee-saved register that is not saved in the prolog.166 const MachineFrameInfo &MFI = MF.getFrameInfo();167 BitVector Pristine = MFI.getPristineRegs(MF);168 for (const MCPhysReg *I = MF.getRegInfo().getCalleeSavedRegs(); *I;169 ++I) {170 unsigned Reg = *I;171 if (!IsReturnBlock && !Pristine.test(Reg))172 continue;173 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {174 MCRegister AliasReg = *AI;175 State->UnionGroups(AliasReg, 0);176 KillIndices[AliasReg.id()] = BB->size();177 DefIndices[AliasReg.id()] = ~0u;178 }179 }180}181 182void AggressiveAntiDepBreaker::FinishBlock() {183 delete State;184 State = nullptr;185}186 187void AggressiveAntiDepBreaker::Observe(MachineInstr &MI, unsigned Count,188 unsigned InsertPosIndex) {189 assert(Count < InsertPosIndex && "Instruction index out of expected range!");190 191 std::set<MCRegister> PassthruRegs;192 GetPassthruRegs(MI, PassthruRegs);193 PrescanInstruction(MI, Count, PassthruRegs);194 ScanInstruction(MI, Count);195 196 LLVM_DEBUG(dbgs() << "Observe: ");197 LLVM_DEBUG(MI.dump());198 LLVM_DEBUG(dbgs() << "\tRegs:");199 200 std::vector<unsigned> &DefIndices = State->GetDefIndices();201 for (unsigned Reg = 1; Reg != TRI->getNumRegs(); ++Reg) {202 // If Reg is current live, then mark that it can't be renamed as203 // we don't know the extent of its live-range anymore (now that it204 // has been scheduled). If it is not live but was defined in the205 // previous schedule region, then set its def index to the most206 // conservative location (i.e. the beginning of the previous207 // schedule region).208 if (State->IsLive(Reg)) {209 LLVM_DEBUG(if (State->GetGroup(Reg) != 0) dbgs()210 << " " << printReg(Reg, TRI) << "=g" << State->GetGroup(Reg)211 << "->g0(region live-out)");212 State->UnionGroups(Reg, 0);213 } else if ((DefIndices[Reg] < InsertPosIndex)214 && (DefIndices[Reg] >= Count)) {215 DefIndices[Reg] = Count;216 }217 }218 LLVM_DEBUG(dbgs() << '\n');219}220 221bool AggressiveAntiDepBreaker::IsImplicitDefUse(MachineInstr &MI,222 MachineOperand &MO) {223 if (!MO.isReg() || !MO.isImplicit())224 return false;225 226 Register Reg = MO.getReg();227 if (Reg == 0)228 return false;229 230 MachineOperand *Op = nullptr;231 if (MO.isDef())232 Op = MI.findRegisterUseOperand(Reg, /*TRI=*/nullptr, true);233 else234 Op = MI.findRegisterDefOperand(Reg, /*TRI=*/nullptr);235 236 return(Op && Op->isImplicit());237}238 239void AggressiveAntiDepBreaker::GetPassthruRegs(240 MachineInstr &MI, std::set<MCRegister> &PassthruRegs) {241 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {242 MachineOperand &MO = MI.getOperand(i);243 if (!MO.isReg()) continue;244 if ((MO.isDef() && MI.isRegTiedToUseOperand(i)) ||245 IsImplicitDefUse(MI, MO)) {246 const Register Reg = MO.getReg();247 for (MCPhysReg SubReg : TRI->subregs_inclusive(Reg))248 PassthruRegs.insert(SubReg);249 }250 }251}252 253/// AntiDepEdges - Return in Edges the anti- and output- dependencies254/// in SU that we want to consider for breaking.255static void AntiDepEdges(const SUnit *SU, std::vector<const SDep *> &Edges) {256 SmallSet<Register, 4> RegSet;257 for (const SDep &Pred : SU->Preds) {258 if ((Pred.getKind() == SDep::Anti) || (Pred.getKind() == SDep::Output)) {259 if (RegSet.insert(Pred.getReg()).second)260 Edges.push_back(&Pred);261 }262 }263}264 265/// CriticalPathStep - Return the next SUnit after SU on the bottom-up266/// critical path.267static const SUnit *CriticalPathStep(const SUnit *SU) {268 const SDep *Next = nullptr;269 unsigned NextDepth = 0;270 // Find the predecessor edge with the greatest depth.271 if (SU) {272 for (const SDep &Pred : SU->Preds) {273 const SUnit *PredSU = Pred.getSUnit();274 unsigned PredLatency = Pred.getLatency();275 unsigned PredTotalLatency = PredSU->getDepth() + PredLatency;276 // In the case of a latency tie, prefer an anti-dependency edge over277 // other types of edges.278 if (NextDepth < PredTotalLatency ||279 (NextDepth == PredTotalLatency && Pred.getKind() == SDep::Anti)) {280 NextDepth = PredTotalLatency;281 Next = &Pred;282 }283 }284 }285 286 return (Next) ? Next->getSUnit() : nullptr;287}288 289void AggressiveAntiDepBreaker::HandleLastUse(MCRegister Reg, unsigned KillIdx,290 const char *tag,291 const char *header,292 const char *footer) {293 std::vector<unsigned> &KillIndices = State->GetKillIndices();294 std::vector<unsigned> &DefIndices = State->GetDefIndices();295 std::multimap<MCRegister, AggressiveAntiDepState::RegisterReference>296 &RegRefs = State->GetRegRefs();297 298 // FIXME: We must leave subregisters of live super registers as live, so that299 // we don't clear out the register tracking information for subregisters of300 // super registers we're still tracking (and with which we're unioning301 // subregister definitions).302 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)303 if (TRI->isSuperRegister(Reg, *AI) && State->IsLive(*AI)) {304 LLVM_DEBUG(if (!header && footer) dbgs() << footer);305 return;306 }307 308 if (!State->IsLive(Reg)) {309 KillIndices[Reg.id()] = KillIdx;310 DefIndices[Reg.id()] = ~0u;311 RegRefs.erase(Reg);312 State->LeaveGroup(Reg);313 LLVM_DEBUG(if (header) {314 dbgs() << header << printReg(Reg, TRI);315 header = nullptr;316 });317 LLVM_DEBUG(dbgs() << "->g" << State->GetGroup(Reg) << tag);318 // Repeat for subregisters. Note that we only do this if the superregister319 // was not live because otherwise, regardless whether we have an explicit320 // use of the subregister, the subregister's contents are needed for the321 // uses of the superregister.322 for (MCPhysReg SubregReg : TRI->subregs(Reg)) {323 if (!State->IsLive(SubregReg)) {324 KillIndices[SubregReg] = KillIdx;325 DefIndices[SubregReg] = ~0u;326 RegRefs.erase(SubregReg);327 State->LeaveGroup(SubregReg);328 LLVM_DEBUG(if (header) {329 dbgs() << header << printReg(Reg, TRI);330 header = nullptr;331 });332 LLVM_DEBUG(dbgs() << " " << printReg(SubregReg, TRI) << "->g"333 << State->GetGroup(SubregReg) << tag);334 }335 }336 }337 338 LLVM_DEBUG(if (!header && footer) dbgs() << footer);339}340 341void AggressiveAntiDepBreaker::PrescanInstruction(342 MachineInstr &MI, unsigned Count,343 const std::set<MCRegister> &PassthruRegs) {344 std::vector<unsigned> &DefIndices = State->GetDefIndices();345 std::multimap<MCRegister, AggressiveAntiDepState::RegisterReference>346 &RegRefs = State->GetRegRefs();347 348 // Handle dead defs by simulating a last-use of the register just349 // after the def. A dead def can occur because the def is truly350 // dead, or because only a subregister is live at the def. If we351 // don't do this the dead def will be incorrectly merged into the352 // previous def.353 for (const MachineOperand &MO : MI.all_defs()) {354 Register Reg = MO.getReg();355 if (!Reg)356 continue;357 358 HandleLastUse(Reg.asMCReg(), Count + 1, "", "\tDead Def: ", "\n");359 }360 361 LLVM_DEBUG(dbgs() << "\tDef Groups:");362 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {363 MachineOperand &MO = MI.getOperand(i);364 if (!MO.isReg() || !MO.isDef()) continue;365 Register Reg = MO.getReg();366 if (!Reg)367 continue;368 369 LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI) << "=g"370 << State->GetGroup(Reg));371 372 // If MI's defs have a special allocation requirement, don't allow373 // any def registers to be changed. Also assume all registers374 // defined in a call must not be changed (ABI). Inline assembly may375 // reference either system calls or the register directly. Skip it until we376 // can tell user specified registers from compiler-specified.377 if (MI.isCall() || MI.hasExtraDefRegAllocReq() || TII->isPredicated(MI) ||378 MI.isInlineAsm()) {379 LLVM_DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)");380 State->UnionGroups(Reg, 0);381 }382 383 // Any aliased that are live at this point are completely or384 // partially defined here, so group those aliases with Reg.385 for (MCRegAliasIterator AI(Reg, TRI, false); AI.isValid(); ++AI) {386 MCRegister AliasReg = *AI;387 if (State->IsLive(AliasReg)) {388 State->UnionGroups(Reg, AliasReg);389 LLVM_DEBUG(dbgs() << "->g" << State->GetGroup(Reg) << "(via "390 << printReg(AliasReg, TRI) << ")");391 }392 }393 394 // Note register reference...395 const TargetRegisterClass *RC = nullptr;396 if (i < MI.getDesc().getNumOperands())397 RC = TII->getRegClass(MI.getDesc(), i);398 AggressiveAntiDepState::RegisterReference RR = { &MO, RC };399 RegRefs.emplace(Reg.asMCReg(), RR);400 }401 402 LLVM_DEBUG(dbgs() << '\n');403 404 // Scan the register defs for this instruction and update405 // live-ranges.406 for (const MachineOperand &MO : MI.all_defs()) {407 Register Reg = MO.getReg();408 if (!Reg)409 continue;410 // Ignore KILLs and passthru registers for liveness...411 if (MI.isKill() || (PassthruRegs.count(Reg) != 0))412 continue;413 414 // Update def for Reg and aliases.415 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {416 // We need to be careful here not to define already-live super registers.417 // If the super register is already live, then this definition is not418 // a definition of the whole super register (just a partial insertion419 // into it). Earlier subregister definitions (which we've not yet visited420 // because we're iterating bottom-up) need to be linked to the same group421 // as this definition.422 if (TRI->isSuperRegister(Reg, *AI) && State->IsLive(*AI))423 continue;424 425 DefIndices[(*AI).id()] = Count;426 }427 }428}429 430void AggressiveAntiDepBreaker::ScanInstruction(MachineInstr &MI,431 unsigned Count) {432 LLVM_DEBUG(dbgs() << "\tUse Groups:");433 std::multimap<MCRegister, AggressiveAntiDepState::RegisterReference>434 &RegRefs = State->GetRegRefs();435 436 // If MI's uses have special allocation requirement, don't allow437 // any use registers to be changed. Also assume all registers438 // used in a call must not be changed (ABI).439 // Inline Assembly register uses also cannot be safely changed.440 // FIXME: The issue with predicated instruction is more complex. We are being441 // conservatively here because the kill markers cannot be trusted after442 // if-conversion:443 // %r6 = LDR %sp, %reg0, 92, 14, %reg0; mem:LD4[FixedStack14]444 // ...445 // STR %r0, killed %r6, %reg0, 0, 0, %cpsr; mem:ST4[%395]446 // %r6 = LDR %sp, %reg0, 100, 0, %cpsr; mem:LD4[FixedStack12]447 // STR %r0, killed %r6, %reg0, 0, 14, %reg0; mem:ST4[%396](align=8)448 //449 // The first R6 kill is not really a kill since it's killed by a predicated450 // instruction which may not be executed. The second R6 def may or may not451 // re-define R6 so it's not safe to change it since the last R6 use cannot be452 // changed.453 bool Special = MI.isCall() || MI.hasExtraSrcRegAllocReq() ||454 TII->isPredicated(MI) || MI.isInlineAsm();455 456 // Scan the register uses for this instruction and update457 // live-ranges, groups and RegRefs.458 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {459 MachineOperand &MO = MI.getOperand(i);460 if (!MO.isReg() || !MO.isUse()) continue;461 Register Reg = MO.getReg();462 if (!Reg)463 continue;464 465 LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI) << "=g"466 << State->GetGroup(Reg));467 468 // It wasn't previously live but now it is, this is a kill. Forget469 // the previous live-range information and start a new live-range470 // for the register.471 HandleLastUse(Reg.asMCReg(), Count, "(last-use)");472 473 if (Special) {474 LLVM_DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)");475 State->UnionGroups(Reg, 0);476 }477 478 // Note register reference...479 const TargetRegisterClass *RC = nullptr;480 if (i < MI.getDesc().getNumOperands())481 RC = TII->getRegClass(MI.getDesc(), i);482 AggressiveAntiDepState::RegisterReference RR = { &MO, RC };483 RegRefs.emplace(Reg.asMCReg(), RR);484 }485 486 LLVM_DEBUG(dbgs() << '\n');487 488 // Form a group of all defs and uses of a KILL instruction to ensure489 // that all registers are renamed as a group.490 if (MI.isKill()) {491 LLVM_DEBUG(dbgs() << "\tKill Group:");492 493 Register FirstReg;494 for (const MachineOperand &MO : MI.operands()) {495 if (!MO.isReg()) continue;496 Register Reg = MO.getReg();497 if (!Reg)498 continue;499 500 if (FirstReg) {501 LLVM_DEBUG(dbgs() << "=" << printReg(Reg, TRI));502 State->UnionGroups(FirstReg, Reg);503 } else {504 LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI));505 FirstReg = Reg;506 }507 }508 509 LLVM_DEBUG(dbgs() << "->g" << State->GetGroup(FirstReg) << '\n');510 }511}512 513BitVector AggressiveAntiDepBreaker::GetRenameRegisters(MCRegister Reg) {514 BitVector BV(TRI->getNumRegs(), false);515 bool first = true;516 517 // Check all references that need rewriting for Reg. For each, use518 // the corresponding register class to narrow the set of registers519 // that are appropriate for renaming.520 for (const auto &Q : make_range(State->GetRegRefs().equal_range(Reg))) {521 const TargetRegisterClass *RC = Q.second.RC;522 if (!RC) continue;523 524 BitVector RCBV = TRI->getAllocatableSet(MF, RC);525 if (first) {526 BV |= RCBV;527 first = false;528 } else {529 BV &= RCBV;530 }531 532 LLVM_DEBUG(dbgs() << " " << TRI->getRegClassName(RC));533 }534 535 return BV;536}537 538bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters(539 MCRegister SuperReg, unsigned AntiDepGroupIndex,540 RenameOrderType &RenameOrder, std::map<MCRegister, MCRegister> &RenameMap) {541 std::vector<unsigned> &KillIndices = State->GetKillIndices();542 std::vector<unsigned> &DefIndices = State->GetDefIndices();543 std::multimap<MCRegister, AggressiveAntiDepState::RegisterReference>544 &RegRefs = State->GetRegRefs();545 546 // Collect all referenced registers in the same group as547 // AntiDepReg. These all need to be renamed together if we are to548 // break the anti-dependence.549 std::vector<MCRegister> Regs;550 State->GetGroupRegs(AntiDepGroupIndex, Regs, &RegRefs);551 assert(!Regs.empty() && "Empty register group!");552 if (Regs.empty())553 return false;554 555 // Collect the BitVector of registers that can be used to rename556 // each register.557 LLVM_DEBUG(dbgs() << "\tRename Candidates for Group g" << AntiDepGroupIndex558 << ":\n");559 std::map<MCRegister, BitVector> RenameRegisterMap;560 for (MCRegister Reg : Regs) {561 // If Reg has any references, then collect possible rename regs562 if (RegRefs.count(Reg) > 0) {563 LLVM_DEBUG(dbgs() << "\t\t" << printReg(Reg, TRI) << ":");564 565 BitVector &BV = RenameRegisterMap[Reg];566 assert(BV.empty());567 BV = GetRenameRegisters(Reg);568 569 LLVM_DEBUG({570 dbgs() << " ::";571 for (unsigned r : BV.set_bits())572 dbgs() << " " << printReg(r, TRI);573 dbgs() << "\n";574 });575 }576 }577 578 // All group registers should be a subreg of SuperReg.579 for (MCRegister Reg : Regs) {580 if (Reg == SuperReg) continue;581 bool IsSub = TRI->isSubRegister(SuperReg, Reg);582 // FIXME: remove this once PR18663 has been properly fixed. For now,583 // return a conservative answer:584 // assert(IsSub && "Expecting group subregister");585 if (!IsSub)586 return false;587 }588 589#ifndef NDEBUG590 // If DebugDiv > 0 then only rename (renamecnt % DebugDiv) == DebugMod591 if (DebugDiv > 0) {592 static int renamecnt = 0;593 if (renamecnt++ % DebugDiv != DebugMod)594 return false;595 596 dbgs() << "*** Performing rename " << printReg(SuperReg, TRI)597 << " for debug ***\n";598 }599#endif600 601 // Check each possible rename register for SuperReg in round-robin602 // order. If that register is available, and the corresponding603 // registers are available for the other group subregisters, then we604 // can use those registers to rename.605 606 // FIXME: Using getMinimalPhysRegClass is very conservative. We should607 // check every use of the register and find the largest register class608 // that can be used in all of them.609 const TargetRegisterClass *SuperRC =610 TRI->getMinimalPhysRegClass(SuperReg, MVT::Other);611 612 ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(SuperRC);613 if (Order.empty()) {614 LLVM_DEBUG(dbgs() << "\tEmpty Super Regclass!!\n");615 return false;616 }617 618 LLVM_DEBUG(dbgs() << "\tFind Registers:");619 620 RenameOrder.insert(RenameOrderType::value_type(SuperRC, Order.size()));621 622 unsigned OrigR = RenameOrder[SuperRC];623 unsigned EndR = ((OrigR == Order.size()) ? 0 : OrigR);624 unsigned R = OrigR;625 do {626 if (R == 0) R = Order.size();627 --R;628 const MCRegister NewSuperReg = Order[R];629 // Don't consider non-allocatable registers630 if (!MRI.isAllocatable(NewSuperReg)) continue;631 // Don't replace a register with itself.632 if (NewSuperReg == SuperReg) continue;633 634 LLVM_DEBUG(dbgs() << " [" << printReg(NewSuperReg, TRI) << ':');635 RenameMap.clear();636 637 // For each referenced group register (which must be a SuperReg or638 // a subregister of SuperReg), find the corresponding subregister639 // of NewSuperReg and make sure it is free to be renamed.640 for (MCRegister Reg : Regs) {641 MCRegister NewReg;642 if (Reg == SuperReg) {643 NewReg = NewSuperReg;644 } else {645 unsigned NewSubRegIdx = TRI->getSubRegIndex(SuperReg, Reg);646 if (NewSubRegIdx != 0)647 NewReg = TRI->getSubReg(NewSuperReg, NewSubRegIdx);648 }649 650 LLVM_DEBUG(dbgs() << " " << printReg(NewReg, TRI));651 652 // Check if Reg can be renamed to NewReg.653 if (!RenameRegisterMap[Reg].test(NewReg.id())) {654 LLVM_DEBUG(dbgs() << "(no rename)");655 goto next_super_reg;656 }657 658 // If NewReg is dead and NewReg's most recent def is not before659 // Regs's kill, it's safe to replace Reg with NewReg. We660 // must also check all aliases of NewReg, because we can't define a661 // register when any sub or super is already live.662 if (State->IsLive(NewReg) ||663 (KillIndices[Reg.id()] > DefIndices[NewReg.id()])) {664 LLVM_DEBUG(dbgs() << "(live)");665 goto next_super_reg;666 } else {667 bool found = false;668 for (MCRegAliasIterator AI(NewReg, TRI, false); AI.isValid(); ++AI) {669 MCRegister AliasReg = *AI;670 if (State->IsLive(AliasReg) ||671 (KillIndices[Reg.id()] > DefIndices[AliasReg.id()])) {672 LLVM_DEBUG(dbgs()673 << "(alias " << printReg(AliasReg, TRI) << " live)");674 found = true;675 break;676 }677 }678 if (found)679 goto next_super_reg;680 }681 682 // We cannot rename 'Reg' to 'NewReg' if one of the uses of 'Reg' also683 // defines 'NewReg' via an early-clobber operand.684 for (const auto &Q : make_range(RegRefs.equal_range(Reg))) {685 MachineInstr *UseMI = Q.second.Operand->getParent();686 int Idx = UseMI->findRegisterDefOperandIdx(NewReg, TRI, false, true);687 if (Idx == -1)688 continue;689 690 if (UseMI->getOperand(Idx).isEarlyClobber()) {691 LLVM_DEBUG(dbgs() << "(ec)");692 goto next_super_reg;693 }694 }695 696 // Also, we cannot rename 'Reg' to 'NewReg' if the instruction defining697 // 'Reg' is an early-clobber define and that instruction also uses698 // 'NewReg'.699 for (const auto &Q : make_range(RegRefs.equal_range(Reg))) {700 if (!Q.second.Operand->isDef() || !Q.second.Operand->isEarlyClobber())701 continue;702 703 MachineInstr *DefMI = Q.second.Operand->getParent();704 if (DefMI->readsRegister(NewReg, TRI)) {705 LLVM_DEBUG(dbgs() << "(ec)");706 goto next_super_reg;707 }708 }709 710 // Record that 'Reg' can be renamed to 'NewReg'.711 RenameMap.insert(std::make_pair(Reg, NewReg));712 }713 714 // If we fall-out here, then every register in the group can be715 // renamed, as recorded in RenameMap.716 RenameOrder.erase(SuperRC);717 RenameOrder.insert(RenameOrderType::value_type(SuperRC, R));718 LLVM_DEBUG(dbgs() << "]\n");719 return true;720 721 next_super_reg:722 LLVM_DEBUG(dbgs() << ']');723 } while (R != EndR);724 725 LLVM_DEBUG(dbgs() << '\n');726 727 // No registers are free and available!728 return false;729}730 731/// BreakAntiDependencies - Identifiy anti-dependencies within the732/// ScheduleDAG and break them by renaming registers.733unsigned AggressiveAntiDepBreaker::BreakAntiDependencies(734 const std::vector<SUnit> &SUnits,735 MachineBasicBlock::iterator Begin,736 MachineBasicBlock::iterator End,737 unsigned InsertPosIndex,738 DbgValueVector &DbgValues) {739 std::vector<unsigned> &KillIndices = State->GetKillIndices();740 std::vector<unsigned> &DefIndices = State->GetDefIndices();741 std::multimap<MCRegister, AggressiveAntiDepState::RegisterReference>742 &RegRefs = State->GetRegRefs();743 744 // The code below assumes that there is at least one instruction,745 // so just duck out immediately if the block is empty.746 if (SUnits.empty()) return 0;747 748 // For each regclass the next register to use for renaming.749 RenameOrderType RenameOrder;750 751 // ...need a map from MI to SUnit.752 std::map<MachineInstr *, const SUnit *> MISUnitMap;753 for (const SUnit &SU : SUnits)754 MISUnitMap.insert(std::make_pair(SU.getInstr(), &SU));755 756 // Track progress along the critical path through the SUnit graph as757 // we walk the instructions. This is needed for regclasses that only758 // break critical-path anti-dependencies.759 const SUnit *CriticalPathSU = nullptr;760 MachineInstr *CriticalPathMI = nullptr;761 if (CriticalPathSet.any()) {762 for (const SUnit &SU : SUnits) {763 if (!CriticalPathSU ||764 ((SU.getDepth() + SU.Latency) >765 (CriticalPathSU->getDepth() + CriticalPathSU->Latency))) {766 CriticalPathSU = &SU;767 }768 }769 assert(CriticalPathSU && "Failed to find SUnit critical path");770 CriticalPathMI = CriticalPathSU->getInstr();771 }772 773#ifndef NDEBUG774 LLVM_DEBUG(dbgs() << "\n===== Aggressive anti-dependency breaking\n");775 LLVM_DEBUG(dbgs() << "Available regs:");776 for (unsigned Reg = 1; Reg < TRI->getNumRegs(); ++Reg) {777 if (!State->IsLive(Reg))778 LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI));779 }780 LLVM_DEBUG(dbgs() << '\n');781#endif782 783 BitVector RegAliases(TRI->getNumRegs());784 785 // Attempt to break anti-dependence edges. Walk the instructions786 // from the bottom up, tracking information about liveness as we go787 // to help determine which registers are available.788 unsigned Broken = 0;789 unsigned Count = InsertPosIndex - 1;790 for (MachineBasicBlock::iterator I = End, E = Begin;791 I != E; --Count) {792 MachineInstr &MI = *--I;793 794 if (MI.isDebugInstr())795 continue;796 797 LLVM_DEBUG(dbgs() << "Anti: ");798 LLVM_DEBUG(MI.dump());799 800 std::set<MCRegister> PassthruRegs;801 GetPassthruRegs(MI, PassthruRegs);802 803 // Process the defs in MI...804 PrescanInstruction(MI, Count, PassthruRegs);805 806 // The dependence edges that represent anti- and output-807 // dependencies that are candidates for breaking.808 std::vector<const SDep *> Edges;809 const SUnit *PathSU = MISUnitMap[&MI];810 AntiDepEdges(PathSU, Edges);811 812 // If MI is not on the critical path, then we don't rename813 // registers in the CriticalPathSet.814 BitVector *ExcludeRegs = nullptr;815 if (&MI == CriticalPathMI) {816 CriticalPathSU = CriticalPathStep(CriticalPathSU);817 CriticalPathMI = (CriticalPathSU) ? CriticalPathSU->getInstr() : nullptr;818 } else if (CriticalPathSet.any()) {819 ExcludeRegs = &CriticalPathSet;820 }821 822 // Ignore KILL instructions (they form a group in ScanInstruction823 // but don't cause any anti-dependence breaking themselves)824 if (!MI.isKill()) {825 // Attempt to break each anti-dependency...826 for (const SDep *Edge : Edges) {827 SUnit *NextSU = Edge->getSUnit();828 829 if ((Edge->getKind() != SDep::Anti) &&830 (Edge->getKind() != SDep::Output)) continue;831 832 MCRegister AntiDepReg = Edge->getReg().asMCReg();833 LLVM_DEBUG(dbgs() << "\tAntidep reg: " << printReg(AntiDepReg, TRI));834 assert(AntiDepReg && "Anti-dependence on reg0?");835 836 if (!MRI.isAllocatable(AntiDepReg)) {837 // Don't break anti-dependencies on non-allocatable registers.838 LLVM_DEBUG(dbgs() << " (non-allocatable)\n");839 continue;840 } else if (ExcludeRegs && ExcludeRegs->test(AntiDepReg.id())) {841 // Don't break anti-dependencies for critical path registers842 // if not on the critical path843 LLVM_DEBUG(dbgs() << " (not critical-path)\n");844 continue;845 } else if (PassthruRegs.count(AntiDepReg) != 0) {846 // If the anti-dep register liveness "passes-thru", then847 // don't try to change it. It will be changed along with848 // the use if required to break an earlier antidep.849 LLVM_DEBUG(dbgs() << " (passthru)\n");850 continue;851 } else {852 // No anti-dep breaking for implicit deps853 MachineOperand *AntiDepOp =854 MI.findRegisterDefOperand(AntiDepReg, /*TRI=*/nullptr);855 assert(AntiDepOp && "Can't find index for defined register operand");856 if (!AntiDepOp || AntiDepOp->isImplicit()) {857 LLVM_DEBUG(dbgs() << " (implicit)\n");858 continue;859 }860 861 // If the SUnit has other dependencies on the SUnit that862 // it anti-depends on, don't bother breaking the863 // anti-dependency since those edges would prevent such864 // units from being scheduled past each other865 // regardless.866 //867 // Also, if there are dependencies on other SUnits with the868 // same register as the anti-dependency, don't attempt to869 // break it.870 for (const SDep &Pred : PathSU->Preds) {871 if (Pred.getSUnit() == NextSU ? (Pred.getKind() != SDep::Anti ||872 Pred.getReg() != AntiDepReg)873 : (Pred.getKind() == SDep::Data &&874 Pred.getReg() == AntiDepReg)) {875 AntiDepReg = MCRegister();876 break;877 }878 }879 for (const SDep &Pred : PathSU->Preds) {880 if ((Pred.getSUnit() == NextSU) && (Pred.getKind() != SDep::Anti) &&881 (Pred.getKind() != SDep::Output)) {882 LLVM_DEBUG(dbgs() << " (real dependency)\n");883 AntiDepReg = MCRegister();884 break;885 } else if ((Pred.getSUnit() != NextSU) &&886 (Pred.getKind() == SDep::Data) &&887 (Pred.getReg() == AntiDepReg)) {888 LLVM_DEBUG(dbgs() << " (other dependency)\n");889 AntiDepReg = MCRegister();890 break;891 }892 }893 894 if (!AntiDepReg)895 continue;896 }897 898 assert(AntiDepReg);899 900 // Determine AntiDepReg's register group.901 const unsigned GroupIndex = State->GetGroup(AntiDepReg);902 if (GroupIndex == 0) {903 LLVM_DEBUG(dbgs() << " (zero group)\n");904 continue;905 }906 907 LLVM_DEBUG(dbgs() << '\n');908 909 // Look for a suitable register to use to break the anti-dependence.910 std::map<MCRegister, MCRegister> RenameMap;911 if (FindSuitableFreeRegisters(AntiDepReg, GroupIndex, RenameOrder,912 RenameMap)) {913 LLVM_DEBUG(dbgs() << "\tBreaking anti-dependence edge on "914 << printReg(AntiDepReg, TRI) << ":");915 916 // Handle each group register...917 for (const auto &P : RenameMap) {918 MCRegister CurrReg = P.first;919 MCRegister NewReg = P.second;920 921 LLVM_DEBUG(dbgs() << " " << printReg(CurrReg, TRI) << "->"922 << printReg(NewReg, TRI) << "("923 << RegRefs.count(CurrReg) << " refs)");924 925 // Update the references to the old register CurrReg to926 // refer to the new register NewReg.927 for (const auto &Q : make_range(RegRefs.equal_range(CurrReg))) {928 Q.second.Operand->setReg(NewReg);929 // If the SU for the instruction being updated has debug930 // information related to the anti-dependency register, make931 // sure to update that as well.932 const SUnit *SU = MISUnitMap[Q.second.Operand->getParent()];933 if (!SU) continue;934 UpdateDbgValues(DbgValues, Q.second.Operand->getParent(),935 AntiDepReg, NewReg);936 }937 938 // We just went back in time and modified history; the939 // liveness information for CurrReg is now inconsistent. Set940 // the state as if it were dead.941 State->UnionGroups(NewReg, 0);942 RegRefs.erase(NewReg);943 DefIndices[NewReg.id()] = DefIndices[CurrReg.id()];944 KillIndices[NewReg.id()] = KillIndices[CurrReg.id()];945 946 State->UnionGroups(CurrReg, 0);947 RegRefs.erase(CurrReg);948 DefIndices[CurrReg.id()] = KillIndices[CurrReg.id()];949 KillIndices[CurrReg.id()] = ~0u;950 assert(((KillIndices[CurrReg.id()] == ~0u) !=951 (DefIndices[CurrReg.id()] == ~0u)) &&952 "Kill and Def maps aren't consistent for AntiDepReg!");953 }954 955 ++Broken;956 LLVM_DEBUG(dbgs() << '\n');957 }958 }959 }960 961 ScanInstruction(MI, Count);962 }963 964 return Broken;965}966 967AntiDepBreaker *llvm::createAggressiveAntiDepBreaker(968 MachineFunction &MFi, const RegisterClassInfo &RCI,969 TargetSubtargetInfo::RegClassVector &CriticalPathRCs) {970 return new AggressiveAntiDepBreaker(MFi, RCI, CriticalPathRCs);971}972