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