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 (MCSubRegIterator I(RegID, &MRI); I.isValid(); ++I) {
 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 (MCSuperRegIterator I(RegID, &MRI); I.isValid(); ++I) {
 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 (MCSubRegIterator I(Reg, &MRI); I.isValid(); ++I) {
 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 (MCSubRegIterator I(ZeroRegisterID, &MRI); I.isValid(); ++I)
 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     // Update the mapping for register RegID including its sub-registers.
 292     RegisterMappings[RegID].first = Write;
 293     RegisterMappings[RegID].second.AliasRegID = 0U;
 294     for (MCSubRegIterator I(RegID, &MRI); I.isValid(); ++I) {
 295       RegisterMappings[*I].first = Write;
 296       RegisterMappings[*I].second.AliasRegID = 0U;
 297     }
 298
 299     // No physical registers are allocated for instructions that are optimized
 300     // in hardware. For example, zero-latency data-dependency breaking
 301     // instructions don't consume physical registers.
 302     if (ShouldAllocatePhysRegs)
 303       allocatePhysRegs(RegisterMappings[RegID].second, UsedPhysRegs);
 304   }
 305
 306   if (!WS.clearsSuperRegisters())
 307     return;
 308
 309   for (MCSuperRegIterator I(RegID, &MRI); I.isValid(); ++I) {
 310     if (!IsEliminated) {
 311       RegisterMappings[*I].first = Write;
 312       RegisterMappings[*I].second.AliasRegID = 0U;
 313     }
 314
 315     ZeroRegisters.setBitVal(*I, IsWriteZero);
 316   }
 317 }
 318
 319 void RegisterFile::removeRegisterWrite(
 320     const WriteState &WS, MutableArrayRef<unsigned> FreedPhysRegs) {
 321   // Early exit if this write was eliminated. A write eliminated at register
 322   // renaming stage generates an alias, and it is not added to the PRF.
 323   if (WS.isEliminated())
 324     return;
 325
 326   MCPhysReg RegID = WS.getRegisterID();
 327
 328   // This allows InstrPostProcess to remove register Defs
 329   // by setting their RegisterID to 0.
 330   if (!RegID)
 331     return;
 332
 333   assert(WS.getCyclesLeft() != UNKNOWN_CYCLES &&
 334          "Invalidating a write of unknown cycles!");
 335   assert(WS.getCyclesLeft() <= 0 && "Invalid cycles left for this write!");
 336
 337   bool ShouldFreePhysRegs = !WS.isWriteZero();
 338   MCPhysReg RenameAs = RegisterMappings[RegID].second.RenameAs;
 339   if (RenameAs && RenameAs != RegID) {
 340     RegID = RenameAs;
 341
 342     if (!WS.clearsSuperRegisters()) {
 343       // Keep the definition of `RegID` together with register `RenameAs`.
 344       ShouldFreePhysRegs = false;
 345     }
 346   }
 347
 348   if (ShouldFreePhysRegs)
 349     freePhysRegs(RegisterMappings[RegID].second, FreedPhysRegs);
 350
 351   WriteRef &WR = RegisterMappings[RegID].first;
 352   if (WR.getWriteState() == &WS)
 353     WR.commit();
 354
 355   for (MCSubRegIterator I(RegID, &MRI); I.isValid(); ++I) {
 356     WriteRef &OtherWR = RegisterMappings[*I].first;
 357     if (OtherWR.getWriteState() == &WS)
 358       OtherWR.commit();
 359   }
 360
 361   if (!WS.clearsSuperRegisters())
 362     return;
 363
 364   for (MCSuperRegIterator I(RegID, &MRI); I.isValid(); ++I) {
 365     WriteRef &OtherWR = RegisterMappings[*I].first;
 366     if (OtherWR.getWriteState() == &WS)
 367       OtherWR.commit();
 368   }
 369 }
 370
 371 bool RegisterFile::canEliminateMove(const WriteState &WS, const ReadState &RS,
 372                                     unsigned RegisterFileIndex) const {
 373   const RegisterMapping &RMFrom = RegisterMappings[RS.getRegisterID()];
 374   const RegisterMapping &RMTo = RegisterMappings[WS.getRegisterID()];
 375   const RegisterMappingTracker &RMT = RegisterFiles[RegisterFileIndex];
 376
 377   // From and To must be owned by the PRF at index `RegisterFileIndex`.
 378   const RegisterRenamingInfo &RRIFrom = RMFrom.second;
 379   if (RRIFrom.IndexPlusCost.first != RegisterFileIndex)
 380     return false;
 381
 382   const RegisterRenamingInfo &RRITo = RMTo.second;
 383   if (RRITo.IndexPlusCost.first != RegisterFileIndex)
 384     return false;
 385
 386   // Early exit if the destination register is from a register class that
 387   // doesn't allow move elimination.
 388   if (!RegisterMappings[RRITo.RenameAs].second.AllowMoveElimination)
 389     return false;
 390
 391   // We only allow move elimination for writes that update a full physical
 392   // register. On X86, move elimination is possible with 32-bit general purpose
 393   // registers because writes to those registers are not partial writes.  If a
 394   // register move is a partial write, then we conservatively assume that move
 395   // elimination fails, since it would either trigger a partial update, or the
 396   // issue of a merge opcode.
 397   //
 398   // Note that this constraint may be lifted in future.  For example, we could
 399   // make this model more flexible, and let users customize the set of registers
 400   // (i.e. register classes) that allow move elimination.
 401   //
 402   // For now, we assume that there is a strong correlation between registers
 403   // that allow move elimination, and how those same registers are renamed in
 404   // hardware.
 405   if (RRITo.RenameAs && RRITo.RenameAs != WS.getRegisterID())
 406     if (!WS.clearsSuperRegisters())
 407       return false;
 408
 409   bool IsZeroMove = ZeroRegisters[RS.getRegisterID()];
 410   return (!RMT.AllowZeroMoveEliminationOnly || IsZeroMove);
 411 }
 412
 413 bool RegisterFile::tryEliminateMoveOrSwap(MutableArrayRef<WriteState> Writes,
 414                                           MutableArrayRef<ReadState> Reads) {
 415   if (Writes.size() != Reads.size())
 416     return false;
 417
 418   // This logic assumes that writes and reads are contributed by a register move
 419   // or a register swap operation. In particular, it assumes a simple register
 420   // move if there is only one write.  It assumes a swap operation if there are
 421   // exactly two writes.
 422   if (Writes.empty() || Writes.size() > 2)
 423     return false;
 424
 425   // All registers must be owned by the same PRF.
 426   const RegisterRenamingInfo &RRInfo =
 427       RegisterMappings[Writes[0].getRegisterID()].second;
 428   unsigned RegisterFileIndex = RRInfo.IndexPlusCost.first;
 429   RegisterMappingTracker &RMT = RegisterFiles[RegisterFileIndex];
 430
 431   // Early exit if the PRF cannot eliminate more moves/xchg in this cycle.
 432   if (RMT.MaxMoveEliminatedPerCycle &&
 433       (RMT.NumMoveEliminated + Writes.size()) > RMT.MaxMoveEliminatedPerCycle)
 434     return false;
 435
 436   for (size_t I = 0, E = Writes.size(); I < E; ++I) {
 437     const ReadState &RS = Reads[I];
 438     const WriteState &WS = Writes[E - (I + 1)];
 439     if (!canEliminateMove(WS, RS, RegisterFileIndex))
 440       return false;
 441   }
 442
 443   for (size_t I = 0, E = Writes.size(); I < E; ++I) {
 444     ReadState &RS = Reads[I];
 445     WriteState &WS = Writes[E - (I + 1)];
 446
 447     const RegisterMapping &RMFrom = RegisterMappings[RS.getRegisterID()];
 448     const RegisterMapping &RMTo = RegisterMappings[WS.getRegisterID()];
 449     const RegisterRenamingInfo &RRIFrom = RMFrom.second;
 450     const RegisterRenamingInfo &RRITo = RMTo.second;
 451
 452     // Construct an alias.
 453     MCPhysReg AliasedReg =
 454         RRIFrom.RenameAs ? RRIFrom.RenameAs : RS.getRegisterID();
 455     MCPhysReg AliasReg = RRITo.RenameAs ? RRITo.RenameAs : WS.getRegisterID();
 456
 457     const RegisterRenamingInfo &RMAlias = RegisterMappings[AliasedReg].second;
 458     if (RMAlias.AliasRegID)
 459       AliasedReg = RMAlias.AliasRegID;
 460
 461     RegisterMappings[AliasReg].second.AliasRegID = AliasedReg;
 462     for (MCSubRegIterator I(AliasReg, &MRI); I.isValid(); ++I)
 463       RegisterMappings[*I].second.AliasRegID = AliasedReg;
 464
 465     if (ZeroRegisters[RS.getRegisterID()]) {
 466       WS.setWriteZero();
 467       RS.setReadZero();
 468     }
 469
 470     WS.setEliminated();
 471     RMT.NumMoveEliminated++;
 472   }
 473
 474   return true;
 475 }
 476
 477 unsigned WriteRef::getWriteBackCycle() const {
 478   assert(hasKnownWriteBackCycle() && "Instruction not executed!");
 479   assert((!Write || Write->getCyclesLeft() <= 0) &&
 480          "Inconsistent state found!");
 481   return WriteBackCycle;
 482 }
 483
 484 unsigned RegisterFile::getElapsedCyclesFromWriteBack(const WriteRef &WR) const {
 485   assert(WR.hasKnownWriteBackCycle() && "Write hasn't been committed yet!");
 486   return CurrentCycle - WR.getWriteBackCycle();
 487 }
 488
 489 void RegisterFile::collectWrites(
 490     const MCSubtargetInfo &STI, const ReadState &RS,
 491     SmallVectorImpl<WriteRef> &Writes,
 492     SmallVectorImpl<WriteRef> &CommittedWrites) const {
 493   const ReadDescriptor &RD = RS.getDescriptor();
 494   const MCSchedModel &SM = STI.getSchedModel();
 495   const MCSchedClassDesc *SC = SM.getSchedClassDesc(RD.SchedClassID);
 496   MCPhysReg RegID = RS.getRegisterID();
 497   assert(RegID && RegID < RegisterMappings.size());
 498   LLVM_DEBUG(dbgs() << "[PRF] collecting writes for register "
 499                     << MRI.getName(RegID) << '\n');
 500
 501   // Check if this is an alias.
 502   const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second;
 503   if (RRI.AliasRegID)
 504     RegID = RRI.AliasRegID;
 505
 506   const WriteRef &WR = RegisterMappings[RegID].first;
 507   if (WR.getWriteState()) {
 508     Writes.push_back(WR);
 509   } else if (WR.hasKnownWriteBackCycle()) {
 510     unsigned WriteResID = WR.getWriteResourceID();
 511     int ReadAdvance = STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID);
 512     if (ReadAdvance < 0) {
 513       unsigned Elapsed = getElapsedCyclesFromWriteBack(WR);
 514       if (Elapsed < static_cast<unsigned>(-ReadAdvance))
 515         CommittedWrites.push_back(WR);
 516     }
 517   }
 518
 519   // Handle potential partial register updates.
 520   for (MCSubRegIterator I(RegID, &MRI); I.isValid(); ++I) {
 521     const WriteRef &WR = RegisterMappings[*I].first;
 522     if (WR.getWriteState()) {
 523       Writes.push_back(WR);
 524     } else if (WR.hasKnownWriteBackCycle()) {
 525       unsigned WriteResID = WR.getWriteResourceID();
 526       int ReadAdvance = STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID);
 527       if (ReadAdvance < 0) {
 528         unsigned Elapsed = getElapsedCyclesFromWriteBack(WR);
 529         if (Elapsed < static_cast<unsigned>(-ReadAdvance))
 530           CommittedWrites.push_back(WR);
 531       }
 532     }
 533   }
 534
 535   // Remove duplicate entries and resize the input vector.
 536   if (Writes.size() > 1) {
 537     sort(Writes, [](const WriteRef &Lhs, const WriteRef &Rhs) {
 538       return Lhs.getWriteState() < Rhs.getWriteState();
 539     });
 540     auto It = std::unique(Writes.begin(), Writes.end());
 541     Writes.resize(std::distance(Writes.begin(), It));
 542   }
 543
 544   LLVM_DEBUG({
 545     for (const WriteRef &WR : Writes) {
 546       const WriteState &WS = *WR.getWriteState();
 547       dbgs() << "[PRF] Found a dependent use of Register "
 548              << MRI.getName(WS.getRegisterID()) << " (defined by instruction #"
 549              << WR.getSourceIndex() << ")\n";
 550     }
 551   });
 552 }
 553
 554 RegisterFile::RAWHazard
 555 RegisterFile::checkRAWHazards(const MCSubtargetInfo &STI,
 556                               const ReadState &RS) const {
 557   RAWHazard Hazard;
 558   SmallVector<WriteRef, 4> Writes;
 559   SmallVector<WriteRef, 4> CommittedWrites;
 560
 561   const MCSchedModel &SM = STI.getSchedModel();
 562   const ReadDescriptor &RD = RS.getDescriptor();
 563   const MCSchedClassDesc *SC = SM.getSchedClassDesc(RD.SchedClassID);
 564
 565   collectWrites(STI, RS, Writes, CommittedWrites);
 566   for (const WriteRef &WR : Writes) {
 567     const WriteState *WS = WR.getWriteState();
 568     unsigned WriteResID = WS->getWriteResourceID();
 569     int ReadAdvance = STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID);
 570
 571     if (WS->getCyclesLeft() == UNKNOWN_CYCLES) {
 572       if (Hazard.isValid())
 573         continue;
 574
 575       Hazard.RegisterID = WR.getRegisterID();
 576       Hazard.CyclesLeft = UNKNOWN_CYCLES;
 577       continue;
 578     }
 579
 580     int CyclesLeft = WS->getCyclesLeft() - ReadAdvance;
 581     if (CyclesLeft > 0) {
 582       if (Hazard.CyclesLeft < CyclesLeft) {
 583         Hazard.RegisterID = WR.getRegisterID();
 584         Hazard.CyclesLeft = CyclesLeft;
 585       }
 586     }
 587   }
 588   Writes.clear();
 589
 590   for (const WriteRef &WR : CommittedWrites) {
 591     unsigned WriteResID = WR.getWriteResourceID();
 592     int NegReadAdvance = -STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID);
 593     int Elapsed = static_cast<int>(getElapsedCyclesFromWriteBack(WR));
 594     int CyclesLeft = NegReadAdvance - Elapsed;
 595     assert(CyclesLeft > 0 && "Write should not be in the CommottedWrites set!");
 596     if (Hazard.CyclesLeft < CyclesLeft) {
 597       Hazard.RegisterID = WR.getRegisterID();
 598       Hazard.CyclesLeft = CyclesLeft;
 599     }
 600   }
 601
 602   return Hazard;
 603 }
 604
 605 void RegisterFile::addRegisterRead(ReadState &RS,
 606                                    const MCSubtargetInfo &STI) const {
 607   MCPhysReg RegID = RS.getRegisterID();
 608   const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second;
 609   RS.setPRF(RRI.IndexPlusCost.first);
 610   if (RS.isIndependentFromDef())
 611     return;
 612
 613   if (ZeroRegisters[RS.getRegisterID()])
 614     RS.setReadZero();
 615
 616   SmallVector<WriteRef, 4> DependentWrites;
 617   SmallVector<WriteRef, 4> CompletedWrites;
 618   collectWrites(STI, RS, DependentWrites, CompletedWrites);
 619   RS.setDependentWrites(DependentWrites.size() + CompletedWrites.size());
 620
 621   // We know that this read depends on all the writes in DependentWrites.
 622   // For each write, check if we have ReadAdvance information, and use it
 623   // to figure out in how many cycles this read will be available.
 624   const ReadDescriptor &RD = RS.getDescriptor();
 625   const MCSchedModel &SM = STI.getSchedModel();
 626   const MCSchedClassDesc *SC = SM.getSchedClassDesc(RD.SchedClassID);
 627   for (WriteRef &WR : DependentWrites) {
 628     unsigned WriteResID = WR.getWriteResourceID();
 629     WriteState &WS = *WR.getWriteState();
 630     int ReadAdvance = STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID);
 631     WS.addUser(WR.getSourceIndex(), &RS, ReadAdvance);
 632   }
 633
 634   for (WriteRef &WR : CompletedWrites) {
 635     unsigned WriteResID = WR.getWriteResourceID();
 636     assert(WR.hasKnownWriteBackCycle() && "Invalid write!");
 637     assert(STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID) < 0);
 638     unsigned ReadAdvance = static_cast<unsigned>(
 639         -STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID));
 640     unsigned Elapsed = getElapsedCyclesFromWriteBack(WR);
 641     assert(Elapsed < ReadAdvance && "Should not have been added to the set!");
 642     RS.writeStartEvent(WR.getSourceIndex(), WR.getRegisterID(),
 643                        ReadAdvance - Elapsed);
 644   }
 645 }
 646
 647 unsigned RegisterFile::isAvailable(ArrayRef<MCPhysReg> Regs) const {
 648   SmallVector<unsigned, 4> NumPhysRegs(getNumRegisterFiles());
 649
 650   // Find how many new mappings must be created for each register file.
 651   for (const MCPhysReg RegID : Regs) {
 652     const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second;
 653     const IndexPlusCostPairTy &Entry = RRI.IndexPlusCost;
 654     if (Entry.first)
 655       NumPhysRegs[Entry.first] += Entry.second;
 656     NumPhysRegs[0] += Entry.second;
 657   }
 658
 659   unsigned Response = 0;
 660   for (unsigned I = 0, E = getNumRegisterFiles(); I < E; ++I) {
 661     unsigned NumRegs = NumPhysRegs[I];
 662     if (!NumRegs)
 663       continue;
 664
 665     const RegisterMappingTracker &RMT = RegisterFiles[I];
 666     if (!RMT.NumPhysRegs) {
 667       // The register file has an unbounded number of microarchitectural
 668       // registers.
 669       continue;
 670     }
 671
 672     if (RMT.NumPhysRegs < NumRegs) {
 673       // The current register file is too small. This may occur if the number of
 674       // microarchitectural registers in register file #0 was changed by the
 675       // users via flag -reg-file-size. Alternatively, the scheduling model
 676       // specified a too small number of registers for this register file.
 677       LLVM_DEBUG(
 678           dbgs() << "[PRF] Not enough registers in the register file.\n");
 679
 680       // FIXME: Normalize the instruction register count to match the
 681       // NumPhysRegs value.  This is a highly unusual case, and is not expected
 682       // to occur.  This normalization is hiding an inconsistency in either the
 683       // scheduling model or in the value that the user might have specified
 684       // for NumPhysRegs.
 685       NumRegs = RMT.NumPhysRegs;
 686     }
 687
 688     if (RMT.NumPhysRegs < (RMT.NumUsedPhysRegs + NumRegs))
 689       Response |= (1U << I);
 690   }
 691
 692   return Response;
 693 }
 694
 695 #ifndef NDEBUG
 696 void WriteRef::dump() const {
 697   dbgs() << "IID=" << getSourceIndex() << ' ';
 698   if (isValid())
 699     getWriteState()->dump();
 700   else
 701     dbgs() << "(null)";
 702 }
 703
 704 void RegisterFile::dump() const {
 705   for (unsigned I = 0, E = MRI.getNumRegs(); I < E; ++I) {
 706     const RegisterMapping &RM = RegisterMappings[I];
 707     const RegisterRenamingInfo &RRI = RM.second;
 708     if (ZeroRegisters[I]) {
 709       dbgs() << MRI.getName(I) << ", " << I
 710              << ", PRF=" << RRI.IndexPlusCost.first
 711              << ", Cost=" << RRI.IndexPlusCost.second
 712              << ", RenameAs=" << RRI.RenameAs << ", IsZero=" << ZeroRegisters[I]
 713              << ",";
 714       RM.first.dump();
 715       dbgs() << '\n';
 716     }
 717   }
 718
 719   for (unsigned I = 0, E = getNumRegisterFiles(); I < E; ++I) {
 720     dbgs() << "Register File #" << I;
 721     const RegisterMappingTracker &RMT = RegisterFiles[I];
 722     dbgs() << "\n  TotalMappings:        " << RMT.NumPhysRegs
 723            << "\n  NumUsedMappings:      " << RMT.NumUsedPhysRegs << '\n';
 724   }
 725 }
 726 #endif
 727
 728 } // namespace mca
 729 } // namespace llvm