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