1 //===- RegisterBankEmitter.cpp - Generate a Register Bank Desc. -*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This tablegen backend is responsible for emitting a description of a target
11 // register bank for a code generator.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "llvm/ADT/BitVector.h"
16 #include "llvm/Support/Debug.h"
17 #include "llvm/TableGen/Error.h"
18 #include "llvm/TableGen/Record.h"
19 #include "llvm/TableGen/TableGenBackend.h"
20 
21 #include "CodeGenHwModes.h"
22 #include "CodeGenRegisters.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   getExplictlySpecifiedRegisterClasses(
65       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   RecordKeeper &Records;
109   CodeGenRegBank RegisterClassHierarchy;
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)
120       : Records(R), RegisterClassHierarchy(Records, CodeGenHwModes(R)) {}
121 
122   void run(raw_ostream &OS);
123 };
124 
125 } // end anonymous namespace
126 
127 /// Emit code to declare the ID enumeration and external global instance
128 /// variables.
129 void RegisterBankEmitter::emitHeader(raw_ostream &OS,
130                                      const StringRef TargetName,
131                                      const std::vector<RegisterBank> &Banks) {
132   // <Target>RegisterBankInfo.h
133   OS << "namespace llvm {\n"
134      << "namespace " << TargetName << " {\n"
135      << "enum {\n";
136   for (const auto &Bank : Banks)
137     OS << "  " << Bank.getEnumeratorName() << ",\n";
138   OS << "  NumRegisterBanks,\n"
139      << "};\n"
140      << "} // end namespace " << TargetName << "\n"
141      << "} // end namespace llvm\n";
142 }
143 
144 /// Emit declarations of the <Target>GenRegisterBankInfo class.
145 void RegisterBankEmitter::emitBaseClassDefinition(
146     raw_ostream &OS, const StringRef TargetName,
147     const std::vector<RegisterBank> &Banks) {
148   OS << "private:\n"
149      << "  static RegisterBank *RegBanks[];\n\n"
150      << "protected:\n"
151      << "  " << TargetName << "GenRegisterBankInfo();\n"
152      << "\n";
153 }
154 
155 /// Visit each register class belonging to the given register bank.
156 ///
157 /// A class belongs to the bank iff any of these apply:
158 /// * It is explicitly specified
159 /// * It is a subclass of a class that is a member.
160 /// * It is a class containing subregisters of the registers of a class that
161 ///   is a member. This is known as a subreg-class.
162 ///
163 /// This function must be called for each explicitly specified register class.
164 ///
165 /// \param RC The register class to search.
166 /// \param Kind A debug string containing the path the visitor took to reach RC.
167 /// \param VisitFn The action to take for each class visited. It may be called
168 ///                multiple times for a given class if there are multiple paths
169 ///                to the class.
170 static void visitRegisterBankClasses(
171     CodeGenRegBank &RegisterClassHierarchy, const CodeGenRegisterClass *RC,
172     const Twine Kind,
173     std::function<void(const CodeGenRegisterClass *, StringRef)> VisitFn,
174     SmallPtrSetImpl<const CodeGenRegisterClass *> &VisitedRCs) {
175 
176   // Make sure we only visit each class once to avoid infinite loops.
177   if (VisitedRCs.count(RC))
178     return;
179   VisitedRCs.insert(RC);
180 
181   // Visit each explicitly named class.
182   VisitFn(RC, Kind.str());
183 
184   for (const auto &PossibleSubclass : RegisterClassHierarchy.getRegClasses()) {
185     std::string TmpKind =
186         (Twine(Kind) + " (" + PossibleSubclass.getName() + ")").str();
187 
188     // Visit each subclass of an explicitly named class.
189     if (RC != &PossibleSubclass && RC->hasSubClass(&PossibleSubclass))
190       visitRegisterBankClasses(RegisterClassHierarchy, &PossibleSubclass,
191                                TmpKind + " " + RC->getName() + " subclass",
192                                VisitFn, VisitedRCs);
193 
194     // Visit each class that contains only subregisters of RC with a common
195     // subregister-index.
196     //
197     // More precisely, PossibleSubclass is a subreg-class iff Reg:SubIdx is in
198     // PossibleSubclass for all registers Reg from RC using any
199     // subregister-index SubReg
200     for (const auto &SubIdx : RegisterClassHierarchy.getSubRegIndices()) {
201       BitVector BV(RegisterClassHierarchy.getRegClasses().size());
202       PossibleSubclass.getSuperRegClasses(&SubIdx, BV);
203       if (BV.test(RC->EnumValue)) {
204         std::string TmpKind2 = (Twine(TmpKind) + " " + RC->getName() +
205                                 " class-with-subregs: " + RC->getName())
206                                    .str();
207         VisitFn(&PossibleSubclass, TmpKind2);
208       }
209     }
210   }
211 }
212 
213 void RegisterBankEmitter::emitBaseClassImplementation(
214     raw_ostream &OS, StringRef TargetName,
215     std::vector<RegisterBank> &Banks) {
216 
217   OS << "namespace llvm {\n"
218      << "namespace " << TargetName << " {\n";
219   for (const auto &Bank : Banks) {
220     std::vector<std::vector<const CodeGenRegisterClass *>> RCsGroupedByWord(
221         (RegisterClassHierarchy.getRegClasses().size() + 31) / 32);
222 
223     for (const auto &RC : Bank.register_classes())
224       RCsGroupedByWord[RC->EnumValue / 32].push_back(RC);
225 
226     OS << "const uint32_t " << Bank.getCoverageArrayName() << "[] = {\n";
227     unsigned LowestIdxInWord = 0;
228     for (const auto &RCs : RCsGroupedByWord) {
229       OS << "    // " << LowestIdxInWord << "-" << (LowestIdxInWord + 31) << "\n";
230       for (const auto &RC : RCs) {
231         std::string QualifiedRegClassID =
232             (Twine(RC->Namespace) + "::" + RC->getName() + "RegClassID").str();
233         OS << "    (1u << (" << QualifiedRegClassID << " - "
234            << LowestIdxInWord << ")) |\n";
235       }
236       OS << "    0,\n";
237       LowestIdxInWord += 32;
238     }
239     OS << "};\n";
240   }
241   OS << "\n";
242 
243   for (const auto &Bank : Banks) {
244     std::string QualifiedBankID =
245         (TargetName + "::" + Bank.getEnumeratorName()).str();
246     const CodeGenRegisterClass &RC = *Bank.getRCWithLargestRegsSize();
247     unsigned Size = RC.RSI.get(DefaultMode).SpillSize;
248     OS << "RegisterBank " << Bank.getInstanceVarName() << "(/* ID */ "
249        << QualifiedBankID << ", /* Name */ \"" << Bank.getName()
250        << "\", /* Size */ " << Size << ", "
251        << "/* CoveredRegClasses */ " << Bank.getCoverageArrayName()
252        << ", /* NumRegClasses */ "
253        << RegisterClassHierarchy.getRegClasses().size() << ");\n";
254   }
255   OS << "} // end namespace " << TargetName << "\n"
256      << "\n";
257 
258   OS << "RegisterBank *" << TargetName
259      << "GenRegisterBankInfo::RegBanks[] = {\n";
260   for (const auto &Bank : Banks)
261     OS << "    &" << TargetName << "::" << Bank.getInstanceVarName() << ",\n";
262   OS << "};\n\n";
263 
264   OS << TargetName << "GenRegisterBankInfo::" << TargetName
265      << "GenRegisterBankInfo()\n"
266      << "    : RegisterBankInfo(RegBanks, " << TargetName
267      << "::NumRegisterBanks) {\n"
268      << "  // Assert that RegBank indices match their ID's\n"
269      << "#ifndef NDEBUG\n"
270      << "  unsigned Index = 0;\n"
271      << "  for (const auto &RB : RegBanks)\n"
272      << "    assert(Index++ == RB->getID() && \"Index != ID\");\n"
273      << "#endif // NDEBUG\n"
274      << "}\n"
275      << "} // end namespace llvm\n";
276 }
277 
278 void RegisterBankEmitter::run(raw_ostream &OS) {
279   std::vector<Record*> Targets = Records.getAllDerivedDefinitions("Target");
280   if (Targets.size() != 1)
281     PrintFatalError("ERROR: Too many or too few subclasses of Target defined!");
282   StringRef TargetName = Targets[0]->getName();
283 
284   std::vector<RegisterBank> Banks;
285   for (const auto &V : Records.getAllDerivedDefinitions("RegisterBank")) {
286     SmallPtrSet<const CodeGenRegisterClass *, 8> VisitedRCs;
287     RegisterBank Bank(*V);
288 
289     for (const CodeGenRegisterClass *RC :
290          Bank.getExplictlySpecifiedRegisterClasses(RegisterClassHierarchy)) {
291       visitRegisterBankClasses(
292           RegisterClassHierarchy, RC, "explicit",
293           [&Bank](const CodeGenRegisterClass *RC, StringRef Kind) {
294             DEBUG(dbgs() << "Added " << RC->getName() << "(" << Kind << ")\n");
295             Bank.addRegisterClass(RC);
296           }, VisitedRCs);
297     }
298 
299     Banks.push_back(Bank);
300   }
301 
302   // Warn about ambiguous MIR caused by register bank/class name clashes.
303   for (const auto &Class : Records.getAllDerivedDefinitions("RegisterClass")) {
304     for (const auto &Bank : Banks) {
305       if (Bank.getName().lower() == Class->getName().lower()) {
306         PrintWarning(Bank.getDef().getLoc(), "Register bank names should be "
307                                              "distinct from register classes "
308                                              "to avoid ambiguous MIR");
309         PrintNote(Bank.getDef().getLoc(), "RegisterBank was declared here");
310         PrintNote(Class->getLoc(), "RegisterClass was declared here");
311       }
312     }
313   }
314 
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