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 RegisterFile::RegisterFile(const MCSchedModel &SM, const MCRegisterInfo &mri,
  26                            unsigned NumRegs)
  27     : MRI(mri),
  28       RegisterMappings(mri.getNumRegs(), {WriteRef(), RegisterRenamingInfo()}),
  29       ZeroRegisters(mri.getNumRegs(), false) {
  30   initialize(SM, NumRegs);
  31 }
  32
  33 void RegisterFile::initialize(const MCSchedModel &SM, unsigned NumRegs) {
  34   // Create a default register file that "sees" all the machine registers
  35   // declared by the target. The number of physical registers in the default
  36   // register file is set equal to `NumRegs`. A value of zero for `NumRegs`
  37   // means: this register file has an unbounded number of physical registers.
  38   RegisterFiles.emplace_back(NumRegs);
  39   if (!SM.hasExtraProcessorInfo())
  40     return;
  41
  42   // For each user defined register file, allocate a RegisterMappingTracker
  43   // object. The size of every register file, as well as the mapping between
  44   // register files and register classes is specified via tablegen.
  45   const MCExtraProcessorInfo &Info = SM.getExtraProcessorInfo();
  46
  47   // Skip invalid register file at index 0.
  48   for (unsigned I = 1, E = Info.NumRegisterFiles; I < E; ++I) {
  49     const MCRegisterFileDesc &RF = Info.RegisterFiles[I];
  50     assert(RF.NumPhysRegs && "Invalid PRF with zero physical registers!");
  51
  52     // The cost of a register definition is equivalent to the number of
  53     // physical registers that are allocated at register renaming stage.
  54     unsigned Length = RF.NumRegisterCostEntries;
  55     const MCRegisterCostEntry *FirstElt =
  56         &Info.RegisterCostTable[RF.RegisterCostEntryIdx];
  57     addRegisterFile(RF, ArrayRef<MCRegisterCostEntry>(FirstElt, Length));
  58   }
  59 }
  60
  61 void RegisterFile::cycleStart() {
  62   for (RegisterMappingTracker &RMT : RegisterFiles)
  63     RMT.NumMoveEliminated = 0;
  64 }
  65
  66 void RegisterFile::addRegisterFile(const MCRegisterFileDesc &RF,
  67                                    ArrayRef<MCRegisterCostEntry> Entries) {
  68   // A default register file is always allocated at index #0. That register file
  69   // is mainly used to count the total number of mappings created by all
  70   // register files at runtime. Users can limit the number of available physical
  71   // registers in register file #0 through the command line flag
  72   // `-register-file-size`.
  73   unsigned RegisterFileIndex = RegisterFiles.size();
  74   RegisterFiles.emplace_back(RF.NumPhysRegs, RF.MaxMovesEliminatedPerCycle,
  75                              RF.AllowZeroMoveEliminationOnly);
  76
  77   // Special case where there is no register class identifier in the set.
  78   // An empty set of register classes means: this register file contains all
  79   // the physical registers specified by the target.
  80   // We optimistically assume that a register can be renamed at the cost of a
  81   // single physical register. The constructor of RegisterFile ensures that
  82   // a RegisterMapping exists for each logical register defined by the Target.
  83   if (Entries.empty())
  84     return;
  85
  86   // Now update the cost of individual registers.
  87   for (const MCRegisterCostEntry &RCE : Entries) {
  88     const MCRegisterClass &RC = MRI.getRegClass(RCE.RegisterClassID);
  89     for (const MCPhysReg Reg : RC) {
  90       RegisterRenamingInfo &Entry = RegisterMappings[Reg].second;
  91       IndexPlusCostPairTy &IPC = Entry.IndexPlusCost;
  92       if (IPC.first && IPC.first != RegisterFileIndex) {
  93         // The only register file that is allowed to overlap is the default
  94         // register file at index #0. The analysis is inaccurate if register
  95         // files overlap.
  96         errs() << "warning: register " << MRI.getName(Reg)
  97                << " defined in multiple register files.";
  98       }
  99       IPC = std::make_pair(RegisterFileIndex, RCE.Cost);
 100       Entry.RenameAs = Reg;
 101       Entry.AllowMoveElimination = RCE.AllowMoveElimination;
 102
 103       // Assume the same cost for each sub-register.
 104       for (MCSubRegIterator I(Reg, &MRI); I.isValid(); ++I) {
 105         RegisterRenamingInfo &OtherEntry = RegisterMappings[*I].second;
 106         if (!OtherEntry.IndexPlusCost.first &&
 107             (!OtherEntry.RenameAs ||
 108              MRI.isSuperRegister(*I, OtherEntry.RenameAs))) {
 109           OtherEntry.IndexPlusCost = IPC;
 110           OtherEntry.RenameAs = Reg;
 111         }
 112       }
 113     }
 114   }
 115 }
 116
 117 void RegisterFile::allocatePhysRegs(const RegisterRenamingInfo &Entry,
 118                                     MutableArrayRef<unsigned> UsedPhysRegs) {
 119   unsigned RegisterFileIndex = Entry.IndexPlusCost.first;
 120   unsigned Cost = Entry.IndexPlusCost.second;
 121   if (RegisterFileIndex) {
 122     RegisterMappingTracker &RMT = RegisterFiles[RegisterFileIndex];
 123     RMT.NumUsedPhysRegs += Cost;
 124     UsedPhysRegs[RegisterFileIndex] += Cost;
 125   }
 126
 127   // Now update the default register mapping tracker.
 128   RegisterFiles[0].NumUsedPhysRegs += Cost;
 129   UsedPhysRegs[0] += Cost;
 130 }
 131
 132 void RegisterFile::freePhysRegs(const RegisterRenamingInfo &Entry,
 133                                 MutableArrayRef<unsigned> FreedPhysRegs) {
 134   unsigned RegisterFileIndex = Entry.IndexPlusCost.first;
 135   unsigned Cost = Entry.IndexPlusCost.second;
 136   if (RegisterFileIndex) {
 137     RegisterMappingTracker &RMT = RegisterFiles[RegisterFileIndex];
 138     RMT.NumUsedPhysRegs -= Cost;
 139     FreedPhysRegs[RegisterFileIndex] += Cost;
 140   }
 141
 142   // Now update the default register mapping tracker.
 143   RegisterFiles[0].NumUsedPhysRegs -= Cost;
 144   FreedPhysRegs[0] += Cost;
 145 }
 146
 147 void RegisterFile::addRegisterWrite(WriteRef Write,
 148                                     MutableArrayRef<unsigned> UsedPhysRegs) {
 149   WriteState &WS = *Write.getWriteState();
 150   MCPhysReg RegID = WS.getRegisterID();
 151   assert(RegID && "Adding an invalid register definition?");
 152
 153   LLVM_DEBUG({
 154     dbgs() << "RegisterFile: addRegisterWrite [ " << Write.getSourceIndex()
 155            << ", " << MRI.getName(RegID) << "]\n";
 156   });
 157
 158   // If RenameAs is equal to RegID, then RegID is subject to register renaming
 159   // and false dependencies on RegID are all eliminated.
 160
 161   // If RenameAs references the invalid register, then we optimistically assume
 162   // that it can be renamed. In the absence of tablegen descriptors for register
 163   // files, RenameAs is always set to the invalid register ID.  In all other
 164   // cases, RenameAs must be either equal to RegID, or it must reference a
 165   // super-register of RegID.
 166
 167   // If RenameAs is a super-register of RegID, then a write to RegID has always
 168   // a false dependency on RenameAs. The only exception is for when the write
 169   // implicitly clears the upper portion of the underlying register.
 170   // If a write clears its super-registers, then it is renamed as `RenameAs`.
 171   bool IsWriteZero = WS.isWriteZero();
 172   bool IsEliminated = WS.isEliminated();
 173   bool ShouldAllocatePhysRegs = !IsWriteZero && !IsEliminated;
 174   const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second;
 175   WS.setPRF(RRI.IndexPlusCost.first);
 176
 177   if (RRI.RenameAs && RRI.RenameAs != RegID) {
 178     RegID = RRI.RenameAs;
 179     WriteRef &OtherWrite = RegisterMappings[RegID].first;
 180
 181     if (!WS.clearsSuperRegisters()) {
 182       // The processor keeps the definition of `RegID` together with register
 183       // `RenameAs`. Since this partial write is not renamed, no physical
 184       // register is allocated.
 185       ShouldAllocatePhysRegs = false;
 186
 187       WriteState *OtherWS = OtherWrite.getWriteState();
 188       if (OtherWS && (OtherWrite.getSourceIndex() != Write.getSourceIndex())) {
 189         // This partial write has a false dependency on RenameAs.
 190         assert(!IsEliminated && "Unexpected partial update!");
 191         OtherWS->addUser(OtherWrite.getSourceIndex(), &WS);
 192       }
 193     }
 194   }
 195
 196   // Update zero registers.
 197   MCPhysReg ZeroRegisterID =
 198       WS.clearsSuperRegisters() ? RegID : WS.getRegisterID();
 199   if (IsWriteZero) {
 200     ZeroRegisters.setBit(ZeroRegisterID);
 201     for (MCSubRegIterator I(ZeroRegisterID, &MRI); I.isValid(); ++I)
 202       ZeroRegisters.setBit(*I);
 203   } else {
 204     ZeroRegisters.clearBit(ZeroRegisterID);
 205     for (MCSubRegIterator I(ZeroRegisterID, &MRI); I.isValid(); ++I)
 206       ZeroRegisters.clearBit(*I);
 207   }
 208
 209   // If this is move has been eliminated, then the call to tryEliminateMove
 210   // should have already updated all the register mappings.
 211   if (!IsEliminated) {
 212     // Update the mapping for register RegID including its sub-registers.
 213     RegisterMappings[RegID].first = Write;
 214     RegisterMappings[RegID].second.AliasRegID = 0U;
 215     for (MCSubRegIterator I(RegID, &MRI); I.isValid(); ++I) {
 216       RegisterMappings[*I].first = Write;
 217       RegisterMappings[*I].second.AliasRegID = 0U;
 218     }
 219
 220     // No physical registers are allocated for instructions that are optimized
 221     // in hardware. For example, zero-latency data-dependency breaking
 222     // instructions don't consume physical registers.
 223     if (ShouldAllocatePhysRegs)
 224       allocatePhysRegs(RegisterMappings[RegID].second, UsedPhysRegs);
 225   }
 226
 227   if (!WS.clearsSuperRegisters())
 228     return;
 229
 230   for (MCSuperRegIterator I(RegID, &MRI); I.isValid(); ++I) {
 231     if (!IsEliminated) {
 232       RegisterMappings[*I].first = Write;
 233       RegisterMappings[*I].second.AliasRegID = 0U;
 234     }
 235
 236     if (IsWriteZero)
 237       ZeroRegisters.setBit(*I);
 238     else
 239       ZeroRegisters.clearBit(*I);
 240   }
 241 }
 242
 243 void RegisterFile::removeRegisterWrite(
 244     const WriteState &WS, MutableArrayRef<unsigned> FreedPhysRegs) {
 245   // Early exit if this write was eliminated. A write eliminated at register
 246   // renaming stage generates an alias, and it is not added to the PRF.
 247   if (WS.isEliminated())
 248     return;
 249
 250   MCPhysReg RegID = WS.getRegisterID();
 251
 252   assert(RegID != 0 && "Invalidating an already invalid register?");
 253   assert(WS.getCyclesLeft() != UNKNOWN_CYCLES &&
 254          "Invalidating a write of unknown cycles!");
 255   assert(WS.getCyclesLeft() <= 0 && "Invalid cycles left for this write!");
 256
 257   bool ShouldFreePhysRegs = !WS.isWriteZero();
 258   MCPhysReg RenameAs = RegisterMappings[RegID].second.RenameAs;
 259   if (RenameAs && RenameAs != RegID) {
 260     RegID = RenameAs;
 261
 262     if (!WS.clearsSuperRegisters()) {
 263       // Keep the definition of `RegID` together with register `RenameAs`.
 264       ShouldFreePhysRegs = false;
 265     }
 266   }
 267
 268   if (ShouldFreePhysRegs)
 269     freePhysRegs(RegisterMappings[RegID].second, FreedPhysRegs);
 270
 271   WriteRef &WR = RegisterMappings[RegID].first;
 272   if (WR.getWriteState() == &WS)
 273     WR.invalidate();
 274
 275   for (MCSubRegIterator I(RegID, &MRI); I.isValid(); ++I) {
 276     WriteRef &OtherWR = RegisterMappings[*I].first;
 277     if (OtherWR.getWriteState() == &WS)
 278       OtherWR.invalidate();
 279   }
 280
 281   if (!WS.clearsSuperRegisters())
 282     return;
 283
 284   for (MCSuperRegIterator I(RegID, &MRI); I.isValid(); ++I) {
 285     WriteRef &OtherWR = RegisterMappings[*I].first;
 286     if (OtherWR.getWriteState() == &WS)
 287       OtherWR.invalidate();
 288   }
 289 }
 290
 291 bool RegisterFile::tryEliminateMove(WriteState &WS, ReadState &RS) {
 292   const RegisterMapping &RMFrom = RegisterMappings[RS.getRegisterID()];
 293   const RegisterMapping &RMTo = RegisterMappings[WS.getRegisterID()];
 294
 295   // From and To must be owned by the same PRF.
 296   const RegisterRenamingInfo &RRIFrom = RMFrom.second;
 297   const RegisterRenamingInfo &RRITo = RMTo.second;
 298   unsigned RegisterFileIndex = RRIFrom.IndexPlusCost.first;
 299   if (RegisterFileIndex != RRITo.IndexPlusCost.first)
 300     return false;
 301
 302   // We only allow move elimination for writes that update a full physical
 303   // register. On X86, move elimination is possible with 32-bit general purpose
 304   // registers because writes to those registers are not partial writes.  If a
 305   // register move is a partial write, then we conservatively assume that move
 306   // elimination fails, since it would either trigger a partial update, or the
 307   // issue of a merge opcode.
 308   //
 309   // Note that this constraint may be lifted in future.  For example, we could
 310   // make this model more flexible, and let users customize the set of registers
 311   // (i.e. register classes) that allow move elimination.
 312   //
 313   // For now, we assume that there is a strong correlation between registers
 314   // that allow move elimination, and how those same registers are renamed in
 315   // hardware.
 316   if (RRITo.RenameAs && RRITo.RenameAs != WS.getRegisterID()) {
 317     // Early exit if the PRF doesn't support move elimination for this register.
 318     if (!RegisterMappings[RRITo.RenameAs].second.AllowMoveElimination)
 319       return false;
 320     if (!WS.clearsSuperRegisters())
 321       return false;
 322   }
 323
 324   RegisterMappingTracker &RMT = RegisterFiles[RegisterFileIndex];
 325   if (RMT.MaxMoveEliminatedPerCycle &&
 326       RMT.NumMoveEliminated == RMT.MaxMoveEliminatedPerCycle)
 327     return false;
 328
 329   bool IsZeroMove = ZeroRegisters[RS.getRegisterID()];
 330   if (RMT.AllowZeroMoveEliminationOnly && !IsZeroMove)
 331     return false;
 332
 333   // Construct an alias.
 334   MCPhysReg AliasedReg =
 335       RRIFrom.RenameAs ? RRIFrom.RenameAs : RS.getRegisterID();
 336   MCPhysReg AliasReg = RRITo.RenameAs ? RRITo.RenameAs : WS.getRegisterID();
 337
 338   const RegisterRenamingInfo &RMAlias = RegisterMappings[AliasedReg].second;
 339   if (RMAlias.AliasRegID)
 340     AliasedReg = RMAlias.AliasRegID;
 341
 342   RegisterMappings[AliasReg].second.AliasRegID = AliasedReg;
 343   for (MCSubRegIterator I(AliasReg, &MRI); I.isValid(); ++I)
 344     RegisterMappings[*I].second.AliasRegID = AliasedReg;
 345
 346   if (IsZeroMove) {
 347     WS.setWriteZero();
 348     RS.setReadZero();
 349   }
 350   WS.setEliminated();
 351   RMT.NumMoveEliminated++;
 352
 353   return true;
 354 }
 355
 356 void RegisterFile::collectWrites(const ReadState &RS,
 357                                  SmallVectorImpl<WriteRef> &Writes) const {
 358   MCPhysReg RegID = RS.getRegisterID();
 359   assert(RegID && RegID < RegisterMappings.size());
 360   LLVM_DEBUG(dbgs() << "RegisterFile: collecting writes for register "
 361                     << MRI.getName(RegID) << '\n');
 362
 363   // Check if this is an alias.
 364   const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second;
 365   if (RRI.AliasRegID)
 366     RegID = RRI.AliasRegID;
 367
 368   const WriteRef &WR = RegisterMappings[RegID].first;
 369   if (WR.isValid())
 370     Writes.push_back(WR);
 371
 372   // Handle potential partial register updates.
 373   for (MCSubRegIterator I(RegID, &MRI); I.isValid(); ++I) {
 374     const WriteRef &WR = RegisterMappings[*I].first;
 375     if (WR.isValid())
 376       Writes.push_back(WR);
 377   }
 378
 379   // Remove duplicate entries and resize the input vector.
 380   if (Writes.size() > 1) {
 381     sort(Writes, [](const WriteRef &Lhs, const WriteRef &Rhs) {
 382       return Lhs.getWriteState() < Rhs.getWriteState();
 383     });
 384     auto It = std::unique(Writes.begin(), Writes.end());
 385     Writes.resize(std::distance(Writes.begin(), It));
 386   }
 387
 388   LLVM_DEBUG({
 389     for (const WriteRef &WR : Writes) {
 390       const WriteState &WS = *WR.getWriteState();
 391       dbgs() << "[PRF] Found a dependent use of Register "
 392              << MRI.getName(WS.getRegisterID()) << " (defined by instruction #"
 393              << WR.getSourceIndex() << ")\n";
 394     }
 395   });
 396 }
 397
 398 void RegisterFile::addRegisterRead(ReadState &RS,
 399                                    const MCSubtargetInfo &STI) const {
 400   MCPhysReg RegID = RS.getRegisterID();
 401   const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second;
 402   RS.setPRF(RRI.IndexPlusCost.first);
 403   if (RS.isIndependentFromDef())
 404     return;
 405
 406   if (ZeroRegisters[RS.getRegisterID()])
 407     RS.setReadZero();
 408
 409   SmallVector<WriteRef, 4> DependentWrites;
 410   collectWrites(RS, DependentWrites);
 411   RS.setDependentWrites(DependentWrites.size());
 412
 413   // We know that this read depends on all the writes in DependentWrites.
 414   // For each write, check if we have ReadAdvance information, and use it
 415   // to figure out in how many cycles this read becomes available.
 416   const ReadDescriptor &RD = RS.getDescriptor();
 417   const MCSchedModel &SM = STI.getSchedModel();
 418   const MCSchedClassDesc *SC = SM.getSchedClassDesc(RD.SchedClassID);
 419   for (WriteRef &WR : DependentWrites) {
 420     WriteState &WS = *WR.getWriteState();
 421     unsigned WriteResID = WS.getWriteResourceID();
 422     int ReadAdvance = STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID);
 423     WS.addUser(WR.getSourceIndex(), &RS, ReadAdvance);
 424   }
 425 }
 426
 427 unsigned RegisterFile::isAvailable(ArrayRef<MCPhysReg> Regs) const {
 428   SmallVector<unsigned, 4> NumPhysRegs(getNumRegisterFiles());
 429
 430   // Find how many new mappings must be created for each register file.
 431   for (const MCPhysReg RegID : Regs) {
 432     const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second;
 433     const IndexPlusCostPairTy &Entry = RRI.IndexPlusCost;
 434     if (Entry.first)
 435       NumPhysRegs[Entry.first] += Entry.second;
 436     NumPhysRegs[0] += Entry.second;
 437   }
 438
 439   unsigned Response = 0;
 440   for (unsigned I = 0, E = getNumRegisterFiles(); I < E; ++I) {
 441     unsigned NumRegs = NumPhysRegs[I];
 442     if (!NumRegs)
 443       continue;
 444
 445     const RegisterMappingTracker &RMT = RegisterFiles[I];
 446     if (!RMT.NumPhysRegs) {
 447       // The register file has an unbounded number of microarchitectural
 448       // registers.
 449       continue;
 450     }
 451
 452     if (RMT.NumPhysRegs < NumRegs) {
 453       // The current register file is too small. This may occur if the number of
 454       // microarchitectural registers in register file #0 was changed by the
 455       // users via flag -reg-file-size. Alternatively, the scheduling model
 456       // specified a too small number of registers for this register file.
 457       LLVM_DEBUG(dbgs() << "Not enough registers in the register file.\n");
 458
 459       // FIXME: Normalize the instruction register count to match the
 460       // NumPhysRegs value.  This is a highly unusual case, and is not expected
 461       // to occur.  This normalization is hiding an inconsistency in either the
 462       // scheduling model or in the value that the user might have specified
 463       // for NumPhysRegs.
 464       NumRegs = RMT.NumPhysRegs;
 465     }
 466
 467     if (RMT.NumPhysRegs < (RMT.NumUsedPhysRegs + NumRegs))
 468       Response |= (1U << I);
 469   }
 470
 471   return Response;
 472 }
 473
 474 #ifndef NDEBUG
 475 void RegisterFile::dump() const {
 476   for (unsigned I = 0, E = MRI.getNumRegs(); I < E; ++I) {
 477     const RegisterMapping &RM = RegisterMappings[I];
 478     const RegisterRenamingInfo &RRI = RM.second;
 479     if (ZeroRegisters[I]) {
 480       dbgs() << MRI.getName(I) << ", " << I
 481              << ", PRF=" << RRI.IndexPlusCost.first
 482              << ", Cost=" << RRI.IndexPlusCost.second
 483              << ", RenameAs=" << RRI.RenameAs << ", IsZero=" << ZeroRegisters[I]
 484              << ",";
 485       RM.first.dump();
 486       dbgs() << '\n';
 487     }
 488   }
 489
 490   for (unsigned I = 0, E = getNumRegisterFiles(); I < E; ++I) {
 491     dbgs() << "Register File #" << I;
 492     const RegisterMappingTracker &RMT = RegisterFiles[I];
 493     dbgs() << "\n  TotalMappings:        " << RMT.NumPhysRegs
 494            << "\n  NumUsedMappings:      " << RMT.NumUsedPhysRegs << '\n';
 495   }
 496 }
 497 #endif
 498
 499 } // namespace mca
 500 } // namespace llvm