llvm/utils/TableGen/RegisterBankEmitter.cpp

   1 //===- RegisterBankEmitter.cpp - Generate a Register Bank Desc. -*- 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 //
   9 // This tablegen backend is responsible for emitting a description of a target
  10 // register bank for a code generator.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "Common/CodeGenRegisters.h"
  15 #include "Common/CodeGenTarget.h"
  16 #include "Common/InfoByHwMode.h"
  17 #include "llvm/ADT/BitVector.h"
  18 #include "llvm/Support/Debug.h"
  19 #include "llvm/Support/MathExtras.h"
  20 #include "llvm/TableGen/Error.h"
  21 #include "llvm/TableGen/Record.h"
  22 #include "llvm/TableGen/TGTimer.h"
  23 #include "llvm/TableGen/TableGenBackend.h"
  24
  25 #define DEBUG_TYPE "register-bank-emitter"
  26
  27 using namespace llvm;
  28
  29 namespace {
  30 class RegisterBank {
  31
  32   /// A vector of register classes that are included in the register bank.
  33   typedef std::vector<const CodeGenRegisterClass *> RegisterClassesTy;
  34
  35 private:
  36   const Record &TheDef;
  37
  38   /// The register classes that are covered by the register bank.
  39   RegisterClassesTy RCs;
  40
  41   /// The register class with the largest register size.
  42   std::vector<const CodeGenRegisterClass *> RCsWithLargestRegSize;
  43
  44 public:
  45   RegisterBank(const Record &TheDef, unsigned NumModeIds)
  46       : TheDef(TheDef), RCsWithLargestRegSize(NumModeIds) {}
  47
  48   /// Get the human-readable name for the bank.
  49   StringRef getName() const { return TheDef.getValueAsString("Name"); }
  50   /// Get the name of the enumerator in the ID enumeration.
  51   std::string getEnumeratorName() const {
  52     return (TheDef.getName() + "ID").str();
  53   }
  54
  55   /// Get the name of the array holding the register class coverage data;
  56   std::string getCoverageArrayName() const {
  57     return (TheDef.getName() + "CoverageData").str();
  58   }
  59
  60   /// Get the name of the global instance variable.
  61   StringRef getInstanceVarName() const { return TheDef.getName(); }
  62
  63   const Record &getDef() const { return TheDef; }
  64
  65   /// Get the register classes listed in the RegisterBank.RegisterClasses field.
  66   std::vector<const CodeGenRegisterClass *>
  67   getExplicitlySpecifiedRegisterClasses(
  68       const CodeGenRegBank &RegisterClassHierarchy) const {
  69     std::vector<const CodeGenRegisterClass *> RCs;
  70     for (const auto *RCDef : getDef().getValueAsListOfDefs("RegisterClasses"))
  71       RCs.push_back(RegisterClassHierarchy.getRegClass(RCDef));
  72     return RCs;
  73   }
  74
  75   /// Add a register class to the bank without duplicates.
  76   void addRegisterClass(const CodeGenRegisterClass *RC) {
  77     if (llvm::is_contained(RCs, RC))
  78       return;
  79
  80     // FIXME? We really want the register size rather than the spill size
  81     //        since the spill size may be bigger on some targets with
  82     //        limited load/store instructions. However, we don't store the
  83     //        register size anywhere (we could sum the sizes of the subregisters
  84     //        but there may be additional bits too) and we can't derive it from
  85     //        the VT's reliably due to Untyped.
  86     unsigned NumModeIds = RCsWithLargestRegSize.size();
  87     for (unsigned M = 0; M < NumModeIds; ++M) {
  88       if (RCsWithLargestRegSize[M] == nullptr)
  89         RCsWithLargestRegSize[M] = RC;
  90       else if (RCsWithLargestRegSize[M]->RSI.get(M).SpillSize <
  91                RC->RSI.get(M).SpillSize)
  92         RCsWithLargestRegSize[M] = RC;
  93       assert(RCsWithLargestRegSize[M] && "RC was nullptr?");
  94     }
  95
  96     RCs.emplace_back(RC);
  97   }
  98
  99   const CodeGenRegisterClass *getRCWithLargestRegSize(unsigned HwMode) const {
 100     return RCsWithLargestRegSize[HwMode];
 101   }
 102
 103   iterator_range<typename RegisterClassesTy::const_iterator>
 104   register_classes() const {
 105     return llvm::make_range(RCs.begin(), RCs.end());
 106   }
 107 };
 108
 109 class RegisterBankEmitter {
 110 private:
 111   const CodeGenTarget Target;
 112   const RecordKeeper &Records;
 113
 114   void emitHeader(raw_ostream &OS, const StringRef TargetName,
 115                   ArrayRef<RegisterBank> Banks);
 116   void emitBaseClassDefinition(raw_ostream &OS, const StringRef TargetName,
 117                                ArrayRef<RegisterBank> Banks);
 118   void emitBaseClassImplementation(raw_ostream &OS, const StringRef TargetName,
 119                                    ArrayRef<RegisterBank> Banks);
 120
 121 public:
 122   RegisterBankEmitter(const RecordKeeper &R) : Target(R), Records(R) {}
 123
 124   void run(raw_ostream &OS);
 125 };
 126
 127 } // end anonymous namespace
 128
 129 /// Emit code to declare the ID enumeration and external global instance
 130 /// variables.
 131 void RegisterBankEmitter::emitHeader(raw_ostream &OS,
 132                                      const StringRef TargetName,
 133                                      ArrayRef<RegisterBank> Banks) {
 134   // <Target>RegisterBankInfo.h
 135   OS << "namespace llvm {\n"
 136      << "namespace " << TargetName << " {\n"
 137      << "enum : unsigned {\n";
 138
 139   OS << "  InvalidRegBankID = ~0u,\n";
 140   unsigned ID = 0;
 141   for (const auto &Bank : Banks)
 142     OS << "  " << Bank.getEnumeratorName() << " = " << ID++ << ",\n";
 143   OS << "  NumRegisterBanks,\n"
 144      << "};\n"
 145      << "} // end namespace " << TargetName << "\n"
 146      << "} // end namespace llvm\n";
 147 }
 148
 149 /// Emit declarations of the <Target>GenRegisterBankInfo class.
 150 void RegisterBankEmitter::emitBaseClassDefinition(
 151     raw_ostream &OS, const StringRef TargetName, ArrayRef<RegisterBank> Banks) {
 152   OS << "private:\n"
 153      << "  static const RegisterBank *RegBanks[];\n"
 154      << "  static const unsigned Sizes[];\n\n"
 155      << "public:\n"
 156      << "  const RegisterBank &getRegBankFromRegClass(const "
 157         "TargetRegisterClass &RC, LLT Ty) const override;\n"
 158      << "protected:\n"
 159      << "  " << TargetName << "GenRegisterBankInfo(unsigned HwMode = 0);\n"
 160      << "\n";
 161 }
 162
 163 /// Visit each register class belonging to the given register bank.
 164 ///
 165 /// A class belongs to the bank iff any of these apply:
 166 /// * It is explicitly specified
 167 /// * It is a subclass of a class that is a member.
 168 /// * It is a class containing subregisters of the registers of a class that
 169 ///   is a member. This is known as a subreg-class.
 170 ///
 171 /// This function must be called for each explicitly specified register class.
 172 ///
 173 /// \param RC The register class to search.
 174 /// \param Kind A debug string containing the path the visitor took to reach RC.
 175 /// \param VisitFn The action to take for each class visited. It may be called
 176 ///                multiple times for a given class if there are multiple paths
 177 ///                to the class.
 178 static void visitRegisterBankClasses(
 179     const CodeGenRegBank &RegisterClassHierarchy,
 180     const CodeGenRegisterClass *RC, const Twine &Kind,
 181     std::function<void(const CodeGenRegisterClass *, StringRef)> VisitFn,
 182     SmallPtrSetImpl<const CodeGenRegisterClass *> &VisitedRCs) {
 183
 184   // Make sure we only visit each class once to avoid infinite loops.
 185   if (!VisitedRCs.insert(RC).second)
 186     return;
 187
 188   // Visit each explicitly named class.
 189   VisitFn(RC, Kind.str());
 190
 191   for (const auto &PossibleSubclass : RegisterClassHierarchy.getRegClasses()) {
 192     std::string TmpKind =
 193         (Kind + " (" + PossibleSubclass.getName() + ")").str();
 194
 195     // Visit each subclass of an explicitly named class.
 196     if (RC != &PossibleSubclass && RC->hasSubClass(&PossibleSubclass))
 197       visitRegisterBankClasses(RegisterClassHierarchy, &PossibleSubclass,
 198                                TmpKind + " " + RC->getName() + " subclass",
 199                                VisitFn, VisitedRCs);
 200
 201     // Visit each class that contains only subregisters of RC with a common
 202     // subregister-index.
 203     //
 204     // More precisely, PossibleSubclass is a subreg-class iff Reg:SubIdx is in
 205     // PossibleSubclass for all registers Reg from RC using any
 206     // subregister-index SubReg
 207     for (const auto &SubIdx : RegisterClassHierarchy.getSubRegIndices()) {
 208       BitVector BV(RegisterClassHierarchy.getRegClasses().size());
 209       PossibleSubclass.getSuperRegClasses(&SubIdx, BV);
 210       if (BV.test(RC->EnumValue)) {
 211         std::string TmpKind2 = (Twine(TmpKind) + " " + RC->getName() +
 212                                 " class-with-subregs: " + RC->getName())
 213                                    .str();
 214         VisitFn(&PossibleSubclass, TmpKind2);
 215       }
 216     }
 217   }
 218 }
 219
 220 void RegisterBankEmitter::emitBaseClassImplementation(
 221     raw_ostream &OS, StringRef TargetName, ArrayRef<RegisterBank> Banks) {
 222   const CodeGenRegBank &RegisterClassHierarchy = Target.getRegBank();
 223   const CodeGenHwModes &CGH = Target.getHwModes();
 224
 225   OS << "namespace llvm {\n"
 226      << "namespace " << TargetName << " {\n";
 227   for (const auto &Bank : Banks) {
 228     std::vector<std::vector<const CodeGenRegisterClass *>> RCsGroupedByWord(
 229         (RegisterClassHierarchy.getRegClasses().size() + 31) / 32);
 230
 231     for (const auto &RC : Bank.register_classes())
 232       RCsGroupedByWord[RC->EnumValue / 32].push_back(RC);
 233
 234     OS << "const uint32_t " << Bank.getCoverageArrayName() << "[] = {\n";
 235     unsigned LowestIdxInWord = 0;
 236     for (const auto &RCs : RCsGroupedByWord) {
 237       OS << "    // " << LowestIdxInWord << "-" << (LowestIdxInWord + 31)
 238          << "\n";
 239       for (const auto &RC : RCs) {
 240         OS << "    (1u << (" << RC->getQualifiedIdName() << " - "
 241            << LowestIdxInWord << ")) |\n";
 242       }
 243       OS << "    0,\n";
 244       LowestIdxInWord += 32;
 245     }
 246     OS << "};\n";
 247   }
 248   OS << "\n";
 249
 250   for (const auto &Bank : Banks) {
 251     std::string QualifiedBankID =
 252         (TargetName + "::" + Bank.getEnumeratorName()).str();
 253     OS << "constexpr RegisterBank " << Bank.getInstanceVarName() << "(/* ID */ "
 254        << QualifiedBankID << ", /* Name */ \"" << Bank.getName() << "\", "
 255        << "/* CoveredRegClasses */ " << Bank.getCoverageArrayName()
 256        << ", /* NumRegClasses */ "
 257        << RegisterClassHierarchy.getRegClasses().size() << ");\n";
 258   }
 259   OS << "} // end namespace " << TargetName << "\n"
 260      << "\n";
 261
 262   OS << "const RegisterBank *" << TargetName
 263      << "GenRegisterBankInfo::RegBanks[] = {\n";
 264   for (const auto &Bank : Banks)
 265     OS << "    &" << TargetName << "::" << Bank.getInstanceVarName() << ",\n";
 266   OS << "};\n\n";
 267
 268   unsigned NumModeIds = CGH.getNumModeIds();
 269   OS << "const unsigned " << TargetName << "GenRegisterBankInfo::Sizes[] = {\n";
 270   for (unsigned M = 0; M < NumModeIds; ++M) {
 271     OS << "    // Mode = " << M << " (";
 272     if (M == DefaultMode)
 273       OS << "Default";
 274     else
 275       OS << CGH.getMode(M).Name;
 276     OS << ")\n";
 277     for (const auto &Bank : Banks) {
 278       const CodeGenRegisterClass &RC = *Bank.getRCWithLargestRegSize(M);
 279       unsigned Size = RC.RSI.get(M).SpillSize;
 280       OS << "    " << Size << ",\n";
 281     }
 282   }
 283   OS << "};\n\n";
 284
 285   OS << TargetName << "GenRegisterBankInfo::" << TargetName
 286      << "GenRegisterBankInfo(unsigned HwMode)\n"
 287      << "    : RegisterBankInfo(RegBanks, " << TargetName
 288      << "::NumRegisterBanks, Sizes, HwMode) {\n"
 289      << "  // Assert that RegBank indices match their ID's\n"
 290      << "#ifndef NDEBUG\n"
 291      << "  for (auto RB : enumerate(RegBanks))\n"
 292      << "    assert(RB.index() == RB.value()->getID() && \"Index != ID\");\n"
 293      << "#endif // NDEBUG\n"
 294      << "}\n";
 295
 296   uint32_t NumRegBanks = Banks.size();
 297   uint32_t BitSize = NextPowerOf2(Log2_32(NumRegBanks));
 298   uint32_t ElemsPerWord = 32 / BitSize;
 299   uint32_t BitMask = (1 << BitSize) - 1;
 300   bool HasAmbigousOrMissingEntry = false;
 301   struct Entry {
 302     std::string RCIdName;
 303     std::string RBIdName;
 304   };
 305   SmallVector<Entry, 0> Entries;
 306   for (const auto &Bank : Banks) {
 307     for (const auto *RC : Bank.register_classes()) {
 308       if (RC->EnumValue >= Entries.size())
 309         Entries.resize(RC->EnumValue + 1);
 310       Entry &E = Entries[RC->EnumValue];
 311       E.RCIdName = RC->getIdName();
 312       if (!E.RBIdName.empty()) {
 313         HasAmbigousOrMissingEntry = true;
 314         E.RBIdName = "InvalidRegBankID";
 315       } else {
 316         E.RBIdName = (TargetName + "::" + Bank.getEnumeratorName()).str();
 317       }
 318     }
 319   }
 320   for (auto &E : Entries) {
 321     if (E.RBIdName.empty()) {
 322       HasAmbigousOrMissingEntry = true;
 323       E.RBIdName = "InvalidRegBankID";
 324     }
 325   }
 326   OS << "const RegisterBank &\n"
 327      << TargetName
 328      << "GenRegisterBankInfo::getRegBankFromRegClass"
 329         "(const TargetRegisterClass &RC, LLT) const {\n";
 330   if (HasAmbigousOrMissingEntry) {
 331     OS << "  constexpr uint32_t InvalidRegBankID = uint32_t("
 332        << TargetName + "::InvalidRegBankID) & " << BitMask << ";\n";
 333   }
 334   unsigned TableSize =
 335       Entries.size() / ElemsPerWord + ((Entries.size() % ElemsPerWord) > 0);
 336   OS << "  static const uint32_t RegClass2RegBank[" << TableSize << "] = {\n";
 337   uint32_t Shift = 32 - BitSize;
 338   bool First = true;
 339   std::string TrailingComment;
 340   for (auto &E : Entries) {
 341     Shift += BitSize;
 342     if (Shift == 32) {
 343       Shift = 0;
 344       if (First)
 345         First = false;
 346       else
 347         OS << ',' << TrailingComment << '\n';
 348     } else {
 349       OS << " |" << TrailingComment << '\n';
 350     }
 351     OS << "    ("
 352        << (E.RBIdName.empty()
 353                ? "InvalidRegBankID"
 354                : Twine("uint32_t(").concat(E.RBIdName).concat(")").str())
 355        << " << " << Shift << ')';
 356     if (!E.RCIdName.empty())
 357       TrailingComment = " // " + E.RCIdName;
 358     else
 359       TrailingComment = "";
 360   }
 361   OS << TrailingComment
 362      << "\n  };\n"
 363         "  const unsigned RegClassID = RC.getID();\n"
 364         "  if (LLVM_LIKELY(RegClassID < "
 365      << Entries.size()
 366      << ")) {\n"
 367         "    unsigned RegBankID = (RegClass2RegBank[RegClassID / "
 368      << ElemsPerWord << "] >> ((RegClassID % " << ElemsPerWord << ") * "
 369      << BitSize << ")) & " << BitMask << ";\n";
 370   if (HasAmbigousOrMissingEntry) {
 371     OS << "    if (RegBankID != InvalidRegBankID)\n"
 372           "      return getRegBank(RegBankID);\n";
 373   } else
 374     OS << "    return getRegBank(RegBankID);\n";
 375   OS << "  }\n"
 376         "  llvm_unreachable(llvm::Twine(\"Target needs to handle register "
 377         "class ID "
 378         "0x\").concat(llvm::Twine::utohexstr(RegClassID)).str().c_str());\n"
 379         "}\n";
 380
 381   OS << "} // end namespace llvm\n";
 382 }
 383
 384 void RegisterBankEmitter::run(raw_ostream &OS) {
 385   StringRef TargetName = Target.getName();
 386   const CodeGenRegBank &RegisterClassHierarchy = Target.getRegBank();
 387   const CodeGenHwModes &CGH = Target.getHwModes();
 388
 389   TGTimer &Timer = Records.getTimer();
 390   Timer.startTimer("Analyze records");
 391   std::vector<RegisterBank> Banks;
 392   for (const auto &V : Records.getAllDerivedDefinitions("RegisterBank")) {
 393     SmallPtrSet<const CodeGenRegisterClass *, 8> VisitedRCs;
 394     RegisterBank Bank(*V, CGH.getNumModeIds());
 395
 396     for (const CodeGenRegisterClass *RC :
 397          Bank.getExplicitlySpecifiedRegisterClasses(RegisterClassHierarchy)) {
 398       visitRegisterBankClasses(
 399           RegisterClassHierarchy, RC, "explicit",
 400           [&Bank](const CodeGenRegisterClass *RC, StringRef Kind) {
 401             LLVM_DEBUG(dbgs()
 402                        << "Added " << RC->getName() << "(" << Kind << ")\n");
 403             Bank.addRegisterClass(RC);
 404           },
 405           VisitedRCs);
 406     }
 407
 408     Banks.push_back(Bank);
 409   }
 410
 411   // Warn about ambiguous MIR caused by register bank/class name clashes.
 412   Timer.startTimer("Warn ambiguous");
 413   for (const auto &Class : RegisterClassHierarchy.getRegClasses()) {
 414     for (const auto &Bank : Banks) {
 415       if (Bank.getName().lower() == StringRef(Class.getName()).lower()) {
 416         PrintWarning(Bank.getDef().getLoc(), "Register bank names should be "
 417                                              "distinct from register classes "
 418                                              "to avoid ambiguous MIR");
 419         PrintNote(Bank.getDef().getLoc(), "RegisterBank was declared here");
 420         PrintNote(Class.getDef()->getLoc(), "RegisterClass was declared here");
 421       }
 422     }
 423   }
 424
 425   Timer.startTimer("Emit output");
 426   emitSourceFileHeader("Register Bank Source Fragments", OS);
 427   OS << "#ifdef GET_REGBANK_DECLARATIONS\n"
 428      << "#undef GET_REGBANK_DECLARATIONS\n";
 429   emitHeader(OS, TargetName, Banks);
 430   OS << "#endif // GET_REGBANK_DECLARATIONS\n\n"
 431      << "#ifdef GET_TARGET_REGBANK_CLASS\n"
 432      << "#undef GET_TARGET_REGBANK_CLASS\n";
 433   emitBaseClassDefinition(OS, TargetName, Banks);
 434   OS << "#endif // GET_TARGET_REGBANK_CLASS\n\n"
 435      << "#ifdef GET_TARGET_REGBANK_IMPL\n"
 436      << "#undef GET_TARGET_REGBANK_IMPL\n";
 437   emitBaseClassImplementation(OS, TargetName, Banks);
 438   OS << "#endif // GET_TARGET_REGBANK_IMPL\n";
 439 }
 440
 441 static TableGen::Emitter::OptClass<RegisterBankEmitter>
 442     X("gen-register-bank", "Generate registers bank descriptions");