llvm/lib/MCA/HardwareUnits/RegisterFile.cpp

   1 //===--------------------- RegisterFile.cpp ---------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 /// \file
   9 ///
  10 /// This file defines a register mapping file class.  This class is responsible
  11 /// for managing hardware register files and the tracking of data dependencies
  12 /// between registers.
  13 ///
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/MCA/HardwareUnits/RegisterFile.h"
  17 #include "llvm/MCA/Instruction.h"
  18 #include "llvm/Support/Debug.h"
  19
  20 #define DEBUG_TYPE "llvm-mca"
  21
  22 namespace llvm {
  23 namespace mca {
  24
  25 const unsigned WriteRef::INVALID_IID = std::numeric_limits<unsigned>::max();
  26
  27 WriteRef::WriteRef(unsigned SourceIndex, WriteState *WS)
  28     : IID(SourceIndex), WriteBackCycle(), WriteResID(), RegisterID(),
  29       Write(WS) {}
  30
  31 void WriteRef::commit() {
  32   assert(Write && Write->isExecuted() && "Cannot commit before write back!");
  33   RegisterID = Write->getRegisterID();
  34   WriteResID = Write->getWriteResourceID();
  35   Write = nullptr;
  36 }
  37
  38 void WriteRef::notifyExecuted(unsigned Cycle) {
  39   assert(Write && Write->isExecuted() && "Not executed!");
  40   WriteBackCycle = Cycle;
  41 }
  42
  43 bool WriteRef::hasKnownWriteBackCycle() const {
  44   return isValid() && (!Write || Write->isExecuted());
  45 }
  46
  47 bool WriteRef::isWriteZero() const {
  48   assert(isValid() && "Invalid null WriteState found!");
  49   return getWriteState()->isWriteZero();
  50 }
  51
  52 unsigned WriteRef::getWriteResourceID() const {
  53   if (Write)
  54     return Write->getWriteResourceID();
  55   return WriteResID;
  56 }
  57
  58 MCPhysReg WriteRef::getRegisterID() const {
  59   if (Write)
  60     return Write->getRegisterID();
  61   return RegisterID;
  62 }
  63
  64 RegisterFile::RegisterFile(const MCSchedModel &SM, const MCRegisterInfo &mri,
  65                            unsigned NumRegs)
  66     : MRI(mri),
  67       RegisterMappings(mri.getNumRegs(), {WriteRef(), RegisterRenamingInfo()}),
  68       ZeroRegisters(mri.getNumRegs(), false), CurrentCycle() {
  69   initialize(SM, NumRegs);
  70 }
  71
  72 void RegisterFile::initialize(const MCSchedModel &SM, unsigned NumRegs) {
  73   // Create a default register file that "sees" all the machine registers
  74   // declared by the target. The number of physical registers in the default
  75   // register file is set equal to `NumRegs`. A value of zero for `NumRegs`
  76   // means: this register file has an unbounded number of physical registers.
  77   RegisterFiles.emplace_back(NumRegs);
  78   if (!SM.hasExtraProcessorInfo())
  79     return;
  80
  81   // For each user defined register file, allocate a RegisterMappingTracker
  82   // object. The size of every register file, as well as the mapping between
  83   // register files and register classes is specified via tablegen.
  84   const MCExtraProcessorInfo &Info = SM.getExtraProcessorInfo();
  85
  86   // Skip invalid register file at index 0.
  87   for (unsigned I = 1, E = Info.NumRegisterFiles; I < E; ++I) {
  88     const MCRegisterFileDesc &RF = Info.RegisterFiles[I];
  89     assert(RF.NumPhysRegs && "Invalid PRF with zero physical registers!");
  90
  91     // The cost of a register definition is equivalent to the number of
  92     // physical registers that are allocated at register renaming stage.
  93     unsigned Length = RF.NumRegisterCostEntries;
  94     const MCRegisterCostEntry *FirstElt =
  95         &Info.RegisterCostTable[RF.RegisterCostEntryIdx];
  96     addRegisterFile(RF, ArrayRef<MCRegisterCostEntry>(FirstElt, Length));
  97   }
  98 }
  99
 100 void RegisterFile::cycleStart() {
 101   for (RegisterMappingTracker &RMT : RegisterFiles)
 102     RMT.NumMoveEliminated = 0;
 103 }
 104
 105 void RegisterFile::onInstructionExecuted(Instruction *IS) {
 106   assert(IS && IS->isExecuted() && "Unexpected internal state found!");
 107   for (WriteState &WS : IS->getDefs()) {
 108     if (WS.isEliminated())
 109       return;
 110
 111     MCPhysReg RegID = WS.getRegisterID();
 112
 113     // This allows InstrPostProcess to remove register Defs
 114     // by setting their RegisterID to 0.
 115     if (!RegID)
 116       continue;
 117
 118     assert(WS.getCyclesLeft() != UNKNOWN_CYCLES &&
 119            "The number of cycles should be known at this point!");
 120     assert(WS.getCyclesLeft() <= 0 && "Invalid cycles left for this write!");
 121
 122     MCPhysReg RenameAs = RegisterMappings[RegID].second.RenameAs;
 123     if (RenameAs && RenameAs != RegID)
 124       RegID = RenameAs;
 125
 126     WriteRef &WR = RegisterMappings[RegID].first;
 127     if (WR.getWriteState() == &WS)
 128       WR.notifyExecuted(CurrentCycle);
 129
 130     for (MCPhysReg I : MRI.subregs(RegID)) {
 131       WriteRef &OtherWR = RegisterMappings[I].first;
 132       if (OtherWR.getWriteState() == &WS)
 133         OtherWR.notifyExecuted(CurrentCycle);
 134     }
 135
 136     if (!WS.clearsSuperRegisters())
 137       continue;
 138
 139     for (MCPhysReg I : MRI.superregs(RegID)) {
 140       WriteRef &OtherWR = RegisterMappings[I].first;
 141       if (OtherWR.getWriteState() == &WS)
 142         OtherWR.notifyExecuted(CurrentCycle);
 143     }
 144   }
 145 }
 146
 147 void RegisterFile::addRegisterFile(const MCRegisterFileDesc &RF,
 148                                    ArrayRef<MCRegisterCostEntry> Entries) {
 149   // A default register file is always allocated at index #0. That register file
 150   // is mainly used to count the total number of mappings created by all
 151   // register files at runtime. Users can limit the number of available physical
 152   // registers in register file #0 through the command line flag
 153   // `-register-file-size`.
 154   unsigned RegisterFileIndex = RegisterFiles.size();
 155   RegisterFiles.emplace_back(RF.NumPhysRegs, RF.MaxMovesEliminatedPerCycle,
 156                              RF.AllowZeroMoveEliminationOnly);
 157
 158   // Special case where there is no register class identifier in the set.
 159   // An empty set of register classes means: this register file contains all
 160   // the physical registers specified by the target.
 161   // We optimistically assume that a register can be renamed at the cost of a
 162   // single physical register. The constructor of RegisterFile ensures that
 163   // a RegisterMapping exists for each logical register defined by the Target.
 164   if (Entries.empty())
 165     return;
 166
 167   // Now update the cost of individual registers.
 168   for (const MCRegisterCostEntry &RCE : Entries) {
 169     const MCRegisterClass &RC = MRI.getRegClass(RCE.RegisterClassID);
 170     for (const MCPhysReg Reg : RC) {
 171       RegisterRenamingInfo &Entry = RegisterMappings[Reg].second;
 172       IndexPlusCostPairTy &IPC = Entry.IndexPlusCost;
 173       if (IPC.first && IPC.first != RegisterFileIndex) {
 174         // The only register file that is allowed to overlap is the default
 175         // register file at index #0. The analysis is inaccurate if register
 176         // files overlap.
 177         errs() << "warning: register " << MRI.getName(Reg)
 178                << " defined in multiple register files.";
 179       }
 180       IPC = std::make_pair(RegisterFileIndex, RCE.Cost);
 181       Entry.RenameAs = Reg;
 182       Entry.AllowMoveElimination = RCE.AllowMoveElimination;
 183
 184       // Assume the same cost for each sub-register.
 185       for (MCPhysReg I : MRI.subregs(Reg)) {
 186         RegisterRenamingInfo &OtherEntry = RegisterMappings[I].second;
 187         if (!OtherEntry.IndexPlusCost.first &&
 188             (!OtherEntry.RenameAs ||
 189              MRI.isSuperRegister(I, OtherEntry.RenameAs))) {
 190           OtherEntry.IndexPlusCost = IPC;
 191           OtherEntry.RenameAs = Reg;
 192         }
 193       }
 194     }
 195   }
 196 }
 197
 198 void RegisterFile::allocatePhysRegs(const RegisterRenamingInfo &Entry,
 199                                     MutableArrayRef<unsigned> UsedPhysRegs) {
 200   unsigned RegisterFileIndex = Entry.IndexPlusCost.first;
 201   unsigned Cost = Entry.IndexPlusCost.second;
 202   if (RegisterFileIndex) {
 203     RegisterMappingTracker &RMT = RegisterFiles[RegisterFileIndex];
 204     RMT.NumUsedPhysRegs += Cost;
 205     UsedPhysRegs[RegisterFileIndex] += Cost;
 206   }
 207
 208   // Now update the default register mapping tracker.
 209   RegisterFiles[0].NumUsedPhysRegs += Cost;
 210   UsedPhysRegs[0] += Cost;
 211 }
 212
 213 void RegisterFile::freePhysRegs(const RegisterRenamingInfo &Entry,
 214                                 MutableArrayRef<unsigned> FreedPhysRegs) {
 215   unsigned RegisterFileIndex = Entry.IndexPlusCost.first;
 216   unsigned Cost = Entry.IndexPlusCost.second;
 217   if (RegisterFileIndex) {
 218     RegisterMappingTracker &RMT = RegisterFiles[RegisterFileIndex];
 219     RMT.NumUsedPhysRegs -= Cost;
 220     FreedPhysRegs[RegisterFileIndex] += Cost;
 221   }
 222
 223   // Now update the default register mapping tracker.
 224   RegisterFiles[0].NumUsedPhysRegs -= Cost;
 225   FreedPhysRegs[0] += Cost;
 226 }
 227
 228 void RegisterFile::addRegisterWrite(WriteRef Write,
 229                                     MutableArrayRef<unsigned> UsedPhysRegs) {
 230   WriteState &WS = *Write.getWriteState();
 231   MCPhysReg RegID = WS.getRegisterID();
 232
 233   // This allows InstrPostProcess to remove register Defs
 234   // by setting their RegisterID to 0.
 235   if (!RegID)
 236     return;
 237
 238   LLVM_DEBUG({
 239     dbgs() << "[PRF] addRegisterWrite [ " << Write.getSourceIndex() << ", "
 240            << MRI.getName(RegID) << "]\n";
 241   });
 242
 243   // If RenameAs is equal to RegID, then RegID is subject to register renaming
 244   // and false dependencies on RegID are all eliminated.
 245
 246   // If RenameAs references the invalid register, then we optimistically assume
 247   // that it can be renamed. In the absence of tablegen descriptors for register
 248   // files, RenameAs is always set to the invalid register ID.  In all other
 249   // cases, RenameAs must be either equal to RegID, or it must reference a
 250   // super-register of RegID.
 251
 252   // If RenameAs is a super-register of RegID, then a write to RegID has always
 253   // a false dependency on RenameAs. The only exception is for when the write
 254   // implicitly clears the upper portion of the underlying register.
 255   // If a write clears its super-registers, then it is renamed as `RenameAs`.
 256   bool IsWriteZero = WS.isWriteZero();
 257   bool IsEliminated = WS.isEliminated();
 258   bool ShouldAllocatePhysRegs = !IsWriteZero && !IsEliminated;
 259   const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second;
 260   WS.setPRF(RRI.IndexPlusCost.first);
 261
 262   if (RRI.RenameAs && RRI.RenameAs != RegID) {
 263     RegID = RRI.RenameAs;
 264     WriteRef &OtherWrite = RegisterMappings[RegID].first;
 265
 266     if (!WS.clearsSuperRegisters()) {
 267       // The processor keeps the definition of `RegID` together with register
 268       // `RenameAs`. Since this partial write is not renamed, no physical
 269       // register is allocated.
 270       ShouldAllocatePhysRegs = false;
 271
 272       WriteState *OtherWS = OtherWrite.getWriteState();
 273       if (OtherWS && (OtherWrite.getSourceIndex() != Write.getSourceIndex())) {
 274         // This partial write has a false dependency on RenameAs.
 275         assert(!IsEliminated && "Unexpected partial update!");
 276         OtherWS->addUser(OtherWrite.getSourceIndex(), &WS);
 277       }
 278     }
 279   }
 280
 281   // Update zero registers.
 282   MCPhysReg ZeroRegisterID =
 283       WS.clearsSuperRegisters() ? RegID : WS.getRegisterID();
 284   ZeroRegisters.setBitVal(ZeroRegisterID, IsWriteZero);
 285   for (MCPhysReg I : MRI.subregs(ZeroRegisterID))
 286     ZeroRegisters.setBitVal(I, IsWriteZero);
 287
 288   // If this move has been eliminated, then method tryEliminateMoveOrSwap should
 289   // have already updated all the register mappings.
 290   if (!IsEliminated) {
 291     // Check if this is one of multiple writes performed by this
 292     // instruction to register RegID.
 293     const WriteRef &OtherWrite = RegisterMappings[RegID].first;
 294     const WriteState *OtherWS = OtherWrite.getWriteState();
 295     if (OtherWS && OtherWrite.getSourceIndex() == Write.getSourceIndex()) {
 296       if (OtherWS->getLatency() > WS.getLatency()) {
 297         // Conservatively keep the slowest write on RegID.
 298         if (ShouldAllocatePhysRegs)
 299           allocatePhysRegs(RegisterMappings[RegID].second, UsedPhysRegs);
 300         return;
 301       }
 302     }
 303
 304     // Update the mapping for register RegID including its sub-registers.
 305     RegisterMappings[RegID].first = Write;
 306     RegisterMappings[RegID].second.AliasRegID = 0U;
 307     for (MCPhysReg I : MRI.subregs(RegID)) {
 308       RegisterMappings[I].first = Write;
 309       RegisterMappings[I].second.AliasRegID = 0U;
 310     }
 311
 312     // No physical registers are allocated for instructions that are optimized
 313     // in hardware. For example, zero-latency data-dependency breaking
 314     // instructions don't consume physical registers.
 315     if (ShouldAllocatePhysRegs)
 316       allocatePhysRegs(RegisterMappings[RegID].second, UsedPhysRegs);
 317   }
 318
 319   if (!WS.clearsSuperRegisters())
 320     return;
 321
 322   for (MCPhysReg I : MRI.superregs(RegID)) {
 323     if (!IsEliminated) {
 324       RegisterMappings[I].first = Write;
 325       RegisterMappings[I].second.AliasRegID = 0U;
 326     }
 327
 328     ZeroRegisters.setBitVal(I, IsWriteZero);
 329   }
 330 }
 331
 332 void RegisterFile::removeRegisterWrite(
 333     const WriteState &WS, MutableArrayRef<unsigned> FreedPhysRegs) {
 334   // Early exit if this write was eliminated. A write eliminated at register
 335   // renaming stage generates an alias, and it is not added to the PRF.
 336   if (WS.isEliminated())
 337     return;
 338
 339   MCPhysReg RegID = WS.getRegisterID();
 340
 341   // This allows InstrPostProcess to remove register Defs
 342   // by setting their RegisterID to 0.
 343   if (!RegID)
 344     return;
 345
 346   assert(WS.getCyclesLeft() != UNKNOWN_CYCLES &&
 347          "Invalidating a write of unknown cycles!");
 348   assert(WS.getCyclesLeft() <= 0 && "Invalid cycles left for this write!");
 349
 350   bool ShouldFreePhysRegs = !WS.isWriteZero();
 351   MCPhysReg RenameAs = RegisterMappings[RegID].second.RenameAs;
 352   if (RenameAs && RenameAs != RegID) {
 353     RegID = RenameAs;
 354
 355     if (!WS.clearsSuperRegisters()) {
 356       // Keep the definition of `RegID` together with register `RenameAs`.
 357       ShouldFreePhysRegs = false;
 358     }
 359   }
 360
 361   if (ShouldFreePhysRegs)
 362     freePhysRegs(RegisterMappings[RegID].second, FreedPhysRegs);
 363
 364   WriteRef &WR = RegisterMappings[RegID].first;
 365   if (WR.getWriteState() == &WS)
 366     WR.commit();
 367
 368   for (MCPhysReg I : MRI.subregs(RegID)) {
 369     WriteRef &OtherWR = RegisterMappings[I].first;
 370     if (OtherWR.getWriteState() == &WS)
 371       OtherWR.commit();
 372   }
 373
 374   if (!WS.clearsSuperRegisters())
 375     return;
 376
 377   for (MCPhysReg I : MRI.superregs(RegID)) {
 378     WriteRef &OtherWR = RegisterMappings[I].first;
 379     if (OtherWR.getWriteState() == &WS)
 380       OtherWR.commit();
 381   }
 382 }
 383
 384 bool RegisterFile::canEliminateMove(const WriteState &WS, const ReadState &RS,
 385                                     unsigned RegisterFileIndex) const {
 386   const RegisterMapping &RMFrom = RegisterMappings[RS.getRegisterID()];
 387   const RegisterMapping &RMTo = RegisterMappings[WS.getRegisterID()];
 388   const RegisterMappingTracker &RMT = RegisterFiles[RegisterFileIndex];
 389
 390   // From and To must be owned by the PRF at index `RegisterFileIndex`.
 391   const RegisterRenamingInfo &RRIFrom = RMFrom.second;
 392   if (RRIFrom.IndexPlusCost.first != RegisterFileIndex)
 393     return false;
 394
 395   const RegisterRenamingInfo &RRITo = RMTo.second;
 396   if (RRITo.IndexPlusCost.first != RegisterFileIndex)
 397     return false;
 398
 399   // Early exit if the destination register is from a register class that
 400   // doesn't allow move elimination.
 401   if (!RegisterMappings[RRITo.RenameAs].second.AllowMoveElimination)
 402     return false;
 403
 404   // We only allow move elimination for writes that update a full physical
 405   // register. On X86, move elimination is possible with 32-bit general purpose
 406   // registers because writes to those registers are not partial writes.  If a
 407   // register move is a partial write, then we conservatively assume that move
 408   // elimination fails, since it would either trigger a partial update, or the
 409   // issue of a merge opcode.
 410   //
 411   // Note that this constraint may be lifted in future.  For example, we could
 412   // make this model more flexible, and let users customize the set of registers
 413   // (i.e. register classes) that allow move elimination.
 414   //
 415   // For now, we assume that there is a strong correlation between registers
 416   // that allow move elimination, and how those same registers are renamed in
 417   // hardware.
 418   if (RRITo.RenameAs && RRITo.RenameAs != WS.getRegisterID())
 419     if (!WS.clearsSuperRegisters())
 420       return false;
 421
 422   bool IsZeroMove = ZeroRegisters[RS.getRegisterID()];
 423   return (!RMT.AllowZeroMoveEliminationOnly || IsZeroMove);
 424 }
 425
 426 bool RegisterFile::tryEliminateMoveOrSwap(MutableArrayRef<WriteState> Writes,
 427                                           MutableArrayRef<ReadState> Reads) {
 428   if (Writes.size() != Reads.size())
 429     return false;
 430
 431   // This logic assumes that writes and reads are contributed by a register move
 432   // or a register swap operation. In particular, it assumes a simple register
 433   // move if there is only one write.  It assumes a swap operation if there are
 434   // exactly two writes.
 435   if (Writes.empty() || Writes.size() > 2)
 436     return false;
 437
 438   // All registers must be owned by the same PRF.
 439   const RegisterRenamingInfo &RRInfo =
 440       RegisterMappings[Writes[0].getRegisterID()].second;
 441   unsigned RegisterFileIndex = RRInfo.IndexPlusCost.first;
 442   RegisterMappingTracker &RMT = RegisterFiles[RegisterFileIndex];
 443
 444   // Early exit if the PRF cannot eliminate more moves/xchg in this cycle.
 445   if (RMT.MaxMoveEliminatedPerCycle &&
 446       (RMT.NumMoveEliminated + Writes.size()) > RMT.MaxMoveEliminatedPerCycle)
 447     return false;
 448
 449   for (size_t I = 0, E = Writes.size(); I < E; ++I) {
 450     const ReadState &RS = Reads[I];
 451     const WriteState &WS = Writes[E - (I + 1)];
 452     if (!canEliminateMove(WS, RS, RegisterFileIndex))
 453       return false;
 454   }
 455
 456   for (size_t I = 0, E = Writes.size(); I < E; ++I) {
 457     ReadState &RS = Reads[I];
 458     WriteState &WS = Writes[E - (I + 1)];
 459
 460     const RegisterMapping &RMFrom = RegisterMappings[RS.getRegisterID()];
 461     const RegisterMapping &RMTo = RegisterMappings[WS.getRegisterID()];
 462     const RegisterRenamingInfo &RRIFrom = RMFrom.second;
 463     const RegisterRenamingInfo &RRITo = RMTo.second;
 464
 465     // Construct an alias.
 466     MCPhysReg AliasedReg =
 467         RRIFrom.RenameAs ? RRIFrom.RenameAs : RS.getRegisterID();
 468     MCPhysReg AliasReg = RRITo.RenameAs ? RRITo.RenameAs : WS.getRegisterID();
 469
 470     const RegisterRenamingInfo &RMAlias = RegisterMappings[AliasedReg].second;
 471     if (RMAlias.AliasRegID)
 472       AliasedReg = RMAlias.AliasRegID;
 473
 474     RegisterMappings[AliasReg].second.AliasRegID = AliasedReg;
 475     for (MCPhysReg I : MRI.subregs(AliasReg))
 476       RegisterMappings[I].second.AliasRegID = AliasedReg;
 477
 478     if (ZeroRegisters[RS.getRegisterID()]) {
 479       WS.setWriteZero();
 480       RS.setReadZero();
 481     }
 482
 483     WS.setEliminated();
 484     RMT.NumMoveEliminated++;
 485   }
 486
 487   return true;
 488 }
 489
 490 unsigned WriteRef::getWriteBackCycle() const {
 491   assert(hasKnownWriteBackCycle() && "Instruction not executed!");
 492   assert((!Write || Write->getCyclesLeft() <= 0) &&
 493          "Inconsistent state found!");
 494   return WriteBackCycle;
 495 }
 496
 497 unsigned RegisterFile::getElapsedCyclesFromWriteBack(const WriteRef &WR) const {
 498   assert(WR.hasKnownWriteBackCycle() && "Write hasn't been committed yet!");
 499   return CurrentCycle - WR.getWriteBackCycle();
 500 }
 501
 502 void RegisterFile::collectWrites(
 503     const MCSubtargetInfo &STI, const ReadState &RS,
 504     SmallVectorImpl<WriteRef> &Writes,
 505     SmallVectorImpl<WriteRef> &CommittedWrites) const {
 506   const ReadDescriptor &RD = RS.getDescriptor();
 507   const MCSchedModel &SM = STI.getSchedModel();
 508   const MCSchedClassDesc *SC = SM.getSchedClassDesc(RD.SchedClassID);
 509   MCPhysReg RegID = RS.getRegisterID();
 510   assert(RegID && RegID < RegisterMappings.size());
 511   LLVM_DEBUG(dbgs() << "[PRF] collecting writes for register "
 512                     << MRI.getName(RegID) << '\n');
 513
 514   // Check if this is an alias.
 515   const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second;
 516   if (RRI.AliasRegID)
 517     RegID = RRI.AliasRegID;
 518
 519   const WriteRef &WR = RegisterMappings[RegID].first;
 520   if (WR.getWriteState()) {
 521     Writes.push_back(WR);
 522   } else if (WR.hasKnownWriteBackCycle()) {
 523     unsigned WriteResID = WR.getWriteResourceID();
 524     int ReadAdvance = STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID);
 525     if (ReadAdvance < 0) {
 526       unsigned Elapsed = getElapsedCyclesFromWriteBack(WR);
 527       if (Elapsed < static_cast<unsigned>(-ReadAdvance))
 528         CommittedWrites.push_back(WR);
 529     }
 530   }
 531
 532   // Handle potential partial register updates.
 533   for (MCPhysReg I : MRI.subregs(RegID)) {
 534     const WriteRef &WR = RegisterMappings[I].first;
 535     if (WR.getWriteState()) {
 536       Writes.push_back(WR);
 537     } else if (WR.hasKnownWriteBackCycle()) {
 538       unsigned WriteResID = WR.getWriteResourceID();
 539       int ReadAdvance = STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID);
 540       if (ReadAdvance < 0) {
 541         unsigned Elapsed = getElapsedCyclesFromWriteBack(WR);
 542         if (Elapsed < static_cast<unsigned>(-ReadAdvance))
 543           CommittedWrites.push_back(WR);
 544       }
 545     }
 546   }
 547
 548   // Remove duplicate entries and resize the input vector.
 549   if (Writes.size() > 1) {
 550     sort(Writes, [](const WriteRef &Lhs, const WriteRef &Rhs) {
 551       return Lhs.getWriteState() < Rhs.getWriteState();
 552     });
 553     auto It = std::unique(Writes.begin(), Writes.end());
 554     Writes.resize(std::distance(Writes.begin(), It));
 555   }
 556
 557   LLVM_DEBUG({
 558     for (const WriteRef &WR : Writes) {
 559       const WriteState &WS = *WR.getWriteState();
 560       dbgs() << "[PRF] Found a dependent use of Register "
 561              << MRI.getName(WS.getRegisterID()) << " (defined by instruction #"
 562              << WR.getSourceIndex() << ")\n";
 563     }
 564   });
 565 }
 566
 567 RegisterFile::RAWHazard
 568 RegisterFile::checkRAWHazards(const MCSubtargetInfo &STI,
 569                               const ReadState &RS) const {
 570   RAWHazard Hazard;
 571   SmallVector<WriteRef, 4> Writes;
 572   SmallVector<WriteRef, 4> CommittedWrites;
 573
 574   const MCSchedModel &SM = STI.getSchedModel();
 575   const ReadDescriptor &RD = RS.getDescriptor();
 576   const MCSchedClassDesc *SC = SM.getSchedClassDesc(RD.SchedClassID);
 577
 578   collectWrites(STI, RS, Writes, CommittedWrites);
 579   for (const WriteRef &WR : Writes) {
 580     const WriteState *WS = WR.getWriteState();
 581     unsigned WriteResID = WS->getWriteResourceID();
 582     int ReadAdvance = STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID);
 583
 584     if (WS->getCyclesLeft() == UNKNOWN_CYCLES) {
 585       if (Hazard.isValid())
 586         continue;
 587
 588       Hazard.RegisterID = WR.getRegisterID();
 589       Hazard.CyclesLeft = UNKNOWN_CYCLES;
 590       continue;
 591     }
 592
 593     int CyclesLeft = WS->getCyclesLeft() - ReadAdvance;
 594     if (CyclesLeft > 0) {
 595       if (Hazard.CyclesLeft < CyclesLeft) {
 596         Hazard.RegisterID = WR.getRegisterID();
 597         Hazard.CyclesLeft = CyclesLeft;
 598       }
 599     }
 600   }
 601   Writes.clear();
 602
 603   for (const WriteRef &WR : CommittedWrites) {
 604     unsigned WriteResID = WR.getWriteResourceID();
 605     int NegReadAdvance = -STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID);
 606     int Elapsed = static_cast<int>(getElapsedCyclesFromWriteBack(WR));
 607     int CyclesLeft = NegReadAdvance - Elapsed;
 608     assert(CyclesLeft > 0 && "Write should not be in the CommottedWrites set!");
 609     if (Hazard.CyclesLeft < CyclesLeft) {
 610       Hazard.RegisterID = WR.getRegisterID();
 611       Hazard.CyclesLeft = CyclesLeft;
 612     }
 613   }
 614
 615   return Hazard;
 616 }
 617
 618 void RegisterFile::addRegisterRead(ReadState &RS,
 619                                    const MCSubtargetInfo &STI) const {
 620   MCPhysReg RegID = RS.getRegisterID();
 621   const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second;
 622   RS.setPRF(RRI.IndexPlusCost.first);
 623   if (RS.isIndependentFromDef())
 624     return;
 625
 626   if (ZeroRegisters[RS.getRegisterID()])
 627     RS.setReadZero();
 628
 629   SmallVector<WriteRef, 4> DependentWrites;
 630   SmallVector<WriteRef, 4> CompletedWrites;
 631   collectWrites(STI, RS, DependentWrites, CompletedWrites);
 632   RS.setDependentWrites(DependentWrites.size() + CompletedWrites.size());
 633
 634   // We know that this read depends on all the writes in DependentWrites.
 635   // For each write, check if we have ReadAdvance information, and use it
 636   // to figure out in how many cycles this read will be available.
 637   const ReadDescriptor &RD = RS.getDescriptor();
 638   const MCSchedModel &SM = STI.getSchedModel();
 639   const MCSchedClassDesc *SC = SM.getSchedClassDesc(RD.SchedClassID);
 640   for (WriteRef &WR : DependentWrites) {
 641     unsigned WriteResID = WR.getWriteResourceID();
 642     WriteState &WS = *WR.getWriteState();
 643     int ReadAdvance = STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID);
 644     WS.addUser(WR.getSourceIndex(), &RS, ReadAdvance);
 645   }
 646
 647   for (WriteRef &WR : CompletedWrites) {
 648     unsigned WriteResID = WR.getWriteResourceID();
 649     assert(WR.hasKnownWriteBackCycle() && "Invalid write!");
 650     assert(STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID) < 0);
 651     unsigned ReadAdvance = static_cast<unsigned>(
 652         -STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID));
 653     unsigned Elapsed = getElapsedCyclesFromWriteBack(WR);
 654     assert(Elapsed < ReadAdvance && "Should not have been added to the set!");
 655     RS.writeStartEvent(WR.getSourceIndex(), WR.getRegisterID(),
 656                        ReadAdvance - Elapsed);
 657   }
 658 }
 659
 660 unsigned RegisterFile::isAvailable(ArrayRef<MCPhysReg> Regs) const {
 661   SmallVector<unsigned, 4> NumPhysRegs(getNumRegisterFiles());
 662
 663   // Find how many new mappings must be created for each register file.
 664   for (const MCPhysReg RegID : Regs) {
 665     const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second;
 666     const IndexPlusCostPairTy &Entry = RRI.IndexPlusCost;
 667     if (Entry.first)
 668       NumPhysRegs[Entry.first] += Entry.second;
 669     NumPhysRegs[0] += Entry.second;
 670   }
 671
 672   unsigned Response = 0;
 673   for (unsigned I = 0, E = getNumRegisterFiles(); I < E; ++I) {
 674     unsigned NumRegs = NumPhysRegs[I];
 675     if (!NumRegs)
 676       continue;
 677
 678     const RegisterMappingTracker &RMT = RegisterFiles[I];
 679     if (!RMT.NumPhysRegs) {
 680       // The register file has an unbounded number of microarchitectural
 681       // registers.
 682       continue;
 683     }
 684
 685     if (RMT.NumPhysRegs < NumRegs) {
 686       // The current register file is too small. This may occur if the number of
 687       // microarchitectural registers in register file #0 was changed by the
 688       // users via flag -reg-file-size. Alternatively, the scheduling model
 689       // specified a too small number of registers for this register file.
 690       LLVM_DEBUG(
 691           dbgs() << "[PRF] Not enough registers in the register file.\n");
 692
 693       // FIXME: Normalize the instruction register count to match the
 694       // NumPhysRegs value.  This is a highly unusual case, and is not expected
 695       // to occur.  This normalization is hiding an inconsistency in either the
 696       // scheduling model or in the value that the user might have specified
 697       // for NumPhysRegs.
 698       NumRegs = RMT.NumPhysRegs;
 699     }
 700
 701     if (RMT.NumPhysRegs < (RMT.NumUsedPhysRegs + NumRegs))
 702       Response |= (1U << I);
 703   }
 704
 705   return Response;
 706 }
 707
 708 #ifndef NDEBUG
 709 void WriteRef::dump() const {
 710   dbgs() << "IID=" << getSourceIndex() << ' ';
 711   if (isValid())
 712     getWriteState()->dump();
 713   else
 714     dbgs() << "(null)";
 715 }
 716
 717 void RegisterFile::dump() const {
 718   for (unsigned I = 0, E = MRI.getNumRegs(); I < E; ++I) {
 719     const RegisterMapping &RM = RegisterMappings[I];
 720     const RegisterRenamingInfo &RRI = RM.second;
 721     if (ZeroRegisters[I]) {
 722       dbgs() << MRI.getName(I) << ", " << I
 723              << ", PRF=" << RRI.IndexPlusCost.first
 724              << ", Cost=" << RRI.IndexPlusCost.second
 725              << ", RenameAs=" << RRI.RenameAs << ", IsZero=" << ZeroRegisters[I]
 726              << ",";
 727       RM.first.dump();
 728       dbgs() << '\n';
 729     }
 730   }
 731
 732   for (unsigned I = 0, E = getNumRegisterFiles(); I < E; ++I) {
 733     dbgs() << "Register File #" << I;
 734     const RegisterMappingTracker &RMT = RegisterFiles[I];
 735     dbgs() << "\n  TotalMappings:        " << RMT.NumPhysRegs
 736            << "\n  NumUsedMappings:      " << RMT.NumUsedPhysRegs << '\n';
 737   }
 738 }
 739 #endif
 740
 741 } // namespace mca
 742 } // namespace llvm