/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/include/llvm/MC/LaneBitmask.h

Bug Summary

File:	build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/include/llvm/MC/LaneBitmask.h
Warning:	line 86, column 34 The result of the left shift is undefined due to shifting by '4294967295', which is greater or equal to the width of type 'llvm::LaneBitmask::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-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm -resource-dir /usr/lib/llvm-15/lib/clang/15.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I utils/TableGen -I /build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/utils/TableGen -I include -I /build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-15/lib/clang/15.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm=build-llvm -fmacro-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm=build-llvm -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/= -O3 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm=build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-04-20-140412-16051-1 -x c++ /build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/utils/TableGen/CodeGenRegisters.cpp

/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/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), 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.
  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("");
    if (!RegNames.empty()) {
      if (RegNames.size() <= n)
        PrintFatalError(Def->getLoc(),
                        "Register tuple definition missing name for '" +
                          Name + "'.");
      AsmName = StringInit::get(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(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);
    }
  }
}
725};

727} // end anonymous namespace

729//===----------------------------------------------------------------------===//
730//                            CodeGenRegisterClass
731//===----------------------------------------------------------------------===//

733static 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());
736}

738CodeGenRegisterClass::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", 792, __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", 792, __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 (AllocationPriority < 0 || AllocationPriority > 63)
  PrintFatalError(R->getLoc(), "AllocationPriority out of range [0,63]");
this->AllocationPriority = AllocationPriority;

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

816// Create an inferred register class that was missing from the .td files.
817// Most properties will be inherited from the closest super-class after the
818// class structure has been computed.
819CodeGenRegisterClass::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), TSFlags(0) {
Artificial = true;
GeneratePressureSet = false;
for (const auto R : Members) {
  TopoSigs.set(R->getTopoSig());
  Artificial &= R->Artificial;
}
830}

832// Compute inherited propertied for a synthesized register class.
833void 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", 834, __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", 835, __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;
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]);
861}

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

868unsigned 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);
876}

878namespace 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 << " }";
}

887} // end namespace llvm

889// This is a simple lexicographical order that can be used to search for sets.
890// It is not the same as the topological order provided by TopoOrderRC.
891bool CodeGenRegisterClass::Key::
892operator<(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"
, 893, __extension__ __PRETTY_FUNCTION__));
return std::tie(*Members, RSI) < std::tie(*B.Members, B.RSI);
895}

897// Returns true if RC is a strict subclass.
898// RC is a sub-class of this class if it is a valid replacement for any
899// instruction operand where a register of this classis required. It must
900// satisfy these conditions:
901//
902// 1. All RC registers are also in this.
903// 2. The RC spill size must not be smaller than our spill size.
904// 3. RC spill alignment must be compatible with ours.
905//
906static 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<>>());
912}

914/// Sorting predicate for register classes.  This provides a topological
915/// ordering that arranges all register classes before their sub-classes.
916///
917/// Register classes with the same registers, spill size, and alignment form a
918/// clique.  They will be ordered alphabetically.
919///
920static 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();
941}

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

950// Compute sub-classes of all register classes.
951// Assume the classes are ordered topologically.
952void 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);
1000}

1002Optional<std::pair<CodeGenRegisterClass *, CodeGenRegisterClass *>>
1003CodeGenRegisterClass::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 None;
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", 1031, __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", 1031, __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 None;
1086}

1088void 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);
1095}

1097// Populate a unique sorted list of units from a register set.
1098void 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));
1109}

1111//===----------------------------------------------------------------------===//
1112//                           CodeGenRegisterCategory
1113//===----------------------------------------------------------------------===//

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

1122//===----------------------------------------------------------------------===//
1123//                               CodeGenRegBank
1124//===----------------------------------------------------------------------===//

1126CodeGenRegBank::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);
1245}

1247// Create a synthetic CodeGenSubRegIndex without a corresponding Record.
1248CodeGenSubRegIndex*
1249CodeGenRegBank::createSubRegIndex(StringRef Name, StringRef Namespace) {
SubRegIndices.emplace_back(Name, Namespace, SubRegIndices.size() + 1);
return &SubRegIndices.back();
1252}

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

1263const CodeGenSubRegIndex *
1264CodeGenRegBank::findSubRegIdx(const Record* Def) const {
return Def2SubRegIdx.lookup(Def);
1266}

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

1277void 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));
1285}

1287// Create a synthetic sub-class if it is missing.
1288CodeGenRegisterClass*
1289CodeGenRegBank::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();
1302}

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

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

1311CodeGenSubRegIndex*
1312CodeGenRegBank::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;
1324}

1326CodeGenSubRegIndex *CodeGenRegBank::
1327getConcatSubRegIndex(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", 1328, __extension__
 __PRETTY_FUNCTION__));
1329#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", 1331, __extension__
 __PRETTY_FUNCTION__));
}
1333#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;
for (unsigned i = 1, e = Parts.size(); i != e; ++i) {
  Name += '_';
  Name += Parts[i]->getName();
  Size += Parts[i]->Size;
  if (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;
1361}

1363void 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", 1440, __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());
      }
    }
  }
}
1455}

1457// Compute lane masks. This is similar to register units, but at the
1458// sub-register index level. Each bit in the lane mask is like a register unit
1459// class, and two lane masks will have a bit in common if two sub-register
1460// indices overlap in some register.
1461//
1462// Conservatively share a lane mask bit if two sub-register indices overlap in
1463// some registers, but not in others. That shouldn't happen a lot.
1464void 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", 1500, __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", 1500, __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"
, 1518, __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", 1526, __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;
}
1589}

1591namespace {

1593// UberRegSet is a helper class for computeRegUnitWeights. Each UberRegSet is
1594// the transitive closure of the union of overlapping register
1595// classes. Together, the UberRegSets form a partition of the registers. If we
1596// consider overlapping register classes to be connected, then each UberRegSet
1597// is a set of connected components.
1598//
1599// An UberRegSet will likely be a horizontal slice of register names of
1600// the same width. Nontrivial subregisters should then be in a separate
1601// UberRegSet. But this property isn't required for valid computation of
1602// register unit weights.
1603//
1604// A Weight field caches the max per-register unit weight in each UberRegSet.
1605//
1606// A set of SingularDeterminants flags single units of some register in this set
1607// for which the unit weight equals the set weight. These units should not have
1608// their weight increased.
1609struct UberRegSet {
CodeGenRegister::Vec Regs;
unsigned Weight = 0;
CodeGenRegister::RegUnitList SingularDeterminants;

UberRegSet() = default;
1615};

1617} // end anonymous namespace

1619// Partition registers into UberRegSets, where each set is the transitive
1620// closure of the union of overlapping register classes.
1621//
1622// UberRegSets[0] is a special non-allocatable set.
1623static 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", 1630, __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", 1630, __extension__
 __PRETTY_FUNCTION__));

// For simplicitly make the SetID the same as EnumValue.
IntEqClasses UberSetIDs(Registers.size()+1);
std::set<unsigned> AllocatableRegs;
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", 1644, __extension__
 __PRETTY_FUNCTION__));

  AllocatableRegs.insert((*Regs.begin())->EnumValue);
  for (const CodeGenRegister *CGR : llvm::drop_begin(Regs)) {
    AllocatableRegs.insert(CGR->EnumValue);
    UberSetIDs.join(USetID, CGR->EnumValue);
  }
}
// Combine non-allocatable regs.
for (const auto &Reg : Registers) {
  unsigned RegNum = Reg.EnumValue;
  if (AllocatableRegs.count(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);
  sortAndUniqueRegisters(USet->Regs);
  RegSets[i++] = USet;
}
1681}

1683// Recompute each UberSet weight after changing unit weights.
1684static 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();
    }
  }
}
1729}

1731// normalizeWeight is a computeRegUnitWeights helper that adjusts the weight of
1732// a register and its subregisters so that they have the same weight as their
1733// UberSet. Self-recursion processes the subregister tree in postorder so
1734// subregisters are normalized first.
1735//
1736// Side effects:
1737// - creates new adopted register units
1738// - causes superregisters to inherit adopted units
1739// - increases the weight of "singular" units
1740// - induces recomputation of UberWeights.
1741static 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;
1798}

1800// Compute a weight for each register unit created during getSubRegs.
1801//
1802// The goal is that two registers in the same class will have the same weight,
1803// where each register's weight is defined as sum of its units' weights.
1804void 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", 1816, __extension__
 __PRETTY_FUNCTION__));
  (void) NumIters;
  Changed = false;
  for (auto &Reg : Registers) {
    CodeGenRegister::RegUnitList NormalUnits;
    BitVector NormalRegs;
    Changed |= normalizeWeight(&Reg, UberSets, RegSets, NormalRegs,
                               NormalUnits, *this);
  }
}
1826}

1828// Find a set in UniqueSets with the same elements as Set.
1829// Return an iterator into UniqueSets.
1830static std::vector<RegUnitSet>::const_iterator
1831findRegUnitSet(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;
1840}

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

1849/// Iteratively prune unit sets. Prune subsets that are close to the superset,
1850/// but with one or two registers removed. We occasionally have registers like
1851/// APSR and PC thrown in with the general registers. We also see many
1852/// special-purpose register subsets, such as tail-call and Thumb
1853/// encodings. Generating all possible overlapping sets is combinatorial and
1854/// overkill for modeling pressure. Ideally we could fix this statically in
1855/// tablegen by (1) having the target define register classes that only include
1856/// the allocatable registers and marking other classes as non-allocatable and
1857/// (2) having a way to mark special purpose classes as "don't-care" classes for
1858/// the purpose of pressure.  However, we make an attempt to handle targets that
1859/// are not nicely defined by merging nearly identical register unit sets
1860/// statically. This generates smaller tables. Then, dynamically, we adjust the
1861/// set limit by filtering the reserved registers.
1862///
1863/// Merge sets only if the units have the same weight. For example, on ARM,
1864/// Q-tuples with ssub index 0 include all S regs but also include D16+. We
1865/// should not expand the S set to include D regs.
1866void 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", 1867, __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);
1907}

1909// Create a RegUnitSet for each RegClass that contains all units in the class
1910// including adopted units that are necessary to model register pressure. Then
1911// iteratively compute RegUnitSets such that the union of any two overlapping
1912// RegUnitSets is repreresented.
1913//
1914// RegisterInfoEmitter will map each RegClass to its RegUnitClass and any
1915// RegUnitSet that is a superset of that RegUnitClass.
1916void 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", 1917, __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", 1969, __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", 2053, __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", 2053, __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);
  }
}
2083}

2085void 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", 2110,
 __extension__ __PRETTY_FUNCTION__));
          Found = true;
        }
        ++u;
      }
      (void)Found;
      assert(Found)(static_cast <bool> (Found) ? void (0) : __assert_fail (
"Found", "llvm/utils/TableGen/CodeGenRegisters.cpp", 2116, __extension__
 __PRETTY_FUNCTION__));
    }
  }
  Register.setRegUnitLaneMasks(RegUnitLaneMasks);
}
2121}

2123void 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;
}
2163}

2165//
2166// Synthesize missing register class intersections.
2167//
2168// Make sure that sub-classes of RC exists such that getCommonSubClass(RC, X)
2169// returns a maximal register class for all X.
2170//
2171void CodeGenRegBank::inferCommonSubClass(CodeGenRegisterClass *RC) {
assert(!RegClasses.empty())(static_cast <bool> (!RegClasses.empty()) ? void (0) : __assert_fail
 ("!RegClasses.empty()", "llvm/utils/TableGen/CodeGenRegisters.cpp"
, 2172, __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());
}
2203}

2205//
2206// Synthesize missing sub-classes for getSubClassWithSubReg().
2207//
2208// Make sure that the set of registers in RC with a given SubIdx sub-register
2209// form a register class.  Update RC->SubClassWithSubReg.
2210//
2211void 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);
}
2252}

2254//
2255// Synthesize missing sub-classes of RC for getMatchingSuperRegClass().
2256//
2257// Create sub-classes of RC such that getMatchingSuperRegClass(RC, SubIdx, X)
2258// has a maximal result for any SubIdx and any X >= FirstSubRegRC.
2259//

2261void 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", 2280, __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"
, 2289, __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());
  }
}
2321}

2323//
2324// Infer missing register classes.
2325//
2326void CodeGenRegBank::computeInferredRegisterClasses() {
assert(!RegClasses.empty())(static_cast <bool> (!RegClasses.empty()) ? void (0) : __assert_fail
 ("!RegClasses.empty()", "llvm/utils/TableGen/CodeGenRegisters.cpp"
, 2327, __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;
  }
}
2366}

2368/// getRegisterClassForRegister - Find the register class that contains the
2369/// specified physical register.  If the register is not in a register class,
2370/// return null. If the register is in multiple classes, and the classes have a
2371/// superset-subset relationship and the same set of types, return the
2372/// superclass.  Otherwise return null.
2373const CodeGenRegisterClass*
2374CodeGenRegBank::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;
2411}

2413const CodeGenRegisterClass *
2414CodeGenRegBank::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", 2424, __extension__
 __PRETTY_FUNCTION__));
return BestRC;
2426}

2428BitVector 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;
2467}

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

←

/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/include/llvm/MC/LaneBitmask.h

→

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

←

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