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