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