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