contrib/llvm/tools/llvm-mca/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 "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 llvm::MCSchedModel &SM,
  28                            const llvm::MCRegisterInfo &mri, unsigned NumRegs)
  29     : MRI(mri), RegisterMappings(mri.getNumRegs(),
  30                                  {WriteRef(), {IndexPlusCostPairTy(0, 1), 0}}) {
  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   addRegisterFile({} /* all registers */, 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   for (unsigned I = 0, E = Info.NumRegisterFiles; I < E; ++I) {
  48     const MCRegisterFileDesc &RF = Info.RegisterFiles[I];
  49     // Skip invalid register files with zero physical registers.
  50     unsigned Length = RF.NumRegisterCostEntries;
  51     if (!RF.NumPhysRegs)
  52       continue;
  53     // The cost of a register definition is equivalent to the number of
  54     // physical registers that are allocated at register renaming stage.
  55     const MCRegisterCostEntry *FirstElt =
  56         &Info.RegisterCostTable[RF.RegisterCostEntryIdx];
  57     addRegisterFile(ArrayRef<MCRegisterCostEntry>(FirstElt, Length),
  58                     RF.NumPhysRegs);
  59   }
  60 }
  61
  62 void RegisterFile::addRegisterFile(ArrayRef<MCRegisterCostEntry> Entries,
  63                                    unsigned NumPhysRegs) {
  64   // A default register file is always allocated at index #0. That register file
  65   // is mainly used to count the total number of mappings created by all
  66   // register files at runtime. Users can limit the number of available physical
  67   // registers in register file #0 through the command line flag
  68   // `-register-file-size`.
  69   unsigned RegisterFileIndex = RegisterFiles.size();
  70   RegisterFiles.emplace_back(NumPhysRegs);
  71
  72   // Special case where there is no register class identifier in the set.
  73   // An empty set of register classes means: this register file contains all
  74   // the physical registers specified by the target.
  75   // We optimistically assume that a register can be renamed at the cost of a
  76   // single physical register. The constructor of RegisterFile ensures that
  77   // a RegisterMapping exists for each logical register defined by the Target.
  78   if (Entries.empty())
  79     return;
  80
  81   // Now update the cost of individual registers.
  82   for (const MCRegisterCostEntry &RCE : Entries) {
  83     const MCRegisterClass &RC = MRI.getRegClass(RCE.RegisterClassID);
  84     for (const MCPhysReg Reg : RC) {
  85       RegisterRenamingInfo &Entry = RegisterMappings[Reg].second;
  86       IndexPlusCostPairTy &IPC = Entry.IndexPlusCost;
  87       if (IPC.first && IPC.first != RegisterFileIndex) {
  88         // The only register file that is allowed to overlap is the default
  89         // register file at index #0. The analysis is inaccurate if register
  90         // files overlap.
  91         errs() << "warning: register " << MRI.getName(Reg)
  92                << " defined in multiple register files.";
  93       }
  94       IPC = std::make_pair(RegisterFileIndex, RCE.Cost);
  95       Entry.RenameAs = Reg;
  96
  97       // Assume the same cost for each sub-register.
  98       for (MCSubRegIterator I(Reg, &MRI); I.isValid(); ++I) {
  99         RegisterRenamingInfo &OtherEntry = RegisterMappings[*I].second;
 100         if (!OtherEntry.IndexPlusCost.first &&
 101             (!OtherEntry.RenameAs ||
 102              MRI.isSuperRegister(*I, OtherEntry.RenameAs))) {
 103           OtherEntry.IndexPlusCost = IPC;
 104           OtherEntry.RenameAs = Reg;
 105         }
 106       }
 107     }
 108   }
 109 }
 110
 111 void RegisterFile::allocatePhysRegs(const RegisterRenamingInfo &Entry,
 112                                     MutableArrayRef<unsigned> UsedPhysRegs) {
 113   unsigned RegisterFileIndex = Entry.IndexPlusCost.first;
 114   unsigned Cost = Entry.IndexPlusCost.second;
 115   if (RegisterFileIndex) {
 116     RegisterMappingTracker &RMT = RegisterFiles[RegisterFileIndex];
 117     RMT.NumUsedPhysRegs += Cost;
 118     UsedPhysRegs[RegisterFileIndex] += Cost;
 119   }
 120
 121   // Now update the default register mapping tracker.
 122   RegisterFiles[0].NumUsedPhysRegs += Cost;
 123   UsedPhysRegs[0] += Cost;
 124 }
 125
 126 void RegisterFile::freePhysRegs(const RegisterRenamingInfo &Entry,
 127                                 MutableArrayRef<unsigned> FreedPhysRegs) {
 128   unsigned RegisterFileIndex = Entry.IndexPlusCost.first;
 129   unsigned Cost = Entry.IndexPlusCost.second;
 130   if (RegisterFileIndex) {
 131     RegisterMappingTracker &RMT = RegisterFiles[RegisterFileIndex];
 132     RMT.NumUsedPhysRegs -= Cost;
 133     FreedPhysRegs[RegisterFileIndex] += Cost;
 134   }
 135
 136   // Now update the default register mapping tracker.
 137   RegisterFiles[0].NumUsedPhysRegs -= Cost;
 138   FreedPhysRegs[0] += Cost;
 139 }
 140
 141 void RegisterFile::addRegisterWrite(WriteRef Write,
 142                                     MutableArrayRef<unsigned> UsedPhysRegs,
 143                                     bool ShouldAllocatePhysRegs) {
 144   WriteState &WS = *Write.getWriteState();
 145   unsigned RegID = WS.getRegisterID();
 146   assert(RegID && "Adding an invalid register definition?");
 147
 148   LLVM_DEBUG({
 149     dbgs() << "RegisterFile: addRegisterWrite [ " << Write.getSourceIndex()
 150            << ", " << MRI.getName(RegID) << "]\n";
 151   });
 152
 153   // If RenameAs is equal to RegID, then RegID is subject to register renaming
 154   // and false dependencies on RegID are all eliminated.
 155
 156   // If RenameAs references the invalid register, then we optimistically assume
 157   // that it can be renamed. In the absence of tablegen descriptors for register
 158   // files, RenameAs is always set to the invalid register ID.  In all other
 159   // cases, RenameAs must be either equal to RegID, or it must reference a
 160   // super-register of RegID.
 161
 162   // If RenameAs is a super-register of RegID, then a write to RegID has always
 163   // a false dependency on RenameAs. The only exception is for when the write
 164   // implicitly clears the upper portion of the underlying register.
 165   // If a write clears its super-registers, then it is renamed as `RenameAs`.
 166   const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second;
 167   if (RRI.RenameAs && RRI.RenameAs != RegID) {
 168     RegID = RRI.RenameAs;
 169     const WriteRef &OtherWrite = RegisterMappings[RegID].first;
 170
 171     if (!WS.clearsSuperRegisters()) {
 172       // The processor keeps the definition of `RegID` together with register
 173       // `RenameAs`. Since this partial write is not renamed, no physical
 174       // register is allocated.
 175       ShouldAllocatePhysRegs = false;
 176
 177       if (OtherWrite.getSourceIndex() != Write.getSourceIndex()) {
 178         // This partial write has a false dependency on RenameAs.
 179         WS.setDependentWrite(OtherWrite.getWriteState());
 180       }
 181     }
 182   }
 183
 184   // Update the mapping for register RegID including its sub-registers.
 185   RegisterMappings[RegID].first = Write;
 186   for (MCSubRegIterator I(RegID, &MRI); I.isValid(); ++I)
 187     RegisterMappings[*I].first = Write;
 188
 189   // No physical registers are allocated for instructions that are optimized in
 190   // hardware. For example, zero-latency data-dependency breaking instructions
 191   // don't consume physical registers.
 192   if (ShouldAllocatePhysRegs)
 193     allocatePhysRegs(RegisterMappings[RegID].second, UsedPhysRegs);
 194
 195   if (!WS.clearsSuperRegisters())
 196     return;
 197
 198   for (MCSuperRegIterator I(RegID, &MRI); I.isValid(); ++I)
 199     RegisterMappings[*I].first = Write;
 200 }
 201
 202 void RegisterFile::removeRegisterWrite(const WriteState &WS,
 203                                        MutableArrayRef<unsigned> FreedPhysRegs,
 204                                        bool ShouldFreePhysRegs) {
 205   unsigned RegID = WS.getRegisterID();
 206
 207   assert(RegID != 0 && "Invalidating an already invalid register?");
 208   assert(WS.getCyclesLeft() != UNKNOWN_CYCLES &&
 209          "Invalidating a write of unknown cycles!");
 210   assert(WS.getCyclesLeft() <= 0 && "Invalid cycles left for this write!");
 211
 212   unsigned RenameAs = RegisterMappings[RegID].second.RenameAs;
 213   if (RenameAs && RenameAs != RegID) {
 214     RegID = RenameAs;
 215
 216     if (!WS.clearsSuperRegisters()) {
 217       // Keep the definition of `RegID` together with register `RenameAs`.
 218       ShouldFreePhysRegs = false;
 219     }
 220   }
 221
 222   if (ShouldFreePhysRegs)
 223     freePhysRegs(RegisterMappings[RegID].second, FreedPhysRegs);
 224
 225   WriteRef &WR = RegisterMappings[RegID].first;
 226   if (WR.getWriteState() == &WS)
 227     WR.invalidate();
 228
 229   for (MCSubRegIterator I(RegID, &MRI); I.isValid(); ++I) {
 230     WriteRef &OtherWR = RegisterMappings[*I].first;
 231     if (OtherWR.getWriteState() == &WS)
 232       OtherWR.invalidate();
 233   }
 234
 235   if (!WS.clearsSuperRegisters())
 236     return;
 237
 238   for (MCSuperRegIterator I(RegID, &MRI); I.isValid(); ++I) {
 239     WriteRef &OtherWR = RegisterMappings[*I].first;
 240     if (OtherWR.getWriteState() == &WS)
 241       OtherWR.invalidate();
 242   }
 243 }
 244
 245 void RegisterFile::collectWrites(SmallVectorImpl<WriteRef> &Writes,
 246                                  unsigned RegID) const {
 247   assert(RegID && RegID < RegisterMappings.size());
 248   LLVM_DEBUG(dbgs() << "RegisterFile: collecting writes for register "
 249                     << MRI.getName(RegID) << '\n');
 250   const WriteRef &WR = RegisterMappings[RegID].first;
 251   if (WR.isValid())
 252     Writes.push_back(WR);
 253
 254   // Handle potential partial register updates.
 255   for (MCSubRegIterator I(RegID, &MRI); I.isValid(); ++I) {
 256     const WriteRef &WR = RegisterMappings[*I].first;
 257     if (WR.isValid())
 258       Writes.push_back(WR);
 259   }
 260
 261   // Remove duplicate entries and resize the input vector.
 262   llvm::sort(Writes.begin(), Writes.end(),
 263              [](const WriteRef &Lhs, const WriteRef &Rhs) {
 264                return Lhs.getWriteState() < Rhs.getWriteState();
 265              });
 266   auto It = std::unique(Writes.begin(), Writes.end());
 267   Writes.resize(std::distance(Writes.begin(), It));
 268
 269   LLVM_DEBUG({
 270     for (const WriteRef &WR : Writes) {
 271       const WriteState &WS = *WR.getWriteState();
 272       dbgs() << "[PRF] Found a dependent use of Register "
 273              << MRI.getName(WS.getRegisterID()) << " (defined by intruction #"
 274              << WR.getSourceIndex() << ")\n";
 275     }
 276   });
 277 }
 278
 279 unsigned RegisterFile::isAvailable(ArrayRef<unsigned> Regs) const {
 280   SmallVector<unsigned, 4> NumPhysRegs(getNumRegisterFiles());
 281
 282   // Find how many new mappings must be created for each register file.
 283   for (const unsigned RegID : Regs) {
 284     const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second;
 285     const IndexPlusCostPairTy &Entry = RRI.IndexPlusCost;
 286     if (Entry.first)
 287       NumPhysRegs[Entry.first] += Entry.second;
 288     NumPhysRegs[0] += Entry.second;
 289   }
 290
 291   unsigned Response = 0;
 292   for (unsigned I = 0, E = getNumRegisterFiles(); I < E; ++I) {
 293     unsigned NumRegs = NumPhysRegs[I];
 294     if (!NumRegs)
 295       continue;
 296
 297     const RegisterMappingTracker &RMT = RegisterFiles[I];
 298     if (!RMT.NumPhysRegs) {
 299       // The register file has an unbounded number of microarchitectural
 300       // registers.
 301       continue;
 302     }
 303
 304     if (RMT.NumPhysRegs < NumRegs) {
 305       // The current register file is too small. This may occur if the number of
 306       // microarchitectural registers in register file #0 was changed by the
 307       // users via flag -reg-file-size. Alternatively, the scheduling model
 308       // specified a too small number of registers for this register file.
 309       report_fatal_error(
 310           "Not enough microarchitectural registers in the register file");
 311     }
 312
 313     if (RMT.NumPhysRegs < (RMT.NumUsedPhysRegs + NumRegs))
 314       Response |= (1U << I);
 315   }
 316
 317   return Response;
 318 }
 319
 320 #ifndef NDEBUG
 321 void RegisterFile::dump() const {
 322   for (unsigned I = 0, E = MRI.getNumRegs(); I < E; ++I) {
 323     const RegisterMapping &RM = RegisterMappings[I];
 324     if (!RM.first.getWriteState())
 325       continue;
 326     const RegisterRenamingInfo &RRI = RM.second;
 327     dbgs() << MRI.getName(I) << ", " << I << ", PRF=" << RRI.IndexPlusCost.first
 328            << ", Cost=" << RRI.IndexPlusCost.second
 329            << ", RenameAs=" << RRI.RenameAs << ", ";
 330     RM.first.dump();
 331     dbgs() << '\n';
 332   }
 333
 334   for (unsigned I = 0, E = getNumRegisterFiles(); I < E; ++I) {
 335     dbgs() << "Register File #" << I;
 336     const RegisterMappingTracker &RMT = RegisterFiles[I];
 337     dbgs() << "\n  TotalMappings:        " << RMT.NumPhysRegs
 338            << "\n  NumUsedMappings:      " << RMT.NumUsedPhysRegs << '\n';
 339   }
 340 }
 341 #endif
 342
 343 } // namespace mca