/build/source/llvm/include/llvm/MC/LaneBitmask.h

Bug Summary

File:	build/source/llvm/include/llvm/MC/LaneBitmask.h
Warning:	line 84, 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

Show analyzer invocation

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/source/build-llvm/tools/clang/stage2-bins -resource-dir /usr/lib/llvm-17/lib/clang/17 -D _DEBUG -D _GLIBCXX_ASSERTIONS -D _GNU_SOURCE -D _LIBCPP_ENABLE_ASSERTIONS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I utils/TableGen -I /build/source/llvm/utils/TableGen -I include -I /build/source/llvm/include -I /build/source/llvm/utils/TableGen/GlobalISel/.. -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-17/lib/clang/17/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/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fmacro-prefix-map=/build/source/= -fcoverage-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fcoverage-prefix-map=/build/source/= -source-date-epoch 1683717183 -O2 -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/source/build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/= -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-2023-05-10-133810-16478-1 -x c++ /build/source/llvm/utils/TableGen/CodeGenRegisters.cpp

/build/source/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//===----------------------------------------------------------------------===//

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>

42using namespace llvm;

44#define DEBUG_TYPE"regalloc-emitter" "regalloc-emitter"

46//===----------------------------------------------------------------------===//
47//                             CodeGenSubRegIndex
48//===----------------------------------------------------------------------===//

50CodeGenSubRegIndex::CodeGenSubRegIndex(Record *R, unsigned Enum)
: TheDef(R), EnumValue(Enum), AllSuperRegsCovered(true), Artificial(true) {
Name = std::string(R->getName());
if (R->getValue("Namespace"))
  Namespace = std::string(R->getValueAsString("Namespace"));
Size = R->getValueAsInt("Size");
Offset = R->getValueAsInt("Offset");
57}

59CodeGenSubRegIndex::CodeGenSubRegIndex(StringRef N, StringRef Nspace,
                                     unsigned Enum)
  : TheDef(nullptr), Name(std::string(N)), Namespace(std::string(Nspace)),
    Size(-1), Offset(-1), EnumValue(Enum), AllSuperRegsCovered(true),
    Artificial(true) {}

65std::string CodeGenSubRegIndex::getQualifiedName() const {
std::string N = getNamespace();
if (!N.empty())
  N += "::";
N += getName();
return N;
71}

73void CodeGenSubRegIndex::updateComponents(CodeGenRegBank &RegBank) {
if (!TheDef)
  return;

std::vector<Record*> Comps = TheDef->getValueAsListOfDefs("ComposedOf");
if (!Comps.empty()) {
  if (Comps.size() != 2)
    PrintFatalError(TheDef->getLoc(),
                    "ComposedOf must have exactly two entries");
  CodeGenSubRegIndex *A = RegBank.getSubRegIdx(Comps[0]);
  CodeGenSubRegIndex *B = RegBank.getSubRegIdx(Comps[1]);
  CodeGenSubRegIndex *X = A->addComposite(B, this);
  if (X)
    PrintFatalError(TheDef->getLoc(), "Ambiguous ComposedOf entries");
}

std::vector<Record*> Parts =
  TheDef->getValueAsListOfDefs("CoveringSubRegIndices");
if (!Parts.empty()) {
  if (Parts.size() < 2)
    PrintFatalError(TheDef->getLoc(),
                    "CoveredBySubRegs must have two or more entries");
  SmallVector<CodeGenSubRegIndex*, 8> IdxParts;
  for (Record *Part : Parts)
    IdxParts.push_back(RegBank.getSubRegIdx(Part));
  setConcatenationOf(IdxParts);
}
100}

102LaneBitmask CodeGenSubRegIndex::computeLaneMask() const {
// Already computed?
if (LaneMask.any())
  return LaneMask;

// Recursion guard, shouldn't be required.
LaneMask = LaneBitmask::getAll();

// The lane mask is simply the union of all sub-indices.
LaneBitmask M;
for (const auto &C : Composed)
  M |= C.second->computeLaneMask();
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__));
LaneMask = M;
return LaneMask;
117}

119void CodeGenSubRegIndex::setConcatenationOf(
  ArrayRef<CodeGenSubRegIndex*> Parts) {
if (ConcatenationOf.empty())
  ConcatenationOf.assign(Parts.begin(), Parts.end());
else
  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__))
                    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}

128void CodeGenSubRegIndex::computeConcatTransitiveClosure() {
for (SmallVectorImpl<CodeGenSubRegIndex*>::iterator
     I = ConcatenationOf.begin(); I != ConcatenationOf.end(); /*empty*/) {
  CodeGenSubRegIndex *SubIdx = *I;
  SubIdx->computeConcatTransitiveClosure();
133#ifndef NDEBUG
  for (CodeGenSubRegIndex *SRI : SubIdx->ConcatenationOf)
    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

  if (SubIdx->ConcatenationOf.empty()) {
    ++I;
  } else {
    I = ConcatenationOf.erase(I);
    I = ConcatenationOf.insert(I, SubIdx->ConcatenationOf.begin(),
                               SubIdx->ConcatenationOf.end());
    I += SubIdx->ConcatenationOf.size();
  }
}
147}

149//===----------------------------------------------------------------------===//
150//                              CodeGenRegister
151//===----------------------------------------------------------------------===//

153CodeGenRegister::CodeGenRegister(Record *R, unsigned Enum)
  : TheDef(R), EnumValue(Enum),
    CostPerUse(R->getValueAsListOfInts("CostPerUse")),
    CoveredBySubRegs(R->getValueAsBit("CoveredBySubRegs")),
    HasDisjunctSubRegs(false), Constant(R->getValueAsBit("isConstant")),
    SubRegsComplete(false), SuperRegsComplete(false), TopoSig(~0u) {
Artificial = R->getValueAsBit("isArtificial");
160}

162void CodeGenRegister::buildObjectGraph(CodeGenRegBank &RegBank) {
std::vector<Record*> SRIs = TheDef->getValueAsListOfDefs("SubRegIndices");
std::vector<Record*> SRs = TheDef->getValueAsListOfDefs("SubRegs");

if (SRIs.size() != SRs.size())
  PrintFatalError(TheDef->getLoc(),
                  "SubRegs and SubRegIndices must have the same size");

for (unsigned i = 0, e = SRIs.size(); i != e; ++i) {
  ExplicitSubRegIndices.push_back(RegBank.getSubRegIdx(SRIs[i]));
  ExplicitSubRegs.push_back(RegBank.getReg(SRs[i]));
}

// Also compute leading super-registers. Each register has a list of
// covered-by-subregs super-registers where it appears as the first explicit
// sub-register.
//
// This is used by computeSecondarySubRegs() to find candidates.
if (CoveredBySubRegs && !ExplicitSubRegs.empty())
  ExplicitSubRegs.front()->LeadingSuperRegs.push_back(this);

// Add ad hoc alias links. This is a symmetric relationship between two
// registers, so build a symmetric graph by adding links in both ends.
std::vector<Record*> Aliases = TheDef->getValueAsListOfDefs("Aliases");
for (Record *Alias : Aliases) {
  CodeGenRegister *Reg = RegBank.getReg(Alias);
  ExplicitAliases.push_back(Reg);
  Reg->ExplicitAliases.push_back(this);
}
191}

193StringRef CodeGenRegister::getName() const {
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__));
return TheDef->getName();
196}

198namespace {

200// Iterate over all register units in a set of registers.
201class RegUnitIterator {
CodeGenRegister::Vec::const_iterator RegI, RegE;
CodeGenRegister::RegUnitList::iterator UnitI, UnitE;
static CodeGenRegister::RegUnitList Sentinel;

206public:
RegUnitIterator(const CodeGenRegister::Vec &Regs):
  RegI(Regs.begin()), RegE(Regs.end()) {

  if (RegI == RegE) {
    UnitI = Sentinel.end();
    UnitE = Sentinel.end();
  } else {
    UnitI = (*RegI)->getRegUnits().begin();
    UnitE = (*RegI)->getRegUnits().end();
    advance();
  }
}

bool isValid() const { return UnitI != UnitE; }

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; }

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; }

/// Preincrement.  Move to the next unit.
void operator++() {
  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__));
  ++UnitI;
  advance();
}

233protected:
void advance() {
  while (UnitI == UnitE) {
    if (++RegI == RegE)
      break;
    UnitI = (*RegI)->getRegUnits().begin();
    UnitE = (*RegI)->getRegUnits().end();
  }
}
242};

244CodeGenRegister::RegUnitList RegUnitIterator::Sentinel;

246} // end anonymous namespace

248// Return true of this unit appears in RegUnits.
249static bool hasRegUnit(CodeGenRegister::RegUnitList &RegUnits, unsigned Unit) {
return RegUnits.test(Unit);
251}

253// Inherit register units from subregisters.
254// Return true if the RegUnits changed.
255bool CodeGenRegister::inheritRegUnits(CodeGenRegBank &RegBank) {
bool changed = false;
for (const auto &SubReg : SubRegs) {
  CodeGenRegister *SR = SubReg.second;
  // Merge the subregister's units into this register's RegUnits.
  changed |= (RegUnits |= SR->RegUnits);
}

return changed;
264}

266const CodeGenRegister::SubRegMap &
267CodeGenRegister::computeSubRegs(CodeGenRegBank &RegBank) {
// Only compute this map once.
if (SubRegsComplete)
  return SubRegs;
SubRegsComplete = true;

HasDisjunctSubRegs = ExplicitSubRegs.size() > 1;

// First insert the explicit subregs and make sure they are fully indexed.
for (unsigned i = 0, e = ExplicitSubRegs.size(); i != e; ++i) {
  CodeGenRegister *SR = ExplicitSubRegs[i];
  CodeGenSubRegIndex *Idx = ExplicitSubRegIndices[i];
  if (!SR->Artificial)
    Idx->Artificial = false;
  if (!SubRegs.insert(std::make_pair(Idx, SR)).second)
    PrintFatalError(TheDef->getLoc(), "SubRegIndex " + Idx->getName() +
                    " appears twice in Register " + getName());
  // Map explicit sub-registers first, so the names take precedence.
  // The inherited sub-registers are mapped below.
  SubReg2Idx.insert(std::make_pair(SR, Idx));
}

// Keep track of inherited subregs and how they can be reached.
SmallPtrSet<CodeGenRegister*, 8> Orphans;

// Clone inherited subregs and place duplicate entries in Orphans.
// Here the order is important - earlier subregs take precedence.
for (CodeGenRegister *ESR : ExplicitSubRegs) {
  const SubRegMap &Map = ESR->computeSubRegs(RegBank);
  HasDisjunctSubRegs |= ESR->HasDisjunctSubRegs;

  for (const auto &SR : Map) {
    if (!SubRegs.insert(SR).second)
      Orphans.insert(SR.second);
  }
}

// Expand any composed subreg indices.
// If dsub_2 has ComposedOf = [qsub_1, dsub_0], and this register has a
// qsub_1 subreg, add a dsub_2 subreg.  Keep growing Indices and process
// expanded subreg indices recursively.
SmallVector<CodeGenSubRegIndex*, 8> Indices = ExplicitSubRegIndices;
for (unsigned i = 0; i != Indices.size(); ++i) {
  CodeGenSubRegIndex *Idx = Indices[i];
  const CodeGenSubRegIndex::CompMap &Comps = Idx->getComposites();
  CodeGenRegister *SR = SubRegs[Idx];
  const SubRegMap &Map = SR->computeSubRegs(RegBank);

  // Look at the possible compositions of Idx.
  // They may not all be supported by SR.
  for (auto Comp : Comps) {
    SubRegMap::const_iterator SRI = Map.find(Comp.first);
    if (SRI == Map.end())
      continue; // Idx + I->first doesn't exist in SR.
    // Add I->second as a name for the subreg SRI->second, assuming it is
    // orphaned, and the name isn't already used for something else.
    if (SubRegs.count(Comp.second) || !Orphans.erase(SRI->second))
      continue;
    // We found a new name for the orphaned sub-register.
    SubRegs.insert(std::make_pair(Comp.second, SRI->second));
    Indices.push_back(Comp.second);
  }
}

// Now Orphans contains the inherited subregisters without a direct index.
// Create inferred indexes for all missing entries.
// Work backwards in the Indices vector in order to compose subregs bottom-up.
// Consider this subreg sequence:
//
//   qsub_1 -> dsub_0 -> ssub_0
//
// The qsub_1 -> dsub_0 composition becomes dsub_2, so the ssub_0 register
// can be reached in two different ways:
//
//   qsub_1 -> ssub_0
//   dsub_2 -> ssub_0
//
// We pick the latter composition because another register may have [dsub_0,
// dsub_1, dsub_2] subregs without necessarily having a qsub_1 subreg.  The
// dsub_2 -> ssub_0 composition can be shared.
while (!Indices.empty() && !Orphans.empty()) {
  CodeGenSubRegIndex *Idx = Indices.pop_back_val();
  CodeGenRegister *SR = SubRegs[Idx];
  const SubRegMap &Map = SR->computeSubRegs(RegBank);
  for (const auto &SubReg : Map)
    if (Orphans.erase(SubReg.second))
      SubRegs[RegBank.getCompositeSubRegIndex(Idx, SubReg.first)] = SubReg.second;
}

// Compute the inverse SubReg -> Idx map.
for (const auto &SubReg : SubRegs) {
  if (SubReg.second == this) {
    ArrayRef<SMLoc> Loc;
    if (TheDef)
      Loc = TheDef->getLoc();
    PrintFatalError(Loc, "Register " + getName() +
                    " has itself as a sub-register");
  }

  // Compute AllSuperRegsCovered.
  if (!CoveredBySubRegs)
    SubReg.first->AllSuperRegsCovered = false;

  // Ensure that every sub-register has a unique name.
  DenseMap<const CodeGenRegister*, CodeGenSubRegIndex*>::iterator Ins =
    SubReg2Idx.insert(std::make_pair(SubReg.second, SubReg.first)).first;
  if (Ins->second == SubReg.first)
    continue;
  // Trouble: Two different names for SubReg.second.
  ArrayRef<SMLoc> Loc;
  if (TheDef)
    Loc = TheDef->getLoc();
  PrintFatalError(Loc, "Sub-register can't have two names: " +
                SubReg.second->getName() + " available as " +
                SubReg.first->getName() + " and " + Ins->second->getName());
}

// Derive possible names for sub-register concatenations from any explicit
// sub-registers. By doing this before computeSecondarySubRegs(), we ensure
// that getConcatSubRegIndex() won't invent any concatenated indices that the
// user already specified.
for (unsigned i = 0, e = ExplicitSubRegs.size(); i != e; ++i) {
  CodeGenRegister *SR = ExplicitSubRegs[i];
  if (!SR->CoveredBySubRegs || SR->ExplicitSubRegs.size() <= 1 ||
      SR->Artificial)
    continue;

  // SR is composed of multiple sub-regs. Find their names in this register.
  SmallVector<CodeGenSubRegIndex*, 8> Parts;
  for (unsigned j = 0, e = SR->ExplicitSubRegs.size(); j != e; ++j) {
    CodeGenSubRegIndex &I = *SR->ExplicitSubRegIndices[j];
    if (!I.Artificial)
      Parts.push_back(getSubRegIndex(SR->ExplicitSubRegs[j]));
  }

  // Offer this as an existing spelling for the concatenation of Parts.
  CodeGenSubRegIndex &Idx = *ExplicitSubRegIndices[i];
  Idx.setConcatenationOf(Parts);
}

// Initialize RegUnitList. Because getSubRegs is called recursively, this
// processes the register hierarchy in postorder.
//
// Inherit all sub-register units. It is good enough to look at the explicit
// sub-registers, the other registers won't contribute any more units.
for (unsigned i = 0, e = ExplicitSubRegs.size(); i != e; ++i) {
  CodeGenRegister *SR = ExplicitSubRegs[i];
  RegUnits |= SR->RegUnits;
}

// Absent any ad hoc aliasing, we create one register unit per leaf register.
// These units correspond to the maximal cliques in the register overlap
// graph which is optimal.
//
// When there is ad hoc aliasing, we simply create one unit per edge in the
// undirected ad hoc aliasing graph. Technically, we could do better by
// identifying maximal cliques in the ad hoc graph, but cliques larger than 2
// are extremely rare anyway (I've never seen one), so we don't bother with
// the added complexity.
for (unsigned i = 0, e = ExplicitAliases.size(); i != e; ++i) {
  CodeGenRegister *AR = ExplicitAliases[i];
  // Only visit each edge once.
  if (AR->SubRegsComplete)
    continue;
  // Create a RegUnit representing this alias edge, and add it to both
  // registers.
  unsigned Unit = RegBank.newRegUnit(this, AR);
  RegUnits.set(Unit);
  AR->RegUnits.set(Unit);
}

// Finally, create units for leaf registers without ad hoc aliases. Note that
// a leaf register with ad hoc aliases doesn't get its own unit - it isn't
// necessary. This means the aliasing leaf registers can share a single unit.
if (RegUnits.empty())
  RegUnits.set(RegBank.newRegUnit(this));

// We have now computed the native register units. More may be adopted later
// for balancing purposes.
NativeRegUnits = RegUnits;

return SubRegs;
449}

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) {
SmallVector<SubRegMap::value_type, 8> NewSubRegs;

std::queue<std::pair<CodeGenSubRegIndex*,CodeGenRegister*>> SubRegQueue;
for (std::pair<CodeGenSubRegIndex*,CodeGenRegister*> P : SubRegs)
  SubRegQueue.push(P);

// Look at the leading super-registers of each sub-register. Those are the
// candidates for new sub-registers, assuming they are fully contained in
// this register.
while (!SubRegQueue.empty()) {
  CodeGenSubRegIndex *SubRegIdx;
  const CodeGenRegister *SubReg;
  std::tie(SubRegIdx, SubReg) = SubRegQueue.front();
  SubRegQueue.pop();

  const CodeGenRegister::SuperRegList &Leads = SubReg->LeadingSuperRegs;
  for (unsigned i = 0, e = Leads.size(); i != e; ++i) {
    CodeGenRegister *Cand = const_cast<CodeGenRegister*>(Leads[i]);
    // Already got this sub-register?
    if (Cand == this || getSubRegIndex(Cand))
      continue;
    // Check if each component of Cand is already a sub-register.
    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__))
           "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__));
    if (Cand->ExplicitSubRegs.size() == 1)
      continue;
    SmallVector<CodeGenSubRegIndex*, 8> Parts;
    // We know that the first component is (SubRegIdx,SubReg). However we
    // may still need to split it into smaller subregister parts.
    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__));
    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__));
    for (CodeGenRegister *SubReg : Cand->ExplicitSubRegs) {
      if (CodeGenSubRegIndex *SubRegIdx = getSubRegIndex(SubReg)) {
        if (SubRegIdx->ConcatenationOf.empty())
          Parts.push_back(SubRegIdx);
        else
          append_range(Parts, SubRegIdx->ConcatenationOf);
      } else {
        // Sub-register doesn't exist.
        Parts.clear();
        break;
      }
    }
    // There is nothing to do if some Cand sub-register is not part of this
    // register.
    if (Parts.empty())
      continue;

    // Each part of Cand is a sub-register of this. Make the full Cand also
    // a sub-register with a concatenated sub-register index.
    CodeGenSubRegIndex *Concat = RegBank.getConcatSubRegIndex(Parts);
    std::pair<CodeGenSubRegIndex*,CodeGenRegister*> NewSubReg =
        std::make_pair(Concat, Cand);

    if (!SubRegs.insert(NewSubReg).second)
      continue;

    // We inserted a new subregister.
    NewSubRegs.push_back(NewSubReg);
    SubRegQueue.push(NewSubReg);
    SubReg2Idx.insert(std::make_pair(Cand, Concat));
  }
}

// Create sub-register index composition maps for the synthesized indices.
for (unsigned i = 0, e = NewSubRegs.size(); i != e; ++i) {
  CodeGenSubRegIndex *NewIdx = NewSubRegs[i].first;
  CodeGenRegister *NewSubReg = NewSubRegs[i].second;
  for (auto SubReg : NewSubReg->SubRegs) {
    CodeGenSubRegIndex *SubIdx = getSubRegIndex(SubReg.second);
    if (!SubIdx)
      PrintFatalError(TheDef->getLoc(), "No SubRegIndex for " +
                                            SubReg.second->getName() +
                                            " in " + getName());
    NewIdx->addComposite(SubReg.first, SubIdx);
  }
}
542}

544void CodeGenRegister::computeSuperRegs(CodeGenRegBank &RegBank) {
// Only visit each register once.
if (SuperRegsComplete)
  return;
SuperRegsComplete = true;

// Make sure all sub-registers have been visited first, so the super-reg
// lists will be topologically ordered.
for (auto SubReg : SubRegs)
  SubReg.second->computeSuperRegs(RegBank);

// Now add this as a super-register on all sub-registers.
// Also compute the TopoSigId in post-order.
TopoSigId Id;
for (auto SubReg : SubRegs) {
  // Topological signature computed from SubIdx, TopoId(SubReg).
  // Loops and idempotent indices have TopoSig = ~0u.
  Id.push_back(SubReg.first->EnumValue);
  Id.push_back(SubReg.second->TopoSig);

  // Don't add duplicate entries.
  if (!SubReg.second->SuperRegs.empty() &&
      SubReg.second->SuperRegs.back() == this)
    continue;
  SubReg.second->SuperRegs.push_back(this);
}
TopoSig = RegBank.getTopoSig(Id);
571}

573void
574CodeGenRegister::addSubRegsPreOrder(SetVector<const CodeGenRegister*> &OSet,
                                  CodeGenRegBank &RegBank) const {
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__));
for (unsigned i = 0, e = ExplicitSubRegs.size(); i != e; ++i) {
  CodeGenRegister *SR = ExplicitSubRegs[i];
  if (OSet.insert(SR))
    SR->addSubRegsPreOrder(OSet, RegBank);
}
// Add any secondary sub-registers that weren't part of the explicit tree.
for (auto SubReg : SubRegs)
  OSet.insert(SubReg.second);
585}

587// Get the sum of this register's unit weights.
588unsigned CodeGenRegister::getWeight(const CodeGenRegBank &RegBank) const {
unsigned Weight = 0;
for (unsigned RegUnit : RegUnits) {
  Weight += RegBank.getRegUnit(RegUnit).Weight;
}
return Weight;
594}

596//===----------------------------------------------------------------------===//
597//                               RegisterTuples
598//===----------------------------------------------------------------------===//

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 {

605struct TupleExpander : SetTheory::Expander {
// Reference to SynthDefs in the containing CodeGenRegBank, to keep track of
// the synthesized definitions for their lifetime.
std::vector<std::unique_ptr<Record>> &SynthDefs;

TupleExpander(std::vector<std::unique_ptr<Record>> &SynthDefs)
    : SynthDefs(SynthDefs) {}

void expand(SetTheory &ST, Record *Def, SetTheory::RecSet &Elts) override {
  std::vector<Record*> Indices = Def->getValueAsListOfDefs("SubRegIndices");
  unsigned Dim = Indices.size();
  ListInit *SubRegs = Def->getValueAsListInit("SubRegs");
  if (Dim != SubRegs->size())
    PrintFatalError(Def->getLoc(), "SubRegIndices and SubRegs size mismatch");
  if (Dim < 2)
    PrintFatalError(Def->getLoc(),
                    "Tuples must have at least 2 sub-registers");

  // Evaluate the sub-register lists to be zipped.
  unsigned Length = ~0u;
  SmallVector<SetTheory::RecSet, 4> Lists(Dim);
  for (unsigned i = 0; i != Dim; ++i) {
    ST.evaluate(SubRegs->getElement(i), Lists[i], Def->getLoc());
    Length = std::min(Length, unsigned(Lists[i].size()));
  }

  if (Length == 0)
    return;

  // Precompute some types.
  Record *RegisterCl = Def->getRecords().getClass("Register");
  RecTy *RegisterRecTy = RecordRecTy::get(RegisterCl);
  std::vector<StringRef> RegNames =
    Def->getValueAsListOfStrings("RegAsmNames");

  // Zip them up.
  RecordKeeper &RK = Def->getRecords();
  for (unsigned n = 0; n != Length; ++n) {
    std::string Name;
    Record *Proto = Lists[0][n];
    std::vector<Init*> Tuple;
    for (unsigned i = 0; i != Dim; ++i) {
      Record *Reg = Lists[i][n];
      if (i) Name += '_';
      Name += Reg->getName();
      Tuple.push_back(DefInit::get(Reg));
    }

    // Take the cost list of the first register in the tuple.
    ListInit *CostList = Proto->getValueAsListInit("CostPerUse");
    SmallVector<Init *, 2> CostPerUse;
    CostPerUse.insert(CostPerUse.end(), CostList->begin(), CostList->end());

    StringInit *AsmName = StringInit::get(RK, "");
    if (!RegNames.empty()) {
      if (RegNames.size() <= n)
        PrintFatalError(Def->getLoc(),
                        "Register tuple definition missing name for '" +
                          Name + "'.");
      AsmName = StringInit::get(RK, RegNames[n]);
    }

    // Create a new Record representing the synthesized register. This record
    // is only for consumption by CodeGenRegister, it is not added to the
    // RecordKeeper.
    SynthDefs.emplace_back(
        std::make_unique<Record>(Name, Def->getLoc(), Def->getRecords()));
    Record *NewReg = SynthDefs.back().get();
    Elts.insert(NewReg);

    // Copy Proto super-classes.
    ArrayRef<std::pair<Record *, SMRange>> Supers = Proto->getSuperClasses();
    for (const auto &SuperPair : Supers)
      NewReg->addSuperClass(SuperPair.first, SuperPair.second);

    // Copy Proto fields.
    for (unsigned i = 0, e = Proto->getValues().size(); i != e; ++i) {
      RecordVal RV = Proto->getValues()[i];

      // Skip existing fields, like NAME.
      if (NewReg->getValue(RV.getNameInit()))
        continue;

      StringRef Field = RV.getName();

      // Replace the sub-register list with Tuple.
      if (Field == "SubRegs")
        RV.setValue(ListInit::get(Tuple, RegisterRecTy));

      if (Field == "AsmName")
        RV.setValue(AsmName);

      // CostPerUse is aggregated from all Tuple members.
      if (Field == "CostPerUse")
        RV.setValue(ListInit::get(CostPerUse, CostList->getElementType()));

      // Composite registers are always covered by sub-registers.
      if (Field == "CoveredBySubRegs")
        RV.setValue(BitInit::get(RK, true));

      // Copy fields from the RegisterTuples def.
      if (Field == "SubRegIndices" ||
          Field == "CompositeIndices") {
        NewReg->addValue(*Def->getValue(Field));
        continue;
      }

      // Some fields get their default uninitialized value.
      if (Field == "DwarfNumbers" ||
          Field == "DwarfAlias" ||
          Field == "Aliases") {
        if (const RecordVal *DefRV = RegisterCl->getValue(Field))
          NewReg->addValue(*DefRV);
        continue;
      }

      // Everything else is copied from Proto.
      NewReg->addValue(RV);
    }
  }
}
726};

728} // end anonymous namespace

730//===----------------------------------------------------------------------===//
731//                            CodeGenRegisterClass
732//===----------------------------------------------------------------------===//

734static void sortAndUniqueRegisters(CodeGenRegister::Vec &M) {
llvm::sort(M, deref<std::less<>>());
M.erase(std::unique(M.begin(), M.end(), deref<std::equal_to<>>()), M.end());
737}

739CodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank, Record *R)
  : TheDef(R), Name(std::string(R->getName())),
    TopoSigs(RegBank.getNumTopoSigs()), EnumValue(-1), TSFlags(0) {
GeneratePressureSet = R->getValueAsBit("GeneratePressureSet");
std::vector<Record*> TypeList = R->getValueAsListOfDefs("RegTypes");
if (TypeList.empty())
  PrintFatalError(R->getLoc(), "RegTypes list must not be empty!");
for (unsigned i = 0, e = TypeList.size(); i != e; ++i) {
  Record *Type = TypeList[i];
  if (!Type->isSubClassOf("ValueType"))
    PrintFatalError(R->getLoc(),
                    "RegTypes list member '" + Type->getName() +
                        "' does not derive from the ValueType class!");
  VTs.push_back(getValueTypeByHwMode(Type, RegBank.getHwModes()));
}

// Allocation order 0 is the full set. AltOrders provides others.
const SetTheory::RecVec *Elements = RegBank.getSets().expand(R);
ListInit *AltOrders = R->getValueAsListInit("AltOrders");
Orders.resize(1 + AltOrders->size());

// Default allocation order always contains all registers.
Artificial = true;
for (unsigned i = 0, e = Elements->size(); i != e; ++i) {
  Orders[0].push_back((*Elements)[i]);
  const CodeGenRegister *Reg = RegBank.getReg((*Elements)[i]);
  Members.push_back(Reg);
  Artificial &= Reg->Artificial;
  TopoSigs.set(Reg->getTopoSig());
}
sortAndUniqueRegisters(Members);

// Alternative allocation orders may be subsets.
SetTheory::RecSet Order;
for (unsigned i = 0, e = AltOrders->size(); i != e; ++i) {
  RegBank.getSets().evaluate(AltOrders->getElement(i), Order, R->getLoc());
  Orders[1 + i].append(Order.begin(), Order.end());
  // Verify that all altorder members are regclass members.
  while (!Order.empty()) {
    CodeGenRegister *Reg = RegBank.getReg(Order.back());
    Order.pop_back();
    if (!contains(Reg))
      PrintFatalError(R->getLoc(), " AltOrder register " + Reg->getName() +
                    " is not a class member");
  }
}

Namespace = R->getValueAsString("Namespace");

if (const RecordVal *RV = R->getValue("RegInfos"))
  if (DefInit *DI = dyn_cast_or_null<DefInit>(RV->getValue()))
    RSI = RegSizeInfoByHwMode(DI->getDef(), RegBank.getHwModes());
unsigned Size = R->getValueAsInt("Size");
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__))
       "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__));
if (!RSI.hasDefault()) {
  RegSizeInfo RI;
  RI.RegSize = RI.SpillSize = Size ? Size
                                   : VTs[0].getSimple().getSizeInBits();
  RI.SpillAlignment = R->getValueAsInt("Alignment");
  RSI.insertRegSizeForMode(DefaultMode, RI);
}

CopyCost = R->getValueAsInt("CopyCost");
Allocatable = R->getValueAsBit("isAllocatable");
AltOrderSelect = R->getValueAsString("AltOrderSelect");
int AllocationPriority = R->getValueAsInt("AllocationPriority");
if (!isUInt<5>(AllocationPriority))
  PrintFatalError(R->getLoc(), "AllocationPriority out of range [0,31]");
this->AllocationPriority = AllocationPriority;

GlobalPriority = R->getValueAsBit("GlobalPriority");

BitsInit *TSF = R->getValueAsBitsInit("TSFlags");
for (unsigned I = 0, E = TSF->getNumBits(); I != E; ++I) {
  BitInit *Bit = cast<BitInit>(TSF->getBit(I));
  TSFlags |= uint8_t(Bit->getValue()) << I;
}
817}

819// Create an inferred register class that was missing from the .td files.
820// Most properties will be inherited from the closest super-class after the
821// class structure has been computed.
822CodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank,
                                         StringRef Name, Key Props)
  : Members(*Props.Members), TheDef(nullptr), Name(std::string(Name)),
    TopoSigs(RegBank.getNumTopoSigs()), EnumValue(-1), RSI(Props.RSI),
    CopyCost(0), Allocatable(true), AllocationPriority(0),
    GlobalPriority(false), TSFlags(0) {
Artificial = true;
GeneratePressureSet = false;
for (const auto R : Members) {
  TopoSigs.set(R->getTopoSig());
  Artificial &= R->Artificial;
}
834}

836// Compute inherited propertied for a synthesized register class.
837void CodeGenRegisterClass::inheritProperties(CodeGenRegBank &RegBank) {
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", 838, __extension__
 __PRETTY_FUNCTION__));
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", 839, __extension__
 __PRETTY_FUNCTION__));

// The last super-class is the smallest one.
CodeGenRegisterClass &Super = *SuperClasses.back();

// Most properties are copied directly.
// Exceptions are members, size, and alignment
Namespace = Super.Namespace;
VTs = Super.VTs;
CopyCost = Super.CopyCost;
// Check for allocatable superclasses.
Allocatable = any_of(SuperClasses, [&](const CodeGenRegisterClass *S) {
  return S->Allocatable;
});
AltOrderSelect = Super.AltOrderSelect;
AllocationPriority = Super.AllocationPriority;
GlobalPriority = Super.GlobalPriority;
TSFlags = Super.TSFlags;
GeneratePressureSet |= Super.GeneratePressureSet;

// Copy all allocation orders, filter out foreign registers from the larger
// super-class.
Orders.resize(Super.Orders.size());
for (unsigned i = 0, ie = Super.Orders.size(); i != ie; ++i)
  for (unsigned j = 0, je = Super.Orders[i].size(); j != je; ++j)
    if (contains(RegBank.getReg(Super.Orders[i][j])))
      Orders[i].push_back(Super.Orders[i][j]);
866}

868bool CodeGenRegisterClass::hasType(const ValueTypeByHwMode &VT) const {
if (llvm::is_contained(VTs, VT))
  return true;

// If VT is not identical to any of this class's types, but is a simple
// type, check if any of the types for this class contain it under some
// mode.
// The motivating example came from RISC-V, where (likely because of being
// guarded by "64-bit" predicate), the type of X5 was {*:[i64]}, but the
// type in GRC was {*:[i32], m1:[i64]}.
if (VT.isSimple()) {
  MVT T = VT.getSimple();
  for (const ValueTypeByHwMode &OurVT : VTs) {
    if (llvm::count_if(OurVT, [T](auto &&P) { return P.second == T; }))
      return true;
  }
}
return false;
886}

888bool CodeGenRegisterClass::contains(const CodeGenRegister *Reg) const {
return std::binary_search(Members.begin(), Members.end(), Reg,
                          deref<std::less<>>());
891}

893unsigned CodeGenRegisterClass::getWeight(const CodeGenRegBank& RegBank) const {
if (TheDef && !TheDef->isValueUnset("Weight"))
  return TheDef->getValueAsInt("Weight");

if (Members.empty() || Artificial)
  return 0;

return (*Members.begin())->getWeight(RegBank);
901}

903namespace llvm {

raw_ostream &operator<<(raw_ostream &OS, const CodeGenRegisterClass::Key &K) {
  OS << "{ " << K.RSI;
  for (const auto R : *K.Members)
    OS << ", " << R->getName();
  return OS << " }";
}

912} // end namespace llvm

914// This is a simple lexicographical order that can be used to search for sets.
915// It is not the same as the topological order provided by TopoOrderRC.
916bool CodeGenRegisterClass::Key::
917operator<(const CodeGenRegisterClass::Key &B) const {
assert(Members && B.Members)(static_cast <bool> (Members && B.Members) ? void
 (0) : __assert_fail ("Members && B.Members", "llvm/utils/TableGen/CodeGenRegisters.cpp"
, 918, __extension__ __PRETTY_FUNCTION__));
return std::tie(*Members, RSI) < std::tie(*B.Members, B.RSI);
920}

922// Returns true if RC is a strict subclass.
923// RC is a sub-class of this class if it is a valid replacement for any
924// instruction operand where a register of this classis required. It must
925// satisfy these conditions:
926//
927// 1. All RC registers are also in this.
928// 2. The RC spill size must not be smaller than our spill size.
929// 3. RC spill alignment must be compatible with ours.
930//
931static bool testSubClass(const CodeGenRegisterClass *A,
                       const CodeGenRegisterClass *B) {
return A->RSI.isSubClassOf(B->RSI) &&
       std::includes(A->getMembers().begin(), A->getMembers().end(),
                     B->getMembers().begin(), B->getMembers().end(),
                     deref<std::less<>>());
937}

939/// Sorting predicate for register classes.  This provides a topological
940/// ordering that arranges all register classes before their sub-classes.
941///
942/// Register classes with the same registers, spill size, and alignment form a
943/// clique.  They will be ordered alphabetically.
944///
945static bool TopoOrderRC(const CodeGenRegisterClass &PA,
                      const CodeGenRegisterClass &PB) {
auto *A = &PA;
auto *B = &PB;
if (A == B)
  return false;

if (A->RSI < B->RSI)
  return true;
if (A->RSI != B->RSI)
  return false;

// Order by descending set size.  Note that the classes' allocation order may
// not have been computed yet.  The Members set is always vaild.
if (A->getMembers().size() > B->getMembers().size())
  return true;
if (A->getMembers().size() < B->getMembers().size())
  return false;

// Finally order by name as a tie breaker.
return StringRef(A->getName()) < B->getName();
966}

968std::string CodeGenRegisterClass::getQualifiedName() const {
if (Namespace.empty())
  return getName();
else
  return (Namespace + "::" + getName()).str();
973}

975// Compute sub-classes of all register classes.
976// Assume the classes are ordered topologically.
977void CodeGenRegisterClass::computeSubClasses(CodeGenRegBank &RegBank) {
auto &RegClasses = RegBank.getRegClasses();

// Visit backwards so sub-classes are seen first.
for (auto I = RegClasses.rbegin(), E = RegClasses.rend(); I != E; ++I) {
  CodeGenRegisterClass &RC = *I;
  RC.SubClasses.resize(RegClasses.size());
  RC.SubClasses.set(RC.EnumValue);
  if (RC.Artificial)
    continue;

  // Normally, all subclasses have IDs >= rci, unless RC is part of a clique.
  for (auto I2 = I.base(), E2 = RegClasses.end(); I2 != E2; ++I2) {
    CodeGenRegisterClass &SubRC = *I2;
    if (RC.SubClasses.test(SubRC.EnumValue))
      continue;
    if (!testSubClass(&RC, &SubRC))
      continue;
    // SubRC is a sub-class. Grap all its sub-classes so we won't have to
    // check them again.
    RC.SubClasses |= SubRC.SubClasses;
  }

  // Sweep up missed clique members.  They will be immediately preceding RC.
  for (auto I2 = std::next(I); I2 != E && testSubClass(&RC, &*I2); ++I2)
    RC.SubClasses.set(I2->EnumValue);
}

// Compute the SuperClasses lists from the SubClasses vectors.
for (auto &RC : RegClasses) {
  const BitVector &SC = RC.getSubClasses();
  auto I = RegClasses.begin();
  for (int s = 0, next_s = SC.find_first(); next_s != -1;
       next_s = SC.find_next(s)) {
    std::advance(I, next_s - s);
    s = next_s;
    if (&*I == &RC)
      continue;
    I->SuperClasses.push_back(&RC);
  }
}

// With the class hierarchy in place, let synthesized register classes inherit
// properties from their closest super-class. The iteration order here can
// propagate properties down multiple levels.
for (auto &RC : RegClasses)
  if (!RC.getDef())
    RC.inheritProperties(RegBank);
1025}

1027std::optional<std::pair<CodeGenRegisterClass *, CodeGenRegisterClass *>>
1028CodeGenRegisterClass::getMatchingSubClassWithSubRegs(
  CodeGenRegBank &RegBank, const CodeGenSubRegIndex *SubIdx) const {
auto SizeOrder = [this](const CodeGenRegisterClass *A,
                    const CodeGenRegisterClass *B) {
  // If there are multiple, identical register classes, prefer the original
  // register class.
  if (A == B)
    return false;
  if (A->getMembers().size() == B->getMembers().size())
    return A == this;
  return A->getMembers().size() > B->getMembers().size();
};

auto &RegClasses = RegBank.getRegClasses();

// Find all the subclasses of this one that fully support the sub-register
// index and order them by size. BiggestSuperRC should always be first.
CodeGenRegisterClass *BiggestSuperRegRC = getSubClassWithSubReg(SubIdx);
if (!BiggestSuperRegRC)
  return std::nullopt;
BitVector SuperRegRCsBV = BiggestSuperRegRC->getSubClasses();
std::vector<CodeGenRegisterClass *> SuperRegRCs;
for (auto &RC : RegClasses)
  if (SuperRegRCsBV[RC.EnumValue])
    SuperRegRCs.emplace_back(&RC);
llvm::stable_sort(SuperRegRCs, SizeOrder);

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", 1056, __extension__
 __PRETTY_FUNCTION__))
       "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", 1056, __extension__
 __PRETTY_FUNCTION__));

// Find all the subreg classes and order them by size too.
std::vector<std::pair<CodeGenRegisterClass *, BitVector>> SuperRegClasses;
for (auto &RC: RegClasses) {
  BitVector SuperRegClassesBV(RegClasses.size());
  RC.getSuperRegClasses(SubIdx, SuperRegClassesBV);
  if (SuperRegClassesBV.any())
    SuperRegClasses.push_back(std::make_pair(&RC, SuperRegClassesBV));
}
llvm::sort(SuperRegClasses,
           [&](const std::pair<CodeGenRegisterClass *, BitVector> &A,
               const std::pair<CodeGenRegisterClass *, BitVector> &B) {
             return SizeOrder(A.first, B.first);
           });

// Find the biggest subclass and subreg class such that R:subidx is in the
// subreg class for all R in subclass.
//
// For example:
// All registers in X86's GR64 have a sub_32bit subregister but no class
// exists that contains all the 32-bit subregisters because GR64 contains RIP
// but GR32 does not contain EIP. Instead, we constrain SuperRegRC to
// GR32_with_sub_8bit (which is identical to GR32_with_sub_32bit) and then,
// having excluded RIP, we are able to find a SubRegRC (GR32).
CodeGenRegisterClass *ChosenSuperRegClass = nullptr;
CodeGenRegisterClass *SubRegRC = nullptr;
for (auto *SuperRegRC : SuperRegRCs) {
  for (const auto &SuperRegClassPair : SuperRegClasses) {
    const BitVector &SuperRegClassBV = SuperRegClassPair.second;
    if (SuperRegClassBV[SuperRegRC->EnumValue]) {
      SubRegRC = SuperRegClassPair.first;
      ChosenSuperRegClass = SuperRegRC;

      // If SubRegRC is bigger than SuperRegRC then there are members of
      // SubRegRC that don't have super registers via SubIdx. Keep looking to
      // find a better fit and fall back on this one if there isn't one.
      //
      // This is intended to prevent X86 from making odd choices such as
      // picking LOW32_ADDR_ACCESS_RBP instead of GR32 in the example above.
      // LOW32_ADDR_ACCESS_RBP is a valid choice but contains registers that
      // aren't subregisters of SuperRegRC whereas GR32 has a direct 1:1
      // mapping.
      if (SuperRegRC->getMembers().size() >= SubRegRC->getMembers().size())
        return std::make_pair(ChosenSuperRegClass, SubRegRC);
    }
  }

  // If we found a fit but it wasn't quite ideal because SubRegRC had excess
  // registers, then we're done.
  if (ChosenSuperRegClass)
    return std::make_pair(ChosenSuperRegClass, SubRegRC);
}

return std::nullopt;
1111}

1113void CodeGenRegisterClass::getSuperRegClasses(const CodeGenSubRegIndex *SubIdx,
                                            BitVector &Out) const {
auto FindI = SuperRegClasses.find(SubIdx);
if (FindI == SuperRegClasses.end())
  return;
for (CodeGenRegisterClass *RC : FindI->second)
  Out.set(RC->EnumValue);
1120}

1122// Populate a unique sorted list of units from a register set.
1123void CodeGenRegisterClass::buildRegUnitSet(const CodeGenRegBank &RegBank,
std::vector<unsigned> &RegUnits) const {
std::vector<unsigned> TmpUnits;
for (RegUnitIterator UnitI(Members); UnitI.isValid(); ++UnitI) {
  const RegUnit &RU = RegBank.getRegUnit(*UnitI);
  if (!RU.Artificial)
    TmpUnits.push_back(*UnitI);
}
llvm::sort(TmpUnits);
std::unique_copy(TmpUnits.begin(), TmpUnits.end(),
                 std::back_inserter(RegUnits));
1134}

1136//===----------------------------------------------------------------------===//
1137//                           CodeGenRegisterCategory
1138//===----------------------------------------------------------------------===//

1140CodeGenRegisterCategory::CodeGenRegisterCategory(CodeGenRegBank &RegBank,
                                               Record *R)
  : TheDef(R), Name(std::string(R->getName())) {
for (Record *RegClass : R->getValueAsListOfDefs("Classes"))
  Classes.push_back(RegBank.getRegClass(RegClass));
1145}

1147//===----------------------------------------------------------------------===//
1148//                               CodeGenRegBank
1149//===----------------------------------------------------------------------===//

1151CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records,
                             const CodeGenHwModes &Modes) : CGH(Modes) {
// Configure register Sets to understand register classes and tuples.
Sets.addFieldExpander("RegisterClass", "MemberList");
Sets.addFieldExpander("CalleeSavedRegs", "SaveList");
Sets.addExpander("RegisterTuples",
                 std::make_unique<TupleExpander>(SynthDefs));

// Read in the user-defined (named) sub-register indices.
// More indices will be synthesized later.
std::vector<Record*> SRIs = Records.getAllDerivedDefinitions("SubRegIndex");
llvm::sort(SRIs, LessRecord());
for (unsigned i = 0, e = SRIs.size(); i != e; ++i)
  getSubRegIdx(SRIs[i]);
// Build composite maps from ComposedOf fields.
for (auto &Idx : SubRegIndices)
  Idx.updateComponents(*this);

// Read in the register definitions.
std::vector<Record*> Regs = Records.getAllDerivedDefinitions("Register");
llvm::sort(Regs, LessRecordRegister());
// Assign the enumeration values.
for (unsigned i = 0, e = Regs.size(); i != e; ++i)
  getReg(Regs[i]);

// Expand tuples and number the new registers.
std::vector<Record*> Tups =
  Records.getAllDerivedDefinitions("RegisterTuples");

for (Record *R : Tups) {
  std::vector<Record *> TupRegs = *Sets.expand(R);
  llvm::sort(TupRegs, LessRecordRegister());
  for (Record *RC : TupRegs)
    getReg(RC);
}

// Now all the registers are known. Build the object graph of explicit
// register-register references.
for (auto &Reg : Registers)
  Reg.buildObjectGraph(*this);

// Compute register name map.
for (auto &Reg : Registers)
  // FIXME: This could just be RegistersByName[name] = register, except that
  // causes some failures in MIPS - perhaps they have duplicate register name
  // entries? (or maybe there's a reason for it - I don't know much about this
  // code, just drive-by refactoring)
  RegistersByName.insert(
      std::make_pair(Reg.TheDef->getValueAsString("AsmName"), &Reg));

// Precompute all sub-register maps.
// This will create Composite entries for all inferred sub-register indices.
for (auto &Reg : Registers)
  Reg.computeSubRegs(*this);

// Compute transitive closure of subregister index ConcatenationOf vectors
// and initialize ConcatIdx map.
for (CodeGenSubRegIndex &SRI : SubRegIndices) {
  SRI.computeConcatTransitiveClosure();
  if (!SRI.ConcatenationOf.empty())
    ConcatIdx.insert(std::make_pair(
        SmallVector<CodeGenSubRegIndex*,8>(SRI.ConcatenationOf.begin(),
                                           SRI.ConcatenationOf.end()), &SRI));
}

// Infer even more sub-registers by combining leading super-registers.
for (auto &Reg : Registers)
  if (Reg.CoveredBySubRegs)
    Reg.computeSecondarySubRegs(*this);

// After the sub-register graph is complete, compute the topologically
// ordered SuperRegs list.
for (auto &Reg : Registers)
  Reg.computeSuperRegs(*this);

// For each pair of Reg:SR, if both are non-artificial, mark the
// corresponding sub-register index as non-artificial.
for (auto &Reg : Registers) {
  if (Reg.Artificial)
    continue;
  for (auto P : Reg.getSubRegs()) {
    const CodeGenRegister *SR = P.second;
    if (!SR->Artificial)
      P.first->Artificial = false;
  }
}

// Native register units are associated with a leaf register. They've all been
// discovered now.
NumNativeRegUnits = RegUnits.size();

// Read in register class definitions.
std::vector<Record*> RCs = Records.getAllDerivedDefinitions("RegisterClass");
if (RCs.empty())
  PrintFatalError("No 'RegisterClass' subclasses defined!");

// Allocate user-defined register classes.
for (auto *R : RCs) {
  RegClasses.emplace_back(*this, R);
  CodeGenRegisterClass &RC = RegClasses.back();
  if (!RC.Artificial)
    addToMaps(&RC);
}

// Infer missing classes to create a full algebra.
computeInferredRegisterClasses();

// Order register classes topologically and assign enum values.
RegClasses.sort(TopoOrderRC);
unsigned i = 0;
for (auto &RC : RegClasses)
  RC.EnumValue = i++;
CodeGenRegisterClass::computeSubClasses(*this);

// Read in the register category definitions.
std::vector<Record *> RCats =
    Records.getAllDerivedDefinitions("RegisterCategory");
for (auto *R : RCats)
  RegCategories.emplace_back(*this, R);
1270}

1272// Create a synthetic CodeGenSubRegIndex without a corresponding Record.
1273CodeGenSubRegIndex*
1274CodeGenRegBank::createSubRegIndex(StringRef Name, StringRef Namespace) {
SubRegIndices.emplace_back(Name, Namespace, SubRegIndices.size() + 1);
return &SubRegIndices.back();
1277}

1279CodeGenSubRegIndex *CodeGenRegBank::getSubRegIdx(Record *Def) {
CodeGenSubRegIndex *&Idx = Def2SubRegIdx[Def];
if (Idx)
  return Idx;
SubRegIndices.emplace_back(Def, SubRegIndices.size() + 1);
Idx = &SubRegIndices.back();
return Idx;
1286}

1288const CodeGenSubRegIndex *
1289CodeGenRegBank::findSubRegIdx(const Record* Def) const {
return Def2SubRegIdx.lookup(Def);
1291}

1293CodeGenRegister *CodeGenRegBank::getReg(Record *Def) {
CodeGenRegister *&Reg = Def2Reg[Def];
if (Reg)
  return Reg;
Registers.emplace_back(Def, Registers.size() + 1);
Reg = &Registers.back();
return Reg;
1300}

1302void CodeGenRegBank::addToMaps(CodeGenRegisterClass *RC) {
if (Record *Def = RC->getDef())
  Def2RC.insert(std::make_pair(Def, RC));

// Duplicate classes are rejected by insert().
// That's OK, we only care about the properties handled by CGRC::Key.
CodeGenRegisterClass::Key K(*RC);
Key2RC.insert(std::make_pair(K, RC));
1310}

1312// Create a synthetic sub-class if it is missing.
1313CodeGenRegisterClass*
1314CodeGenRegBank::getOrCreateSubClass(const CodeGenRegisterClass *RC,
                                  const CodeGenRegister::Vec *Members,
                                  StringRef Name) {
// Synthetic sub-class has the same size and alignment as RC.
CodeGenRegisterClass::Key K(Members, RC->RSI);
RCKeyMap::const_iterator FoundI = Key2RC.find(K);
if (FoundI != Key2RC.end())
  return FoundI->second;

// Sub-class doesn't exist, create a new one.
RegClasses.emplace_back(*this, Name, K);
addToMaps(&RegClasses.back());
return &RegClasses.back();
1327}

1329CodeGenRegisterClass *CodeGenRegBank::getRegClass(const Record *Def) const {
if (CodeGenRegisterClass *RC = Def2RC.lookup(Def))
  return RC;

PrintFatalError(Def->getLoc(), "Not a known RegisterClass!");
1334}

1336CodeGenSubRegIndex*
1337CodeGenRegBank::getCompositeSubRegIndex(CodeGenSubRegIndex *A,
                                      CodeGenSubRegIndex *B) {
// Look for an existing entry.
CodeGenSubRegIndex *Comp = A->compose(B);
if (Comp)
  return Comp;

// None exists, synthesize one.
std::string Name = A->getName() + "_then_" + B->getName();
Comp = createSubRegIndex(Name, A->getNamespace());
A->addComposite(B, Comp);
return Comp;
1349}

1351CodeGenSubRegIndex *CodeGenRegBank::
1352getConcatSubRegIndex(const SmallVector<CodeGenSubRegIndex *, 8> &Parts) {
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", 1353, __extension__
 __PRETTY_FUNCTION__));
1354#ifndef NDEBUG
for (CodeGenSubRegIndex *Idx : Parts) {
  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", 1356, __extension__
 __PRETTY_FUNCTION__));
}
1358#endif

// Look for an existing entry.
CodeGenSubRegIndex *&Idx = ConcatIdx[Parts];
if (Idx)
  return Idx;

// None exists, synthesize one.
std::string Name = Parts.front()->getName();
// Determine whether all parts are contiguous.
bool isContinuous = true;
unsigned Size = Parts.front()->Size;
unsigned LastOffset = Parts.front()->Offset;
unsigned LastSize = Parts.front()->Size;
unsigned UnknownSize = (uint16_t)-1;
for (unsigned i = 1, e = Parts.size(); i != e; ++i) {
  Name += '_';
  Name += Parts[i]->getName();
  if (Size == UnknownSize || Parts[i]->Size == UnknownSize)
    Size = UnknownSize;
  else
    Size += Parts[i]->Size;
  if (LastSize == UnknownSize || Parts[i]->Offset != (LastOffset + LastSize))
    isContinuous = false;
  LastOffset = Parts[i]->Offset;
  LastSize = Parts[i]->Size;
}
Idx = createSubRegIndex(Name, Parts.front()->getNamespace());
Idx->Size = Size;
Idx->Offset = isContinuous ? Parts.front()->Offset : -1;
Idx->ConcatenationOf.assign(Parts.begin(), Parts.end());
return Idx;
1390}

1392void CodeGenRegBank::computeComposites() {
using RegMap = std::map<const CodeGenRegister*, const CodeGenRegister*>;

// Subreg -> { Reg->Reg }, where the right-hand side is the mapping from
// register to (sub)register associated with the action of the left-hand
// side subregister.
std::map<const CodeGenSubRegIndex*, RegMap> SubRegAction;
for (const CodeGenRegister &R : Registers) {
  const CodeGenRegister::SubRegMap &SM = R.getSubRegs();
  for (std::pair<const CodeGenSubRegIndex*, const CodeGenRegister*> P : SM)
    SubRegAction[P.first].insert({&R, P.second});
}

// Calculate the composition of two subregisters as compositions of their
// associated actions.
auto compose = [&SubRegAction] (const CodeGenSubRegIndex *Sub1,
                                const CodeGenSubRegIndex *Sub2) {
  RegMap C;
  const RegMap &Img1 = SubRegAction.at(Sub1);
  const RegMap &Img2 = SubRegAction.at(Sub2);
  for (std::pair<const CodeGenRegister*, const CodeGenRegister*> P : Img1) {
    auto F = Img2.find(P.second);
    if (F != Img2.end())
      C.insert({P.first, F->second});
  }
  return C;
};

// Check if the two maps agree on the intersection of their domains.
auto agree = [] (const RegMap &Map1, const RegMap &Map2) {
  // Technically speaking, an empty map agrees with any other map, but
  // this could flag false positives. We're interested in non-vacuous
  // agreements.
  if (Map1.empty() || Map2.empty())
    return false;
  for (std::pair<const CodeGenRegister*, const CodeGenRegister*> P : Map1) {
    auto F = Map2.find(P.first);
    if (F == Map2.end() || P.second != F->second)
      return false;
  }
  return true;
};

using CompositePair = std::pair<const CodeGenSubRegIndex*,
                                const CodeGenSubRegIndex*>;
SmallSet<CompositePair,4> UserDefined;
for (const CodeGenSubRegIndex &Idx : SubRegIndices)
  for (auto P : Idx.getComposites())
    UserDefined.insert(std::make_pair(&Idx, P.first));

// Keep track of TopoSigs visited. We only need to visit each TopoSig once,
// and many registers will share TopoSigs on regular architectures.
BitVector TopoSigs(getNumTopoSigs());

for (const auto &Reg1 : Registers) {
  // Skip identical subreg structures already processed.
  if (TopoSigs.test(Reg1.getTopoSig()))
    continue;
  TopoSigs.set(Reg1.getTopoSig());

  const CodeGenRegister::SubRegMap &SRM1 = Reg1.getSubRegs();
  for (auto I1 : SRM1) {
    CodeGenSubRegIndex *Idx1 = I1.first;
    CodeGenRegister *Reg2 = I1.second;
    // Ignore identity compositions.
    if (&Reg1 == Reg2)
      continue;
    const CodeGenRegister::SubRegMap &SRM2 = Reg2->getSubRegs();
    // Try composing Idx1 with another SubRegIndex.
    for (auto I2 : SRM2) {
      CodeGenSubRegIndex *Idx2 = I2.first;
      CodeGenRegister *Reg3 = I2.second;
      // Ignore identity compositions.
      if (Reg2 == Reg3)
        continue;
      // OK Reg1:IdxPair == Reg3. Find the index with Reg:Idx == Reg3.
      CodeGenSubRegIndex *Idx3 = Reg1.getSubRegIndex(Reg3);
      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", 1469, __extension__
 __PRETTY_FUNCTION__));

      // Conflicting composition? Emit a warning but allow it.
      if (CodeGenSubRegIndex *Prev = Idx1->addComposite(Idx2, Idx3)) {
        // If the composition was not user-defined, always emit a warning.
        if (!UserDefined.count({Idx1, Idx2}) ||
            agree(compose(Idx1, Idx2), SubRegAction.at(Idx3)))
          PrintWarning(Twine("SubRegIndex ") + Idx1->getQualifiedName() +
                       " and " + Idx2->getQualifiedName() +
                       " compose ambiguously as " + Prev->getQualifiedName() +
                       " or " + Idx3->getQualifiedName());
      }
    }
  }
}
1484}

1486// Compute lane masks. This is similar to register units, but at the
1487// sub-register index level. Each bit in the lane mask is like a register unit
1488// class, and two lane masks will have a bit in common if two sub-register
1489// indices overlap in some register.
1490//
1491// Conservatively share a lane mask bit if two sub-register indices overlap in
1492// some registers, but not in others. That shouldn't happen a lot.
1493void CodeGenRegBank::computeSubRegLaneMasks() {
// First assign individual bits to all the leaf indices.
unsigned Bit = 0;
// Determine mask of lanes that cover their registers.
CoveringLanes = LaneBitmask::getAll();
for (auto &Idx : SubRegIndices) {
  if (Idx.getComposites().empty()) {
    if (Bit > LaneBitmask::BitWidth) {
      PrintFatalError(
        Twine("Ran out of lanemask bits to represent subregister ")
        + Idx.getName());
    }
    Idx.LaneMask = LaneBitmask::getLane(Bit);
    ++Bit;
  } else {
    Idx.LaneMask = LaneBitmask::getNone();
  }
}

// Compute transformation sequences for composeSubRegIndexLaneMask. The idea
// here is that for each possible target subregister we look at the leafs
// in the subregister graph that compose for this target and create
// transformation sequences for the lanemasks. Each step in the sequence
// consists of a bitmask and a bitrotate operation. As the rotation amounts
// are usually the same for many subregisters we can easily combine the steps
// by combining the masks.
for (const auto &Idx : SubRegIndices) {
  const auto &Composites = Idx.getComposites();
  auto &LaneTransforms = Idx.CompositionLaneMaskTransform;

  if (Composites.empty()) {
2
←
Assuming the condition is true→
3
←
Taking true branch→
    // Moving from a class with no subregisters we just had a single lane:
    // The subregister must be a leaf subregister and only occupies 1 bit.
    // Move the bit from the class without subregisters into that position.
    unsigned DstBit = Idx.LaneMask.getHighestLane();
4
←
Calling 'LaneBitmask::getHighestLane'→
9
←
Returning from 'LaneBitmask::getHighestLane'→
10
←
'DstBit' initialized to 4294967295→
    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", 1529, __extension__
 __PRETTY_FUNCTION__))
11
←
Passing the value 4294967295 via 1st parameter 'Lane'→
12
←
Calling 'LaneBitmask::getLane'→
           "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", 1529, __extension__
 __PRETTY_FUNCTION__));
    MaskRolPair MaskRol = { LaneBitmask::getLane(0), (uint8_t)DstBit };
    LaneTransforms.push_back(MaskRol);
  } else {
    // Go through all leaf subregisters and find the ones that compose with
    // Idx. These make out all possible valid bits in the lane mask we want to
    // transform. Looking only at the leafs ensure that only a single bit in
    // the mask is set.
    unsigned NextBit = 0;
    for (auto &Idx2 : SubRegIndices) {
      // Skip non-leaf subregisters.
      if (!Idx2.getComposites().empty())
        continue;
      // Replicate the behaviour from the lane mask generation loop above.
      unsigned SrcBit = NextBit;
      LaneBitmask SrcMask = LaneBitmask::getLane(SrcBit);
      if (NextBit < LaneBitmask::BitWidth-1)
        ++NextBit;
      assert(Idx2.LaneMask == SrcMask)(static_cast <bool> (Idx2.LaneMask == SrcMask) ? void (
0) : __assert_fail ("Idx2.LaneMask == SrcMask", "llvm/utils/TableGen/CodeGenRegisters.cpp"
, 1547, __extension__ __PRETTY_FUNCTION__));

      // Get the composed subregister if there is any.
      auto C = Composites.find(&Idx2);
      if (C == Composites.end())
        continue;
      const CodeGenSubRegIndex *Composite = C->second;
      // The Composed subreg should be a leaf subreg too
      assert(Composite->getComposites().empty())(static_cast <bool> (Composite->getComposites().empty
()) ? void (0) : __assert_fail ("Composite->getComposites().empty()"
, "llvm/utils/TableGen/CodeGenRegisters.cpp", 1555, __extension__
 __PRETTY_FUNCTION__));

      // Create Mask+Rotate operation and merge with existing ops if possible.
      unsigned DstBit = Composite->LaneMask.getHighestLane();
      int Shift = DstBit - SrcBit;
      uint8_t RotateLeft = Shift >= 0 ? (uint8_t)Shift
                                      : LaneBitmask::BitWidth + Shift;
      for (auto &I : LaneTransforms) {
        if (I.RotateLeft == RotateLeft) {
          I.Mask |= SrcMask;
          SrcMask = LaneBitmask::getNone();
        }
      }
      if (SrcMask.any()) {
        MaskRolPair MaskRol = { SrcMask, RotateLeft };
        LaneTransforms.push_back(MaskRol);
      }
    }
  }

  // Optimize if the transformation consists of one step only: Set mask to
  // 0xffffffff (including some irrelevant invalid bits) so that it should
  // merge with more entries later while compressing the table.
  if (LaneTransforms.size() == 1)
    LaneTransforms[0].Mask = LaneBitmask::getAll();

  // Further compression optimization: For invalid compositions resulting
  // in a sequence with 0 entries we can just pick any other. Choose
  // Mask 0xffffffff with Rotation 0.
  if (LaneTransforms.size() == 0) {
    MaskRolPair P = { LaneBitmask::getAll(), 0 };
    LaneTransforms.push_back(P);
  }
}

// FIXME: What if ad-hoc aliasing introduces overlaps that aren't represented
// by the sub-register graph? This doesn't occur in any known targets.

// Inherit lanes from composites.
for (const auto &Idx : SubRegIndices) {
  LaneBitmask Mask = Idx.computeLaneMask();
  // If some super-registers without CoveredBySubRegs use this index, we can
  // no longer assume that the lanes are covering their registers.
  if (!Idx.AllSuperRegsCovered)
    CoveringLanes &= ~Mask;
}

// Compute lane mask combinations for register classes.
for (auto &RegClass : RegClasses) {
  LaneBitmask LaneMask;
  for (const auto &SubRegIndex : SubRegIndices) {
    if (RegClass.getSubClassWithSubReg(&SubRegIndex) == nullptr)
      continue;
    LaneMask |= SubRegIndex.LaneMask;
  }

  // For classes without any subregisters set LaneMask to 1 instead of 0.
  // This makes it easier for client code to handle classes uniformly.
  if (LaneMask.none())
    LaneMask = LaneBitmask::getLane(0);

  RegClass.LaneMask = LaneMask;
}
1618}

1620namespace {

1622// UberRegSet is a helper class for computeRegUnitWeights. Each UberRegSet is
1623// the transitive closure of the union of overlapping register
1624// classes. Together, the UberRegSets form a partition of the registers. If we
1625// consider overlapping register classes to be connected, then each UberRegSet
1626// is a set of connected components.
1627//
1628// An UberRegSet will likely be a horizontal slice of register names of
1629// the same width. Nontrivial subregisters should then be in a separate
1630// UberRegSet. But this property isn't required for valid computation of
1631// register unit weights.
1632//
1633// A Weight field caches the max per-register unit weight in each UberRegSet.
1634//
1635// A set of SingularDeterminants flags single units of some register in this set
1636// for which the unit weight equals the set weight. These units should not have
1637// their weight increased.
1638struct UberRegSet {
CodeGenRegister::Vec Regs;
unsigned Weight = 0;
CodeGenRegister::RegUnitList SingularDeterminants;

UberRegSet() = default;
1644};

1646} // end anonymous namespace

1648// Partition registers into UberRegSets, where each set is the transitive
1649// closure of the union of overlapping register classes.
1650//
1651// UberRegSets[0] is a special non-allocatable set.
1652static void computeUberSets(std::vector<UberRegSet> &UberSets,
                          std::vector<UberRegSet*> &RegSets,
                          CodeGenRegBank &RegBank) {
const auto &Registers = RegBank.getRegisters();

// The Register EnumValue is one greater than its index into Registers.
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", 1659, __extension__
 __PRETTY_FUNCTION__))
       "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", 1659, __extension__
 __PRETTY_FUNCTION__));

// For simplicitly make the SetID the same as EnumValue.
IntEqClasses UberSetIDs(Registers.size() + 1);
BitVector AllocatableRegs(Registers.size() + 1);
for (auto &RegClass : RegBank.getRegClasses()) {
  if (!RegClass.Allocatable)
    continue;

  const CodeGenRegister::Vec &Regs = RegClass.getMembers();
  if (Regs.empty())
    continue;

  unsigned USetID = UberSetIDs.findLeader((*Regs.begin())->EnumValue);
  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", 1673, __extension__
 __PRETTY_FUNCTION__));

  AllocatableRegs.set((*Regs.begin())->EnumValue);
  for (const CodeGenRegister *CGR : llvm::drop_begin(Regs)) {
    AllocatableRegs.set(CGR->EnumValue);
    UberSetIDs.join(USetID, CGR->EnumValue);
  }
}
// Combine non-allocatable regs.
for (const auto &Reg : Registers) {
  unsigned RegNum = Reg.EnumValue;
  if (AllocatableRegs.test(RegNum))
    continue;

  UberSetIDs.join(0, RegNum);
}
UberSetIDs.compress();

// Make the first UberSet a special unallocatable set.
unsigned ZeroID = UberSetIDs[0];

// Insert Registers into the UberSets formed by union-find.
// Do not resize after this.
UberSets.resize(UberSetIDs.getNumClasses());
unsigned i = 0;
for (const CodeGenRegister &Reg : Registers) {
  unsigned USetID = UberSetIDs[Reg.EnumValue];
  if (!USetID)
    USetID = ZeroID;
  else if (USetID == ZeroID)
    USetID = 0;

  UberRegSet *USet = &UberSets[USetID];
  USet->Regs.push_back(&Reg);
  RegSets[i++] = USet;
}
1709}

1711// Recompute each UberSet weight after changing unit weights.
1712static void computeUberWeights(std::vector<UberRegSet> &UberSets,
                             CodeGenRegBank &RegBank) {
// Skip the first unallocatable set.
for (std::vector<UberRegSet>::iterator I = std::next(UberSets.begin()),
       E = UberSets.end(); I != E; ++I) {

  // Initialize all unit weights in this set, and remember the max units/reg.
  const CodeGenRegister *Reg = nullptr;
  unsigned MaxWeight = 0, Weight = 0;
  for (RegUnitIterator UnitI(I->Regs); UnitI.isValid(); ++UnitI) {
    if (Reg != UnitI.getReg()) {
      if (Weight > MaxWeight)
        MaxWeight = Weight;
      Reg = UnitI.getReg();
      Weight = 0;
    }
    if (!RegBank.getRegUnit(*UnitI).Artificial) {
      unsigned UWeight = RegBank.getRegUnit(*UnitI).Weight;
      if (!UWeight) {
        UWeight = 1;
        RegBank.increaseRegUnitWeight(*UnitI, UWeight);
      }
      Weight += UWeight;
    }
  }
  if (Weight > MaxWeight)
    MaxWeight = Weight;
  if (I->Weight != MaxWeight) {
    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)
                      << 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)
               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)
                    : 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)
               << " " << 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)
               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);
    // Update the set weight.
    I->Weight = MaxWeight;
  }

  // Find singular determinants.
  for (const auto R : I->Regs) {
    if (R->getRegUnits().count() == 1 && R->getWeight(RegBank) == I->Weight) {
      I->SingularDeterminants |= R->getRegUnits();
    }
  }
}
1757}

1759// normalizeWeight is a computeRegUnitWeights helper that adjusts the weight of
1760// a register and its subregisters so that they have the same weight as their
1761// UberSet. Self-recursion processes the subregister tree in postorder so
1762// subregisters are normalized first.
1763//
1764// Side effects:
1765// - creates new adopted register units
1766// - causes superregisters to inherit adopted units
1767// - increases the weight of "singular" units
1768// - induces recomputation of UberWeights.
1769static bool normalizeWeight(CodeGenRegister *Reg,
                          std::vector<UberRegSet> &UberSets,
                          std::vector<UberRegSet*> &RegSets,
                          BitVector &NormalRegs,
                          CodeGenRegister::RegUnitList &NormalUnits,
                          CodeGenRegBank &RegBank) {
NormalRegs.resize(std::max(Reg->EnumValue + 1, NormalRegs.size()));
if (NormalRegs.test(Reg->EnumValue))
  return false;
NormalRegs.set(Reg->EnumValue);

bool Changed = false;
const CodeGenRegister::SubRegMap &SRM = Reg->getSubRegs();
for (auto SRI : SRM) {
  if (SRI.second == Reg)
    continue; // self-cycles happen

  Changed |= normalizeWeight(SRI.second, UberSets, RegSets, NormalRegs,
                             NormalUnits, RegBank);
}
// Postorder register normalization.

// Inherit register units newly adopted by subregisters.
if (Reg->inheritRegUnits(RegBank))
  computeUberWeights(UberSets, RegBank);

// Check if this register is too skinny for its UberRegSet.
UberRegSet *UberSet = RegSets[RegBank.getRegIndex(Reg)];

unsigned RegWeight = Reg->getWeight(RegBank);
if (UberSet->Weight > RegWeight) {
  // A register unit's weight can be adjusted only if it is the singular unit
  // for this register, has not been used to normalize a subregister's set,
  // and has not already been used to singularly determine this UberRegSet.
  unsigned AdjustUnit = *Reg->getRegUnits().begin();
  if (Reg->getRegUnits().count() != 1
      || hasRegUnit(NormalUnits, AdjustUnit)
      || hasRegUnit(UberSet->SingularDeterminants, AdjustUnit)) {
    // We don't have an adjustable unit, so adopt a new one.
    AdjustUnit = RegBank.newRegUnit(UberSet->Weight - RegWeight);
    Reg->adoptRegUnit(AdjustUnit);
    // Adopting a unit does not immediately require recomputing set weights.
  }
  else {
    // Adjust the existing single unit.
    if (!RegBank.getRegUnit(AdjustUnit).Artificial)
      RegBank.increaseRegUnitWeight(AdjustUnit, UberSet->Weight - RegWeight);
    // The unit may be shared among sets and registers within this set.
    computeUberWeights(UberSets, RegBank);
  }
  Changed = true;
}

// Mark these units normalized so superregisters can't change their weights.
NormalUnits |= Reg->getRegUnits();

return Changed;
1826}

1828// Compute a weight for each register unit created during getSubRegs.
1829//
1830// The goal is that two registers in the same class will have the same weight,
1831// where each register's weight is defined as sum of its units' weights.
1832void CodeGenRegBank::computeRegUnitWeights() {
std::vector<UberRegSet> UberSets;
std::vector<UberRegSet*> RegSets(Registers.size());
computeUberSets(UberSets, RegSets, *this);
// UberSets and RegSets are now immutable.

computeUberWeights(UberSets, *this);

// Iterate over each Register, normalizing the unit weights until reaching
// a fix point.
unsigned NumIters = 0;
for (bool Changed = true; Changed; ++NumIters) {
  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", 1844, __extension__
 __PRETTY_FUNCTION__));
  (void) NumIters;
  Changed = false;
  for (auto &Reg : Registers) {
    CodeGenRegister::RegUnitList NormalUnits;
    BitVector NormalRegs;
    Changed |= normalizeWeight(&Reg, UberSets, RegSets, NormalRegs,
                               NormalUnits, *this);
  }
}
1854}

1856// Find a set in UniqueSets with the same elements as Set.
1857// Return an iterator into UniqueSets.
1858static std::vector<RegUnitSet>::const_iterator
1859findRegUnitSet(const std::vector<RegUnitSet> &UniqueSets,
             const RegUnitSet &Set) {
std::vector<RegUnitSet>::const_iterator
  I = UniqueSets.begin(), E = UniqueSets.end();
for(;I != E; ++I) {
  if (I->Units == Set.Units)
    break;
}
return I;
1868}

1870// Return true if the RUSubSet is a subset of RUSuperSet.
1871static bool isRegUnitSubSet(const std::vector<unsigned> &RUSubSet,
                          const std::vector<unsigned> &RUSuperSet) {
return std::includes(RUSuperSet.begin(), RUSuperSet.end(),
                     RUSubSet.begin(), RUSubSet.end());
1875}

1877/// Iteratively prune unit sets. Prune subsets that are close to the superset,
1878/// but with one or two registers removed. We occasionally have registers like
1879/// APSR and PC thrown in with the general registers. We also see many
1880/// special-purpose register subsets, such as tail-call and Thumb
1881/// encodings. Generating all possible overlapping sets is combinatorial and
1882/// overkill for modeling pressure. Ideally we could fix this statically in
1883/// tablegen by (1) having the target define register classes that only include
1884/// the allocatable registers and marking other classes as non-allocatable and
1885/// (2) having a way to mark special purpose classes as "don't-care" classes for
1886/// the purpose of pressure.  However, we make an attempt to handle targets that
1887/// are not nicely defined by merging nearly identical register unit sets
1888/// statically. This generates smaller tables. Then, dynamically, we adjust the
1889/// set limit by filtering the reserved registers.
1890///
1891/// Merge sets only if the units have the same weight. For example, on ARM,
1892/// Q-tuples with ssub index 0 include all S regs but also include D16+. We
1893/// should not expand the S set to include D regs.
1894void CodeGenRegBank::pruneUnitSets() {
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", 1895, __extension__
 __PRETTY_FUNCTION__));

// Form an equivalence class of UnitSets with no significant difference.
std::vector<unsigned> SuperSetIDs;
for (unsigned SubIdx = 0, EndIdx = RegUnitSets.size();
     SubIdx != EndIdx; ++SubIdx) {
  const RegUnitSet &SubSet = RegUnitSets[SubIdx];
  unsigned SuperIdx = 0;
  for (; SuperIdx != EndIdx; ++SuperIdx) {
    if (SuperIdx == SubIdx)
      continue;

    unsigned UnitWeight = RegUnits[SubSet.Units[0]].Weight;
    const RegUnitSet &SuperSet = RegUnitSets[SuperIdx];
    if (isRegUnitSubSet(SubSet.Units, SuperSet.Units)
        && (SubSet.Units.size() + 3 > SuperSet.Units.size())
        && UnitWeight == RegUnits[SuperSet.Units[0]].Weight
        && UnitWeight == RegUnits[SuperSet.Units.back()].Weight) {
      LLVM_DEBUG(dbgs() << "UnitSet " << SubIdx << " subsumed by " << SuperIdxdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc-emitter")) { dbgs() << "UnitSet " << SubIdx
 << " subsumed by " << SuperIdx << "\n"; } }
 while (false)
                        << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc-emitter")) { dbgs() << "UnitSet " << SubIdx
 << " subsumed by " << SuperIdx << "\n"; } }
 while (false);
      // We can pick any of the set names for the merged set. Go for the
      // shortest one to avoid picking the name of one of the classes that are
      // artificially created by tablegen. So "FPR128_lo" instead of
      // "QQQQ_with_qsub3_in_FPR128_lo".
      if (RegUnitSets[SubIdx].Name.size() < RegUnitSets[SuperIdx].Name.size())
        RegUnitSets[SuperIdx].Name = RegUnitSets[SubIdx].Name;
      break;
    }
  }
  if (SuperIdx == EndIdx)
    SuperSetIDs.push_back(SubIdx);
}
// Populate PrunedUnitSets with each equivalence class's superset.
std::vector<RegUnitSet> PrunedUnitSets(SuperSetIDs.size());
for (unsigned i = 0, e = SuperSetIDs.size(); i != e; ++i) {
  unsigned SuperIdx = SuperSetIDs[i];
  PrunedUnitSets[i].Name = RegUnitSets[SuperIdx].Name;
  PrunedUnitSets[i].Units.swap(RegUnitSets[SuperIdx].Units);
}
RegUnitSets.swap(PrunedUnitSets);
1935}

1937// Create a RegUnitSet for each RegClass that contains all units in the class
1938// including adopted units that are necessary to model register pressure. Then
1939// iteratively compute RegUnitSets such that the union of any two overlapping
1940// RegUnitSets is repreresented.
1941//
1942// RegisterInfoEmitter will map each RegClass to its RegUnitClass and any
1943// RegUnitSet that is a superset of that RegUnitClass.
1944void CodeGenRegBank::computeRegUnitSets() {
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", 1945, __extension__
 __PRETTY_FUNCTION__));

// Compute a unique RegUnitSet for each RegClass.
auto &RegClasses = getRegClasses();
for (auto &RC : RegClasses) {
  if (!RC.Allocatable || RC.Artificial || !RC.GeneratePressureSet)
    continue;

  // Speculatively grow the RegUnitSets to hold the new set.
  RegUnitSets.resize(RegUnitSets.size() + 1);
  RegUnitSets.back().Name = RC.getName();

  // Compute a sorted list of units in this class.
  RC.buildRegUnitSet(*this, RegUnitSets.back().Units);

  // Find an existing RegUnitSet.
  std::vector<RegUnitSet>::const_iterator SetI =
    findRegUnitSet(RegUnitSets, RegUnitSets.back());
  if (SetI != std::prev(RegUnitSets.end()))
    RegUnitSets.pop_back();
}

if (RegUnitSets.empty())
  PrintFatalError("RegUnitSets cannot be empty!");

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)
                                                 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)
                                                 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)
  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)
  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)
    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)
  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)
})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);

// Iteratively prune unit sets.
pruneUnitSets();

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)
                                               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)
                                               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)
  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)
  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)
    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)
  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)
} 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);

// Iterate over all unit sets, including new ones added by this loop.
unsigned NumRegUnitSubSets = RegUnitSets.size();
for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx) {
  // In theory, this is combinatorial. In practice, it needs to be bounded
  // by a small number of sets for regpressure to be efficient.
  // If the assert is hit, we need to implement pruning.
  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", 1997, __extension__
 __PRETTY_FUNCTION__));

  // Compare new sets with all original classes.
  for (unsigned SearchIdx = (Idx >= NumRegUnitSubSets) ? 0 : Idx+1;
       SearchIdx != EndIdx; ++SearchIdx) {
    std::set<unsigned> Intersection;
    std::set_intersection(RegUnitSets[Idx].Units.begin(),
                          RegUnitSets[Idx].Units.end(),
                          RegUnitSets[SearchIdx].Units.begin(),
                          RegUnitSets[SearchIdx].Units.end(),
                          std::inserter(Intersection, Intersection.begin()));
    if (Intersection.empty())
      continue;

    // Speculatively grow the RegUnitSets to hold the new set.
    RegUnitSets.resize(RegUnitSets.size() + 1);
    RegUnitSets.back().Name =
      RegUnitSets[Idx].Name + "_with_" + RegUnitSets[SearchIdx].Name;

    std::set_union(RegUnitSets[Idx].Units.begin(),
                   RegUnitSets[Idx].Units.end(),
                   RegUnitSets[SearchIdx].Units.begin(),
                   RegUnitSets[SearchIdx].Units.end(),
                   std::inserter(RegUnitSets.back().Units,
                                 RegUnitSets.back().Units.begin()));

    // Find an existing RegUnitSet, or add the union to the unique sets.
    std::vector<RegUnitSet>::const_iterator SetI =
      findRegUnitSet(RegUnitSets, RegUnitSets.back());
    if (SetI != std::prev(RegUnitSets.end()))
      RegUnitSets.pop_back();
    else {
      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)
                        << 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)
                 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)
                      : 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)
                 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);
    }
  }
}

// Iteratively prune unit sets after inferring supersets.
pruneUnitSets();

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)
    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)
                         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)
      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)
      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)
        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)
      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)
    })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);

// For each register class, list the UnitSets that are supersets.
RegClassUnitSets.resize(RegClasses.size());
int RCIdx = -1;
for (auto &RC : RegClasses) {
  ++RCIdx;
  if (!RC.Allocatable)
    continue;

  // Recompute the sorted list of units in this class.
  std::vector<unsigned> RCRegUnits;
  RC.buildRegUnitSet(*this, RCRegUnits);

  // Don't increase pressure for unallocatable regclasses.
  if (RCRegUnits.empty())
    continue;

  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)
             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)
                  : 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)
             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);

  // Find all supersets.
  for (unsigned USIdx = 0, USEnd = RegUnitSets.size();
       USIdx != USEnd; ++USIdx) {
    if (isRegUnitSubSet(RCRegUnits, RegUnitSets[USIdx].Units)) {
      LLVM_DEBUG(dbgs() << " " << USIdx)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc-emitter")) { dbgs() << " " << USIdx; }
 } while (false);
      RegClassUnitSets[RCIdx].push_back(USIdx);
    }
  }
  LLVM_DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc-emitter")) { dbgs() << "\n"; } } while (false
);
  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", 2081, __extension__
 __PRETTY_FUNCTION__))
         "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", 2081, __extension__
 __PRETTY_FUNCTION__));
}

// For each register unit, ensure that we have the list of UnitSets that
// contain the unit. Normally, this matches an existing list of UnitSets for a
// register class. If not, we create a new entry in RegClassUnitSets as a
// "fake" register class.
for (unsigned UnitIdx = 0, UnitEnd = NumNativeRegUnits;
     UnitIdx < UnitEnd; ++UnitIdx) {
  std::vector<unsigned> RUSets;
  for (unsigned i = 0, e = RegUnitSets.size(); i != e; ++i) {
    RegUnitSet &RUSet = RegUnitSets[i];
    if (!is_contained(RUSet.Units, UnitIdx))
      continue;
    RUSets.push_back(i);
  }
  unsigned RCUnitSetsIdx = 0;
  for (unsigned e = RegClassUnitSets.size();
       RCUnitSetsIdx != e; ++RCUnitSetsIdx) {
    if (RegClassUnitSets[RCUnitSetsIdx] == RUSets) {
      break;
    }
  }
  RegUnits[UnitIdx].RegClassUnitSetsIdx = RCUnitSetsIdx;
  if (RCUnitSetsIdx == RegClassUnitSets.size()) {
    // Create a new list of UnitSets as a "fake" register class.
    RegClassUnitSets.resize(RCUnitSetsIdx + 1);
    RegClassUnitSets[RCUnitSetsIdx].swap(RUSets);
  }
}
2111}

2113void CodeGenRegBank::computeRegUnitLaneMasks() {
for (auto &Register : Registers) {
  // Create an initial lane mask for all register units.
  const auto &RegUnits = Register.getRegUnits();
  CodeGenRegister::RegUnitLaneMaskList
      RegUnitLaneMasks(RegUnits.count(), LaneBitmask::getNone());
  // Iterate through SubRegisters.
  typedef CodeGenRegister::SubRegMap SubRegMap;
  const SubRegMap &SubRegs = Register.getSubRegs();
  for (auto S : SubRegs) {
    CodeGenRegister *SubReg = S.second;
    // Ignore non-leaf subregisters, their lane masks are fully covered by
    // the leaf subregisters anyway.
    if (!SubReg->getSubRegs().empty())
      continue;
    CodeGenSubRegIndex *SubRegIndex = S.first;
    const CodeGenRegister *SubRegister = S.second;
    LaneBitmask LaneMask = SubRegIndex->LaneMask;
    // Distribute LaneMask to Register Units touched.
    for (unsigned SUI : SubRegister->getRegUnits()) {
      bool Found = false;
      unsigned u = 0;
      for (unsigned RU : RegUnits) {
        if (SUI == RU) {
          RegUnitLaneMasks[u] |= LaneMask;
          assert(!Found)(static_cast <bool> (!Found) ? void (0) : __assert_fail
 ("!Found", "llvm/utils/TableGen/CodeGenRegisters.cpp", 2138,
 __extension__ __PRETTY_FUNCTION__));
          Found = true;
        }
        ++u;
      }
      (void)Found;
      assert(Found)(static_cast <bool> (Found) ? void (0) : __assert_fail (
"Found", "llvm/utils/TableGen/CodeGenRegisters.cpp", 2144, __extension__
 __PRETTY_FUNCTION__));
    }
  }
  Register.setRegUnitLaneMasks(RegUnitLaneMasks);
}
2149}

2151void CodeGenRegBank::computeDerivedInfo() {
computeComposites();
computeSubRegLaneMasks();
1
Calling 'CodeGenRegBank::computeSubRegLaneMasks'→

// Compute a weight for each register unit created during getSubRegs.
// This may create adopted register units (with unit # >= NumNativeRegUnits).
computeRegUnitWeights();

// Compute a unique set of RegUnitSets. One for each RegClass and inferred
// supersets for the union of overlapping sets.
computeRegUnitSets();

computeRegUnitLaneMasks();

// Compute register class HasDisjunctSubRegs/CoveredBySubRegs flag.
for (CodeGenRegisterClass &RC : RegClasses) {
  RC.HasDisjunctSubRegs = false;
  RC.CoveredBySubRegs = true;
  for (const CodeGenRegister *Reg : RC.getMembers()) {
    RC.HasDisjunctSubRegs |= Reg->HasDisjunctSubRegs;
    RC.CoveredBySubRegs &= Reg->CoveredBySubRegs;
  }
}

// Get the weight of each set.
for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx)
  RegUnitSets[Idx].Weight = getRegUnitSetWeight(RegUnitSets[Idx].Units);

// Find the order of each set.
RegUnitSetOrder.reserve(RegUnitSets.size());
for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx)
  RegUnitSetOrder.push_back(Idx);

llvm::stable_sort(RegUnitSetOrder, [this](unsigned ID1, unsigned ID2) {
  return getRegPressureSet(ID1).Units.size() <
         getRegPressureSet(ID2).Units.size();
});
for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx) {
  RegUnitSets[RegUnitSetOrder[Idx]].Order = Idx;
}
2191}

2193//
2194// Synthesize missing register class intersections.
2195//
2196// Make sure that sub-classes of RC exists such that getCommonSubClass(RC, X)
2197// returns a maximal register class for all X.
2198//
2199void CodeGenRegBank::inferCommonSubClass(CodeGenRegisterClass *RC) {
assert(!RegClasses.empty())(static_cast <bool> (!RegClasses.empty()) ? void (0) : __assert_fail
 ("!RegClasses.empty()", "llvm/utils/TableGen/CodeGenRegisters.cpp"
, 2200, __extension__ __PRETTY_FUNCTION__));
// Stash the iterator to the last element so that this loop doesn't visit
// elements added by the getOrCreateSubClass call within it.
for (auto I = RegClasses.begin(), E = std::prev(RegClasses.end());
     I != std::next(E); ++I) {
  CodeGenRegisterClass *RC1 = RC;
  CodeGenRegisterClass *RC2 = &*I;
  if (RC1 == RC2)
    continue;

  // Compute the set intersection of RC1 and RC2.
  const CodeGenRegister::Vec &Memb1 = RC1->getMembers();
  const CodeGenRegister::Vec &Memb2 = RC2->getMembers();
  CodeGenRegister::Vec Intersection;
  std::set_intersection(Memb1.begin(), Memb1.end(), Memb2.begin(),
                        Memb2.end(),
                        std::inserter(Intersection, Intersection.begin()),
                        deref<std::less<>>());

  // Skip disjoint class pairs.
  if (Intersection.empty())
    continue;

  // If RC1 and RC2 have different spill sizes or alignments, use the
  // stricter one for sub-classing.  If they are equal, prefer RC1.
  if (RC2->RSI.hasStricterSpillThan(RC1->RSI))
    std::swap(RC1, RC2);

  getOrCreateSubClass(RC1, &Intersection,
                      RC1->getName() + "_and_" + RC2->getName());
}
2231}

2233//
2234// Synthesize missing sub-classes for getSubClassWithSubReg().
2235//
2236// Make sure that the set of registers in RC with a given SubIdx sub-register
2237// form a register class.  Update RC->SubClassWithSubReg.
2238//
2239void CodeGenRegBank::inferSubClassWithSubReg(CodeGenRegisterClass *RC) {
// Map SubRegIndex to set of registers in RC supporting that SubRegIndex.
typedef std::map<const CodeGenSubRegIndex *, CodeGenRegister::Vec,
                 deref<std::less<>>>
    SubReg2SetMap;

// Compute the set of registers supporting each SubRegIndex.
SubReg2SetMap SRSets;
for (const auto R : RC->getMembers()) {
  if (R->Artificial)
    continue;
  const CodeGenRegister::SubRegMap &SRM = R->getSubRegs();
  for (auto I : SRM) {
    if (!I.first->Artificial)
      SRSets[I.first].push_back(R);
  }
}

for (auto I : SRSets)
  sortAndUniqueRegisters(I.second);

// Find matching classes for all SRSets entries.  Iterate in SubRegIndex
// numerical order to visit synthetic indices last.
for (const auto &SubIdx : SubRegIndices) {
  if (SubIdx.Artificial)
    continue;
  SubReg2SetMap::const_iterator I = SRSets.find(&SubIdx);
  // Unsupported SubRegIndex. Skip it.
  if (I == SRSets.end())
    continue;
  // In most cases, all RC registers support the SubRegIndex.
  if (I->second.size() == RC->getMembers().size()) {
    RC->setSubClassWithSubReg(&SubIdx, RC);
    continue;
  }
  // This is a real subset.  See if we have a matching class.
  CodeGenRegisterClass *SubRC =
    getOrCreateSubClass(RC, &I->second,
                        RC->getName() + "_with_" + I->first->getName());
  RC->setSubClassWithSubReg(&SubIdx, SubRC);
}
2280}

2282//
2283// Synthesize missing sub-classes of RC for getMatchingSuperRegClass().
2284//
2285// Create sub-classes of RC such that getMatchingSuperRegClass(RC, SubIdx, X)
2286// has a maximal result for any SubIdx and any X >= FirstSubRegRC.
2287//

2289void CodeGenRegBank::inferMatchingSuperRegClass(CodeGenRegisterClass *RC,
                                              std::list<CodeGenRegisterClass>::iterator FirstSubRegRC) {
SmallVector<std::pair<const CodeGenRegister*,
                      const CodeGenRegister*>, 16> SSPairs;
BitVector TopoSigs(getNumTopoSigs());

// Iterate in SubRegIndex numerical order to visit synthetic indices last.
for (auto &SubIdx : SubRegIndices) {
  // Skip indexes that aren't fully supported by RC's registers. This was
  // computed by inferSubClassWithSubReg() above which should have been
  // called first.
  if (RC->getSubClassWithSubReg(&SubIdx) != RC)
    continue;

  // Build list of (Super, Sub) pairs for this SubIdx.
  SSPairs.clear();
  TopoSigs.reset();
  for (const auto Super : RC->getMembers()) {
    const CodeGenRegister *Sub = Super->getSubRegs().find(&SubIdx)->second;
    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", 2308, __extension__
 __PRETTY_FUNCTION__));
    SSPairs.push_back(std::make_pair(Super, Sub));
    TopoSigs.set(Sub->getTopoSig());
  }

  // Iterate over sub-register class candidates.  Ignore classes created by
  // this loop. They will never be useful.
  // Store an iterator to the last element (not end) so that this loop doesn't
  // visit newly inserted elements.
  assert(!RegClasses.empty())(static_cast <bool> (!RegClasses.empty()) ? void (0) : __assert_fail
 ("!RegClasses.empty()", "llvm/utils/TableGen/CodeGenRegisters.cpp"
, 2317, __extension__ __PRETTY_FUNCTION__));
  for (auto I = FirstSubRegRC, E = std::prev(RegClasses.end());
       I != std::next(E); ++I) {
    CodeGenRegisterClass &SubRC = *I;
    if (SubRC.Artificial)
      continue;
    // Topological shortcut: SubRC members have the wrong shape.
    if (!TopoSigs.anyCommon(SubRC.getTopoSigs()))
      continue;
    // Compute the subset of RC that maps into SubRC.
    CodeGenRegister::Vec SubSetVec;
    for (unsigned i = 0, e = SSPairs.size(); i != e; ++i)
      if (SubRC.contains(SSPairs[i].second))
        SubSetVec.push_back(SSPairs[i].first);

    if (SubSetVec.empty())
      continue;

    // RC injects completely into SubRC.
    sortAndUniqueRegisters(SubSetVec);
    if (SubSetVec.size() == SSPairs.size()) {
      SubRC.addSuperRegClass(&SubIdx, RC);
      continue;
    }

    // Only a subset of RC maps into SubRC. Make sure it is represented by a
    // class.
    getOrCreateSubClass(RC, &SubSetVec, RC->getName() + "_with_" +
                                        SubIdx.getName() + "_in_" +
                                        SubRC.getName());
  }
}
2349}

2351//
2352// Infer missing register classes.
2353//
2354void CodeGenRegBank::computeInferredRegisterClasses() {
assert(!RegClasses.empty())(static_cast <bool> (!RegClasses.empty()) ? void (0) : __assert_fail
 ("!RegClasses.empty()", "llvm/utils/TableGen/CodeGenRegisters.cpp"
, 2355, __extension__ __PRETTY_FUNCTION__));
// When this function is called, the register classes have not been sorted
// and assigned EnumValues yet.  That means getSubClasses(),
// getSuperClasses(), and hasSubClass() functions are defunct.

// Use one-before-the-end so it doesn't move forward when new elements are
// added.
auto FirstNewRC = std::prev(RegClasses.end());

// Visit all register classes, including the ones being added by the loop.
// Watch out for iterator invalidation here.
for (auto I = RegClasses.begin(), E = RegClasses.end(); I != E; ++I) {
  CodeGenRegisterClass *RC = &*I;
  if (RC->Artificial)
    continue;

  // Synthesize answers for getSubClassWithSubReg().
  inferSubClassWithSubReg(RC);

  // Synthesize answers for getCommonSubClass().
  inferCommonSubClass(RC);

  // Synthesize answers for getMatchingSuperRegClass().
  inferMatchingSuperRegClass(RC);

  // New register classes are created while this loop is running, and we need
  // to visit all of them.  I  particular, inferMatchingSuperRegClass needs
  // to match old super-register classes with sub-register classes created
  // after inferMatchingSuperRegClass was called.  At this point,
  // inferMatchingSuperRegClass has checked SuperRC = [0..rci] with SubRC =
  // [0..FirstNewRC).  We need to cover SubRC = [FirstNewRC..rci].
  if (I == FirstNewRC) {
    auto NextNewRC = std::prev(RegClasses.end());
    for (auto I2 = RegClasses.begin(), E2 = std::next(FirstNewRC); I2 != E2;
         ++I2)
      inferMatchingSuperRegClass(&*I2, E2);
    FirstNewRC = NextNewRC;
  }
}
2394}

2396/// getRegisterClassForRegister - Find the register class that contains the
2397/// specified physical register.  If the register is not in a register class,
2398/// return null. If the register is in multiple classes, and the classes have a
2399/// superset-subset relationship and the same set of types, return the
2400/// superclass.  Otherwise return null.
2401const CodeGenRegisterClass*
2402CodeGenRegBank::getRegClassForRegister(Record *R) {
const CodeGenRegister *Reg = getReg(R);
const CodeGenRegisterClass *FoundRC = nullptr;
for (const auto &RC : getRegClasses()) {
  if (!RC.contains(Reg))
    continue;

  // If this is the first class that contains the register,
  // make a note of it and go on to the next class.
  if (!FoundRC) {
    FoundRC = &RC;
    continue;
  }

  // If a register's classes have different types, return null.
  if (RC.getValueTypes() != FoundRC->getValueTypes())
    return nullptr;

  // Check to see if the previously found class that contains
  // the register is a subclass of the current class. If so,
  // prefer the superclass.
  if (RC.hasSubClass(FoundRC)) {
    FoundRC = &RC;
    continue;
  }

  // Check to see if the previously found class that contains
  // the register is a superclass of the current class. If so,
  // prefer the superclass.
  if (FoundRC->hasSubClass(&RC))
    continue;

  // Multiple classes, and neither is a superclass of the other.
  // Return null.
  return nullptr;
}
return FoundRC;
2439}

2441const CodeGenRegisterClass *
2442CodeGenRegBank::getMinimalPhysRegClass(Record *RegRecord,
                                     ValueTypeByHwMode *VT) {
const CodeGenRegister *Reg = getReg(RegRecord);
const CodeGenRegisterClass *BestRC = nullptr;
for (const auto &RC : getRegClasses()) {
  if ((!VT || RC.hasType(*VT)) &&
      RC.contains(Reg) && (!BestRC || BestRC->hasSubClass(&RC)))
    BestRC = &RC;
}

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", 2452, __extension__
 __PRETTY_FUNCTION__));
return BestRC;
2454}

2456BitVector CodeGenRegBank::computeCoveredRegisters(ArrayRef<Record*> Regs) {
SetVector<const CodeGenRegister*> Set;

// First add Regs with all sub-registers.
for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
  CodeGenRegister *Reg = getReg(Regs[i]);
  if (Set.insert(Reg))
    // Reg is new, add all sub-registers.
    // The pre-ordering is not important here.
    Reg->addSubRegsPreOrder(Set, *this);
}

// Second, find all super-registers that are completely covered by the set.
for (unsigned i = 0; i != Set.size(); ++i) {
  const CodeGenRegister::SuperRegList &SR = Set[i]->getSuperRegs();
  for (unsigned j = 0, e = SR.size(); j != e; ++j) {
    const CodeGenRegister *Super = SR[j];
    if (!Super->CoveredBySubRegs || Set.count(Super))
      continue;
    // This new super-register is covered by its sub-registers.
    bool AllSubsInSet = true;
    const CodeGenRegister::SubRegMap &SRM = Super->getSubRegs();
    for (auto I : SRM)
      if (!Set.count(I.second)) {
        AllSubsInSet = false;
        break;
      }
    // All sub-registers in Set, add Super as well.
    // We will visit Super later to recheck its super-registers.
    if (AllSubsInSet)
      Set.insert(Super);
  }
}

// Convert to BitVector.
BitVector BV(Registers.size() + 1);
for (unsigned i = 0, e = Set.size(); i != e; ++i)
  BV.set(Set[i]->EnumValue);
return BV;
2495}

2497void CodeGenRegBank::printRegUnitName(unsigned Unit) const {
if (Unit < NumNativeRegUnits)
  dbgs() << ' ' << RegUnits[Unit].Roots[0]->getName();
else
  dbgs() << " #" << Unit;
2502}

←

/build/source/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 { return llvm::popcount(Mask); }
77    unsigned getHighestLane() const {
78      return Log2_64(Mask);
5
←
Calling 'Log2_64'→
7
←
Returning from 'Log2_64'→
8
←
Returning the value 4294967295→
79    }
80 
81    static constexpr LaneBitmask getNone() { return LaneBitmask(0); }
82    static constexpr LaneBitmask getAll() { return ~LaneBitmask(0); }
83    static constexpr LaneBitmask getLane(unsigned Lane) {
84      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'
85    }
86 
87  private:
88    Type Mask = 0;
89  };
90 
91  /// Create Printable object to print LaneBitmasks on a \ref raw_ostream.
92  inline Printable PrintLaneMask(LaneBitmask LaneMask) {
93    return Printable([LaneMask](raw_ostream &OS) {
94      OS << format(LaneBitmask::FormatStr, LaneMask.getAsInteger());
95    });
96  }
97 
98} // end namespace llvm
99 
100#endif // LLVM_MC_LANEBITMASK_H

←

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