Bug Summary

File:build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/include/llvm/MC/LaneBitmask.h
Warning:line 86, column 34
The result of the left shift is undefined due to shifting by '4294967295', which is greater or equal to the width of type 'Type'

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name CodeGenRegisters.cpp -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/build-llvm -resource-dir /usr/lib/llvm-16/lib/clang/16.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I utils/TableGen -I /build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/utils/TableGen -I include -I /build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-16/lib/clang/16.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/build-llvm=build-llvm -fmacro-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/build-llvm=build-llvm -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/= -O3 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -Wno-misleading-indentation -std=c++17 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/build-llvm=build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-09-04-125545-48738-1 -x c++ /build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/utils/TableGen/CodeGenRegisters.cpp

/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/utils/TableGen/CodeGenRegisters.cpp

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

/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/include/llvm/MC/LaneBitmask.h

1//===- llvm/MC/LaneBitmask.h ------------------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// A common definition of LaneBitmask for use in TableGen and CodeGen.
11///
12/// A lane mask is a bitmask representing the covering of a register with
13/// sub-registers.
14///
15/// This is typically used to track liveness at sub-register granularity.
16/// Lane masks for sub-register indices are similar to register units for
17/// physical registers. The individual bits in a lane mask can't be assigned
18/// any specific meaning. They can be used to check if two sub-register
19/// indices overlap.
20///
21/// Iff the target has a register such that:
22///
23/// getSubReg(Reg, A) overlaps getSubReg(Reg, B)
24///
25/// then:
26///
27/// (getSubRegIndexLaneMask(A) & getSubRegIndexLaneMask(B)) != 0
28
29#ifndef LLVM_MC_LANEBITMASK_H
30#define LLVM_MC_LANEBITMASK_H
31
32#include "llvm/Support/Compiler.h"
33#include "llvm/Support/Format.h"
34#include "llvm/Support/MathExtras.h"
35#include "llvm/Support/Printable.h"
36#include "llvm/Support/raw_ostream.h"
37
38namespace llvm {
39
40 struct LaneBitmask {
41 // When changing the underlying type, change the format string as well.
42 using Type = uint64_t;
43 enum : unsigned { BitWidth = 8*sizeof(Type) };
44 constexpr static const char *const FormatStr = "%016llX";
45
46 constexpr LaneBitmask() = default;
47 explicit constexpr LaneBitmask(Type V) : Mask(V) {}
48
49 constexpr bool operator== (LaneBitmask M) const { return Mask == M.Mask; }
50 constexpr bool operator!= (LaneBitmask M) const { return Mask != M.Mask; }
51 constexpr bool operator< (LaneBitmask M) const { return Mask < M.Mask; }
52 constexpr bool none() const { return Mask == 0; }
53 constexpr bool any() const { return Mask != 0; }
54 constexpr bool all() const { return ~Mask == 0; }
55
56 constexpr LaneBitmask operator~() const {
57 return LaneBitmask(~Mask);
58 }
59 constexpr LaneBitmask operator|(LaneBitmask M) const {
60 return LaneBitmask(Mask | M.Mask);
61 }
62 constexpr LaneBitmask operator&(LaneBitmask M) const {
63 return LaneBitmask(Mask & M.Mask);
64 }
65 LaneBitmask &operator|=(LaneBitmask M) {
66 Mask |= M.Mask;
67 return *this;
68 }
69 LaneBitmask &operator&=(LaneBitmask M) {
70 Mask &= M.Mask;
71 return *this;
72 }
73
74 constexpr Type getAsInteger() const { return Mask; }
75
76 unsigned getNumLanes() const {
77 return countPopulation(Mask);
78 }
79 unsigned getHighestLane() const {
80 return Log2_64(Mask);
5
Calling 'Log2_64'
7
Returning from 'Log2_64'
8
Returning the value 4294967295
81 }
82
83 static constexpr LaneBitmask getNone() { return LaneBitmask(0); }
84 static constexpr LaneBitmask getAll() { return ~LaneBitmask(0); }
85 static constexpr LaneBitmask getLane(unsigned Lane) {
86 return LaneBitmask(Type(1) << Lane);
13
The result of the left shift is undefined due to shifting by '4294967295', which is greater or equal to the width of type 'Type'
87 }
88
89 private:
90 Type Mask = 0;
91 };
92
93 /// Create Printable object to print LaneBitmasks on a \ref raw_ostream.
94 inline Printable PrintLaneMask(LaneBitmask LaneMask) {
95 return Printable([LaneMask](raw_ostream &OS) {
96 OS << format(LaneBitmask::FormatStr, LaneMask.getAsInteger());
97 });
98 }
99
100} // end namespace llvm
101
102#endif // LLVM_MC_LANEBITMASK_H

/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/include/llvm/Support/MathExtras.h

1//===-- llvm/Support/MathExtras.h - Useful math functions -------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file contains some functions that are useful for math stuff.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_SUPPORT_MATHEXTRAS_H
14#define LLVM_SUPPORT_MATHEXTRAS_H
15
16#include "llvm/ADT/bit.h"
17#include "llvm/Support/Compiler.h"
18#include <cassert>
19#include <climits>
20#include <cmath>
21#include <cstdint>
22#include <cstring>
23#include <limits>
24#include <type_traits>
25
26#ifdef _MSC_VER
27// Declare these intrinsics manually rather including intrin.h. It's very
28// expensive, and MathExtras.h is popular.
29// #include <intrin.h>
30extern "C" {
31unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask);
32unsigned char _BitScanForward64(unsigned long *_Index, unsigned __int64 _Mask);
33unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask);
34unsigned char _BitScanReverse64(unsigned long *_Index, unsigned __int64 _Mask);
35}
36#endif
37
38namespace llvm {
39
40/// The behavior an operation has on an input of 0.
41enum ZeroBehavior {
42 /// The returned value is undefined.
43 ZB_Undefined,
44 /// The returned value is numeric_limits<T>::max()
45 ZB_Max,
46 /// The returned value is numeric_limits<T>::digits
47 ZB_Width
48};
49
50/// Mathematical constants.
51namespace numbers {
52// TODO: Track C++20 std::numbers.
53// TODO: Favor using the hexadecimal FP constants (requires C++17).
54constexpr double e = 2.7182818284590452354, // (0x1.5bf0a8b145749P+1) https://oeis.org/A001113
55 egamma = .57721566490153286061, // (0x1.2788cfc6fb619P-1) https://oeis.org/A001620
56 ln2 = .69314718055994530942, // (0x1.62e42fefa39efP-1) https://oeis.org/A002162
57 ln10 = 2.3025850929940456840, // (0x1.24bb1bbb55516P+1) https://oeis.org/A002392
58 log2e = 1.4426950408889634074, // (0x1.71547652b82feP+0)
59 log10e = .43429448190325182765, // (0x1.bcb7b1526e50eP-2)
60 pi = 3.1415926535897932385, // (0x1.921fb54442d18P+1) https://oeis.org/A000796
61 inv_pi = .31830988618379067154, // (0x1.45f306bc9c883P-2) https://oeis.org/A049541
62 sqrtpi = 1.7724538509055160273, // (0x1.c5bf891b4ef6bP+0) https://oeis.org/A002161
63 inv_sqrtpi = .56418958354775628695, // (0x1.20dd750429b6dP-1) https://oeis.org/A087197
64 sqrt2 = 1.4142135623730950488, // (0x1.6a09e667f3bcdP+0) https://oeis.org/A00219
65 inv_sqrt2 = .70710678118654752440, // (0x1.6a09e667f3bcdP-1)
66 sqrt3 = 1.7320508075688772935, // (0x1.bb67ae8584caaP+0) https://oeis.org/A002194
67 inv_sqrt3 = .57735026918962576451, // (0x1.279a74590331cP-1)
68 phi = 1.6180339887498948482; // (0x1.9e3779b97f4a8P+0) https://oeis.org/A001622
69constexpr float ef = 2.71828183F, // (0x1.5bf0a8P+1) https://oeis.org/A001113
70 egammaf = .577215665F, // (0x1.2788d0P-1) https://oeis.org/A001620
71 ln2f = .693147181F, // (0x1.62e430P-1) https://oeis.org/A002162
72 ln10f = 2.30258509F, // (0x1.26bb1cP+1) https://oeis.org/A002392
73 log2ef = 1.44269504F, // (0x1.715476P+0)
74 log10ef = .434294482F, // (0x1.bcb7b2P-2)
75 pif = 3.14159265F, // (0x1.921fb6P+1) https://oeis.org/A000796
76 inv_pif = .318309886F, // (0x1.45f306P-2) https://oeis.org/A049541
77 sqrtpif = 1.77245385F, // (0x1.c5bf8aP+0) https://oeis.org/A002161
78 inv_sqrtpif = .564189584F, // (0x1.20dd76P-1) https://oeis.org/A087197
79 sqrt2f = 1.41421356F, // (0x1.6a09e6P+0) https://oeis.org/A002193
80 inv_sqrt2f = .707106781F, // (0x1.6a09e6P-1)
81 sqrt3f = 1.73205081F, // (0x1.bb67aeP+0) https://oeis.org/A002194
82 inv_sqrt3f = .577350269F, // (0x1.279a74P-1)
83 phif = 1.61803399F; // (0x1.9e377aP+0) https://oeis.org/A001622
84} // namespace numbers
85
86namespace detail {
87template <typename T, std::size_t SizeOfT> struct TrailingZerosCounter {
88 static unsigned count(T Val, ZeroBehavior) {
89 if (!Val)
90 return std::numeric_limits<T>::digits;
91 if (Val & 0x1)
92 return 0;
93
94 // Bisection method.
95 unsigned ZeroBits = 0;
96 T Shift = std::numeric_limits<T>::digits >> 1;
97 T Mask = std::numeric_limits<T>::max() >> Shift;
98 while (Shift) {
99 if ((Val & Mask) == 0) {
100 Val >>= Shift;
101 ZeroBits |= Shift;
102 }
103 Shift >>= 1;
104 Mask >>= Shift;
105 }
106 return ZeroBits;
107 }
108};
109
110#if defined(__GNUC__4) || defined(_MSC_VER)
111template <typename T> struct TrailingZerosCounter<T, 4> {
112 static unsigned count(T Val, ZeroBehavior ZB) {
113 if (ZB != ZB_Undefined && Val == 0)
114 return 32;
115
116#if __has_builtin(__builtin_ctz)1 || defined(__GNUC__4)
117 return __builtin_ctz(Val);
118#elif defined(_MSC_VER)
119 unsigned long Index;
120 _BitScanForward(&Index, Val);
121 return Index;
122#endif
123 }
124};
125
126#if !defined(_MSC_VER) || defined(_M_X64)
127template <typename T> struct TrailingZerosCounter<T, 8> {
128 static unsigned count(T Val, ZeroBehavior ZB) {
129 if (ZB != ZB_Undefined && Val == 0)
130 return 64;
131
132#if __has_builtin(__builtin_ctzll)1 || defined(__GNUC__4)
133 return __builtin_ctzll(Val);
134#elif defined(_MSC_VER)
135 unsigned long Index;
136 _BitScanForward64(&Index, Val);
137 return Index;
138#endif
139 }
140};
141#endif
142#endif
143} // namespace detail
144
145/// Count number of 0's from the least significant bit to the most
146/// stopping at the first 1.
147///
148/// Only unsigned integral types are allowed.
149///
150/// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
151/// valid arguments.
152template <typename T>
153unsigned countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
154 static_assert(std::is_unsigned_v<T>,
155 "Only unsigned integral types are allowed.");
156 return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB);
157}
158
159namespace detail {
160template <typename T, std::size_t SizeOfT> struct LeadingZerosCounter {
161 static unsigned count(T Val, ZeroBehavior) {
162 if (!Val)
163 return std::numeric_limits<T>::digits;
164
165 // Bisection method.
166 unsigned ZeroBits = 0;
167 for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) {
168 T Tmp = Val >> Shift;
169 if (Tmp)
170 Val = Tmp;
171 else
172 ZeroBits |= Shift;
173 }
174 return ZeroBits;
175 }
176};
177
178#if defined(__GNUC__4) || defined(_MSC_VER)
179template <typename T> struct LeadingZerosCounter<T, 4> {
180 static unsigned count(T Val, ZeroBehavior ZB) {
181 if (ZB != ZB_Undefined && Val == 0)
182 return 32;
183
184#if __has_builtin(__builtin_clz)1 || defined(__GNUC__4)
185 return __builtin_clz(Val);
186#elif defined(_MSC_VER)
187 unsigned long Index;
188 _BitScanReverse(&Index, Val);
189 return Index ^ 31;
190#endif
191 }
192};
193
194#if !defined(_MSC_VER) || defined(_M_X64)
195template <typename T> struct LeadingZerosCounter<T, 8> {
196 static unsigned count(T Val, ZeroBehavior ZB) {
197 if (ZB != ZB_Undefined && Val == 0)
198 return 64;
199
200#if __has_builtin(__builtin_clzll)1 || defined(__GNUC__4)
201 return __builtin_clzll(Val);
202#elif defined(_MSC_VER)
203 unsigned long Index;
204 _BitScanReverse64(&Index, Val);
205 return Index ^ 63;
206#endif
207 }
208};
209#endif
210#endif
211} // namespace detail
212
213/// Count number of 0's from the most significant bit to the least
214/// stopping at the first 1.
215///
216/// Only unsigned integral types are allowed.
217///
218/// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
219/// valid arguments.
220template <typename T>
221unsigned countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
222 static_assert(std::is_unsigned_v<T>,
223 "Only unsigned integral types are allowed.");
224 return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val, ZB);
225}
226
227/// Get the index of the first set bit starting from the least
228/// significant bit.
229///
230/// Only unsigned integral types are allowed.
231///
232/// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
233/// valid arguments.
234template <typename T> T findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) {
235 if (ZB == ZB_Max && Val == 0)
236 return std::numeric_limits<T>::max();
237
238 return countTrailingZeros(Val, ZB_Undefined);
239}
240
241/// Create a bitmask with the N right-most bits set to 1, and all other
242/// bits set to 0. Only unsigned types are allowed.
243template <typename T> T maskTrailingOnes(unsigned N) {
244 static_assert(std::is_unsigned<T>::value, "Invalid type!");
245 const unsigned Bits = CHAR_BIT8 * sizeof(T);
246 assert(N <= Bits && "Invalid bit index")(static_cast <bool> (N <= Bits && "Invalid bit index"
) ? void (0) : __assert_fail ("N <= Bits && \"Invalid bit index\""
, "llvm/include/llvm/Support/MathExtras.h", 246, __extension__
__PRETTY_FUNCTION__))
;
247 return N == 0 ? 0 : (T(-1) >> (Bits - N));
248}
249
250/// Create a bitmask with the N left-most bits set to 1, and all other
251/// bits set to 0. Only unsigned types are allowed.
252template <typename T> T maskLeadingOnes(unsigned N) {
253 return ~maskTrailingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
254}
255
256/// Create a bitmask with the N right-most bits set to 0, and all other
257/// bits set to 1. Only unsigned types are allowed.
258template <typename T> T maskTrailingZeros(unsigned N) {
259 return maskLeadingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
260}
261
262/// Create a bitmask with the N left-most bits set to 0, and all other
263/// bits set to 1. Only unsigned types are allowed.
264template <typename T> T maskLeadingZeros(unsigned N) {
265 return maskTrailingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
266}
267
268/// Get the index of the last set bit starting from the least
269/// significant bit.
270///
271/// Only unsigned integral types are allowed.
272///
273/// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
274/// valid arguments.
275template <typename T> T findLastSet(T Val, ZeroBehavior ZB = ZB_Max) {
276 if (ZB == ZB_Max && Val == 0)
277 return std::numeric_limits<T>::max();
278
279 // Use ^ instead of - because both gcc and llvm can remove the associated ^
280 // in the __builtin_clz intrinsic on x86.
281 return countLeadingZeros(Val, ZB_Undefined) ^
282 (std::numeric_limits<T>::digits - 1);
283}
284
285/// Macro compressed bit reversal table for 256 bits.
286///
287/// http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
288static const unsigned char BitReverseTable256[256] = {
289#define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64
290#define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16)
291#define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4)
292 R6(0), R6(2), R6(1), R6(3)
293#undef R2
294#undef R4
295#undef R6
296};
297
298/// Reverse the bits in \p Val.
299template <typename T> T reverseBits(T Val) {
300#if __has_builtin(__builtin_bitreverse8)1
301 if constexpr (std::is_same_v<T, uint8_t>)
302 return __builtin_bitreverse8(Val);
303#endif
304#if __has_builtin(__builtin_bitreverse16)1
305 if constexpr (std::is_same_v<T, uint16_t>)
306 return __builtin_bitreverse16(Val);
307#endif
308#if __has_builtin(__builtin_bitreverse32)1
309 if constexpr (std::is_same_v<T, uint32_t>)
310 return __builtin_bitreverse32(Val);
311#endif
312#if __has_builtin(__builtin_bitreverse64)1
313 if constexpr (std::is_same_v<T, uint64_t>)
314 return __builtin_bitreverse64(Val);
315#endif
316
317 unsigned char in[sizeof(Val)];
318 unsigned char out[sizeof(Val)];
319 std::memcpy(in, &Val, sizeof(Val));
320 for (unsigned i = 0; i < sizeof(Val); ++i)
321 out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
322 std::memcpy(&Val, out, sizeof(Val));
323 return Val;
324}
325
326// NOTE: The following support functions use the _32/_64 extensions instead of
327// type overloading so that signed and unsigned integers can be used without
328// ambiguity.
329
330/// Return the high 32 bits of a 64 bit value.
331constexpr inline uint32_t Hi_32(uint64_t Value) {
332 return static_cast<uint32_t>(Value >> 32);
333}
334
335/// Return the low 32 bits of a 64 bit value.
336constexpr inline uint32_t Lo_32(uint64_t Value) {
337 return static_cast<uint32_t>(Value);
338}
339
340/// Make a 64-bit integer from a high / low pair of 32-bit integers.
341constexpr inline uint64_t Make_64(uint32_t High, uint32_t Low) {
342 return ((uint64_t)High << 32) | (uint64_t)Low;
343}
344
345/// Checks if an integer fits into the given bit width.
346template <unsigned N> constexpr inline bool isInt(int64_t x) {
347 if constexpr (N == 8)
348 return static_cast<int8_t>(x) == x;
349 if constexpr (N == 16)
350 return static_cast<int16_t>(x) == x;
351 if constexpr (N == 32)
352 return static_cast<int32_t>(x) == x;
353 if constexpr (N < 64)
354 return -(INT64_C(1)1L << (N - 1)) <= x && x < (INT64_C(1)1L << (N - 1));
355 (void)x; // MSVC v19.25 warns that x is unused.
356 return true;
357}
358
359/// Checks if a signed integer is an N bit number shifted left by S.
360template <unsigned N, unsigned S>
361constexpr inline bool isShiftedInt(int64_t x) {
362 static_assert(
363 N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
364 static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
365 return isInt<N + S>(x) && (x % (UINT64_C(1)1UL << S) == 0);
366}
367
368/// Checks if an unsigned integer fits into the given bit width.
369template <unsigned N> constexpr inline bool isUInt(uint64_t x) {
370 static_assert(N > 0, "isUInt<0> doesn't make sense");
371 if constexpr (N == 8)
372 return static_cast<uint8_t>(x) == x;
373 if constexpr (N == 16)
374 return static_cast<uint16_t>(x) == x;
375 if constexpr (N == 32)
376 return static_cast<uint32_t>(x) == x;
377 if constexpr (N < 64)
378 return x < (UINT64_C(1)1UL << (N));
379 (void)x; // MSVC v19.25 warns that x is unused.
380 return true;
381}
382
383/// Checks if a unsigned integer is an N bit number shifted left by S.
384template <unsigned N, unsigned S>
385constexpr inline bool isShiftedUInt(uint64_t x) {
386 static_assert(
387 N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
388 static_assert(N + S <= 64,
389 "isShiftedUInt<N, S> with N + S > 64 is too wide.");
390 // Per the two static_asserts above, S must be strictly less than 64. So
391 // 1 << S is not undefined behavior.
392 return isUInt<N + S>(x) && (x % (UINT64_C(1)1UL << S) == 0);
393}
394
395/// Gets the maximum value for a N-bit unsigned integer.
396inline uint64_t maxUIntN(uint64_t N) {
397 assert(N > 0 && N <= 64 && "integer width out of range")(static_cast <bool> (N > 0 && N <= 64 &&
"integer width out of range") ? void (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\""
, "llvm/include/llvm/Support/MathExtras.h", 397, __extension__
__PRETTY_FUNCTION__))
;
398
399 // uint64_t(1) << 64 is undefined behavior, so we can't do
400 // (uint64_t(1) << N) - 1
401 // without checking first that N != 64. But this works and doesn't have a
402 // branch.
403 return UINT64_MAX(18446744073709551615UL) >> (64 - N);
404}
405
406/// Gets the minimum value for a N-bit signed integer.
407inline int64_t minIntN(int64_t N) {
408 assert(N > 0 && N <= 64 && "integer width out of range")(static_cast <bool> (N > 0 && N <= 64 &&
"integer width out of range") ? void (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\""
, "llvm/include/llvm/Support/MathExtras.h", 408, __extension__
__PRETTY_FUNCTION__))
;
409
410 return UINT64_C(1)1UL + ~(UINT64_C(1)1UL << (N - 1));
411}
412
413/// Gets the maximum value for a N-bit signed integer.
414inline int64_t maxIntN(int64_t N) {
415 assert(N > 0 && N <= 64 && "integer width out of range")(static_cast <bool> (N > 0 && N <= 64 &&
"integer width out of range") ? void (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\""
, "llvm/include/llvm/Support/MathExtras.h", 415, __extension__
__PRETTY_FUNCTION__))
;
416
417 // This relies on two's complement wraparound when N == 64, so we convert to
418 // int64_t only at the very end to avoid UB.
419 return (UINT64_C(1)1UL << (N - 1)) - 1;
420}
421
422/// Checks if an unsigned integer fits into the given (dynamic) bit width.
423inline bool isUIntN(unsigned N, uint64_t x) {
424 return N >= 64 || x <= maxUIntN(N);
425}
426
427/// Checks if an signed integer fits into the given (dynamic) bit width.
428inline bool isIntN(unsigned N, int64_t x) {
429 return N >= 64 || (minIntN(N) <= x && x <= maxIntN(N));
430}
431
432/// Return true if the argument is a non-empty sequence of ones starting at the
433/// least significant bit with the remainder zero (32 bit version).
434/// Ex. isMask_32(0x0000FFFFU) == true.
435constexpr inline bool isMask_32(uint32_t Value) {
436 return Value && ((Value + 1) & Value) == 0;
437}
438
439/// Return true if the argument is a non-empty sequence of ones starting at the
440/// least significant bit with the remainder zero (64 bit version).
441constexpr inline bool isMask_64(uint64_t Value) {
442 return Value && ((Value + 1) & Value) == 0;
443}
444
445/// Return true if the argument contains a non-empty sequence of ones with the
446/// remainder zero (32 bit version.) Ex. isShiftedMask_32(0x0000FF00U) == true.
447constexpr inline bool isShiftedMask_32(uint32_t Value) {
448 return Value && isMask_32((Value - 1) | Value);
449}
450
451/// Return true if the argument contains a non-empty sequence of ones with the
452/// remainder zero (64 bit version.)
453constexpr inline bool isShiftedMask_64(uint64_t Value) {
454 return Value && isMask_64((Value - 1) | Value);
455}
456
457/// Return true if the argument is a power of two > 0.
458/// Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
459constexpr inline bool isPowerOf2_32(uint32_t Value) {
460 return llvm::has_single_bit(Value);
461}
462
463/// Return true if the argument is a power of two > 0 (64 bit edition.)
464constexpr inline bool isPowerOf2_64(uint64_t Value) {
465 return llvm::has_single_bit(Value);
466}
467
468/// Count the number of ones from the most significant bit to the first
469/// zero bit.
470///
471/// Ex. countLeadingOnes(0xFF0FFF00) == 8.
472/// Only unsigned integral types are allowed.
473///
474/// \param ZB the behavior on an input of all ones. Only ZB_Width and
475/// ZB_Undefined are valid arguments.
476template <typename T>
477unsigned countLeadingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
478 static_assert(std::is_unsigned_v<T>,
479 "Only unsigned integral types are allowed.");
480 return countLeadingZeros<T>(~Value, ZB);
481}
482
483/// Count the number of ones from the least significant bit to the first
484/// zero bit.
485///
486/// Ex. countTrailingOnes(0x00FF00FF) == 8.
487/// Only unsigned integral types are allowed.
488///
489/// \param ZB the behavior on an input of all ones. Only ZB_Width and
490/// ZB_Undefined are valid arguments.
491template <typename T>
492unsigned countTrailingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
493 static_assert(std::is_unsigned_v<T>,
494 "Only unsigned integral types are allowed.");
495 return countTrailingZeros<T>(~Value, ZB);
496}
497
498/// Count the number of set bits in a value.
499/// Ex. countPopulation(0xF000F000) = 8
500/// Returns 0 if the word is zero.
501template <typename T>
502inline unsigned countPopulation(T Value) {
503 static_assert(std::is_unsigned_v<T>,
504 "Only unsigned integral types are allowed.");
505 return (unsigned)llvm::popcount(Value);
506}
507
508/// Return true if the argument contains a non-empty sequence of ones with the
509/// remainder zero (32 bit version.) Ex. isShiftedMask_32(0x0000FF00U) == true.
510/// If true, \p MaskIdx will specify the index of the lowest set bit and \p
511/// MaskLen is updated to specify the length of the mask, else neither are
512/// updated.
513inline bool isShiftedMask_32(uint32_t Value, unsigned &MaskIdx,
514 unsigned &MaskLen) {
515 if (!isShiftedMask_32(Value))
516 return false;
517 MaskIdx = countTrailingZeros(Value);
518 MaskLen = countPopulation(Value);
519 return true;
520}
521
522/// Return true if the argument contains a non-empty sequence of ones with the
523/// remainder zero (64 bit version.) If true, \p MaskIdx will specify the index
524/// of the lowest set bit and \p MaskLen is updated to specify the length of the
525/// mask, else neither are updated.
526inline bool isShiftedMask_64(uint64_t Value, unsigned &MaskIdx,
527 unsigned &MaskLen) {
528 if (!isShiftedMask_64(Value))
529 return false;
530 MaskIdx = countTrailingZeros(Value);
531 MaskLen = countPopulation(Value);
532 return true;
533}
534
535/// Compile time Log2.
536/// Valid only for positive powers of two.
537template <size_t kValue> constexpr inline size_t CTLog2() {
538 static_assert(kValue > 0 && llvm::isPowerOf2_64(kValue),
539 "Value is not a valid power of 2");
540 return 1 + CTLog2<kValue / 2>();
541}
542
543template <> constexpr inline size_t CTLog2<1>() { return 0; }
544
545/// Return the floor log base 2 of the specified value, -1 if the value is zero.
546/// (32 bit edition.)
547/// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
548inline unsigned Log2_32(uint32_t Value) {
549 return 31 - countLeadingZeros(Value);
550}
551
552/// Return the floor log base 2 of the specified value, -1 if the value is zero.
553/// (64 bit edition.)
554inline unsigned Log2_64(uint64_t Value) {
555 return 63 - countLeadingZeros(Value);
6
Returning the value 4294967295
556}
557
558/// Return the ceil log base 2 of the specified value, 32 if the value is zero.
559/// (32 bit edition).
560/// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
561inline unsigned Log2_32_Ceil(uint32_t Value) {
562 return 32 - countLeadingZeros(Value - 1);
563}
564
565/// Return the ceil log base 2 of the specified value, 64 if the value is zero.
566/// (64 bit edition.)
567inline unsigned Log2_64_Ceil(uint64_t Value) {
568 return 64 - countLeadingZeros(Value - 1);
569}
570
571/// This function takes a 64-bit integer and returns the bit equivalent double.
572inline double BitsToDouble(uint64_t Bits) {
573 static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
574 return llvm::bit_cast<double>(Bits);
575}
576
577/// This function takes a 32-bit integer and returns the bit equivalent float.
578inline float BitsToFloat(uint32_t Bits) {
579 static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
580 return llvm::bit_cast<float>(Bits);
581}
582
583/// This function takes a double and returns the bit equivalent 64-bit integer.
584/// Note that copying doubles around changes the bits of NaNs on some hosts,
585/// notably x86, so this routine cannot be used if these bits are needed.
586inline uint64_t DoubleToBits(double Double) {
587 static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
588 return llvm::bit_cast<uint64_t>(Double);
589}
590
591/// This function takes a float and returns the bit equivalent 32-bit integer.
592/// Note that copying floats around changes the bits of NaNs on some hosts,
593/// notably x86, so this routine cannot be used if these bits are needed.
594inline uint32_t FloatToBits(float Float) {
595 static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
596 return llvm::bit_cast<uint32_t>(Float);
597}
598
599/// A and B are either alignments or offsets. Return the minimum alignment that
600/// may be assumed after adding the two together.
601constexpr inline uint64_t MinAlign(uint64_t A, uint64_t B) {
602 // The largest power of 2 that divides both A and B.
603 //
604 // Replace "-Value" by "1+~Value" in the following commented code to avoid
605 // MSVC warning C4146
606 // return (A | B) & -(A | B);
607 return (A | B) & (1 + ~(A | B));
608}
609
610/// Returns the next power of two (in 64-bits) that is strictly greater than A.
611/// Returns zero on overflow.
612constexpr inline uint64_t NextPowerOf2(uint64_t A) {
613 A |= (A >> 1);
614 A |= (A >> 2);
615 A |= (A >> 4);
616 A |= (A >> 8);
617 A |= (A >> 16);
618 A |= (A >> 32);
619 return A + 1;
620}
621
622/// Returns the power of two which is less than or equal to the given value.
623/// Essentially, it is a floor operation across the domain of powers of two.
624inline uint64_t PowerOf2Floor(uint64_t A) {
625 if (!A) return 0;
626 return 1ull << (63 - countLeadingZeros(A, ZB_Undefined));
627}
628
629/// Returns the power of two which is greater than or equal to the given value.
630/// Essentially, it is a ceil operation across the domain of powers of two.
631inline uint64_t PowerOf2Ceil(uint64_t A) {
632 if (!A)
633 return 0;
634 return NextPowerOf2(A - 1);
635}
636
637/// Returns the next integer (mod 2**64) that is greater than or equal to
638/// \p Value and is a multiple of \p Align. \p Align must be non-zero.
639///
640/// Examples:
641/// \code
642/// alignTo(5, 8) = 8
643/// alignTo(17, 8) = 24
644/// alignTo(~0LL, 8) = 0
645/// alignTo(321, 255) = 510
646/// \endcode
647inline uint64_t alignTo(uint64_t Value, uint64_t Align) {
648 assert(Align != 0u && "Align can't be 0.")(static_cast <bool> (Align != 0u && "Align can't be 0."
) ? void (0) : __assert_fail ("Align != 0u && \"Align can't be 0.\""
, "llvm/include/llvm/Support/MathExtras.h", 648, __extension__
__PRETTY_FUNCTION__))
;
649 return (Value + Align - 1) / Align * Align;
650}
651
652inline uint64_t alignToPowerOf2(uint64_t Value, uint64_t Align) {
653 assert(Align != 0 && (Align & (Align - 1)) == 0 &&(static_cast <bool> (Align != 0 && (Align &
(Align - 1)) == 0 && "Align must be a power of 2") ?
void (0) : __assert_fail ("Align != 0 && (Align & (Align - 1)) == 0 && \"Align must be a power of 2\""
, "llvm/include/llvm/Support/MathExtras.h", 654, __extension__
__PRETTY_FUNCTION__))
654 "Align must be a power of 2")(static_cast <bool> (Align != 0 && (Align &
(Align - 1)) == 0 && "Align must be a power of 2") ?
void (0) : __assert_fail ("Align != 0 && (Align & (Align - 1)) == 0 && \"Align must be a power of 2\""
, "llvm/include/llvm/Support/MathExtras.h", 654, __extension__
__PRETTY_FUNCTION__))
;
655 return (Value + Align - 1) & -Align;
656}
657
658/// If non-zero \p Skew is specified, the return value will be a minimal integer
659/// that is greater than or equal to \p Size and equal to \p A * N + \p Skew for
660/// some integer N. If \p Skew is larger than \p A, its value is adjusted to '\p
661/// Skew mod \p A'. \p Align must be non-zero.
662///
663/// Examples:
664/// \code
665/// alignTo(5, 8, 7) = 7
666/// alignTo(17, 8, 1) = 17
667/// alignTo(~0LL, 8, 3) = 3
668/// alignTo(321, 255, 42) = 552
669/// \endcode
670inline uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew) {
671 assert(Align != 0u && "Align can't be 0.")(static_cast <bool> (Align != 0u && "Align can't be 0."
) ? void (0) : __assert_fail ("Align != 0u && \"Align can't be 0.\""
, "llvm/include/llvm/Support/MathExtras.h", 671, __extension__
__PRETTY_FUNCTION__))
;
672 Skew %= Align;
673 return alignTo(Value - Skew, Align) + Skew;
674}
675
676/// Returns the next integer (mod 2**64) that is greater than or equal to
677/// \p Value and is a multiple of \c Align. \c Align must be non-zero.
678template <uint64_t Align> constexpr inline uint64_t alignTo(uint64_t Value) {
679 static_assert(Align != 0u, "Align must be non-zero");
680 return (Value + Align - 1) / Align * Align;
681}
682
683/// Returns the integer ceil(Numerator / Denominator).
684inline uint64_t divideCeil(uint64_t Numerator, uint64_t Denominator) {
685 return alignTo(Numerator, Denominator) / Denominator;
686}
687
688/// Returns the integer nearest(Numerator / Denominator).
689inline uint64_t divideNearest(uint64_t Numerator, uint64_t Denominator) {
690 return (Numerator + (Denominator / 2)) / Denominator;
691}
692
693/// Returns the largest uint64_t less than or equal to \p Value and is
694/// \p Skew mod \p Align. \p Align must be non-zero
695inline uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
696 assert(Align != 0u && "Align can't be 0.")(static_cast <bool> (Align != 0u && "Align can't be 0."
) ? void (0) : __assert_fail ("Align != 0u && \"Align can't be 0.\""
, "llvm/include/llvm/Support/MathExtras.h", 696, __extension__
__PRETTY_FUNCTION__))
;
697 Skew %= Align;
698 return (Value - Skew) / Align * Align + Skew;
699}
700
701/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
702/// Requires 0 < B <= 32.
703template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
704 static_assert(B > 0, "Bit width can't be 0.");
705 static_assert(B <= 32, "Bit width out of range.");
706 return int32_t(X << (32 - B)) >> (32 - B);
707}
708
709/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
710/// Requires 0 < B <= 32.
711inline int32_t SignExtend32(uint32_t X, unsigned B) {
712 assert(B > 0 && "Bit width can't be 0.")(static_cast <bool> (B > 0 && "Bit width can't be 0."
) ? void (0) : __assert_fail ("B > 0 && \"Bit width can't be 0.\""
, "llvm/include/llvm/Support/MathExtras.h", 712, __extension__
__PRETTY_FUNCTION__))
;
713 assert(B <= 32 && "Bit width out of range.")(static_cast <bool> (B <= 32 && "Bit width out of range."
) ? void (0) : __assert_fail ("B <= 32 && \"Bit width out of range.\""
, "llvm/include/llvm/Support/MathExtras.h", 713, __extension__
__PRETTY_FUNCTION__))
;
714 return int32_t(X << (32 - B)) >> (32 - B);
715}
716
717/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
718/// Requires 0 < B <= 64.
719template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
720 static_assert(B > 0, "Bit width can't be 0.");
721 static_assert(B <= 64, "Bit width out of range.");
722 return int64_t(x << (64 - B)) >> (64 - B);
723}
724
725/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
726/// Requires 0 < B <= 64.
727inline int64_t SignExtend64(uint64_t X, unsigned B) {
728 assert(B > 0 && "Bit width can't be 0.")(static_cast <bool> (B > 0 && "Bit width can't be 0."
) ? void (0) : __assert_fail ("B > 0 && \"Bit width can't be 0.\""
, "llvm/include/llvm/Support/MathExtras.h", 728, __extension__
__PRETTY_FUNCTION__))
;
729 assert(B <= 64 && "Bit width out of range.")(static_cast <bool> (B <= 64 && "Bit width out of range."
) ? void (0) : __assert_fail ("B <= 64 && \"Bit width out of range.\""
, "llvm/include/llvm/Support/MathExtras.h", 729, __extension__
__PRETTY_FUNCTION__))
;
730 return int64_t(X << (64 - B)) >> (64 - B);
731}
732
733/// Subtract two unsigned integers, X and Y, of type T and return the absolute
734/// value of the result.
735template <typename T>
736std::enable_if_t<std::is_unsigned<T>::value, T> AbsoluteDifference(T X, T Y) {
737 return X > Y ? (X - Y) : (Y - X);
738}
739
740/// Add two unsigned integers, X and Y, of type T. Clamp the result to the
741/// maximum representable value of T on overflow. ResultOverflowed indicates if
742/// the result is larger than the maximum representable value of type T.
743template <typename T>
744std::enable_if_t<std::is_unsigned<T>::value, T>
745SaturatingAdd(T X, T Y, bool *ResultOverflowed = nullptr) {
746 bool Dummy;
747 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
748 // Hacker's Delight, p. 29
749 T Z = X + Y;
750 Overflowed = (Z < X || Z < Y);
751 if (Overflowed)
752 return std::numeric_limits<T>::max();
753 else
754 return Z;
755}
756
757/// Multiply two unsigned integers, X and Y, of type T. Clamp the result to the
758/// maximum representable value of T on overflow. ResultOverflowed indicates if
759/// the result is larger than the maximum representable value of type T.
760template <typename T>
761std::enable_if_t<std::is_unsigned<T>::value, T>
762SaturatingMultiply(T X, T Y, bool *ResultOverflowed = nullptr) {
763 bool Dummy;
764 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
765
766 // Hacker's Delight, p. 30 has a different algorithm, but we don't use that
767 // because it fails for uint16_t (where multiplication can have undefined
768 // behavior due to promotion to int), and requires a division in addition
769 // to the multiplication.
770
771 Overflowed = false;
772
773 // Log2(Z) would be either Log2Z or Log2Z + 1.
774 // Special case: if X or Y is 0, Log2_64 gives -1, and Log2Z
775 // will necessarily be less than Log2Max as desired.
776 int Log2Z = Log2_64(X) + Log2_64(Y);
777 const T Max = std::numeric_limits<T>::max();
778 int Log2Max = Log2_64(Max);
779 if (Log2Z < Log2Max) {
780 return X * Y;
781 }
782 if (Log2Z > Log2Max) {
783 Overflowed = true;
784 return Max;
785 }
786
787 // We're going to use the top bit, and maybe overflow one
788 // bit past it. Multiply all but the bottom bit then add
789 // that on at the end.
790 T Z = (X >> 1) * Y;
791 if (Z & ~(Max >> 1)) {
792 Overflowed = true;
793 return Max;
794 }
795 Z <<= 1;
796 if (X & 1)
797 return SaturatingAdd(Z, Y, ResultOverflowed);
798
799 return Z;
800}
801
802/// Multiply two unsigned integers, X and Y, and add the unsigned integer, A to
803/// the product. Clamp the result to the maximum representable value of T on
804/// overflow. ResultOverflowed indicates if the result is larger than the
805/// maximum representable value of type T.
806template <typename T>
807std::enable_if_t<std::is_unsigned<T>::value, T>
808SaturatingMultiplyAdd(T X, T Y, T A, bool *ResultOverflowed = nullptr) {
809 bool Dummy;
810 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
811
812 T Product = SaturatingMultiply(X, Y, &Overflowed);
813 if (Overflowed)
814 return Product;
815
816 return SaturatingAdd(A, Product, &Overflowed);
817}
818
819/// Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
820extern const float huge_valf;
821
822
823/// Add two signed integers, computing the two's complement truncated result,
824/// returning true if overflow occurred.
825template <typename T>
826std::enable_if_t<std::is_signed<T>::value, T> AddOverflow(T X, T Y, T &Result) {
827#if __has_builtin(__builtin_add_overflow)1
828 return __builtin_add_overflow(X, Y, &Result);
829#else
830 // Perform the unsigned addition.
831 using U = std::make_unsigned_t<T>;
832 const U UX = static_cast<U>(X);
833 const U UY = static_cast<U>(Y);
834 const U UResult = UX + UY;
835
836 // Convert to signed.
837 Result = static_cast<T>(UResult);
838
839 // Adding two positive numbers should result in a positive number.
840 if (X > 0 && Y > 0)
841 return Result <= 0;
842 // Adding two negatives should result in a negative number.
843 if (X < 0 && Y < 0)
844 return Result >= 0;
845 return false;
846#endif
847}
848
849/// Subtract two signed integers, computing the two's complement truncated
850/// result, returning true if an overflow ocurred.
851template <typename T>
852std::enable_if_t<std::is_signed<T>::value, T> SubOverflow(T X, T Y, T &Result) {
853#if __has_builtin(__builtin_sub_overflow)1
854 return __builtin_sub_overflow(X, Y, &Result);
855#else
856 // Perform the unsigned addition.
857 using U = std::make_unsigned_t<T>;
858 const U UX = static_cast<U>(X);
859 const U UY = static_cast<U>(Y);
860 const U UResult = UX - UY;
861
862 // Convert to signed.
863 Result = static_cast<T>(UResult);
864
865 // Subtracting a positive number from a negative results in a negative number.
866 if (X <= 0 && Y > 0)
867 return Result >= 0;
868 // Subtracting a negative number from a positive results in a positive number.
869 if (X >= 0 && Y < 0)
870 return Result <= 0;
871 return false;
872#endif
873}
874
875/// Multiply two signed integers, computing the two's complement truncated
876/// result, returning true if an overflow ocurred.
877template <typename T>
878std::enable_if_t<std::is_signed<T>::value, T> MulOverflow(T X, T Y, T &Result) {
879 // Perform the unsigned multiplication on absolute values.
880 using U = std::make_unsigned_t<T>;
881 const U UX = X < 0 ? (0 - static_cast<U>(X)) : static_cast<U>(X);
882 const U UY = Y < 0 ? (0 - static_cast<U>(Y)) : static_cast<U>(Y);
883 const U UResult = UX * UY;
884
885 // Convert to signed.
886 const bool IsNegative = (X < 0) ^ (Y < 0);
887 Result = IsNegative ? (0 - UResult) : UResult;
888
889 // If any of the args was 0, result is 0 and no overflow occurs.
890 if (UX == 0 || UY == 0)
891 return false;
892
893 // UX and UY are in [1, 2^n], where n is the number of digits.
894 // Check how the max allowed absolute value (2^n for negative, 2^(n-1) for
895 // positive) divided by an argument compares to the other.
896 if (IsNegative)
897 return UX > (static_cast<U>(std::numeric_limits<T>::max()) + U(1)) / UY;
898 else
899 return UX > (static_cast<U>(std::numeric_limits<T>::max())) / UY;
900}
901
902} // End llvm namespace
903
904#endif