contrib/llvm/lib/MCA/HardwareUnits/RegisterFile.cpp

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