1//===- CodeGenRegisters.cpp - Register and RegisterClass Info -------------===//
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 file defines structures to encapsulate information gleaned from the
10// target register and register class definitions.
11//
12//===----------------------------------------------------------------------===//
13
14#include "CodeGenRegisters.h"
15#include "llvm/ADT/ArrayRef.h"
16#include "llvm/ADT/BitVector.h"
17#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/IntEqClasses.h"
19#include "llvm/ADT/PointerUnion.h"
20#include "llvm/ADT/PostOrderIterator.h"
21#include "llvm/ADT/STLExtras.h"
22#include "llvm/ADT/SetVector.h"
23#include "llvm/ADT/SmallPtrSet.h"
24#include "llvm/ADT/SmallSet.h"
25#include "llvm/ADT/SmallVector.h"
26#include "llvm/ADT/StringRef.h"
27#include "llvm/ADT/StringSet.h"
28#include "llvm/ADT/Twine.h"
29#include "llvm/Support/Debug.h"
30#include "llvm/Support/raw_ostream.h"
31#include "llvm/TableGen/Error.h"
32#include "llvm/TableGen/Record.h"
33#include "llvm/TableGen/TGTimer.h"
34#include <algorithm>
35#include <cassert>
36#include <cstdint>
37#include <iterator>
38#include <map>
39#include <queue>
40#include <string>
41#include <tuple>
42#include <utility>
43#include <vector>
44
45using namespace llvm;
46
47#define DEBUG_TYPE "regalloc-emitter"
48
49//===----------------------------------------------------------------------===//
50// CodeGenSubRegIndex
51//===----------------------------------------------------------------------===//
52
53CodeGenSubRegIndex::CodeGenSubRegIndex(const Record *R, unsigned Enum,
54 const CodeGenHwModes &CGH)
55 : TheDef(R), Name(R->getName().str()), EnumValue(Enum),
56 AllSuperRegsCovered(true), Artificial(true) {
57 if (R->getValue(Name: "Namespace"))
58 Namespace = R->getValueAsString(FieldName: "Namespace").str();
59
60 if (const Record *RV = R->getValueAsOptionalDef(FieldName: "SubRegRanges"))
61 Range = SubRegRangeByHwMode(RV, CGH);
62 if (!Range.hasDefault())
63 Range.insertSubRegRangeForMode(Mode: DefaultMode, Info: SubRegRange(R));
64}
65
66CodeGenSubRegIndex::CodeGenSubRegIndex(StringRef N, StringRef Nspace,
67 unsigned Enum)
68 : TheDef(nullptr), Name(N.str()), Namespace(Nspace.str()),
69 Range(SubRegRange(-1, -1)), EnumValue(Enum), AllSuperRegsCovered(true),
70 Artificial(true) {}
71
72std::string CodeGenSubRegIndex::getQualifiedName() const {
73 std::string N = getNamespace();
74 if (!N.empty())
75 N += "::";
76 N += getName();
77 return N;
78}
79
80void CodeGenSubRegIndex::updateComponents(CodeGenRegBank &RegBank) {
81 if (!TheDef)
82 return;
83
84 std::vector<const Record *> Comps =
85 TheDef->getValueAsListOfDefs(FieldName: "ComposedOf");
86 if (!Comps.empty()) {
87 if (Comps.size() != 2)
88 PrintFatalError(ErrorLoc: TheDef->getLoc(),
89 Msg: "ComposedOf must have exactly two entries");
90 CodeGenSubRegIndex *A = RegBank.getSubRegIdx(Comps[0]);
91 CodeGenSubRegIndex *B = RegBank.getSubRegIdx(Comps[1]);
92 CodeGenSubRegIndex *X = A->addComposite(A: B, B: this, CGH: RegBank.getHwModes());
93 if (X)
94 PrintFatalError(ErrorLoc: TheDef->getLoc(), Msg: "Ambiguous ComposedOf entries");
95 }
96
97 std::vector<const Record *> Parts =
98 TheDef->getValueAsListOfDefs(FieldName: "CoveringSubRegIndices");
99 if (!Parts.empty()) {
100 if (Parts.size() < 2)
101 PrintFatalError(ErrorLoc: TheDef->getLoc(),
102 Msg: "CoveringSubRegIndices must have two or more entries");
103 SmallVector<CodeGenSubRegIndex *, 8> IdxParts;
104 for (const Record *Part : Parts)
105 IdxParts.push_back(Elt: RegBank.getSubRegIdx(Part));
106 setConcatenationOf(IdxParts);
107 }
108}
109
110LaneBitmask CodeGenSubRegIndex::computeLaneMask() const {
111 // Already computed?
112 if (LaneMask.any())
113 return LaneMask;
114
115 // Recursion guard, shouldn't be required.
116 LaneMask = LaneBitmask::getAll();
117
118 // The lane mask is simply the union of all sub-indices.
119 LaneBitmask M;
120 for (const auto &C : Composed)
121 M |= C.second->computeLaneMask();
122 assert(M.any() && "Missing lane mask, sub-register cycle?");
123 LaneMask = M;
124 return LaneMask;
125}
126
127void CodeGenSubRegIndex::setConcatenationOf(
128 ArrayRef<CodeGenSubRegIndex *> Parts) {
129 if (ConcatenationOf.empty()) {
130 ConcatenationOf.assign(in_start: Parts.begin(), in_end: Parts.end());
131 return;
132 }
133 assert(llvm::equal(Parts, ConcatenationOf) && "parts consistent");
134}
135
136void CodeGenSubRegIndex::computeConcatTransitiveClosure() {
137 for (SmallVectorImpl<CodeGenSubRegIndex *>::iterator I =
138 ConcatenationOf.begin();
139 I != ConcatenationOf.end();
140 /*empty*/) {
141 CodeGenSubRegIndex *SubIdx = *I;
142 SubIdx->computeConcatTransitiveClosure();
143#ifndef NDEBUG
144 for (CodeGenSubRegIndex *SRI : SubIdx->ConcatenationOf)
145 assert(SRI->ConcatenationOf.empty() && "No transitive closure?");
146#endif
147
148 if (SubIdx->ConcatenationOf.empty()) {
149 ++I;
150 } else {
151 I = ConcatenationOf.erase(CI: I);
152 I = ConcatenationOf.insert(I, From: SubIdx->ConcatenationOf.begin(),
153 To: SubIdx->ConcatenationOf.end());
154 I += SubIdx->ConcatenationOf.size();
155 }
156 }
157}
158
159//===----------------------------------------------------------------------===//
160// CodeGenRegister
161//===----------------------------------------------------------------------===//
162
163CodeGenRegister::CodeGenRegister(const Record *R, unsigned Enum)
164 : TheDef(R), EnumValue(Enum),
165 CostPerUse(R->getValueAsListOfInts(FieldName: "CostPerUse")),
166 CoveredBySubRegs(R->getValueAsBit(FieldName: "CoveredBySubRegs")),
167 Constant(R->getValueAsBit(FieldName: "isConstant")), SubRegsComplete(false),
168 SuperRegsComplete(false), TopoSig(~0u) {
169 Artificial = R->getValueAsBit(FieldName: "isArtificial");
170}
171
172void CodeGenRegister::buildObjectGraph(CodeGenRegBank &RegBank) {
173 std::vector<const Record *> SRIs =
174 TheDef->getValueAsListOfDefs(FieldName: "SubRegIndices");
175 std::vector<const Record *> SRs = TheDef->getValueAsListOfDefs(FieldName: "SubRegs");
176
177 for (const auto &[SRI, SR] : zip_equal(t&: SRIs, u&: SRs)) {
178 ExplicitSubRegIndices.push_back(Elt: RegBank.getSubRegIdx(SRI));
179 ExplicitSubRegs.push_back(Elt: RegBank.getReg(SR));
180 }
181
182 // Also compute leading super-registers. Each register has a list of
183 // covered-by-subregs super-registers where it appears as the first explicit
184 // sub-register.
185 //
186 // This is used by computeSecondarySubRegs() to find candidates.
187 if (CoveredBySubRegs && !ExplicitSubRegs.empty())
188 ExplicitSubRegs.front()->LeadingSuperRegs.push_back(x: this);
189
190 // Add ad hoc alias links. This is a symmetric relationship between two
191 // registers, so build a symmetric graph by adding links in both ends.
192 for (const Record *Alias : TheDef->getValueAsListOfDefs(FieldName: "Aliases")) {
193 CodeGenRegister *Reg = RegBank.getReg(Alias);
194 ExplicitAliases.push_back(Elt: Reg);
195 Reg->ExplicitAliases.push_back(Elt: this);
196 }
197}
198
199// Inherit register units from subregisters.
200// Return true if the RegUnits changed.
201bool CodeGenRegister::inheritRegUnits(CodeGenRegBank &RegBank) {
202 bool changed = false;
203 for (const auto &[_, SR] : SubRegs) {
204 // Merge the subregister's units into this register's RegUnits.
205 changed |= (RegUnits |= SR->RegUnits);
206 }
207
208 return changed;
209}
210
211const CodeGenRegister::SubRegMap &
212CodeGenRegister::computeSubRegs(CodeGenRegBank &RegBank) {
213 // Only compute this map once.
214 if (SubRegsComplete)
215 return SubRegs;
216 SubRegsComplete = true;
217
218 HasDisjunctSubRegs = ExplicitSubRegs.size() > 1;
219
220 // First insert the explicit subregs and make sure they are fully indexed.
221 for (auto [SR, Idx] : zip_equal(t&: ExplicitSubRegs, u&: ExplicitSubRegIndices)) {
222 if (!SR->Artificial)
223 Idx->Artificial = false;
224 if (!SubRegs.try_emplace(k: Idx, args&: SR).second)
225 PrintFatalError(ErrorLoc: TheDef->getLoc(), Msg: "SubRegIndex " + Idx->getName() +
226 " appears twice in Register " +
227 getName());
228 // Map explicit sub-registers first, so the names take precedence.
229 // The inherited sub-registers are mapped below.
230 SubReg2Idx.try_emplace(Key: SR, Args&: Idx);
231 }
232
233 // Keep track of inherited subregs and how they can be reached.
234 SmallPtrSet<CodeGenRegister *, 8> Orphans;
235
236 // Clone inherited subregs and place duplicate entries in Orphans.
237 // Here the order is important - earlier subregs take precedence.
238 for (CodeGenRegister *ESR : ExplicitSubRegs) {
239 const SubRegMap &Map = ESR->computeSubRegs(RegBank);
240 HasDisjunctSubRegs |= ESR->HasDisjunctSubRegs;
241
242 for (const auto &SR : Map) {
243 if (!SubRegs.insert(x: SR).second)
244 Orphans.insert(Ptr: SR.second);
245 }
246 }
247
248 // Expand any composed subreg indices.
249 // If dsub_2 has ComposedOf = [qsub_1, dsub_0], and this register has a
250 // qsub_1 subreg, add a dsub_2 subreg. Keep growing Indices and process
251 // expanded subreg indices recursively.
252 SmallVector<CodeGenSubRegIndex *, 8> Indices = ExplicitSubRegIndices;
253 for (unsigned i = 0; i != Indices.size(); ++i) {
254 CodeGenSubRegIndex *Idx = Indices[i];
255 const CodeGenSubRegIndex::CompMap &Comps = Idx->getComposites();
256 CodeGenRegister *SR = SubRegs[Idx];
257 const SubRegMap &Map = SR->computeSubRegs(RegBank);
258
259 // Look at the possible compositions of Idx.
260 // They may not all be supported by SR.
261 for (auto [Key, Val] : Comps) {
262 SubRegMap::const_iterator SRI = Map.find(x: Key);
263 if (SRI == Map.end())
264 continue; // Idx + I->first doesn't exist in SR.
265 // Add `Val` as a name for the subreg SRI->second, assuming it is
266 // orphaned, and the name isn't already used for something else.
267 if (SubRegs.count(x: Val) || !Orphans.erase(Ptr: SRI->second))
268 continue;
269 // We found a new name for the orphaned sub-register.
270 SubRegs.try_emplace(k: Val, args: SRI->second);
271 Indices.push_back(Elt: Val);
272 }
273 }
274
275 // Now Orphans contains the inherited subregisters without a direct index.
276 // Create inferred indexes for all missing entries.
277 // Work backwards in the Indices vector in order to compose subregs bottom-up.
278 // Consider this subreg sequence:
279 //
280 // qsub_1 -> dsub_0 -> ssub_0
281 //
282 // The qsub_1 -> dsub_0 composition becomes dsub_2, so the ssub_0 register
283 // can be reached in two different ways:
284 //
285 // qsub_1 -> ssub_0
286 // dsub_2 -> ssub_0
287 //
288 // We pick the latter composition because another register may have [dsub_0,
289 // dsub_1, dsub_2] subregs without necessarily having a qsub_1 subreg. The
290 // dsub_2 -> ssub_0 composition can be shared.
291 while (!Indices.empty() && !Orphans.empty()) {
292 CodeGenSubRegIndex *Idx = Indices.pop_back_val();
293 CodeGenRegister *SR = SubRegs[Idx];
294 const SubRegMap &Map = SR->computeSubRegs(RegBank);
295 for (const auto &[SRI, SubReg] : Map)
296 if (Orphans.erase(Ptr: SubReg))
297 SubRegs[RegBank.getCompositeSubRegIndex(A: Idx, B: SRI)] = SubReg;
298 }
299
300 // Compute the inverse SubReg -> Idx map.
301 for (auto &[SRI, SubReg] : SubRegs) {
302 if (SubReg == this) {
303 ArrayRef<SMLoc> Loc;
304 if (TheDef)
305 Loc = TheDef->getLoc();
306 PrintFatalError(ErrorLoc: Loc, Msg: "Register " + getName() +
307 " has itself as a sub-register");
308 }
309
310 // Compute AllSuperRegsCovered.
311 if (!CoveredBySubRegs)
312 SRI->AllSuperRegsCovered = false;
313
314 // Ensure that every sub-register has a unique name.
315 DenseMap<const CodeGenRegister *, CodeGenSubRegIndex *>::iterator Ins =
316 SubReg2Idx.try_emplace(Key: SubReg, Args: SRI).first;
317 if (Ins->second == SRI)
318 continue;
319 // Trouble: Two different names for SubReg.second.
320 ArrayRef<SMLoc> Loc;
321 if (TheDef)
322 Loc = TheDef->getLoc();
323 PrintFatalError(ErrorLoc: Loc, Msg: "Sub-register can't have two names: " +
324 SubReg->getName() + " available as " +
325 SRI->getName() + " and " + Ins->second->getName());
326 }
327
328 // Derive possible names for sub-register concatenations from any explicit
329 // sub-registers. By doing this before computeSecondarySubRegs(), we ensure
330 // that getConcatSubRegIndex() won't invent any concatenated indices that the
331 // user already specified.
332 for (auto [Idx, SR] : enumerate(First&: ExplicitSubRegs)) {
333 if (!SR->CoveredBySubRegs || SR->Artificial)
334 continue;
335
336 // SR is composed of multiple sub-regs. Find their names in this register.
337 bool AnyArtificial = false;
338 SmallVector<CodeGenSubRegIndex *, 8> Parts;
339 for (unsigned j = 0, e = SR->ExplicitSubRegs.size(); j != e; ++j) {
340 CodeGenSubRegIndex &I = *SR->ExplicitSubRegIndices[j];
341 if (I.Artificial) {
342 AnyArtificial = true;
343 break;
344 }
345 Parts.push_back(Elt: getSubRegIndex(Reg: SR->ExplicitSubRegs[j]));
346 }
347
348 if (AnyArtificial)
349 continue;
350
351 // Offer this as an existing spelling for the concatenation of Parts.
352 ExplicitSubRegIndices[Idx]->setConcatenationOf(Parts);
353 }
354
355 // Initialize RegUnitList. Because getSubRegs is called recursively, this
356 // processes the register hierarchy in postorder.
357 if (ExplicitSubRegs.empty()) {
358 // Create one register unit per leaf register. These units correspond to the
359 // maximal cliques in the register overlap graph which is optimal.
360 RegUnits.set(RegBank.newRegUnit(R0: this));
361 } else {
362 // Inherit all sub-register units. It is good enough to look at the explicit
363 // sub-registers, the other registers won't contribute any more units.
364 for (const CodeGenRegister *SR : ExplicitSubRegs)
365 RegUnits |= SR->RegUnits;
366 }
367
368 // When there is ad hoc aliasing, we simply create one unit per edge in the
369 // undirected ad hoc aliasing graph. Technically, we could do better by
370 // identifying maximal cliques in the ad hoc graph, but cliques larger than 2
371 // are extremely rare anyway (I've never seen one), so we don't bother with
372 // the added complexity.
373 for (CodeGenRegister *AR : ExplicitAliases) {
374 // Only visit each edge once.
375 if (AR->SubRegsComplete)
376 continue;
377 // Create a RegUnit representing this alias edge, and add it to both
378 // registers.
379 unsigned Unit = RegBank.newRegUnit(R0: this, R1: AR);
380 RegUnits.set(Unit);
381 AR->RegUnits.set(Unit);
382 }
383
384 // We have now computed the native register units. More may be adopted later
385 // for balancing purposes.
386 NativeRegUnits = RegUnits;
387
388 return SubRegs;
389}
390
391// In a register that is covered by its sub-registers, try to find redundant
392// sub-registers. For example:
393//
394// QQ0 = {Q0, Q1}
395// Q0 = {D0, D1}
396// Q1 = {D2, D3}
397//
398// We can infer that D1_D2 is also a sub-register, even if it wasn't named in
399// the register definition.
400//
401// The explicitly specified registers form a tree. This function discovers
402// sub-register relationships that would force a DAG.
403//
404void CodeGenRegister::computeSecondarySubRegs(CodeGenRegBank &RegBank) {
405 SmallVector<SubRegMap::value_type, 8> NewSubRegs;
406
407 std::queue<std::pair<CodeGenSubRegIndex *, CodeGenRegister *>> SubRegQueue;
408 for (auto [SRI, SubReg] : SubRegs)
409 SubRegQueue.emplace(args: SRI, args&: SubReg);
410
411 // Look at the leading super-registers of each sub-register. Those are the
412 // candidates for new sub-registers, assuming they are fully contained in
413 // this register.
414 while (!SubRegQueue.empty()) {
415 auto [SubRegIdx, SubReg] = SubRegQueue.front();
416 SubRegQueue.pop();
417
418 const CodeGenRegister::SuperRegList &Leads = SubReg->LeadingSuperRegs;
419 for (const CodeGenRegister *Cand : Leads) {
420 // Already got this sub-register?
421 if (Cand == this || getSubRegIndex(Reg: Cand))
422 continue;
423 // Check if each component of Cand is already a sub-register.
424 assert(!Cand->ExplicitSubRegs.empty() &&
425 "Super-register has no sub-registers");
426 if (Cand->ExplicitSubRegs.size() == 1)
427 continue;
428 SmallVector<CodeGenSubRegIndex *, 8> Parts;
429 // We know that the first component is (SubRegIdx,SubReg). However we
430 // may still need to split it into smaller subregister parts.
431 assert(Cand->ExplicitSubRegs[0] == SubReg && "LeadingSuperRegs correct");
432 assert(getSubRegIndex(SubReg) == SubRegIdx && "LeadingSuperRegs correct");
433 for (CodeGenRegister *SubReg : Cand->ExplicitSubRegs) {
434 if (CodeGenSubRegIndex *SubRegIdx = getSubRegIndex(Reg: SubReg)) {
435 if (SubRegIdx->ConcatenationOf.empty())
436 Parts.push_back(Elt: SubRegIdx);
437 else
438 append_range(C&: Parts, R&: SubRegIdx->ConcatenationOf);
439 } else {
440 // Sub-register doesn't exist.
441 Parts.clear();
442 break;
443 }
444 }
445 // There is nothing to do if some Cand sub-register is not part of this
446 // register.
447 if (Parts.empty())
448 continue;
449
450 // Each part of Cand is a sub-register of this. Make the full Cand also
451 // a sub-register with a concatenated sub-register index.
452 CodeGenSubRegIndex *Concat =
453 RegBank.getConcatSubRegIndex(Parts, CGH: RegBank.getHwModes());
454 std::pair<CodeGenSubRegIndex *, CodeGenRegister *> NewSubReg = {
455 Concat, const_cast<CodeGenRegister *>(Cand)};
456
457 if (!SubRegs.insert(x&: NewSubReg).second)
458 continue;
459
460 // We inserted a new subregister.
461 NewSubRegs.push_back(Elt: NewSubReg);
462 SubRegQueue.push(x: NewSubReg);
463 SubReg2Idx.try_emplace(Key: Cand, Args&: Concat);
464 }
465 }
466
467 // Create sub-register index composition maps for the synthesized indices.
468 for (auto [NewIdx, NewSubReg] : NewSubRegs) {
469 for (auto [SRI, SubReg] : NewSubReg->SubRegs) {
470 CodeGenSubRegIndex *SubIdx = getSubRegIndex(Reg: SubReg);
471 if (!SubIdx)
472 PrintFatalError(ErrorLoc: TheDef->getLoc(), Msg: "No SubRegIndex for " +
473 SubReg->getName() + " in " +
474 getName());
475 NewIdx->addComposite(A: SRI, B: SubIdx, CGH: RegBank.getHwModes());
476 }
477 }
478}
479
480void CodeGenRegister::computeSuperRegs(CodeGenRegBank &RegBank) {
481 // Only visit each register once.
482 if (SuperRegsComplete)
483 return;
484 SuperRegsComplete = true;
485
486 // Make sure all sub-registers have been visited first, so the super-reg
487 // lists will be topologically ordered.
488 for (auto SubReg : SubRegs)
489 SubReg.second->computeSuperRegs(RegBank);
490
491 // Now add this as a super-register on all sub-registers.
492 // Also compute the TopoSigId in post-order.
493 TopoSigId Id;
494 for (auto SubReg : SubRegs) {
495 // Topological signature computed from SubIdx, TopoId(SubReg).
496 // Loops and idempotent indices have TopoSig = ~0u.
497 Id.push_back(Elt: SubReg.first->EnumValue);
498 Id.push_back(Elt: SubReg.second->TopoSig);
499
500 // Don't add duplicate entries.
501 if (!SubReg.second->SuperRegs.empty() &&
502 SubReg.second->SuperRegs.back() == this)
503 continue;
504 SubReg.second->SuperRegs.push_back(x: this);
505 }
506 TopoSig = RegBank.getTopoSig(Id);
507}
508
509void CodeGenRegister::addSubRegsPreOrder(
510 SetVector<const CodeGenRegister *> &OSet, CodeGenRegBank &RegBank) const {
511 assert(SubRegsComplete && "Must precompute sub-registers");
512 for (CodeGenRegister *SR : ExplicitSubRegs) {
513 if (OSet.insert(X: SR))
514 SR->addSubRegsPreOrder(OSet, RegBank);
515 }
516 // Add any secondary sub-registers that weren't part of the explicit tree.
517 OSet.insert_range(R: llvm::make_second_range(c: SubRegs));
518}
519
520// Get the sum of this register's unit weights.
521unsigned CodeGenRegister::getWeight(const CodeGenRegBank &RegBank) const {
522 unsigned Weight = 0;
523 for (unsigned RegUnit : RegUnits)
524 Weight += RegBank.getRegUnit(RUID: RegUnit).Weight;
525 return Weight;
526}
527
528//===----------------------------------------------------------------------===//
529// RegisterTuples
530//===----------------------------------------------------------------------===//
531
532// A RegisterTuples def is used to generate pseudo-registers from lists of
533// sub-registers. We provide a SetTheory expander class that returns the new
534// registers.
535namespace {
536
537struct TupleExpander : SetTheory::Expander {
538 // Reference to SynthDefs in the containing CodeGenRegBank, to keep track of
539 // the synthesized definitions for their lifetime.
540 std::vector<std::unique_ptr<Record>> &SynthDefs;
541
542 // Track all synthesized tuple names in order to detect duplicate definitions.
543 llvm::StringSet<> TupleNames;
544
545 TupleExpander(std::vector<std::unique_ptr<Record>> &SynthDefs)
546 : SynthDefs(SynthDefs) {}
547
548 void expand(SetTheory &ST, const Record *Def,
549 SetTheory::RecSet &Elts) override {
550 std::vector<const Record *> Indices =
551 Def->getValueAsListOfDefs(FieldName: "SubRegIndices");
552 unsigned Dim = Indices.size();
553 const ListInit *SubRegs = Def->getValueAsListInit(FieldName: "SubRegs");
554
555 // Evaluate the sub-register lists to be zipped.
556 unsigned Length = ~0u;
557 SmallVector<SetTheory::RecSet, 4> Lists(Dim);
558 for (unsigned i = 0; i != Dim; ++i) {
559 ST.evaluate(Expr: SubRegs->getElement(Idx: i), Elts&: Lists[i], Loc: Def->getLoc());
560 Length = std::min(a: Length, b: unsigned(Lists[i].size()));
561 }
562
563 if (Length == 0)
564 return;
565
566 // Precompute some types.
567 const Record *RegisterCl = Def->getRecords().getClass(Name: "Register");
568 const RecTy *RegisterRecTy = RecordRecTy::get(Class: RegisterCl);
569 std::vector<StringRef> RegNames =
570 Def->getValueAsListOfStrings(FieldName: "RegAsmNames");
571
572 // Zip them up.
573 RecordKeeper &RK = Def->getRecords();
574 for (unsigned n = 0; n != Length; ++n) {
575 std::string Name;
576 const Record *Proto = Lists[0][n];
577 std::vector<Init *> Tuple;
578 for (unsigned i = 0; i != Dim; ++i) {
579 const Record *Reg = Lists[i][n];
580 if (i)
581 Name += '_';
582 Name += Reg->getName();
583 Tuple.push_back(x: Reg->getDefInit());
584 }
585
586 // Take the cost list of the first register in the tuple.
587 const ListInit *CostList = Proto->getValueAsListInit(FieldName: "CostPerUse");
588 SmallVector<const Init *, 2> CostPerUse(CostList->getElements());
589
590 const StringInit *AsmName = StringInit::get(RK, "");
591 if (!RegNames.empty()) {
592 if (RegNames.size() <= n)
593 PrintFatalError(ErrorLoc: Def->getLoc(),
594 Msg: "Register tuple definition missing name for '" +
595 Name + "'.");
596 AsmName = StringInit::get(RK, RegNames[n]);
597 }
598
599 // Create a new Record representing the synthesized register. This record
600 // is only for consumption by CodeGenRegister, it is not added to the
601 // RecordKeeper.
602 SynthDefs.emplace_back(
603 args: std::make_unique<Record>(args&: Name, args: Def->getLoc(), args&: Def->getRecords()));
604 Record *NewReg = SynthDefs.back().get();
605 Elts.insert(X: NewReg);
606
607 // Detect duplicates among synthesized registers.
608 const auto Res = TupleNames.insert(key: NewReg->getName());
609 if (!Res.second)
610 PrintFatalError(ErrorLoc: Def->getLoc(),
611 Msg: "Register tuple redefines register '" + Name + "'.");
612
613 // Copy Proto super-classes.
614 for (const auto &[Super, Loc] : Proto->getDirectSuperClasses())
615 NewReg->addDirectSuperClass(R: Super, Range: Loc);
616
617 // Copy Proto fields.
618 for (RecordVal RV : Proto->getValues()) {
619 // Skip existing fields, like NAME.
620 if (NewReg->getValue(Name: RV.getNameInit()))
621 continue;
622
623 StringRef Field = RV.getName();
624
625 // Replace the sub-register list with Tuple.
626 if (Field == "SubRegs")
627 RV.setValue(ListInit::get(Range: Tuple, EltTy: RegisterRecTy));
628
629 if (Field == "AsmName")
630 RV.setValue(AsmName);
631
632 // CostPerUse is aggregated from all Tuple members.
633 if (Field == "CostPerUse")
634 RV.setValue(ListInit::get(Range: CostPerUse, EltTy: CostList->getElementType()));
635
636 // Composite registers are always covered by sub-registers.
637 if (Field == "CoveredBySubRegs")
638 RV.setValue(BitInit::get(RK, V: true));
639
640 // Copy fields from the RegisterTuples def.
641 if (Field == "SubRegIndices") {
642 NewReg->addValue(RV: *Def->getValue(Name: Field));
643 continue;
644 }
645
646 // Some fields get their default uninitialized value.
647 if (Field == "DwarfNumbers" || Field == "DwarfAlias" ||
648 Field == "Aliases") {
649 if (const RecordVal *DefRV = RegisterCl->getValue(Name: Field))
650 NewReg->addValue(RV: *DefRV);
651 continue;
652 }
653
654 // Everything else is copied from Proto.
655 NewReg->addValue(RV);
656 }
657 }
658 }
659};
660
661} // end anonymous namespace
662
663//===----------------------------------------------------------------------===//
664// CodeGenRegisterClass
665//===----------------------------------------------------------------------===//
666
667static void sortAndUniqueRegisters(CodeGenRegister::Vec &M) {
668 llvm::sort(C&: M, Comp: deref<std::less<>>());
669 M.erase(first: llvm::unique(R&: M, P: deref<std::equal_to<>>()), last: M.end());
670}
671
672CodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank,
673 const Record *R)
674 : TheDef(R), Name(R->getName().str()),
675 RegsWithSuperRegsTopoSigs(RegBank.getNumTopoSigs()), EnumValue(-1),
676 TSFlags(0) {
677 GeneratePressureSet = R->getValueAsBit(FieldName: "GeneratePressureSet");
678 for (const Record *Type : R->getValueAsListOfDefs(FieldName: "RegTypes"))
679 VTs.push_back(Elt: getValueTypeByHwMode(Rec: Type, CGH: RegBank.getHwModes()));
680
681 // Allocation order 0 is the full set. AltOrders provides others.
682 const SetTheory::RecVec *Elements = RegBank.getSets().expand(Set: R);
683 const ListInit *AltOrders = R->getValueAsListInit(FieldName: "AltOrders");
684 Orders.resize(new_size: 1 + AltOrders->size());
685
686 // Default allocation order always contains all registers.
687 MemberBV.resize(N: RegBank.getRegisters().size());
688 Artificial = true;
689 for (const Record *Element : *Elements) {
690 Orders[0].push_back(Elt: Element);
691 const CodeGenRegister *Reg = RegBank.getReg(Element);
692 Members.push_back(x: Reg);
693 MemberBV.set(CodeGenRegBank::getRegIndex(Reg));
694 Artificial &= Reg->Artificial;
695 if (!Reg->getSuperRegs().empty())
696 RegsWithSuperRegsTopoSigs.set(Reg->getTopoSig());
697 }
698 sortAndUniqueRegisters(M&: Members);
699
700 // Alternative allocation orders may be subsets.
701 SetTheory::RecSet Order;
702 for (auto [Idx, AltOrderElem] : enumerate(First: AltOrders->getElements())) {
703 RegBank.getSets().evaluate(Expr: AltOrderElem, Elts&: Order, Loc: R->getLoc());
704 Orders[1 + Idx].append(in_start: Order.begin(), in_end: Order.end());
705 // Verify that all altorder members are regclass members.
706 while (!Order.empty()) {
707 CodeGenRegister *Reg = RegBank.getReg(Order.back());
708 Order.pop_back();
709 if (!contains(Reg))
710 PrintFatalError(ErrorLoc: R->getLoc(), Msg: " AltOrder register " + Reg->getName() +
711 " is not a class member");
712 }
713 }
714
715 Namespace = R->getValueAsString(FieldName: "Namespace");
716
717 if (const Record *RV = R->getValueAsOptionalDef(FieldName: "RegInfos"))
718 RSI = RegSizeInfoByHwMode(RV, RegBank.getHwModes());
719 unsigned Size = R->getValueAsInt(FieldName: "Size");
720 if (!RSI.hasDefault() && Size == 0 && !VTs[0].isSimple())
721 PrintFatalError(ErrorLoc: R->getLoc(), Msg: "Impossible to determine register size");
722 if (!RSI.hasDefault()) {
723 RegSizeInfo RI;
724 RI.RegSize = RI.SpillSize =
725 Size ? Size : VTs[0].getSimple().getSizeInBits();
726 RI.SpillAlignment = R->getValueAsInt(FieldName: "Alignment");
727 RSI.insertRegSizeForMode(Mode: DefaultMode, Info: RI);
728 }
729
730 int CopyCostParsed = R->getValueAsInt(FieldName: "CopyCost");
731 Allocatable = R->getValueAsBit(FieldName: "isAllocatable");
732 AltOrderSelect = R->getValueAsString(FieldName: "AltOrderSelect");
733 int SpillStackIDParsed = R->getValueAsInt(FieldName: "SpillStackID");
734 if (!isUInt<8>(x: SpillStackIDParsed))
735 PrintFatalError(ErrorLoc: R->getLoc(), Msg: "SpillStackID out of range [0,255]");
736 SpillStackID = SpillStackIDParsed;
737 int AllocationPriority = R->getValueAsInt(FieldName: "AllocationPriority");
738 if (!isUInt<5>(x: AllocationPriority))
739 PrintFatalError(ErrorLoc: R->getLoc(), Msg: "AllocationPriority out of range [0,31]");
740 this->AllocationPriority = AllocationPriority;
741
742 GlobalPriority = R->getValueAsBit(FieldName: "GlobalPriority");
743
744 const BitsInit *TSF = R->getValueAsBitsInit(FieldName: "TSFlags");
745 TSFlags = uint8_t(*TSF->convertInitializerToInt());
746
747 // Saturate negative costs to the maximum
748 if (CopyCostParsed < 0)
749 CopyCost = std::numeric_limits<uint8_t>::max();
750 else if (!isUInt<8>(x: CopyCostParsed))
751 PrintFatalError(ErrorLoc: R->getLoc(), Msg: "'CopyCost' must be an 8-bit value");
752
753 CopyCost = CopyCostParsed;
754}
755
756// Create an inferred register class that was missing from the .td files.
757// Most properties will be inherited from the closest super-class after the
758// class structure has been computed.
759CodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank,
760 StringRef Name, Key Props)
761 : Members(*Props.Members), TheDef(nullptr), Name(Name.str()),
762 RegsWithSuperRegsTopoSigs(RegBank.getNumTopoSigs()), EnumValue(-1),
763 RSI(Props.RSI), CopyCost(0), Allocatable(true), AllocationPriority(0),
764 GlobalPriority(false), TSFlags(0), SpillStackID(0) {
765 MemberBV.resize(N: RegBank.getRegisters().size());
766 Artificial = true;
767 GeneratePressureSet = false;
768 for (const auto R : Members) {
769 MemberBV.set(CodeGenRegBank::getRegIndex(Reg: R));
770 if (!R->getSuperRegs().empty())
771 RegsWithSuperRegsTopoSigs.set(R->getTopoSig());
772 Artificial &= R->Artificial;
773 }
774}
775
776// Compute inherited properties for a synthesized register class.
777void CodeGenRegisterClass::inheritProperties(CodeGenRegBank &RegBank) {
778 assert(!getDef() && "Only synthesized classes can inherit properties");
779 assert(!SuperClasses.empty() && "Synthesized class without super class");
780
781 // The last super-class is the smallest one in topological order. Check for
782 // allocatable super-classes and inherit from the nearest allocatable one if
783 // any.
784 auto NearestAllocSCRIt =
785 find_if(Range: reverse(C&: SuperClasses),
786 P: [&](const CodeGenRegisterClass *S) { return S->Allocatable; });
787 CodeGenRegisterClass &Super = NearestAllocSCRIt == SuperClasses.rend()
788 ? *SuperClasses.back()
789 : **NearestAllocSCRIt;
790
791 // Most properties are copied directly.
792 // Exceptions are members, size, and alignment
793 Namespace = Super.Namespace;
794 VTs = Super.VTs;
795 CopyCost = Super.CopyCost;
796 Allocatable = Super.Allocatable;
797 AltOrderSelect = Super.AltOrderSelect;
798 AllocationPriority = Super.AllocationPriority;
799 GlobalPriority = Super.GlobalPriority;
800 TSFlags = Super.TSFlags;
801 SpillStackID = Super.SpillStackID;
802 GeneratePressureSet |= Super.GeneratePressureSet;
803
804 // Copy all allocation orders, filter out foreign registers from the larger
805 // super-class.
806 Orders.resize(new_size: Super.Orders.size());
807 for (auto [Idx, Outer] : enumerate(First&: Super.Orders))
808 for (const Record *Reg : Outer)
809 if (contains(RegBank.getReg(Reg)))
810 Orders[Idx].push_back(Elt: Reg);
811}
812
813bool CodeGenRegisterClass::hasType(const ValueTypeByHwMode &VT) const {
814 if (llvm::is_contained(Range: VTs, Element: VT))
815 return true;
816
817 // If VT is not identical to any of this class's types, but is a simple
818 // type, check if any of the types for this class contain it under some
819 // mode.
820 // The motivating example came from RISC-V, where (likely because of being
821 // guarded by "64-bit" predicate), the type of X5 was {*:[i64]}, but the
822 // type in GRC was {*:[i32], m1:[i64]}.
823 if (VT.isSimple()) {
824 MVT T = VT.getSimple();
825 for (const ValueTypeByHwMode &OurVT : VTs) {
826 if (llvm::is_contained(Range: llvm::make_second_range(c: OurVT), Element: T))
827 return true;
828 }
829 }
830 return false;
831}
832
833bool CodeGenRegisterClass::contains(const CodeGenRegister *Reg) const {
834 return MemberBV.test(Idx: CodeGenRegBank::getRegIndex(Reg));
835}
836
837unsigned CodeGenRegisterClass::getWeight(const CodeGenRegBank &RegBank) const {
838 if (TheDef && !TheDef->isValueUnset(FieldName: "Weight"))
839 return TheDef->getValueAsInt(FieldName: "Weight");
840
841 if (Artificial)
842 return 0;
843
844 for (const CodeGenRegister *Reg : Members) {
845 if (!Reg->Artificial)
846 return Reg->getWeight(RegBank);
847 }
848
849 return 0;
850}
851
852// This is a simple lexicographical order that can be used to search for sets.
853// It is not the same as the topological order provided by TopoOrderRC.
854bool CodeGenRegisterClass::Key::operator<(
855 const CodeGenRegisterClass::Key &B) const {
856 assert(Members && B.Members);
857
858 // Lexicographical comparison. Ignores artificial registers when asked.
859 auto IA = Members->begin(), EA = Members->end();
860 auto IB = B.Members->begin(), EB = B.Members->end();
861 for (;;) {
862 while (IgnoreArtificialMembers && IA != EA && (*IA)->Artificial)
863 ++IA;
864 while (IgnoreArtificialMembers && IB != EB && (*IB)->Artificial)
865 ++IB;
866 if (IA == EA && IB == EB)
867 break;
868 if (IA == EA || IB == EB)
869 return IA == EA;
870 if (**IA != **IB)
871 return **IA < **IB;
872 ++IA;
873 ++IB;
874 }
875 return RSI < B.RSI;
876}
877
878// Returns true if RC is a strict subclass.
879// RC is a sub-class of this class if it is a valid replacement for any
880// instruction operand where a register of this classis required. It must
881// satisfy these conditions:
882//
883// 1. All RC registers are also in this.
884// 2. The RC spill size must not be smaller than our spill size.
885// 3. RC spill alignment must be compatible with ours.
886//
887static bool testSubClass(const CodeGenRegisterClass *A,
888 const CodeGenRegisterClass *B) {
889 return A->RSI.isSubClassOf(I: B->RSI) &&
890 llvm::includes(Range1: A->getMembers(), Range2: B->getMembers(), C: deref<std::less<>>());
891}
892
893/// Sorting predicate for register classes. This provides a topological
894/// ordering that arranges all register classes before their sub-classes.
895///
896/// Register classes with the same registers, spill size, and alignment form a
897/// clique. They will be ordered alphabetically.
898///
899static bool TopoOrderRC(const CodeGenRegisterClass &A,
900 const CodeGenRegisterClass &B) {
901 if (&A == &B)
902 return false;
903
904 constexpr size_t SIZET_MAX = std::numeric_limits<size_t>::max();
905
906 // Sort in the following order:
907 // (a) first by register size in ascending order.
908 // (b) then by set size in descending order.
909 // (c) finally, by name as a tie breaker.
910 //
911 // For set size, note that the classes' allocation order may not have been
912 // computed yet, but the members set is always valid. Also, since we use
913 // std::tie() < operator for ordering, we can achieve the descending set size
914 // ordering by using (SIZET_MAX - set_size) in the std::tie.
915 return std::tuple(A.RSI, SIZET_MAX - A.getMembers().size(),
916 StringRef(A.getName())) <
917 std::tuple(B.RSI, SIZET_MAX - B.getMembers().size(),
918 StringRef(B.getName()));
919}
920
921std::string CodeGenRegisterClass::getNamespaceQualification() const {
922 return Namespace.empty() ? "" : (Namespace + "::").str();
923}
924
925std::string CodeGenRegisterClass::getQualifiedName() const {
926 return getNamespaceQualification() + getName();
927}
928
929std::string CodeGenRegisterClass::getIdName() const {
930 return getName() + "RegClassID";
931}
932
933std::string CodeGenRegisterClass::getQualifiedIdName() const {
934 return getNamespaceQualification() + getIdName();
935}
936
937// Compute sub-classes of all register classes.
938// Assume the classes are ordered topologically.
939void CodeGenRegisterClass::computeSubClasses(CodeGenRegBank &RegBank) {
940 std::list<CodeGenRegisterClass> &RegClasses = RegBank.getRegClasses();
941
942 const size_t NumRegClasses = RegClasses.size();
943 // Visit backwards so sub-classes are seen first.
944 for (auto I = RegClasses.rbegin(), E = RegClasses.rend(); I != E; ++I) {
945 CodeGenRegisterClass &RC = *I;
946 RC.SubClasses.resize(N: NumRegClasses);
947 RC.SubClasses.set(RC.EnumValue);
948 if (RC.Artificial)
949 continue;
950
951 // Normally, all subclasses have IDs >= rci, unless RC is part of a clique.
952 for (auto I2 = I.base(), E2 = RegClasses.end(); I2 != E2; ++I2) {
953 CodeGenRegisterClass &SubRC = *I2;
954 if (RC.SubClasses.test(Idx: SubRC.EnumValue))
955 continue;
956 if (!testSubClass(A: &RC, B: &SubRC))
957 continue;
958 // SubRC is a sub-class. Grap all its sub-classes so we won't have to
959 // check them again.
960 RC.SubClasses |= SubRC.SubClasses;
961 }
962
963 // Sweep up missed clique members. They will be immediately preceding RC.
964 for (auto I2 = std::next(x: I); I2 != E && testSubClass(A: &RC, B: &*I2); ++I2)
965 RC.SubClasses.set(I2->EnumValue);
966 }
967
968 // Compute the SuperClasses lists from the SubClasses vectors.
969 for (auto &RC : RegClasses) {
970 const BitVector &SC = RC.getSubClasses();
971 auto I = RegClasses.begin();
972 for (int s = 0, next_s = SC.find_first(); next_s != -1;
973 next_s = SC.find_next(Prev: s)) {
974 std::advance(i&: I, n: next_s - s);
975 s = next_s;
976 if (&*I == &RC)
977 continue;
978 I->SuperClasses.push_back(Elt: &RC);
979 }
980 }
981
982 // With the class hierarchy in place, let synthesized register classes inherit
983 // properties from their closest super-class. The iteration order here can
984 // propagate properties down multiple levels.
985 for (CodeGenRegisterClass &RC : RegClasses)
986 if (!RC.getDef())
987 RC.inheritProperties(RegBank);
988}
989
990std::optional<std::pair<CodeGenRegisterClass *, CodeGenRegisterClass *>>
991CodeGenRegisterClass::getMatchingSubClassWithSubRegs(
992 CodeGenRegBank &RegBank, const CodeGenSubRegIndex *SubIdx) const {
993 auto WeakSizeOrder = [this](const CodeGenRegisterClass *A,
994 const CodeGenRegisterClass *B) {
995 // If there are multiple, identical register classes, prefer the original
996 // register class.
997 if (A == B)
998 return false;
999 if (A->getMembers().size() == B->getMembers().size()) {
1000 if (A->getBaseClassOrder() != B->getBaseClassOrder())
1001 return A->getBaseClassOrder() > B->getBaseClassOrder();
1002 return A == this;
1003 }
1004 return A->getMembers().size() > B->getMembers().size();
1005 };
1006
1007 std::list<CodeGenRegisterClass> &RegClasses = RegBank.getRegClasses();
1008
1009 // Find all the subclasses of this one that fully support the sub-register
1010 // index and order them by size. BiggestSuperRC should always be first.
1011 CodeGenRegisterClass *BiggestSuperRegRC = getSubClassWithSubReg(SubIdx);
1012 if (!BiggestSuperRegRC)
1013 return std::nullopt;
1014 BitVector SuperRegRCsBV = BiggestSuperRegRC->getSubClasses();
1015 std::vector<CodeGenRegisterClass *> SuperRegRCs;
1016 for (auto &RC : RegClasses)
1017 if (SuperRegRCsBV[RC.EnumValue])
1018 SuperRegRCs.emplace_back(args: &RC);
1019 llvm::stable_sort(Range&: SuperRegRCs, C: WeakSizeOrder);
1020
1021 assert((SuperRegRCs.front() == BiggestSuperRegRC ||
1022 SuperRegRCs.front()->getBaseClassOrder() >
1023 BiggestSuperRegRC->getBaseClassOrder()) &&
1024 "Biggest class wasn't first");
1025
1026 // Find all the subreg classes and order them by size too.
1027 std::vector<std::pair<CodeGenRegisterClass *, BitVector>> SuperRegClasses;
1028 for (auto &RC : RegClasses) {
1029 BitVector SuperRegClassesBV(RegClasses.size());
1030 RC.getSuperRegClasses(SubIdx, Out&: SuperRegClassesBV);
1031 if (SuperRegClassesBV.any())
1032 SuperRegClasses.emplace_back(args: &RC, args&: SuperRegClassesBV);
1033 }
1034 llvm::stable_sort(Range&: SuperRegClasses,
1035 C: [&](const std::pair<CodeGenRegisterClass *, BitVector> &A,
1036 const std::pair<CodeGenRegisterClass *, BitVector> &B) {
1037 return WeakSizeOrder(A.first, B.first);
1038 });
1039
1040 // Find the biggest subclass and subreg class such that R:subidx is in the
1041 // subreg class for all R in subclass.
1042 //
1043 // For example:
1044 // All registers in X86's GR64 have a sub_32bit subregister but no class
1045 // exists that contains all the 32-bit subregisters because GR64 contains RIP
1046 // but GR32 does not contain EIP. Instead, we constrain SuperRegRC to
1047 // GR32_with_sub_8bit (which is identical to GR32_with_sub_32bit) and then,
1048 // having excluded RIP, we are able to find a SubRegRC (GR32).
1049 CodeGenRegisterClass *ChosenSuperRegClass = nullptr;
1050 CodeGenRegisterClass *SubRegRC = nullptr;
1051 for (CodeGenRegisterClass *SuperRegRC : SuperRegRCs) {
1052 for (const auto &[SuperRegClass, SuperRegClassBV] : SuperRegClasses) {
1053 if (SuperRegClassBV[SuperRegRC->EnumValue]) {
1054 SubRegRC = SuperRegClass;
1055 ChosenSuperRegClass = SuperRegRC;
1056
1057 // If SubRegRC is bigger than SuperRegRC then there are members of
1058 // SubRegRC that don't have super registers via SubIdx. Keep looking to
1059 // find a better fit and fall back on this one if there isn't one.
1060 //
1061 // This is intended to prevent X86 from making odd choices such as
1062 // picking LOW32_ADDR_ACCESS_RBP instead of GR32 in the example above.
1063 // LOW32_ADDR_ACCESS_RBP is a valid choice but contains registers that
1064 // aren't subregisters of SuperRegRC whereas GR32 has a direct 1:1
1065 // mapping.
1066 if (SuperRegRC->getMembers().size() >= SubRegRC->getMembers().size())
1067 return std::pair(ChosenSuperRegClass, SubRegRC);
1068 }
1069 }
1070
1071 // If we found a fit but it wasn't quite ideal because SubRegRC had excess
1072 // registers, then we're done.
1073 if (ChosenSuperRegClass)
1074 return std::pair(ChosenSuperRegClass, SubRegRC);
1075 }
1076
1077 return std::nullopt;
1078}
1079
1080void CodeGenRegisterClass::getSuperRegClasses(const CodeGenSubRegIndex *SubIdx,
1081 BitVector &Out) const {
1082 auto FindI = SuperRegClasses.find(Val: SubIdx);
1083 if (FindI == SuperRegClasses.end())
1084 return;
1085 for (CodeGenRegisterClass *RC : FindI->second)
1086 Out.set(RC->EnumValue);
1087}
1088
1089// Populate a unique sorted list of units from a register set.
1090void CodeGenRegisterClass::buildRegUnitSet(
1091 const CodeGenRegBank &RegBank, std::vector<unsigned> &RegUnits) const {
1092 std::vector<unsigned> TmpUnits;
1093 for (const CodeGenRegister *Reg : Members) {
1094 for (unsigned UnitI : Reg->getRegUnits()) {
1095 const RegUnit &RU = RegBank.getRegUnit(RUID: UnitI);
1096 if (!RU.Artificial)
1097 TmpUnits.push_back(x: UnitI);
1098 }
1099 }
1100 llvm::sort(C&: TmpUnits);
1101 std::unique_copy(first: TmpUnits.begin(), last: TmpUnits.end(),
1102 result: std::back_inserter(x&: RegUnits));
1103}
1104
1105// Combine our super classes of the given sub-register index with all of their
1106// super classes in turn.
1107void CodeGenRegisterClass::extendSuperRegClasses(CodeGenSubRegIndex *SubIdx) {
1108 auto It = SuperRegClasses.find(Val: SubIdx);
1109 if (It == SuperRegClasses.end())
1110 return;
1111
1112 SmallVector<CodeGenRegisterClass *> MidRCs;
1113 llvm::append_range(C&: MidRCs, R&: It->second);
1114
1115 for (CodeGenRegisterClass *MidRC : MidRCs) {
1116 for (auto &Pair : MidRC->SuperRegClasses) {
1117 CodeGenSubRegIndex *ComposedSubIdx = Pair.first->compose(Idx: SubIdx);
1118 if (!ComposedSubIdx)
1119 continue;
1120
1121 for (CodeGenRegisterClass *SuperRC : Pair.second)
1122 addSuperRegClass(SubIdx: ComposedSubIdx, SuperRC);
1123 }
1124 }
1125}
1126
1127//===----------------------------------------------------------------------===//
1128// CodeGenRegisterCategory
1129//===----------------------------------------------------------------------===//
1130
1131CodeGenRegisterCategory::CodeGenRegisterCategory(CodeGenRegBank &RegBank,
1132 const Record *R)
1133 : TheDef(R), Name(R->getName().str()) {
1134 for (const Record *RegClass : R->getValueAsListOfDefs(FieldName: "Classes"))
1135 Classes.push_back(x: RegBank.getRegClass(RegClass));
1136}
1137
1138//===----------------------------------------------------------------------===//
1139// CodeGenRegBank
1140//===----------------------------------------------------------------------===//
1141
1142CodeGenRegBank::CodeGenRegBank(const RecordKeeper &Records,
1143 const CodeGenHwModes &Modes,
1144 const bool RegistersAreIntervals)
1145 : Records(Records), CGH(Modes),
1146 RegistersAreIntervals(RegistersAreIntervals) {
1147 // Configure register Sets to understand register classes and tuples.
1148 Sets.addFieldExpander(ClassName: "RegisterClass", FieldName: "MemberList");
1149 Sets.addFieldExpander(ClassName: "CalleeSavedRegs", FieldName: "SaveList");
1150 Sets.addExpander(ClassName: "RegisterTuples",
1151 std::make_unique<TupleExpander>(args&: SynthDefs));
1152
1153 // Read in the user-defined (named) sub-register indices.
1154 // More indices will be synthesized later.
1155 for (const Record *SRI : Records.getAllDerivedDefinitions(ClassName: "SubRegIndex"))
1156 getSubRegIdx(SRI);
1157 // Build composite maps from ComposedOf fields.
1158 for (auto &Idx : SubRegIndices)
1159 Idx.updateComponents(RegBank&: *this);
1160
1161 // Read in the register and register tuple definitions.
1162 const RecordKeeper &RC = Records;
1163 std::vector<const Record *> Regs = RC.getAllDerivedDefinitions(ClassName: "Register");
1164 if (!Regs.empty() && Regs[0]->isSubClassOf(Name: "X86Reg")) {
1165 // For X86, we need to sort Registers and RegisterTuples together to list
1166 // new registers and register tuples at a later position. So that we can
1167 // reduce unnecessary iterations on unsupported registers in LiveVariables.
1168 // TODO: Remove this logic when migrate from LiveVariables to LiveIntervals
1169 // completely.
1170 for (const Record *R : Records.getAllDerivedDefinitions(ClassName: "RegisterTuples")) {
1171 // Expand tuples and merge the vectors
1172 std::vector<const Record *> TupRegs = *Sets.expand(Set: R);
1173 llvm::append_range(C&: Regs, R&: TupRegs);
1174 }
1175
1176 llvm::sort(C&: Regs, Comp: LessRecordRegister());
1177 // Assign the enumeration values.
1178 for (const Record *Reg : Regs)
1179 getReg(Reg);
1180 } else {
1181 llvm::sort(C&: Regs, Comp: LessRecordRegister());
1182 // Assign the enumeration values.
1183 for (const Record *Reg : Regs)
1184 getReg(Reg);
1185
1186 // Expand tuples and number the new registers.
1187 for (const Record *R : Records.getAllDerivedDefinitions(ClassName: "RegisterTuples")) {
1188 std::vector<const Record *> TupRegs = *Sets.expand(Set: R);
1189 llvm::sort(C&: TupRegs, Comp: LessRecordRegister());
1190 for (const Record *RC : TupRegs)
1191 getReg(RC);
1192 }
1193 }
1194
1195 // Now all the registers are known. Build the object graph of explicit
1196 // register-register references.
1197 for (CodeGenRegister &Reg : Registers)
1198 Reg.buildObjectGraph(RegBank&: *this);
1199
1200 // Compute register name map.
1201 for (CodeGenRegister &Reg : Registers)
1202 // FIXME: This could just be RegistersByName[name] = register, except that
1203 // causes some failures in MIPS - perhaps they have duplicate register name
1204 // entries? (or maybe there's a reason for it - I don't know much about this
1205 // code, just drive-by refactoring)
1206 RegistersByName.try_emplace(Key: Reg.TheDef->getValueAsString(FieldName: "AsmName"), Args: &Reg);
1207
1208 // Precompute all sub-register maps.
1209 // This will create Composite entries for all inferred sub-register indices.
1210 for (CodeGenRegister &Reg : Registers)
1211 Reg.computeSubRegs(RegBank&: *this);
1212
1213 // Compute transitive closure of subregister index ConcatenationOf vectors
1214 // and initialize ConcatIdx map.
1215 for (CodeGenSubRegIndex &SRI : SubRegIndices) {
1216 SRI.computeConcatTransitiveClosure();
1217 if (!SRI.ConcatenationOf.empty())
1218 ConcatIdx.try_emplace(
1219 k: SmallVector<CodeGenSubRegIndex *, 8>(SRI.ConcatenationOf.begin(),
1220 SRI.ConcatenationOf.end()),
1221 args: &SRI);
1222 }
1223
1224 // Infer even more sub-registers by combining leading super-registers.
1225 for (CodeGenRegister &Reg : Registers)
1226 if (Reg.CoveredBySubRegs)
1227 Reg.computeSecondarySubRegs(RegBank&: *this);
1228
1229 // After the sub-register graph is complete, compute the topologically
1230 // ordered SuperRegs list.
1231 for (CodeGenRegister &Reg : Registers)
1232 Reg.computeSuperRegs(RegBank&: *this);
1233
1234 // For each pair of Reg:SR, if both are non-artificial, mark the
1235 // corresponding sub-register index as non-artificial.
1236 for (CodeGenRegister &Reg : Registers) {
1237 if (Reg.Artificial)
1238 continue;
1239 for (auto [SRI, SR] : Reg.getSubRegs()) {
1240 if (!SR->Artificial)
1241 SRI->Artificial = false;
1242 }
1243 }
1244
1245 computeSubRegIndicesRPOT();
1246
1247 // Native register units are associated with a leaf register. They've all been
1248 // discovered now.
1249 NumNativeRegUnits = RegUnits.size();
1250
1251 // Read in register class definitions.
1252 ArrayRef<const Record *> RCs =
1253 Records.getAllDerivedDefinitions(ClassName: "RegisterClass");
1254 if (RCs.empty())
1255 PrintFatalError(Msg: "No 'RegisterClass' subclasses defined!");
1256
1257 // Allocate user-defined register classes.
1258 for (const Record *R : RCs) {
1259 RegClasses.emplace_back(args&: *this, args&: R);
1260 CodeGenRegisterClass &RC = RegClasses.back();
1261 if (!RC.Artificial)
1262 addToMaps(&RC);
1263 }
1264
1265 // Infer missing classes to create a full algebra.
1266 computeInferredRegisterClasses();
1267
1268 // Order register classes topologically and assign enum values.
1269 RegClasses.sort(comp: TopoOrderRC);
1270 for (auto [Idx, RC] : enumerate(First&: RegClasses))
1271 RC.EnumValue = Idx;
1272 CodeGenRegisterClass::computeSubClasses(RegBank&: *this);
1273
1274 // Read in the register category definitions.
1275 for (const Record *R : Records.getAllDerivedDefinitions(ClassName: "RegisterCategory"))
1276 RegCategories.emplace_back(args&: *this, args&: R);
1277}
1278
1279// Create a synthetic CodeGenSubRegIndex without a corresponding Record.
1280CodeGenSubRegIndex *CodeGenRegBank::createSubRegIndex(StringRef Name,
1281 StringRef Namespace) {
1282 SubRegIndices.emplace_back(args&: Name, args&: Namespace, args: SubRegIndices.size() + 1);
1283 return &SubRegIndices.back();
1284}
1285
1286CodeGenSubRegIndex *CodeGenRegBank::getSubRegIdx(const Record *Def) {
1287 CodeGenSubRegIndex *&Idx = Def2SubRegIdx[Def];
1288 if (Idx)
1289 return Idx;
1290 SubRegIndices.emplace_back(args&: Def, args: SubRegIndices.size() + 1, args: getHwModes());
1291 Idx = &SubRegIndices.back();
1292 return Idx;
1293}
1294
1295const CodeGenSubRegIndex *
1296CodeGenRegBank::findSubRegIdx(const Record *Def) const {
1297 return Def2SubRegIdx.at(Val: Def);
1298}
1299
1300CodeGenRegister *CodeGenRegBank::getReg(const Record *Def) {
1301 CodeGenRegister *&Reg = Def2Reg[Def];
1302 if (Reg)
1303 return Reg;
1304 Registers.emplace_back(args&: Def, args: Registers.size() + 1);
1305 Reg = &Registers.back();
1306 return Reg;
1307}
1308
1309void CodeGenRegBank::addToMaps(CodeGenRegisterClass *RC) {
1310 if (const Record *Def = RC->getDef())
1311 Def2RC.try_emplace(Key: Def, Args&: RC);
1312
1313 // Duplicate classes are rejected by insert().
1314 // That's OK, we only care about the properties handled by CGRC::Key.
1315 CodeGenRegisterClass::Key K(*RC, /*IgnoreArtificialMembers=*/true);
1316 Key2RC.try_emplace(k: K, args&: RC);
1317}
1318
1319// Create a synthetic sub-class if it is missing.
1320std::pair<CodeGenRegisterClass *, bool>
1321CodeGenRegBank::getOrCreateSubClass(const CodeGenRegisterClass *RC,
1322 const CodeGenRegister::Vec *Members,
1323 StringRef Name) {
1324 // Synthetic sub-class has the same size and alignment as RC.
1325 CodeGenRegisterClass::Key K(Members, RC->RSI,
1326 /*IgnoreArtificialMembers=*/true);
1327 RCKeyMap::const_iterator FoundI = Key2RC.find(x: K);
1328 if (FoundI != Key2RC.end())
1329 return {FoundI->second, false};
1330
1331 // Sub-class doesn't exist, create a new one.
1332 RegClasses.emplace_back(args&: *this, args&: Name, args&: K);
1333 addToMaps(RC: &RegClasses.back());
1334 return {&RegClasses.back(), true};
1335}
1336
1337CodeGenRegisterClass *CodeGenRegBank::getRegClass(const Record *Def,
1338 ArrayRef<SMLoc> Loc) const {
1339 assert(Def->isSubClassOf("RegisterClassLike"));
1340 if (CodeGenRegisterClass *RC = Def2RC.lookup(Val: Def))
1341 return RC;
1342
1343 ArrayRef<SMLoc> DiagLoc = Loc.empty() ? Def->getLoc() : Loc;
1344 // TODO: Ideally we should update the API to allow resolving HwMode.
1345 if (Def->isSubClassOf(Name: "RegClassByHwMode"))
1346 PrintError(ErrorLoc: DiagLoc, Msg: "cannot resolve HwMode for " + Def->getName());
1347 else
1348 PrintError(ErrorLoc: DiagLoc, Msg: Def->getName() + " is not a known RegisterClass!");
1349 PrintFatalNote(ErrorLoc: Def->getLoc(), Msg: Def->getName() + " defined here");
1350}
1351
1352CodeGenSubRegIndex *
1353CodeGenRegBank::getCompositeSubRegIndex(CodeGenSubRegIndex *A,
1354 CodeGenSubRegIndex *B) {
1355 // Look for an existing entry.
1356 CodeGenSubRegIndex *Comp = A->compose(Idx: B);
1357 if (Comp)
1358 return Comp;
1359
1360 // None exists, synthesize one.
1361 std::string Name = A->getName() + "_then_" + B->getName();
1362 Comp = createSubRegIndex(Name, Namespace: A->getNamespace());
1363 A->addComposite(A: B, B: Comp, CGH: getHwModes());
1364 return Comp;
1365}
1366
1367CodeGenSubRegIndex *CodeGenRegBank::getConcatSubRegIndex(
1368 const SmallVector<CodeGenSubRegIndex *, 8> &Parts,
1369 const CodeGenHwModes &CGH) {
1370 assert(Parts.size() > 1 && "Need two parts to concatenate");
1371#ifndef NDEBUG
1372 for (CodeGenSubRegIndex *Idx : Parts) {
1373 assert(Idx->ConcatenationOf.empty() && "No transitive closure?");
1374 }
1375#endif
1376
1377 // Look for an existing entry.
1378 CodeGenSubRegIndex *&Idx = ConcatIdx[Parts];
1379 if (Idx)
1380 return Idx;
1381
1382 // None exists, synthesize one.
1383 std::string Name = Parts.front()->getName();
1384 const unsigned UnknownSize = (uint32_t)-1;
1385
1386 for (const CodeGenSubRegIndex *Part : ArrayRef(Parts).drop_front()) {
1387 Name += '_';
1388 Name += Part->getName();
1389 }
1390
1391 Idx = createSubRegIndex(Name, Namespace: Parts.front()->getNamespace());
1392 Idx->ConcatenationOf.assign(in_start: Parts.begin(), in_end: Parts.end());
1393
1394 unsigned NumModes = CGH.getNumModeIds();
1395 for (unsigned M = 0; M < NumModes; ++M) {
1396 const CodeGenSubRegIndex *FirstPart = Parts.front();
1397
1398 // Determine whether all parts are contiguous.
1399 bool IsContinuous = true;
1400 const SubRegRange &FirstPartRange = FirstPart->Range.get(Mode: M);
1401 unsigned Size = FirstPartRange.Size;
1402 unsigned LastOffset = FirstPartRange.Offset;
1403 unsigned LastSize = FirstPartRange.Size;
1404
1405 for (const CodeGenSubRegIndex *Part : ArrayRef(Parts).drop_front()) {
1406 const SubRegRange &PartRange = Part->Range.get(Mode: M);
1407 if (Size == UnknownSize || PartRange.Size == UnknownSize)
1408 Size = UnknownSize;
1409 else
1410 Size += PartRange.Size;
1411 if (LastSize == UnknownSize ||
1412 PartRange.Offset != (LastOffset + LastSize))
1413 IsContinuous = false;
1414 LastOffset = PartRange.Offset;
1415 LastSize = PartRange.Size;
1416 }
1417 unsigned Offset = IsContinuous ? FirstPartRange.Offset : -1;
1418 Idx->Range.get(Mode: M) = SubRegRange(Size, Offset);
1419 }
1420
1421 return Idx;
1422}
1423
1424void CodeGenRegBank::computeComposites() {
1425 using RegMap = std::map<const CodeGenRegister *, const CodeGenRegister *>;
1426
1427 // Subreg -> { Reg->Reg }, where the right-hand side is the mapping from
1428 // register to (sub)register associated with the action of the left-hand
1429 // side subregister.
1430 std::map<const CodeGenSubRegIndex *, RegMap> SubRegAction;
1431 for (const CodeGenRegister &R : Registers) {
1432 const CodeGenRegister::SubRegMap &SM = R.getSubRegs();
1433 for (auto [SRI, SubReg] : SM)
1434 SubRegAction[SRI].try_emplace(k: &R, args&: SubReg);
1435 }
1436
1437 // Calculate the composition of two subregisters as compositions of their
1438 // associated actions.
1439 auto compose = [&SubRegAction](const CodeGenSubRegIndex *Sub1,
1440 const CodeGenSubRegIndex *Sub2) {
1441 RegMap C;
1442 const RegMap &Img1 = SubRegAction.at(k: Sub1);
1443 const RegMap &Img2 = SubRegAction.at(k: Sub2);
1444 for (auto [R, SubReg] : Img1) {
1445 auto F = Img2.find(x: SubReg);
1446 if (F != Img2.end())
1447 C.try_emplace(k: R, args: F->second);
1448 }
1449 return C;
1450 };
1451
1452 // Check if the two maps agree on the intersection of their domains.
1453 auto agree = [](const RegMap &Map1, const RegMap &Map2) {
1454 // Technically speaking, an empty map agrees with any other map, but
1455 // this could flag false positives. We're interested in non-vacuous
1456 // agreements.
1457 if (Map1.empty() || Map2.empty())
1458 return false;
1459 for (auto [K, V] : Map1) {
1460 auto F = Map2.find(x: K);
1461 if (F == Map2.end() || V != F->second)
1462 return false;
1463 }
1464 return true;
1465 };
1466
1467 using CompositePair =
1468 std::pair<const CodeGenSubRegIndex *, const CodeGenSubRegIndex *>;
1469 SmallSet<CompositePair, 4> UserDefined;
1470 for (const CodeGenSubRegIndex &Idx : SubRegIndices)
1471 for (auto P : Idx.getComposites())
1472 UserDefined.insert(V: {&Idx, P.first});
1473
1474 // Keep track of TopoSigs visited. We only need to visit each TopoSig once,
1475 // and many registers will share TopoSigs on regular architectures.
1476 BitVector TopoSigs(getNumTopoSigs());
1477
1478 for (const CodeGenRegister &Reg1 : Registers) {
1479 // Skip identical subreg structures already processed.
1480 if (TopoSigs.test(Idx: Reg1.getTopoSig()))
1481 continue;
1482 TopoSigs.set(Reg1.getTopoSig());
1483
1484 const CodeGenRegister::SubRegMap &SRM1 = Reg1.getSubRegs();
1485 for (auto [Idx1, Reg2] : SRM1) {
1486 // Ignore identity compositions.
1487 if (&Reg1 == Reg2)
1488 continue;
1489 const CodeGenRegister::SubRegMap &SRM2 = Reg2->getSubRegs();
1490 // Try composing Idx1 with another SubRegIndex.
1491 for (auto I2 : SRM2) {
1492 CodeGenSubRegIndex *Idx2 = I2.first;
1493 CodeGenRegister *Reg3 = I2.second;
1494 // Ignore identity compositions.
1495 if (Reg2 == Reg3)
1496 continue;
1497 // OK Reg1:IdxPair == Reg3. Find the index with Reg:Idx == Reg3.
1498 CodeGenSubRegIndex *Idx3 = Reg1.getSubRegIndex(Reg: Reg3);
1499 assert(Idx3 && "Sub-register doesn't have an index");
1500
1501 // Conflicting composition? Emit a warning but allow it.
1502 if (CodeGenSubRegIndex *Prev =
1503 Idx1->addComposite(A: Idx2, B: Idx3, CGH: getHwModes())) {
1504 // If the composition was not user-defined, always emit a warning.
1505 if (!UserDefined.contains(V: {Idx1, Idx2}) ||
1506 agree(compose(Idx1, Idx2), SubRegAction.at(k: Idx3)))
1507 PrintWarning(Msg: Twine("SubRegIndex ") + Idx1->getQualifiedName() +
1508 " and " + Idx2->getQualifiedName() +
1509 " compose ambiguously as " + Prev->getQualifiedName() +
1510 " or " + Idx3->getQualifiedName());
1511 }
1512 }
1513 }
1514 }
1515}
1516
1517// Compute lane masks. This is similar to register units, but at the
1518// sub-register index level. Each bit in the lane mask is like a register unit
1519// class, and two lane masks will have a bit in common if two sub-register
1520// indices overlap in some register.
1521//
1522// Conservatively share a lane mask bit if two sub-register indices overlap in
1523// some registers, but not in others. That shouldn't happen a lot.
1524void CodeGenRegBank::computeSubRegLaneMasks() {
1525 // First assign individual bits to all the leaf indices.
1526 unsigned Bit = 0;
1527 // Determine mask of lanes that cover their registers.
1528 CoveringLanes = LaneBitmask::getAll();
1529 for (CodeGenSubRegIndex &Idx : SubRegIndices) {
1530 if (Idx.getComposites().empty()) {
1531 if (Bit >= LaneBitmask::BitWidth) {
1532 PrintFatalError(
1533 Msg: Twine("Ran out of lanemask bits to represent subregister ") +
1534 Idx.getName());
1535 }
1536 Idx.LaneMask = LaneBitmask::getLane(Lane: Bit);
1537 ++Bit;
1538 } else {
1539 Idx.LaneMask = LaneBitmask::getNone();
1540 }
1541 }
1542
1543 // Compute transformation sequences for composeSubRegIndexLaneMask. The idea
1544 // here is that for each possible target subregister we look at the leafs
1545 // in the subregister graph that compose for this target and create
1546 // transformation sequences for the lanemasks. Each step in the sequence
1547 // consists of a bitmask and a bitrotate operation. As the rotation amounts
1548 // are usually the same for many subregisters we can easily combine the steps
1549 // by combining the masks.
1550 for (const CodeGenSubRegIndex &Idx : SubRegIndices) {
1551 const CodeGenSubRegIndex::CompMap &Composites = Idx.getComposites();
1552 auto &LaneTransforms = Idx.CompositionLaneMaskTransform;
1553
1554 if (Composites.empty()) {
1555 // Moving from a class with no subregisters we just had a single lane:
1556 // The subregister must be a leaf subregister and only occupies 1 bit.
1557 // Move the bit from the class without subregisters into that position.
1558 unsigned DstBit = Idx.LaneMask.getHighestLane();
1559 assert(Idx.LaneMask == LaneBitmask::getLane(DstBit) &&
1560 "Must be a leaf subregister");
1561 MaskRolPair MaskRol = {.Mask: LaneBitmask::getLane(Lane: 0), .RotateLeft: (uint8_t)DstBit};
1562 LaneTransforms.push_back(Elt: MaskRol);
1563 } else {
1564 // Go through all leaf subregisters and find the ones that compose with
1565 // Idx. These make out all possible valid bits in the lane mask we want to
1566 // transform. Looking only at the leafs ensure that only a single bit in
1567 // the mask is set.
1568 unsigned NextBit = 0;
1569 for (CodeGenSubRegIndex &Idx2 : SubRegIndices) {
1570 // Skip non-leaf subregisters.
1571 if (!Idx2.getComposites().empty())
1572 continue;
1573 // Replicate the behaviour from the lane mask generation loop above.
1574 unsigned SrcBit = NextBit;
1575 LaneBitmask SrcMask = LaneBitmask::getLane(Lane: SrcBit);
1576 if (NextBit < LaneBitmask::BitWidth - 1)
1577 ++NextBit;
1578 assert(Idx2.LaneMask == SrcMask);
1579
1580 // Get the composed subregister if there is any.
1581 auto C = Composites.find(x: &Idx2);
1582 if (C == Composites.end())
1583 continue;
1584 const CodeGenSubRegIndex *Composite = C->second;
1585 // The Composed subreg should be a leaf subreg too
1586 assert(Composite->getComposites().empty());
1587
1588 // Create Mask+Rotate operation and merge with existing ops if possible.
1589 unsigned DstBit = Composite->LaneMask.getHighestLane();
1590 int Shift = DstBit - SrcBit;
1591 uint8_t RotateLeft =
1592 Shift >= 0 ? (uint8_t)Shift : LaneBitmask::BitWidth + Shift;
1593 for (MaskRolPair &I : LaneTransforms) {
1594 if (I.RotateLeft == RotateLeft) {
1595 I.Mask |= SrcMask;
1596 SrcMask = LaneBitmask::getNone();
1597 }
1598 }
1599 if (SrcMask.any()) {
1600 MaskRolPair MaskRol = {.Mask: SrcMask, .RotateLeft: RotateLeft};
1601 LaneTransforms.push_back(Elt: MaskRol);
1602 }
1603 }
1604 }
1605
1606 // Optimize if the transformation consists of one step only: Set mask to
1607 // 0xffffffff (including some irrelevant invalid bits) so that it should
1608 // merge with more entries later while compressing the table.
1609 if (LaneTransforms.size() == 1)
1610 LaneTransforms[0].Mask = LaneBitmask::getAll();
1611
1612 // Further compression optimization: For invalid compositions resulting
1613 // in a sequence with 0 entries we can just pick any other. Choose
1614 // Mask 0xffffffff with Rotation 0.
1615 if (LaneTransforms.size() == 0) {
1616 MaskRolPair P = {.Mask: LaneBitmask::getAll(), .RotateLeft: 0};
1617 LaneTransforms.push_back(Elt: P);
1618 }
1619 }
1620
1621 // FIXME: What if ad-hoc aliasing introduces overlaps that aren't represented
1622 // by the sub-register graph? This doesn't occur in any known targets.
1623
1624 // Inherit lanes from composites.
1625 for (const CodeGenSubRegIndex &Idx : SubRegIndices) {
1626 LaneBitmask Mask = Idx.computeLaneMask();
1627 // If some super-registers without CoveredBySubRegs use this index, we can
1628 // no longer assume that the lanes are covering their registers.
1629 if (!Idx.AllSuperRegsCovered)
1630 CoveringLanes &= ~Mask;
1631 }
1632
1633 // Compute lane mask combinations for register classes.
1634 for (auto &RegClass : RegClasses) {
1635 LaneBitmask LaneMask;
1636 for (const CodeGenSubRegIndex &SubRegIndex : SubRegIndices) {
1637 if (RegClass.getSubClassWithSubReg(SubIdx: &SubRegIndex) == nullptr)
1638 continue;
1639 LaneMask |= SubRegIndex.LaneMask;
1640 }
1641
1642 // For classes without any subregisters set LaneMask to 1 instead of 0.
1643 // This makes it easier for client code to handle classes uniformly.
1644 if (LaneMask.none())
1645 LaneMask = LaneBitmask::getLane(Lane: 0);
1646
1647 RegClass.LaneMask = LaneMask;
1648 }
1649}
1650
1651namespace {
1652
1653// A directed graph on sub-register indices with a virtual source node that
1654// has an arc to all other nodes, and an arc from A to B if sub-register index
1655// B can be obtained by composing A with some other sub-register index.
1656struct SubRegIndexCompositionGraph {
1657 std::deque<CodeGenSubRegIndex> &SubRegIndices;
1658 CodeGenSubRegIndex::CompMap EntryNode;
1659
1660 SubRegIndexCompositionGraph(std::deque<CodeGenSubRegIndex> &SubRegIndices)
1661 : SubRegIndices(SubRegIndices) {
1662 for (CodeGenSubRegIndex &Idx : SubRegIndices) {
1663 EntryNode.try_emplace(k: &Idx, args: &Idx);
1664 }
1665 }
1666};
1667
1668} // namespace
1669
1670template <> struct llvm::GraphTraits<SubRegIndexCompositionGraph> {
1671 using NodeRef =
1672 PointerUnion<CodeGenSubRegIndex *, const CodeGenSubRegIndex::CompMap *>;
1673
1674 // Using a reverse iterator causes sub-register indices to appear in their
1675 // more natural order in RPOT.
1676 using CompMapIt = CodeGenSubRegIndex::CompMap::const_reverse_iterator;
1677 struct ChildIteratorType
1678 : public iterator_adaptor_base<
1679 ChildIteratorType, CompMapIt,
1680 std::iterator_traits<CompMapIt>::iterator_category, NodeRef> {
1681 ChildIteratorType(CompMapIt I)
1682 : ChildIteratorType::iterator_adaptor_base(I) {}
1683
1684 NodeRef operator*() const { return wrapped()->second; }
1685 };
1686
1687 static NodeRef getEntryNode(const SubRegIndexCompositionGraph &G) {
1688 return &G.EntryNode;
1689 }
1690
1691 static const CodeGenSubRegIndex::CompMap *children(NodeRef N) {
1692 if (auto *Idx = dyn_cast<CodeGenSubRegIndex *>(Val&: N))
1693 return &Idx->getComposites();
1694 return cast<const CodeGenSubRegIndex::CompMap *>(Val&: N);
1695 }
1696
1697 static ChildIteratorType child_begin(NodeRef N) {
1698 return ChildIteratorType(children(N)->rbegin());
1699 }
1700 static ChildIteratorType child_end(NodeRef N) {
1701 return ChildIteratorType(children(N)->rend());
1702 }
1703
1704 static auto nodes_begin(SubRegIndexCompositionGraph *G) {
1705 return G->SubRegIndices.begin();
1706 }
1707 static auto nodes_end(SubRegIndexCompositionGraph *G) {
1708 return G->SubRegIndices.end();
1709 }
1710
1711 static unsigned size(SubRegIndexCompositionGraph *G) {
1712 return G->SubRegIndices.size();
1713 }
1714};
1715
1716void CodeGenRegBank::computeSubRegIndicesRPOT() {
1717 SubRegIndexCompositionGraph G(SubRegIndices);
1718 ReversePostOrderTraversal<SubRegIndexCompositionGraph> RPOT(G);
1719 for (const auto N : RPOT) {
1720 if (auto *Idx = dyn_cast<CodeGenSubRegIndex *>(Val: N))
1721 SubRegIndicesRPOT.push_back(x: Idx);
1722 }
1723}
1724
1725namespace {
1726
1727// UberRegSet is a helper class for computeRegUnitWeights. Each UberRegSet is
1728// the transitive closure of the union of overlapping register
1729// classes. Together, the UberRegSets form a partition of the registers. If we
1730// consider overlapping register classes to be connected, then each UberRegSet
1731// is a set of connected components.
1732//
1733// An UberRegSet will likely be a horizontal slice of register names of
1734// the same width. Nontrivial subregisters should then be in a separate
1735// UberRegSet. But this property isn't required for valid computation of
1736// register unit weights.
1737//
1738// A Weight field caches the max per-register unit weight in each UberRegSet.
1739//
1740// A set of SingularDeterminants flags single units of some register in this set
1741// for which the unit weight equals the set weight. These units should not have
1742// their weight increased.
1743struct UberRegSet {
1744 CodeGenRegister::Vec Regs;
1745 unsigned Weight = 0;
1746 CodeGenRegister::RegUnitList SingularDeterminants;
1747
1748 UberRegSet() = default;
1749};
1750
1751} // end anonymous namespace
1752
1753// Partition registers into UberRegSets, where each set is the transitive
1754// closure of the union of overlapping register classes.
1755//
1756// UberRegSets[0] is a special non-allocatable set.
1757static void computeUberSets(std::vector<UberRegSet> &UberSets,
1758 std::vector<UberRegSet *> &RegSets,
1759 CodeGenRegBank &RegBank) {
1760 const auto &Registers = RegBank.getRegisters();
1761
1762 // The Register EnumValue is one greater than its index into Registers.
1763 assert(Registers.size() == Registers.back().EnumValue &&
1764 "register enum value mismatch");
1765
1766 // For simplicitly make the SetID the same as EnumValue.
1767 IntEqClasses UberSetIDs(Registers.size() + 1);
1768 BitVector AllocatableRegs(Registers.size() + 1);
1769 for (CodeGenRegisterClass &RegClass : RegBank.getRegClasses()) {
1770 if (!RegClass.Allocatable)
1771 continue;
1772
1773 // Ignore artificial registers. They may be members of register
1774 // classes that together include registers and their subregisters,
1775 // in which case it is impossible to normalize the weights of
1776 // their register units.
1777 CodeGenRegister::Vec Regs;
1778 for (const CodeGenRegister *Reg : RegClass.getMembers()) {
1779 if (!Reg->Artificial)
1780 Regs.push_back(x: Reg);
1781 }
1782
1783 if (Regs.empty())
1784 continue;
1785
1786 unsigned USetID = UberSetIDs.findLeader(a: (*Regs.begin())->EnumValue);
1787 assert(USetID && "register number 0 is invalid");
1788
1789 AllocatableRegs.set((*Regs.begin())->EnumValue);
1790 for (const CodeGenRegister *CGR : llvm::drop_begin(RangeOrContainer&: Regs)) {
1791 AllocatableRegs.set(CGR->EnumValue);
1792 UberSetIDs.join(a: USetID, b: CGR->EnumValue);
1793 }
1794 }
1795 // Combine non-allocatable regs.
1796 for (const CodeGenRegister &Reg : Registers) {
1797 unsigned RegNum = Reg.EnumValue;
1798 if (AllocatableRegs.test(Idx: RegNum))
1799 continue;
1800
1801 UberSetIDs.join(a: 0, b: RegNum);
1802 }
1803 UberSetIDs.compress();
1804
1805 // Make the first UberSet a special unallocatable set.
1806 unsigned ZeroID = UberSetIDs[0];
1807
1808 // Insert Registers into the UberSets formed by union-find.
1809 // Do not resize after this.
1810 UberSets.resize(new_size: UberSetIDs.getNumClasses());
1811 for (auto [Idx, Reg] : enumerate(First: Registers)) {
1812 unsigned USetID = UberSetIDs[Reg.EnumValue];
1813 if (!USetID)
1814 USetID = ZeroID;
1815 else if (USetID == ZeroID)
1816 USetID = 0;
1817
1818 UberRegSet *USet = &UberSets[USetID];
1819 USet->Regs.push_back(x: &Reg);
1820 RegSets[Idx] = USet;
1821 }
1822}
1823
1824// Recompute a single UberSet's weight after a change to register-unit weights.
1825static void computeUberWeight(UberRegSet &S, CodeGenRegBank &RegBank) {
1826 // Initialize all unit weights in this set, and remember the max units/reg.
1827 unsigned MaxWeight = 0;
1828 for (const CodeGenRegister *R : S.Regs) {
1829 unsigned Weight = 0;
1830 for (unsigned U : R->getRegUnits()) {
1831 if (!RegBank.getRegUnit(RUID: U).Artificial) {
1832 unsigned UWeight = RegBank.getRegUnit(RUID: U).Weight;
1833 if (!UWeight) {
1834 UWeight = 1;
1835 RegBank.increaseRegUnitWeight(RUID: U, Inc: UWeight);
1836 }
1837 Weight += UWeight;
1838 }
1839 }
1840 MaxWeight = std::max(a: MaxWeight, b: Weight);
1841 }
1842 if (S.Weight != MaxWeight) {
1843 LLVM_DEBUG({
1844 dbgs() << "UberSet Weight " << MaxWeight;
1845 for (const CodeGenRegister *R : S.Regs)
1846 dbgs() << " " << R->getName();
1847 dbgs() << '\n';
1848 });
1849 // Update the set weight.
1850 S.Weight = MaxWeight;
1851 }
1852
1853 // Find singular determinants.
1854 for (const CodeGenRegister *R : S.Regs)
1855 if (R->getRegUnits().count() == 1 && R->getWeight(RegBank) == S.Weight)
1856 S.SingularDeterminants |= R->getRegUnits();
1857}
1858
1859// Recompute each UberSet weight after changing unit weights.
1860static void computeUberWeights(MutableArrayRef<UberRegSet> UberSets,
1861 CodeGenRegBank &RegBank) {
1862 // Skip the first unallocatable set.
1863 for (UberRegSet &S : UberSets.drop_front())
1864 computeUberWeight(S, RegBank);
1865}
1866
1867// normalizeWeight is a computeRegUnitWeights helper that adjusts the weight of
1868// a register and its subregisters so that they have the same weight as their
1869// UberSet. Self-recursion processes the subregister tree in postorder so
1870// subregisters are normalized first.
1871//
1872// Side effects:
1873// - creates new adopted register units
1874// - causes superregisters to inherit adopted units
1875// - increases the weight of "singular" units
1876// - induces recomputation of UberWeights.
1877static bool normalizeWeight(CodeGenRegister *Reg,
1878 std::vector<UberRegSet> &UberSets,
1879 std::vector<UberRegSet *> &RegSets,
1880 BitVector &NormalRegs,
1881 CodeGenRegister::RegUnitList &NormalUnits,
1882 CodeGenRegBank &RegBank) {
1883 NormalRegs.resize(N: std::max(a: Reg->EnumValue + 1, b: NormalRegs.size()));
1884 if (NormalRegs.test(Idx: Reg->EnumValue))
1885 return false;
1886 NormalRegs.set(Reg->EnumValue);
1887
1888 bool Changed = false;
1889 const CodeGenRegister::SubRegMap &SRM = Reg->getSubRegs();
1890 for (auto SRI : SRM) {
1891 if (SRI.second == Reg)
1892 continue; // self-cycles happen
1893
1894 Changed |= normalizeWeight(Reg: SRI.second, UberSets, RegSets, NormalRegs,
1895 NormalUnits, RegBank);
1896 }
1897 // Postorder register normalization.
1898
1899 // Inherit register units newly adopted by subregisters. Inheriting units
1900 // only changes this register's weight, so just its own UberSet can change;
1901 // recompute only that set rather than rescanning every UberSet.
1902 if (Reg->inheritRegUnits(RegBank))
1903 computeUberWeight(S&: *RegSets[RegBank.getRegIndex(Reg)], RegBank);
1904
1905 // Check if this register is too skinny for its UberRegSet.
1906 UberRegSet *UberSet = RegSets[RegBank.getRegIndex(Reg)];
1907
1908 unsigned RegWeight = Reg->getWeight(RegBank);
1909 if (UberSet->Weight > RegWeight) {
1910 // A register unit's weight can be adjusted only if it is the singular unit
1911 // for this register, has not been used to normalize a subregister's set,
1912 // and has not already been used to singularly determine this UberRegSet.
1913 unsigned AdjustUnit = *Reg->getRegUnits().begin();
1914 if (Reg->getRegUnits().count() != 1 || NormalUnits.test(Idx: AdjustUnit) ||
1915 UberSet->SingularDeterminants.test(Idx: AdjustUnit)) {
1916 // We don't have an adjustable unit, so adopt a new one.
1917 AdjustUnit = RegBank.newRegUnit(Weight: UberSet->Weight - RegWeight);
1918 Reg->adoptRegUnit(RUID: AdjustUnit);
1919 // Adopting a unit does not immediately require recomputing set weights.
1920 } else {
1921 // Adjust the existing single unit.
1922 if (!RegBank.getRegUnit(RUID: AdjustUnit).Artificial)
1923 RegBank.increaseRegUnitWeight(RUID: AdjustUnit, Inc: UberSet->Weight - RegWeight);
1924 // The unit may be shared among sets and registers within this set.
1925 computeUberWeights(UberSets, RegBank);
1926 }
1927 Changed = true;
1928 }
1929
1930 // Mark these units normalized so superregisters can't change their weights.
1931 NormalUnits |= Reg->getRegUnits();
1932
1933 return Changed;
1934}
1935
1936// Compute a weight for each register unit created during getSubRegs.
1937//
1938// The goal is that two registers in the same class will have the same weight,
1939// where each register's weight is defined as sum of its units' weights.
1940void CodeGenRegBank::computeRegUnitWeights() {
1941 std::vector<UberRegSet> UberSets;
1942 std::vector<UberRegSet *> RegSets(Registers.size());
1943 computeUberSets(UberSets, RegSets, RegBank&: *this);
1944 // UberSets and RegSets are now immutable.
1945
1946 computeUberWeights(UberSets, RegBank&: *this);
1947
1948 // Iterate over each Register, normalizing the unit weights until reaching
1949 // a fix point.
1950 unsigned NumIters = 0;
1951 for (bool Changed = true; Changed; ++NumIters) {
1952 assert(NumIters <= NumNativeRegUnits && "Runaway register unit weights");
1953 (void)NumIters;
1954 Changed = false;
1955 for (CodeGenRegister &Reg : Registers) {
1956 CodeGenRegister::RegUnitList NormalUnits;
1957 BitVector NormalRegs;
1958 Changed |= normalizeWeight(Reg: &Reg, UberSets, RegSets, NormalRegs,
1959 NormalUnits, RegBank&: *this);
1960 }
1961 }
1962}
1963
1964// isContiguous is a enforceRegUnitIntervals helper that returns true if all
1965// units in Units form a contiguous interval.
1966static bool isContiguous(const CodeGenRegister::RegUnitList &Units) {
1967 unsigned LastUnit = Units.find_first();
1968 for (auto ThisUnit : llvm::make_range(x: ++Units.begin(), y: Units.end())) {
1969 if (ThisUnit != LastUnit + 1)
1970 return false;
1971 LastUnit = ThisUnit;
1972 }
1973 return true;
1974}
1975
1976// Enforce that all registers are intervals of regunits if the target
1977// requests this property. This will renumber regunits to ensure the
1978// interval property holds, or error out if it cannot be satisfied.
1979void CodeGenRegBank::enforceRegUnitIntervals() {
1980 if (!RegistersAreIntervals)
1981 return;
1982
1983 LLVM_DEBUG(dbgs() << "Enforcing regunit intervals for target\n");
1984 std::vector<unsigned> RegUnitRenumbering(RegUnits.size(), ~0u);
1985
1986 // RegUnits that have been renumbered from X -> Y. Y is what is marked so that
1987 // it doesn't create a chain of swaps.
1988 SparseBitVector<> DontRenumberUnits;
1989
1990 auto GetRenumberedUnit = [&](unsigned RegUnit) -> unsigned {
1991 if (unsigned RenumberedUnit = RegUnitRenumbering[RegUnit];
1992 RenumberedUnit != ~0u)
1993 return RenumberedUnit;
1994 return RegUnit;
1995 };
1996
1997 // Process registers in definition order
1998 for (CodeGenRegister &Reg : Registers) {
1999 LLVM_DEBUG(dbgs() << "Processing register " << Reg.getName() << "\n");
2000 const auto &Units = Reg.getNativeRegUnits();
2001 if (Units.empty())
2002 continue;
2003 SparseBitVector<> RenumberedUnits;
2004 // First renumber all the units for this register according to previous
2005 // renumbering.
2006 LLVM_DEBUG(dbgs() << " Original (Renumbered) units:");
2007 for (unsigned U : Units) {
2008 LLVM_DEBUG(dbgs() << " " << U << "(" << GetRenumberedUnit(U) << "), ");
2009 RenumberedUnits.set(GetRenumberedUnit(U));
2010 }
2011 LLVM_DEBUG(dbgs() << "\n");
2012
2013 unsigned LastUnit = RenumberedUnits.find_first();
2014 for (auto ThisUnit :
2015 llvm::make_range(x: ++RenumberedUnits.begin(), y: RenumberedUnits.end())) {
2016 if (ThisUnit != LastUnit + 1) {
2017 if (DontRenumberUnits.test(Idx: LastUnit + 1)) {
2018 PrintFatalError(
2019 Msg: "cannot enforce regunit intervals for register " + Reg.getName() +
2020 ": unit " + Twine(LastUnit + 1) +
2021 " (root: " + RegUnits[LastUnit + 1].Roots[0]->getName() +
2022 ") has already been renumbered and cannot be swapped");
2023 }
2024 LLVM_DEBUG(dbgs() << " Renumbering unit " << ThisUnit << " to "
2025 << (LastUnit + 1) << "\n");
2026 RegUnitRenumbering[LastUnit + 1] = ThisUnit;
2027 RegUnitRenumbering[ThisUnit] = LastUnit + 1;
2028 DontRenumberUnits.set(LastUnit + 1);
2029 ThisUnit = LastUnit + 1;
2030 }
2031 LastUnit = ThisUnit;
2032 }
2033 }
2034
2035 // Apply the renumbering to all registers
2036 for (CodeGenRegister &Reg : Registers) {
2037 CodeGenRegister::RegUnitList NewRegUnits;
2038 for (unsigned OldUnit : Reg.getRegUnits())
2039 NewRegUnits.set(GetRenumberedUnit(OldUnit));
2040 Reg.setNewRegUnits(NewRegUnits);
2041
2042 CodeGenRegister::RegUnitList NewNativeUnits;
2043 for (unsigned OldUnit : Reg.getNativeRegUnits())
2044 NewNativeUnits.set(GetRenumberedUnit(OldUnit));
2045 if (!isContiguous(Units: NewNativeUnits)) {
2046 PrintFatalError(Msg: "cannot enforce regunit intervals, final "
2047 "renumbering did not produce contiguous units "
2048 "for register " +
2049 Reg.getName() + "\n");
2050 }
2051 Reg.NativeRegUnits = NewNativeUnits;
2052 }
2053}
2054
2055// Find a set in UniqueSets with the same elements as Set.
2056// Return an iterator into UniqueSets.
2057static std::vector<RegUnitSet>::const_iterator
2058findRegUnitSet(const std::vector<RegUnitSet> &UniqueSets,
2059 const RegUnitSet &Set) {
2060 return llvm::find_if(
2061 Range: UniqueSets, P: [&Set](const RegUnitSet &I) { return I.Units == Set.Units; });
2062}
2063
2064// Return true if the RUSubSet is a subset of RUSuperSet.
2065static bool isRegUnitSubSet(const std::vector<unsigned> &RUSubSet,
2066 const std::vector<unsigned> &RUSuperSet) {
2067 return llvm::includes(Range1: RUSuperSet, Range2: RUSubSet);
2068}
2069
2070/// Iteratively prune unit sets. Prune subsets that are close to the superset,
2071/// but with one or two registers removed. We occasionally have registers like
2072/// APSR and PC thrown in with the general registers. We also see many
2073/// special-purpose register subsets, such as tail-call and Thumb
2074/// encodings. Generating all possible overlapping sets is combinatorial and
2075/// overkill for modeling pressure. Ideally we could fix this statically in
2076/// tablegen by (1) having the target define register classes that only include
2077/// the allocatable registers and marking other classes as non-allocatable and
2078/// (2) having a way to mark special purpose classes as "don't-care" classes for
2079/// the purpose of pressure. However, we make an attempt to handle targets that
2080/// are not nicely defined by merging nearly identical register unit sets
2081/// statically. This generates smaller tables. Then, dynamically, we adjust the
2082/// set limit by filtering the reserved registers.
2083///
2084/// Merge sets only if the units have the same weight. For example, on ARM,
2085/// Q-tuples with ssub index 0 include all S regs but also include D16+. We
2086/// should not expand the S set to include D regs.
2087void CodeGenRegBank::pruneUnitSets() {
2088 assert(RegClassUnitSets.empty() && "this invalidates RegClassUnitSets");
2089
2090 // Form an equivalence class of UnitSets with no significant difference.
2091 std::vector<unsigned> SuperSetIDs;
2092 unsigned EndIdx = RegUnitSets.size();
2093 for (auto [SubIdx, SubSet] : enumerate(First&: RegUnitSets)) {
2094 unsigned SuperIdx = 0;
2095 for (; SuperIdx != EndIdx; ++SuperIdx) {
2096 if (SuperIdx == SubIdx)
2097 continue;
2098
2099 unsigned UnitWeight = RegUnits[SubSet.Units[0]].Weight;
2100 const RegUnitSet &SuperSet = RegUnitSets[SuperIdx];
2101 if (isRegUnitSubSet(RUSubSet: SubSet.Units, RUSuperSet: SuperSet.Units) &&
2102 (SubSet.Units.size() + 3 > SuperSet.Units.size()) &&
2103 UnitWeight == RegUnits[SuperSet.Units[0]].Weight &&
2104 UnitWeight == RegUnits[SuperSet.Units.back()].Weight) {
2105 LLVM_DEBUG({
2106 dbgs() << "UnitSet " << SubIdx << " subsumed by " << SuperIdx << '\n';
2107 });
2108 // We can pick any of the set names for the merged set. Go for the
2109 // shortest one to avoid picking the name of one of the classes that are
2110 // artificially created by tablegen. So "FPR128_lo" instead of
2111 // "QQQQ_with_qsub3_in_FPR128_lo".
2112 if (RegUnitSets[SubIdx].Name.size() < RegUnitSets[SuperIdx].Name.size())
2113 RegUnitSets[SuperIdx].Name = RegUnitSets[SubIdx].Name;
2114 break;
2115 }
2116 }
2117 if (SuperIdx == EndIdx)
2118 SuperSetIDs.push_back(x: SubIdx);
2119 }
2120 // Populate PrunedUnitSets with each equivalence class's superset.
2121 std::vector<RegUnitSet> PrunedUnitSets;
2122 PrunedUnitSets.reserve(n: SuperSetIDs.size());
2123 for (unsigned SuperIdx : SuperSetIDs) {
2124 PrunedUnitSets.emplace_back(args&: RegUnitSets[SuperIdx].Name);
2125 PrunedUnitSets.back().Units = std::move(RegUnitSets[SuperIdx].Units);
2126 }
2127 RegUnitSets = std::move(PrunedUnitSets);
2128}
2129
2130// Create a RegUnitSet for each RegClass that contains all units in the class
2131// including adopted units that are necessary to model register pressure. Then
2132// iteratively compute RegUnitSets such that the union of any two overlapping
2133// RegUnitSets is represented.
2134//
2135// RegisterInfoEmitter will map each RegClass to its RegUnitClass and any
2136// RegUnitSet that is a superset of that RegUnitClass.
2137void CodeGenRegBank::computeRegUnitSets() {
2138 assert(RegUnitSets.empty() && "dirty RegUnitSets");
2139
2140#ifndef NDEBUG
2141 // Helper to print register unit sets.
2142 auto PrintRegUnitSets = [this]() {
2143 for (auto [USIdx, US] : enumerate(RegUnitSets)) {
2144 dbgs() << "UnitSet " << USIdx << " " << US.Name << ":";
2145 printRegUnitNames(US.Units);
2146 }
2147 };
2148#endif // NDEBUG
2149
2150 // Compute a unique RegUnitSet for each RegClass.
2151 auto &RegClasses = getRegClasses();
2152 for (CodeGenRegisterClass &RC : RegClasses) {
2153 if (!RC.Allocatable || RC.Artificial || !RC.GeneratePressureSet)
2154 continue;
2155
2156 // Compute a sorted list of units in this class.
2157 RegUnitSet RUSet(RC.getName());
2158 RC.buildRegUnitSet(RegBank: *this, RegUnits&: RUSet.Units);
2159
2160 // Find an existing RegUnitSet.
2161 if (findRegUnitSet(UniqueSets: RegUnitSets, Set: RUSet) == RegUnitSets.end())
2162 RegUnitSets.push_back(x: std::move(RUSet));
2163 }
2164
2165 if (RegUnitSets.empty())
2166 PrintFatalError(Msg: "RegUnitSets cannot be empty!");
2167
2168 LLVM_DEBUG({
2169 dbgs() << "\nBefore pruning:\n";
2170 PrintRegUnitSets();
2171 });
2172
2173 // Iteratively prune unit sets.
2174 pruneUnitSets();
2175
2176 LLVM_DEBUG({
2177 dbgs() << "\nBefore union:\n";
2178 PrintRegUnitSets();
2179 dbgs() << "\nUnion sets:\n";
2180 });
2181
2182 // Iterate over all unit sets, including new ones added by this loop.
2183 // FIXME: Since `EndIdx` is computed just once during loop initialization,
2184 // does this really iterate over new unit sets added by this loop?
2185 unsigned NumRegUnitSubSets = RegUnitSets.size();
2186 for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx) {
2187 // In theory, this is combinatorial. In practice, it needs to be bounded
2188 // by a small number of sets for regpressure to be efficient.
2189 // If the assert is hit, we need to implement pruning.
2190 assert(Idx < (2 * NumRegUnitSubSets) && "runaway unit set inference");
2191
2192 // Compare new sets with all original classes.
2193 for (unsigned SearchIdx = (Idx >= NumRegUnitSubSets) ? 0 : Idx + 1;
2194 SearchIdx != EndIdx; ++SearchIdx) {
2195 std::vector<unsigned> Intersection;
2196 std::set_intersection(
2197 first1: RegUnitSets[Idx].Units.begin(), last1: RegUnitSets[Idx].Units.end(),
2198 first2: RegUnitSets[SearchIdx].Units.begin(),
2199 last2: RegUnitSets[SearchIdx].Units.end(), result: std::back_inserter(x&: Intersection));
2200 if (Intersection.empty())
2201 continue;
2202
2203 RegUnitSet RUSet(RegUnitSets[Idx].Name + "_with_" +
2204 RegUnitSets[SearchIdx].Name);
2205 std::set_union(first1: RegUnitSets[Idx].Units.begin(),
2206 last1: RegUnitSets[Idx].Units.end(),
2207 first2: RegUnitSets[SearchIdx].Units.begin(),
2208 last2: RegUnitSets[SearchIdx].Units.end(),
2209 result: std::inserter(x&: RUSet.Units, i: RUSet.Units.begin()));
2210
2211 // Find an existing RegUnitSet, or add the union to the unique sets.
2212 if (findRegUnitSet(UniqueSets: RegUnitSets, Set: RUSet) == RegUnitSets.end()) {
2213 LLVM_DEBUG({
2214 dbgs() << "UnitSet " << RegUnitSets.size() << " " << RUSet.Name
2215 << ":";
2216 printRegUnitNames(RUSet.Units);
2217 });
2218 RegUnitSets.push_back(x: std::move(RUSet));
2219 }
2220 }
2221 }
2222
2223 // Iteratively prune unit sets after inferring supersets.
2224 pruneUnitSets();
2225
2226 LLVM_DEBUG({
2227 dbgs() << '\n';
2228 PrintRegUnitSets();
2229 });
2230
2231 // For each register class, list the UnitSets that are supersets.
2232 RegClassUnitSets.resize(new_size: RegClasses.size());
2233 for (CodeGenRegisterClass &RC : RegClasses) {
2234 if (!RC.Allocatable)
2235 continue;
2236
2237 // Recompute the sorted list of units in this class.
2238 std::vector<unsigned> RCRegUnits;
2239 RC.buildRegUnitSet(RegBank: *this, RegUnits&: RCRegUnits);
2240
2241 // Don't increase pressure for unallocatable regclasses.
2242 if (RCRegUnits.empty())
2243 continue;
2244
2245 LLVM_DEBUG({
2246 dbgs() << "RC " << RC.getName() << " Units:\n";
2247 printRegUnitNames(RCRegUnits);
2248 dbgs() << "UnitSetIDs:";
2249 });
2250
2251 // Find all supersets.
2252 for (const auto &[USIdx, Set] : enumerate(First&: RegUnitSets)) {
2253 if (isRegUnitSubSet(RUSubSet: RCRegUnits, RUSuperSet: Set.Units)) {
2254 LLVM_DEBUG(dbgs() << " " << USIdx);
2255 RegClassUnitSets[RC.EnumValue].push_back(x: USIdx);
2256 }
2257 }
2258 LLVM_DEBUG(dbgs() << '\n');
2259 assert(
2260 (!RegClassUnitSets[RC.EnumValue].empty() || !RC.GeneratePressureSet) &&
2261 "missing unit set for regclass");
2262 }
2263
2264 // For each register unit, ensure that we have the list of UnitSets that
2265 // contain the unit. Normally, this matches an existing list of UnitSets for a
2266 // register class. If not, we create a new entry in RegClassUnitSets as a
2267 // "fake" register class.
2268 for (unsigned UnitIdx = 0, UnitEnd = NumNativeRegUnits; UnitIdx < UnitEnd;
2269 ++UnitIdx) {
2270 std::vector<unsigned> RUSets;
2271 for (auto [Idx, S] : enumerate(First&: RegUnitSets))
2272 if (is_contained(Range&: S.Units, Element: UnitIdx))
2273 RUSets.push_back(x: Idx);
2274
2275 unsigned RCUnitSetsIdx = 0;
2276 for (unsigned e = RegClassUnitSets.size(); RCUnitSetsIdx != e;
2277 ++RCUnitSetsIdx) {
2278 if (RegClassUnitSets[RCUnitSetsIdx] == RUSets) {
2279 break;
2280 }
2281 }
2282 RegUnits[UnitIdx].RegClassUnitSetsIdx = RCUnitSetsIdx;
2283 if (RCUnitSetsIdx == RegClassUnitSets.size()) {
2284 // Create a new list of UnitSets as a "fake" register class.
2285 RegClassUnitSets.push_back(x: std::move(RUSets));
2286 }
2287 }
2288}
2289
2290void CodeGenRegBank::computeRegUnitLaneMasks() {
2291 for (CodeGenRegister &Register : Registers) {
2292 // Create an initial lane mask for all register units.
2293 const auto &RegUnits = Register.getRegUnits();
2294 CodeGenRegister::RegUnitLaneMaskList RegUnitLaneMasks(
2295 RegUnits.count(), LaneBitmask::getAll());
2296 // Iterate through SubRegisters.
2297 using SubRegMap = CodeGenRegister::SubRegMap;
2298 const SubRegMap &SubRegs = Register.getSubRegs();
2299 for (auto [SubRegIndex, SubReg] : SubRegs) {
2300 // Ignore non-leaf subregisters, their lane masks are fully covered by
2301 // the leaf subregisters anyway.
2302 if (!SubReg->getSubRegs().empty())
2303 continue;
2304 LaneBitmask LaneMask = SubRegIndex->LaneMask;
2305 // Distribute LaneMask to Register Units touched.
2306 for (unsigned SUI : SubReg->getRegUnits()) {
2307 bool Found = false;
2308 unsigned u = 0;
2309 for (unsigned RU : RegUnits) {
2310 if (SUI == RU) {
2311 RegUnitLaneMasks[u] &= LaneMask;
2312 assert(!Found);
2313 Found = true;
2314 }
2315 ++u;
2316 }
2317 (void)Found;
2318 assert(Found);
2319 }
2320 }
2321 Register.setRegUnitLaneMasks(RegUnitLaneMasks);
2322 }
2323}
2324
2325void CodeGenRegBank::computeDerivedInfo() {
2326 computeComposites();
2327 computeSubRegLaneMasks();
2328
2329 // Compute a weight for each register unit created during getSubRegs.
2330 // This may create adopted register units (with unit # >= NumNativeRegUnits).
2331 Records.getTimer().startTimer(Name: "Compute reg unit weights");
2332 computeRegUnitWeights();
2333 Records.getTimer().stopTimer();
2334
2335 // Enforce regunit intervals if requested by the target.
2336 Records.getTimer().startTimer(Name: "Enforce regunit intervals");
2337 enforceRegUnitIntervals();
2338 Records.getTimer().stopTimer();
2339
2340 // Compute a unique set of RegUnitSets. One for each RegClass and inferred
2341 // supersets for the union of overlapping sets.
2342 computeRegUnitSets();
2343
2344 computeRegUnitLaneMasks();
2345
2346 // Compute register class HasDisjunctSubRegs/CoveredBySubRegs flag.
2347 for (CodeGenRegisterClass &RC : RegClasses) {
2348 RC.HasDisjunctSubRegs = false;
2349 RC.CoveredBySubRegs = true;
2350 for (const CodeGenRegister *Reg : RC.getMembers()) {
2351 RC.HasDisjunctSubRegs |= Reg->HasDisjunctSubRegs;
2352 RC.CoveredBySubRegs &= Reg->CoveredBySubRegs;
2353 }
2354 }
2355
2356 // Get the weight of each set.
2357 for (auto [Idx, US] : enumerate(First&: RegUnitSets))
2358 RegUnitSets[Idx].Weight = getRegUnitSetWeight(Units: US.Units);
2359
2360 // Find the order of each set.
2361 RegUnitSetOrder.reserve(n: RegUnitSets.size());
2362 for (unsigned Idx : seq<unsigned>(Size: RegUnitSets.size()))
2363 RegUnitSetOrder.push_back(x: Idx);
2364
2365 llvm::stable_sort(Range&: RegUnitSetOrder, C: [this](unsigned ID1, unsigned ID2) {
2366 return getRegPressureSet(Idx: ID1).Units.size() <
2367 getRegPressureSet(Idx: ID2).Units.size();
2368 });
2369 for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx)
2370 RegUnitSets[RegUnitSetOrder[Idx]].Order = Idx;
2371}
2372
2373//
2374// Synthesize missing register class intersections.
2375//
2376// Make sure that sub-classes of RC exists such that getCommonSubClass(RC, X)
2377// returns a maximal register class for all X.
2378//
2379void CodeGenRegBank::inferCommonSubClass(CodeGenRegisterClass *RC) {
2380 assert(!RegClasses.empty());
2381 // Stash the iterator to the last element so that this loop doesn't visit
2382 // elements added by the getOrCreateSubClass call within it.
2383 for (auto I = RegClasses.begin(), E = std::prev(x: RegClasses.end());
2384 I != std::next(x: E); ++I) {
2385 CodeGenRegisterClass *RC1 = RC;
2386 CodeGenRegisterClass *RC2 = &*I;
2387 if (RC1 == RC2)
2388 continue;
2389
2390 // Compute the set intersection of RC1 and RC2.
2391 const CodeGenRegister::Vec &Memb1 = RC1->getMembers();
2392 const CodeGenRegister::Vec &Memb2 = RC2->getMembers();
2393 CodeGenRegister::Vec Intersection;
2394 std::set_intersection(first1: Memb1.begin(), last1: Memb1.end(), first2: Memb2.begin(),
2395 last2: Memb2.end(),
2396 result: std::inserter(x&: Intersection, i: Intersection.begin()),
2397 comp: deref<std::less<>>());
2398
2399 // Skip disjoint class pairs.
2400 if (Intersection.empty())
2401 continue;
2402
2403 // Skip casses where the intersection is composed of artificial
2404 // registers.
2405 if (llvm::all_of(Range&: Intersection, P: [](const CodeGenRegister *Reg) {
2406 return Reg->Artificial;
2407 }))
2408 continue;
2409
2410 // If RC1 and RC2 have different spill sizes or alignments, use the
2411 // stricter one for sub-classing. If they are equal, prefer RC1.
2412 if (RC2->RSI.hasStricterSpillThan(I: RC1->RSI))
2413 std::swap(a&: RC1, b&: RC2);
2414
2415 getOrCreateSubClass(RC: RC1, Members: &Intersection,
2416 Name: RC1->getName() + "_and_" + RC2->getName());
2417 }
2418}
2419
2420//
2421// Synthesize missing sub-classes for getSubClassWithSubReg().
2422//
2423// Make sure that the set of registers in RC with a given SubIdx sub-register
2424// form a register class. Update RC->SubClassWithSubReg.
2425//
2426void CodeGenRegBank::inferSubClassWithSubReg(CodeGenRegisterClass *RC) {
2427 // Map SubRegIndex to set of registers in RC supporting that SubRegIndex.
2428 using SubReg2SetMap = std::map<const CodeGenSubRegIndex *,
2429 CodeGenRegister::Vec, deref<std::less<>>>;
2430
2431 // Compute the set of registers supporting each SubRegIndex.
2432 SubReg2SetMap SRSets;
2433 for (const CodeGenRegister *R : RC->getMembers()) {
2434 if (R->Artificial)
2435 continue;
2436 const CodeGenRegister::SubRegMap &SRM = R->getSubRegs();
2437 for (auto [I, _] : SRM)
2438 SRSets[I].push_back(x: R);
2439 }
2440
2441 // Find matching classes for all SRSets entries. Iterate in SubRegIndex
2442 // numerical order to visit synthetic indices last.
2443 for (const CodeGenSubRegIndex &SubIdx : SubRegIndices) {
2444 SubReg2SetMap::const_iterator I = SRSets.find(x: &SubIdx);
2445 // Unsupported SubRegIndex. Skip it.
2446 if (I == SRSets.end())
2447 continue;
2448 // In most cases, all RC registers support the SubRegIndex.
2449 auto IsNotArtificial = [](const CodeGenRegister *R) {
2450 return !R->Artificial;
2451 };
2452 if (I->second.size() ==
2453 (size_t)count_if(Range: RC->getMembers(), P: IsNotArtificial)) {
2454 RC->setSubClassWithSubReg(SubIdx: &SubIdx, SubRC: RC);
2455 continue;
2456 }
2457 if (SubIdx.Artificial)
2458 continue;
2459 // This is a real subset. See if we have a matching class.
2460 CodeGenRegisterClass *SubRC =
2461 getOrCreateSubClass(RC, Members: &I->second,
2462 Name: RC->getName() + "_with_" + I->first->getName())
2463 .first;
2464 RC->setSubClassWithSubReg(SubIdx: &SubIdx, SubRC);
2465 }
2466}
2467
2468//
2469// Synthesize missing sub-classes of RC for getMatchingSuperRegClass().
2470//
2471// Create sub-classes of RC such that getMatchingSuperRegClass(RC, SubIdx, X)
2472// has a maximal result for any SubIdx and any X >= FirstSubRegRC.
2473//
2474
2475void CodeGenRegBank::inferMatchingSuperRegClass(
2476 CodeGenRegisterClass *RC,
2477 std::list<CodeGenRegisterClass>::iterator FirstSubRegRC) {
2478 DenseSet<const CodeGenSubRegIndex *> ImpliedSubRegIndices;
2479 std::vector<const CodeGenRegister *> SubRegs;
2480 BitVector TopoSigs(getNumTopoSigs());
2481
2482 // Iterate subregister indices in topological order to visit larger indices
2483 // first. This allows us to skip the smaller indices in many cases because
2484 // their inferred super-register classes are implied.
2485 for (CodeGenSubRegIndex *SubIdx : SubRegIndicesRPOT) {
2486 // Skip indexes that aren't fully supported by RC's registers. This was
2487 // computed by inferSubClassWithSubReg() above which should have been
2488 // called first.
2489 if (RC->getSubClassWithSubReg(SubIdx) != RC)
2490 continue;
2491
2492 if (ImpliedSubRegIndices.contains(V: SubIdx))
2493 continue;
2494
2495 // Build list of (Sub, Super) pairs for this SubIdx, sorted by Sub. Note
2496 // that the list may contain entries with the same Sub but different Supers.
2497 SubRegs.clear();
2498 TopoSigs.reset();
2499 for (const CodeGenRegister *Super : RC->getMembers()) {
2500 if (Super->Artificial)
2501 continue;
2502 const CodeGenRegister *Sub = Super->getSubRegs().find(x: SubIdx)->second;
2503 assert(Sub && "Missing sub-register");
2504 SubRegs.push_back(x: Sub);
2505 TopoSigs.set(Sub->getTopoSig());
2506 }
2507
2508 // Iterate over sub-register class candidates. Ignore classes created by
2509 // this loop. They will never be useful.
2510 // Store an iterator to the last element (not end) so that this loop doesn't
2511 // visit newly inserted elements.
2512 assert(!RegClasses.empty());
2513 for (auto I = FirstSubRegRC, E = std::prev(x: RegClasses.end());
2514 I != std::next(x: E); ++I) {
2515 CodeGenRegisterClass &SubRC = *I;
2516 if (SubRC.Artificial)
2517 continue;
2518 // Topological shortcut: SubRC members have the wrong shape.
2519 if (!TopoSigs.anyCommon(RHS: SubRC.getRegsWithSuperRegsTopoSigs()))
2520 continue;
2521 // Compute the subset of RC that maps into SubRC.
2522 CodeGenRegister::Vec SubSetVec;
2523 auto IsNotArtificial = [](const CodeGenRegister *R) {
2524 return !R->Artificial;
2525 };
2526 auto NonArtificialMembers =
2527 make_filter_range(Range: RC->getMembers(), Pred: IsNotArtificial);
2528 for (const auto &[Sub, Super] :
2529 zip_equal(t&: SubRegs, u&: NonArtificialMembers)) {
2530 if (SubRC.contains(Reg: Sub))
2531 SubSetVec.push_back(x: Super);
2532 }
2533
2534 if (SubSetVec.empty())
2535 continue;
2536
2537 // RC injects completely into SubRC.
2538 if (SubSetVec.size() ==
2539 (size_t)count_if(Range: RC->getMembers(), P: IsNotArtificial)) {
2540 SubRC.addSuperRegClass(SubIdx, SuperRC: RC);
2541
2542 // We can skip checking subregister indices that can be composed from
2543 // the current SubIdx.
2544 //
2545 // Proof sketch: Let SubRC' be another register class and SubSubIdx
2546 // a subregister index that can be composed from SubIdx.
2547 //
2548 // Calling this function with SubRC in place of RC ensures the existence
2549 // of a subclass X of SubRC with the registers that have subregisters in
2550 // SubRC'.
2551 //
2552 // The set of registers in RC with SubSubIdx in SubRC' is equal to the
2553 // set of registers in RC with SubIdx in X (because every register in
2554 // RC has a corresponding subregister in SubRC), and so checking the
2555 // pair (SubSubIdx, SubRC') is redundant with checking (SubIdx, X).
2556 for (const auto &SubSubIdx : SubIdx->getComposites())
2557 ImpliedSubRegIndices.insert(V: SubSubIdx.second);
2558
2559 continue;
2560 }
2561
2562 // Only a subset of RC maps into SubRC. Make sure it is represented by a
2563 // class.
2564 //
2565 // The name of the inferred register class follows the template
2566 // "<RC>_with_<SubIdx>_in_<SubRC>".
2567 //
2568 // When SubRC is already an inferred class, prefer a name of the form
2569 // "<RC>_with_<CompositeSubIdx>_in_<SubSubRC>" over a chain of the form
2570 // "<RC>_with_<SubIdx>_in_<OtherRc>_with_<SubSubIdx>_in_<SubSubRC>".
2571 CodeGenSubRegIndex *CompositeSubIdx = SubIdx;
2572 CodeGenRegisterClass *CompositeSubRC = &SubRC;
2573 if (CodeGenSubRegIndex *SubSubIdx = SubRC.getInferredFromSubRegIdx()) {
2574 auto It = SubIdx->getComposites().find(x: SubSubIdx);
2575 if (It != SubIdx->getComposites().end()) {
2576 CompositeSubIdx = It->second;
2577 CompositeSubRC = SubRC.getInferredFromRC();
2578 }
2579 }
2580
2581 auto [SubSetRC, Inserted] = getOrCreateSubClass(
2582 RC, Members: &SubSetVec,
2583 Name: RC->getName() + "_with_" + CompositeSubIdx->getName() + "_in_" +
2584 CompositeSubRC->getName());
2585
2586 if (Inserted)
2587 SubSetRC->setInferredFrom(Idx: CompositeSubIdx, RC: CompositeSubRC);
2588 }
2589 }
2590}
2591
2592//
2593// Infer missing register classes.
2594//
2595void CodeGenRegBank::computeInferredRegisterClasses() {
2596 assert(!RegClasses.empty());
2597 // When this function is called, the register classes have not been sorted
2598 // and assigned EnumValues yet. That means getSubClasses(),
2599 // getSuperClasses(), and hasSubClass() functions are defunct.
2600
2601 Records.getTimer().startTimer(Name: "Compute inferred register classes");
2602
2603 // Use one-before-the-end so it doesn't move forward when new elements are
2604 // added.
2605 auto FirstNewRC = std::prev(x: RegClasses.end());
2606
2607 // Visit all register classes, including the ones being added by the loop.
2608 // Watch out for iterator invalidation here.
2609 for (auto I = RegClasses.begin(), E = RegClasses.end(); I != E; ++I) {
2610 CodeGenRegisterClass *RC = &*I;
2611 if (RC->Artificial)
2612 continue;
2613
2614 // Synthesize answers for getSubClassWithSubReg().
2615 inferSubClassWithSubReg(RC);
2616
2617 // Synthesize answers for getCommonSubClass().
2618 inferCommonSubClass(RC);
2619
2620 // Synthesize answers for getMatchingSuperRegClass().
2621 inferMatchingSuperRegClass(RC);
2622
2623 // New register classes are created while this loop is running, and we need
2624 // to visit all of them. In particular, inferMatchingSuperRegClass needs
2625 // to match old super-register classes with sub-register classes created
2626 // after inferMatchingSuperRegClass was called. At this point,
2627 // inferMatchingSuperRegClass has checked SuperRC = [0..rci] with SubRC =
2628 // [0..FirstNewRC). We need to cover SubRC = [FirstNewRC..rci].
2629 if (I == FirstNewRC) {
2630 auto NextNewRC = std::prev(x: RegClasses.end());
2631 for (auto I2 = RegClasses.begin(), E2 = std::next(x: FirstNewRC); I2 != E2;
2632 ++I2)
2633 inferMatchingSuperRegClass(RC: &*I2, FirstSubRegRC: E2);
2634 FirstNewRC = NextNewRC;
2635 }
2636 }
2637
2638 Records.getTimer().startTimer(Name: "Extend super-register classes");
2639
2640 // Compute the transitive closure for super-register classes.
2641 //
2642 // By iterating over sub-register indices in topological order, we only ever
2643 // add super-register classes for sub-register indices that have not already
2644 // been visited. That allows computing the transitive closure in a single
2645 // pass.
2646 for (CodeGenSubRegIndex *SubIdx : SubRegIndicesRPOT) {
2647 for (CodeGenRegisterClass &SubRC : RegClasses)
2648 SubRC.extendSuperRegClasses(SubIdx);
2649 }
2650
2651 Records.getTimer().stopTimer();
2652}
2653
2654/// getRegisterClassForRegister - Find the register class that contains the
2655/// specified physical register. If the register is not in a register class,
2656/// return null. If the register is in multiple classes, and the classes have a
2657/// superset-subset relationship and the same set of types, return the
2658/// superclass. Otherwise return null.
2659const CodeGenRegisterClass *
2660CodeGenRegBank::getRegClassForRegister(const Record *R) {
2661 const CodeGenRegister *Reg = getReg(Def: R);
2662 const CodeGenRegisterClass *FoundRC = nullptr;
2663 for (const CodeGenRegisterClass &RC : getRegClasses()) {
2664 if (!RC.contains(Reg))
2665 continue;
2666
2667 // If this is the first class that contains the register,
2668 // make a note of it and go on to the next class.
2669 if (!FoundRC) {
2670 FoundRC = &RC;
2671 continue;
2672 }
2673
2674 // If a register's classes have different types, return null.
2675 if (RC.getValueTypes() != FoundRC->getValueTypes())
2676 return nullptr;
2677
2678 // Check to see if the previously found class that contains
2679 // the register is a subclass of the current class. If so,
2680 // prefer the superclass.
2681 if (RC.hasSubClass(RC: FoundRC)) {
2682 FoundRC = &RC;
2683 continue;
2684 }
2685
2686 // Check to see if the previously found class that contains
2687 // the register is a superclass of the current class. If so,
2688 // prefer the superclass.
2689 if (FoundRC->hasSubClass(RC: &RC))
2690 continue;
2691
2692 // Multiple classes, and neither is a superclass of the other.
2693 // Return null.
2694 return nullptr;
2695 }
2696 return FoundRC;
2697}
2698
2699bool CodeGenRegBank::regClassContainsReg(const Record *RegClassDef,
2700 const Record *RegDef,
2701 ArrayRef<SMLoc> Loc) {
2702 // Check all four combinations of Register[ByHwMode] X RegClass[ByHwMode],
2703 // starting with the two RegClassByHwMode cases.
2704 unsigned NumModes = CGH.getNumModeIds();
2705 std::optional<RegisterByHwMode> RegByMode;
2706 CodeGenRegister *Reg = nullptr;
2707 if (RegDef->isSubClassOf(Name: "RegisterByHwMode"))
2708 RegByMode = RegisterByHwMode(RegDef, *this);
2709 else
2710 Reg = getReg(Def: RegDef);
2711 if (RegClassDef->isSubClassOf(Name: "RegClassByHwMode")) {
2712 RegClassByHwMode RC(RegClassDef, *this);
2713 for (unsigned M = 0; M < NumModes; ++M) {
2714 if (RC.hasMode(M) && !RC.get(Mode: M)->contains(Reg: Reg ? Reg : RegByMode->get(Mode: M)))
2715 return false;
2716 }
2717 return true;
2718 }
2719 // Otherwise we have a plain register class, check Register[ByHwMode]
2720 CodeGenRegisterClass *RC = getRegClass(Def: RegClassDef, Loc);
2721 if (Reg)
2722 return RC->contains(Reg);
2723 for (unsigned M = 0; M < NumModes; ++M) {
2724 if (RegByMode->hasMode(M) && !RC->contains(Reg: RegByMode->get(Mode: M)))
2725 return false;
2726 }
2727 return true; // RegByMode contained for all possible modes.
2728}
2729
2730const CodeGenRegisterClass *
2731CodeGenRegBank::getMinimalPhysRegClass(const Record *RegRecord,
2732 ValueTypeByHwMode *VT) {
2733 const CodeGenRegister *Reg = getReg(Def: RegRecord);
2734 const CodeGenRegisterClass *BestRC = nullptr;
2735 for (const CodeGenRegisterClass &RC : getRegClasses()) {
2736 if ((!VT || RC.hasType(VT: *VT)) && RC.contains(Reg) &&
2737 (!BestRC || BestRC->hasSubClass(RC: &RC)))
2738 BestRC = &RC;
2739 }
2740
2741 assert(BestRC && "Couldn't find the register class");
2742 return BestRC;
2743}
2744
2745const CodeGenRegisterClass *
2746CodeGenRegBank::getSuperRegForSubReg(const ValueTypeByHwMode &ValueTy,
2747 const CodeGenSubRegIndex *SubIdx,
2748 bool MustBeAllocatable) const {
2749 std::vector<const CodeGenRegisterClass *> Candidates;
2750 auto &RegClasses = getRegClasses();
2751
2752 // Try to find a register class which supports ValueTy, and also contains
2753 // SubIdx.
2754 for (const CodeGenRegisterClass &RC : RegClasses) {
2755 // Is there a subclass of this class which contains this subregister index?
2756 const CodeGenRegisterClass *SubClassWithSubReg =
2757 RC.getSubClassWithSubReg(SubIdx);
2758 if (!SubClassWithSubReg)
2759 continue;
2760
2761 // We have a class. Check if it supports this value type.
2762 if (!llvm::is_contained(Range: SubClassWithSubReg->VTs, Element: ValueTy))
2763 continue;
2764
2765 // If necessary, check that it is allocatable.
2766 if (MustBeAllocatable && !SubClassWithSubReg->Allocatable)
2767 continue;
2768
2769 // We have a register class which supports both the value type and
2770 // subregister index. Remember it.
2771 Candidates.push_back(x: SubClassWithSubReg);
2772 }
2773
2774 // If we didn't find anything, we're done.
2775 if (Candidates.empty())
2776 return nullptr;
2777
2778 // Find and return the largest of our candidate classes.
2779 llvm::stable_sort(Range&: Candidates, C: [&](const CodeGenRegisterClass *A,
2780 const CodeGenRegisterClass *B) {
2781 if (A->getMembers().size() > B->getMembers().size())
2782 return true;
2783
2784 if (A->getMembers().size() < B->getMembers().size())
2785 return false;
2786
2787 // Order by name as a tie-breaker.
2788 return StringRef(A->getName()) < B->getName();
2789 });
2790
2791 return Candidates[0];
2792}
2793
2794BitVector
2795CodeGenRegBank::computeCoveredRegisters(ArrayRef<const Record *> Regs) {
2796 SetVector<const CodeGenRegister *> Set;
2797
2798 // First add Regs with all sub-registers.
2799 for (const Record *RegDef : Regs) {
2800 CodeGenRegister *Reg = getReg(Def: RegDef);
2801 if (Set.insert(X: Reg))
2802 // Reg is new, add all sub-registers.
2803 // The pre-ordering is not important here.
2804 Reg->addSubRegsPreOrder(OSet&: Set, RegBank&: *this);
2805 }
2806
2807 // Second, find all super-registers that are completely covered by the set.
2808 for (unsigned i = 0; i != Set.size(); ++i) {
2809 for (const CodeGenRegister *Super : Set[i]->getSuperRegs()) {
2810 if (!Super->CoveredBySubRegs || Set.contains(key: Super))
2811 continue;
2812 // This new super-register is covered by its sub-registers.
2813 bool AllSubsInSet = true;
2814 const CodeGenRegister::SubRegMap &SRM = Super->getSubRegs();
2815 for (auto [_, SR] : SRM)
2816 if (!Set.contains(key: SR)) {
2817 AllSubsInSet = false;
2818 break;
2819 }
2820 // All sub-registers in Set, add Super as well.
2821 // We will visit Super later to recheck its super-registers.
2822 if (AllSubsInSet)
2823 Set.insert(X: Super);
2824 }
2825 }
2826
2827 // Convert to BitVector.
2828 BitVector BV(Registers.size() + 1);
2829 for (const CodeGenRegister *Reg : Set)
2830 BV.set(Reg->EnumValue);
2831 return BV;
2832}
2833
2834void CodeGenRegBank::printRegUnitNames(ArrayRef<unsigned> Units) const {
2835 for (unsigned Unit : Units) {
2836 if (Unit < NumNativeRegUnits)
2837 dbgs() << ' ' << RegUnits[Unit].Roots[0]->getName();
2838 else
2839 dbgs() << " #" << Unit;
2840 }
2841 dbgs() << '\n';
2842}
2843