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