brintos / llvm-project-archived public Read only

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