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