LCOV - code coverage report
Current view: top level - lib/CodeGen - AggressiveAntiDepBreaker.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 396 402 98.5 %
Date: 2017-09-14 15:23:50 Functions: 22 24 91.7 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===----- AggressiveAntiDepBreaker.cpp - Anti-dep breaker ----------------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file implements the AggressiveAntiDepBreaker class, which
      11             : // implements register anti-dependence breaking during post-RA
      12             : // scheduling. It attempts to break all anti-dependencies within a
      13             : // block.
      14             : //
      15             : //===----------------------------------------------------------------------===//
      16             : 
      17             : #include "AggressiveAntiDepBreaker.h"
      18             : #include "llvm/CodeGen/MachineBasicBlock.h"
      19             : #include "llvm/CodeGen/MachineFrameInfo.h"
      20             : #include "llvm/CodeGen/MachineInstr.h"
      21             : #include "llvm/CodeGen/RegisterClassInfo.h"
      22             : #include "llvm/Support/CommandLine.h"
      23             : #include "llvm/Support/Debug.h"
      24             : #include "llvm/Support/ErrorHandling.h"
      25             : #include "llvm/Support/raw_ostream.h"
      26             : #include "llvm/Target/TargetInstrInfo.h"
      27             : #include "llvm/Target/TargetRegisterInfo.h"
      28             : using namespace llvm;
      29             : 
      30             : #define DEBUG_TYPE "post-RA-sched"
      31             : 
      32             : // If DebugDiv > 0 then only break antidep with (ID % DebugDiv) == DebugMod
      33             : static cl::opt<int>
      34       72306 : DebugDiv("agg-antidep-debugdiv",
      35      216918 :          cl::desc("Debug control for aggressive anti-dep breaker"),
      36      289224 :          cl::init(0), cl::Hidden);
      37             : static cl::opt<int>
      38       72306 : DebugMod("agg-antidep-debugmod",
      39      216918 :          cl::desc("Debug control for aggressive anti-dep breaker"),
      40      289224 :          cl::init(0), cl::Hidden);
      41             : 
      42       12211 : AggressiveAntiDepState::AggressiveAntiDepState(const unsigned TargetRegs,
      43       12211 :                                                MachineBasicBlock *BB) :
      44             :   NumTargetRegs(TargetRegs), GroupNodes(TargetRegs, 0),
      45             :   GroupNodeIndices(TargetRegs, 0),
      46             :   KillIndices(TargetRegs, 0),
      47      122110 :   DefIndices(TargetRegs, 0)
      48             : {
      49       12211 :   const unsigned BBSize = BB->size();
      50     3511851 :   for (unsigned i = 0; i < NumTargetRegs; ++i) {
      51             :     // Initialize all registers to be in their own group. Initially we
      52             :     // assign the register to the same-indexed GroupNode.
      53     6999280 :     GroupNodeIndices[i] = i;
      54             :     // Initialize the indices to indicate that no registers are live.
      55     6999280 :     KillIndices[i] = ~0u;
      56     6999280 :     DefIndices[i] = BBSize;
      57             :   }
      58       12211 : }
      59             : 
      60           0 : unsigned AggressiveAntiDepState::GetGroup(unsigned Reg) {
      61    14556644 :   unsigned Node = GroupNodeIndices[Reg];
      62    22296410 :   while (GroupNodes[Node] != Node)
      63             :     Node = GroupNodes[Node];
      64             : 
      65           0 :   return Node;
      66             : }
      67             : 
      68        2417 : void AggressiveAntiDepState::GetGroupRegs(
      69             :   unsigned Group,
      70             :   std::vector<unsigned> &Regs,
      71             :   std::multimap<unsigned, AggressiveAntiDepState::RegisterReference> *RegRefs)
      72             : {
      73      601407 :   for (unsigned Reg = 0; Reg != NumTargetRegs; ++Reg) {
      74     1201794 :     if ((GetGroup(Reg) == Group) && (RegRefs->count(Reg) > 0))
      75        2581 :       Regs.push_back(Reg);
      76             :   }
      77        2417 : }
      78             : 
      79     3337701 : unsigned AggressiveAntiDepState::UnionGroups(unsigned Reg1, unsigned Reg2)
      80             : {
      81             :   assert(GroupNodes[0] == 0 && "GroupNode 0 not parent!");
      82             :   assert(GroupNodeIndices[0] == 0 && "Reg 0 not in Group 0!");
      83             : 
      84             :   // find group for each register
      85     3337701 :   unsigned Group1 = GetGroup(Reg1);
      86     3337701 :   unsigned Group2 = GetGroup(Reg2);
      87             : 
      88             :   // if either group is 0, then that must become the parent
      89     3337701 :   unsigned Parent = (Group1 == 0) ? Group1 : Group2;
      90     3337701 :   unsigned Other = (Parent == Group1) ? Group2 : Group1;
      91     6675402 :   GroupNodes.at(Other) = Parent;
      92     3337701 :   return Parent;
      93             : }
      94             : 
      95      123918 : unsigned AggressiveAntiDepState::LeaveGroup(unsigned Reg)
      96             : {
      97             :   // Create a new GroupNode for Reg. Reg's existing GroupNode must
      98             :   // stay as is because there could be other GroupNodes referring to
      99             :   // it.
     100      247836 :   unsigned idx = GroupNodes.size();
     101      123918 :   GroupNodes.push_back(idx);
     102      247836 :   GroupNodeIndices[Reg] = idx;
     103      123918 :   return idx;
     104             : }
     105             : 
     106           0 : bool AggressiveAntiDepState::IsLive(unsigned Reg)
     107             : {
     108             :   // KillIndex must be defined and DefIndex not defined for a register
     109             :   // to be live.
     110    11990560 :   return((KillIndices[Reg] != ~0u) && (DefIndices[Reg] == ~0u));
     111             : }
     112             : 
     113        7427 : AggressiveAntiDepBreaker::AggressiveAntiDepBreaker(
     114             :     MachineFunction &MFi, const RegisterClassInfo &RCI,
     115        7427 :     TargetSubtargetInfo::RegClassVector &CriticalPathRCs)
     116        7427 :     : AntiDepBreaker(), MF(MFi), MRI(MF.getRegInfo()),
     117        7427 :       TII(MF.getSubtarget().getInstrInfo()),
     118        7427 :       TRI(MF.getSubtarget().getRegisterInfo()), RegClassInfo(RCI),
     119       37135 :       State(nullptr) {
     120             :   /* Collect a bitset of all registers that are only broken if they
     121             :      are on the critical path. */
     122       21418 :   for (unsigned i = 0, e = CriticalPathRCs.size(); i < e; ++i) {
     123       19692 :     BitVector CPSet = TRI->getAllocatableSet(MF, CriticalPathRCs[i]);
     124       13128 :     if (CriticalPathSet.none())
     125        6564 :       CriticalPathSet = CPSet;
     126             :     else
     127           0 :       CriticalPathSet |= CPSet;
     128             :    }
     129             : 
     130             :   DEBUG(dbgs() << "AntiDep Critical-Path Registers:");
     131             :   DEBUG(for (unsigned r : CriticalPathSet.set_bits())
     132             :           dbgs() << " " << TRI->getName(r));
     133             :   DEBUG(dbgs() << '\n');
     134        7427 : }
     135             : 
     136       29708 : AggressiveAntiDepBreaker::~AggressiveAntiDepBreaker() {
     137        7427 :   delete State;
     138       14854 : }
     139             : 
     140       12211 : void AggressiveAntiDepBreaker::StartBlock(MachineBasicBlock *BB) {
     141             :   assert(!State);
     142       12211 :   State = new AggressiveAntiDepState(TRI->getNumRegs(), BB);
     143             : 
     144       12211 :   bool IsReturnBlock = BB->isReturnBlock();
     145       12211 :   std::vector<unsigned> &KillIndices = State->GetKillIndices();
     146       12211 :   std::vector<unsigned> &DefIndices = State->GetDefIndices();
     147             : 
     148             :   // Examine the live-in regs of all successors.
     149       12211 :   for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
     150       31434 :          SE = BB->succ_end(); SI != SE; ++SI)
     151       39877 :     for (const auto &LI : (*SI)->liveins()) {
     152      120364 :       for (MCRegAliasIterator AI(LI.PhysReg, TRI, true); AI.isValid(); ++AI) {
     153       41341 :         unsigned Reg = *AI;
     154       41341 :         State->UnionGroups(Reg, 0);
     155      124023 :         KillIndices[Reg] = BB->size();
     156       82682 :         DefIndices[Reg] = ~0u;
     157             :       }
     158             :     }
     159             : 
     160             :   // Mark live-out callee-saved registers. In a return block this is
     161             :   // all callee-saved registers. In non-return this is any
     162             :   // callee-saved register that is not saved in the prolog.
     163       12211 :   const MachineFrameInfo &MFI = MF.getFrameInfo();
     164       12211 :   BitVector Pristine = MFI.getPristineRegs(MF);
     165      546791 :   for (const MCPhysReg *I = MF.getRegInfo().getCalleeSavedRegs(); *I;
     166             :        ++I) {
     167      534580 :     unsigned Reg = *I;
     168      728953 :     if (!IsReturnBlock && !Pristine.test(Reg))
     169        7578 :       continue;
     170     3910462 :     for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
     171     1428229 :       unsigned AliasReg = *AI;
     172     1428229 :       State->UnionGroups(AliasReg, 0);
     173     4284687 :       KillIndices[AliasReg] = BB->size();
     174     2856458 :       DefIndices[AliasReg] = ~0u;
     175             :     }
     176             :   }
     177       12211 : }
     178             : 
     179       12211 : void AggressiveAntiDepBreaker::FinishBlock() {
     180       12211 :   delete State;
     181       12211 :   State = nullptr;
     182       12211 : }
     183             : 
     184       15647 : void AggressiveAntiDepBreaker::Observe(MachineInstr &MI, unsigned Count,
     185             :                                        unsigned InsertPosIndex) {
     186             :   assert(Count < InsertPosIndex && "Instruction index out of expected range!");
     187             : 
     188       31294 :   std::set<unsigned> PassthruRegs;
     189       15647 :   GetPassthruRegs(MI, PassthruRegs);
     190       15647 :   PrescanInstruction(MI, Count, PassthruRegs);
     191       15647 :   ScanInstruction(MI, Count);
     192             : 
     193             :   DEBUG(dbgs() << "Observe: ");
     194             :   DEBUG(MI.dump());
     195             :   DEBUG(dbgs() << "\tRegs:");
     196             : 
     197       15647 :   std::vector<unsigned> &DefIndices = State->GetDefIndices();
     198     4584697 :   for (unsigned Reg = 0; Reg != TRI->getNumRegs(); ++Reg) {
     199             :     // If Reg is current live, then mark that it can't be renamed as
     200             :     // we don't know the extent of its live-range anymore (now that it
     201             :     // has been scheduled). If it is not live but was defined in the
     202             :     // previous schedule region, then set its def index to the most
     203             :     // conservative location (i.e. the beginning of the previous
     204             :     // schedule region).
     205     6374361 :     if (State->IsLive(Reg)) {
     206             :       DEBUG(if (State->GetGroup(Reg) != 0)
     207             :               dbgs() << " " << TRI->getName(Reg) << "=g" <<
     208             :                 State->GetGroup(Reg) << "->g0(region live-out)");
     209     1805311 :       State->UnionGroups(Reg, 0);
     210     5527478 :     } else if ((DefIndices[Reg] < InsertPosIndex)
     211     2763739 :                && (DefIndices[Reg] >= Count)) {
     212       22267 :       DefIndices[Reg] = Count;
     213             :     }
     214             :   }
     215             :   DEBUG(dbgs() << '\n');
     216       15647 : }
     217             : 
     218      168701 : bool AggressiveAntiDepBreaker::IsImplicitDefUse(MachineInstr &MI,
     219             :                                                 MachineOperand &MO) {
     220      337402 :   if (!MO.isReg() || !MO.isImplicit())
     221             :     return false;
     222             : 
     223       48419 :   unsigned Reg = MO.getReg();
     224       48419 :   if (Reg == 0)
     225             :     return false;
     226             : 
     227       48419 :   MachineOperand *Op = nullptr;
     228       48419 :   if (MO.isDef())
     229         281 :     Op = MI.findRegisterUseOperand(Reg, true);
     230             :   else
     231        2023 :     Op = MI.findRegisterDefOperand(Reg);
     232             : 
     233        4608 :   return(Op && Op->isImplicit());
     234             : }
     235             : 
     236       68028 : void AggressiveAntiDepBreaker::GetPassthruRegs(
     237             :     MachineInstr &MI, std::set<unsigned> &PassthruRegs) {
     238      286510 :   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
     239      436964 :     MachineOperand &MO = MI.getOperand(i);
     240      218482 :     if (!MO.isReg()) continue;
     241      339654 :     if ((MO.isDef() && MI.isRegTiedToUseOperand(i)) ||
     242      168701 :         IsImplicitDefUse(MI, MO)) {
     243        4278 :       const unsigned Reg = MO.getReg();
     244        4278 :       for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
     245       10265 :            SubRegs.isValid(); ++SubRegs)
     246       17961 :         PassthruRegs.insert(*SubRegs);
     247             :     }
     248             :   }
     249       68028 : }
     250             : 
     251             : /// AntiDepEdges - Return in Edges the anti- and output- dependencies
     252             : /// in SU that we want to consider for breaking.
     253       52381 : static void AntiDepEdges(const SUnit *SU, std::vector<const SDep*>& Edges) {
     254      104762 :   SmallSet<unsigned, 4> RegSet;
     255      258173 :   for (SUnit::const_pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end();
     256      153411 :        P != PE; ++P) {
     257      188455 :     if ((P->getKind() == SDep::Anti) || (P->getKind() == SDep::Output)) {
     258       29792 :       if (RegSet.insert(P->getReg()).second)
     259       36114 :         Edges.push_back(&*P);
     260             :     }
     261             :   }
     262       52381 : }
     263             : 
     264             : /// CriticalPathStep - Return the next SUnit after SU on the bottom-up
     265             : /// critical path.
     266       27734 : static const SUnit *CriticalPathStep(const SUnit *SU) {
     267       27734 :   const SDep *Next = nullptr;
     268       27734 :   unsigned NextDepth = 0;
     269             :   // Find the predecessor edge with the greatest depth.
     270       27734 :   if (SU) {
     271      126366 :     for (SUnit::const_pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end();
     272       70898 :          P != PE; ++P) {
     273       43164 :       const SUnit *PredSU = P->getSUnit();
     274       43164 :       unsigned PredLatency = P->getLatency();
     275       43164 :       unsigned PredTotalLatency = PredSU->getDepth() + PredLatency;
     276             :       // In the case of a latency tie, prefer an anti-dependency edge over
     277             :       // other types of edges.
     278       43164 :       if (NextDepth < PredTotalLatency ||
     279        8525 :           (NextDepth == PredTotalLatency && P->getKind() == SDep::Anti)) {
     280             :         NextDepth = PredTotalLatency;
     281             :         Next = &*P;
     282             :       }
     283             :     }
     284             :   }
     285             : 
     286       44228 :   return (Next) ? Next->getSUnit() : nullptr;
     287             : }
     288             : 
     289      170953 : void AggressiveAntiDepBreaker::HandleLastUse(unsigned Reg, unsigned KillIdx,
     290             :                                              const char *tag,
     291             :                                              const char *header,
     292             :                                              const char *footer) {
     293      170953 :   std::vector<unsigned> &KillIndices = State->GetKillIndices();
     294      170953 :   std::vector<unsigned> &DefIndices = State->GetDefIndices();
     295             :   std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
     296      341906 :     RegRefs = State->GetRegRefs();
     297             : 
     298             :   // FIXME: We must leave subregisters of live super registers as live, so that
     299             :   // we don't clear out the register tracking information for subregisters of
     300             :   // super registers we're still tracking (and with which we're unioning
     301             :   // subregister definitions).
     302     1056296 :   for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
     303      833676 :     if (TRI->isSuperRegister(Reg, *AI) && State->IsLive(*AI)) {
     304             :       DEBUG(if (!header && footer) dbgs() << footer);
     305       15094 :       return;
     306             :     }
     307             : 
     308      155859 :   if (!State->IsLive(Reg)) {
     309      161076 :     KillIndices[Reg] = KillIdx;
     310      161076 :     DefIndices[Reg] = ~0u;
     311       80538 :     RegRefs.erase(Reg);
     312       80538 :     State->LeaveGroup(Reg);
     313             :     DEBUG(if (header) {
     314             :         dbgs() << header << TRI->getName(Reg); header = nullptr; });
     315             :     DEBUG(dbgs() << "->g" << State->GetGroup(Reg) << tag);
     316             :     // Repeat for subregisters. Note that we only do this if the superregister
     317             :     // was not live because otherwise, regardless whether we have an explicit
     318             :     // use of the subregister, the subregister's contents are needed for the
     319             :     // uses of the superregister.
     320      207053 :     for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
     321       91954 :       unsigned SubregReg = *SubRegs;
     322       45977 :       if (!State->IsLive(SubregReg)) {
     323       86760 :         KillIndices[SubregReg] = KillIdx;
     324       86760 :         DefIndices[SubregReg] = ~0u;
     325       43380 :         RegRefs.erase(SubregReg);
     326       43380 :         State->LeaveGroup(SubregReg);
     327             :         DEBUG(if (header) {
     328             :             dbgs() << header << TRI->getName(Reg); header = nullptr; });
     329             :         DEBUG(dbgs() << " " << TRI->getName(SubregReg) << "->g" <<
     330             :               State->GetGroup(SubregReg) << tag);
     331             :       }
     332             :     }
     333             :   }
     334             : 
     335             :   DEBUG(if (!header && footer) dbgs() << footer);
     336             : }
     337             : 
     338       68028 : void AggressiveAntiDepBreaker::PrescanInstruction(
     339             :     MachineInstr &MI, unsigned Count, std::set<unsigned> &PassthruRegs) {
     340       68028 :   std::vector<unsigned> &DefIndices = State->GetDefIndices();
     341             :   std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
     342      136056 :     RegRefs = State->GetRegRefs();
     343             : 
     344             :   // Handle dead defs by simulating a last-use of the register just
     345             :   // after the def. A dead def can occur because the def is truly
     346             :   // dead, or because only a subregister is live at the def. If we
     347             :   // don't do this the dead def will be incorrectly merged into the
     348             :   // previous def.
     349      286510 :   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
     350      436964 :     MachineOperand &MO = MI.getOperand(i);
     351      389435 :     if (!MO.isReg() || !MO.isDef()) continue;
     352       56054 :     unsigned Reg = MO.getReg();
     353       56054 :     if (Reg == 0) continue;
     354             : 
     355       56054 :     HandleLastUse(Reg, Count + 1, "", "\tDead Def: ", "\n");
     356             :   }
     357             : 
     358             :   DEBUG(dbgs() << "\tDef Groups:");
     359      286510 :   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
     360      436964 :     MachineOperand &MO = MI.getOperand(i);
     361      551863 :     if (!MO.isReg() || !MO.isDef()) continue;
     362       56054 :     unsigned Reg = MO.getReg();
     363       56054 :     if (Reg == 0) continue;
     364             : 
     365             :     DEBUG(dbgs() << " " << TRI->getName(Reg) << "=g" << State->GetGroup(Reg));
     366             : 
     367             :     // If MI's defs have a special allocation requirement, don't allow
     368             :     // any def registers to be changed. Also assume all registers
     369             :     // defined in a call must not be changed (ABI). Inline assembly may
     370             :     // reference either system calls or the register directly. Skip it until we
     371             :     // can tell user specified registers from compiler-specified.
     372      158329 :     if (MI.isCall() || MI.hasExtraDefRegAllocReq() || TII->isPredicated(MI) ||
     373       50585 :         MI.isInlineAsm()) {
     374             :       DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)");
     375        6456 :       State->UnionGroups(Reg, 0);
     376             :     }
     377             : 
     378             :     // Any aliased that are live at this point are completely or
     379             :     // partially defined here, so group those aliases with Reg.
     380      252944 :     for (MCRegAliasIterator AI(Reg, TRI, false); AI.isValid(); ++AI) {
     381       70418 :       unsigned AliasReg = *AI;
     382      114401 :       if (State->IsLive(AliasReg)) {
     383       43983 :         State->UnionGroups(Reg, AliasReg);
     384             :         DEBUG(dbgs() << "->g" << State->GetGroup(Reg) << "(via " <<
     385             :               TRI->getName(AliasReg) << ")");
     386             :       }
     387             :     }
     388             : 
     389             :     // Note register reference...
     390       56054 :     const TargetRegisterClass *RC = nullptr;
     391      112108 :     if (i < MI.getDesc().getNumOperands())
     392       42988 :       RC = TII->getRegClass(MI.getDesc(), i, TRI, MF);
     393       56054 :     AggressiveAntiDepState::RegisterReference RR = { &MO, RC };
     394      168162 :     RegRefs.insert(std::make_pair(Reg, RR));
     395             :   }
     396             : 
     397             :   DEBUG(dbgs() << '\n');
     398             : 
     399             :   // Scan the register defs for this instruction and update
     400             :   // live-ranges.
     401      286510 :   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
     402      436964 :     MachineOperand &MO = MI.getOperand(i);
     403      551863 :     if (!MO.isReg() || !MO.isDef()) continue;
     404       56054 :     unsigned Reg = MO.getReg();
     405       56054 :     if (Reg == 0) continue;
     406             :     // Ignore KILLs and passthru registers for liveness...
     407      112108 :     if (MI.isKill() || (PassthruRegs.count(Reg) != 0))
     408        4433 :       continue;
     409             : 
     410             :     // Update def for Reg and aliases.
     411      406535 :     for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
     412             :       // We need to be careful here not to define already-live super registers.
     413             :       // If the super register is already live, then this definition is not
     414             :       // a definition of the whole super register (just a partial insertion
     415             :       // into it). Earlier subregister definitions (which we've not yet visited
     416             :       // because we're iterating bottom-up) need to be linked to the same group
     417             :       // as this definition.
     418      285606 :       if (TRI->isSuperRegister(Reg, *AI) && State->IsLive(*AI))
     419        7041 :         continue;
     420             : 
     421      237590 :       DefIndices[*AI] = Count;
     422             :     }
     423             :   }
     424       68028 : }
     425             : 
     426       68028 : void AggressiveAntiDepBreaker::ScanInstruction(MachineInstr &MI,
     427             :                                                unsigned Count) {
     428             :   DEBUG(dbgs() << "\tUse Groups:");
     429             :   std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
     430      136056 :     RegRefs = State->GetRegRefs();
     431             : 
     432             :   // If MI's uses have special allocation requirement, don't allow
     433             :   // any use registers to be changed. Also assume all registers
     434             :   // used in a call must not be changed (ABI).
     435             :   // Inline Assembly register uses also cannot be safely changed.
     436             :   // FIXME: The issue with predicated instruction is more complex. We are being
     437             :   // conservatively here because the kill markers cannot be trusted after
     438             :   // if-conversion:
     439             :   // %R6<def> = LDR %SP, %reg0, 92, pred:14, pred:%reg0; mem:LD4[FixedStack14]
     440             :   // ...
     441             :   // STR %R0, %R6<kill>, %reg0, 0, pred:0, pred:%CPSR; mem:ST4[%395]
     442             :   // %R6<def> = LDR %SP, %reg0, 100, pred:0, pred:%CPSR; mem:LD4[FixedStack12]
     443             :   // STR %R0, %R6<kill>, %reg0, 0, pred:14, pred:%reg0; mem:ST4[%396](align=8)
     444             :   //
     445             :   // The first R6 kill is not really a kill since it's killed by a predicated
     446             :   // instruction which may not be executed. The second R6 def may or may not
     447             :   // re-define R6 so it's not safe to change it since the last R6 use cannot be
     448             :   // changed.
     449      200762 :   bool Special = MI.isCall() || MI.hasExtraSrcRegAllocReq() ||
     450      199979 :                  TII->isPredicated(MI) || MI.isInlineAsm();
     451             : 
     452             :   // Scan the register uses for this instruction and update
     453             :   // live-ranges, groups and RegRefs.
     454      286510 :   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
     455      436964 :     MachineOperand &MO = MI.getOperand(i);
     456      389435 :     if (!MO.isReg() || !MO.isUse()) continue;
     457      114899 :     unsigned Reg = MO.getReg();
     458      114899 :     if (Reg == 0) continue;
     459             : 
     460             :     DEBUG(dbgs() << " " << TRI->getName(Reg) << "=g" <<
     461             :           State->GetGroup(Reg));
     462             : 
     463             :     // It wasn't previously live but now it is, this is a kill. Forget
     464             :     // the previous live-range information and start a new live-range
     465             :     // for the register.
     466      114899 :     HandleLastUse(Reg, Count, "(last-use)");
     467             : 
     468      114899 :     if (Special) {
     469             :       DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)");
     470        7989 :       State->UnionGroups(Reg, 0);
     471             :     }
     472             : 
     473             :     // Note register reference...
     474      114899 :     const TargetRegisterClass *RC = nullptr;
     475      229798 :     if (i < MI.getDesc().getNumOperands())
     476       78584 :       RC = TII->getRegClass(MI.getDesc(), i, TRI, MF);
     477      114899 :     AggressiveAntiDepState::RegisterReference RR = { &MO, RC };
     478      344697 :     RegRefs.insert(std::make_pair(Reg, RR));
     479             :   }
     480             : 
     481             :   DEBUG(dbgs() << '\n');
     482             : 
     483             :   // Form a group of all defs and uses of a KILL instruction to ensure
     484             :   // that all registers are renamed as a group.
     485       68028 :   if (MI.isKill()) {
     486             :     DEBUG(dbgs() << "\tKill Group:");
     487             : 
     488         180 :     unsigned FirstReg = 0;
     489         712 :     for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
     490        1064 :       MachineOperand &MO = MI.getOperand(i);
     491         532 :       if (!MO.isReg()) continue;
     492         532 :       unsigned Reg = MO.getReg();
     493         532 :       if (Reg == 0) continue;
     494             : 
     495         532 :       if (FirstReg != 0) {
     496             :         DEBUG(dbgs() << "=" << TRI->getName(Reg));
     497         352 :         State->UnionGroups(FirstReg, Reg);
     498             :       } else {
     499             :         DEBUG(dbgs() << " " << TRI->getName(Reg));
     500             :         FirstReg = Reg;
     501             :       }
     502             :     }
     503             : 
     504             :     DEBUG(dbgs() << "->g" << State->GetGroup(FirstReg) << '\n');
     505             :   }
     506       68028 : }
     507             : 
     508        2581 : BitVector AggressiveAntiDepBreaker::GetRenameRegisters(unsigned Reg) {
     509        2581 :   BitVector BV(TRI->getNumRegs(), false);
     510        2581 :   bool first = true;
     511             : 
     512             :   // Check all references that need rewriting for Reg. For each, use
     513             :   // the corresponding register class to narrow the set of registers
     514             :   // that are appropriate for renaming.
     515       13173 :   for (const auto &Q : make_range(State->GetRegRefs().equal_range(Reg))) {
     516        5430 :     const TargetRegisterClass *RC = Q.second.RC;
     517        5430 :     if (!RC) continue;
     518             : 
     519       10614 :     BitVector RCBV = TRI->getAllocatableSet(MF, RC);
     520        5307 :     if (first) {
     521        2581 :       BV |= RCBV;
     522        2581 :       first = false;
     523             :     } else {
     524        2726 :       BV &= RCBV;
     525             :     }
     526             : 
     527             :     DEBUG(dbgs() << " " << TRI->getRegClassName(RC));
     528             :   }
     529             : 
     530        2581 :   return BV;
     531             : }
     532             : 
     533        2417 : bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters(
     534             :                                 unsigned AntiDepGroupIndex,
     535             :                                 RenameOrderType& RenameOrder,
     536             :                                 std::map<unsigned, unsigned> &RenameMap) {
     537        2417 :   std::vector<unsigned> &KillIndices = State->GetKillIndices();
     538        2417 :   std::vector<unsigned> &DefIndices = State->GetDefIndices();
     539             :   std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
     540        4834 :     RegRefs = State->GetRegRefs();
     541             : 
     542             :   // Collect all referenced registers in the same group as
     543             :   // AntiDepReg. These all need to be renamed together if we are to
     544             :   // break the anti-dependence.
     545        4834 :   std::vector<unsigned> Regs;
     546        2417 :   State->GetGroupRegs(AntiDepGroupIndex, Regs, &RegRefs);
     547             :   assert(Regs.size() > 0 && "Empty register group!");
     548        4834 :   if (Regs.size() == 0)
     549             :     return false;
     550             : 
     551             :   // Find the "superest" register in the group. At the same time,
     552             :   // collect the BitVector of registers that can be used to rename
     553             :   // each register.
     554             :   DEBUG(dbgs() << "\tRename Candidates for Group g" << AntiDepGroupIndex
     555             :         << ":\n");
     556        2417 :   std::map<unsigned, BitVector> RenameRegisterMap;
     557        2417 :   unsigned SuperReg = 0;
     558        4998 :   for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
     559        5162 :     unsigned Reg = Regs[i];
     560        2581 :     if ((SuperReg == 0) || TRI->isSuperRegister(SuperReg, Reg))
     561        2519 :       SuperReg = Reg;
     562             : 
     563             :     // If Reg has any references, then collect possible rename regs
     564        2581 :     if (RegRefs.count(Reg) > 0) {
     565             :       DEBUG(dbgs() << "\t\t" << TRI->getName(Reg) << ":");
     566             : 
     567        2581 :       BitVector &BV = RenameRegisterMap[Reg];
     568             :       assert(BV.empty());
     569        7743 :       BV = GetRenameRegisters(Reg);
     570             : 
     571             :       DEBUG({
     572             :         dbgs() << " ::";
     573             :         for (unsigned r : BV.set_bits())
     574             :           dbgs() << " " << TRI->getName(r);
     575             :         dbgs() << "\n";
     576             :       });
     577             :     }
     578             :   }
     579             : 
     580             :   // All group registers should be a subreg of SuperReg.
     581        7415 :   for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
     582        5162 :     unsigned Reg = Regs[i];
     583        2581 :     if (Reg == SuperReg) continue;
     584         328 :     bool IsSub = TRI->isSubRegister(SuperReg, Reg);
     585             :     // FIXME: remove this once PR18663 has been properly fixed. For now,
     586             :     // return a conservative answer:
     587             :     // assert(IsSub && "Expecting group subregister");
     588         164 :     if (!IsSub)
     589             :       return false;
     590             :   }
     591             : 
     592             : #ifndef NDEBUG
     593             :   // If DebugDiv > 0 then only rename (renamecnt % DebugDiv) == DebugMod
     594             :   if (DebugDiv > 0) {
     595             :     static int renamecnt = 0;
     596             :     if (renamecnt++ % DebugDiv != DebugMod)
     597             :       return false;
     598             : 
     599             :     dbgs() << "*** Performing rename " << TRI->getName(SuperReg) <<
     600             :       " for debug ***\n";
     601             :   }
     602             : #endif
     603             : 
     604             :   // Check each possible rename register for SuperReg in round-robin
     605             :   // order. If that register is available, and the corresponding
     606             :   // registers are available for the other group subregisters, then we
     607             :   // can use those registers to rename.
     608             : 
     609             :   // FIXME: Using getMinimalPhysRegClass is very conservative. We should
     610             :   // check every use of the register and find the largest register class
     611             :   // that can be used in all of them.
     612             :   const TargetRegisterClass *SuperRC =
     613        4834 :     TRI->getMinimalPhysRegClass(SuperReg, MVT::Other);
     614             : 
     615        2417 :   ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(SuperRC);
     616        2417 :   if (Order.empty()) {
     617             :     DEBUG(dbgs() << "\tEmpty Super Regclass!!\n");
     618             :     return false;
     619             :   }
     620             : 
     621             :   DEBUG(dbgs() << "\tFind Registers:");
     622             : 
     623        7251 :   RenameOrder.insert(RenameOrderType::value_type(SuperRC, Order.size()));
     624             : 
     625        2417 :   unsigned OrigR = RenameOrder[SuperRC];
     626        2417 :   unsigned EndR = ((OrigR == Order.size()) ? 0 : OrigR);
     627        2417 :   unsigned R = OrigR;
     628             :   do {
     629       24203 :     if (R == 0) R = Order.size();
     630       24203 :     --R;
     631       48406 :     const unsigned NewSuperReg = Order[R];
     632             :     // Don't consider non-allocatable registers
     633       24203 :     if (!MRI.isAllocatable(NewSuperReg)) continue;
     634             :     // Don't replace a register with itself.
     635       24203 :     if (NewSuperReg == SuperReg) continue;
     636             : 
     637             :     DEBUG(dbgs() << " [" << TRI->getName(NewSuperReg) << ':');
     638       23406 :     RenameMap.clear();
     639             : 
     640             :     // For each referenced group register (which must be a SuperReg or
     641             :     // a subregister of SuperReg), find the corresponding subregister
     642             :     // of NewSuperReg and make sure it is free to be renamed.
     643       48835 :     for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
     644       47052 :       unsigned Reg = Regs[i];
     645       23526 :       unsigned NewReg = 0;
     646       23526 :       if (Reg == SuperReg) {
     647             :         NewReg = NewSuperReg;
     648             :       } else {
     649         556 :         unsigned NewSubRegIdx = TRI->getSubRegIndex(SuperReg, Reg);
     650         556 :         if (NewSubRegIdx != 0)
     651         556 :           NewReg = TRI->getSubReg(NewSuperReg, NewSubRegIdx);
     652             :       }
     653             : 
     654             :       DEBUG(dbgs() << " " << TRI->getName(NewReg));
     655             : 
     656             :       // Check if Reg can be renamed to NewReg.
     657       47052 :       if (!RenameRegisterMap[Reg].test(NewReg)) {
     658             :         DEBUG(dbgs() << "(no rename)");
     659       21503 :         goto next_super_reg;
     660             :       }
     661             : 
     662             :       // If NewReg is dead and NewReg's most recent def is not before
     663             :       // Regs's kill, it's safe to replace Reg with NewReg. We
     664             :       // must also check all aliases of NewReg, because we can't define a
     665             :       // register when any sub or super is already live.
     666       32819 :       if (State->IsLive(NewReg) || (KillIndices[Reg] > DefIndices[NewReg])) {
     667             :         DEBUG(dbgs() << "(live)");
     668             :         goto next_super_reg;
     669             :       } else {
     670        2593 :         bool found = false;
     671       10160 :         for (MCRegAliasIterator AI(NewReg, TRI, false); AI.isValid(); ++AI) {
     672        3057 :           unsigned AliasReg = *AI;
     673        5883 :           if (State->IsLive(AliasReg) ||
     674        8478 :               (KillIndices[Reg] > DefIndices[AliasReg])) {
     675             :             DEBUG(dbgs() << "(alias " << TRI->getName(AliasReg) << " live)");
     676             :             found = true;
     677             :             break;
     678             :           }
     679             :         }
     680        2593 :         if (found)
     681             :           goto next_super_reg;
     682             :       }
     683             : 
     684             :       // We cannot rename 'Reg' to 'NewReg' if one of the uses of 'Reg' also
     685             :       // defines 'NewReg' via an early-clobber operand.
     686        8201 :       for (const auto &Q : make_range(RegRefs.equal_range(Reg))) {
     687        4155 :         MachineInstr *UseMI = Q.second.Operand->getParent();
     688        4155 :         int Idx = UseMI->findRegisterDefOperandIdx(NewReg, false, true, TRI);
     689        4155 :         if (Idx == -1)
     690        4143 :           continue;
     691             : 
     692          36 :         if (UseMI->getOperand(Idx).isEarlyClobber()) {
     693             :           DEBUG(dbgs() << "(ec)");
     694             :           goto next_super_reg;
     695             :         }
     696             :       }
     697             : 
     698             :       // Also, we cannot rename 'Reg' to 'NewReg' if the instruction defining
     699             :       // 'Reg' is an early-clobber define and that instruction also uses
     700             :       // 'NewReg'.
     701        8201 :       for (const auto &Q : make_range(RegRefs.equal_range(Reg))) {
     702       14441 :         if (!Q.second.Operand->isDef() || !Q.second.Operand->isEarlyClobber())
     703        4155 :           continue;
     704             : 
     705           0 :         MachineInstr *DefMI = Q.second.Operand->getParent();
     706           0 :         if (DefMI->readsRegister(NewReg, TRI)) {
     707             :           DEBUG(dbgs() << "(ec)");
     708             :           goto next_super_reg;
     709             :         }
     710             :       }
     711             : 
     712             :       // Record that 'Reg' can be renamed to 'NewReg'.
     713        4046 :       RenameMap.insert(std::pair<unsigned, unsigned>(Reg, NewReg));
     714             :     }
     715             : 
     716             :     // If we fall-out here, then every register in the group can be
     717             :     // renamed, as recorded in RenameMap.
     718        1903 :     RenameOrder.erase(SuperRC);
     719        3806 :     RenameOrder.insert(RenameOrderType::value_type(SuperRC, R));
     720             :     DEBUG(dbgs() << "]\n");
     721        1903 :     return true;
     722             : 
     723       22300 :   next_super_reg:
     724             :     DEBUG(dbgs() << ']');
     725       22300 :   } while (R != EndR);
     726             : 
     727             :   DEBUG(dbgs() << '\n');
     728             : 
     729             :   // No registers are free and available!
     730             :   return false;
     731             : }
     732             : 
     733             : /// BreakAntiDependencies - Identifiy anti-dependencies within the
     734             : /// ScheduleDAG and break them by renaming registers.
     735             : ///
     736       27858 : unsigned AggressiveAntiDepBreaker::BreakAntiDependencies(
     737             :                               const std::vector<SUnit>& SUnits,
     738             :                               MachineBasicBlock::iterator Begin,
     739             :                               MachineBasicBlock::iterator End,
     740             :                               unsigned InsertPosIndex,
     741             :                               DbgValueVector &DbgValues) {
     742             : 
     743       27858 :   std::vector<unsigned> &KillIndices = State->GetKillIndices();
     744       27858 :   std::vector<unsigned> &DefIndices = State->GetDefIndices();
     745             :   std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
     746       55716 :     RegRefs = State->GetRegRefs();
     747             : 
     748             :   // The code below assumes that there is at least one instruction,
     749             :   // so just duck out immediately if the block is empty.
     750       27858 :   if (SUnits.empty()) return 0;
     751             : 
     752             :   // For each regclass the next register to use for renaming.
     753       12920 :   RenameOrderType RenameOrder;
     754             : 
     755             :   // ...need a map from MI to SUnit.
     756       25840 :   std::map<MachineInstr *, const SUnit *> MISUnitMap;
     757       78221 :   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
     758      104762 :     const SUnit *SU = &SUnits[i];
     759      157143 :     MISUnitMap.insert(std::pair<MachineInstr *, const SUnit *>(SU->getInstr(),
     760             :                                                                SU));
     761             :   }
     762             : 
     763             :   // Track progress along the critical path through the SUnit graph as
     764             :   // we walk the instructions. This is needed for regclasses that only
     765             :   // break critical-path anti-dependencies.
     766             :   const SUnit *CriticalPathSU = nullptr;
     767             :   MachineInstr *CriticalPathMI = nullptr;
     768       12920 :   if (CriticalPathSet.any()) {
     769       66571 :     for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
     770       88182 :       const SUnit *SU = &SUnits[i];
     771       76942 :       if (!CriticalPathSU ||
     772       32851 :           ((SU->getDepth() + SU->Latency) >
     773       32851 :            (CriticalPathSU->getDepth() + CriticalPathSU->Latency))) {
     774             :         CriticalPathSU = SU;
     775             :       }
     776             :     }
     777             : 
     778       11240 :     CriticalPathMI = CriticalPathSU->getInstr();
     779             :   }
     780             : 
     781             : #ifndef NDEBUG
     782             :   DEBUG(dbgs() << "\n===== Aggressive anti-dependency breaking\n");
     783             :   DEBUG(dbgs() << "Available regs:");
     784             :   for (unsigned Reg = 0; Reg < TRI->getNumRegs(); ++Reg) {
     785             :     if (!State->IsLive(Reg))
     786             :       DEBUG(dbgs() << " " << TRI->getName(Reg));
     787             :   }
     788             :   DEBUG(dbgs() << '\n');
     789             : #endif
     790             : 
     791       25840 :   BitVector RegAliases(TRI->getNumRegs());
     792             : 
     793             :   // Attempt to break anti-dependence edges. Walk the instructions
     794             :   // from the bottom up, tracking information about liveness as we go
     795             :   // to help determine which registers are available.
     796       12920 :   unsigned Broken = 0;
     797       12920 :   unsigned Count = InsertPosIndex - 1;
     798       65314 :   for (MachineBasicBlock::iterator I = End, E = Begin;
     799       65314 :        I != E; --Count) {
     800      104788 :     MachineInstr &MI = *--I;
     801             : 
     802       52394 :     if (MI.isDebugValue())
     803          13 :       continue;
     804             : 
     805             :     DEBUG(dbgs() << "Anti: ");
     806             :     DEBUG(MI.dump());
     807             : 
     808      104762 :     std::set<unsigned> PassthruRegs;
     809       52381 :     GetPassthruRegs(MI, PassthruRegs);
     810             : 
     811             :     // Process the defs in MI...
     812       52381 :     PrescanInstruction(MI, Count, PassthruRegs);
     813             : 
     814             :     // The dependence edges that represent anti- and output-
     815             :     // dependencies that are candidates for breaking.
     816      104762 :     std::vector<const SDep *> Edges;
     817       52381 :     const SUnit *PathSU = MISUnitMap[&MI];
     818       52381 :     AntiDepEdges(PathSU, Edges);
     819             : 
     820             :     // If MI is not on the critical path, then we don't rename
     821             :     // registers in the CriticalPathSet.
     822       52381 :     BitVector *ExcludeRegs = nullptr;
     823       52381 :     if (&MI == CriticalPathMI) {
     824       27734 :       CriticalPathSU = CriticalPathStep(CriticalPathSU);
     825       27734 :       CriticalPathMI = (CriticalPathSU) ? CriticalPathSU->getInstr() : nullptr;
     826       24647 :     } else if (CriticalPathSet.any()) {
     827       16357 :       ExcludeRegs = &CriticalPathSet;
     828             :     }
     829             : 
     830             :     // Ignore KILL instructions (they form a group in ScanInstruction
     831             :     // but don't cause any anti-dependence breaking themselves)
     832       52381 :     if (!MI.isKill()) {
     833             :       // Attempt to break each anti-dependency...
     834      122411 :       for (unsigned i = 0, e = Edges.size(); i != e; ++i) {
     835       36018 :         const SDep *Edge = Edges[i];
     836       18009 :         SUnit *NextSU = Edge->getSUnit();
     837             : 
     838       27076 :         if ((Edge->getKind() != SDep::Anti) &&
     839       24659 :             (Edge->getKind() != SDep::Output)) continue;
     840             : 
     841       18009 :         unsigned AntiDepReg = Edge->getReg();
     842             :         DEBUG(dbgs() << "\tAntidep reg: " << TRI->getName(AntiDepReg));
     843             :         assert(AntiDepReg != 0 && "Anti-dependence on reg0?");
     844             : 
     845       18212 :         if (!MRI.isAllocatable(AntiDepReg)) {
     846             :           // Don't break anti-dependencies on non-allocatable registers.
     847             :           DEBUG(dbgs() << " (non-allocatable)\n");
     848         203 :           continue;
     849       26977 :         } else if (ExcludeRegs && ExcludeRegs->test(AntiDepReg)) {
     850             :           // Don't break anti-dependencies for critical path registers
     851             :           // if not on the critical path
     852             :           DEBUG(dbgs() << " (not critical-path)\n");
     853        3318 :           continue;
     854       14488 :         } else if (PassthruRegs.count(AntiDepReg) != 0) {
     855             :           // If the anti-dep register liveness "passes-thru", then
     856             :           // don't try to change it. It will be changed along with
     857             :           // the use if required to break an earlier antidep.
     858             :           DEBUG(dbgs() << " (passthru)\n");
     859         973 :           continue;
     860             :         } else {
     861             :           // No anti-dep breaking for implicit deps
     862       27030 :           MachineOperand *AntiDepOp = MI.findRegisterDefOperand(AntiDepReg);
     863             :           assert(AntiDepOp && "Can't find index for defined register operand");
     864       27843 :           if (!AntiDepOp || AntiDepOp->isImplicit()) {
     865             :             DEBUG(dbgs() << " (implicit)\n");
     866         813 :             continue;
     867             :           }
     868             : 
     869             :           // If the SUnit has other dependencies on the SUnit that
     870             :           // it anti-depends on, don't bother breaking the
     871             :           // anti-dependency since those edges would prevent such
     872             :           // units from being scheduled past each other
     873             :           // regardless.
     874             :           //
     875             :           // Also, if there are dependencies on other SUnits with the
     876             :           // same register as the anti-dependency, don't attempt to
     877             :           // break it.
     878       43831 :           for (SUnit::const_pred_iterator P = PathSU->Preds.begin(),
     879       56533 :                  PE = PathSU->Preds.end(); P != PE; ++P) {
     880       26872 :             if (P->getSUnit() == NextSU ?
     881       13356 :                 (P->getKind() != SDep::Anti || P->getReg() != AntiDepReg) :
     882       13516 :                 (P->getKind() == SDep::Data && P->getReg() == AntiDepReg)) {
     883             :               AntiDepReg = 0;
     884             :               break;
     885             :             }
     886             :           }
     887       39503 :           for (SUnit::const_pred_iterator P = PathSU->Preds.begin(),
     888       12702 :                  PE = PathSU->Preds.end(); P != PE; ++P) {
     889       70145 :             if ((P->getSUnit() == NextSU) && (P->getKind() != SDep::Anti) &&
     890       15017 :                 (P->getKind() != SDep::Output)) {
     891             :               DEBUG(dbgs() << " (real dependency)\n");
     892             :               AntiDepReg = 0;
     893             :               break;
     894       41159 :             } else if ((P->getSUnit() != NextSU) &&
     895       45610 :                        (P->getKind() == SDep::Data) &&
     896        4451 :                        (P->getReg() == AntiDepReg)) {
     897             :               DEBUG(dbgs() << " (other dependency)\n");
     898             :               AntiDepReg = 0;
     899             :               break;
     900             :             }
     901             :           }
     902             : 
     903       12702 :           if (AntiDepReg == 0) continue;
     904             : 
     905             :           // If the definition of the anti-dependency register does not start
     906             :           // a new live range, bail out. This can happen if the anti-dep
     907             :           // register is a sub-register of another register whose live range
     908             :           // spans over PathSU. In such case, PathSU defines only a part of
     909             :           // the larger register.
     910        4257 :           RegAliases.reset();
     911       28634 :           for (MCRegAliasIterator AI(AntiDepReg, TRI, true); AI.isValid(); ++AI)
     912       20120 :             RegAliases.set(*AI);
     913       23592 :           for (SDep S : PathSU->Succs) {
     914       11148 :             SDep::Kind K = S.getKind();
     915       11148 :             if (K != SDep::Data && K != SDep::Output && K != SDep::Anti)
     916        3101 :               continue;
     917        8047 :             unsigned R = S.getReg();
     918       16094 :             if (!RegAliases[R])
     919        1268 :               continue;
     920        8396 :             if (R == AntiDepReg || TRI->isSubRegister(AntiDepReg, R))
     921        6452 :               continue;
     922             :             AntiDepReg = 0;
     923             :             break;
     924             :           }
     925             : 
     926        4257 :           if (AntiDepReg == 0) continue;
     927             :         }
     928             : 
     929             :         assert(AntiDepReg != 0);
     930             :         if (AntiDepReg == 0) continue;
     931             : 
     932             :         // Determine AntiDepReg's register group.
     933        7860 :         const unsigned GroupIndex = State->GetGroup(AntiDepReg);
     934        3930 :         if (GroupIndex == 0) {
     935             :           DEBUG(dbgs() << " (zero group)\n");
     936        1513 :           continue;
     937             :         }
     938             : 
     939             :         DEBUG(dbgs() << '\n');
     940             : 
     941             :         // Look for a suitable register to use to break the anti-dependence.
     942        4834 :         std::map<unsigned, unsigned> RenameMap;
     943        2417 :         if (FindSuitableFreeRegisters(GroupIndex, RenameOrder, RenameMap)) {
     944             :           DEBUG(dbgs() << "\tBreaking anti-dependence edge on "
     945             :                 << TRI->getName(AntiDepReg) << ":");
     946             : 
     947             :           // Handle each group register...
     948             :           for (std::map<unsigned, unsigned>::iterator
     949        3806 :                  S = RenameMap.begin(), E = RenameMap.end(); S != E; ++S) {
     950        2020 :             unsigned CurrReg = S->first;
     951        2020 :             unsigned NewReg = S->second;
     952             : 
     953             :             DEBUG(dbgs() << " " << TRI->getName(CurrReg) << "->" <<
     954             :                   TRI->getName(NewReg) << "(" <<
     955             :                   RegRefs.count(CurrReg) << " refs)");
     956             : 
     957             :             // Update the references to the old register CurrReg to
     958             :             // refer to the new register NewReg.
     959        8192 :             for (const auto &Q : make_range(RegRefs.equal_range(CurrReg))) {
     960        4152 :               Q.second.Operand->setReg(NewReg);
     961             :               // If the SU for the instruction being updated has debug
     962             :               // information related to the anti-dependency register, make
     963             :               // sure to update that as well.
     964        4152 :               const SUnit *SU = MISUnitMap[Q.second.Operand->getParent()];
     965        4152 :               if (!SU) continue;
     966        4152 :               UpdateDbgValues(DbgValues, Q.second.Operand->getParent(),
     967             :                               AntiDepReg, NewReg);
     968             :             }
     969             : 
     970             :             // We just went back in time and modified history; the
     971             :             // liveness information for CurrReg is now inconsistent. Set
     972             :             // the state as if it were dead.
     973        2020 :             State->UnionGroups(NewReg, 0);
     974        2020 :             RegRefs.erase(NewReg);
     975        6060 :             DefIndices[NewReg] = DefIndices[CurrReg];
     976        6060 :             KillIndices[NewReg] = KillIndices[CurrReg];
     977             : 
     978        2020 :             State->UnionGroups(CurrReg, 0);
     979        2020 :             RegRefs.erase(CurrReg);
     980        6060 :             DefIndices[CurrReg] = KillIndices[CurrReg];
     981        4040 :             KillIndices[CurrReg] = ~0u;
     982             :             assert(((KillIndices[CurrReg] == ~0u) !=
     983             :                     (DefIndices[CurrReg] == ~0u)) &&
     984             :                    "Kill and Def maps aren't consistent for AntiDepReg!");
     985             :           }
     986             : 
     987        1903 :           ++Broken;
     988             :           DEBUG(dbgs() << '\n');
     989             :         }
     990             :       }
     991             :     }
     992             : 
     993       52381 :     ScanInstruction(MI, Count);
     994             :   }
     995             : 
     996       12920 :   return Broken;
     997      216918 : }

Generated by: LCOV version 1.13