llvm/utils/TableGen/Common/GlobalISel/MatchTable/Matchers.cpp

//===- Matchers.cpp -------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#include "Matchers.h"
#include "Common/CodeGenInstruction.h"
#include "Common/CodeGenRegisters.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/LEB128.h"
#include "llvm/Support/ScopedPrinter.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/TableGen/Error.h"

#define DEBUG_TYPE "gi-match-table-matchers"

STATISTIC(NumPatternEmitted, "Number of patterns emitted");

using namespace llvm;
using namespace gi;

// FIXME: Use createStringError instead.
static Error failUnsupported(const Twine &Reason) {
  return make_error<StringError>(Reason, inconvertibleErrorCode());
}

/// Get the name of the enum value used to number the predicate function.
static std::string getEnumNameForPredicate(const TreePredicateFn &Predicate) {
  if (Predicate.hasGISelPredicateCode())
    return "GICXXPred_MI_" + Predicate.getFnName();
  if (Predicate.hasGISelLeafPredicateCode())
    return "GICXXPred_MO_" + Predicate.getFnName();
  return "GICXXPred_" + Predicate.getImmTypeIdentifier().str() + "_" +
         Predicate.getFnName();
}

static std::string
getMatchOpcodeForImmPredicate(const TreePredicateFn &Predicate) {
  return "GIM_Check" + Predicate.getImmTypeIdentifier().str() + "ImmPredicate";
}

//===- Helpers ------------------------------------------------------------===//

template <class GroupT>
static std::vector<Matcher *>
optimizeRules(ArrayRef<Matcher *> Rules,
              std::vector<std::unique_ptr<Matcher>> &MatcherStorage) {

  std::vector<Matcher *> Worklist(Rules.begin(), Rules.end());
  std::vector<Matcher *> OptRules;
  std::unique_ptr<GroupT> CurrentGroup = std::make_unique<GroupT>();
  assert(CurrentGroup->empty() && "Newly created group isn't empty!");
  unsigned NumGroups = 0;

  auto ProcessCurrentGroup = [&]() {
    if (CurrentGroup->empty())
      // An empty group is good to be reused:
      return;

    // If the group isn't large enough to provide any benefit, move all the
    // added rules out of it and make sure to re-create the group to properly
    // re-initialize it:
    if (CurrentGroup->size() < 2)
      append_range(OptRules, CurrentGroup->matchers());
    else {
      CurrentGroup->finalize();
      CurrentGroup->optimize();
      OptRules.push_back(CurrentGroup.get());
      MatcherStorage.emplace_back(std::move(CurrentGroup));
      ++NumGroups;
    }
    CurrentGroup = std::make_unique<GroupT>();
  };

  for (Matcher *Rule : Worklist) {
    // Greedily add as many matchers as possible to the current group:
    if (CurrentGroup->addMatcher(*Rule))
      continue;

    ProcessCurrentGroup();
    assert(CurrentGroup->empty() && "A group wasn't properly re-initialized");

    // Try to add the pending matcher to a newly created empty group:
    if (!CurrentGroup->addMatcher(*Rule))
      // If we couldn't add the matcher to an empty group, that group type
      // doesn't support that kind of matchers at all, so just skip it:
      OptRules.push_back(Rule);
  }
  ProcessCurrentGroup();

  assert(OptRules.size() <= Worklist.size() && "Optimization added rules?");
  LLVM_DEBUG(dbgs() << "NumGroups: " << NumGroups << "\n");
  (void)NumGroups;
  assert(CurrentGroup->empty() && "The last group wasn't properly processed");
  return OptRules;
}

std::vector<Matcher *> llvm::gi::optimizeRuleset(
    MutableArrayRef<RuleMatcher> Rules,
    std::vector<std::unique_ptr<Matcher>> &MatcherStorage) {
  SmallVector<Matcher *> InputRules(make_pointer_range(Rules));

  // Now sort the Rules.
  unsigned CurrentOrdering = 0;
  StringMap<unsigned> OpcodeOrder;
  for (RuleMatcher &Rule : Rules) {
    const StringRef Opcode = Rule.getOpcode();
    assert(!Opcode.empty() && "Didn't expect an undefined opcode");
    if (OpcodeOrder.try_emplace(Opcode, CurrentOrdering).second)
      ++CurrentOrdering;
  }

  llvm::stable_sort(
      InputRules, [&OpcodeOrder](const Matcher *A, const Matcher *B) {
        const auto *L = cast<RuleMatcher>(A);
        const auto *R = cast<RuleMatcher>(B);
        return std::tuple(OpcodeOrder[L->getOpcode()],
                          L->roots_front().getNumOperandMatchers()) <
               std::tuple(OpcodeOrder[R->getOpcode()],
                          R->roots_front().getNumOperandMatchers());
      });

  for (Matcher *R : InputRules)
    R->optimize();

  // Then form groups, and switches in that order.
  std::vector<Matcher *> OptRules =
      optimizeRules<GroupMatcher>(InputRules, MatcherStorage);
  OptRules = optimizeRules<SwitchMatcher>(OptRules, MatcherStorage);
  return OptRules;
}

MatchTable llvm::gi::buildMatchTable(ArrayRef<Matcher *> Rules,
                                     bool WithCoverage, bool IsCombiner) {
  MatchTable Table(WithCoverage, IsCombiner);
  for (Matcher *Rule : Rules)
    Rule->emit(Table);

  return Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
}

template <class Range> static bool matchersRecordOperand(Range &&R) {
  return any_of(R, [](const auto &I) { return I->recordsOperand(); });
}

static void emitType(MatchTable &Table, const LLTCodeGenOrTempType &Ty) {
  if (Ty.isLLTCodeGen())
    Table << MatchTable::NamedValue(1, Ty.getLLTCodeGen().getCxxEnumValue());
  else
    Table << MatchTable::IntValue(1, Ty.getTempTypeIdx());
}

//===- Matcher ------------------------------------------------------------===//

void Matcher::optimize() {}

Matcher::~Matcher() = default;

//===- GroupMatcher -------------------------------------------------------===//

bool GroupMatcher::recordsOperand() const {
  return matchersRecordOperand(Conditions) || matchersRecordOperand(Matchers);
}

bool GroupMatcher::candidateConditionMatches(
    const PredicateMatcher &Predicate) const {

  if (empty()) {
    // Sharing predicates for nested instructions is not supported yet as we
    // currently don't hoist the GIM_RecordInsn's properly, therefore we can
    // only work on the original root instruction (InsnVarID == 0):
    if (Predicate.getInsnVarID() != 0)
      return false;
    // ... otherwise an empty group can handle any predicate with no specific
    // requirements:
    return true;
  }

  const Matcher &Representative = **Matchers.begin();
  const auto &RepresentativeCondition = Representative.getFirstCondition();
  // ... if not empty, the group can only accomodate matchers with the exact
  // same first condition:
  return Predicate.isIdentical(RepresentativeCondition);
}

std::unique_ptr<PredicateMatcher> GroupMatcher::popFirstCondition() {
  assert(!Conditions.empty() &&
         "Trying to pop a condition from a condition-less group");
  std::unique_ptr<PredicateMatcher> P = std::move(Conditions.front());
  Conditions.erase(Conditions.begin());
  return P;
}

bool GroupMatcher::addMatcher(Matcher &Candidate) {
  if (!Candidate.hasFirstCondition())
    return false;

  // Only add candidates that have a matching first condition that can be
  // hoisted into the GroupMatcher.
  const PredicateMatcher &Predicate = Candidate.getFirstCondition();
  if (!candidateConditionMatches(Predicate) ||
      !Predicate.canHoistOutsideOf(Candidate))
    return false;

  Matchers.push_back(&Candidate);
  return true;
}

void GroupMatcher::finalize() {
  assert(Conditions.empty() && "Already finalized?");
  if (empty())
    return;

  Matcher &FirstRule = **Matchers.begin();
  for (;;) {
    // All the checks are expected to succeed during the first iteration:
    for (const auto &Rule : Matchers)
      if (!Rule->hasFirstCondition())
        return;
    // Hoist the first condition if it is identical in all matchers in the group
    // and it can be hoisted in every matcher.
    const auto &FirstCondition = FirstRule.getFirstCondition();
    if (!FirstCondition.canHoistOutsideOf(FirstRule))
      return;
    for (unsigned I = 1, E = Matchers.size(); I < E; ++I) {
      const auto &OtherFirstCondition = Matchers[I]->getFirstCondition();
      if (!OtherFirstCondition.isIdentical(FirstCondition) ||
          !OtherFirstCondition.canHoistOutsideOf(*Matchers[I]))
        return;
    }

    Conditions.push_back(FirstRule.popFirstCondition());
    for (unsigned I = 1, E = Matchers.size(); I < E; ++I)
      Matchers[I]->popFirstCondition();
  }
}

void GroupMatcher::emit(MatchTable &Table) {
  unsigned LabelID = ~0U;
  if (!Conditions.empty()) {
    LabelID = Table.allocateLabelID();
    Table << MatchTable::Opcode("GIM_Try", +1)
          << MatchTable::Comment("On fail goto")
          << MatchTable::JumpTarget(LabelID) << MatchTable::LineBreak;
  }
  for (auto &Condition : Conditions)
    Condition->emitPredicateOpcodes(Table);

  for (const auto &M : Matchers)
    M->emit(Table);

  // Exit the group
  if (!Conditions.empty())
    Table << MatchTable::Opcode("GIM_Reject", -1) << MatchTable::LineBreak
          << MatchTable::Label(LabelID);
}

void GroupMatcher::optimize() {
  // Make sure we only sort by a specific predicate within a range of rules that
  // all have that predicate checked against a specific value (not a wildcard):
  // TODO: Is this even relevant ? Check diffs w/ just using a simple sort
  // instead of this.
  auto F = Matchers.begin();
  auto T = F;
  auto E = Matchers.end();
  while (T != E) {
    while (T != E) {
      if (!(*T)->getFirstConditionAsRootType().get().isValid())
        break;
      ++T;
    }
    std::stable_sort(F, T, [](Matcher *A, Matcher *B) {
      return A->getFirstConditionAsRootType() <
             B->getFirstConditionAsRootType();
    });
    if (T != E)
      F = ++T;
  }
  Matchers = optimizeRules<GroupMatcher>(Matchers, MatcherStorage);
  Matchers = optimizeRules<SwitchMatcher>(Matchers, MatcherStorage);
}

LLTCodeGen GroupMatcher::getFirstConditionAsRootType() const {
  if (!hasFirstCondition())
    return {};

  const PredicateMatcher &PM = *Conditions.front();
  if (const auto *TM = dyn_cast<LLTOperandMatcher>(&PM)) {
    if (TM->getInsnVarID() == 0 && TM->getOpIdx() == 0)
      return TM->getTy();
  }

  return {};
}

//===- SwitchMatcher ------------------------------------------------------===//

SwitchMatcher::SwitchMatcher() : Matcher(MK_Switch) {}
SwitchMatcher::~SwitchMatcher() = default;

bool SwitchMatcher::recordsOperand() const {
  assert(!isa_and_present<RecordNamedOperandMatcher>(Condition.get()) &&
         "Switch conditions should not record named operands");
  return matchersRecordOperand(Matchers);
}

bool SwitchMatcher::isSupportedPredicateType(const PredicateMatcher &P) {
  return isa<InstructionOpcodeMatcher>(P) || isa<LLTOperandShapeMatcher>(P) ||
         isa<LLTOperandMatcher>(P);
}

bool SwitchMatcher::candidateConditionMatches(
    const PredicateMatcher &Predicate) const {

  if (empty()) {
    // Sharing predicates for nested instructions is not supported yet as we
    // currently don't hoist the GIM_RecordInsn's properly, therefore we can
    // only work on the original root instruction (InsnVarID == 0):
    if (Predicate.getInsnVarID() != 0)
      return false;
    // ... while an attempt to add even a root matcher to an empty SwitchMatcher
    // could fail as not all the types of conditions are supported:
    if (!isSupportedPredicateType(Predicate))
      return false;
    // ... or the condition might not have a proper implementation of
    // getValue() / isIdenticalDownToValue() yet:
    if (!Predicate.hasValue())
      return false;
    // ... otherwise an empty Switch can accomodate the condition with no
    // further requirements:
    return true;
  }

  const Matcher &CaseRepresentative = **Matchers.begin();
  const auto &RepresentativeCondition = CaseRepresentative.getFirstCondition();
  // Switch-cases must share the same kind of condition and path to the value it
  // checks:
  if (!Predicate.isIdenticalDownToValue(RepresentativeCondition))
    return false;

  return true;
}

bool SwitchMatcher::addMatcher(Matcher &Candidate) {
  if (!Candidate.hasFirstCondition())
    return false;

  const PredicateMatcher &Predicate = Candidate.getFirstCondition();
  if (!candidateConditionMatches(Predicate))
    return false;
  const auto Value = Predicate.getValue();
  auto It = Buckets.find(Value.RawValue);
  if (It == Buckets.end())
    It = Buckets.emplace(Value.RawValue, Bucket(Value)).first;
#ifndef NDEBUG
  else
    assert(It->second.Value.Record.EmitStr == Value.Record.EmitStr &&
           "Mismatched records for identical switch value");
#endif
  It->second.Matchers.push_back(&Candidate);
  Matchers.push_back(&Candidate);
  return true;
}

void SwitchMatcher::finalize() {
  assert(Condition == nullptr && "Already finalized");
#ifndef NDEBUG
  unsigned NumBucketedMatchers = 0;
  for (const auto &Entry : Buckets)
    NumBucketedMatchers += Entry.second.Matchers.size();
  assert(NumBucketedMatchers == Matchers.size() && "Broken SwitchMatcher");
#endif
  if (empty())
    return;

  Condition = Matchers.front()->popFirstCondition();
  for (unsigned I = 1, E = Matchers.size(); I < E; ++I)
    Matchers[I]->popFirstCondition();

  // After removing the switch condition, try to hoist any shared predicates
  // within each switch bucket.
  for (auto &Entry : Buckets) {
    auto &BucketMatchers = Entry.second.Matchers;
    BucketMatchers =
        optimizeRules<GroupMatcher>(BucketMatchers, MatcherStorage);
  }

  Matchers.clear();
  for (auto &Entry : Buckets)
    append_range(Matchers, Entry.second.Matchers);
}

void SwitchMatcher::emitPredicateSpecificOpcodes(const PredicateMatcher &P,
                                                 MatchTable &Table) {
  assert(isSupportedPredicateType(P) && "Predicate type is not supported");

  if (const auto *Condition = dyn_cast<InstructionOpcodeMatcher>(&P)) {
    Table << MatchTable::Opcode("GIM_SwitchOpcode") << MatchTable::Comment("MI")
          << MatchTable::ULEB128Value(Condition->getInsnVarID());
    return;
  }
  if (const auto *Condition = dyn_cast<LLTOperandShapeMatcher>(&P)) {
    Table << MatchTable::Opcode("GIM_SwitchTypeShape")
          << MatchTable::Comment("MI")
          << MatchTable::ULEB128Value(Condition->getInsnVarID())
          << MatchTable::Comment("Op")
          << MatchTable::ULEB128Value(Condition->getOpIdx());
    return;
  }
  if (const auto *Condition = dyn_cast<LLTOperandMatcher>(&P)) {
    Table << MatchTable::Opcode("GIM_SwitchType") << MatchTable::Comment("MI")
          << MatchTable::ULEB128Value(Condition->getInsnVarID())
          << MatchTable::Comment("Op")
          << MatchTable::ULEB128Value(Condition->getOpIdx());
    return;
  }

  llvm_unreachable("emitPredicateSpecificOpcodes is broken: can not handle a "
                   "predicate type that is claimed to be supported");
}

void SwitchMatcher::emit(MatchTable &Table) {
#ifndef NDEBUG
  unsigned NumBucketedMatchers = 0;
  for (const auto &Entry : Buckets)
    NumBucketedMatchers += Entry.second.Matchers.size();
  assert(NumBucketedMatchers == Matchers.size() && "Broken SwitchMatcher");
#endif
  if (empty())
    return;
  assert(Condition != nullptr &&
         "Broken SwitchMatcher, hasn't been finalized?");

  std::vector<unsigned> LabelIDs(Buckets.size());
  std::generate(LabelIDs.begin(), LabelIDs.end(),
                [&Table]() { return Table.allocateLabelID(); });
  const unsigned Default = Table.allocateLabelID();

  const int64_t LowerBound = Buckets.begin()->second.Value.RawValue;
  const int64_t UpperBound = Buckets.rbegin()->second.Value.RawValue + 1;

  emitPredicateSpecificOpcodes(*Condition, Table);

  Table << MatchTable::Comment("[") << MatchTable::IntValue(2, LowerBound)
        << MatchTable::IntValue(2, UpperBound) << MatchTable::Comment(")")
        << MatchTable::Comment("default:") << MatchTable::JumpTarget(Default);

  int64_t J = LowerBound;
  unsigned CaseIdx = 0;
  for (auto &Entry : Buckets) {
    auto &V = Entry.second.Value;
    while (J++ < V.RawValue)
      Table << MatchTable::IntValue(4, 0);
    V.Record.turnIntoComment();
    Table << MatchTable::LineBreak << V.Record
          << MatchTable::JumpTarget(LabelIDs[CaseIdx]);
    ++CaseIdx;
  }
  Table << MatchTable::LineBreak;

  CaseIdx = 0;
  for (auto &Entry : Buckets) {
    Table << MatchTable::Label(LabelIDs[CaseIdx]);
    for (Matcher *M : Entry.second.Matchers)
      M->emit(Table);
    Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
    ++CaseIdx;
  }
  Table << MatchTable::Label(Default);
}

//===- RuleMatcher --------------------------------------------------------===//

RuleMatcher::RuleMatcher(ArrayRef<SMLoc> SrcLoc, bool UsesRecordOperand)
    : Matcher(Matcher::MK_Rule), UsesRecordOperand(UsesRecordOperand),
      SrcLoc(SrcLoc), RuleID(NextRuleID++) {}

uint64_t RuleMatcher::NextRuleID = 0;

StringRef RuleMatcher::getOpcode() const { return Roots.front()->getOpcode(); }

bool RuleMatcher::recordsOperand() const {
  return !usesRecordOperand() || matchersRecordOperand(InsnMatchers);
}

LLTCodeGen RuleMatcher::getFirstConditionAsRootType() const {
  InstructionMatcher &InsnMatcher = *Roots.front();
  if (!InsnMatcher.predicates_empty()) {
    if (const auto *TM =
            dyn_cast<LLTOperandMatcher>(&**InsnMatcher.predicates_begin())) {
      if (TM->getInsnVarID() == 0 && TM->getOpIdx() == 0)
        return TM->getTy();
    }
  }
  return {};
}

void RuleMatcher::optimize() {
  for (const auto &InsnMatcher : InsnMatchers) {
    for (auto &OM : InsnMatcher->operands()) {
      // Complex Patterns are usually expensive and they relatively rarely fail
      // on their own: more often we end up throwing away all the work done by a
      // matching part of a complex pattern because some other part of the
      // enclosing pattern didn't match. All of this makes it beneficial to
      // delay complex patterns until the very end of the rule matching,
      // especially for targets having lots of complex patterns.
      for (auto &OP : OM->predicates())
        if (isa<ComplexPatternOperandMatcher>(OP))
          EpilogueMatchers.emplace_back(std::move(OP));
      OM->eraseNullPredicates();
    }
    InsnMatcher->optimize();
  }
  llvm::sort(EpilogueMatchers, [](const std::unique_ptr<PredicateMatcher> &L,
                                  const std::unique_ptr<PredicateMatcher> &R) {
    return std::tuple(L->getKind(), L->getInsnVarID(), L->getOpIdx()) <
           std::tuple(R->getKind(), R->getInsnVarID(), R->getOpIdx());
  });

  // Deduplicate EraseInst actions, and if an EraseInst erases the root, place
  // it at the end to favor generation of GIR_EraseRootFromParent_Done
  DenseSet<unsigned> AlreadySeenEraseInsts;
  auto EraseRootIt = Actions.end();
  auto It = Actions.begin();
  while (It != Actions.end()) {
    if (const auto *EI = dyn_cast<EraseInstAction>(It->get())) {
      unsigned InstID = EI->getInsnID();
      if (!AlreadySeenEraseInsts.insert(InstID).second) {
        It = Actions.erase(It);
        continue;
      }

      if (InstID == 0)
        EraseRootIt = It;
    }

    ++It;
  }

  if (EraseRootIt != Actions.end())
    Actions.splice(Actions.end(), Actions, EraseRootIt);
}

bool RuleMatcher::hasFirstCondition() const {
  if (roots_empty())
    return false;
  InstructionMatcher &Matcher = roots_front();
  if (!Matcher.predicates_empty())
    return true;
  for (auto &OM : Matcher.operands())
    for (auto &OP : OM->predicates())
      if (!isa<InstructionOperandMatcher>(OP))
        return true;
  return false;
}

const PredicateMatcher &RuleMatcher::getFirstCondition() const {
  assert(!roots_empty() &&
         "Trying to get a condition from an empty RuleMatcher");

  InstructionMatcher &Matcher = roots_front();
  if (!Matcher.predicates_empty())
    return **Matcher.predicates_begin();
  // If there is no more predicate on the instruction itself, look at its
  // operands.
  for (auto &OM : Matcher.operands())
    for (auto &OP : OM->predicates())
      if (!isa<InstructionOperandMatcher>(OP))
        return *OP;

  llvm_unreachable("Trying to get a condition from an InstructionMatcher with "
                   "no conditions");
}

std::unique_ptr<PredicateMatcher> RuleMatcher::popFirstCondition() {
  assert(!roots_empty() &&
         "Trying to pop a condition from an empty RuleMatcher");

  InstructionMatcher &Matcher = roots_front();
  if (!Matcher.predicates_empty())
    return Matcher.predicates_pop_front();
  // If there is no more predicate on the instruction itself, look at its
  // operands.
  for (auto &OM : Matcher.operands())
    for (auto &OP : OM->predicates())
      if (!isa<InstructionOperandMatcher>(OP)) {
        std::unique_ptr<PredicateMatcher> Result = std::move(OP);
        OM->eraseNullPredicates();
        return Result;
      }

  llvm_unreachable("Trying to pop a condition from an InstructionMatcher with "
                   "no conditions");
}

GISelFlags RuleMatcher::updateGISelFlag(GISelFlags CurFlags, const Record *R,
                                        StringRef FlagName,
                                        GISelFlags FlagBit) {
  // If the value of a flag is unset, ignore it.
  // If it's set, it always takes precedence over the existing value so
  // clear/set the corresponding bit.
  bool Unset = false;
  bool Value = R->getValueAsBitOrUnset("GIIgnoreCopies", Unset);
  if (!Unset)
    return Value ? (CurFlags | FlagBit) : (CurFlags & ~FlagBit);
  return CurFlags;
}

SaveAndRestore<GISelFlags> RuleMatcher::setGISelFlags(const Record *R) {
  if (!R || !R->isSubClassOf("GISelFlags"))
    return {Flags, Flags};

  assert((R->isSubClassOf("PatFrags") || R->isSubClassOf("Pattern")) &&
         "GISelFlags is only expected on Pattern/PatFrags!");

  GISelFlags NewFlags =
      updateGISelFlag(Flags, R, "GIIgnoreCopies", GISF_IgnoreCopies);
  return {Flags, NewFlags};
}

Error RuleMatcher::defineComplexSubOperand(StringRef SymbolicName,
                                           const Record *ComplexPattern,
                                           unsigned RendererID,
                                           unsigned SubOperandID,
                                           StringRef ParentSymbolicName) {
  std::string ParentName(ParentSymbolicName);
  auto [It, Inserted] = ComplexSubOperands.try_emplace(
      SymbolicName, ComplexPattern, RendererID, SubOperandID);
  if (!Inserted) {
    const std::string &RecordedParentName =
        ComplexSubOperandsParentName[SymbolicName];
    if (RecordedParentName != ParentName)
      return failUnsupported("Error: Complex suboperand " + SymbolicName +
                             " referenced by different operands: " +
                             RecordedParentName + " and " + ParentName + ".");
    // Complex suboperand referenced more than once from same the operand is
    // used to generate 'same operand check'. Emitting of
    // GIR_ComplexSubOperandRenderer for them is already handled.
    return Error::success();
  }

  ComplexSubOperandsParentName[SymbolicName] = std::move(ParentName);

  return Error::success();
}

InstructionMatcher &
RuleMatcher::allocateInstructionMatcher(StringRef SymbolicName,
                                        bool AllowNumOpsCheck) {
  return *InsnMatchers.emplace_back(std::make_unique<InstructionMatcher>(
      *this, InsnMatchers.size(), SymbolicName, AllowNumOpsCheck));
}

InstructionMatcher &RuleMatcher::addInstructionMatcher(StringRef SymbolicName) {
  auto &Res = allocateInstructionMatcher(SymbolicName);
  Roots.push_back(&Res);
  MutatableInsns.insert(&Res);
  return Res;
}

void RuleMatcher::addRequiredSimplePredicate(StringRef PredName) {
  RequiredSimplePredicates.push_back(PredName.str());
}

const std::vector<std::string> &RuleMatcher::getRequiredSimplePredicates() {
  return RequiredSimplePredicates;
}

void RuleMatcher::defineOperand(StringRef SymbolicName, OperandMatcher &OM) {
  if (DefinedOperands.try_emplace(SymbolicName, &OM).second)
    return;

  // If the operand is already defined, then we must ensure both references in
  // the matcher have the exact same node.
  RuleMatcher &RM = OM.getInstructionMatcher().getRuleMatcher();
  auto &OtherOM = getOperandMatcher(OM.getSymbolicName());
  OM.addPredicate<SameOperandMatcher>(OtherOM.getInsnVarID(),
                                      OtherOM.getOpIdx(), RM.getGISelFlags());
}

void RuleMatcher::definePhysRegOperand(const Record *Reg, OperandMatcher &OM) {
  PhysRegOperands.try_emplace(Reg, &OM);
}

InstructionMatcher &
RuleMatcher::getInstructionMatcher(StringRef SymbolicName) const {
  for (const auto &InsnMatcher : InsnMatchers) {
    if (InsnMatcher->getSymbolicName() == SymbolicName)
      return *InsnMatcher;
  }
  llvm_unreachable(
      ("Failed to lookup instruction " + SymbolicName).str().c_str());
}

const OperandMatcher &
RuleMatcher::getPhysRegOperandMatcher(const Record *Reg) const {
  const auto &I = PhysRegOperands.find(Reg);

  if (I == PhysRegOperands.end()) {
    PrintFatalError(SrcLoc, "Register " + Reg->getName() +
                                " was not declared in matcher");
  }

  return *I->second;
}

OperandMatcher &RuleMatcher::getOperandMatcher(StringRef Name) {
  const auto &I = DefinedOperands.find(Name);

  if (I == DefinedOperands.end())
    PrintFatalError(SrcLoc, "Operand " + Name + " was not declared in matcher");

  return *I->second;
}

const OperandMatcher &RuleMatcher::getOperandMatcher(StringRef Name) const {
  const auto &I = DefinedOperands.find(Name);

  if (I == DefinedOperands.end())
    PrintFatalError(SrcLoc, "Operand " + Name + " was not declared in matcher");

  return *I->second;
}

void RuleMatcher::emit(MatchTable &Table) {
  if (Roots.empty())
    llvm_unreachable("Unexpected empty matcher!");

  // The representation supports rules that require multiple roots such as:
  //    %ptr(p0) = ...
  //    %elt0(s32) = G_LOAD %ptr
  //    %1(p0) = G_ADD %ptr, 4
  //    %elt1(s32) = G_LOAD p0 %1
  // which could be usefully folded into:
  //    %ptr(p0) = ...
  //    %elt0(s32), %elt1(s32) = TGT_LOAD_PAIR %ptr
  // on some targets but we don't need to make use of that yet.
  assert(Roots.size() == 1 && "Cannot handle multi-root matchers yet");

  unsigned LabelID = Table.allocateLabelID();

  if (!RequiredFeatures.empty() || HwModeIdx >= 0) {
    Table << MatchTable::Opcode("GIM_Try_CheckFeatures", +1)
          << MatchTable::Comment("On fail goto")
          << MatchTable::JumpTarget(LabelID)
          << MatchTable::NamedValue(
                 2, getNameForFeatureBitset(RequiredFeatures, HwModeIdx));
  } else {
    Table << MatchTable::Opcode("GIM_Try", +1)
          << MatchTable::Comment("On fail goto")
          << MatchTable::JumpTarget(LabelID);
  }
  Table << MatchTable::Comment(("Rule ID " + Twine(RuleID) + " //").str())
        << MatchTable::LineBreak;

  if (!RequiredSimplePredicates.empty()) {
    for (const auto &Pred : RequiredSimplePredicates) {
      Table << MatchTable::Opcode("GIM_CheckSimplePredicate")
            << MatchTable::NamedValue(2, Pred) << MatchTable::LineBreak;
    }
  }

  Roots.front()->emitPredicateOpcodes(Table);

  // Check if it's safe to replace registers.
  for (const auto &MA : Actions)
    MA->emitAdditionalPredicates(Table);

  // We must also check if it's safe to fold the matched instructions.
  if (InsnMatchers.size() >= 2) {

    // FIXME: Emit checks to determine it's _actually_ safe to fold and/or
    //        account for unsafe cases.
    //
    //        Example:
    //          MI1--> %0 = ...
    //                 %1 = ... %0
    //          MI0--> %2 = ... %0
    //          It's not safe to erase MI1. We currently handle this by not
    //          erasing %0 (even when it's dead).
    //
    //        Example:
    //          MI1--> %0 = load volatile @a
    //                 %1 = load volatile @a
    //          MI0--> %2 = ... %0
    //          It's not safe to sink %0's def past %1. We currently handle
    //          this by rejecting all loads.
    //
    //        Example:
    //          MI1--> %0 = load @a
    //                 %1 = store @a
    //          MI0--> %2 = ... %0
    //          It's not safe to sink %0's def past %1. We currently handle
    //          this by rejecting all loads.
    //
    //        Example:
    //                   G_CONDBR %cond, @BB1
    //                 BB0:
    //          MI1-->   %0 = load @a
    //                   G_BR @BB1
    //                 BB1:
    //          MI0-->   %2 = ... %0
    //          It's not always safe to sink %0 across control flow. In this
    //          case it may introduce a memory fault. We currentl handle
    //          this by rejecting all loads.

    Table << MatchTable::Opcode("GIM_CheckIsSafeToFold")
          << MatchTable::Comment("NumInsns")
          << MatchTable::IntValue(1, InsnMatchers.size() - 1)
          << MatchTable::LineBreak;
  }

  for (const auto &PM : EpilogueMatchers)
    PM->emitPredicateOpcodes(Table);

  if (!CustomCXXAction.empty()) {
    /// Handle combiners relying on custom C++ code instead of actions.
    assert(Table.isCombiner() && "CustomCXXAction is only for combiners!");
    // We cannot have actions other than debug comments.
    assert(none_of(Actions, [](auto &A) {
      return A->getKind() != MatchAction::AK_DebugComment;
    }));
    for (const auto &MA : Actions)
      MA->emitActionOpcodes(Table);
    Table << MatchTable::Opcode("GIR_DoneWithCustomAction", -1)
          << MatchTable::Comment("Fn")
          << MatchTable::NamedValue(2, CustomCXXAction)
          << MatchTable::LineBreak;
  } else {
    // Emit all actions except the last one, then emit coverage and emit the
    // final action.
    //
    // This is because some actions, such as GIR_EraseRootFromParent_Done, also
    // double as a GIR_Done and terminate execution of the rule.
    if (!Actions.empty()) {
      for (const auto &MA : drop_end(Actions))
        MA->emitActionOpcodes(Table);
    }

    // Emit coverage right before the Done opcode>
    auto EmitCoverage = [&] {
      assert((Table.isWithCoverage() ? !Table.isCombiner() : true) &&
             "Combiner tables don't support coverage!");
      if (Table.isWithCoverage())
        Table << MatchTable::Opcode("GIR_Coverage")
              << MatchTable::IntValue(4, RuleID) << MatchTable::LineBreak;
      else if (!Table.isCombiner())
        Table << MatchTable::Comment(
                     ("GIR_Coverage, " + Twine(RuleID) + ",").str())
              << MatchTable::LineBreak;
    };

    if (Actions.empty() ||
        !Actions.back()->emitActionOpcodesAndDone(Table, EmitCoverage)) {
      EmitCoverage();
      Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak;
    }
  }

  Table << MatchTable::Label(LabelID);
  ++NumPatternEmitted;
}

bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const {
  // Rules involving more match roots have higher priority.
  if (Roots.size() > B.Roots.size())
    return true;
  if (Roots.size() < B.Roots.size())
    return false;

  for (auto Matcher : zip(Roots, B.Roots)) {
    if (std::get<0>(Matcher)->isHigherPriorityThan(*std::get<1>(Matcher)))
      return true;
    if (std::get<1>(Matcher)->isHigherPriorityThan(*std::get<0>(Matcher)))
      return false;
  }

  return false;
}

unsigned RuleMatcher::countRendererFns() const {
  return std::accumulate(Roots.begin(), Roots.end(), 0,
                         [](unsigned A, InstructionMatcher *Matcher) {
                           return A + Matcher->countRendererFns();
                         });
}

void RuleMatcher::roots_pop_front() { Roots.erase(Roots.begin()); }

//===- PredicateMatcher ---------------------------------------------------===//

PredicateMatcher::~PredicateMatcher() = default;

//===- OperandPredicateMatcher --------------------------------------------===//

OperandPredicateMatcher::~OperandPredicateMatcher() = default;

bool OperandPredicateMatcher::isHigherPriorityThan(
    const OperandPredicateMatcher &B) const {
  // Generally speaking, an instruction is more important than an Int or a
  // LiteralInt because it can cover more nodes but there's an exception to
  // this. G_CONSTANT's are less important than either of those two because they
  // are more permissive.

  const auto *AOM = dyn_cast<InstructionOperandMatcher>(this);
  const auto *BOM = dyn_cast<InstructionOperandMatcher>(&B);
  bool AIsConstantInsn = AOM && AOM->getInsnMatcher().isConstantInstruction();
  bool BIsConstantInsn = BOM && BOM->getInsnMatcher().isConstantInstruction();

  // The relative priorities between a G_CONSTANT and any other instruction
  // don't actually matter but this code is needed to ensure a strict weak
  // ordering. This is particularly important on Windows where the rules will
  // be incorrectly sorted without it.
  if (AOM && BOM)
    return !AIsConstantInsn && BIsConstantInsn;

  if (AIsConstantInsn && (B.Kind == OPM_Int || B.Kind == OPM_LiteralInt))
    return false;
  if (BIsConstantInsn && (Kind == OPM_Int || Kind == OPM_LiteralInt))
    return true;

  return Kind < B.Kind;
}

//===- SameOperandMatcher -------------------------------------------------===//

void SameOperandMatcher::emitPredicateOpcodes(MatchTable &Table) const {
  const bool IgnoreCopies = Flags & GISF_IgnoreCopies;
  Table << MatchTable::Opcode(IgnoreCopies
                                  ? "GIM_CheckIsSameOperandIgnoreCopies"
                                  : "GIM_CheckIsSameOperand")
        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
        << MatchTable::Comment("OpIdx") << MatchTable::ULEB128Value(OpIdx)
        << MatchTable::Comment("OtherMI")
        << MatchTable::ULEB128Value(OtherInsnID)
        << MatchTable::Comment("OtherOpIdx")
        << MatchTable::ULEB128Value(OtherOpIdx) << MatchTable::LineBreak;
}

//===- LLTOperandMatcher --------------------------------------------------===//

std::map<LLTCodeGen, unsigned> LLTOperandMatcher::TypeIDValues;

RecordAndValue LLTOperandMatcher::getValue() const {
  const auto VI = TypeIDValues.find(Ty);
  if (VI == TypeIDValues.end())
    return MatchTable::NamedValue(1, getTy().getCxxEnumValue());
  return {MatchTable::NamedValue(1, getTy().getCxxEnumValue()), VI->second};
}

bool LLTOperandMatcher::hasValue() const {
  if (TypeIDValues.size() != KnownTypes.size())
    initTypeIDValuesMap();
  return TypeIDValues.count(Ty);
}

void LLTOperandMatcher::emitPredicateOpcodes(MatchTable &Table) const {
  if (InsnVarID == 0) {
    Table << MatchTable::Opcode("GIM_RootCheckType");
  } else {
    Table << MatchTable::Opcode("GIM_CheckType") << MatchTable::Comment("MI")
          << MatchTable::ULEB128Value(InsnVarID);
  }
  Table << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
        << MatchTable::Comment("Type") << getValue().Record
        << MatchTable::LineBreak;
}

//===- PointerToAnyOperandMatcher -----------------------------------------===//

void PointerToAnyOperandMatcher::emitPredicateOpcodes(MatchTable &Table) const {
  Table << MatchTable::Opcode("GIM_CheckPointerToAny")
        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
        << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
        << MatchTable::Comment("SizeInBits")
        << MatchTable::ULEB128Value(SizeInBits) << MatchTable::LineBreak;
}

//===- RecordNamedOperandMatcher ------------------------------------------===//

void RecordNamedOperandMatcher::emitPredicateOpcodes(MatchTable &Table) const {
  Table << MatchTable::Opcode("GIM_RecordNamedOperand")
        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
        << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
        << MatchTable::Comment("StoreIdx") << MatchTable::ULEB128Value(StoreIdx)
        << MatchTable::Comment("Name : " + Name) << MatchTable::LineBreak;
}

//===- RecordRegisterType ------------------------------------------===//

void RecordRegisterType::emitPredicateOpcodes(MatchTable &Table) const {
  assert(Idx < 0 && "Temp types always have negative indexes!");
  Table << MatchTable::Opcode("GIM_RecordRegType") << MatchTable::Comment("MI")
        << MatchTable::ULEB128Value(InsnVarID) << MatchTable::Comment("Op")
        << MatchTable::ULEB128Value(OpIdx) << MatchTable::Comment("TempTypeIdx")
        << MatchTable::IntValue(1, Idx) << MatchTable::LineBreak;
}

//===- ComplexPatternOperandMatcher ---------------------------------------===//

void ComplexPatternOperandMatcher::emitPredicateOpcodes(
    MatchTable &Table) const {
  unsigned ID = getAllocatedTemporariesBaseID();
  Table << MatchTable::Opcode("GIM_CheckComplexPattern")
        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
        << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
        << MatchTable::Comment("Renderer") << MatchTable::IntValue(2, ID)
        << MatchTable::NamedValue(2, ("GICP_" + TheDef.getName()).str())
        << MatchTable::LineBreak;
}

unsigned ComplexPatternOperandMatcher::getAllocatedTemporariesBaseID() const {
  return Operand.getAllocatedTemporariesBaseID();
}

//===- RegisterBankOperandMatcher -----------------------------------------===//

bool RegisterBankOperandMatcher::isIdentical(const PredicateMatcher &B) const {
  return OperandPredicateMatcher::isIdentical(B) &&
         RC.getDef() == cast<RegisterBankOperandMatcher>(&B)->RC.getDef();
}

void RegisterBankOperandMatcher::emitPredicateOpcodes(MatchTable &Table) const {
  if (InsnVarID == 0) {
    Table << MatchTable::Opcode("GIM_RootCheckRegBankForClass");
  } else {
    Table << MatchTable::Opcode("GIM_CheckRegBankForClass")
          << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID);
  }

  Table << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
        << MatchTable::Comment("RC")
        << MatchTable::NamedValue(2, RC.getQualifiedIdName())
        << MatchTable::LineBreak;
}

//===- MBBOperandMatcher --------------------------------------------------===//

void MBBOperandMatcher::emitPredicateOpcodes(MatchTable &Table) const {
  Table << MatchTable::Opcode("GIM_CheckIsMBB") << MatchTable::Comment("MI")
        << MatchTable::ULEB128Value(InsnVarID) << MatchTable::Comment("Op")
        << MatchTable::ULEB128Value(OpIdx) << MatchTable::LineBreak;
}

//===- ImmOperandMatcher --------------------------------------------------===//

void ImmOperandMatcher::emitPredicateOpcodes(MatchTable &Table) const {
  Table << MatchTable::Opcode("GIM_CheckIsImm") << MatchTable::Comment("MI")
        << MatchTable::ULEB128Value(InsnVarID) << MatchTable::Comment("Op")
        << MatchTable::ULEB128Value(OpIdx) << MatchTable::LineBreak;
}

//===- ConstantIntOperandMatcher ------------------------------------------===//

void ConstantIntOperandMatcher::emitPredicateOpcodes(MatchTable &Table) const {
  const bool IsInt8 = isInt<8>(Value);
  Table << MatchTable::Opcode(IsInt8 ? "GIM_CheckConstantInt8"
                                     : "GIM_CheckConstantInt")
        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
        << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
        << MatchTable::IntValue(IsInt8 ? 1 : 8, Value) << MatchTable::LineBreak;
}

//===- LiteralIntOperandMatcher -------------------------------------------===//

void LiteralIntOperandMatcher::emitPredicateOpcodes(MatchTable &Table) const {
  Table << MatchTable::Opcode("GIM_CheckLiteralInt")
        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
        << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
        << MatchTable::IntValue(8, Value) << MatchTable::LineBreak;
}

//===- CmpPredicateOperandMatcher -----------------------------------------===//

void CmpPredicateOperandMatcher::emitPredicateOpcodes(MatchTable &Table) const {
  Table << MatchTable::Opcode("GIM_CheckCmpPredicate")
        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
        << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
        << MatchTable::Comment("Predicate")
        << MatchTable::NamedValue(2, "CmpInst", PredName)
        << MatchTable::LineBreak;
}

//===- IntrinsicIDOperandMatcher ------------------------------------------===//

void IntrinsicIDOperandMatcher::emitPredicateOpcodes(MatchTable &Table) const {
  Table << MatchTable::Opcode("GIM_CheckIntrinsicID")
        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
        << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
        << MatchTable::NamedValue(2, "Intrinsic::" + II->EnumName.str())
        << MatchTable::LineBreak;
}

//===- OperandImmPredicateMatcher -----------------------------------------===//

void OperandImmPredicateMatcher::emitPredicateOpcodes(MatchTable &Table) const {
  Table << MatchTable::Opcode("GIM_CheckImmOperandPredicate")
        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
        << MatchTable::Comment("MO") << MatchTable::ULEB128Value(OpIdx)
        << MatchTable::Comment("Predicate")
        << MatchTable::NamedValue(2, getEnumNameForPredicate(Predicate))
        << MatchTable::LineBreak;
}

//===- OperandLeafPredicateMatcher ----------------------------------------===//

void OperandLeafPredicateMatcher::emitPredicateOpcodes(
    MatchTable &Table) const {
  Table << MatchTable::Opcode("GIM_CheckLeafOperandPredicate")
        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
        << MatchTable::Comment("MO") << MatchTable::ULEB128Value(OpIdx)
        << MatchTable::Comment("Predicate")
        << MatchTable::NamedValue(2, getEnumNameForPredicate(Predicate))
        << MatchTable::LineBreak;
}

//===- OperandMatcher -----------------------------------------------------===//

std::string OperandMatcher::getOperandExpr(unsigned InsnVarID) const {
  return "State.MIs[" + llvm::to_string(InsnVarID) + "]->getOperand(" +
         llvm::to_string(OpIdx) + ")";
}

unsigned OperandMatcher::getInsnVarID() const { return Insn.getInsnVarID(); }

TempTypeIdx OperandMatcher::getTempTypeIdx(RuleMatcher &Rule) {
  assert(!IsVariadic && "Cannot use this on variadic operands!");
  if (TTIdx >= 0) {
    // Temp type index not assigned yet, so assign one and add the necessary
    // predicate.
    TTIdx = Rule.getNextTempTypeIdx();
    assert(TTIdx < 0);
    addPredicate<RecordRegisterType>(TTIdx);
    return TTIdx;
  }
  return TTIdx;
}

bool OperandMatcher::recordsOperand() const {
  return matchersRecordOperand(Predicates);
}

void OperandMatcher::emitPredicateOpcodes(MatchTable &Table) {
  if (!Optimized) {
    std::string Comment;
    raw_string_ostream CommentOS(Comment);
    CommentOS << "MIs[" << getInsnVarID() << "] ";
    if (SymbolicName.empty())
      CommentOS << "Operand " << OpIdx;
    else
      CommentOS << SymbolicName;
    Table << MatchTable::Comment(Comment) << MatchTable::LineBreak;
  }

  emitPredicateListOpcodes(Table);
}

bool OperandMatcher::isHigherPriorityThan(OperandMatcher &B) {
  // Operand matchers involving more predicates have higher priority.
  if (predicates_size() > B.predicates_size())
    return true;
  if (predicates_size() < B.predicates_size())
    return false;

  // This assumes that predicates are added in a consistent order.
  for (auto &&Predicate : zip(predicates(), B.predicates())) {
    if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate)))
      return true;
    if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate)))
      return false;
  }

  return false;
}

unsigned OperandMatcher::countRendererFns() {
  return std::accumulate(
      predicates().begin(), predicates().end(), 0,
      [](unsigned A,
         const std::unique_ptr<OperandPredicateMatcher> &Predicate) {
        return A + Predicate->countRendererFns();
      });
}

Error OperandMatcher::addTypeCheckPredicate(const TypeSetByHwMode &VTy,
                                            bool OperandIsAPointer) {
  if (!VTy.isMachineValueType())
    return failUnsupported("unsupported typeset");

  if ((VTy.getMachineValueType() == MVT::iPTR ||
       VTy.getMachineValueType() == MVT::cPTR) &&
      OperandIsAPointer) {
    addPredicate<PointerToAnyOperandMatcher>(0);
    return Error::success();
  }

  // Metadata operands have no LLT representation and no runtime type check is
  // needed — they are guaranteed to be MO_Metadata by the IRTranslator. This
  // mirrors how srcvalue is handled in importChildMatcher.
  if (VTy.getMachineValueType() == MVT::Metadata)
    return Error::success();

  auto OpTyOrNone = MVTToLLT(VTy.getMachineValueType().SimpleTy);
  if (!OpTyOrNone)
    return failUnsupported("unsupported type");

  if (OperandIsAPointer)
    addPredicate<PointerToAnyOperandMatcher>(OpTyOrNone->get().getSizeInBits());
  else if (VTy.isPointer())
    addPredicate<LLTOperandMatcher>(
        LLT::pointer(VTy.getPtrAddrSpace(), OpTyOrNone->get().getSizeInBits()));
  else
    addPredicate<LLTOperandMatcher>(*OpTyOrNone);
  return Error::success();
}

//===- InstructionOpcodeMatcher -------------------------------------------===//

DenseMap<const CodeGenInstruction *, unsigned>
    InstructionOpcodeMatcher::OpcodeValues;

RecordAndValue
InstructionOpcodeMatcher::getInstValue(const CodeGenInstruction *I) const {
  const auto VI = OpcodeValues.find(I);
  if (VI != OpcodeValues.end())
    return {MatchTable::NamedValue(2, I->Namespace, I->getName()), VI->second};
  return MatchTable::NamedValue(2, I->Namespace, I->getName());
}

void InstructionOpcodeMatcher::initOpcodeValuesMap(
    const CodeGenTarget &Target) {
  OpcodeValues.clear();

  for (const CodeGenInstruction *I : Target.getInstructions())
    OpcodeValues[I] = Target.getInstrIntValue(I->TheDef);
}

RecordAndValue InstructionOpcodeMatcher::getValue() const {
  assert(Insts.size() == 1);

  const CodeGenInstruction *I = Insts[0];
  const auto VI = OpcodeValues.find(I);
  if (VI != OpcodeValues.end())
    return {MatchTable::NamedValue(2, I->Namespace, I->getName()), VI->second};
  return MatchTable::NamedValue(2, I->Namespace, I->getName());
}

void InstructionOpcodeMatcher::emitPredicateOpcodes(MatchTable &Table) const {
  StringRef CheckType =
      Insts.size() == 1 ? "GIM_CheckOpcode" : "GIM_CheckOpcodeIsEither";
  Table << MatchTable::Opcode(CheckType) << MatchTable::Comment("MI")
        << MatchTable::ULEB128Value(InsnVarID);

  for (const CodeGenInstruction *I : Insts)
    Table << getInstValue(I).Record;
  Table << MatchTable::LineBreak;
}

bool InstructionOpcodeMatcher::isHigherPriorityThan(
    const InstructionPredicateMatcher &B) const {
  if (InstructionPredicateMatcher::isHigherPriorityThan(B))
    return true;
  if (B.InstructionPredicateMatcher::isHigherPriorityThan(*this))
    return false;

  // Prioritize opcodes for cosmetic reasons in the generated source. Although
  // this is cosmetic at the moment, we may want to drive a similar ordering
  // using instruction frequency information to improve compile time.
  if (const InstructionOpcodeMatcher *BO =
          dyn_cast<InstructionOpcodeMatcher>(&B))
    return Insts[0]->getName() < BO->Insts[0]->getName();

  return false;
}

bool InstructionOpcodeMatcher::isConstantInstruction() const {
  return Insts.size() == 1 && Insts[0]->getName() == "G_CONSTANT";
}

StringRef InstructionOpcodeMatcher::getOpcode() const {
  return Insts[0]->getName();
}

bool InstructionOpcodeMatcher::isVariadicNumOperands() const {
  // If one is variadic, they all should be.
  return Insts[0]->Operands.isVariadic;
}

StringRef InstructionOpcodeMatcher::getOperandType(unsigned OpIdx) const {
  // Types expected to be uniform for all alternatives.
  return Insts[0]->Operands[OpIdx].OperandType;
}

//===- InstructionNumOperandsMatcher --------------------------------------===//

void InstructionNumOperandsMatcher::emitPredicateOpcodes(
    MatchTable &Table) const {
  StringRef Opc;
  switch (CK) {
  case CheckKind::Eq:
    Opc = "GIM_CheckNumOperands";
    break;
  case CheckKind::GE:
    Opc = "GIM_CheckNumOperandsGE";
    break;
  case CheckKind::LE:
    Opc = "GIM_CheckNumOperandsLE";
    break;
  }
  Table << MatchTable::Opcode(Opc) << MatchTable::Comment("MI")
        << MatchTable::ULEB128Value(InsnVarID)
        << MatchTable::Comment("Expected")
        << MatchTable::ULEB128Value(NumOperands) << MatchTable::LineBreak;
}

//===- InstructionImmPredicateMatcher -------------------------------------===//

bool InstructionImmPredicateMatcher::isIdentical(
    const PredicateMatcher &B) const {
  return InstructionPredicateMatcher::isIdentical(B) &&
         Predicate.getOrigPatFragRecord() ==
             cast<InstructionImmPredicateMatcher>(&B)
                 ->Predicate.getOrigPatFragRecord();
}

void InstructionImmPredicateMatcher::emitPredicateOpcodes(
    MatchTable &Table) const {
  Table << MatchTable::Opcode(getMatchOpcodeForImmPredicate(Predicate))
        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
        << MatchTable::Comment("Predicate")
        << MatchTable::NamedValue(2, getEnumNameForPredicate(Predicate))
        << MatchTable::LineBreak;
}

//===- AtomicOrderingMMOPredicateMatcher ----------------------------------===//

bool AtomicOrderingMMOPredicateMatcher::isIdentical(
    const PredicateMatcher &B) const {
  if (!InstructionPredicateMatcher::isIdentical(B))
    return false;
  const auto &R = *cast<AtomicOrderingMMOPredicateMatcher>(&B);
  return Order == R.Order && Comparator == R.Comparator;
}

void AtomicOrderingMMOPredicateMatcher::emitPredicateOpcodes(
    MatchTable &Table) const {
  StringRef Opcode = "GIM_CheckAtomicOrdering";

  if (Comparator == AO_OrStronger)
    Opcode = "GIM_CheckAtomicOrderingOrStrongerThan";
  if (Comparator == AO_WeakerThan)
    Opcode = "GIM_CheckAtomicOrderingWeakerThan";

  Table << MatchTable::Opcode(Opcode) << MatchTable::Comment("MI")
        << MatchTable::ULEB128Value(InsnVarID) << MatchTable::Comment("Order")
        << MatchTable::NamedValue(1,
                                  ("(uint8_t)AtomicOrdering::" + Order).str())
        << MatchTable::LineBreak;
}

//===- MemorySizePredicateMatcher -----------------------------------------===//

void MemorySizePredicateMatcher::emitPredicateOpcodes(MatchTable &Table) const {
  Table << MatchTable::Opcode("GIM_CheckMemorySizeEqualTo")
        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
        << MatchTable::Comment("MMO") << MatchTable::ULEB128Value(MMOIdx)
        << MatchTable::Comment("Size") << MatchTable::IntValue(4, Size)
        << MatchTable::LineBreak;
}

//===- MemoryAddressSpacePredicateMatcher ---------------------------------===//

bool MemoryAddressSpacePredicateMatcher::isIdentical(
    const PredicateMatcher &B) const {
  if (!InstructionPredicateMatcher::isIdentical(B))
    return false;
  auto *Other = cast<MemoryAddressSpacePredicateMatcher>(&B);
  return MMOIdx == Other->MMOIdx && AddrSpaces == Other->AddrSpaces;
}

void MemoryAddressSpacePredicateMatcher::emitPredicateOpcodes(
    MatchTable &Table) const {
  assert(AddrSpaces.size() < 256);
  Table << MatchTable::Opcode("GIM_CheckMemoryAddressSpace")
        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
        << MatchTable::Comment("MMO")
        << MatchTable::ULEB128Value(MMOIdx)
        // Encode number of address spaces to expect.
        << MatchTable::Comment("NumAddrSpace")
        << MatchTable::IntValue(1, AddrSpaces.size());
  for (unsigned AS : AddrSpaces)
    Table << MatchTable::Comment("AddrSpace") << MatchTable::ULEB128Value(AS);

  Table << MatchTable::LineBreak;
}

//===- MemoryAlignmentPredicateMatcher ------------------------------------===//

bool MemoryAlignmentPredicateMatcher::isIdentical(
    const PredicateMatcher &B) const {
  if (!InstructionPredicateMatcher::isIdentical(B))
    return false;
  auto *Other = cast<MemoryAlignmentPredicateMatcher>(&B);
  return MMOIdx == Other->MMOIdx && MinAlign == Other->MinAlign;
}

void MemoryAlignmentPredicateMatcher::emitPredicateOpcodes(
    MatchTable &Table) const {
  // TODO: we could support more, just need to emit the right opcode or switch
  // to log alignment.
  assert(MinAlign < 256);
  Table << MatchTable::Opcode("GIM_CheckMemoryAlignment")
        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
        << MatchTable::Comment("MMO") << MatchTable::ULEB128Value(MMOIdx)
        << MatchTable::Comment("MinAlign") << MatchTable::IntValue(1, MinAlign)
        << MatchTable::LineBreak;
}

//===- MemoryVsLLTSizePredicateMatcher ------------------------------------===//

bool MemoryVsLLTSizePredicateMatcher::isIdentical(
    const PredicateMatcher &B) const {
  return InstructionPredicateMatcher::isIdentical(B) &&
         MMOIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->MMOIdx &&
         Relation == cast<MemoryVsLLTSizePredicateMatcher>(&B)->Relation &&
         OpIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->OpIdx;
}

void MemoryVsLLTSizePredicateMatcher::emitPredicateOpcodes(
    MatchTable &Table) const {
  Table << MatchTable::Opcode(
               Relation == EqualTo       ? "GIM_CheckMemorySizeEqualToLLT"
               : Relation == GreaterThan ? "GIM_CheckMemorySizeGreaterThanLLT"
                                         : "GIM_CheckMemorySizeLessThanLLT")
        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
        << MatchTable::Comment("MMO") << MatchTable::ULEB128Value(MMOIdx)
        << MatchTable::Comment("OpIdx") << MatchTable::ULEB128Value(OpIdx)
        << MatchTable::LineBreak;
}

//===- VectorSplatImmPredicateMatcher -------------------------------------===//

void VectorSplatImmPredicateMatcher::emitPredicateOpcodes(
    MatchTable &Table) const {
  if (Kind == AllOnes)
    Table << MatchTable::Opcode("GIM_CheckIsBuildVectorAllOnes");
  else
    Table << MatchTable::Opcode("GIM_CheckIsBuildVectorAllZeros");

  Table << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID);
  Table << MatchTable::LineBreak;
}

//===- GenericInstructionPredicateMatcher ---------------------------------===//

GenericInstructionPredicateMatcher::GenericInstructionPredicateMatcher(
    unsigned InsnVarID, TreePredicateFn Predicate)
    : GenericInstructionPredicateMatcher(InsnVarID,
                                         getEnumNameForPredicate(Predicate)) {}

bool GenericInstructionPredicateMatcher::isIdentical(
    const PredicateMatcher &B) const {
  return InstructionPredicateMatcher::isIdentical(B) &&
         EnumVal ==
             static_cast<const GenericInstructionPredicateMatcher &>(B).EnumVal;
}
void GenericInstructionPredicateMatcher::emitPredicateOpcodes(
    MatchTable &Table) const {
  Table << MatchTable::Opcode("GIM_CheckCxxInsnPredicate")
        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
        << MatchTable::Comment("FnId") << MatchTable::NamedValue(2, EnumVal)
        << MatchTable::LineBreak;
}

//===- MIFlagsInstructionPredicateMatcher ---------------------------------===//

bool MIFlagsInstructionPredicateMatcher::isIdentical(
    const PredicateMatcher &B) const {
  if (!InstructionPredicateMatcher::isIdentical(B))
    return false;
  const auto &Other =
      static_cast<const MIFlagsInstructionPredicateMatcher &>(B);
  return Flags == Other.Flags && CheckNot == Other.CheckNot;
}

void MIFlagsInstructionPredicateMatcher::emitPredicateOpcodes(
    MatchTable &Table) const {
  Table << MatchTable::Opcode(CheckNot ? "GIM_MIFlagsNot" : "GIM_MIFlags")
        << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
        << MatchTable::NamedValue(4, join(Flags, " | "))
        << MatchTable::LineBreak;
}

//===- InstructionMatcher -------------------------------------------------===//

OperandMatcher &
InstructionMatcher::addOperand(unsigned OpIdx, const std::string &SymbolicName,
                               unsigned AllocatedTemporariesBaseID,
                               bool IsVariadic) {
  assert((Operands.empty() || !Operands.back()->isVariadic()) &&
         "Cannot add more operands after a variadic operand");
  Operands.emplace_back(new OperandMatcher(
      *this, OpIdx, SymbolicName, AllocatedTemporariesBaseID, IsVariadic));
  if (!SymbolicName.empty())
    Rule.defineOperand(SymbolicName, *Operands.back());
  return *Operands.back();
}

OperandMatcher &InstructionMatcher::getOperand(unsigned OpIdx) {
  auto I = llvm::find_if(Operands,
                         [&OpIdx](const std::unique_ptr<OperandMatcher> &X) {
                           return X->getOpIdx() == OpIdx;
                         });
  if (I != Operands.end())
    return **I;
  llvm_unreachable("Failed to lookup operand");
}

OperandMatcher &InstructionMatcher::addPhysRegInput(const Record *Reg,
                                                    unsigned OpIdx,
                                                    unsigned TempOpIdx) {
  assert(SymbolicName.empty());
  OperandMatcher *OM = new OperandMatcher(*this, OpIdx, "", TempOpIdx);
  Operands.emplace_back(OM);
  Rule.definePhysRegOperand(Reg, *OM);
  return *OM;
}

bool InstructionMatcher::recordsOperand() const {
  return matchersRecordOperand(Predicates) || matchersRecordOperand(operands());
}

void InstructionMatcher::emitPredicateOpcodes(MatchTable &Table) {
  if (canAddNumOperandsCheck()) {
    InstructionNumOperandsMatcher(InsnVarID, getNumOperandMatchers())
        .emitPredicateOpcodes(Table);
  }

  // First emit all instruction level predicates need to be verified before we
  // can verify operands.
  emitFilteredPredicateListOpcodes(
      [](const PredicateMatcher &P) { return !P.dependsOnRecordedOperands(); },
      Table);

  // Emit all operand constraints.
  for (const auto &Operand : Operands)
    Operand->emitPredicateOpcodes(Table);

  // All of the tablegen defined predicates should now be matched. Now emit
  // any custom predicates that rely on all generated checks.
  emitFilteredPredicateListOpcodes(
      [](const PredicateMatcher &P) { return P.dependsOnRecordedOperands(); },
      Table);
}

bool InstructionMatcher::isHigherPriorityThan(InstructionMatcher &B) {
  // Instruction matchers involving more operands have higher priority.
  if (Operands.size() > B.Operands.size())
    return true;
  if (Operands.size() < B.Operands.size())
    return false;

  for (auto &&P : zip(predicates(), B.predicates())) {
    auto L = static_cast<InstructionPredicateMatcher *>(std::get<0>(P).get());
    auto R = static_cast<InstructionPredicateMatcher *>(std::get<1>(P).get());
    if (L->isHigherPriorityThan(*R))
      return true;
    if (R->isHigherPriorityThan(*L))
      return false;
  }

  for (auto Operand : zip(Operands, B.Operands)) {
    if (std::get<0>(Operand)->isHigherPriorityThan(*std::get<1>(Operand)))
      return true;
    if (std::get<1>(Operand)->isHigherPriorityThan(*std::get<0>(Operand)))
      return false;
  }
  // Instruction matchers involving more predicates have higher priority.
  if (predicates_size() > B.predicates_size())
    return true;
  if (predicates_size() < B.predicates_size())
    return false;

  return false;
}

unsigned InstructionMatcher::countRendererFns() {
  return std::accumulate(
             predicates().begin(), predicates().end(), 0,
             [](unsigned A,
                const std::unique_ptr<PredicateMatcher> &Predicate) {
               return A + Predicate->countRendererFns();
             }) +
         std::accumulate(
             Operands.begin(), Operands.end(), 0,
             [](unsigned A, const std::unique_ptr<OperandMatcher> &Operand) {
               return A + Operand->countRendererFns();
             });
}

void InstructionMatcher::optimize() {
  SmallVector<std::unique_ptr<PredicateMatcher>, 8> Stash;
  const auto &OpcMatcher = getOpcodeMatcher();

  Stash.push_back(predicates_pop_front());
  if (Stash.back().get() == &OpcMatcher) {
    // FIXME: Is this even needed still? Why the isVariadicNumOperands check?
    if (canAddNumOperandsCheck() && OpcMatcher.isVariadicNumOperands() &&
        getNumOperandMatchers() != 0) {
      Stash.emplace_back(new InstructionNumOperandsMatcher(
          InsnVarID, getNumOperandMatchers()));
    }
    AllowNumOpsCheck = false;

    for (auto &OM : Operands)
      for (auto &OP : OM->predicates())
        if (isa<IntrinsicIDOperandMatcher>(OP)) {
          Stash.push_back(std::move(OP));
          OM->eraseNullPredicates();
          break;
        }
  }

  if (InsnVarID > 0) {
    assert(!Operands.empty() && "Nested instruction is expected to def a vreg");
    for (auto &OP : Operands[0]->predicates())
      OP.reset();
    Operands[0]->eraseNullPredicates();
  }
  for (auto &OM : Operands) {
    for (auto &OP : OM->predicates())
      if (isa<LLTOperandMatcher>(OP) || isa<LLTOperandShapeMatcher>(OP))
        Stash.push_back(std::move(OP));
    OM->eraseNullPredicates();
  }
  while (!Stash.empty())
    prependPredicate(Stash.pop_back_val());
}

//===- InstructionOperandMatcher ------------------------------------------===//

void InstructionOperandMatcher::emitCaptureOpcodes(MatchTable &Table) const {
  const unsigned NewInsnVarID = InsnMatcher.getInsnVarID();
  const bool IgnoreCopies = Flags & GISF_IgnoreCopies;
  Table << MatchTable::Opcode(IgnoreCopies ? "GIM_RecordInsnIgnoreCopies"
                                           : "GIM_RecordInsn")
        << MatchTable::Comment("DefineMI")
        << MatchTable::ULEB128Value(NewInsnVarID) << MatchTable::Comment("MI")
        << MatchTable::ULEB128Value(getInsnVarID())
        << MatchTable::Comment("OpIdx") << MatchTable::ULEB128Value(getOpIdx())
        << MatchTable::Comment("MIs[" + llvm::to_string(NewInsnVarID) + "]")
        << MatchTable::LineBreak;
}

bool InstructionOperandMatcher::isHigherPriorityThan(
    const OperandPredicateMatcher &B) const {
  if (OperandPredicateMatcher::isHigherPriorityThan(B))
    return true;
  if (B.OperandPredicateMatcher::isHigherPriorityThan(*this))
    return false;

  if (const InstructionOperandMatcher *BP =
          dyn_cast<InstructionOperandMatcher>(&B))
    if (InsnMatcher.isHigherPriorityThan(BP->InsnMatcher))
      return true;
  return false;
}

//===- OperandRenderer ----------------------------------------------------===//

OperandRenderer::~OperandRenderer() = default;

//===- CopyRenderer -------------------------------------------------------===//

void CopyRenderer::emitRenderOpcodes(MatchTable &Table, unsigned NewInsnID,
                                     unsigned OldInsnID, unsigned OldOpIdx,
                                     StringRef Name, bool ForVariadic) {
  if (!ForVariadic && NewInsnID == 0 && OldInsnID == 0) {
    Table << MatchTable::Opcode("GIR_RootToRootCopy");
  } else {
    Table << MatchTable::Opcode(ForVariadic ? "GIR_CopyRemaining" : "GIR_Copy")
          << MatchTable::Comment("NewInsnID")
          << MatchTable::ULEB128Value(NewInsnID)
          << MatchTable::Comment("OldInsnID")
          << MatchTable::ULEB128Value(OldInsnID);
  }

  Table << MatchTable::Comment("OpIdx") << MatchTable::ULEB128Value(OldOpIdx)
        << MatchTable::Comment(Name) << MatchTable::LineBreak;
}

void CopyRenderer::emitRenderOpcodes(MatchTable &Table) const {
  emitRenderOpcodes(Table, NewInsnID, OldInsnID, OldOpIdx, SymbolicName,
                    OldOpIsVariadic);
}

//===- CopyPhysRegRenderer ------------------------------------------------===//

void CopyPhysRegRenderer::emitRenderOpcodes(MatchTable &Table) const {
  CopyRenderer::emitRenderOpcodes(Table, NewInsnID, OldInsnID, OldOpIdx,
                                  PhysReg->getName());
}

//===- CopyOrAddZeroRegRenderer -------------------------------------------===//

void CopyOrAddZeroRegRenderer::emitRenderOpcodes(MatchTable &Table) const {
  Table << MatchTable::Opcode("GIR_CopyOrAddZeroReg")
        << MatchTable::Comment("NewInsnID")
        << MatchTable::ULEB128Value(NewInsnID)
        << MatchTable::Comment("OldInsnID")
        << MatchTable::ULEB128Value(OldInsnID) << MatchTable::Comment("OpIdx")
        << MatchTable::ULEB128Value(OldOpIdx)
        << MatchTable::NamedValue(
               2,
               (ZeroRegisterDef->getValue("Namespace")
                    ? ZeroRegisterDef->getValueAsString("Namespace")
                    : ""),
               ZeroRegisterDef->getName())
        << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
}

//===- CopyConstantAsImmRenderer ------------------------------------------===//

void CopyConstantAsImmRenderer::emitRenderOpcodes(MatchTable &Table) const {
  Table << MatchTable::Opcode(Signed ? "GIR_CopyConstantAsSImm"
                                     : "GIR_CopyConstantAsUImm")
        << MatchTable::Comment("NewInsnID")
        << MatchTable::ULEB128Value(NewInsnID)
        << MatchTable::Comment("OldInsnID")
        << MatchTable::ULEB128Value(OldInsnID)
        << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
}

//===- CopyFConstantAsFPImmRenderer ---------------------------------------===//

void CopyFConstantAsFPImmRenderer::emitRenderOpcodes(MatchTable &Table) const {
  Table << MatchTable::Opcode("GIR_CopyFConstantAsFPImm")
        << MatchTable::Comment("NewInsnID")
        << MatchTable::ULEB128Value(NewInsnID)
        << MatchTable::Comment("OldInsnID")
        << MatchTable::ULEB128Value(OldInsnID)
        << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
}

//===- CopySubRegRenderer -------------------------------------------------===//

void CopySubRegRenderer::emitRenderOpcodes(MatchTable &Table) const {
  Table << MatchTable::Opcode("GIR_CopySubReg")
        << MatchTable::Comment("NewInsnID")
        << MatchTable::ULEB128Value(NewInsnID)
        << MatchTable::Comment("OldInsnID")
        << MatchTable::ULEB128Value(OldInsnID) << MatchTable::Comment("OpIdx")
        << MatchTable::ULEB128Value(OldOpIdx)
        << MatchTable::Comment("SubRegIdx")
        << MatchTable::IntValue(2, SubReg->EnumValue)
        << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
}

//===- AddRegisterRenderer ------------------------------------------------===//

void AddRegisterRenderer::emitRenderOpcodes(MatchTable &Table) const {
  Table << MatchTable::Opcode("GIR_AddRegister")
        << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID);
  if (RegisterDef->getName() != "zero_reg") {
    Table << MatchTable::NamedValue(
        2,
        (RegisterDef->getValue("Namespace")
             ? RegisterDef->getValueAsString("Namespace")
             : ""),
        RegisterDef->getName());
  } else {
    Table << MatchTable::NamedValue(2, Target.getRegNamespace(), "NoRegister");
  }
  Table << MatchTable::Comment("AddRegisterRegFlags");

  // TODO: This is encoded as a 64-bit element, but only 16 or 32-bits are
  // really needed for a physical register reference. We can pack the
  // register and flags in a single field.
  if (IsDef) {
    Table << MatchTable::NamedValue(
        2, IsDead ? "static_cast<uint16_t>(RegState::Define|RegState::Dead)"
                  : "static_cast<uint16_t>(RegState::Define)");
  } else {
    assert(!IsDead && "A use cannot be dead");
    Table << MatchTable::IntValue(2, 0);
  }
  Table << MatchTable::LineBreak;
}

//===- TempRegRenderer ----------------------------------------------------===//

void TempRegRenderer::emitRenderOpcodes(MatchTable &Table) const {
  const bool NeedsFlags = (SubRegIdx || IsDef);
  if (SubRegIdx) {
    assert(!IsDef);
    Table << MatchTable::Opcode("GIR_AddTempSubRegister");
  } else {
    Table << MatchTable::Opcode(NeedsFlags ? "GIR_AddTempRegister"
                                           : "GIR_AddSimpleTempRegister");
  }

  Table << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
        << MatchTable::Comment("TempRegID")
        << MatchTable::ULEB128Value(TempRegID);

  if (!NeedsFlags) {
    Table << MatchTable::LineBreak;
    return;
  }

  Table << MatchTable::Comment("TempRegFlags");
  if (IsDef) {
    SmallString<32> RegFlags;
    RegFlags += "static_cast<uint16_t>(RegState::Define";
    if (IsDead)
      RegFlags += "|RegState::Dead";
    RegFlags += ")";
    Table << MatchTable::NamedValue(2, RegFlags);
  } else {
    Table << MatchTable::IntValue(2, 0);
  }

  if (SubRegIdx)
    Table << MatchTable::NamedValue(2, SubRegIdx->getQualifiedName());
  Table << MatchTable::LineBreak;
}

//===- ImmRenderer --------------------------------------------------------===//

void ImmRenderer::emitAddImm(MatchTable &Table, unsigned InsnID, int64_t Imm,
                             StringRef ImmName) {
  const bool IsInt8 = isInt<8>(Imm);

  Table << MatchTable::Opcode(IsInt8 ? "GIR_AddImm8" : "GIR_AddImm")
        << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
        << MatchTable::Comment(ImmName)
        << MatchTable::IntValue(IsInt8 ? 1 : 8, Imm) << MatchTable::LineBreak;
}

void ImmRenderer::emitRenderOpcodes(MatchTable &Table) const {
  if (CImmLLT) {
    assert(Table.isCombiner() &&
           "ConstantInt immediate are only for combiners!");
    Table << MatchTable::Opcode("GIR_AddCImm") << MatchTable::Comment("InsnID")
          << MatchTable::ULEB128Value(InsnID) << MatchTable::Comment("Type");
    emitType(Table, *CImmLLT);
    Table << MatchTable::Comment("Imm") << MatchTable::IntValue(8, Imm)
          << MatchTable::LineBreak;
  } else {
    emitAddImm(Table, InsnID, Imm);
  }
}

//===- SubRegIndexRenderer ------------------------------------------------===//

void SubRegIndexRenderer::emitRenderOpcodes(MatchTable &Table) const {
  ImmRenderer::emitAddImm(Table, InsnID, SubRegIdx->EnumValue, "SubRegIndex");
}

//===- RenderComplexPatternOperand ----------------------------------------===//

void RenderComplexPatternOperand::emitRenderOpcodes(MatchTable &Table) const {
  Table << MatchTable::Opcode(
               SubOperand ? (SubReg ? "GIR_ComplexSubOperandSubRegRenderer"
                                    : "GIR_ComplexSubOperandRenderer")
                          : "GIR_ComplexRenderer")
        << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
        << MatchTable::Comment("RendererID")
        << MatchTable::IntValue(2, RendererID);
  if (SubOperand)
    Table << MatchTable::Comment("SubOperand")
          << MatchTable::ULEB128Value(*SubOperand);
  if (SubReg)
    Table << MatchTable::Comment("SubRegIdx")
          << MatchTable::IntValue(2, SubReg->EnumValue);
  Table << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
}

//===- IntrinsicIDRenderer ------------------------------------------------===//

void IntrinsicIDRenderer::emitRenderOpcodes(MatchTable &Table) const {
  Table << MatchTable::Opcode("GIR_AddIntrinsicID") << MatchTable::Comment("MI")
        << MatchTable::ULEB128Value(InsnID)
        << MatchTable::NamedValue(2, "Intrinsic::" + II->EnumName.str())
        << MatchTable::LineBreak;
}

//===- CustomRenderer -----------------------------------------------------===//

void CustomRenderer::emitRenderOpcodes(MatchTable &Table) const {
  Table << MatchTable::Opcode("GIR_CustomRenderer")
        << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
        << MatchTable::Comment("OldInsnID")
        << MatchTable::ULEB128Value(OldInsnID)
        << MatchTable::Comment("Renderer")
        << MatchTable::NamedValue(
               2, "GICR_" + Renderer.getValueAsString("RendererFn").str())
        << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
}

//===- CustomOperandRenderer ----------------------------------------------===//

void CustomOperandRenderer::emitRenderOpcodes(MatchTable &Table) const {
  Table << MatchTable::Opcode("GIR_CustomOperandRenderer")
        << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
        << MatchTable::Comment("OldInsnID")
        << MatchTable::ULEB128Value(OldInsnID) << MatchTable::Comment("OpIdx")
        << MatchTable::ULEB128Value(OldOpIdx)
        << MatchTable::Comment("OperandRenderer")
        << MatchTable::NamedValue(
               2, "GICR_" + Renderer.getValueAsString("RendererFn").str())
        << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
}

//===- BuildMIAction ------------------------------------------------------===//

bool BuildMIAction::canMutate(RuleMatcher &Rule,
                              const InstructionMatcher *Insn) const {
  if (!Insn || Insn->hasVariadicMatcher())
    return false;

  if (OperandRenderers.size() != Insn->getNumOperandMatchers())
    return false;

  for (const auto &Renderer : enumerate(OperandRenderers)) {
    if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.value())) {
      const OperandMatcher &OM =
          Rule.getOperandMatcher(Copy->getSymbolicName());
      if (Insn != &OM.getInstructionMatcher() ||
          OM.getOpIdx() != Renderer.index())
        return false;
    } else {
      return false;
    }
  }

  return true;
}

void BuildMIAction::chooseInsnToMutate(RuleMatcher &Rule) {
  for (auto *MutateCandidate : Rule.mutatable_insns()) {
    if (canMutate(Rule, MutateCandidate)) {
      // Take the first one we're offered that we're able to mutate.
      Rule.reserveInsnMatcherForMutation(MutateCandidate);
      Matched = MutateCandidate;
      Rule.tryEraseInsnID(MutateCandidate->getInsnVarID());
      return;
    }
  }
}

void BuildMIAction::emitActionOpcodes(MatchTable &Table) const {
  const auto AddMIFlags = [&]() {
    for (const InstructionMatcher *IM : CopiedFlags) {
      Table << MatchTable::Opcode("GIR_CopyMIFlags")
            << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
            << MatchTable::Comment("OldInsnID")
            << MatchTable::ULEB128Value(IM->getInsnVarID())
            << MatchTable::LineBreak;
    }

    if (!SetFlags.empty()) {
      Table << MatchTable::Opcode("GIR_SetMIFlags")
            << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
            << MatchTable::NamedValue(4, join(SetFlags, " | "))
            << MatchTable::LineBreak;
    }

    if (!UnsetFlags.empty()) {
      Table << MatchTable::Opcode("GIR_UnsetMIFlags")
            << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
            << MatchTable::NamedValue(4, join(UnsetFlags, " | "))
            << MatchTable::LineBreak;
    }
  };

  if (Matched) {
    unsigned RecycleInsnID = Matched->getInsnVarID();
    Table << MatchTable::Opcode("GIR_MutateOpcode")
          << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
          << MatchTable::Comment("RecycleInsnID")
          << MatchTable::ULEB128Value(RecycleInsnID)
          << MatchTable::Comment("Opcode")
          << MatchTable::NamedValue(2, I->Namespace, I->getName())
          << MatchTable::LineBreak;

    if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) {
      for (auto *Def : I->ImplicitDefs) {
        auto Namespace = Def->getValue("Namespace")
                             ? Def->getValueAsString("Namespace")
                             : "";
        const bool IsDead = DeadImplicitDefs.contains(Def);
        Table << MatchTable::Opcode("GIR_AddImplicitDef")
              << MatchTable::Comment("InsnID")
              << MatchTable::ULEB128Value(InsnID)
              << MatchTable::NamedValue(2, Namespace, Def->getName())
              << (IsDead ? MatchTable::NamedValue(
                               2, "static_cast<unsigned>(RegState::Dead)")
                         : MatchTable::IntValue(2, 0))
              << MatchTable::LineBreak;
      }
      for (auto *Use : I->ImplicitUses) {
        auto Namespace = Use->getValue("Namespace")
                             ? Use->getValueAsString("Namespace")
                             : "";
        Table << MatchTable::Opcode("GIR_AddImplicitUse")
              << MatchTable::Comment("InsnID")
              << MatchTable::ULEB128Value(InsnID)
              << MatchTable::NamedValue(2, Namespace, Use->getName())
              << MatchTable::LineBreak;
      }
    }

    AddMIFlags();

    // Mark the mutated instruction as erased.
    return;
  }

  // TODO: Simple permutation looks like it could be almost as common as
  //       mutation due to commutative operations.

  if (InsnID == 0) {
    Table << MatchTable::Opcode("GIR_BuildRootMI");
  } else {
    Table << MatchTable::Opcode("GIR_BuildMI") << MatchTable::Comment("InsnID")
          << MatchTable::ULEB128Value(InsnID);
  }

  Table << MatchTable::Comment("Opcode")
        << MatchTable::NamedValue(2, I->Namespace, I->getName())
        << MatchTable::LineBreak;

  for (const auto &Renderer : OperandRenderers)
    Renderer->emitRenderOpcodes(Table);

  for (auto [OpIdx, Def] : enumerate(I->ImplicitDefs)) {
    auto Namespace =
        Def->getValue("Namespace") ? Def->getValueAsString("Namespace") : "";
    if (DeadImplicitDefs.contains(Def)) {
      Table
          << MatchTable::Opcode("GIR_SetImplicitDefDead")
          << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
          << MatchTable::Comment(
                 ("OpIdx for " + Namespace + "::" + Def->getName() + "").str())
          << MatchTable::ULEB128Value(OpIdx) << MatchTable::LineBreak;
    }
  }

  if (!MergeInsnIDs.empty()) {
    assert(I->mayLoad || I->mayStore);
    Table << MatchTable::Opcode("GIR_MergeMemOperands")
          << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
          << MatchTable::Comment("NumInsns")
          << MatchTable::IntValue(1, MergeInsnIDs.size())
          << MatchTable::Comment("MergeInsnID's");
    for (const auto &MergeInsnID : MergeInsnIDs)
      Table << MatchTable::ULEB128Value(MergeInsnID);
    Table << MatchTable::LineBreak;
  }

  AddMIFlags();
}

//===- BuildConstantAction ------------------------------------------------===//

void BuildConstantAction::emitActionOpcodes(MatchTable &Table) const {
  Table << MatchTable::Opcode("GIR_BuildConstant")
        << MatchTable::Comment("TempRegID")
        << MatchTable::ULEB128Value(TempRegID) << MatchTable::Comment("Val")
        << MatchTable::IntValue(8, Val) << MatchTable::LineBreak;
}

//===- EraseInstAction ----------------------------------------------------===//

void EraseInstAction::emitActionOpcodes(MatchTable &Table) const {
  Table << MatchTable::Opcode("GIR_EraseFromParent")
        << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
        << MatchTable::LineBreak;
}

bool EraseInstAction::emitActionOpcodesAndDone(
    MatchTable &Table, function_ref<void()> OnDone) const {
  if (InsnID != 0) {
    emitActionOpcodes(Table);
    return false;
  }

  OnDone();
  Table << MatchTable::Opcode("GIR_EraseRootFromParent_Done", -1)
        << MatchTable::LineBreak;
  return true;
}

//===- ReplaceRegAction ---------------------------------------------------===//

void ReplaceRegAction::emitAdditionalPredicates(MatchTable &Table) const {
  if (TempRegID != (unsigned)-1)
    return;

  Table << MatchTable::Opcode("GIM_CheckCanReplaceReg")
        << MatchTable::Comment("OldInsnID")
        << MatchTable::ULEB128Value(OldInsnID)
        << MatchTable::Comment("OldOpIdx") << MatchTable::ULEB128Value(OldOpIdx)
        << MatchTable::Comment("NewInsnId")
        << MatchTable::ULEB128Value(NewInsnId)
        << MatchTable::Comment("NewOpIdx") << MatchTable::ULEB128Value(NewOpIdx)
        << MatchTable::LineBreak;
}

void ReplaceRegAction::emitActionOpcodes(MatchTable &Table) const {
  if (TempRegID != (unsigned)-1) {
    Table << MatchTable::Opcode("GIR_ReplaceRegWithTempReg")
          << MatchTable::Comment("OldInsnID")
          << MatchTable::ULEB128Value(OldInsnID)
          << MatchTable::Comment("OldOpIdx")
          << MatchTable::ULEB128Value(OldOpIdx)
          << MatchTable::Comment("TempRegID")
          << MatchTable::ULEB128Value(TempRegID) << MatchTable::LineBreak;
  } else {
    Table << MatchTable::Opcode("GIR_ReplaceReg")
          << MatchTable::Comment("OldInsnID")
          << MatchTable::ULEB128Value(OldInsnID)
          << MatchTable::Comment("OldOpIdx")
          << MatchTable::ULEB128Value(OldOpIdx)
          << MatchTable::Comment("NewInsnId")
          << MatchTable::ULEB128Value(NewInsnId)
          << MatchTable::Comment("NewOpIdx")
          << MatchTable::ULEB128Value(NewOpIdx) << MatchTable::LineBreak;
  }
}

//===- ConstrainOperandToRegClassAction -----------------------------------===//

void ConstrainOperandToRegClassAction::emitActionOpcodes(
    MatchTable &Table) const {
  Table << MatchTable::Opcode("GIR_ConstrainOperandRC")
        << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
        << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
        << MatchTable::NamedValue(2, RC.getQualifiedIdName())
        << MatchTable::LineBreak;
}

//===- MakeTempRegisterAction ---------------------------------------------===//

void MakeTempRegisterAction::emitActionOpcodes(MatchTable &Table) const {
  Table << MatchTable::Opcode("GIR_MakeTempReg")
        << MatchTable::Comment("TempRegID")
        << MatchTable::ULEB128Value(TempRegID) << MatchTable::Comment("TypeID");
  emitType(Table, Ty);
  Table << MatchTable::LineBreak;
}