brintos / llvm-project-archived public Read only

1//===- GlobalISelMatchTable.cpp -------------------------------------------===//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#include "GlobalISelMatchTable.h"10#include "Common/CodeGenInstruction.h"11#include "Common/CodeGenRegisters.h"12#include "llvm/ADT/Statistic.h"13#include "llvm/Support/Debug.h"14#include "llvm/Support/LEB128.h"15#include "llvm/Support/ScopedPrinter.h"16#include "llvm/Support/raw_ostream.h"17#include "llvm/TableGen/Error.h"18 19#define DEBUG_TYPE "gi-match-table"20 21STATISTIC(NumPatternEmitted, "Number of patterns emitted");22 23using namespace llvm;24using namespace gi;25 26// FIXME: Use createStringError instead.27static Error failUnsupported(const Twine &Reason) {28  return make_error<StringError>(Reason, inconvertibleErrorCode());29}30 31/// Get the name of the enum value used to number the predicate function.32static std::string getEnumNameForPredicate(const TreePredicateFn &Predicate) {33  if (Predicate.hasGISelPredicateCode())34    return "GICXXPred_MI_" + Predicate.getFnName();35  if (Predicate.hasGISelLeafPredicateCode())36    return "GICXXPred_MO_" + Predicate.getFnName();37  return "GICXXPred_" + Predicate.getImmTypeIdentifier().str() + "_" +38         Predicate.getFnName();39}40 41static std::string42getMatchOpcodeForImmPredicate(const TreePredicateFn &Predicate) {43  return "GIM_Check" + Predicate.getImmTypeIdentifier().str() + "ImmPredicate";44}45 46// GIMT_Encode2/4/847constexpr StringLiteral EncodeMacroName = "GIMT_Encode";48 49//===- Helpers ------------------------------------------------------------===//50 51void llvm::gi::emitEncodingMacrosDef(raw_ostream &OS) {52  OS << "#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__\n"53     << "#define " << EncodeMacroName << "2(Val)"54     << " uint8_t(Val), uint8_t((Val) >> 8)\n"55     << "#define " << EncodeMacroName << "4(Val)"56     << " uint8_t(Val), uint8_t((Val) >> 8), "57        "uint8_t((Val) >> 16), uint8_t((Val) >> 24)\n"58     << "#define " << EncodeMacroName << "8(Val)"59     << " uint8_t(Val), uint8_t((Val) >> 8), "60        "uint8_t((Val) >> 16), uint8_t((Val) >> 24),  "61        "uint8_t(uint64_t(Val) >> 32), uint8_t(uint64_t(Val) >> 40), "62        "uint8_t(uint64_t(Val) >> 48), uint8_t(uint64_t(Val) >> 56)\n"63     << "#else\n"64     << "#define " << EncodeMacroName << "2(Val)"65     << " uint8_t((Val) >> 8), uint8_t(Val)\n"66     << "#define " << EncodeMacroName << "4(Val)"67     << " uint8_t((Val) >> 24), uint8_t((Val) >> 16), "68        "uint8_t((Val) >> 8), uint8_t(Val)\n"69     << "#define " << EncodeMacroName << "8(Val)"70     << " uint8_t(uint64_t(Val) >> 56), uint8_t(uint64_t(Val) >> 48), "71        "uint8_t(uint64_t(Val) >> 40), uint8_t(uint64_t(Val) >> 32),  "72        "uint8_t((Val) >> 24), uint8_t((Val) >> 16), "73        "uint8_t((Val) >> 8), uint8_t(Val)\n"74     << "#endif\n";75}76 77void llvm::gi::emitEncodingMacrosUndef(raw_ostream &OS) {78  OS << "#undef " << EncodeMacroName << "2\n"79     << "#undef " << EncodeMacroName << "4\n"80     << "#undef " << EncodeMacroName << "8\n";81}82 83std::string84llvm::gi::getNameForFeatureBitset(ArrayRef<const Record *> FeatureBitset,85                                  int HwModeIdx) {86  std::string Name = "GIFBS";87  for (const Record *Feature : FeatureBitset)88    Name += ("_" + Feature->getName()).str();89  if (HwModeIdx >= 0)90    Name += ("_HwMode" + std::to_string(HwModeIdx));91  return Name;92}93 94template <class GroupT>95std::vector<Matcher *>96llvm::gi::optimizeRules(ArrayRef<Matcher *> Rules,97                        std::vector<std::unique_ptr<Matcher>> &MatcherStorage) {98 99  std::vector<Matcher *> OptRules;100  std::unique_ptr<GroupT> CurrentGroup = std::make_unique<GroupT>();101  assert(CurrentGroup->empty() && "Newly created group isn't empty!");102  unsigned NumGroups = 0;103 104  auto ProcessCurrentGroup = [&]() {105    if (CurrentGroup->empty())106      // An empty group is good to be reused:107      return;108 109    // If the group isn't large enough to provide any benefit, move all the110    // added rules out of it and make sure to re-create the group to properly111    // re-initialize it:112    if (CurrentGroup->size() < 2)113      append_range(OptRules, CurrentGroup->matchers());114    else {115      CurrentGroup->finalize();116      OptRules.push_back(CurrentGroup.get());117      MatcherStorage.emplace_back(std::move(CurrentGroup));118      ++NumGroups;119    }120    CurrentGroup = std::make_unique<GroupT>();121  };122  for (Matcher *Rule : Rules) {123    // Greedily add as many matchers as possible to the current group:124    if (CurrentGroup->addMatcher(*Rule))125      continue;126 127    ProcessCurrentGroup();128    assert(CurrentGroup->empty() && "A group wasn't properly re-initialized");129 130    // Try to add the pending matcher to a newly created empty group:131    if (!CurrentGroup->addMatcher(*Rule))132      // If we couldn't add the matcher to an empty group, that group type133      // doesn't support that kind of matchers at all, so just skip it:134      OptRules.push_back(Rule);135  }136  ProcessCurrentGroup();137 138  LLVM_DEBUG(dbgs() << "NumGroups: " << NumGroups << "\n");139  (void)NumGroups;140  assert(CurrentGroup->empty() && "The last group wasn't properly processed");141  return OptRules;142}143 144template std::vector<Matcher *> llvm::gi::optimizeRules<GroupMatcher>(145    ArrayRef<Matcher *> Rules,146    std::vector<std::unique_ptr<Matcher>> &MatcherStorage);147 148template std::vector<Matcher *> llvm::gi::optimizeRules<SwitchMatcher>(149    ArrayRef<Matcher *> Rules,150    std::vector<std::unique_ptr<Matcher>> &MatcherStorage);151 152static std::string getEncodedEmitStr(StringRef NamedValue, unsigned NumBytes) {153  if (NumBytes == 2 || NumBytes == 4 || NumBytes == 8)154    return (EncodeMacroName + Twine(NumBytes) + "(" + NamedValue + ")").str();155  llvm_unreachable("Unsupported number of bytes!");156}157 158template <class Range> static bool matchersRecordOperand(Range &&R) {159  return any_of(R, [](const auto &I) { return I->recordsOperand(); });160}161 162//===- Global Data --------------------------------------------------------===//163 164std::set<LLTCodeGen> llvm::gi::KnownTypes;165 166//===- MatchTableRecord ---------------------------------------------------===//167 168void MatchTableRecord::emit(raw_ostream &OS, bool LineBreakIsNextAfterThis,169                            const MatchTable &Table) const {170  bool UseLineComment =171      LineBreakIsNextAfterThis || (Flags & MTRF_LineBreakFollows);172  if (Flags & (MTRF_JumpTarget | MTRF_CommaFollows))173    UseLineComment = false;174 175  if (Flags & MTRF_Comment)176    OS << (UseLineComment ? "// " : "/*");177 178  if (NumElements > 1 && !(Flags & (MTRF_PreEncoded | MTRF_Comment)))179    OS << getEncodedEmitStr(EmitStr, NumElements);180  else181    OS << EmitStr;182 183  if (Flags & MTRF_Label)184    OS << ": @" << Table.getLabelIndex(LabelID);185 186  if ((Flags & MTRF_Comment) && !UseLineComment)187    OS << "*/";188 189  if (Flags & MTRF_JumpTarget) {190    if (Flags & MTRF_Comment)191      OS << " ";192    // TODO: Could encode this AOT to speed up build of generated file193    OS << getEncodedEmitStr(llvm::to_string(Table.getLabelIndex(LabelID)),194                            NumElements);195  }196 197  if (Flags & MTRF_CommaFollows) {198    OS << ",";199    if (!LineBreakIsNextAfterThis && !(Flags & MTRF_LineBreakFollows))200      OS << " ";201  }202 203  if (Flags & MTRF_LineBreakFollows)204    OS << "\n";205}206 207//===- MatchTable ---------------------------------------------------------===//208 209MatchTableRecord MatchTable::LineBreak = {210    std::nullopt, "" /* Emit String */, 0 /* Elements */,211    MatchTableRecord::MTRF_LineBreakFollows};212 213MatchTableRecord MatchTable::Comment(StringRef Comment) {214  return MatchTableRecord(std::nullopt, Comment, 0,215                          MatchTableRecord::MTRF_Comment);216}217 218MatchTableRecord MatchTable::Opcode(StringRef Opcode, int IndentAdjust) {219  unsigned ExtraFlags = 0;220  if (IndentAdjust > 0)221    ExtraFlags |= MatchTableRecord::MTRF_Indent;222  if (IndentAdjust < 0)223    ExtraFlags |= MatchTableRecord::MTRF_Outdent;224 225  return MatchTableRecord(std::nullopt, Opcode, 1,226                          MatchTableRecord::MTRF_CommaFollows | ExtraFlags);227}228 229MatchTableRecord MatchTable::NamedValue(unsigned NumBytes,230                                        StringRef NamedValue) {231  return MatchTableRecord(std::nullopt, NamedValue, NumBytes,232                          MatchTableRecord::MTRF_CommaFollows);233}234 235MatchTableRecord MatchTable::NamedValue(unsigned NumBytes, StringRef Namespace,236                                        StringRef NamedValue) {237  return MatchTableRecord(std::nullopt, (Namespace + "::" + NamedValue).str(),238                          NumBytes, MatchTableRecord::MTRF_CommaFollows);239}240 241MatchTableRecord MatchTable::IntValue(unsigned NumBytes, int64_t IntValue) {242  assert(isUIntN(NumBytes * 8, IntValue) || isIntN(NumBytes * 8, IntValue));243  uint64_t UIntValue = IntValue;244  if (NumBytes < 8)245    UIntValue &= (UINT64_C(1) << NumBytes * 8) - 1;246  std::string Str = llvm::to_string(UIntValue);247  if (UIntValue > INT64_MAX)248    Str += 'u';249  // TODO: Could optimize this directly to save the compiler some work when250  // building the file251  return MatchTableRecord(std::nullopt, Str, NumBytes,252                          MatchTableRecord::MTRF_CommaFollows);253}254 255MatchTableRecord MatchTable::ULEB128Value(uint64_t IntValue) {256  uint8_t Buffer[10];257  unsigned Len = encodeULEB128(IntValue, Buffer);258 259  // Simple case (most common)260  if (Len == 1) {261    return MatchTableRecord(std::nullopt, llvm::to_string((unsigned)Buffer[0]),262                            1, MatchTableRecord::MTRF_CommaFollows);263  }264 265  // Print it as, e.g. /* -123456 (*/, 0xC0, 0xBB, 0x78 /*)*/266  std::string Str;267  raw_string_ostream OS(Str);268  OS << "/* " << llvm::to_string(IntValue) << "(*/";269  for (unsigned K = 0; K < Len; ++K) {270    if (K)271      OS << ", ";272    OS << "0x" << llvm::toHex({Buffer[K]});273  }274  OS << "/*)*/";275  return MatchTableRecord(std::nullopt, Str, Len,276                          MatchTableRecord::MTRF_CommaFollows |277                              MatchTableRecord::MTRF_PreEncoded);278}279 280MatchTableRecord MatchTable::Label(unsigned LabelID) {281  return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 0,282                          MatchTableRecord::MTRF_Label |283                              MatchTableRecord::MTRF_Comment |284                              MatchTableRecord::MTRF_LineBreakFollows);285}286 287MatchTableRecord MatchTable::JumpTarget(unsigned LabelID) {288  return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 4,289                          MatchTableRecord::MTRF_JumpTarget |290                              MatchTableRecord::MTRF_Comment |291                              MatchTableRecord::MTRF_CommaFollows);292}293 294void MatchTable::emitUse(raw_ostream &OS) const { OS << "MatchTable" << ID; }295 296void MatchTable::emitDeclaration(raw_ostream &OS) const {297  static constexpr unsigned BaseIndent = 4;298  unsigned Indentation = 0;299  OS << "  constexpr static uint8_t MatchTable" << ID << "[] = {";300  LineBreak.emit(OS, true, *this);301 302  // We want to display the table index of each line in a consistent303  // manner. It has to appear as a column on the left side of the table.304  // To determine how wide the column needs to be, check how many characters305  // we need to fit the largest possible index in the current table.306  const unsigned NumColsForIdx = llvm::to_string(CurrentSize).size();307 308  unsigned CurIndex = 0;309  const auto BeginLine = [&]() {310    OS.indent(BaseIndent);311    std::string IdxStr = llvm::to_string(CurIndex);312    // Pad the string with spaces to keep the size of the prefix consistent.313    OS << " /* ";314    OS.indent(NumColsForIdx - IdxStr.size()) << IdxStr << " */ ";315    OS.indent(Indentation);316  };317 318  BeginLine();319  for (auto I = Contents.begin(), E = Contents.end(); I != E; ++I) {320    bool LineBreakIsNext = false;321    const auto &NextI = std::next(I);322 323    if (NextI != E) {324      if (NextI->EmitStr == "" &&325          NextI->Flags == MatchTableRecord::MTRF_LineBreakFollows)326        LineBreakIsNext = true;327    }328 329    if (I->Flags & MatchTableRecord::MTRF_Indent)330      Indentation += 2;331 332    I->emit(OS, LineBreakIsNext, *this);333    if (I->Flags & MatchTableRecord::MTRF_LineBreakFollows)334      BeginLine();335 336    if (I->Flags & MatchTableRecord::MTRF_Outdent)337      Indentation -= 2;338 339    CurIndex += I->size();340  }341  assert(CurIndex == CurrentSize);342  OS << "}; // Size: " << CurrentSize << " bytes\n";343}344 345MatchTable MatchTable::buildTable(ArrayRef<Matcher *> Rules, bool WithCoverage,346                                  bool IsCombiner) {347  MatchTable Table(WithCoverage, IsCombiner);348  for (Matcher *Rule : Rules)349    Rule->emit(Table);350 351  return Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;352}353 354//===- LLTCodeGen ---------------------------------------------------------===//355 356std::string LLTCodeGen::getCxxEnumValue() const {357  std::string Str;358  raw_string_ostream OS(Str);359 360  emitCxxEnumValue(OS);361  return Str;362}363 364void LLTCodeGen::emitCxxEnumValue(raw_ostream &OS) const {365  if (Ty.isScalar()) {366    OS << "GILLT_s" << Ty.getSizeInBits();367    return;368  }369  if (Ty.isVector()) {370    OS << (Ty.isScalable() ? "GILLT_nxv" : "GILLT_v")371       << Ty.getElementCount().getKnownMinValue() << "s"372       << Ty.getScalarSizeInBits();373    return;374  }375  if (Ty.isPointer()) {376    OS << "GILLT_p" << Ty.getAddressSpace();377    if (Ty.getSizeInBits() > 0)378      OS << "s" << Ty.getSizeInBits();379    return;380  }381  llvm_unreachable("Unhandled LLT");382}383 384void LLTCodeGen::emitCxxConstructorCall(raw_ostream &OS) const {385  if (Ty.isScalar()) {386    OS << "LLT::scalar(" << Ty.getSizeInBits() << ")";387    return;388  }389  if (Ty.isVector()) {390    OS << "LLT::vector("391       << (Ty.isScalable() ? "ElementCount::getScalable("392                           : "ElementCount::getFixed(")393       << Ty.getElementCount().getKnownMinValue() << "), "394       << Ty.getScalarSizeInBits() << ")";395    return;396  }397  if (Ty.isPointer() && Ty.getSizeInBits() > 0) {398    OS << "LLT::pointer(" << Ty.getAddressSpace() << ", " << Ty.getSizeInBits()399       << ")";400    return;401  }402  llvm_unreachable("Unhandled LLT");403}404 405/// This ordering is used for std::unique() and llvm::sort(). There's no406/// particular logic behind the order but either A < B or B < A must be407/// true if A != B.408bool LLTCodeGen::operator<(const LLTCodeGen &Other) const {409  if (Ty.isValid() != Other.Ty.isValid())410    return Ty.isValid() < Other.Ty.isValid();411  if (!Ty.isValid())412    return false;413 414  if (Ty.isVector() != Other.Ty.isVector())415    return Ty.isVector() < Other.Ty.isVector();416  if (Ty.isScalar() != Other.Ty.isScalar())417    return Ty.isScalar() < Other.Ty.isScalar();418  if (Ty.isPointer() != Other.Ty.isPointer())419    return Ty.isPointer() < Other.Ty.isPointer();420 421  if (Ty.isPointer() && Ty.getAddressSpace() != Other.Ty.getAddressSpace())422    return Ty.getAddressSpace() < Other.Ty.getAddressSpace();423 424  if (Ty.isVector() && Ty.getElementCount() != Other.Ty.getElementCount())425    return std::tuple(Ty.isScalable(),426                      Ty.getElementCount().getKnownMinValue()) <427           std::tuple(Other.Ty.isScalable(),428                      Other.Ty.getElementCount().getKnownMinValue());429 430  assert((!Ty.isVector() || Ty.isScalable() == Other.Ty.isScalable()) &&431         "Unexpected mismatch of scalable property");432  return Ty.isVector()433             ? std::tuple(Ty.isScalable(),434                          Ty.getSizeInBits().getKnownMinValue()) <435                   std::tuple(Other.Ty.isScalable(),436                              Other.Ty.getSizeInBits().getKnownMinValue())437             : Ty.getSizeInBits().getFixedValue() <438                   Other.Ty.getSizeInBits().getFixedValue();439}440 441//===- LLTCodeGen Helpers -------------------------------------------------===//442 443std::optional<LLTCodeGen> llvm::gi::MVTToLLT(MVT VT) {444  if (VT.isVector() && !VT.getVectorElementCount().isScalar())445    return LLTCodeGen(446        LLT::vector(VT.getVectorElementCount(), VT.getScalarSizeInBits()));447 448  if (VT.isInteger() || VT.isFloatingPoint())449    return LLTCodeGen(LLT::scalar(VT.getSizeInBits()));450 451  return std::nullopt;452}453 454//===- Matcher ------------------------------------------------------------===//455 456void Matcher::optimize() {}457 458Matcher::~Matcher() = default;459 460//===- GroupMatcher -------------------------------------------------------===//461 462bool GroupMatcher::recordsOperand() const {463  return matchersRecordOperand(Conditions) || matchersRecordOperand(Matchers);464}465 466bool GroupMatcher::candidateConditionMatches(467    const PredicateMatcher &Predicate) const {468 469  if (empty()) {470    // Sharing predicates for nested instructions is not supported yet as we471    // currently don't hoist the GIM_RecordInsn's properly, therefore we can472    // only work on the original root instruction (InsnVarID == 0):473    if (Predicate.getInsnVarID() != 0)474      return false;475    // ... otherwise an empty group can handle any predicate with no specific476    // requirements:477    return true;478  }479 480  const Matcher &Representative = **Matchers.begin();481  const auto &RepresentativeCondition = Representative.getFirstCondition();482  // ... if not empty, the group can only accomodate matchers with the exact483  // same first condition:484  return Predicate.isIdentical(RepresentativeCondition);485}486 487std::unique_ptr<PredicateMatcher> GroupMatcher::popFirstCondition() {488  assert(!Conditions.empty() &&489         "Trying to pop a condition from a condition-less group");490  std::unique_ptr<PredicateMatcher> P = std::move(Conditions.front());491  Conditions.erase(Conditions.begin());492  return P;493}494 495/// Check if the Condition, which is a predicate of M, cannot be hoisted outside496/// of (i.e., checked before) M.497static bool cannotHoistCondition(const PredicateMatcher &Condition,498                                 const Matcher &M) {499  // The condition can't be hoisted if it is a C++ predicate that refers to500  // operands and the operands are registered within the matcher.501  return Condition.dependsOnOperands() && M.recordsOperand();502}503 504bool GroupMatcher::addMatcher(Matcher &Candidate) {505  if (!Candidate.hasFirstCondition())506    return false;507 508  // Only add candidates that have a matching first condition that can be509  // hoisted into the GroupMatcher.510  const PredicateMatcher &Predicate = Candidate.getFirstCondition();511  if (!candidateConditionMatches(Predicate) ||512      cannotHoistCondition(Predicate, Candidate))513    return false;514 515  Matchers.push_back(&Candidate);516  return true;517}518 519void GroupMatcher::finalize() {520  assert(Conditions.empty() && "Already finalized?");521  if (empty())522    return;523 524  Matcher &FirstRule = **Matchers.begin();525  for (;;) {526    // All the checks are expected to succeed during the first iteration:527    for (const auto &Rule : Matchers)528      if (!Rule->hasFirstCondition())529        return;530    // Hoist the first condition if it is identical in all matchers in the group531    // and it can be hoisted in every matcher.532    const auto &FirstCondition = FirstRule.getFirstCondition();533    if (cannotHoistCondition(FirstCondition, FirstRule))534      return;535    for (unsigned I = 1, E = Matchers.size(); I < E; ++I) {536      const auto &OtherFirstCondition = Matchers[I]->getFirstCondition();537      if (!OtherFirstCondition.isIdentical(FirstCondition) ||538          cannotHoistCondition(OtherFirstCondition, *Matchers[I]))539        return;540    }541 542    Conditions.push_back(FirstRule.popFirstCondition());543    for (unsigned I = 1, E = Matchers.size(); I < E; ++I)544      Matchers[I]->popFirstCondition();545  }546}547 548void GroupMatcher::emit(MatchTable &Table) {549  unsigned LabelID = ~0U;550  if (!Conditions.empty()) {551    LabelID = Table.allocateLabelID();552    Table << MatchTable::Opcode("GIM_Try", +1)553          << MatchTable::Comment("On fail goto")554          << MatchTable::JumpTarget(LabelID) << MatchTable::LineBreak;555  }556  for (auto &Condition : Conditions)557    Condition->emitPredicateOpcodes(558        Table, *static_cast<RuleMatcher *>(*Matchers.begin()));559 560  for (const auto &M : Matchers)561    M->emit(Table);562 563  // Exit the group564  if (!Conditions.empty())565    Table << MatchTable::Opcode("GIM_Reject", -1) << MatchTable::LineBreak566          << MatchTable::Label(LabelID);567}568 569void GroupMatcher::optimize() {570  // Make sure we only sort by a specific predicate within a range of rules that571  // all have that predicate checked against a specific value (not a wildcard):572  auto F = Matchers.begin();573  auto T = F;574  auto E = Matchers.end();575  while (T != E) {576    while (T != E) {577      auto *R = static_cast<RuleMatcher *>(*T);578      if (!R->getFirstConditionAsRootType().get().isValid())579        break;580      ++T;581    }582    std::stable_sort(F, T, [](Matcher *A, Matcher *B) {583      auto *L = static_cast<RuleMatcher *>(A);584      auto *R = static_cast<RuleMatcher *>(B);585      return L->getFirstConditionAsRootType() <586             R->getFirstConditionAsRootType();587    });588    if (T != E)589      F = ++T;590  }591  Matchers = optimizeRules<GroupMatcher>(Matchers, MatcherStorage);592  Matchers = optimizeRules<SwitchMatcher>(Matchers, MatcherStorage);593}594 595//===- SwitchMatcher ------------------------------------------------------===//596 597bool SwitchMatcher::recordsOperand() const {598  assert(!isa_and_present<RecordNamedOperandMatcher>(Condition.get()) &&599         "Switch conditions should not record named operands");600  return matchersRecordOperand(Matchers);601}602 603bool SwitchMatcher::isSupportedPredicateType(const PredicateMatcher &P) {604  return isa<InstructionOpcodeMatcher>(P) || isa<LLTOperandMatcher>(P);605}606 607bool SwitchMatcher::candidateConditionMatches(608    const PredicateMatcher &Predicate) const {609 610  if (empty()) {611    // Sharing predicates for nested instructions is not supported yet as we612    // currently don't hoist the GIM_RecordInsn's properly, therefore we can613    // only work on the original root instruction (InsnVarID == 0):614    if (Predicate.getInsnVarID() != 0)615      return false;616    // ... while an attempt to add even a root matcher to an empty SwitchMatcher617    // could fail as not all the types of conditions are supported:618    if (!isSupportedPredicateType(Predicate))619      return false;620    // ... or the condition might not have a proper implementation of621    // getValue() / isIdenticalDownToValue() yet:622    if (!Predicate.hasValue())623      return false;624    // ... otherwise an empty Switch can accomodate the condition with no625    // further requirements:626    return true;627  }628 629  const Matcher &CaseRepresentative = **Matchers.begin();630  const auto &RepresentativeCondition = CaseRepresentative.getFirstCondition();631  // Switch-cases must share the same kind of condition and path to the value it632  // checks:633  if (!Predicate.isIdenticalDownToValue(RepresentativeCondition))634    return false;635 636  const auto Value = Predicate.getValue();637  // ... but be unique with respect to the actual value they check:638  return Values.count(Value) == 0;639}640 641bool SwitchMatcher::addMatcher(Matcher &Candidate) {642  if (!Candidate.hasFirstCondition())643    return false;644 645  const PredicateMatcher &Predicate = Candidate.getFirstCondition();646  if (!candidateConditionMatches(Predicate))647    return false;648  const auto Value = Predicate.getValue();649  Values.insert(Value);650 651  Matchers.push_back(&Candidate);652  return true;653}654 655void SwitchMatcher::finalize() {656  assert(Condition == nullptr && "Already finalized");657  assert(Values.size() == Matchers.size() && "Broken SwitchMatcher");658  if (empty())659    return;660 661  llvm::stable_sort(Matchers, [](const Matcher *L, const Matcher *R) {662    return L->getFirstCondition().getValue() <663           R->getFirstCondition().getValue();664  });665  Condition = Matchers[0]->popFirstCondition();666  for (unsigned I = 1, E = Values.size(); I < E; ++I)667    Matchers[I]->popFirstCondition();668}669 670void SwitchMatcher::emitPredicateSpecificOpcodes(const PredicateMatcher &P,671                                                 MatchTable &Table) {672  assert(isSupportedPredicateType(P) && "Predicate type is not supported");673 674  if (const auto *Condition = dyn_cast<InstructionOpcodeMatcher>(&P)) {675    Table << MatchTable::Opcode("GIM_SwitchOpcode") << MatchTable::Comment("MI")676          << MatchTable::ULEB128Value(Condition->getInsnVarID());677    return;678  }679  if (const auto *Condition = dyn_cast<LLTOperandMatcher>(&P)) {680    Table << MatchTable::Opcode("GIM_SwitchType") << MatchTable::Comment("MI")681          << MatchTable::ULEB128Value(Condition->getInsnVarID())682          << MatchTable::Comment("Op")683          << MatchTable::ULEB128Value(Condition->getOpIdx());684    return;685  }686 687  llvm_unreachable("emitPredicateSpecificOpcodes is broken: can not handle a "688                   "predicate type that is claimed to be supported");689}690 691void SwitchMatcher::emit(MatchTable &Table) {692  assert(Values.size() == Matchers.size() && "Broken SwitchMatcher");693  if (empty())694    return;695  assert(Condition != nullptr &&696         "Broken SwitchMatcher, hasn't been finalized?");697 698  std::vector<unsigned> LabelIDs(Values.size());699  std::generate(LabelIDs.begin(), LabelIDs.end(),700                [&Table]() { return Table.allocateLabelID(); });701  const unsigned Default = Table.allocateLabelID();702 703  const int64_t LowerBound = Values.begin()->RawValue;704  const int64_t UpperBound = Values.rbegin()->RawValue + 1;705 706  emitPredicateSpecificOpcodes(*Condition, Table);707 708  Table << MatchTable::Comment("[") << MatchTable::IntValue(2, LowerBound)709        << MatchTable::IntValue(2, UpperBound) << MatchTable::Comment(")")710        << MatchTable::Comment("default:") << MatchTable::JumpTarget(Default);711 712  int64_t J = LowerBound;713  auto VI = Values.begin();714  for (unsigned I = 0, E = Values.size(); I < E; ++I) {715    auto V = *VI++;716    while (J++ < V.RawValue)717      Table << MatchTable::IntValue(4, 0);718    V.Record.turnIntoComment();719    Table << MatchTable::LineBreak << V.Record720          << MatchTable::JumpTarget(LabelIDs[I]);721  }722  Table << MatchTable::LineBreak;723 724  for (unsigned I = 0, E = Values.size(); I < E; ++I) {725    Table << MatchTable::Label(LabelIDs[I]);726    Matchers[I]->emit(Table);727    Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;728  }729  Table << MatchTable::Label(Default);730}731 732//===- RuleMatcher --------------------------------------------------------===//733 734RuleMatcher::RuleMatcher(ArrayRef<SMLoc> SrcLoc)735    : SrcLoc(SrcLoc), RuleID(NextRuleID++) {}736 737uint64_t RuleMatcher::NextRuleID = 0;738 739StringRef RuleMatcher::getOpcode() const {740  return Matchers.front()->getOpcode();741}742 743bool RuleMatcher::recordsOperand() const {744  return matchersRecordOperand(Matchers);745}746 747LLTCodeGen RuleMatcher::getFirstConditionAsRootType() {748  InstructionMatcher &InsnMatcher = *Matchers.front();749  if (!InsnMatcher.predicates_empty())750    if (const auto *TM =751            dyn_cast<LLTOperandMatcher>(&**InsnMatcher.predicates_begin()))752      if (TM->getInsnVarID() == 0 && TM->getOpIdx() == 0)753        return TM->getTy();754  return {};755}756 757void RuleMatcher::optimize() {758  for (auto &Item : InsnVariableIDs) {759    InstructionMatcher &InsnMatcher = *Item.first;760    for (auto &OM : InsnMatcher.operands()) {761      // Complex Patterns are usually expensive and they relatively rarely fail762      // on their own: more often we end up throwing away all the work done by a763      // matching part of a complex pattern because some other part of the764      // enclosing pattern didn't match. All of this makes it beneficial to765      // delay complex patterns until the very end of the rule matching,766      // especially for targets having lots of complex patterns.767      for (auto &OP : OM->predicates())768        if (isa<ComplexPatternOperandMatcher>(OP))769          EpilogueMatchers.emplace_back(std::move(OP));770      OM->eraseNullPredicates();771    }772    InsnMatcher.optimize();773  }774  llvm::sort(EpilogueMatchers, [](const std::unique_ptr<PredicateMatcher> &L,775                                  const std::unique_ptr<PredicateMatcher> &R) {776    return std::tuple(L->getKind(), L->getInsnVarID(), L->getOpIdx()) <777           std::tuple(R->getKind(), R->getInsnVarID(), R->getOpIdx());778  });779 780  // Deduplicate EraseInst actions, and if an EraseInst erases the root, place781  // it at the end to favor generation of GIR_EraseRootFromParent_Done782  DenseSet<unsigned> AlreadySeenEraseInsts;783  auto EraseRootIt = Actions.end();784  auto It = Actions.begin();785  while (It != Actions.end()) {786    if (const auto *EI = dyn_cast<EraseInstAction>(It->get())) {787      unsigned InstID = EI->getInsnID();788      if (!AlreadySeenEraseInsts.insert(InstID).second) {789        It = Actions.erase(It);790        continue;791      }792 793      if (InstID == 0)794        EraseRootIt = It;795    }796 797    ++It;798  }799 800  if (EraseRootIt != Actions.end())801    Actions.splice(Actions.end(), Actions, EraseRootIt);802}803 804bool RuleMatcher::hasFirstCondition() const {805  if (insnmatchers_empty())806    return false;807  InstructionMatcher &Matcher = insnmatchers_front();808  if (!Matcher.predicates_empty())809    return true;810  for (auto &OM : Matcher.operands())811    for (auto &OP : OM->predicates())812      if (!isa<InstructionOperandMatcher>(OP))813        return true;814  return false;815}816 817const PredicateMatcher &RuleMatcher::getFirstCondition() const {818  assert(!insnmatchers_empty() &&819         "Trying to get a condition from an empty RuleMatcher");820 821  InstructionMatcher &Matcher = insnmatchers_front();822  if (!Matcher.predicates_empty())823    return **Matcher.predicates_begin();824  // If there is no more predicate on the instruction itself, look at its825  // operands.826  for (auto &OM : Matcher.operands())827    for (auto &OP : OM->predicates())828      if (!isa<InstructionOperandMatcher>(OP))829        return *OP;830 831  llvm_unreachable("Trying to get a condition from an InstructionMatcher with "832                   "no conditions");833}834 835std::unique_ptr<PredicateMatcher> RuleMatcher::popFirstCondition() {836  assert(!insnmatchers_empty() &&837         "Trying to pop a condition from an empty RuleMatcher");838 839  InstructionMatcher &Matcher = insnmatchers_front();840  if (!Matcher.predicates_empty())841    return Matcher.predicates_pop_front();842  // If there is no more predicate on the instruction itself, look at its843  // operands.844  for (auto &OM : Matcher.operands())845    for (auto &OP : OM->predicates())846      if (!isa<InstructionOperandMatcher>(OP)) {847        std::unique_ptr<PredicateMatcher> Result = std::move(OP);848        OM->eraseNullPredicates();849        return Result;850      }851 852  llvm_unreachable("Trying to pop a condition from an InstructionMatcher with "853                   "no conditions");854}855 856GISelFlags RuleMatcher::updateGISelFlag(GISelFlags CurFlags, const Record *R,857                                        StringRef FlagName,858                                        GISelFlags FlagBit) {859  // If the value of a flag is unset, ignore it.860  // If it's set, it always takes precedence over the existing value so861  // clear/set the corresponding bit.862  bool Unset = false;863  bool Value = R->getValueAsBitOrUnset("GIIgnoreCopies", Unset);864  if (!Unset)865    return Value ? (CurFlags | FlagBit) : (CurFlags & ~FlagBit);866  return CurFlags;867}868 869SaveAndRestore<GISelFlags> RuleMatcher::setGISelFlags(const Record *R) {870  if (!R || !R->isSubClassOf("GISelFlags"))871    return {Flags, Flags};872 873  assert((R->isSubClassOf("PatFrags") || R->isSubClassOf("Pattern")) &&874         "GISelFlags is only expected on Pattern/PatFrags!");875 876  GISelFlags NewFlags =877      updateGISelFlag(Flags, R, "GIIgnoreCopies", GISF_IgnoreCopies);878  return {Flags, NewFlags};879}880 881Error RuleMatcher::defineComplexSubOperand(StringRef SymbolicName,882                                           const Record *ComplexPattern,883                                           unsigned RendererID,884                                           unsigned SubOperandID,885                                           StringRef ParentSymbolicName) {886  std::string ParentName(ParentSymbolicName);887  auto [It, Inserted] = ComplexSubOperands.try_emplace(888      SymbolicName, ComplexPattern, RendererID, SubOperandID);889  if (!Inserted) {890    const std::string &RecordedParentName =891        ComplexSubOperandsParentName[SymbolicName];892    if (RecordedParentName != ParentName)893      return failUnsupported("Error: Complex suboperand " + SymbolicName +894                             " referenced by different operands: " +895                             RecordedParentName + " and " + ParentName + ".");896    // Complex suboperand referenced more than once from same the operand is897    // used to generate 'same operand check'. Emitting of898    // GIR_ComplexSubOperandRenderer for them is already handled.899    return Error::success();900  }901 902  ComplexSubOperandsParentName[SymbolicName] = std::move(ParentName);903 904  return Error::success();905}906 907InstructionMatcher &RuleMatcher::addInstructionMatcher(StringRef SymbolicName) {908  Matchers.emplace_back(new InstructionMatcher(*this, SymbolicName));909  MutatableInsns.insert(Matchers.back().get());910  return *Matchers.back();911}912 913void RuleMatcher::addRequiredSimplePredicate(StringRef PredName) {914  RequiredSimplePredicates.push_back(PredName.str());915}916 917const std::vector<std::string> &RuleMatcher::getRequiredSimplePredicates() {918  return RequiredSimplePredicates;919}920 921unsigned RuleMatcher::implicitlyDefineInsnVar(InstructionMatcher &Matcher) {922  unsigned NewInsnVarID = NextInsnVarID++;923  InsnVariableIDs[&Matcher] = NewInsnVarID;924  return NewInsnVarID;925}926 927unsigned RuleMatcher::getInsnVarID(InstructionMatcher &InsnMatcher) const {928  const auto &I = InsnVariableIDs.find(&InsnMatcher);929  if (I != InsnVariableIDs.end())930    return I->second;931  llvm_unreachable("Matched Insn was not captured in a local variable");932}933 934void RuleMatcher::defineOperand(StringRef SymbolicName, OperandMatcher &OM) {935  if (DefinedOperands.try_emplace(SymbolicName, &OM).second)936    return;937 938  // If the operand is already defined, then we must ensure both references in939  // the matcher have the exact same node.940  RuleMatcher &RM = OM.getInstructionMatcher().getRuleMatcher();941  OM.addPredicate<SameOperandMatcher>(942      OM.getSymbolicName(), getOperandMatcher(OM.getSymbolicName()).getOpIdx(),943      RM.getGISelFlags());944}945 946void RuleMatcher::definePhysRegOperand(const Record *Reg, OperandMatcher &OM) {947  PhysRegOperands.try_emplace(Reg, &OM);948}949 950InstructionMatcher &951RuleMatcher::getInstructionMatcher(StringRef SymbolicName) const {952  for (const auto &I : InsnVariableIDs)953    if (I.first->getSymbolicName() == SymbolicName)954      return *I.first;955  llvm_unreachable(956      ("Failed to lookup instruction " + SymbolicName).str().c_str());957}958 959const OperandMatcher &960RuleMatcher::getPhysRegOperandMatcher(const Record *Reg) const {961  const auto &I = PhysRegOperands.find(Reg);962 963  if (I == PhysRegOperands.end()) {964    PrintFatalError(SrcLoc, "Register " + Reg->getName() +965                                " was not declared in matcher");966  }967 968  return *I->second;969}970 971OperandMatcher &RuleMatcher::getOperandMatcher(StringRef Name) {972  const auto &I = DefinedOperands.find(Name);973 974  if (I == DefinedOperands.end())975    PrintFatalError(SrcLoc, "Operand " + Name + " was not declared in matcher");976 977  return *I->second;978}979 980const OperandMatcher &RuleMatcher::getOperandMatcher(StringRef Name) const {981  const auto &I = DefinedOperands.find(Name);982 983  if (I == DefinedOperands.end())984    PrintFatalError(SrcLoc, "Operand " + Name + " was not declared in matcher");985 986  return *I->second;987}988 989void RuleMatcher::emit(MatchTable &Table) {990  if (Matchers.empty())991    llvm_unreachable("Unexpected empty matcher!");992 993  // The representation supports rules that require multiple roots such as:994  //    %ptr(p0) = ...995  //    %elt0(s32) = G_LOAD %ptr996  //    %1(p0) = G_ADD %ptr, 4997  //    %elt1(s32) = G_LOAD p0 %1998  // which could be usefully folded into:999  //    %ptr(p0) = ...1000  //    %elt0(s32), %elt1(s32) = TGT_LOAD_PAIR %ptr1001  // on some targets but we don't need to make use of that yet.1002  assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");1003 1004  unsigned LabelID = Table.allocateLabelID();1005  Table << MatchTable::Opcode("GIM_Try", +1)1006        << MatchTable::Comment("On fail goto")1007        << MatchTable::JumpTarget(LabelID)1008        << MatchTable::Comment(("Rule ID " + Twine(RuleID) + " //").str())1009        << MatchTable::LineBreak;1010 1011  if (!RequiredFeatures.empty() || HwModeIdx >= 0) {1012    Table << MatchTable::Opcode("GIM_CheckFeatures")1013          << MatchTable::NamedValue(1014                 2, getNameForFeatureBitset(RequiredFeatures, HwModeIdx))1015          << MatchTable::LineBreak;1016  }1017 1018  if (!RequiredSimplePredicates.empty()) {1019    for (const auto &Pred : RequiredSimplePredicates) {1020      Table << MatchTable::Opcode("GIM_CheckSimplePredicate")1021            << MatchTable::NamedValue(2, Pred) << MatchTable::LineBreak;1022    }1023  }1024 1025  Matchers.front()->emitPredicateOpcodes(Table, *this);1026 1027  // Check if it's safe to replace registers.1028  for (const auto &MA : Actions)1029    MA->emitAdditionalPredicates(Table, *this);1030 1031  // We must also check if it's safe to fold the matched instructions.1032  if (InsnVariableIDs.size() >= 2) {1033 1034    // FIXME: Emit checks to determine it's _actually_ safe to fold and/or1035    //        account for unsafe cases.1036    //1037    //        Example:1038    //          MI1--> %0 = ...1039    //                 %1 = ... %01040    //          MI0--> %2 = ... %01041    //          It's not safe to erase MI1. We currently handle this by not1042    //          erasing %0 (even when it's dead).1043    //1044    //        Example:1045    //          MI1--> %0 = load volatile @a1046    //                 %1 = load volatile @a1047    //          MI0--> %2 = ... %01048    //          It's not safe to sink %0's def past %1. We currently handle1049    //          this by rejecting all loads.1050    //1051    //        Example:1052    //          MI1--> %0 = load @a1053    //                 %1 = store @a1054    //          MI0--> %2 = ... %01055    //          It's not safe to sink %0's def past %1. We currently handle1056    //          this by rejecting all loads.1057    //1058    //        Example:1059    //                   G_CONDBR %cond, @BB11060    //                 BB0:1061    //          MI1-->   %0 = load @a1062    //                   G_BR @BB11063    //                 BB1:1064    //          MI0-->   %2 = ... %01065    //          It's not always safe to sink %0 across control flow. In this1066    //          case it may introduce a memory fault. We currentl handle1067    //          this by rejecting all loads.1068 1069    Table << MatchTable::Opcode("GIM_CheckIsSafeToFold")1070          << MatchTable::Comment("NumInsns")1071          << MatchTable::IntValue(1, InsnVariableIDs.size() - 1)1072          << MatchTable::LineBreak;1073  }1074 1075  for (const auto &PM : EpilogueMatchers)1076    PM->emitPredicateOpcodes(Table, *this);1077 1078  if (!CustomCXXAction.empty()) {1079    /// Handle combiners relying on custom C++ code instead of actions.1080    assert(Table.isCombiner() && "CustomCXXAction is only for combiners!");1081    // We cannot have actions other than debug comments.1082    assert(none_of(Actions, [](auto &A) {1083      return A->getKind() != MatchAction::AK_DebugComment;1084    }));1085    for (const auto &MA : Actions)1086      MA->emitActionOpcodes(Table, *this);1087    Table << MatchTable::Opcode("GIR_DoneWithCustomAction", -1)1088          << MatchTable::Comment("Fn")1089          << MatchTable::NamedValue(2, CustomCXXAction)1090          << MatchTable::LineBreak;1091  } else {1092    // Emit all actions except the last one, then emit coverage and emit the1093    // final action.1094    //1095    // This is because some actions, such as GIR_EraseRootFromParent_Done, also1096    // double as a GIR_Done and terminate execution of the rule.1097    if (!Actions.empty()) {1098      for (const auto &MA : drop_end(Actions))1099        MA->emitActionOpcodes(Table, *this);1100    }1101 1102    assert((Table.isWithCoverage() ? !Table.isCombiner() : true) &&1103           "Combiner tables don't support coverage!");1104    if (Table.isWithCoverage())1105      Table << MatchTable::Opcode("GIR_Coverage")1106            << MatchTable::IntValue(4, RuleID) << MatchTable::LineBreak;1107    else if (!Table.isCombiner())1108      Table << MatchTable::Comment(1109                   ("GIR_Coverage, " + Twine(RuleID) + ",").str())1110            << MatchTable::LineBreak;1111 1112    if (Actions.empty() ||1113        !Actions.back()->emitActionOpcodesAndDone(Table, *this)) {1114      Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak;1115    }1116  }1117 1118  Table << MatchTable::Label(LabelID);1119  ++NumPatternEmitted;1120}1121 1122bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const {1123  // Rules involving more match roots have higher priority.1124  if (Matchers.size() > B.Matchers.size())1125    return true;1126  if (Matchers.size() < B.Matchers.size())1127    return false;1128 1129  for (auto Matcher : zip(Matchers, B.Matchers)) {1130    if (std::get<0>(Matcher)->isHigherPriorityThan(*std::get<1>(Matcher)))1131      return true;1132    if (std::get<1>(Matcher)->isHigherPriorityThan(*std::get<0>(Matcher)))1133      return false;1134  }1135 1136  return false;1137}1138 1139unsigned RuleMatcher::countRendererFns() const {1140  return std::accumulate(1141      Matchers.begin(), Matchers.end(), 0,1142      [](unsigned A, const std::unique_ptr<InstructionMatcher> &Matcher) {1143        return A + Matcher->countRendererFns();1144      });1145}1146 1147void RuleMatcher::insnmatchers_pop_front() { Matchers.erase(Matchers.begin()); }1148 1149//===- PredicateMatcher ---------------------------------------------------===//1150 1151PredicateMatcher::~PredicateMatcher() = default;1152 1153//===- OperandPredicateMatcher --------------------------------------------===//1154 1155OperandPredicateMatcher::~OperandPredicateMatcher() = default;1156 1157bool OperandPredicateMatcher::isHigherPriorityThan(1158    const OperandPredicateMatcher &B) const {1159  // Generally speaking, an instruction is more important than an Int or a1160  // LiteralInt because it can cover more nodes but there's an exception to1161  // this. G_CONSTANT's are less important than either of those two because they1162  // are more permissive.1163 1164  const auto *AOM = dyn_cast<InstructionOperandMatcher>(this);1165  const auto *BOM = dyn_cast<InstructionOperandMatcher>(&B);1166  bool AIsConstantInsn = AOM && AOM->getInsnMatcher().isConstantInstruction();1167  bool BIsConstantInsn = BOM && BOM->getInsnMatcher().isConstantInstruction();1168 1169  // The relative priorities between a G_CONSTANT and any other instruction1170  // don't actually matter but this code is needed to ensure a strict weak1171  // ordering. This is particularly important on Windows where the rules will1172  // be incorrectly sorted without it.1173  if (AOM && BOM)1174    return !AIsConstantInsn && BIsConstantInsn;1175 1176  if (AIsConstantInsn && (B.Kind == OPM_Int || B.Kind == OPM_LiteralInt))1177    return false;1178  if (BIsConstantInsn && (Kind == OPM_Int || Kind == OPM_LiteralInt))1179    return true;1180 1181  return Kind < B.Kind;1182}1183 1184//===- SameOperandMatcher -------------------------------------------------===//1185 1186void SameOperandMatcher::emitPredicateOpcodes(MatchTable &Table,1187                                              RuleMatcher &Rule) const {1188  const OperandMatcher &OtherOM = Rule.getOperandMatcher(MatchingName);1189  unsigned OtherInsnVarID = Rule.getInsnVarID(OtherOM.getInstructionMatcher());1190  assert(OtherInsnVarID == OtherOM.getInstructionMatcher().getInsnVarID());1191  const bool IgnoreCopies = Flags & GISF_IgnoreCopies;1192  Table << MatchTable::Opcode(IgnoreCopies1193                                  ? "GIM_CheckIsSameOperandIgnoreCopies"1194                                  : "GIM_CheckIsSameOperand")1195        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)1196        << MatchTable::Comment("OpIdx") << MatchTable::ULEB128Value(OpIdx)1197        << MatchTable::Comment("OtherMI")1198        << MatchTable::ULEB128Value(OtherInsnVarID)1199        << MatchTable::Comment("OtherOpIdx")1200        << MatchTable::ULEB128Value(OtherOM.getOpIdx())1201        << MatchTable::LineBreak;1202}1203 1204//===- LLTOperandMatcher --------------------------------------------------===//1205 1206std::map<LLTCodeGen, unsigned> LLTOperandMatcher::TypeIDValues;1207 1208RecordAndValue LLTOperandMatcher::getValue() const {1209  const auto VI = TypeIDValues.find(Ty);1210  if (VI == TypeIDValues.end())1211    return MatchTable::NamedValue(1, getTy().getCxxEnumValue());1212  return {MatchTable::NamedValue(1, getTy().getCxxEnumValue()), VI->second};1213}1214 1215bool LLTOperandMatcher::hasValue() const {1216  if (TypeIDValues.size() != KnownTypes.size())1217    initTypeIDValuesMap();1218  return TypeIDValues.count(Ty);1219}1220 1221void LLTOperandMatcher::emitPredicateOpcodes(MatchTable &Table,1222                                             RuleMatcher &Rule) const {1223  if (InsnVarID == 0) {1224    Table << MatchTable::Opcode("GIM_RootCheckType");1225  } else {1226    Table << MatchTable::Opcode("GIM_CheckType") << MatchTable::Comment("MI")1227          << MatchTable::ULEB128Value(InsnVarID);1228  }1229  Table << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)1230        << MatchTable::Comment("Type") << getValue().Record1231        << MatchTable::LineBreak;1232}1233 1234//===- PointerToAnyOperandMatcher -----------------------------------------===//1235 1236void PointerToAnyOperandMatcher::emitPredicateOpcodes(MatchTable &Table,1237                                                      RuleMatcher &Rule) const {1238  Table << MatchTable::Opcode("GIM_CheckPointerToAny")1239        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)1240        << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)1241        << MatchTable::Comment("SizeInBits")1242        << MatchTable::ULEB128Value(SizeInBits) << MatchTable::LineBreak;1243}1244 1245//===- RecordNamedOperandMatcher ------------------------------------------===//1246 1247void RecordNamedOperandMatcher::emitPredicateOpcodes(MatchTable &Table,1248                                                     RuleMatcher &Rule) const {1249  Table << MatchTable::Opcode("GIM_RecordNamedOperand")1250        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)1251        << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)1252        << MatchTable::Comment("StoreIdx") << MatchTable::ULEB128Value(StoreIdx)1253        << MatchTable::Comment("Name : " + Name) << MatchTable::LineBreak;1254}1255 1256//===- RecordRegisterType ------------------------------------------===//1257 1258void RecordRegisterType::emitPredicateOpcodes(MatchTable &Table,1259                                              RuleMatcher &Rule) const {1260  assert(Idx < 0 && "Temp types always have negative indexes!");1261  Table << MatchTable::Opcode("GIM_RecordRegType") << MatchTable::Comment("MI")1262        << MatchTable::ULEB128Value(InsnVarID) << MatchTable::Comment("Op")1263        << MatchTable::ULEB128Value(OpIdx) << MatchTable::Comment("TempTypeIdx")1264        << MatchTable::IntValue(1, Idx) << MatchTable::LineBreak;1265}1266 1267//===- ComplexPatternOperandMatcher ---------------------------------------===//1268 1269void ComplexPatternOperandMatcher::emitPredicateOpcodes(1270    MatchTable &Table, RuleMatcher &Rule) const {1271  unsigned ID = getAllocatedTemporariesBaseID();1272  Table << MatchTable::Opcode("GIM_CheckComplexPattern")1273        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)1274        << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)1275        << MatchTable::Comment("Renderer") << MatchTable::IntValue(2, ID)1276        << MatchTable::NamedValue(2, ("GICP_" + TheDef.getName()).str())1277        << MatchTable::LineBreak;1278}1279 1280unsigned ComplexPatternOperandMatcher::getAllocatedTemporariesBaseID() const {1281  return Operand.getAllocatedTemporariesBaseID();1282}1283 1284//===- RegisterBankOperandMatcher -----------------------------------------===//1285 1286bool RegisterBankOperandMatcher::isIdentical(const PredicateMatcher &B) const {1287  return OperandPredicateMatcher::isIdentical(B) &&1288         RC.getDef() == cast<RegisterBankOperandMatcher>(&B)->RC.getDef();1289}1290 1291void RegisterBankOperandMatcher::emitPredicateOpcodes(MatchTable &Table,1292                                                      RuleMatcher &Rule) const {1293  if (InsnVarID == 0) {1294    Table << MatchTable::Opcode("GIM_RootCheckRegBankForClass");1295  } else {1296    Table << MatchTable::Opcode("GIM_CheckRegBankForClass")1297          << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID);1298  }1299 1300  Table << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)1301        << MatchTable::Comment("RC")1302        << MatchTable::NamedValue(2, RC.getQualifiedIdName())1303        << MatchTable::LineBreak;1304}1305 1306//===- MBBOperandMatcher --------------------------------------------------===//1307 1308void MBBOperandMatcher::emitPredicateOpcodes(MatchTable &Table,1309                                             RuleMatcher &Rule) const {1310  Table << MatchTable::Opcode("GIM_CheckIsMBB") << MatchTable::Comment("MI")1311        << MatchTable::ULEB128Value(InsnVarID) << MatchTable::Comment("Op")1312        << MatchTable::ULEB128Value(OpIdx) << MatchTable::LineBreak;1313}1314 1315//===- ImmOperandMatcher --------------------------------------------------===//1316 1317void ImmOperandMatcher::emitPredicateOpcodes(MatchTable &Table,1318                                             RuleMatcher &Rule) const {1319  Table << MatchTable::Opcode("GIM_CheckIsImm") << MatchTable::Comment("MI")1320        << MatchTable::ULEB128Value(InsnVarID) << MatchTable::Comment("Op")1321        << MatchTable::ULEB128Value(OpIdx) << MatchTable::LineBreak;1322}1323 1324//===- ConstantIntOperandMatcher ------------------------------------------===//1325 1326void ConstantIntOperandMatcher::emitPredicateOpcodes(MatchTable &Table,1327                                                     RuleMatcher &Rule) const {1328  const bool IsInt8 = isInt<8>(Value);1329  Table << MatchTable::Opcode(IsInt8 ? "GIM_CheckConstantInt8"1330                                     : "GIM_CheckConstantInt")1331        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)1332        << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)1333        << MatchTable::IntValue(IsInt8 ? 1 : 8, Value) << MatchTable::LineBreak;1334}1335 1336//===- LiteralIntOperandMatcher -------------------------------------------===//1337 1338void LiteralIntOperandMatcher::emitPredicateOpcodes(MatchTable &Table,1339                                                    RuleMatcher &Rule) const {1340  Table << MatchTable::Opcode("GIM_CheckLiteralInt")1341        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)1342        << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)1343        << MatchTable::IntValue(8, Value) << MatchTable::LineBreak;1344}1345 1346//===- CmpPredicateOperandMatcher -----------------------------------------===//1347 1348void CmpPredicateOperandMatcher::emitPredicateOpcodes(MatchTable &Table,1349                                                      RuleMatcher &Rule) const {1350  Table << MatchTable::Opcode("GIM_CheckCmpPredicate")1351        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)1352        << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)1353        << MatchTable::Comment("Predicate")1354        << MatchTable::NamedValue(2, "CmpInst", PredName)1355        << MatchTable::LineBreak;1356}1357 1358//===- IntrinsicIDOperandMatcher ------------------------------------------===//1359 1360void IntrinsicIDOperandMatcher::emitPredicateOpcodes(MatchTable &Table,1361                                                     RuleMatcher &Rule) const {1362  Table << MatchTable::Opcode("GIM_CheckIntrinsicID")1363        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)1364        << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)1365        << MatchTable::NamedValue(2, "Intrinsic::" + II->EnumName.str())1366        << MatchTable::LineBreak;1367}1368 1369//===- OperandImmPredicateMatcher -----------------------------------------===//1370 1371void OperandImmPredicateMatcher::emitPredicateOpcodes(MatchTable &Table,1372                                                      RuleMatcher &Rule) const {1373  Table << MatchTable::Opcode("GIM_CheckImmOperandPredicate")1374        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)1375        << MatchTable::Comment("MO") << MatchTable::ULEB128Value(OpIdx)1376        << MatchTable::Comment("Predicate")1377        << MatchTable::NamedValue(2, getEnumNameForPredicate(Predicate))1378        << MatchTable::LineBreak;1379}1380 1381//===- OperandLeafPredicateMatcher1382//-----------------------------------------===//1383 1384void OperandLeafPredicateMatcher::emitPredicateOpcodes(1385    MatchTable &Table, RuleMatcher &Rule) const {1386  Table << MatchTable::Opcode("GIM_CheckLeafOperandPredicate")1387        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)1388        << MatchTable::Comment("MO") << MatchTable::ULEB128Value(OpIdx)1389        << MatchTable::Comment("Predicate")1390        << MatchTable::NamedValue(2, getEnumNameForPredicate(Predicate))1391        << MatchTable::LineBreak;1392}1393 1394//===- OperandMatcher -----------------------------------------------------===//1395 1396std::string OperandMatcher::getOperandExpr(unsigned InsnVarID) const {1397  return "State.MIs[" + llvm::to_string(InsnVarID) + "]->getOperand(" +1398         llvm::to_string(OpIdx) + ")";1399}1400 1401unsigned OperandMatcher::getInsnVarID() const { return Insn.getInsnVarID(); }1402 1403TempTypeIdx OperandMatcher::getTempTypeIdx(RuleMatcher &Rule) {1404  assert(!IsVariadic && "Cannot use this on variadic operands!");1405  if (TTIdx >= 0) {1406    // Temp type index not assigned yet, so assign one and add the necessary1407    // predicate.1408    TTIdx = Rule.getNextTempTypeIdx();1409    assert(TTIdx < 0);1410    addPredicate<RecordRegisterType>(TTIdx);1411    return TTIdx;1412  }1413  return TTIdx;1414}1415 1416bool OperandMatcher::recordsOperand() const {1417  return matchersRecordOperand(Predicates);1418}1419 1420void OperandMatcher::emitPredicateOpcodes(MatchTable &Table,1421                                          RuleMatcher &Rule) {1422  if (!Optimized) {1423    std::string Comment;1424    raw_string_ostream CommentOS(Comment);1425    CommentOS << "MIs[" << getInsnVarID() << "] ";1426    if (SymbolicName.empty())1427      CommentOS << "Operand " << OpIdx;1428    else1429      CommentOS << SymbolicName;1430    Table << MatchTable::Comment(Comment) << MatchTable::LineBreak;1431  }1432 1433  emitPredicateListOpcodes(Table, Rule);1434}1435 1436bool OperandMatcher::isHigherPriorityThan(OperandMatcher &B) {1437  // Operand matchers involving more predicates have higher priority.1438  if (predicates_size() > B.predicates_size())1439    return true;1440  if (predicates_size() < B.predicates_size())1441    return false;1442 1443  // This assumes that predicates are added in a consistent order.1444  for (auto &&Predicate : zip(predicates(), B.predicates())) {1445    if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate)))1446      return true;1447    if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate)))1448      return false;1449  }1450 1451  return false;1452}1453 1454unsigned OperandMatcher::countRendererFns() {1455  return std::accumulate(1456      predicates().begin(), predicates().end(), 0,1457      [](unsigned A,1458         const std::unique_ptr<OperandPredicateMatcher> &Predicate) {1459        return A + Predicate->countRendererFns();1460      });1461}1462 1463Error OperandMatcher::addTypeCheckPredicate(const TypeSetByHwMode &VTy,1464                                            bool OperandIsAPointer) {1465  if (!VTy.isMachineValueType())1466    return failUnsupported("unsupported typeset");1467 1468  if ((VTy.getMachineValueType() == MVT::iPTR ||1469       VTy.getMachineValueType() == MVT::cPTR) &&1470      OperandIsAPointer) {1471    addPredicate<PointerToAnyOperandMatcher>(0);1472    return Error::success();1473  }1474 1475  auto OpTyOrNone = MVTToLLT(VTy.getMachineValueType().SimpleTy);1476  if (!OpTyOrNone)1477    return failUnsupported("unsupported type");1478 1479  if (OperandIsAPointer)1480    addPredicate<PointerToAnyOperandMatcher>(OpTyOrNone->get().getSizeInBits());1481  else if (VTy.isPointer())1482    addPredicate<LLTOperandMatcher>(1483        LLT::pointer(VTy.getPtrAddrSpace(), OpTyOrNone->get().getSizeInBits()));1484  else1485    addPredicate<LLTOperandMatcher>(*OpTyOrNone);1486  return Error::success();1487}1488 1489//===- InstructionOpcodeMatcher -------------------------------------------===//1490 1491DenseMap<const CodeGenInstruction *, unsigned>1492    InstructionOpcodeMatcher::OpcodeValues;1493 1494RecordAndValue1495InstructionOpcodeMatcher::getInstValue(const CodeGenInstruction *I) const {1496  const auto VI = OpcodeValues.find(I);1497  if (VI != OpcodeValues.end())1498    return {MatchTable::NamedValue(2, I->Namespace, I->getName()), VI->second};1499  return MatchTable::NamedValue(2, I->Namespace, I->getName());1500}1501 1502void InstructionOpcodeMatcher::initOpcodeValuesMap(1503    const CodeGenTarget &Target) {1504  OpcodeValues.clear();1505 1506  for (const CodeGenInstruction *I : Target.getInstructions())1507    OpcodeValues[I] = Target.getInstrIntValue(I->TheDef);1508}1509 1510RecordAndValue InstructionOpcodeMatcher::getValue() const {1511  assert(Insts.size() == 1);1512 1513  const CodeGenInstruction *I = Insts[0];1514  const auto VI = OpcodeValues.find(I);1515  if (VI != OpcodeValues.end())1516    return {MatchTable::NamedValue(2, I->Namespace, I->getName()), VI->second};1517  return MatchTable::NamedValue(2, I->Namespace, I->getName());1518}1519 1520void InstructionOpcodeMatcher::emitPredicateOpcodes(MatchTable &Table,1521                                                    RuleMatcher &Rule) const {1522  StringRef CheckType =1523      Insts.size() == 1 ? "GIM_CheckOpcode" : "GIM_CheckOpcodeIsEither";1524  Table << MatchTable::Opcode(CheckType) << MatchTable::Comment("MI")1525        << MatchTable::ULEB128Value(InsnVarID);1526 1527  for (const CodeGenInstruction *I : Insts)1528    Table << getInstValue(I).Record;1529  Table << MatchTable::LineBreak;1530}1531 1532bool InstructionOpcodeMatcher::isHigherPriorityThan(1533    const InstructionPredicateMatcher &B) const {1534  if (InstructionPredicateMatcher::isHigherPriorityThan(B))1535    return true;1536  if (B.InstructionPredicateMatcher::isHigherPriorityThan(*this))1537    return false;1538 1539  // Prioritize opcodes for cosmetic reasons in the generated source. Although1540  // this is cosmetic at the moment, we may want to drive a similar ordering1541  // using instruction frequency information to improve compile time.1542  if (const InstructionOpcodeMatcher *BO =1543          dyn_cast<InstructionOpcodeMatcher>(&B))1544    return Insts[0]->getName() < BO->Insts[0]->getName();1545 1546  return false;1547}1548 1549bool InstructionOpcodeMatcher::isConstantInstruction() const {1550  return Insts.size() == 1 && Insts[0]->getName() == "G_CONSTANT";1551}1552 1553StringRef InstructionOpcodeMatcher::getOpcode() const {1554  return Insts[0]->getName();1555}1556 1557bool InstructionOpcodeMatcher::isVariadicNumOperands() const {1558  // If one is variadic, they all should be.1559  return Insts[0]->Operands.isVariadic;1560}1561 1562StringRef InstructionOpcodeMatcher::getOperandType(unsigned OpIdx) const {1563  // Types expected to be uniform for all alternatives.1564  return Insts[0]->Operands[OpIdx].OperandType;1565}1566 1567//===- InstructionNumOperandsMatcher --------------------------------------===//1568 1569void InstructionNumOperandsMatcher::emitPredicateOpcodes(1570    MatchTable &Table, RuleMatcher &Rule) const {1571  StringRef Opc;1572  switch (CK) {1573  case CheckKind::Eq:1574    Opc = "GIM_CheckNumOperands";1575    break;1576  case CheckKind::GE:1577    Opc = "GIM_CheckNumOperandsGE";1578    break;1579  case CheckKind::LE:1580    Opc = "GIM_CheckNumOperandsLE";1581    break;1582  }1583  Table << MatchTable::Opcode(Opc) << MatchTable::Comment("MI")1584        << MatchTable::ULEB128Value(InsnVarID)1585        << MatchTable::Comment("Expected")1586        << MatchTable::ULEB128Value(NumOperands) << MatchTable::LineBreak;1587}1588 1589//===- InstructionImmPredicateMatcher -------------------------------------===//1590 1591bool InstructionImmPredicateMatcher::isIdentical(1592    const PredicateMatcher &B) const {1593  return InstructionPredicateMatcher::isIdentical(B) &&1594         Predicate.getOrigPatFragRecord() ==1595             cast<InstructionImmPredicateMatcher>(&B)1596                 ->Predicate.getOrigPatFragRecord();1597}1598 1599void InstructionImmPredicateMatcher::emitPredicateOpcodes(1600    MatchTable &Table, RuleMatcher &Rule) const {1601  Table << MatchTable::Opcode(getMatchOpcodeForImmPredicate(Predicate))1602        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)1603        << MatchTable::Comment("Predicate")1604        << MatchTable::NamedValue(2, getEnumNameForPredicate(Predicate))1605        << MatchTable::LineBreak;1606}1607 1608//===- AtomicOrderingMMOPredicateMatcher ----------------------------------===//1609 1610bool AtomicOrderingMMOPredicateMatcher::isIdentical(1611    const PredicateMatcher &B) const {1612  if (!InstructionPredicateMatcher::isIdentical(B))1613    return false;1614  const auto &R = *cast<AtomicOrderingMMOPredicateMatcher>(&B);1615  return Order == R.Order && Comparator == R.Comparator;1616}1617 1618void AtomicOrderingMMOPredicateMatcher::emitPredicateOpcodes(1619    MatchTable &Table, RuleMatcher &Rule) const {1620  StringRef Opcode = "GIM_CheckAtomicOrdering";1621 1622  if (Comparator == AO_OrStronger)1623    Opcode = "GIM_CheckAtomicOrderingOrStrongerThan";1624  if (Comparator == AO_WeakerThan)1625    Opcode = "GIM_CheckAtomicOrderingWeakerThan";1626 1627  Table << MatchTable::Opcode(Opcode) << MatchTable::Comment("MI")1628        << MatchTable::ULEB128Value(InsnVarID) << MatchTable::Comment("Order")1629        << MatchTable::NamedValue(1,1630                                  ("(uint8_t)AtomicOrdering::" + Order).str())1631        << MatchTable::LineBreak;1632}1633 1634//===- MemorySizePredicateMatcher -----------------------------------------===//1635 1636void MemorySizePredicateMatcher::emitPredicateOpcodes(MatchTable &Table,1637                                                      RuleMatcher &Rule) const {1638  Table << MatchTable::Opcode("GIM_CheckMemorySizeEqualTo")1639        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)1640        << MatchTable::Comment("MMO") << MatchTable::ULEB128Value(MMOIdx)1641        << MatchTable::Comment("Size") << MatchTable::IntValue(4, Size)1642        << MatchTable::LineBreak;1643}1644 1645//===- MemoryAddressSpacePredicateMatcher ---------------------------------===//1646 1647bool MemoryAddressSpacePredicateMatcher::isIdentical(1648    const PredicateMatcher &B) const {1649  if (!InstructionPredicateMatcher::isIdentical(B))1650    return false;1651  auto *Other = cast<MemoryAddressSpacePredicateMatcher>(&B);1652  return MMOIdx == Other->MMOIdx && AddrSpaces == Other->AddrSpaces;1653}1654 1655void MemoryAddressSpacePredicateMatcher::emitPredicateOpcodes(1656    MatchTable &Table, RuleMatcher &Rule) const {1657  assert(AddrSpaces.size() < 256);1658  Table << MatchTable::Opcode("GIM_CheckMemoryAddressSpace")1659        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)1660        << MatchTable::Comment("MMO")1661        << MatchTable::ULEB128Value(MMOIdx)1662        // Encode number of address spaces to expect.1663        << MatchTable::Comment("NumAddrSpace")1664        << MatchTable::IntValue(1, AddrSpaces.size());1665  for (unsigned AS : AddrSpaces)1666    Table << MatchTable::Comment("AddrSpace") << MatchTable::ULEB128Value(AS);1667 1668  Table << MatchTable::LineBreak;1669}1670 1671//===- MemoryAlignmentPredicateMatcher ------------------------------------===//1672 1673bool MemoryAlignmentPredicateMatcher::isIdentical(1674    const PredicateMatcher &B) const {1675  if (!InstructionPredicateMatcher::isIdentical(B))1676    return false;1677  auto *Other = cast<MemoryAlignmentPredicateMatcher>(&B);1678  return MMOIdx == Other->MMOIdx && MinAlign == Other->MinAlign;1679}1680 1681void MemoryAlignmentPredicateMatcher::emitPredicateOpcodes(1682    MatchTable &Table, RuleMatcher &Rule) const {1683  // TODO: we could support more, just need to emit the right opcode or switch1684  // to log alignment.1685  assert(MinAlign < 256);1686  Table << MatchTable::Opcode("GIM_CheckMemoryAlignment")1687        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)1688        << MatchTable::Comment("MMO") << MatchTable::ULEB128Value(MMOIdx)1689        << MatchTable::Comment("MinAlign") << MatchTable::IntValue(1, MinAlign)1690        << MatchTable::LineBreak;1691}1692 1693//===- MemoryVsLLTSizePredicateMatcher ------------------------------------===//1694 1695bool MemoryVsLLTSizePredicateMatcher::isIdentical(1696    const PredicateMatcher &B) const {1697  return InstructionPredicateMatcher::isIdentical(B) &&1698         MMOIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->MMOIdx &&1699         Relation == cast<MemoryVsLLTSizePredicateMatcher>(&B)->Relation &&1700         OpIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->OpIdx;1701}1702 1703void MemoryVsLLTSizePredicateMatcher::emitPredicateOpcodes(1704    MatchTable &Table, RuleMatcher &Rule) const {1705  Table << MatchTable::Opcode(1706               Relation == EqualTo       ? "GIM_CheckMemorySizeEqualToLLT"1707               : Relation == GreaterThan ? "GIM_CheckMemorySizeGreaterThanLLT"1708                                         : "GIM_CheckMemorySizeLessThanLLT")1709        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)1710        << MatchTable::Comment("MMO") << MatchTable::ULEB128Value(MMOIdx)1711        << MatchTable::Comment("OpIdx") << MatchTable::ULEB128Value(OpIdx)1712        << MatchTable::LineBreak;1713}1714 1715//===- VectorSplatImmPredicateMatcher -------------------------------------===//1716 1717void VectorSplatImmPredicateMatcher::emitPredicateOpcodes(1718    MatchTable &Table, RuleMatcher &Rule) const {1719  if (Kind == AllOnes)1720    Table << MatchTable::Opcode("GIM_CheckIsBuildVectorAllOnes");1721  else1722    Table << MatchTable::Opcode("GIM_CheckIsBuildVectorAllZeros");1723 1724  Table << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID);1725  Table << MatchTable::LineBreak;1726}1727 1728//===- GenericInstructionPredicateMatcher ---------------------------------===//1729 1730GenericInstructionPredicateMatcher::GenericInstructionPredicateMatcher(1731    unsigned InsnVarID, TreePredicateFn Predicate)1732    : GenericInstructionPredicateMatcher(InsnVarID,1733                                         getEnumNameForPredicate(Predicate)) {}1734 1735bool GenericInstructionPredicateMatcher::isIdentical(1736    const PredicateMatcher &B) const {1737  return InstructionPredicateMatcher::isIdentical(B) &&1738         EnumVal ==1739             static_cast<const GenericInstructionPredicateMatcher &>(B).EnumVal;1740}1741void GenericInstructionPredicateMatcher::emitPredicateOpcodes(1742    MatchTable &Table, RuleMatcher &Rule) const {1743  Table << MatchTable::Opcode("GIM_CheckCxxInsnPredicate")1744        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)1745        << MatchTable::Comment("FnId") << MatchTable::NamedValue(2, EnumVal)1746        << MatchTable::LineBreak;1747}1748 1749//===- MIFlagsInstructionPredicateMatcher ---------------------------------===//1750 1751bool MIFlagsInstructionPredicateMatcher::isIdentical(1752    const PredicateMatcher &B) const {1753  if (!InstructionPredicateMatcher::isIdentical(B))1754    return false;1755  const auto &Other =1756      static_cast<const MIFlagsInstructionPredicateMatcher &>(B);1757  return Flags == Other.Flags && CheckNot == Other.CheckNot;1758}1759 1760void MIFlagsInstructionPredicateMatcher::emitPredicateOpcodes(1761    MatchTable &Table, RuleMatcher &Rule) const {1762  Table << MatchTable::Opcode(CheckNot ? "GIM_MIFlagsNot" : "GIM_MIFlags")1763        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)1764        << MatchTable::NamedValue(4, join(Flags, " | "))1765        << MatchTable::LineBreak;1766}1767 1768//===- InstructionMatcher -------------------------------------------------===//1769 1770OperandMatcher &1771InstructionMatcher::addOperand(unsigned OpIdx, const std::string &SymbolicName,1772                               unsigned AllocatedTemporariesBaseID,1773                               bool IsVariadic) {1774  assert((Operands.empty() || !Operands.back()->isVariadic()) &&1775         "Cannot add more operands after a variadic operand");1776  Operands.emplace_back(new OperandMatcher(1777      *this, OpIdx, SymbolicName, AllocatedTemporariesBaseID, IsVariadic));1778  if (!SymbolicName.empty())1779    Rule.defineOperand(SymbolicName, *Operands.back());1780  return *Operands.back();1781}1782 1783OperandMatcher &InstructionMatcher::getOperand(unsigned OpIdx) {1784  auto I = llvm::find_if(Operands,1785                         [&OpIdx](const std::unique_ptr<OperandMatcher> &X) {1786                           return X->getOpIdx() == OpIdx;1787                         });1788  if (I != Operands.end())1789    return **I;1790  llvm_unreachable("Failed to lookup operand");1791}1792 1793OperandMatcher &InstructionMatcher::addPhysRegInput(const Record *Reg,1794                                                    unsigned OpIdx,1795                                                    unsigned TempOpIdx) {1796  assert(SymbolicName.empty());1797  OperandMatcher *OM = new OperandMatcher(*this, OpIdx, "", TempOpIdx);1798  Operands.emplace_back(OM);1799  Rule.definePhysRegOperand(Reg, *OM);1800  return *OM;1801}1802 1803bool InstructionMatcher::recordsOperand() const {1804  return matchersRecordOperand(Predicates) || matchersRecordOperand(operands());1805}1806 1807void InstructionMatcher::emitPredicateOpcodes(MatchTable &Table,1808                                              RuleMatcher &Rule) {1809  if (canAddNumOperandsCheck()) {1810    InstructionNumOperandsMatcher(InsnVarID, getNumOperandMatchers())1811        .emitPredicateOpcodes(Table, Rule);1812  }1813 1814  // First emit all instruction level predicates need to be verified before we1815  // can verify operands.1816  emitFilteredPredicateListOpcodes(1817      [](const PredicateMatcher &P) { return !P.dependsOnOperands(); }, Table,1818      Rule);1819 1820  // Emit all operand constraints.1821  for (const auto &Operand : Operands)1822    Operand->emitPredicateOpcodes(Table, Rule);1823 1824  // All of the tablegen defined predicates should now be matched. Now emit1825  // any custom predicates that rely on all generated checks.1826  emitFilteredPredicateListOpcodes(1827      [](const PredicateMatcher &P) { return P.dependsOnOperands(); }, Table,1828      Rule);1829}1830 1831bool InstructionMatcher::isHigherPriorityThan(InstructionMatcher &B) {1832  // Instruction matchers involving more operands have higher priority.1833  if (Operands.size() > B.Operands.size())1834    return true;1835  if (Operands.size() < B.Operands.size())1836    return false;1837 1838  for (auto &&P : zip(predicates(), B.predicates())) {1839    auto L = static_cast<InstructionPredicateMatcher *>(std::get<0>(P).get());1840    auto R = static_cast<InstructionPredicateMatcher *>(std::get<1>(P).get());1841    if (L->isHigherPriorityThan(*R))1842      return true;1843    if (R->isHigherPriorityThan(*L))1844      return false;1845  }1846 1847  for (auto Operand : zip(Operands, B.Operands)) {1848    if (std::get<0>(Operand)->isHigherPriorityThan(*std::get<1>(Operand)))1849      return true;1850    if (std::get<1>(Operand)->isHigherPriorityThan(*std::get<0>(Operand)))1851      return false;1852  }1853 1854  return false;1855}1856 1857unsigned InstructionMatcher::countRendererFns() {1858  return std::accumulate(1859             predicates().begin(), predicates().end(), 0,1860             [](unsigned A,1861                const std::unique_ptr<PredicateMatcher> &Predicate) {1862               return A + Predicate->countRendererFns();1863             }) +1864         std::accumulate(1865             Operands.begin(), Operands.end(), 0,1866             [](unsigned A, const std::unique_ptr<OperandMatcher> &Operand) {1867               return A + Operand->countRendererFns();1868             });1869}1870 1871void InstructionMatcher::optimize() {1872  SmallVector<std::unique_ptr<PredicateMatcher>, 8> Stash;1873  const auto &OpcMatcher = getOpcodeMatcher();1874 1875  Stash.push_back(predicates_pop_front());1876  if (Stash.back().get() == &OpcMatcher) {1877    // FIXME: Is this even needed still? Why the isVariadicNumOperands check?1878    if (canAddNumOperandsCheck() && OpcMatcher.isVariadicNumOperands() &&1879        getNumOperandMatchers() != 0) {1880      Stash.emplace_back(new InstructionNumOperandsMatcher(1881          InsnVarID, getNumOperandMatchers()));1882    }1883    AllowNumOpsCheck = false;1884 1885    for (auto &OM : Operands)1886      for (auto &OP : OM->predicates())1887        if (isa<IntrinsicIDOperandMatcher>(OP)) {1888          Stash.push_back(std::move(OP));1889          OM->eraseNullPredicates();1890          break;1891        }1892  }1893 1894  if (InsnVarID > 0) {1895    assert(!Operands.empty() && "Nested instruction is expected to def a vreg");1896    for (auto &OP : Operands[0]->predicates())1897      OP.reset();1898    Operands[0]->eraseNullPredicates();1899  }1900  for (auto &OM : Operands) {1901    for (auto &OP : OM->predicates())1902      if (isa<LLTOperandMatcher>(OP))1903        Stash.push_back(std::move(OP));1904    OM->eraseNullPredicates();1905  }1906  while (!Stash.empty())1907    prependPredicate(Stash.pop_back_val());1908}1909 1910//===- InstructionOperandMatcher ------------------------------------------===//1911 1912void InstructionOperandMatcher::emitCaptureOpcodes(MatchTable &Table,1913                                                   RuleMatcher &Rule) const {1914  const unsigned NewInsnVarID = InsnMatcher->getInsnVarID();1915  const bool IgnoreCopies = Flags & GISF_IgnoreCopies;1916  Table << MatchTable::Opcode(IgnoreCopies ? "GIM_RecordInsnIgnoreCopies"1917                                           : "GIM_RecordInsn")1918        << MatchTable::Comment("DefineMI")1919        << MatchTable::ULEB128Value(NewInsnVarID) << MatchTable::Comment("MI")1920        << MatchTable::ULEB128Value(getInsnVarID())1921        << MatchTable::Comment("OpIdx") << MatchTable::ULEB128Value(getOpIdx())1922        << MatchTable::Comment("MIs[" + llvm::to_string(NewInsnVarID) + "]")1923        << MatchTable::LineBreak;1924}1925 1926bool InstructionOperandMatcher::isHigherPriorityThan(1927    const OperandPredicateMatcher &B) const {1928  if (OperandPredicateMatcher::isHigherPriorityThan(B))1929    return true;1930  if (B.OperandPredicateMatcher::isHigherPriorityThan(*this))1931    return false;1932 1933  if (const InstructionOperandMatcher *BP =1934          dyn_cast<InstructionOperandMatcher>(&B))1935    if (InsnMatcher->isHigherPriorityThan(*BP->InsnMatcher))1936      return true;1937  return false;1938}1939 1940//===- OperandRenderer ----------------------------------------------------===//1941 1942OperandRenderer::~OperandRenderer() = default;1943 1944//===- CopyRenderer -------------------------------------------------------===//1945 1946void CopyRenderer::emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule,1947                                     unsigned NewInsnID, unsigned OldInsnID,1948                                     unsigned OpIdx, StringRef Name,1949                                     bool ForVariadic) {1950  if (!ForVariadic && NewInsnID == 0 && OldInsnID == 0) {1951    Table << MatchTable::Opcode("GIR_RootToRootCopy");1952  } else {1953    Table << MatchTable::Opcode(ForVariadic ? "GIR_CopyRemaining" : "GIR_Copy")1954          << MatchTable::Comment("NewInsnID")1955          << MatchTable::ULEB128Value(NewInsnID)1956          << MatchTable::Comment("OldInsnID")1957          << MatchTable::ULEB128Value(OldInsnID);1958  }1959 1960  Table << MatchTable::Comment("OpIdx") << MatchTable::ULEB128Value(OpIdx)1961        << MatchTable::Comment(Name) << MatchTable::LineBreak;1962}1963 1964void CopyRenderer::emitRenderOpcodes(MatchTable &Table,1965                                     RuleMatcher &Rule) const {1966  const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);1967  unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());1968 1969  emitRenderOpcodes(Table, Rule, NewInsnID, OldInsnVarID, Operand.getOpIdx(),1970                    SymbolicName, Operand.isVariadic());1971}1972 1973//===- CopyPhysRegRenderer ------------------------------------------------===//1974 1975void CopyPhysRegRenderer::emitRenderOpcodes(MatchTable &Table,1976                                            RuleMatcher &Rule) const {1977  const OperandMatcher &Operand = Rule.getPhysRegOperandMatcher(PhysReg);1978  unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());1979  CopyRenderer::emitRenderOpcodes(Table, Rule, NewInsnID, OldInsnVarID,1980                                  Operand.getOpIdx(), PhysReg->getName());1981}1982 1983//===- CopyOrAddZeroRegRenderer -------------------------------------------===//1984 1985void CopyOrAddZeroRegRenderer::emitRenderOpcodes(MatchTable &Table,1986                                                 RuleMatcher &Rule) const {1987  const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);1988  unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());1989  Table << MatchTable::Opcode("GIR_CopyOrAddZeroReg")1990        << MatchTable::Comment("NewInsnID")1991        << MatchTable::ULEB128Value(NewInsnID)1992        << MatchTable::Comment("OldInsnID")1993        << MatchTable::ULEB128Value(OldInsnVarID)1994        << MatchTable::Comment("OpIdx")1995        << MatchTable::ULEB128Value(Operand.getOpIdx())1996        << MatchTable::NamedValue(1997               2,1998               (ZeroRegisterDef->getValue("Namespace")1999                    ? ZeroRegisterDef->getValueAsString("Namespace")2000                    : ""),2001               ZeroRegisterDef->getName())2002        << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;2003}2004 2005//===- CopyConstantAsImmRenderer ------------------------------------------===//2006 2007void CopyConstantAsImmRenderer::emitRenderOpcodes(MatchTable &Table,2008                                                  RuleMatcher &Rule) const {2009  InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);2010  unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);2011  Table << MatchTable::Opcode(Signed ? "GIR_CopyConstantAsSImm"2012                                     : "GIR_CopyConstantAsUImm")2013        << MatchTable::Comment("NewInsnID")2014        << MatchTable::ULEB128Value(NewInsnID)2015        << MatchTable::Comment("OldInsnID")2016        << MatchTable::ULEB128Value(OldInsnVarID)2017        << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;2018}2019 2020//===- CopyFConstantAsFPImmRenderer ---------------------------------------===//2021 2022void CopyFConstantAsFPImmRenderer::emitRenderOpcodes(MatchTable &Table,2023                                                     RuleMatcher &Rule) const {2024  InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);2025  unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);2026  Table << MatchTable::Opcode("GIR_CopyFConstantAsFPImm")2027        << MatchTable::Comment("NewInsnID")2028        << MatchTable::ULEB128Value(NewInsnID)2029        << MatchTable::Comment("OldInsnID")2030        << MatchTable::ULEB128Value(OldInsnVarID)2031        << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;2032}2033 2034//===- CopySubRegRenderer -------------------------------------------------===//2035 2036void CopySubRegRenderer::emitRenderOpcodes(MatchTable &Table,2037                                           RuleMatcher &Rule) const {2038  const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);2039  unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());2040  Table << MatchTable::Opcode("GIR_CopySubReg")2041        << MatchTable::Comment("NewInsnID")2042        << MatchTable::ULEB128Value(NewInsnID)2043        << MatchTable::Comment("OldInsnID")2044        << MatchTable::ULEB128Value(OldInsnVarID)2045        << MatchTable::Comment("OpIdx")2046        << MatchTable::ULEB128Value(Operand.getOpIdx())2047        << MatchTable::Comment("SubRegIdx")2048        << MatchTable::IntValue(2, SubReg->EnumValue)2049        << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;2050}2051 2052//===- AddRegisterRenderer ------------------------------------------------===//2053 2054void AddRegisterRenderer::emitRenderOpcodes(MatchTable &Table,2055                                            RuleMatcher &Rule) const {2056  Table << MatchTable::Opcode("GIR_AddRegister")2057        << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID);2058  if (RegisterDef->getName() != "zero_reg") {2059    Table << MatchTable::NamedValue(2060        2,2061        (RegisterDef->getValue("Namespace")2062             ? RegisterDef->getValueAsString("Namespace")2063             : ""),2064        RegisterDef->getName());2065  } else {2066    Table << MatchTable::NamedValue(2, Target.getRegNamespace(), "NoRegister");2067  }2068  Table << MatchTable::Comment("AddRegisterRegFlags");2069 2070  // TODO: This is encoded as a 64-bit element, but only 16 or 32-bits are2071  // really needed for a physical register reference. We can pack the2072  // register and flags in a single field.2073  if (IsDef) {2074    Table << MatchTable::NamedValue(2075        2, IsDead ? "RegState::Define | RegState::Dead" : "RegState::Define");2076  } else {2077    assert(!IsDead && "A use cannot be dead");2078    Table << MatchTable::IntValue(2, 0);2079  }2080  Table << MatchTable::LineBreak;2081}2082 2083//===- TempRegRenderer ----------------------------------------------------===//2084 2085void TempRegRenderer::emitRenderOpcodes(MatchTable &Table,2086                                        RuleMatcher &Rule) const {2087  const bool NeedsFlags = (SubRegIdx || IsDef);2088  if (SubRegIdx) {2089    assert(!IsDef);2090    Table << MatchTable::Opcode("GIR_AddTempSubRegister");2091  } else {2092    Table << MatchTable::Opcode(NeedsFlags ? "GIR_AddTempRegister"2093                                           : "GIR_AddSimpleTempRegister");2094  }2095 2096  Table << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)2097        << MatchTable::Comment("TempRegID")2098        << MatchTable::ULEB128Value(TempRegID);2099 2100  if (!NeedsFlags) {2101    Table << MatchTable::LineBreak;2102    return;2103  }2104 2105  Table << MatchTable::Comment("TempRegFlags");2106  if (IsDef) {2107    SmallString<32> RegFlags;2108    RegFlags += "RegState::Define";2109    if (IsDead)2110      RegFlags += "|RegState::Dead";2111    Table << MatchTable::NamedValue(2, RegFlags);2112  } else {2113    Table << MatchTable::IntValue(2, 0);2114  }2115 2116  if (SubRegIdx)2117    Table << MatchTable::NamedValue(2, SubRegIdx->getQualifiedName());2118  Table << MatchTable::LineBreak;2119}2120 2121//===- ImmRenderer --------------------------------------------------------===//2122 2123void ImmRenderer::emitAddImm(MatchTable &Table, RuleMatcher &RM,2124                             unsigned InsnID, int64_t Imm, StringRef ImmName) {2125  const bool IsInt8 = isInt<8>(Imm);2126 2127  Table << MatchTable::Opcode(IsInt8 ? "GIR_AddImm8" : "GIR_AddImm")2128        << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)2129        << MatchTable::Comment(ImmName)2130        << MatchTable::IntValue(IsInt8 ? 1 : 8, Imm) << MatchTable::LineBreak;2131}2132 2133void ImmRenderer::emitRenderOpcodes(MatchTable &Table,2134                                    RuleMatcher &Rule) const {2135  if (CImmLLT) {2136    assert(Table.isCombiner() &&2137           "ConstantInt immediate are only for combiners!");2138    Table << MatchTable::Opcode("GIR_AddCImm") << MatchTable::Comment("InsnID")2139          << MatchTable::ULEB128Value(InsnID) << MatchTable::Comment("Type")2140          << *CImmLLT << MatchTable::Comment("Imm")2141          << MatchTable::IntValue(8, Imm) << MatchTable::LineBreak;2142  } else {2143    emitAddImm(Table, Rule, InsnID, Imm);2144  }2145}2146 2147//===- SubRegIndexRenderer ------------------------------------------------===//2148 2149void SubRegIndexRenderer::emitRenderOpcodes(MatchTable &Table,2150                                            RuleMatcher &Rule) const {2151  ImmRenderer::emitAddImm(Table, Rule, InsnID, SubRegIdx->EnumValue,2152                          "SubRegIndex");2153}2154 2155//===- RenderComplexPatternOperand ----------------------------------------===//2156 2157void RenderComplexPatternOperand::emitRenderOpcodes(MatchTable &Table,2158                                                    RuleMatcher &Rule) const {2159  Table << MatchTable::Opcode(2160               SubOperand ? (SubReg ? "GIR_ComplexSubOperandSubRegRenderer"2161                                    : "GIR_ComplexSubOperandRenderer")2162                          : "GIR_ComplexRenderer")2163        << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)2164        << MatchTable::Comment("RendererID")2165        << MatchTable::IntValue(2, RendererID);2166  if (SubOperand)2167    Table << MatchTable::Comment("SubOperand")2168          << MatchTable::ULEB128Value(*SubOperand);2169  if (SubReg)2170    Table << MatchTable::Comment("SubRegIdx")2171          << MatchTable::IntValue(2, SubReg->EnumValue);2172  Table << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;2173}2174 2175//===- IntrinsicIDRenderer ------------------------------------------------===//2176 2177void IntrinsicIDRenderer::emitRenderOpcodes(MatchTable &Table,2178                                            RuleMatcher &Rule) const {2179  Table << MatchTable::Opcode("GIR_AddIntrinsicID") << MatchTable::Comment("MI")2180        << MatchTable::ULEB128Value(InsnID)2181        << MatchTable::NamedValue(2, "Intrinsic::" + II->EnumName.str())2182        << MatchTable::LineBreak;2183}2184 2185//===- CustomRenderer -----------------------------------------------------===//2186 2187void CustomRenderer::emitRenderOpcodes(MatchTable &Table,2188                                       RuleMatcher &Rule) const {2189  InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);2190  unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);2191  Table << MatchTable::Opcode("GIR_CustomRenderer")2192        << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)2193        << MatchTable::Comment("OldInsnID")2194        << MatchTable::ULEB128Value(OldInsnVarID)2195        << MatchTable::Comment("Renderer")2196        << MatchTable::NamedValue(2197               2, "GICR_" + Renderer.getValueAsString("RendererFn").str())2198        << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;2199}2200 2201//===- CustomOperandRenderer ----------------------------------------------===//2202 2203void CustomOperandRenderer::emitRenderOpcodes(MatchTable &Table,2204                                              RuleMatcher &Rule) const {2205  const OperandMatcher &OpdMatcher = Rule.getOperandMatcher(SymbolicName);2206  Table << MatchTable::Opcode("GIR_CustomOperandRenderer")2207        << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)2208        << MatchTable::Comment("OldInsnID")2209        << MatchTable::ULEB128Value(OpdMatcher.getInsnVarID())2210        << MatchTable::Comment("OpIdx")2211        << MatchTable::ULEB128Value(OpdMatcher.getOpIdx())2212        << MatchTable::Comment("OperandRenderer")2213        << MatchTable::NamedValue(2214               2, "GICR_" + Renderer.getValueAsString("RendererFn").str())2215        << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;2216}2217 2218//===- BuildMIAction ------------------------------------------------------===//2219 2220bool BuildMIAction::canMutate(RuleMatcher &Rule,2221                              const InstructionMatcher *Insn) const {2222  if (!Insn || Insn->hasVariadicMatcher())2223    return false;2224 2225  if (OperandRenderers.size() != Insn->getNumOperandMatchers())2226    return false;2227 2228  for (const auto &Renderer : enumerate(OperandRenderers)) {2229    if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.value())) {2230      const OperandMatcher &OM =2231          Rule.getOperandMatcher(Copy->getSymbolicName());2232      if (Insn != &OM.getInstructionMatcher() ||2233          OM.getOpIdx() != Renderer.index())2234        return false;2235    } else {2236      return false;2237    }2238  }2239 2240  return true;2241}2242 2243void BuildMIAction::chooseInsnToMutate(RuleMatcher &Rule) {2244  for (auto *MutateCandidate : Rule.mutatable_insns()) {2245    if (canMutate(Rule, MutateCandidate)) {2246      // Take the first one we're offered that we're able to mutate.2247      Rule.reserveInsnMatcherForMutation(MutateCandidate);2248      Matched = MutateCandidate;2249      return;2250    }2251  }2252}2253 2254void BuildMIAction::emitActionOpcodes(MatchTable &Table,2255                                      RuleMatcher &Rule) const {2256  const auto AddMIFlags = [&]() {2257    for (const InstructionMatcher *IM : CopiedFlags) {2258      Table << MatchTable::Opcode("GIR_CopyMIFlags")2259            << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)2260            << MatchTable::Comment("OldInsnID")2261            << MatchTable::ULEB128Value(IM->getInsnVarID())2262            << MatchTable::LineBreak;2263    }2264 2265    if (!SetFlags.empty()) {2266      Table << MatchTable::Opcode("GIR_SetMIFlags")2267            << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)2268            << MatchTable::NamedValue(4, join(SetFlags, " | "))2269            << MatchTable::LineBreak;2270    }2271 2272    if (!UnsetFlags.empty()) {2273      Table << MatchTable::Opcode("GIR_UnsetMIFlags")2274            << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)2275            << MatchTable::NamedValue(4, join(UnsetFlags, " | "))2276            << MatchTable::LineBreak;2277    }2278  };2279 2280  if (Matched) {2281    assert(canMutate(Rule, Matched) &&2282           "Arranged to mutate an insn that isn't mutatable");2283 2284    unsigned RecycleInsnID = Rule.getInsnVarID(*Matched);2285    Table << MatchTable::Opcode("GIR_MutateOpcode")2286          << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)2287          << MatchTable::Comment("RecycleInsnID")2288          << MatchTable::ULEB128Value(RecycleInsnID)2289          << MatchTable::Comment("Opcode")2290          << MatchTable::NamedValue(2, I->Namespace, I->getName())2291          << MatchTable::LineBreak;2292 2293    if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) {2294      for (auto *Def : I->ImplicitDefs) {2295        auto Namespace = Def->getValue("Namespace")2296                             ? Def->getValueAsString("Namespace")2297                             : "";2298        const bool IsDead = DeadImplicitDefs.contains(Def);2299        Table << MatchTable::Opcode("GIR_AddImplicitDef")2300              << MatchTable::Comment("InsnID")2301              << MatchTable::ULEB128Value(InsnID)2302              << MatchTable::NamedValue(2, Namespace, Def->getName())2303              << (IsDead ? MatchTable::NamedValue(2, "RegState", "Dead")2304                         : MatchTable::IntValue(2, 0))2305              << MatchTable::LineBreak;2306      }2307      for (auto *Use : I->ImplicitUses) {2308        auto Namespace = Use->getValue("Namespace")2309                             ? Use->getValueAsString("Namespace")2310                             : "";2311        Table << MatchTable::Opcode("GIR_AddImplicitUse")2312              << MatchTable::Comment("InsnID")2313              << MatchTable::ULEB128Value(InsnID)2314              << MatchTable::NamedValue(2, Namespace, Use->getName())2315              << MatchTable::LineBreak;2316      }2317    }2318 2319    AddMIFlags();2320 2321    // Mark the mutated instruction as erased.2322    Rule.tryEraseInsnID(RecycleInsnID);2323    return;2324  }2325 2326  // TODO: Simple permutation looks like it could be almost as common as2327  //       mutation due to commutative operations.2328 2329  if (InsnID == 0) {2330    Table << MatchTable::Opcode("GIR_BuildRootMI");2331  } else {2332    Table << MatchTable::Opcode("GIR_BuildMI") << MatchTable::Comment("InsnID")2333          << MatchTable::ULEB128Value(InsnID);2334  }2335 2336  Table << MatchTable::Comment("Opcode")2337        << MatchTable::NamedValue(2, I->Namespace, I->getName())2338        << MatchTable::LineBreak;2339 2340  for (const auto &Renderer : OperandRenderers)2341    Renderer->emitRenderOpcodes(Table, Rule);2342 2343  for (auto [OpIdx, Def] : enumerate(I->ImplicitDefs)) {2344    auto Namespace =2345        Def->getValue("Namespace") ? Def->getValueAsString("Namespace") : "";2346    if (DeadImplicitDefs.contains(Def)) {2347      Table2348          << MatchTable::Opcode("GIR_SetImplicitDefDead")2349          << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)2350          << MatchTable::Comment(2351                 ("OpIdx for " + Namespace + "::" + Def->getName() + "").str())2352          << MatchTable::ULEB128Value(OpIdx) << MatchTable::LineBreak;2353    }2354  }2355 2356  if (I->mayLoad || I->mayStore) {2357    // Emit the ID's for all the instructions that are matched by this rule.2358    // TODO: Limit this to matched instructions that mayLoad/mayStore or have2359    //       some other means of having a memoperand. Also limit this to2360    //       emitted instructions that expect to have a memoperand too. For2361    //       example, (G_SEXT (G_LOAD x)) that results in separate load and2362    //       sign-extend instructions shouldn't put the memoperand on the2363    //       sign-extend since it has no effect there.2364 2365    std::vector<unsigned> MergeInsnIDs;2366    for (const auto &IDMatcherPair : Rule.defined_insn_vars())2367      MergeInsnIDs.push_back(IDMatcherPair.second);2368    llvm::sort(MergeInsnIDs);2369 2370    Table << MatchTable::Opcode("GIR_MergeMemOperands")2371          << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)2372          << MatchTable::Comment("NumInsns")2373          << MatchTable::IntValue(1, MergeInsnIDs.size())2374          << MatchTable::Comment("MergeInsnID's");2375    for (const auto &MergeInsnID : MergeInsnIDs)2376      Table << MatchTable::ULEB128Value(MergeInsnID);2377    Table << MatchTable::LineBreak;2378  }2379 2380  AddMIFlags();2381}2382 2383//===- BuildConstantAction ------------------------------------------------===//2384 2385void BuildConstantAction::emitActionOpcodes(MatchTable &Table,2386                                            RuleMatcher &Rule) const {2387  Table << MatchTable::Opcode("GIR_BuildConstant")2388        << MatchTable::Comment("TempRegID")2389        << MatchTable::ULEB128Value(TempRegID) << MatchTable::Comment("Val")2390        << MatchTable::IntValue(8, Val) << MatchTable::LineBreak;2391}2392 2393//===- EraseInstAction ----------------------------------------------------===//2394 2395void EraseInstAction::emitActionOpcodes(MatchTable &Table,2396                                        RuleMatcher &Rule) const {2397  // Avoid erasing the same inst twice.2398  if (!Rule.tryEraseInsnID(InsnID))2399    return;2400 2401  Table << MatchTable::Opcode("GIR_EraseFromParent")2402        << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)2403        << MatchTable::LineBreak;2404}2405 2406bool EraseInstAction::emitActionOpcodesAndDone(MatchTable &Table,2407                                               RuleMatcher &Rule) const {2408  if (InsnID != 0) {2409    emitActionOpcodes(Table, Rule);2410    return false;2411  }2412 2413  if (!Rule.tryEraseInsnID(0))2414    return false;2415 2416  Table << MatchTable::Opcode("GIR_EraseRootFromParent_Done", -1)2417        << MatchTable::LineBreak;2418  return true;2419}2420 2421//===- ReplaceRegAction ---------------------------------------------------===//2422 2423void ReplaceRegAction::emitAdditionalPredicates(MatchTable &Table,2424                                                RuleMatcher &Rule) const {2425  if (TempRegID != (unsigned)-1)2426    return;2427 2428  Table << MatchTable::Opcode("GIM_CheckCanReplaceReg")2429        << MatchTable::Comment("OldInsnID")2430        << MatchTable::ULEB128Value(OldInsnID)2431        << MatchTable::Comment("OldOpIdx") << MatchTable::ULEB128Value(OldOpIdx)2432        << MatchTable::Comment("NewInsnId")2433        << MatchTable::ULEB128Value(NewInsnId)2434        << MatchTable::Comment("NewOpIdx") << MatchTable::ULEB128Value(NewOpIdx)2435        << MatchTable::LineBreak;2436}2437 2438void ReplaceRegAction::emitActionOpcodes(MatchTable &Table,2439                                         RuleMatcher &Rule) const {2440  if (TempRegID != (unsigned)-1) {2441    Table << MatchTable::Opcode("GIR_ReplaceRegWithTempReg")2442          << MatchTable::Comment("OldInsnID")2443          << MatchTable::ULEB128Value(OldInsnID)2444          << MatchTable::Comment("OldOpIdx")2445          << MatchTable::ULEB128Value(OldOpIdx)2446          << MatchTable::Comment("TempRegID")2447          << MatchTable::ULEB128Value(TempRegID) << MatchTable::LineBreak;2448  } else {2449    Table << MatchTable::Opcode("GIR_ReplaceReg")2450          << MatchTable::Comment("OldInsnID")2451          << MatchTable::ULEB128Value(OldInsnID)2452          << MatchTable::Comment("OldOpIdx")2453          << MatchTable::ULEB128Value(OldOpIdx)2454          << MatchTable::Comment("NewInsnId")2455          << MatchTable::ULEB128Value(NewInsnId)2456          << MatchTable::Comment("NewOpIdx")2457          << MatchTable::ULEB128Value(NewOpIdx) << MatchTable::LineBreak;2458  }2459}2460 2461//===- ConstrainOperandToRegClassAction -----------------------------------===//2462 2463void ConstrainOperandToRegClassAction::emitActionOpcodes(2464    MatchTable &Table, RuleMatcher &Rule) const {2465  Table << MatchTable::Opcode("GIR_ConstrainOperandRC")2466        << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)2467        << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)2468        << MatchTable::NamedValue(2, RC.getQualifiedIdName())2469        << MatchTable::LineBreak;2470}2471 2472//===- MakeTempRegisterAction ---------------------------------------------===//2473 2474void MakeTempRegisterAction::emitActionOpcodes(MatchTable &Table,2475                                               RuleMatcher &Rule) const {2476  Table << MatchTable::Opcode("GIR_MakeTempReg")2477        << MatchTable::Comment("TempRegID")2478        << MatchTable::ULEB128Value(TempRegID) << MatchTable::Comment("TypeID")2479        << Ty << MatchTable::LineBreak;2480}2481