contrib/llvm/lib/CodeGen/AggressiveAntiDepBreaker.cpp

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