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 "llvm/ADT/BitVector.h"
15#include "llvm/Support/Debug.h"
16#include "llvm/TableGen/Error.h"
17#include "llvm/TableGen/Record.h"
18#include "llvm/TableGen/TableGenBackend.h"
19
20#include "CodeGenHwModes.h"
21#include "CodeGenRegisters.h"
22
23#define DEBUG_TYPE "register-bank-emitter"
24
25using namespace llvm;
26
27namespace {
28class RegisterBank {
29
30  /// A vector of register classes that are included in the register bank.
31  typedef std::vector<const CodeGenRegisterClass *> RegisterClassesTy;
32
33private:
34  const Record &TheDef;
35
36  /// The register classes that are covered by the register bank.
37  RegisterClassesTy RCs;
38
39  /// The register class with the largest register size.
40  const CodeGenRegisterClass *RCWithLargestRegsSize;
41
42public:
43  RegisterBank(const Record &TheDef)
44      : TheDef(TheDef), RCs(), RCWithLargestRegsSize(nullptr) {}
45
46  /// Get the human-readable name for the bank.
47  StringRef getName() const { return TheDef.getValueAsString("Name"); }
48  /// Get the name of the enumerator in the ID enumeration.
49  std::string getEnumeratorName() const { return (TheDef.getName() + "ID").str(); }
50
51  /// Get the name of the array holding the register class coverage data;
52  std::string getCoverageArrayName() const {
53    return (TheDef.getName() + "CoverageData").str();
54  }
55
56  /// Get the name of the global instance variable.
57  StringRef getInstanceVarName() const { return TheDef.getName(); }
58
59  const Record &getDef() const { return TheDef; }
60
61  /// Get the register classes listed in the RegisterBank.RegisterClasses field.
62  std::vector<const CodeGenRegisterClass *>
63  getExplictlySpecifiedRegisterClasses(
64      CodeGenRegBank &RegisterClassHierarchy) const {
65    std::vector<const CodeGenRegisterClass *> RCs;
66    for (const auto &RCDef : getDef().getValueAsListOfDefs("RegisterClasses"))
67      RCs.push_back(RegisterClassHierarchy.getRegClass(RCDef));
68    return RCs;
69  }
70
71  /// Add a register class to the bank without duplicates.
72  void addRegisterClass(const CodeGenRegisterClass *RC) {
73    if (std::find_if(RCs.begin(), RCs.end(),
74                     [&RC](const CodeGenRegisterClass *X) {
75                       return X == RC;
76                     }) != RCs.end())
77      return;
78
79    // FIXME? We really want the register size rather than the spill size
80    //        since the spill size may be bigger on some targets with
81    //        limited load/store instructions. However, we don't store the
82    //        register size anywhere (we could sum the sizes of the subregisters
83    //        but there may be additional bits too) and we can't derive it from
84    //        the VT's reliably due to Untyped.
85    if (RCWithLargestRegsSize == nullptr)
86      RCWithLargestRegsSize = RC;
87    else if (RCWithLargestRegsSize->RSI.get(DefaultMode).SpillSize <
88             RC->RSI.get(DefaultMode).SpillSize)
89      RCWithLargestRegsSize = RC;
90    assert(RCWithLargestRegsSize && "RC was nullptr?");
91
92    RCs.emplace_back(RC);
93  }
94
95  const CodeGenRegisterClass *getRCWithLargestRegsSize() const {
96    return RCWithLargestRegsSize;
97  }
98
99  iterator_range<typename RegisterClassesTy::const_iterator>
100  register_classes() const {
101    return llvm::make_range(RCs.begin(), RCs.end());
102  }
103};
104
105class RegisterBankEmitter {
106private:
107  RecordKeeper &Records;
108  CodeGenRegBank RegisterClassHierarchy;
109
110  void emitHeader(raw_ostream &OS, const StringRef TargetName,
111                  const std::vector<RegisterBank> &Banks);
112  void emitBaseClassDefinition(raw_ostream &OS, const StringRef TargetName,
113                               const std::vector<RegisterBank> &Banks);
114  void emitBaseClassImplementation(raw_ostream &OS, const StringRef TargetName,
115                                   std::vector<RegisterBank> &Banks);
116
117public:
118  RegisterBankEmitter(RecordKeeper &R)
119      : Records(R), RegisterClassHierarchy(Records, CodeGenHwModes(R)) {}
120
121  void run(raw_ostream &OS);
122};
123
124} // end anonymous namespace
125
126/// Emit code to declare the ID enumeration and external global instance
127/// variables.
128void RegisterBankEmitter::emitHeader(raw_ostream &OS,
129                                     const StringRef TargetName,
130                                     const std::vector<RegisterBank> &Banks) {
131  // <Target>RegisterBankInfo.h
132  OS << "namespace llvm {\n"
133     << "namespace " << TargetName << " {\n"
134     << "enum {\n";
135  for (const auto &Bank : Banks)
136    OS << "  " << Bank.getEnumeratorName() << ",\n";
137  OS << "  NumRegisterBanks,\n"
138     << "};\n"
139     << "} // end namespace " << TargetName << "\n"
140     << "} // end namespace llvm\n";
141}
142
143/// Emit declarations of the <Target>GenRegisterBankInfo class.
144void RegisterBankEmitter::emitBaseClassDefinition(
145    raw_ostream &OS, const StringRef TargetName,
146    const std::vector<RegisterBank> &Banks) {
147  OS << "private:\n"
148     << "  static RegisterBank *RegBanks[];\n\n"
149     << "protected:\n"
150     << "  " << TargetName << "GenRegisterBankInfo();\n"
151     << "\n";
152}
153
154/// Visit each register class belonging to the given register bank.
155///
156/// A class belongs to the bank iff any of these apply:
157/// * It is explicitly specified
158/// * It is a subclass of a class that is a member.
159/// * It is a class containing subregisters of the registers of a class that
160///   is a member. This is known as a subreg-class.
161///
162/// This function must be called for each explicitly specified register class.
163///
164/// \param RC The register class to search.
165/// \param Kind A debug string containing the path the visitor took to reach RC.
166/// \param VisitFn The action to take for each class visited. It may be called
167///                multiple times for a given class if there are multiple paths
168///                to the class.
169static void visitRegisterBankClasses(
170    CodeGenRegBank &RegisterClassHierarchy, const CodeGenRegisterClass *RC,
171    const Twine Kind,
172    std::function<void(const CodeGenRegisterClass *, StringRef)> VisitFn,
173    SmallPtrSetImpl<const CodeGenRegisterClass *> &VisitedRCs) {
174
175  // Make sure we only visit each class once to avoid infinite loops.
176  if (VisitedRCs.count(RC))
177    return;
178  VisitedRCs.insert(RC);
179
180  // Visit each explicitly named class.
181  VisitFn(RC, Kind.str());
182
183  for (const auto &PossibleSubclass : RegisterClassHierarchy.getRegClasses()) {
184    std::string TmpKind =
185        (Twine(Kind) + " (" + PossibleSubclass.getName() + ")").str();
186
187    // Visit each subclass of an explicitly named class.
188    if (RC != &PossibleSubclass && RC->hasSubClass(&PossibleSubclass))
189      visitRegisterBankClasses(RegisterClassHierarchy, &PossibleSubclass,
190                               TmpKind + " " + RC->getName() + " subclass",
191                               VisitFn, VisitedRCs);
192
193    // Visit each class that contains only subregisters of RC with a common
194    // subregister-index.
195    //
196    // More precisely, PossibleSubclass is a subreg-class iff Reg:SubIdx is in
197    // PossibleSubclass for all registers Reg from RC using any
198    // subregister-index SubReg
199    for (const auto &SubIdx : RegisterClassHierarchy.getSubRegIndices()) {
200      BitVector BV(RegisterClassHierarchy.getRegClasses().size());
201      PossibleSubclass.getSuperRegClasses(&SubIdx, BV);
202      if (BV.test(RC->EnumValue)) {
203        std::string TmpKind2 = (Twine(TmpKind) + " " + RC->getName() +
204                                " class-with-subregs: " + RC->getName())
205                                   .str();
206        VisitFn(&PossibleSubclass, TmpKind2);
207      }
208    }
209  }
210}
211
212void RegisterBankEmitter::emitBaseClassImplementation(
213    raw_ostream &OS, StringRef TargetName,
214    std::vector<RegisterBank> &Banks) {
215
216  OS << "namespace llvm {\n"
217     << "namespace " << TargetName << " {\n";
218  for (const auto &Bank : Banks) {
219    std::vector<std::vector<const CodeGenRegisterClass *>> RCsGroupedByWord(
220        (RegisterClassHierarchy.getRegClasses().size() + 31) / 32);
221
222    for (const auto &RC : Bank.register_classes())
223      RCsGroupedByWord[RC->EnumValue / 32].push_back(RC);
224
225    OS << "const uint32_t " << Bank.getCoverageArrayName() << "[] = {\n";
226    unsigned LowestIdxInWord = 0;
227    for (const auto &RCs : RCsGroupedByWord) {
228      OS << "    // " << LowestIdxInWord << "-" << (LowestIdxInWord + 31) << "\n";
229      for (const auto &RC : RCs) {
230        std::string QualifiedRegClassID =
231            (Twine(RC->Namespace) + "::" + RC->getName() + "RegClassID").str();
232        OS << "    (1u << (" << QualifiedRegClassID << " - "
233           << LowestIdxInWord << ")) |\n";
234      }
235      OS << "    0,\n";
236      LowestIdxInWord += 32;
237    }
238    OS << "};\n";
239  }
240  OS << "\n";
241
242  for (const auto &Bank : Banks) {
243    std::string QualifiedBankID =
244        (TargetName + "::" + Bank.getEnumeratorName()).str();
245    const CodeGenRegisterClass &RC = *Bank.getRCWithLargestRegsSize();
246    unsigned Size = RC.RSI.get(DefaultMode).SpillSize;
247    OS << "RegisterBank " << Bank.getInstanceVarName() << "(/* ID */ "
248       << QualifiedBankID << ", /* Name */ \"" << Bank.getName()
249       << "\", /* Size */ " << Size << ", "
250       << "/* CoveredRegClasses */ " << Bank.getCoverageArrayName()
251       << ", /* NumRegClasses */ "
252       << RegisterClassHierarchy.getRegClasses().size() << ");\n";
253  }
254  OS << "} // end namespace " << TargetName << "\n"
255     << "\n";
256
257  OS << "RegisterBank *" << TargetName
258     << "GenRegisterBankInfo::RegBanks[] = {\n";
259  for (const auto &Bank : Banks)
260    OS << "    &" << TargetName << "::" << Bank.getInstanceVarName() << ",\n";
261  OS << "};\n\n";
262
263  OS << TargetName << "GenRegisterBankInfo::" << TargetName
264     << "GenRegisterBankInfo()\n"
265     << "    : RegisterBankInfo(RegBanks, " << TargetName
266     << "::NumRegisterBanks) {\n"
267     << "  // Assert that RegBank indices match their ID's\n"
268     << "#ifndef NDEBUG\n"
269     << "  unsigned Index = 0;\n"
270     << "  for (const auto &RB : RegBanks)\n"
271     << "    assert(Index++ == RB->getID() && \"Index != ID\");\n"
272     << "#endif // NDEBUG\n"
273     << "}\n"
274     << "} // end namespace llvm\n";
275}
276
277void RegisterBankEmitter::run(raw_ostream &OS) {
278  std::vector<Record*> Targets = Records.getAllDerivedDefinitions("Target");
279  if (Targets.size() != 1)
280    PrintFatalError("ERROR: Too many or too few subclasses of Target defined!");
281  StringRef TargetName = Targets[0]->getName();
282
283  std::vector<RegisterBank> Banks;
284  for (const auto &V : Records.getAllDerivedDefinitions("RegisterBank")) {
285    SmallPtrSet<const CodeGenRegisterClass *, 8> VisitedRCs;
286    RegisterBank Bank(*V);
287
288    for (const CodeGenRegisterClass *RC :
289         Bank.getExplictlySpecifiedRegisterClasses(RegisterClassHierarchy)) {
290      visitRegisterBankClasses(
291          RegisterClassHierarchy, RC, "explicit",
292          [&Bank](const CodeGenRegisterClass *RC, StringRef Kind) {
293            LLVM_DEBUG(dbgs()
294                       << "Added " << RC->getName() << "(" << Kind << ")\n");
295            Bank.addRegisterClass(RC);
296          },
297          VisitedRCs);
298    }
299
300    Banks.push_back(Bank);
301  }
302
303  // Warn about ambiguous MIR caused by register bank/class name clashes.
304  for (const auto &Class : Records.getAllDerivedDefinitions("RegisterClass")) {
305    for (const auto &Bank : Banks) {
306      if (Bank.getName().lower() == Class->getName().lower()) {
307        PrintWarning(Bank.getDef().getLoc(), "Register bank names should be "
308                                             "distinct from register classes "
309                                             "to avoid ambiguous MIR");
310        PrintNote(Bank.getDef().getLoc(), "RegisterBank was declared here");
311        PrintNote(Class->getLoc(), "RegisterClass was declared here");
312      }
313    }
314  }
315
316  emitSourceFileHeader("Register Bank Source Fragments", OS);
317  OS << "#ifdef GET_REGBANK_DECLARATIONS\n"
318     << "#undef GET_REGBANK_DECLARATIONS\n";
319  emitHeader(OS, TargetName, Banks);
320  OS << "#endif // GET_REGBANK_DECLARATIONS\n\n"
321     << "#ifdef GET_TARGET_REGBANK_CLASS\n"
322     << "#undef GET_TARGET_REGBANK_CLASS\n";
323  emitBaseClassDefinition(OS, TargetName, Banks);
324  OS << "#endif // GET_TARGET_REGBANK_CLASS\n\n"
325     << "#ifdef GET_TARGET_REGBANK_IMPL\n"
326     << "#undef GET_TARGET_REGBANK_IMPL\n";
327  emitBaseClassImplementation(OS, TargetName, Banks);
328  OS << "#endif // GET_TARGET_REGBANK_IMPL\n";
329}
330
331namespace llvm {
332
333void EmitRegisterBank(RecordKeeper &RK, raw_ostream &OS) {
334  RegisterBankEmitter(RK).run(OS);
335}
336
337} // end namespace llvm
338