xref: /freebsd-current/contrib/llvm-project/llvm/utils/TableGen/GlobalISelCombinerEmitter.cpp

//===- GlobalISelCombinerMatchTableEmitter.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
//
//===----------------------------------------------------------------------===//
//
/// \file Generate a combiner implementation for GlobalISel from a declarative
/// syntax using GlobalISelMatchTable.
///
/// Usually, TableGen backends use "assert is an error" as a means to report
/// invalid input. They try to diagnose common case but don't try very hard and
/// crashes can be common. This backend aims to behave closer to how a language
/// compiler frontend would behave: we try extra hard to diagnose invalid inputs
/// early, and any crash should be considered a bug (= a feature or diagnostic
/// is missing).
///
/// While this can make the backend a bit more complex than it needs to be, it
/// pays off because MIR patterns can get complicated. Giving useful error
/// messages to combine writers can help boost their productivity.
///
/// As with anything, a good balance has to be found. We also don't want to
/// write hundreds of lines of code to detect edge cases. In practice, crashing
/// very occasionally, or giving poor errors in some rare instances, is fine.
///
//===----------------------------------------------------------------------===//

#include "CodeGenInstruction.h"
#include "CodeGenTarget.h"
#include "GlobalISel/CXXPredicates.h"
#include "GlobalISel/CodeExpander.h"
#include "GlobalISel/CodeExpansions.h"
#include "GlobalISel/CombinerUtils.h"
#include "GlobalISel/MatchDataInfo.h"
#include "GlobalISel/Patterns.h"
#include "GlobalISelMatchTable.h"
#include "GlobalISelMatchTableExecutorEmitter.h"
#include "SubtargetFeatureInfo.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringSet.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/PrettyStackTrace.h"
#include "llvm/Support/ScopedPrinter.h"
#include "llvm/TableGen/Error.h"
#include "llvm/TableGen/Record.h"
#include "llvm/TableGen/StringMatcher.h"
#include "llvm/TableGen/TableGenBackend.h"
#include <cstdint>

using namespace llvm;
using namespace llvm::gi;

#define DEBUG_TYPE "gicombiner-emitter"

namespace {
cl::OptionCategory
    GICombinerEmitterCat("Options for -gen-global-isel-combiner");
cl::opt<bool> StopAfterParse(
    "gicombiner-stop-after-parse",
    cl::desc("Stop processing after parsing rules and dump state"),
    cl::cat(GICombinerEmitterCat));
cl::list<std::string>
    SelectedCombiners("combiners", cl::desc("Emit the specified combiners"),
                      cl::cat(GICombinerEmitterCat), cl::CommaSeparated);
cl::opt<bool> DebugCXXPreds(
    "gicombiner-debug-cxxpreds",
    cl::desc("Add Contextual/Debug comments to all C++ predicates"),
    cl::cat(GICombinerEmitterCat));
cl::opt<bool> DebugTypeInfer("gicombiner-debug-typeinfer",
                             cl::desc("Print type inference debug logs"),
                             cl::cat(GICombinerEmitterCat));

constexpr StringLiteral CXXApplyPrefix = "GICXXCustomAction_CombineApply";
constexpr StringLiteral CXXPredPrefix = "GICXXPred_MI_Predicate_";
constexpr StringLiteral MIFlagsEnumClassName = "MIFlagEnum";

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

void declareInstExpansion(CodeExpansions &CE, const InstructionMatcher &IM,
                          StringRef Name) {
  CE.declare(Name, "State.MIs[" + to_string(IM.getInsnVarID()) + "]");
}

void declareInstExpansion(CodeExpansions &CE, const BuildMIAction &A,
                          StringRef Name) {
  // Note: we use redeclare here because this may overwrite a matcher inst
  // expansion.
  CE.redeclare(Name, "OutMIs[" + to_string(A.getInsnID()) + "]");
}

void declareOperandExpansion(CodeExpansions &CE, const OperandMatcher &OM,
                             StringRef Name) {
  CE.declare(Name, "State.MIs[" + to_string(OM.getInsnVarID()) +
                       "]->getOperand(" + to_string(OM.getOpIdx()) + ")");
}

void declareTempRegExpansion(CodeExpansions &CE, unsigned TempRegID,
                             StringRef Name) {
  CE.declare(Name, "State.TempRegisters[" + to_string(TempRegID) + "]");
}

//===- Misc. Helpers  -----------------------------------------------------===//

/// Copies a StringRef into a static pool to preserve it.
/// Most Pattern classes use StringRef so we need this.
StringRef insertStrRef(StringRef S) {
  if (S.empty())
    return {};

  static StringSet<> Pool;
  auto [It, Inserted] = Pool.insert(S);
  return It->getKey();
}

template <typename Container> auto keys(Container &&C) {
  return map_range(C, [](auto &Entry) -> auto & { return Entry.first; });
}

template <typename Container> auto values(Container &&C) {
  return map_range(C, [](auto &Entry) -> auto & { return Entry.second; });
}

std::string getIsEnabledPredicateEnumName(unsigned CombinerRuleID) {
  return "GICXXPred_Simple_IsRule" + to_string(CombinerRuleID) + "Enabled";
}

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

LLTCodeGen getLLTCodeGen(const PatternType &PT) {
  return *MVTToLLT(getValueType(PT.getLLTRecord()));
}

LLTCodeGenOrTempType getLLTCodeGenOrTempType(const PatternType &PT,
                                             RuleMatcher &RM) {
  assert(!PT.isNone());

  if (PT.isLLT())
    return getLLTCodeGen(PT);

  assert(PT.isTypeOf());
  auto &OM = RM.getOperandMatcher(PT.getTypeOfOpName());
  return OM.getTempTypeIdx(RM);
}

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

class PrettyStackTraceParse : public PrettyStackTraceEntry {
  const Record &Def;

public:
  PrettyStackTraceParse(const Record &Def) : Def(Def) {}

  void print(raw_ostream &OS) const override {
    if (Def.isSubClassOf("GICombineRule"))
      OS << "Parsing GICombineRule '" << Def.getName() << "'";
    else if (Def.isSubClassOf(PatFrag::ClassName))
      OS << "Parsing " << PatFrag::ClassName << " '" << Def.getName() << "'";
    else
      OS << "Parsing '" << Def.getName() << "'";
    OS << '\n';
  }
};

class PrettyStackTraceEmit : public PrettyStackTraceEntry {
  const Record &Def;
  const Pattern *Pat = nullptr;

public:
  PrettyStackTraceEmit(const Record &Def, const Pattern *Pat = nullptr)
      : Def(Def), Pat(Pat) {}

  void print(raw_ostream &OS) const override {
    if (Def.isSubClassOf("GICombineRule"))
      OS << "Emitting GICombineRule '" << Def.getName() << "'";
    else if (Def.isSubClassOf(PatFrag::ClassName))
      OS << "Emitting " << PatFrag::ClassName << " '" << Def.getName() << "'";
    else
      OS << "Emitting '" << Def.getName() << "'";

    if (Pat)
      OS << " [" << Pat->getKindName() << " '" << Pat->getName() << "']";
    OS << '\n';
  }
};

//===- CombineRuleOperandTypeChecker --------------------------------------===//

/// This is a wrapper around OperandTypeChecker specialized for Combiner Rules.
/// On top of doing the same things as OperandTypeChecker, this also attempts to
/// infer as many types as possible for temporary register defs & immediates in
/// apply patterns.
///
/// The inference is trivial and leverages the MCOI OperandTypes encoded in
/// CodeGenInstructions to infer types across patterns in a CombineRule. It's
/// thus very limited and only supports CodeGenInstructions (but that's the main
/// use case so it's fine).
///
/// We only try to infer untyped operands in apply patterns when they're temp
/// reg defs, or immediates. Inference always outputs a `TypeOf<$x>` where $x is
/// a named operand from a match pattern.
class CombineRuleOperandTypeChecker : private OperandTypeChecker {
public:
  CombineRuleOperandTypeChecker(const Record &RuleDef,
                                const OperandTable &MatchOpTable)
      : OperandTypeChecker(RuleDef.getLoc()), RuleDef(RuleDef),
        MatchOpTable(MatchOpTable) {}

  /// Records and checks a 'match' pattern.
  bool processMatchPattern(InstructionPattern &P);

  /// Records and checks an 'apply' pattern.
  bool processApplyPattern(InstructionPattern &P);

  /// Propagates types, then perform type inference and do a second round of
  /// propagation in the apply patterns only if any types were inferred.
  void propagateAndInferTypes();

private:
  /// TypeEquivalenceClasses are groups of operands of an instruction that share
  /// a common type.
  ///
  /// e.g. [[a, b], [c, d]] means a and b have the same type, and c and
  /// d have the same type too. b/c and a/d don't have to have the same type,
  /// though.
  using TypeEquivalenceClasses = EquivalenceClasses<StringRef>;

  /// \returns true for `OPERAND_GENERIC_` 0 through 5.
  /// These are the MCOI types that can be registers. The other MCOI types are
  /// either immediates, or fancier operands used only post-ISel, so we don't
  /// care about them for combiners.
  static bool canMCOIOperandTypeBeARegister(StringRef MCOIType) {
    // Assume OPERAND_GENERIC_0 through 5 can be registers. The other MCOI
    // OperandTypes are either never used in gMIR, or not relevant (e.g.
    // OPERAND_GENERIC_IMM, which is definitely never a register).
    return MCOIType.drop_back(1).ends_with("OPERAND_GENERIC_");
  }

  /// Finds the "MCOI::"" operand types for each operand of \p CGP.
  ///
  /// This is a bit trickier than it looks because we need to handle variadic
  /// in/outs.
  ///
  /// e.g. for
  ///   (G_BUILD_VECTOR $vec, $x, $y) ->
  ///   [MCOI::OPERAND_GENERIC_0, MCOI::OPERAND_GENERIC_1,
  ///    MCOI::OPERAND_GENERIC_1]
  ///
  /// For unknown types (which can happen in variadics where varargs types are
  /// inconsistent), a unique name is given, e.g. "unknown_type_0".
  static std::vector<std::string>
  getMCOIOperandTypes(const CodeGenInstructionPattern &CGP);

  /// Adds the TypeEquivalenceClasses for \p P in \p OutTECs.
  void getInstEqClasses(const InstructionPattern &P,
                        TypeEquivalenceClasses &OutTECs) const;

  /// Calls `getInstEqClasses` on all patterns of the rule to produce the whole
  /// rule's TypeEquivalenceClasses.
  TypeEquivalenceClasses getRuleEqClasses() const;

  /// Tries to infer the type of the \p ImmOpIdx -th operand of \p IP using \p
  /// TECs.
  ///
  /// This is achieved by trying to find a named operand in \p IP that shares
  /// the same type as \p ImmOpIdx, and using \ref inferNamedOperandType on that
  /// operand instead.
  ///
  /// \returns the inferred type or an empty PatternType if inference didn't
  /// succeed.
  PatternType inferImmediateType(const InstructionPattern &IP,
                                 unsigned ImmOpIdx,
                                 const TypeEquivalenceClasses &TECs) const;

  /// Looks inside \p TECs to infer \p OpName's type.
  ///
  /// \returns the inferred type or an empty PatternType if inference didn't
  /// succeed.
  PatternType inferNamedOperandType(const InstructionPattern &IP,
                                    StringRef OpName,
                                    const TypeEquivalenceClasses &TECs,
                                    bool AllowSelf = false) const;

  const Record &RuleDef;
  SmallVector<InstructionPattern *, 8> MatchPats;
  SmallVector<InstructionPattern *, 8> ApplyPats;

  const OperandTable &MatchOpTable;
};

bool CombineRuleOperandTypeChecker::processMatchPattern(InstructionPattern &P) {
  MatchPats.push_back(&P);
  return check(P, /*CheckTypeOf*/ [](const auto &) {
    // GITypeOf in 'match' is currently always rejected by the
    // CombineRuleBuilder after inference is done.
    return true;
  });
}

bool CombineRuleOperandTypeChecker::processApplyPattern(InstructionPattern &P) {
  ApplyPats.push_back(&P);
  return check(P, /*CheckTypeOf*/ [&](const PatternType &Ty) {
    // GITypeOf<"$x"> can only be used if "$x" is a matched operand.
    const auto OpName = Ty.getTypeOfOpName();
    if (MatchOpTable.lookup(OpName).Found)
      return true;

    PrintError(RuleDef.getLoc(), "'" + OpName + "' ('" + Ty.str() +
                                     "') does not refer to a matched operand!");
    return false;
  });
}

void CombineRuleOperandTypeChecker::propagateAndInferTypes() {
  /// First step here is to propagate types using the OperandTypeChecker. That
  /// way we ensure all uses of a given register have consistent types.
  propagateTypes();

  /// Build the TypeEquivalenceClasses for the whole rule.
  const TypeEquivalenceClasses TECs = getRuleEqClasses();

  /// Look at the apply patterns and find operands that need to be
  /// inferred. We then try to find an equivalence class that they're a part of
  /// and select the best operand to use for the `GITypeOf` type. We prioritize
  /// defs of matched instructions because those are guaranteed to be registers.
  bool InferredAny = false;
  for (auto *Pat : ApplyPats) {
    for (unsigned K = 0; K < Pat->operands_size(); ++K) {
      auto &Op = Pat->getOperand(K);

      // We only want to take a look at untyped defs or immediates.
      if ((!Op.isDef() && !Op.hasImmValue()) || Op.getType())
        continue;

      // Infer defs & named immediates.
      if (Op.isDef() || Op.isNamedImmediate()) {
        // Check it's not a redefinition of a matched operand.
        // In such cases, inference is not necessary because we just copy
        // operands and don't create temporary registers.
        if (MatchOpTable.lookup(Op.getOperandName()).Found)
          continue;

        // Inference is needed here, so try to do it.
        if (PatternType Ty =
                inferNamedOperandType(*Pat, Op.getOperandName(), TECs)) {
          if (DebugTypeInfer)
            errs() << "INFER: " << Op.describe() << " -> " << Ty.str() << '\n';
          Op.setType(Ty);
          InferredAny = true;
        }

        continue;
      }

      // Infer immediates
      if (Op.hasImmValue()) {
        if (PatternType Ty = inferImmediateType(*Pat, K, TECs)) {
          if (DebugTypeInfer)
            errs() << "INFER: " << Op.describe() << " -> " << Ty.str() << '\n';
          Op.setType(Ty);
          InferredAny = true;
        }
        continue;
      }
    }
  }

  // If we've inferred any types, we want to propagate them across the apply
  // patterns. Type inference only adds GITypeOf types that point to Matched
  // operands, so we definitely don't want to propagate types into the match
  // patterns as well, otherwise bad things happen.
  if (InferredAny) {
    OperandTypeChecker OTC(RuleDef.getLoc());
    for (auto *Pat : ApplyPats) {
      if (!OTC.check(*Pat, [&](const auto &) { return true; }))
        PrintFatalError(RuleDef.getLoc(),
                        "OperandTypeChecker unexpectedly failed on '" +
                            Pat->getName() + "' during Type Inference");
    }
    OTC.propagateTypes();

    if (DebugTypeInfer) {
      errs() << "Apply patterns for rule " << RuleDef.getName()
             << " after inference:\n";
      for (auto *Pat : ApplyPats) {
        errs() << "  ";
        Pat->print(errs(), /*PrintName*/ true);
        errs() << '\n';
      }
      errs() << '\n';
    }
  }
}

PatternType CombineRuleOperandTypeChecker::inferImmediateType(
    const InstructionPattern &IP, unsigned ImmOpIdx,
    const TypeEquivalenceClasses &TECs) const {
  // We can only infer CGPs.
  const auto *CGP = dyn_cast<CodeGenInstructionPattern>(&IP);
  if (!CGP)
    return {};

  // For CGPs, we try to infer immediates by trying to infer another named
  // operand that shares its type.
  //
  // e.g.
  //    Pattern: G_BUILD_VECTOR $x, $y, 0
  //    MCOIs:   [MCOI::OPERAND_GENERIC_0, MCOI::OPERAND_GENERIC_1,
  //              MCOI::OPERAND_GENERIC_1]
  //    $y has the same type as 0, so we can infer $y and get the type 0 should
  //    have.

  // We infer immediates by looking for a named operand that shares the same
  // MCOI type.
  const auto MCOITypes = getMCOIOperandTypes(*CGP);
  StringRef ImmOpTy = MCOITypes[ImmOpIdx];

  for (const auto &[Idx, Ty] : enumerate(MCOITypes)) {
    if (Idx != ImmOpIdx && Ty == ImmOpTy) {
      const auto &Op = IP.getOperand(Idx);
      if (!Op.isNamedOperand())
        continue;

      // Named operand with the same name, try to infer that.
      if (PatternType InferTy = inferNamedOperandType(IP, Op.getOperandName(),
                                                      TECs, /*AllowSelf=*/true))
        return InferTy;
    }
  }

  return {};
}

PatternType CombineRuleOperandTypeChecker::inferNamedOperandType(
    const InstructionPattern &IP, StringRef OpName,
    const TypeEquivalenceClasses &TECs, bool AllowSelf) const {
  // This is the simplest possible case, we just need to find a TEC that
  // contains OpName. Look at all operands in equivalence class and try to
  // find a suitable one. If `AllowSelf` is true, the operand itself is also
  // considered suitable.

  // Check for a def of a matched pattern. This is guaranteed to always
  // be a register so we can blindly use that.
  StringRef GoodOpName;
  for (auto It = TECs.findLeader(OpName); It != TECs.member_end(); ++It) {
    if (!AllowSelf && *It == OpName)
      continue;

    const auto LookupRes = MatchOpTable.lookup(*It);
    if (LookupRes.Def) // Favor defs
      return PatternType::getTypeOf(*It);

    // Otherwise just save this in case we don't find any def.
    if (GoodOpName.empty() && LookupRes.Found)
      GoodOpName = *It;
  }

  if (!GoodOpName.empty())
    return PatternType::getTypeOf(GoodOpName);

  // No good operand found, give up.
  return {};
}

std::vector<std::string> CombineRuleOperandTypeChecker::getMCOIOperandTypes(
    const CodeGenInstructionPattern &CGP) {
  // FIXME?: Should we cache this? We call it twice when inferring immediates.

  static unsigned UnknownTypeIdx = 0;

  std::vector<std::string> OpTypes;
  auto &CGI = CGP.getInst();
  Record *VarArgsTy = CGI.TheDef->isSubClassOf("GenericInstruction")
                          ? CGI.TheDef->getValueAsOptionalDef("variadicOpsType")
                          : nullptr;
  std::string VarArgsTyName =
      VarArgsTy ? ("MCOI::" + VarArgsTy->getValueAsString("OperandType")).str()
                : ("unknown_type_" + Twine(UnknownTypeIdx++)).str();

  // First, handle defs.
  for (unsigned K = 0; K < CGI.Operands.NumDefs; ++K)
    OpTypes.push_back(CGI.Operands[K].OperandType);

  // Then, handle variadic defs if there are any.
  if (CGP.hasVariadicDefs()) {
    for (unsigned K = CGI.Operands.NumDefs; K < CGP.getNumInstDefs(); ++K)
      OpTypes.push_back(VarArgsTyName);
  }

  // If we had variadic defs, the op idx in the pattern won't match the op idx
  // in the CGI anymore.
  int CGIOpOffset = int(CGI.Operands.NumDefs) - CGP.getNumInstDefs();
  assert(CGP.hasVariadicDefs() ? (CGIOpOffset <= 0) : (CGIOpOffset == 0));

  // Handle all remaining use operands, including variadic ones.
  for (unsigned K = CGP.getNumInstDefs(); K < CGP.getNumInstOperands(); ++K) {
    unsigned CGIOpIdx = K + CGIOpOffset;
    if (CGIOpIdx >= CGI.Operands.size()) {
      assert(CGP.isVariadic());
      OpTypes.push_back(VarArgsTyName);
    } else {
      OpTypes.push_back(CGI.Operands[CGIOpIdx].OperandType);
    }
  }

  assert(OpTypes.size() == CGP.operands_size());
  return OpTypes;
}

void CombineRuleOperandTypeChecker::getInstEqClasses(
    const InstructionPattern &P, TypeEquivalenceClasses &OutTECs) const {
  // Determine the TypeEquivalenceClasses by:
  //    - Getting the MCOI Operand Types.
  //    - Creating a Map of MCOI Type -> [Operand Indexes]
  //    - Iterating over the map, filtering types we don't like, and just adding
  //      the array of Operand Indexes to \p OutTECs.

  // We can only do this on CodeGenInstructions. Other InstructionPatterns have
  // no type inference information associated with them.
  // TODO: Could we add some inference information to builtins at least? e.g.
  // ReplaceReg should always replace with a reg of the same type, for instance.
  // Though, those patterns are often used alone so it might not be worth the
  // trouble to infer their types.
  auto *CGP = dyn_cast<CodeGenInstructionPattern>(&P);
  if (!CGP)
    return;

  const auto MCOITypes = getMCOIOperandTypes(*CGP);
  assert(MCOITypes.size() == P.operands_size());

  DenseMap<StringRef, std::vector<unsigned>> TyToOpIdx;
  for (const auto &[Idx, Ty] : enumerate(MCOITypes))
    TyToOpIdx[Ty].push_back(Idx);

  if (DebugTypeInfer)
    errs() << "\tGroups for " << P.getName() << ":\t";

  for (const auto &[Ty, Idxs] : TyToOpIdx) {
    if (!canMCOIOperandTypeBeARegister(Ty))
      continue;

    if (DebugTypeInfer)
      errs() << '[';
    StringRef Sep = "";

    // We only collect named operands.
    StringRef Leader;
    for (unsigned Idx : Idxs) {
      const auto &Op = P.getOperand(Idx);
      if (!Op.isNamedOperand())
        continue;

      const auto OpName = Op.getOperandName();
      if (DebugTypeInfer) {
        errs() << Sep << OpName;
        Sep = ", ";
      }

      if (Leader.empty())
        OutTECs.insert((Leader = OpName));
      else
        OutTECs.unionSets(Leader, OpName);
    }

    if (DebugTypeInfer)
      errs() << "] ";
  }

  if (DebugTypeInfer)
    errs() << '\n';
}

CombineRuleOperandTypeChecker::TypeEquivalenceClasses
CombineRuleOperandTypeChecker::getRuleEqClasses() const {
  StringMap<unsigned> OpNameToEqClassIdx;
  TypeEquivalenceClasses TECs;

  if (DebugTypeInfer)
    errs() << "Rule Operand Type Equivalence Classes for " << RuleDef.getName()
           << ":\n";

  for (const auto *Pat : MatchPats)
    getInstEqClasses(*Pat, TECs);
  for (const auto *Pat : ApplyPats)
    getInstEqClasses(*Pat, TECs);

  if (DebugTypeInfer) {
    errs() << "Final Type Equivalence Classes: ";
    for (auto ClassIt = TECs.begin(); ClassIt != TECs.end(); ++ClassIt) {
      // only print non-empty classes.
      if (auto MembIt = TECs.member_begin(ClassIt);
          MembIt != TECs.member_end()) {
        errs() << '[';
        StringRef Sep = "";
        for (; MembIt != TECs.member_end(); ++MembIt) {
          errs() << Sep << *MembIt;
          Sep = ", ";
        }
        errs() << "] ";
      }
    }
    errs() << '\n';
  }

  return TECs;
}

//===- CombineRuleBuilder -------------------------------------------------===//

/// Parses combine rule and builds a small intermediate representation to tie
/// patterns together and emit RuleMatchers to match them. This may emit more
/// than one RuleMatcher, e.g. for `wip_match_opcode`.
///
/// Memory management for `Pattern` objects is done through `std::unique_ptr`.
/// In most cases, there are two stages to a pattern's lifetime:
///   - Creation in a `parse` function
///     - The unique_ptr is stored in a variable, and may be destroyed if the
///       pattern is found to be semantically invalid.
///   - Ownership transfer into a `PatternMap`
///     - Once a pattern is moved into either the map of Match or Apply
///       patterns, it is known to be valid and it never moves back.
class CombineRuleBuilder {
public:
  using PatternMap = MapVector<StringRef, std::unique_ptr<Pattern>>;
  using PatternAlternatives = DenseMap<const Pattern *, unsigned>;

  CombineRuleBuilder(const CodeGenTarget &CGT,
                     SubtargetFeatureInfoMap &SubtargetFeatures,
                     Record &RuleDef, unsigned ID,
                     std::vector<RuleMatcher> &OutRMs)
      : CGT(CGT), SubtargetFeatures(SubtargetFeatures), RuleDef(RuleDef),
        RuleID(ID), OutRMs(OutRMs) {}

  /// Parses all fields in the RuleDef record.
  bool parseAll();

  /// Emits all RuleMatchers into the vector of RuleMatchers passed in the
  /// constructor.
  bool emitRuleMatchers();

  void print(raw_ostream &OS) const;
  void dump() const { print(dbgs()); }

  /// Debug-only verification of invariants.
#ifndef NDEBUG
  void verify() const;
#endif

private:
  const CodeGenInstruction &getGConstant() const {
    return CGT.getInstruction(RuleDef.getRecords().getDef("G_CONSTANT"));
  }

  void PrintError(Twine Msg) const { ::PrintError(&RuleDef, Msg); }
  void PrintWarning(Twine Msg) const { ::PrintWarning(RuleDef.getLoc(), Msg); }
  void PrintNote(Twine Msg) const { ::PrintNote(RuleDef.getLoc(), Msg); }

  void print(raw_ostream &OS, const PatternAlternatives &Alts) const;

  bool addApplyPattern(std::unique_ptr<Pattern> Pat);
  bool addMatchPattern(std::unique_ptr<Pattern> Pat);

  /// Adds the expansions from \see MatchDatas to \p CE.
  void declareAllMatchDatasExpansions(CodeExpansions &CE) const;

  /// Adds a matcher \p P to \p IM, expanding its code using \p CE.
  /// Note that the predicate is added on the last InstructionMatcher.
  ///
  /// \p Alts is only used if DebugCXXPreds is enabled.
  void addCXXPredicate(RuleMatcher &M, const CodeExpansions &CE,
                       const CXXPattern &P, const PatternAlternatives &Alts);

  /// Adds an apply \p P to \p IM, expanding its code using \p CE.
  void addCXXAction(RuleMatcher &M, const CodeExpansions &CE,
                    const CXXPattern &P);

  bool hasOnlyCXXApplyPatterns() const;
  bool hasEraseRoot() const;

  // Infer machine operand types and check their consistency.
  bool typecheckPatterns();

  /// For all PatFragPatterns, add a new entry in PatternAlternatives for each
  /// PatternList it contains. This is multiplicative, so if we have 2
  /// PatFrags with 3 alternatives each, we get 2*3 permutations added to
  /// PermutationsToEmit. The "MaxPermutations" field controls how many
  /// permutations are allowed before an error is emitted and this function
  /// returns false. This is a simple safeguard to prevent combination of
  /// PatFrags from generating enormous amounts of rules.
  bool buildPermutationsToEmit();

  /// Checks additional semantics of the Patterns.
  bool checkSemantics();

  /// Creates a new RuleMatcher with some boilerplate
  /// settings/actions/predicates, and and adds it to \p OutRMs.
  /// \see addFeaturePredicates too.
  ///
  /// \param Alts Current set of alternatives, for debug comment.
  /// \param AdditionalComment Comment string to be added to the
  ///        `DebugCommentAction`.
  RuleMatcher &addRuleMatcher(const PatternAlternatives &Alts,
                              Twine AdditionalComment = "");
  bool addFeaturePredicates(RuleMatcher &M);

  bool findRoots();
  bool buildRuleOperandsTable();

  bool parseDefs(const DagInit &Def);
  bool
  parsePatternList(const DagInit &List,
                   function_ref<bool(std::unique_ptr<Pattern>)> ParseAction,
                   StringRef Operator, ArrayRef<SMLoc> DiagLoc,
                   StringRef AnonPatNamePrefix) const;

  std::unique_ptr<Pattern> parseInstructionPattern(const Init &Arg,
                                                   StringRef PatName) const;
  std::unique_ptr<Pattern> parseWipMatchOpcodeMatcher(const Init &Arg,
                                                      StringRef PatName) const;
  bool parseInstructionPatternOperand(InstructionPattern &IP,
                                      const Init *OpInit,
                                      const StringInit *OpName) const;
  bool parseInstructionPatternMIFlags(InstructionPattern &IP,
                                      const DagInit *Op) const;
  std::unique_ptr<PatFrag> parsePatFragImpl(const Record *Def) const;
  bool parsePatFragParamList(
      ArrayRef<SMLoc> DiagLoc, const DagInit &OpsList,
      function_ref<bool(StringRef, PatFrag::ParamKind)> ParseAction) const;
  const PatFrag *parsePatFrag(const Record *Def) const;

  bool emitMatchPattern(CodeExpansions &CE, const PatternAlternatives &Alts,
                        const InstructionPattern &IP);
  bool emitMatchPattern(CodeExpansions &CE, const PatternAlternatives &Alts,
                        const AnyOpcodePattern &AOP);

  bool emitPatFragMatchPattern(CodeExpansions &CE,
                               const PatternAlternatives &Alts, RuleMatcher &RM,
                               InstructionMatcher *IM,
                               const PatFragPattern &PFP,
                               DenseSet<const Pattern *> &SeenPats);

  bool emitApplyPatterns(CodeExpansions &CE, RuleMatcher &M);

  // Recursively visits InstructionPatterns from P to build up the
  // RuleMatcher actions.
  bool emitInstructionApplyPattern(CodeExpansions &CE, RuleMatcher &M,
                                   const InstructionPattern &P,
                                   DenseSet<const Pattern *> &SeenPats,
                                   StringMap<unsigned> &OperandToTempRegID);

  bool emitCodeGenInstructionApplyImmOperand(RuleMatcher &M,
                                             BuildMIAction &DstMI,
                                             const CodeGenInstructionPattern &P,
                                             const InstructionOperand &O);

  bool emitBuiltinApplyPattern(CodeExpansions &CE, RuleMatcher &M,
                               const BuiltinPattern &P,
                               StringMap<unsigned> &OperandToTempRegID);

  // Recursively visits CodeGenInstructionPattern from P to build up the
  // RuleMatcher/InstructionMatcher. May create new InstructionMatchers as
  // needed.
  using OperandMapperFnRef =
      function_ref<InstructionOperand(const InstructionOperand &)>;
  using OperandDefLookupFn =
      function_ref<const InstructionPattern *(StringRef)>;
  bool emitCodeGenInstructionMatchPattern(
      CodeExpansions &CE, const PatternAlternatives &Alts, RuleMatcher &M,
      InstructionMatcher &IM, const CodeGenInstructionPattern &P,
      DenseSet<const Pattern *> &SeenPats, OperandDefLookupFn LookupOperandDef,
      OperandMapperFnRef OperandMapper = [](const auto &O) { return O; });

  const CodeGenTarget &CGT;
  SubtargetFeatureInfoMap &SubtargetFeatures;
  Record &RuleDef;
  const unsigned RuleID;
  std::vector<RuleMatcher> &OutRMs;

  // For InstructionMatcher::addOperand
  unsigned AllocatedTemporariesBaseID = 0;

  /// The root of the pattern.
  StringRef RootName;

  /// These maps have ownership of the actual Pattern objects.
  /// They both map a Pattern's name to the Pattern instance.
  PatternMap MatchPats;
  PatternMap ApplyPats;

  /// Operand tables to tie match/apply patterns together.
  OperandTable MatchOpTable;
  OperandTable ApplyOpTable;

  /// Set by findRoots.
  Pattern *MatchRoot = nullptr;
  SmallDenseSet<InstructionPattern *, 2> ApplyRoots;

  SmallVector<MatchDataInfo, 2> MatchDatas;
  SmallVector<PatternAlternatives, 1> PermutationsToEmit;

  // print()/debug-only members.
  mutable SmallPtrSet<const PatFrag *, 2> SeenPatFrags;
};

bool CombineRuleBuilder::parseAll() {
  auto StackTrace = PrettyStackTraceParse(RuleDef);

  if (!parseDefs(*RuleDef.getValueAsDag("Defs")))
    return false;

  if (!parsePatternList(
          *RuleDef.getValueAsDag("Match"),
          [this](auto Pat) { return addMatchPattern(std::move(Pat)); }, "match",
          RuleDef.getLoc(), (RuleDef.getName() + "_match").str()))
    return false;

  if (!parsePatternList(
          *RuleDef.getValueAsDag("Apply"),
          [this](auto Pat) { return addApplyPattern(std::move(Pat)); }, "apply",
          RuleDef.getLoc(), (RuleDef.getName() + "_apply").str()))
    return false;

  if (!buildRuleOperandsTable() || !typecheckPatterns() || !findRoots() ||
      !checkSemantics() || !buildPermutationsToEmit())
    return false;
  LLVM_DEBUG(verify());
  return true;
}

bool CombineRuleBuilder::emitRuleMatchers() {
  auto StackTrace = PrettyStackTraceEmit(RuleDef);

  assert(MatchRoot);
  CodeExpansions CE;
  declareAllMatchDatasExpansions(CE);

  assert(!PermutationsToEmit.empty());
  for (const auto &Alts : PermutationsToEmit) {
    switch (MatchRoot->getKind()) {
    case Pattern::K_AnyOpcode: {
      if (!emitMatchPattern(CE, Alts, *cast<AnyOpcodePattern>(MatchRoot)))
        return false;
      break;
    }
    case Pattern::K_PatFrag:
    case Pattern::K_Builtin:
    case Pattern::K_CodeGenInstruction:
      if (!emitMatchPattern(CE, Alts, *cast<InstructionPattern>(MatchRoot)))
        return false;
      break;
    case Pattern::K_CXX:
      PrintError("C++ code cannot be the root of a rule!");
      return false;
    default:
      llvm_unreachable("unknown pattern kind!");
    }
  }

  return true;
}

void CombineRuleBuilder::print(raw_ostream &OS) const {
  OS << "(CombineRule name:" << RuleDef.getName() << " id:" << RuleID
     << " root:" << RootName << '\n';

  if (!MatchDatas.empty()) {
    OS << "  (MatchDatas\n";
    for (const auto &MD : MatchDatas) {
      OS << "    ";
      MD.print(OS);
      OS << '\n';
    }
    OS << "  )\n";
  }

  if (!SeenPatFrags.empty()) {
    OS << "  (PatFrags\n";
    for (const auto *PF : SeenPatFrags) {
      PF->print(OS, /*Indent=*/"    ");
      OS << '\n';
    }
    OS << "  )\n";
  }

  const auto DumpPats = [&](StringRef Name, const PatternMap &Pats) {
    OS << "  (" << Name << " ";
    if (Pats.empty()) {
      OS << "<empty>)\n";
      return;
    }

    OS << '\n';
    for (const auto &[Name, Pat] : Pats) {
      OS << "    ";
      if (Pat.get() == MatchRoot)
        OS << "<match_root>";
      if (isa<InstructionPattern>(Pat.get()) &&
          ApplyRoots.contains(cast<InstructionPattern>(Pat.get())))
        OS << "<apply_root>";
      OS << Name << ":";
      Pat->print(OS, /*PrintName=*/false);
      OS << '\n';
    }
    OS << "  )\n";
  };

  DumpPats("MatchPats", MatchPats);
  DumpPats("ApplyPats", ApplyPats);

  MatchOpTable.print(OS, "MatchPats", /*Indent*/ "  ");
  ApplyOpTable.print(OS, "ApplyPats", /*Indent*/ "  ");

  if (PermutationsToEmit.size() > 1) {
    OS << "  (PermutationsToEmit\n";
    for (const auto &Perm : PermutationsToEmit) {
      OS << "    ";
      print(OS, Perm);
      OS << ",\n";
    }
    OS << "  )\n";
  }

  OS << ")\n";
}

#ifndef NDEBUG
void CombineRuleBuilder::verify() const {
  const auto VerifyPats = [&](const PatternMap &Pats) {
    for (const auto &[Name, Pat] : Pats) {
      if (!Pat)
        PrintFatalError("null pattern in pattern map!");

      if (Name != Pat->getName()) {
        Pat->dump();
        PrintFatalError("Pattern name mismatch! Map name: " + Name +
                        ", Pat name: " + Pat->getName());
      }

      // Sanity check: the map should point to the same data as the Pattern.
      // Both strings are allocated in the pool using insertStrRef.
      if (Name.data() != Pat->getName().data()) {
        dbgs() << "Map StringRef: '" << Name << "' @ "
               << (const void *)Name.data() << '\n';
        dbgs() << "Pat String: '" << Pat->getName() << "' @ "
               << (const void *)Pat->getName().data() << '\n';
        PrintFatalError("StringRef stored in the PatternMap is not referencing "
                        "the same string as its Pattern!");
      }
    }
  };

  VerifyPats(MatchPats);
  VerifyPats(ApplyPats);

  // Check there are no wip_match_opcode patterns in the "apply" patterns.
  if (any_of(ApplyPats,
             [&](auto &E) { return isa<AnyOpcodePattern>(E.second.get()); })) {
    dump();
    PrintFatalError(
        "illegal wip_match_opcode pattern in the 'apply' patterns!");
  }

  // Check there are no nullptrs in ApplyRoots.
  if (ApplyRoots.contains(nullptr)) {
    PrintFatalError(
        "CombineRuleBuilder's ApplyRoots set contains a null pointer!");
  }
}
#endif

void CombineRuleBuilder::print(raw_ostream &OS,
                               const PatternAlternatives &Alts) const {
  SmallVector<std::string, 1> Strings(
      map_range(Alts, [](const auto &PatAndPerm) {
        return PatAndPerm.first->getName().str() + "[" +
               to_string(PatAndPerm.second) + "]";
      }));
  // Sort so output is deterministic for tests. Otherwise it's sorted by pointer
  // values.
  sort(Strings);
  OS << "[" << join(Strings, ", ") << "]";
}

bool CombineRuleBuilder::addApplyPattern(std::unique_ptr<Pattern> Pat) {
  StringRef Name = Pat->getName();
  if (ApplyPats.contains(Name)) {
    PrintError("'" + Name + "' apply pattern defined more than once!");
    return false;
  }

  if (isa<AnyOpcodePattern>(Pat.get())) {
    PrintError("'" + Name +
               "': wip_match_opcode is not supported in apply patterns");
    return false;
  }

  if (isa<PatFragPattern>(Pat.get())) {
    PrintError("'" + Name + "': using " + PatFrag::ClassName +
               " is not supported in apply patterns");
    return false;
  }

  if (auto *CXXPat = dyn_cast<CXXPattern>(Pat.get()))
    CXXPat->setIsApply();

  ApplyPats[Name] = std::move(Pat);
  return true;
}

bool CombineRuleBuilder::addMatchPattern(std::unique_ptr<Pattern> Pat) {
  StringRef Name = Pat->getName();
  if (MatchPats.contains(Name)) {
    PrintError("'" + Name + "' match pattern defined more than once!");
    return false;
  }

  // For now, none of the builtins can appear in 'match'.
  if (const auto *BP = dyn_cast<BuiltinPattern>(Pat.get())) {
    PrintError("'" + BP->getInstName() +
               "' cannot be used in a 'match' pattern");
    return false;
  }

  MatchPats[Name] = std::move(Pat);
  return true;
}

void CombineRuleBuilder::declareAllMatchDatasExpansions(
    CodeExpansions &CE) const {
  for (const auto &MD : MatchDatas)
    CE.declare(MD.getPatternSymbol(), MD.getQualifiedVariableName());
}

void CombineRuleBuilder::addCXXPredicate(RuleMatcher &M,
                                         const CodeExpansions &CE,
                                         const CXXPattern &P,
                                         const PatternAlternatives &Alts) {
  // FIXME: Hack so C++ code is executed last. May not work for more complex
  // patterns.
  auto &IM = *std::prev(M.insnmatchers().end());
  auto Loc = RuleDef.getLoc();
  const auto AddComment = [&](raw_ostream &OS) {
    OS << "// Pattern Alternatives: ";
    print(OS, Alts);
    OS << '\n';
  };
  const auto &ExpandedCode =
      DebugCXXPreds ? P.expandCode(CE, Loc, AddComment) : P.expandCode(CE, Loc);
  IM->addPredicate<GenericInstructionPredicateMatcher>(
      ExpandedCode.getEnumNameWithPrefix(CXXPredPrefix));
}

void CombineRuleBuilder::addCXXAction(RuleMatcher &M, const CodeExpansions &CE,
                                      const CXXPattern &P) {
  const auto &ExpandedCode = P.expandCode(CE, RuleDef.getLoc());
  M.addAction<CustomCXXAction>(
      ExpandedCode.getEnumNameWithPrefix(CXXApplyPrefix));
}

bool CombineRuleBuilder::hasOnlyCXXApplyPatterns() const {
  return all_of(ApplyPats, [&](auto &Entry) {
    return isa<CXXPattern>(Entry.second.get());
  });
}

bool CombineRuleBuilder::hasEraseRoot() const {
  return any_of(ApplyPats, [&](auto &Entry) {
    if (const auto *BP = dyn_cast<BuiltinPattern>(Entry.second.get()))
      return BP->getBuiltinKind() == BI_EraseRoot;
    return false;
  });
}

bool CombineRuleBuilder::typecheckPatterns() {
  CombineRuleOperandTypeChecker OTC(RuleDef, MatchOpTable);

  for (auto &Pat : values(MatchPats)) {
    if (auto *IP = dyn_cast<InstructionPattern>(Pat.get())) {
      if (!OTC.processMatchPattern(*IP))
        return false;
    }
  }

  for (auto &Pat : values(ApplyPats)) {
    if (auto *IP = dyn_cast<InstructionPattern>(Pat.get())) {
      if (!OTC.processApplyPattern(*IP))
        return false;
    }
  }

  OTC.propagateAndInferTypes();

  // Always check this after in case inference adds some special types to the
  // match patterns.
  for (auto &Pat : values(MatchPats)) {
    if (auto *IP = dyn_cast<InstructionPattern>(Pat.get())) {
      if (IP->diagnoseAllSpecialTypes(
              RuleDef.getLoc(), PatternType::SpecialTyClassName +
                                    " is not supported in 'match' patterns")) {
        return false;
      }
    }
  }
  return true;
}

bool CombineRuleBuilder::buildPermutationsToEmit() {
  PermutationsToEmit.clear();

  // Start with one empty set of alternatives.
  PermutationsToEmit.emplace_back();
  for (const auto &Pat : values(MatchPats)) {
    unsigned NumAlts = 0;
    // Note: technically, AnyOpcodePattern also needs permutations, but:
    //    - We only allow a single one of them in the root.
    //    - They cannot be mixed with any other pattern other than C++ code.
    // So we don't really need to take them into account here. We could, but
    // that pattern is a hack anyway and the less it's involved, the better.
    if (const auto *PFP = dyn_cast<PatFragPattern>(Pat.get()))
      NumAlts = PFP->getPatFrag().num_alternatives();
    else
      continue;

    // For each pattern that needs permutations, multiply the current set of
    // alternatives.
    auto CurPerms = PermutationsToEmit;
    PermutationsToEmit.clear();

    for (const auto &Perm : CurPerms) {
      assert(!Perm.count(Pat.get()) && "Pattern already emitted?");
      for (unsigned K = 0; K < NumAlts; ++K) {
        PatternAlternatives NewPerm = Perm;
        NewPerm[Pat.get()] = K;
        PermutationsToEmit.emplace_back(std::move(NewPerm));
      }
    }
  }

  if (int64_t MaxPerms = RuleDef.getValueAsInt("MaxPermutations");
      MaxPerms > 0) {
    if ((int64_t)PermutationsToEmit.size() > MaxPerms) {
      PrintError("cannot emit rule '" + RuleDef.getName() + "'; " +
                 Twine(PermutationsToEmit.size()) +
                 " permutations would be emitted, but the max is " +
                 Twine(MaxPerms));
      return false;
    }
  }

  // Ensure we always have a single empty entry, it simplifies the emission
  // logic so it doesn't need to handle the case where there are no perms.
  if (PermutationsToEmit.empty()) {
    PermutationsToEmit.emplace_back();
    return true;
  }

  return true;
}

bool CombineRuleBuilder::checkSemantics() {
  assert(MatchRoot && "Cannot call this before findRoots()");

  bool UsesWipMatchOpcode = false;
  for (const auto &Match : MatchPats) {
    const auto *Pat = Match.second.get();

    if (const auto *CXXPat = dyn_cast<CXXPattern>(Pat)) {
      if (!CXXPat->getRawCode().contains("return "))
        PrintWarning("'match' C++ code does not seem to return!");
      continue;
    }

    // MIFlags in match cannot use the following syntax: (MIFlags $mi)
    if (const auto *CGP = dyn_cast<CodeGenInstructionPattern>(Pat)) {
      if (auto *FI = CGP->getMIFlagsInfo()) {
        if (!FI->copy_flags().empty()) {
          PrintError(
              "'match' patterns cannot refer to flags from other instructions");
          PrintNote("MIFlags in '" + CGP->getName() +
                    "' refer to: " + join(FI->copy_flags(), ", "));
          return false;
        }
      }
    }

    const auto *AOP = dyn_cast<AnyOpcodePattern>(Pat);
    if (!AOP)
      continue;

    if (UsesWipMatchOpcode) {
      PrintError("wip_opcode_match can only be present once");
      return false;
    }

    UsesWipMatchOpcode = true;
  }

  for (const auto &Apply : ApplyPats) {
    assert(Apply.second.get());
    const auto *IP = dyn_cast<InstructionPattern>(Apply.second.get());
    if (!IP)
      continue;

    if (UsesWipMatchOpcode) {
      PrintError("cannot use wip_match_opcode in combination with apply "
                 "instruction patterns!");
      return false;
    }

    // Check that the insts mentioned in copy_flags exist.
    if (const auto *CGP = dyn_cast<CodeGenInstructionPattern>(IP)) {
      if (auto *FI = CGP->getMIFlagsInfo()) {
        for (auto InstName : FI->copy_flags()) {
          auto It = MatchPats.find(InstName);
          if (It == MatchPats.end()) {
            PrintError("unknown instruction '$" + InstName +
                       "' referenced in MIFlags of '" + CGP->getName() + "'");
            return false;
          }

          if (!isa<CodeGenInstructionPattern>(It->second.get())) {
            PrintError(
                "'$" + InstName +
                "' does not refer to a CodeGenInstruction in MIFlags of '" +
                CGP->getName() + "'");
            return false;
          }
        }
      }
    }

    const auto *BIP = dyn_cast<BuiltinPattern>(IP);
    if (!BIP)
      continue;
    StringRef Name = BIP->getInstName();

    // (GIEraseInst) has to be the only apply pattern, or it can not be used at
    // all. The root cannot have any defs either.
    switch (BIP->getBuiltinKind()) {
    case BI_EraseRoot: {
      if (ApplyPats.size() > 1) {
        PrintError(Name + " must be the only 'apply' pattern");
        return false;
      }

      const auto *IRoot = dyn_cast<CodeGenInstructionPattern>(MatchRoot);
      if (!IRoot) {
        PrintError(Name +
                   " can only be used if the root is a CodeGenInstruction");
        return false;
      }

      if (IRoot->getNumInstDefs() != 0) {
        PrintError(Name + " can only be used if on roots that do "
                          "not have any output operand");
        PrintNote("'" + IRoot->getInstName() + "' has " +
                  Twine(IRoot->getNumInstDefs()) + " output operands");
        return false;
      }
      break;
    }
    case BI_ReplaceReg: {
      // (GIReplaceReg can only be used on the root instruction)
      // TODO: When we allow rewriting non-root instructions, also allow this.
      StringRef OldRegName = BIP->getOperand(0).getOperandName();
      auto *Def = MatchOpTable.getDef(OldRegName);
      if (!Def) {
        PrintError(Name + " cannot find a matched pattern that defines '" +
                   OldRegName + "'");
        return false;
      }
      if (MatchOpTable.getDef(OldRegName) != MatchRoot) {
        PrintError(Name + " cannot replace '" + OldRegName +
                   "': this builtin can only replace a register defined by the "
                   "match root");
        return false;
      }
      break;
    }
    }
  }

  return true;
}

RuleMatcher &CombineRuleBuilder::addRuleMatcher(const PatternAlternatives &Alts,
                                                Twine AdditionalComment) {
  auto &RM = OutRMs.emplace_back(RuleDef.getLoc());
  addFeaturePredicates(RM);
  RM.setPermanentGISelFlags(GISF_IgnoreCopies);
  RM.addRequiredSimplePredicate(getIsEnabledPredicateEnumName(RuleID));

  std::string Comment;
  raw_string_ostream CommentOS(Comment);
  CommentOS << "Combiner Rule #" << RuleID << ": " << RuleDef.getName();
  if (!Alts.empty()) {
    CommentOS << " @ ";
    print(CommentOS, Alts);
  }
  if (!AdditionalComment.isTriviallyEmpty())
    CommentOS << "; " << AdditionalComment;
  RM.addAction<DebugCommentAction>(Comment);
  return RM;
}

bool CombineRuleBuilder::addFeaturePredicates(RuleMatcher &M) {
  if (!RuleDef.getValue("Predicates"))
    return true;

  ListInit *Preds = RuleDef.getValueAsListInit("Predicates");
  for (Init *PI : Preds->getValues()) {
    DefInit *Pred = dyn_cast<DefInit>(PI);
    if (!Pred)
      continue;

    Record *Def = Pred->getDef();
    if (!Def->isSubClassOf("Predicate")) {
      ::PrintError(Def, "Unknown 'Predicate' Type");
      return false;
    }

    if (Def->getValueAsString("CondString").empty())
      continue;

    if (SubtargetFeatures.count(Def) == 0) {
      SubtargetFeatures.emplace(
          Def, SubtargetFeatureInfo(Def, SubtargetFeatures.size()));
    }

    M.addRequiredFeature(Def);
  }

  return true;
}

bool CombineRuleBuilder::findRoots() {
  const auto Finish = [&]() {
    assert(MatchRoot);

    if (hasOnlyCXXApplyPatterns() || hasEraseRoot())
      return true;

    auto *IPRoot = dyn_cast<InstructionPattern>(MatchRoot);
    if (!IPRoot)
      return true;

    if (IPRoot->getNumInstDefs() == 0) {
      // No defs to work with -> find the root using the pattern name.
      auto It = ApplyPats.find(RootName);
      if (It == ApplyPats.end()) {
        PrintError("Cannot find root '" + RootName + "' in apply patterns!");
        return false;
      }

      auto *ApplyRoot = dyn_cast<InstructionPattern>(It->second.get());
      if (!ApplyRoot) {
        PrintError("apply pattern root '" + RootName +
                   "' must be an instruction pattern");
        return false;
      }

      ApplyRoots.insert(ApplyRoot);
      return true;
    }

    // Collect all redefinitions of the MatchRoot's defs and put them in
    // ApplyRoots.
    const auto DefsNeeded = IPRoot->getApplyDefsNeeded();
    for (auto &Op : DefsNeeded) {
      assert(Op.isDef() && Op.isNamedOperand());
      StringRef Name = Op.getOperandName();

      auto *ApplyRedef = ApplyOpTable.getDef(Name);
      if (!ApplyRedef) {
        PrintError("'" + Name + "' must be redefined in the 'apply' pattern");
        return false;
      }

      ApplyRoots.insert((InstructionPattern *)ApplyRedef);
    }

    if (auto It = ApplyPats.find(RootName); It != ApplyPats.end()) {
      if (find(ApplyRoots, It->second.get()) == ApplyRoots.end()) {
        PrintError("apply pattern '" + RootName +
                   "' is supposed to be a root but it does not redefine any of "
                   "the defs of the match root");
        return false;
      }
    }

    return true;
  };

  // Look by pattern name, e.g.
  //    (G_FNEG $x, $y):$root
  if (auto MatchPatIt = MatchPats.find(RootName);
      MatchPatIt != MatchPats.end()) {
    MatchRoot = MatchPatIt->second.get();
    return Finish();
  }

  // Look by def:
  //    (G_FNEG $root, $y)
  auto LookupRes = MatchOpTable.lookup(RootName);
  if (!LookupRes.Found) {
    PrintError("Cannot find root '" + RootName + "' in match patterns!");
    return false;
  }

  MatchRoot = LookupRes.Def;
  if (!MatchRoot) {
    PrintError("Cannot use live-in operand '" + RootName +
               "' as match pattern root!");
    return false;
  }

  return Finish();
}

bool CombineRuleBuilder::buildRuleOperandsTable() {
  const auto DiagnoseRedefMatch = [&](StringRef OpName) {
    PrintError("Operand '" + OpName +
               "' is defined multiple times in the 'match' patterns");
  };

  const auto DiagnoseRedefApply = [&](StringRef OpName) {
    PrintError("Operand '" + OpName +
               "' is defined multiple times in the 'apply' patterns");
  };

  for (auto &Pat : values(MatchPats)) {
    auto *IP = dyn_cast<InstructionPattern>(Pat.get());
    if (IP && !MatchOpTable.addPattern(IP, DiagnoseRedefMatch))
      return false;
  }

  for (auto &Pat : values(ApplyPats)) {
    auto *IP = dyn_cast<InstructionPattern>(Pat.get());
    if (IP && !ApplyOpTable.addPattern(IP, DiagnoseRedefApply))
      return false;
  }

  return true;
}

bool CombineRuleBuilder::parseDefs(const DagInit &Def) {
  if (Def.getOperatorAsDef(RuleDef.getLoc())->getName() != "defs") {
    PrintError("Expected defs operator");
    return false;
  }

  SmallVector<StringRef> Roots;
  for (unsigned I = 0, E = Def.getNumArgs(); I < E; ++I) {
    if (isSpecificDef(*Def.getArg(I), "root")) {
      Roots.emplace_back(Def.getArgNameStr(I));
      continue;
    }

    // Subclasses of GIDefMatchData should declare that this rule needs to pass
    // data from the match stage to the apply stage, and ensure that the
    // generated matcher has a suitable variable for it to do so.
    if (Record *MatchDataRec =
            getDefOfSubClass(*Def.getArg(I), "GIDefMatchData")) {
      MatchDatas.emplace_back(Def.getArgNameStr(I),
                              MatchDataRec->getValueAsString("Type"));
      continue;
    }

    // Otherwise emit an appropriate error message.
    if (getDefOfSubClass(*Def.getArg(I), "GIDefKind"))
      PrintError("This GIDefKind not implemented in tablegen");
    else if (getDefOfSubClass(*Def.getArg(I), "GIDefKindWithArgs"))
      PrintError("This GIDefKindWithArgs not implemented in tablegen");
    else
      PrintError("Expected a subclass of GIDefKind or a sub-dag whose "
                 "operator is of type GIDefKindWithArgs");
    return false;
  }

  if (Roots.size() != 1) {
    PrintError("Combine rules must have exactly one root");
    return false;
  }

  RootName = Roots.front();

  // Assign variables to all MatchDatas.
  AssignMatchDataVariables(MatchDatas);
  return true;
}

bool CombineRuleBuilder::parsePatternList(
    const DagInit &List,
    function_ref<bool(std::unique_ptr<Pattern>)> ParseAction,
    StringRef Operator, ArrayRef<SMLoc> DiagLoc,
    StringRef AnonPatNamePrefix) const {
  if (List.getOperatorAsDef(RuleDef.getLoc())->getName() != Operator) {
    ::PrintError(DiagLoc, "Expected " + Operator + " operator");
    return false;
  }

  if (List.getNumArgs() == 0) {
    ::PrintError(DiagLoc, Operator + " pattern list is empty");
    return false;
  }

  // The match section consists of a list of matchers and predicates. Parse each
  // one and add the equivalent GIMatchDag nodes, predicates, and edges.
  for (unsigned I = 0; I < List.getNumArgs(); ++I) {
    Init *Arg = List.getArg(I);
    std::string Name = List.getArgName(I)
                           ? List.getArgName(I)->getValue().str()
                           : ("__" + AnonPatNamePrefix + "_" + Twine(I)).str();

    if (auto Pat = parseInstructionPattern(*Arg, Name)) {
      if (!ParseAction(std::move(Pat)))
        return false;
      continue;
    }

    if (auto Pat = parseWipMatchOpcodeMatcher(*Arg, Name)) {
      if (!ParseAction(std::move(Pat)))
        return false;
      continue;
    }

    // Parse arbitrary C++ code
    if (const auto *StringI = dyn_cast<StringInit>(Arg)) {
      auto CXXPat = std::make_unique<CXXPattern>(*StringI, insertStrRef(Name));
      if (!ParseAction(std::move(CXXPat)))
        return false;
      continue;
    }

    ::PrintError(DiagLoc,
                 "Failed to parse pattern: '" + Arg->getAsString() + "'");
    return false;
  }

  return true;
}

std::unique_ptr<Pattern>
CombineRuleBuilder::parseInstructionPattern(const Init &Arg,
                                            StringRef Name) const {
  const DagInit *DagPat = dyn_cast<DagInit>(&Arg);
  if (!DagPat)
    return nullptr;

  std::unique_ptr<InstructionPattern> Pat;
  if (const DagInit *IP = getDagWithOperatorOfSubClass(Arg, "Instruction")) {
    auto &Instr = CGT.getInstruction(IP->getOperatorAsDef(RuleDef.getLoc()));
    Pat =
        std::make_unique<CodeGenInstructionPattern>(Instr, insertStrRef(Name));
  } else if (const DagInit *PFP =
                 getDagWithOperatorOfSubClass(Arg, PatFrag::ClassName)) {
    const Record *Def = PFP->getOperatorAsDef(RuleDef.getLoc());
    const PatFrag *PF = parsePatFrag(Def);
    if (!PF)
      return nullptr; // Already diagnosed by parsePatFrag
    Pat = std::make_unique<PatFragPattern>(*PF, insertStrRef(Name));
  } else if (const DagInit *BP =
                 getDagWithOperatorOfSubClass(Arg, BuiltinPattern::ClassName)) {
    Pat = std::make_unique<BuiltinPattern>(
        *BP->getOperatorAsDef(RuleDef.getLoc()), insertStrRef(Name));
  } else {
    return nullptr;
  }

  for (unsigned K = 0; K < DagPat->getNumArgs(); ++K) {
    Init *Arg = DagPat->getArg(K);
    if (auto *DagArg = getDagWithSpecificOperator(*Arg, "MIFlags")) {
      if (!parseInstructionPatternMIFlags(*Pat, DagArg))
        return nullptr;
      continue;
    }

    if (!parseInstructionPatternOperand(*Pat, Arg, DagPat->getArgName(K)))
      return nullptr;
  }

  if (!Pat->checkSemantics(RuleDef.getLoc()))
    return nullptr;

  return std::move(Pat);
}

std::unique_ptr<Pattern>
CombineRuleBuilder::parseWipMatchOpcodeMatcher(const Init &Arg,
                                               StringRef Name) const {
  const DagInit *Matcher = getDagWithSpecificOperator(Arg, "wip_match_opcode");
  if (!Matcher)
    return nullptr;

  if (Matcher->getNumArgs() == 0) {
    PrintError("Empty wip_match_opcode");
    return nullptr;
  }

  // Each argument is an opcode that can match.
  auto Result = std::make_unique<AnyOpcodePattern>(insertStrRef(Name));
  for (const auto &Arg : Matcher->getArgs()) {
    Record *OpcodeDef = getDefOfSubClass(*Arg, "Instruction");
    if (OpcodeDef) {
      Result->addOpcode(&CGT.getInstruction(OpcodeDef));
      continue;
    }

    PrintError("Arguments to wip_match_opcode must be instructions");
    return nullptr;
  }

  return std::move(Result);
}

bool CombineRuleBuilder::parseInstructionPatternOperand(
    InstructionPattern &IP, const Init *OpInit,
    const StringInit *OpName) const {
  const auto ParseErr = [&]() {
    PrintError("cannot parse operand '" + OpInit->getAsUnquotedString() + "' ");
    if (OpName)
      PrintNote("operand name is '" + OpName->getAsUnquotedString() + "'");
    return false;
  };

  // untyped immediate, e.g. 0
  if (const auto *IntImm = dyn_cast<IntInit>(OpInit)) {
    std::string Name = OpName ? OpName->getAsUnquotedString() : "";
    IP.addOperand(IntImm->getValue(), insertStrRef(Name), PatternType());
    return true;
  }

  // typed immediate, e.g. (i32 0)
  if (const auto *DagOp = dyn_cast<DagInit>(OpInit)) {
    if (DagOp->getNumArgs() != 1)
      return ParseErr();

    const Record *TyDef = DagOp->getOperatorAsDef(RuleDef.getLoc());
    auto ImmTy = PatternType::get(RuleDef.getLoc(), TyDef,
                                  "cannot parse immediate '" +
                                      DagOp->getAsUnquotedString() + "'");
    if (!ImmTy)
      return false;

    if (!IP.hasAllDefs()) {
      PrintError("out operand of '" + IP.getInstName() +
                 "' cannot be an immediate");
      return false;
    }

    const auto *Val = dyn_cast<IntInit>(DagOp->getArg(0));
    if (!Val)
      return ParseErr();

    std::string Name = OpName ? OpName->getAsUnquotedString() : "";
    IP.addOperand(Val->getValue(), insertStrRef(Name), *ImmTy);
    return true;
  }

  // Typed operand e.g. $x/$z in (G_FNEG $x, $z)
  if (auto *DefI = dyn_cast<DefInit>(OpInit)) {
    if (!OpName) {
      PrintError("expected an operand name after '" + OpInit->getAsString() +
                 "'");
      return false;
    }
    const Record *Def = DefI->getDef();
    auto Ty =
        PatternType::get(RuleDef.getLoc(), Def, "cannot parse operand type");
    if (!Ty)
      return false;
    IP.addOperand(insertStrRef(OpName->getAsUnquotedString()), *Ty);
    return true;
  }

  // Untyped operand e.g. $x/$z in (G_FNEG $x, $z)
  if (isa<UnsetInit>(OpInit)) {
    assert(OpName && "Unset w/ no OpName?");
    IP.addOperand(insertStrRef(OpName->getAsUnquotedString()), PatternType());
    return true;
  }

  return ParseErr();
}

bool CombineRuleBuilder::parseInstructionPatternMIFlags(
    InstructionPattern &IP, const DagInit *Op) const {
  auto *CGIP = dyn_cast<CodeGenInstructionPattern>(&IP);
  if (!CGIP) {
    PrintError("matching/writing MIFlags is only allowed on CodeGenInstruction "
               "patterns");
    return false;
  }

  const auto CheckFlagEnum = [&](const Record *R) {
    if (!R->isSubClassOf(MIFlagsEnumClassName)) {
      PrintError("'" + R->getName() + "' is not a subclass of '" +
                 MIFlagsEnumClassName + "'");
      return false;
    }

    return true;
  };

  if (CGIP->getMIFlagsInfo()) {
    PrintError("MIFlags can only be present once on an instruction");
    return false;
  }

  auto &FI = CGIP->getOrCreateMIFlagsInfo();
  for (unsigned K = 0; K < Op->getNumArgs(); ++K) {
    const Init *Arg = Op->getArg(K);

    // Match/set a flag: (MIFlags FmNoNans)
    if (const auto *Def = dyn_cast<DefInit>(Arg)) {
      const Record *R = Def->getDef();
      if (!CheckFlagEnum(R))
        return false;

      FI.addSetFlag(R);
      continue;
    }

    // Do not match a flag/unset a flag: (MIFlags (not FmNoNans))
    if (const DagInit *NotDag = getDagWithSpecificOperator(*Arg, "not")) {
      for (const Init *NotArg : NotDag->getArgs()) {
        const DefInit *DefArg = dyn_cast<DefInit>(NotArg);
        if (!DefArg) {
          PrintError("cannot parse '" + NotArg->getAsUnquotedString() +
                     "': expected a '" + MIFlagsEnumClassName + "'");
          return false;
        }

        const Record *R = DefArg->getDef();
        if (!CheckFlagEnum(R))
          return false;

        FI.addUnsetFlag(R);
        continue;
      }

      continue;
    }

    // Copy flags from a matched instruction: (MIFlags $mi)
    if (isa<UnsetInit>(Arg)) {
      FI.addCopyFlag(insertStrRef(Op->getArgName(K)->getAsUnquotedString()));
      continue;
    }
  }

  return true;
}

std::unique_ptr<PatFrag>
CombineRuleBuilder::parsePatFragImpl(const Record *Def) const {
  auto StackTrace = PrettyStackTraceParse(*Def);
  if (!Def->isSubClassOf(PatFrag::ClassName))
    return nullptr;

  const DagInit *Ins = Def->getValueAsDag("InOperands");
  if (Ins->getOperatorAsDef(Def->getLoc())->getName() != "ins") {
    ::PrintError(Def, "expected 'ins' operator for " + PatFrag::ClassName +
                          " in operands list");
    return nullptr;
  }

  const DagInit *Outs = Def->getValueAsDag("OutOperands");
  if (Outs->getOperatorAsDef(Def->getLoc())->getName() != "outs") {
    ::PrintError(Def, "expected 'outs' operator for " + PatFrag::ClassName +
                          " out operands list");
    return nullptr;
  }

  auto Result = std::make_unique<PatFrag>(*Def);
  if (!parsePatFragParamList(Def->getLoc(), *Outs,
                             [&](StringRef Name, PatFrag::ParamKind Kind) {
                               Result->addOutParam(insertStrRef(Name), Kind);
                               return true;
                             }))
    return nullptr;

  if (!parsePatFragParamList(Def->getLoc(), *Ins,
                             [&](StringRef Name, PatFrag::ParamKind Kind) {
                               Result->addInParam(insertStrRef(Name), Kind);
                               return true;
                             }))
    return nullptr;

  const ListInit *Alts = Def->getValueAsListInit("Alternatives");
  unsigned AltIdx = 0;
  for (const Init *Alt : *Alts) {
    const auto *PatDag = dyn_cast<DagInit>(Alt);
    if (!PatDag) {
      ::PrintError(Def, "expected dag init for PatFrag pattern alternative");
      return nullptr;
    }

    PatFrag::Alternative &A = Result->addAlternative();
    const auto AddPat = [&](std::unique_ptr<Pattern> Pat) {
      A.Pats.push_back(std::move(Pat));
      return true;
    };

    if (!parsePatternList(
            *PatDag, AddPat, "pattern", Def->getLoc(),
            /*AnonPatPrefix*/
            (Def->getName() + "_alt" + Twine(AltIdx++) + "_pattern").str()))
      return nullptr;
  }

  if (!Result->buildOperandsTables() || !Result->checkSemantics())
    return nullptr;

  return Result;
}

bool CombineRuleBuilder::parsePatFragParamList(
    ArrayRef<SMLoc> DiagLoc, const DagInit &OpsList,
    function_ref<bool(StringRef, PatFrag::ParamKind)> ParseAction) const {
  for (unsigned K = 0; K < OpsList.getNumArgs(); ++K) {
    const StringInit *Name = OpsList.getArgName(K);
    const Init *Ty = OpsList.getArg(K);

    if (!Name) {
      ::PrintError(DiagLoc, "all operands must be named'");
      return false;
    }
    const std::string NameStr = Name->getAsUnquotedString();

    PatFrag::ParamKind OpKind;
    if (isSpecificDef(*Ty, "gi_imm"))
      OpKind = PatFrag::PK_Imm;
    else if (isSpecificDef(*Ty, "root"))
      OpKind = PatFrag::PK_Root;
    else if (isa<UnsetInit>(Ty) ||
             isSpecificDef(*Ty, "gi_mo")) // no type = gi_mo.
      OpKind = PatFrag::PK_MachineOperand;
    else {
      ::PrintError(
          DiagLoc,
          "'" + NameStr +
              "' operand type was expected to be 'root', 'gi_imm' or 'gi_mo'");
      return false;
    }

    if (!ParseAction(NameStr, OpKind))
      return false;
  }

  return true;
}

const PatFrag *CombineRuleBuilder::parsePatFrag(const Record *Def) const {
  // Cache already parsed PatFrags to avoid doing extra work.
  static DenseMap<const Record *, std::unique_ptr<PatFrag>> ParsedPatFrags;

  auto It = ParsedPatFrags.find(Def);
  if (It != ParsedPatFrags.end()) {
    SeenPatFrags.insert(It->second.get());
    return It->second.get();
  }

  std::unique_ptr<PatFrag> NewPatFrag = parsePatFragImpl(Def);
  if (!NewPatFrag) {
    ::PrintError(Def, "Could not parse " + PatFrag::ClassName + " '" +
                          Def->getName() + "'");
    // Put a nullptr in the map so we don't attempt parsing this again.
    ParsedPatFrags[Def] = nullptr;
    return nullptr;
  }

  const auto *Res = NewPatFrag.get();
  ParsedPatFrags[Def] = std::move(NewPatFrag);
  SeenPatFrags.insert(Res);
  return Res;
}

bool CombineRuleBuilder::emitMatchPattern(CodeExpansions &CE,
                                          const PatternAlternatives &Alts,
                                          const InstructionPattern &IP) {
  auto StackTrace = PrettyStackTraceEmit(RuleDef, &IP);

  auto &M = addRuleMatcher(Alts);
  InstructionMatcher &IM = M.addInstructionMatcher(IP.getName());
  declareInstExpansion(CE, IM, IP.getName());

  DenseSet<const Pattern *> SeenPats;

  const auto FindOperandDef = [&](StringRef Op) -> InstructionPattern * {
    return MatchOpTable.getDef(Op);
  };

  if (const auto *CGP = dyn_cast<CodeGenInstructionPattern>(&IP)) {
    if (!emitCodeGenInstructionMatchPattern(CE, Alts, M, IM, *CGP, SeenPats,
                                            FindOperandDef))
      return false;
  } else if (const auto *PFP = dyn_cast<PatFragPattern>(&IP)) {
    if (!PFP->getPatFrag().canBeMatchRoot()) {
      PrintError("cannot use '" + PFP->getInstName() + " as match root");
      return false;
    }

    if (!emitPatFragMatchPattern(CE, Alts, M, &IM, *PFP, SeenPats))
      return false;
  } else if (isa<BuiltinPattern>(&IP)) {
    llvm_unreachable("No match builtins known!");
  } else
    llvm_unreachable("Unknown kind of InstructionPattern!");

  // Emit remaining patterns
  for (auto &Pat : values(MatchPats)) {
    if (SeenPats.contains(Pat.get()))
      continue;

    switch (Pat->getKind()) {
    case Pattern::K_AnyOpcode:
      PrintError("wip_match_opcode can not be used with instruction patterns!");
      return false;
    case Pattern::K_PatFrag: {
      if (!emitPatFragMatchPattern(CE, Alts, M, /*IM*/ nullptr,
                                   *cast<PatFragPattern>(Pat.get()), SeenPats))
        return false;
      continue;
    }
    case Pattern::K_Builtin:
      PrintError("No known match builtins");
      return false;
    case Pattern::K_CodeGenInstruction:
      cast<InstructionPattern>(Pat.get())->reportUnreachable(RuleDef.getLoc());
      return false;
    case Pattern::K_CXX: {
      addCXXPredicate(M, CE, *cast<CXXPattern>(Pat.get()), Alts);
      continue;
    }
    default:
      llvm_unreachable("unknown pattern kind!");
    }
  }

  return emitApplyPatterns(CE, M);
}

bool CombineRuleBuilder::emitMatchPattern(CodeExpansions &CE,
                                          const PatternAlternatives &Alts,
                                          const AnyOpcodePattern &AOP) {
  auto StackTrace = PrettyStackTraceEmit(RuleDef, &AOP);

  for (const CodeGenInstruction *CGI : AOP.insts()) {
    auto &M = addRuleMatcher(Alts, "wip_match_opcode '" +
                                       CGI->TheDef->getName() + "'");

    InstructionMatcher &IM = M.addInstructionMatcher(AOP.getName());
    declareInstExpansion(CE, IM, AOP.getName());
    // declareInstExpansion needs to be identical, otherwise we need to create a
    // CodeExpansions object here instead.
    assert(IM.getInsnVarID() == 0);

    IM.addPredicate<InstructionOpcodeMatcher>(CGI);

    // Emit remaining patterns.
    for (auto &Pat : values(MatchPats)) {
      if (Pat.get() == &AOP)
        continue;

      switch (Pat->getKind()) {
      case Pattern::K_AnyOpcode:
        PrintError("wip_match_opcode can only be present once!");
        return false;
      case Pattern::K_PatFrag: {
        DenseSet<const Pattern *> SeenPats;
        if (!emitPatFragMatchPattern(CE, Alts, M, /*IM*/ nullptr,
                                     *cast<PatFragPattern>(Pat.get()),
                                     SeenPats))
          return false;
        continue;
      }
      case Pattern::K_Builtin:
        PrintError("No known match builtins");
        return false;
      case Pattern::K_CodeGenInstruction:
        cast<InstructionPattern>(Pat.get())->reportUnreachable(
            RuleDef.getLoc());
        return false;
      case Pattern::K_CXX: {
        addCXXPredicate(M, CE, *cast<CXXPattern>(Pat.get()), Alts);
        break;
      }
      default:
        llvm_unreachable("unknown pattern kind!");
      }
    }

    if (!emitApplyPatterns(CE, M))
      return false;
  }

  return true;
}

bool CombineRuleBuilder::emitPatFragMatchPattern(
    CodeExpansions &CE, const PatternAlternatives &Alts, RuleMatcher &RM,
    InstructionMatcher *IM, const PatFragPattern &PFP,
    DenseSet<const Pattern *> &SeenPats) {
  auto StackTrace = PrettyStackTraceEmit(RuleDef, &PFP);

  if (SeenPats.contains(&PFP))
    return true;
  SeenPats.insert(&PFP);

  const auto &PF = PFP.getPatFrag();

  if (!IM) {
    // When we don't have an IM, this means this PatFrag isn't reachable from
    // the root. This is only acceptable if it doesn't define anything (e.g. a
    // pure C++ PatFrag).
    if (PF.num_out_params() != 0) {
      PFP.reportUnreachable(RuleDef.getLoc());
      return false;
    }
  } else {
    // When an IM is provided, this is reachable from the root, and we're
    // expecting to have output operands.
    // TODO: If we want to allow for multiple roots we'll need a map of IMs
    // then, and emission becomes a bit more complicated.
    assert(PF.num_roots() == 1);
  }

  CodeExpansions PatFragCEs;
  if (!PFP.mapInputCodeExpansions(CE, PatFragCEs, RuleDef.getLoc()))
    return false;

  // List of {ParamName, ArgName}.
  // When all patterns have been emitted, find expansions in PatFragCEs named
  // ArgName and add their expansion to CE using ParamName as the key.
  SmallVector<std::pair<std::string, std::string>, 4> CEsToImport;

  // Map parameter names to the actual argument.
  const auto OperandMapper =
      [&](const InstructionOperand &O) -> InstructionOperand {
    if (!O.isNamedOperand())
      return O;

    StringRef ParamName = O.getOperandName();

    // Not sure what to do with those tbh. They should probably never be here.
    assert(!O.isNamedImmediate() && "TODO: handle named imms");
    unsigned PIdx = PF.getParamIdx(ParamName);

    // Map parameters to the argument values.
    if (PIdx == (unsigned)-1) {
      // This is a temp of the PatFragPattern, prefix the name to avoid
      // conflicts.
      return O.withNewName(
          insertStrRef((PFP.getName() + "." + ParamName).str()));
    }

    // The operand will be added to PatFragCEs's code expansions using the
    // parameter's name. If it's bound to some operand during emission of the
    // patterns, we'll want to add it to CE.
    auto ArgOp = PFP.getOperand(PIdx);
    if (ArgOp.isNamedOperand())
      CEsToImport.emplace_back(ArgOp.getOperandName().str(), ParamName);

    if (ArgOp.getType() && O.getType() && ArgOp.getType() != O.getType()) {
      StringRef PFName = PF.getName();
      PrintWarning("impossible type constraints: operand " + Twine(PIdx) +
                   " of '" + PFP.getName() + "' has type '" +
                   ArgOp.getType().str() + "', but '" + PFName +
                   "' constrains it to '" + O.getType().str() + "'");
      if (ArgOp.isNamedOperand())
        PrintNote("operand " + Twine(PIdx) + " of '" + PFP.getName() +
                  "' is '" + ArgOp.getOperandName() + "'");
      if (O.isNamedOperand())
        PrintNote("argument " + Twine(PIdx) + " of '" + PFName + "' is '" +
                  ParamName + "'");
    }

    return ArgOp;
  };

  // PatFragPatterns are only made of InstructionPatterns or CXXPatterns.
  // Emit instructions from the root.
  const auto &FragAlt = PF.getAlternative(Alts.lookup(&PFP));
  const auto &FragAltOT = FragAlt.OpTable;
  const auto LookupOperandDef =
      [&](StringRef Op) -> const InstructionPattern * {
    return FragAltOT.getDef(Op);
  };

  DenseSet<const Pattern *> PatFragSeenPats;
  for (const auto &[Idx, InOp] : enumerate(PF.out_params())) {
    if (InOp.Kind != PatFrag::PK_Root)
      continue;

    StringRef ParamName = InOp.Name;
    const auto *Def = FragAltOT.getDef(ParamName);
    assert(Def && "PatFrag::checkSemantics should have emitted an error if "
                  "an out operand isn't defined!");
    assert(isa<CodeGenInstructionPattern>(Def) &&
           "Nested PatFrags not supported yet");

    if (!emitCodeGenInstructionMatchPattern(
            PatFragCEs, Alts, RM, *IM, *cast<CodeGenInstructionPattern>(Def),
            PatFragSeenPats, LookupOperandDef, OperandMapper))
      return false;
  }

  // Emit leftovers.
  for (const auto &Pat : FragAlt.Pats) {
    if (PatFragSeenPats.contains(Pat.get()))
      continue;

    if (const auto *CXXPat = dyn_cast<CXXPattern>(Pat.get())) {
      addCXXPredicate(RM, PatFragCEs, *CXXPat, Alts);
      continue;
    }

    if (const auto *IP = dyn_cast<InstructionPattern>(Pat.get())) {
      IP->reportUnreachable(PF.getLoc());
      return false;
    }

    llvm_unreachable("Unexpected pattern kind in PatFrag");
  }

  for (const auto &[ParamName, ArgName] : CEsToImport) {
    // Note: we're find if ParamName already exists. It just means it's been
    // bound before, so we prefer to keep the first binding.
    CE.declare(ParamName, PatFragCEs.lookup(ArgName));
  }

  return true;
}

bool CombineRuleBuilder::emitApplyPatterns(CodeExpansions &CE, RuleMatcher &M) {
  if (hasOnlyCXXApplyPatterns()) {
    for (auto &Pat : values(ApplyPats))
      addCXXAction(M, CE, *cast<CXXPattern>(Pat.get()));
    return true;
  }

  DenseSet<const Pattern *> SeenPats;
  StringMap<unsigned> OperandToTempRegID;

  for (auto *ApplyRoot : ApplyRoots) {
    assert(isa<InstructionPattern>(ApplyRoot) &&
           "Root can only be a InstructionPattern!");
    if (!emitInstructionApplyPattern(CE, M,
                                     cast<InstructionPattern>(*ApplyRoot),
                                     SeenPats, OperandToTempRegID))
      return false;
  }

  for (auto &Pat : values(ApplyPats)) {
    if (SeenPats.contains(Pat.get()))
      continue;

    switch (Pat->getKind()) {
    case Pattern::K_AnyOpcode:
      llvm_unreachable("Unexpected pattern in apply!");
    case Pattern::K_PatFrag:
      // TODO: We could support pure C++ PatFrags as a temporary thing.
      llvm_unreachable("Unexpected pattern in apply!");
    case Pattern::K_Builtin:
      if (!emitInstructionApplyPattern(CE, M, cast<BuiltinPattern>(*Pat),
                                       SeenPats, OperandToTempRegID))
        return false;
      break;
    case Pattern::K_CodeGenInstruction:
      cast<CodeGenInstructionPattern>(*Pat).reportUnreachable(RuleDef.getLoc());
      return false;
    case Pattern::K_CXX: {
      addCXXAction(M, CE, *cast<CXXPattern>(Pat.get()));
      continue;
    }
    default:
      llvm_unreachable("unknown pattern kind!");
    }
  }

  // Erase the root.
  unsigned RootInsnID =
      M.getInsnVarID(M.getInstructionMatcher(MatchRoot->getName()));
  M.addAction<EraseInstAction>(RootInsnID);

  return true;
}

bool CombineRuleBuilder::emitInstructionApplyPattern(
    CodeExpansions &CE, RuleMatcher &M, const InstructionPattern &P,
    DenseSet<const Pattern *> &SeenPats,
    StringMap<unsigned> &OperandToTempRegID) {
  auto StackTrace = PrettyStackTraceEmit(RuleDef, &P);

  if (SeenPats.contains(&P))
    return true;

  SeenPats.insert(&P);

  // First, render the uses.
  for (auto &Op : P.named_operands()) {
    if (Op.isDef())
      continue;

    StringRef OpName = Op.getOperandName();
    if (const auto *DefPat = ApplyOpTable.getDef(OpName)) {
      if (!emitInstructionApplyPattern(CE, M, *DefPat, SeenPats,
                                       OperandToTempRegID))
        return false;
    } else {
      // If we have no def, check this exists in the MatchRoot.
      if (!Op.isNamedImmediate() && !MatchOpTable.lookup(OpName).Found) {
        PrintError("invalid output operand '" + OpName +
                   "': operand is not a live-in of the match pattern, and it "
                   "has no definition");
        return false;
      }
    }
  }

  if (const auto *BP = dyn_cast<BuiltinPattern>(&P))
    return emitBuiltinApplyPattern(CE, M, *BP, OperandToTempRegID);

  if (isa<PatFragPattern>(&P))
    llvm_unreachable("PatFragPatterns is not supported in 'apply'!");

  auto &CGIP = cast<CodeGenInstructionPattern>(P);

  // Now render this inst.
  auto &DstMI =
      M.addAction<BuildMIAction>(M.allocateOutputInsnID(), &CGIP.getInst());

  for (auto &Op : P.operands()) {
    if (Op.isNamedImmediate()) {
      PrintError("invalid output operand '" + Op.getOperandName() +
                 "': output immediates cannot be named");
      PrintNote("while emitting pattern '" + P.getName() + "' (" +
                P.getInstName() + ")");
      return false;
    }

    if (Op.hasImmValue()) {
      if (!emitCodeGenInstructionApplyImmOperand(M, DstMI, CGIP, Op))
        return false;
      continue;
    }

    StringRef OpName = Op.getOperandName();

    // Uses of operand.
    if (!Op.isDef()) {
      if (auto It = OperandToTempRegID.find(OpName);
          It != OperandToTempRegID.end()) {
        assert(!MatchOpTable.lookup(OpName).Found &&
               "Temp reg is also from match pattern?");
        DstMI.addRenderer<TempRegRenderer>(It->second);
      } else {
        // This should be a match live in or a redef of a matched instr.
        // If it's a use of a temporary register, then we messed up somewhere -
        // the previous condition should have passed.
        assert(MatchOpTable.lookup(OpName).Found &&
               !ApplyOpTable.getDef(OpName) && "Temp reg not emitted yet!");
        DstMI.addRenderer<CopyRenderer>(OpName);
      }
      continue;
    }

    // Determine what we're dealing with. Are we replace a matched instruction?
    // Creating a new one?
    auto OpLookupRes = MatchOpTable.lookup(OpName);
    if (OpLookupRes.Found) {
      if (OpLookupRes.isLiveIn()) {
        // live-in of the match pattern.
        PrintError("Cannot define live-in operand '" + OpName +
                   "' in the 'apply' pattern");
        return false;
      }
      assert(OpLookupRes.Def);

      // TODO: Handle this. We need to mutate the instr, or delete the old
      // one.
      //       Likewise, we also need to ensure we redef everything, if the
      //       instr has more than one def, we need to redef all or nothing.
      if (OpLookupRes.Def != MatchRoot) {
        PrintError("redefining an instruction other than the root is not "
                   "supported (operand '" +
                   OpName + "')");
        return false;
      }
      // redef of a match
      DstMI.addRenderer<CopyRenderer>(OpName);
      continue;
    }

    // Define a new register unique to the apply patterns (AKA a "temp"
    // register).
    unsigned TempRegID;
    if (auto It = OperandToTempRegID.find(OpName);
        It != OperandToTempRegID.end()) {
      TempRegID = It->second;
    } else {
      // This is a brand new register.
      TempRegID = M.allocateTempRegID();
      OperandToTempRegID[OpName] = TempRegID;
      const auto Ty = Op.getType();
      if (!Ty) {
        PrintError("def of a new register '" + OpName +
                   "' in the apply patterns must have a type");
        return false;
      }

      declareTempRegExpansion(CE, TempRegID, OpName);
      // Always insert the action at the beginning, otherwise we may end up
      // using the temp reg before it's available.
      M.insertAction<MakeTempRegisterAction>(
          M.actions_begin(), getLLTCodeGenOrTempType(Ty, M), TempRegID);
    }

    DstMI.addRenderer<TempRegRenderer>(TempRegID, /*IsDef=*/true);
  }

  // Render MIFlags
  if (const auto *FI = CGIP.getMIFlagsInfo()) {
    for (StringRef InstName : FI->copy_flags())
      DstMI.addCopiedMIFlags(M.getInstructionMatcher(InstName));
    for (StringRef F : FI->set_flags())
      DstMI.addSetMIFlags(F);
    for (StringRef F : FI->unset_flags())
      DstMI.addUnsetMIFlags(F);
  }

  // Don't allow mutating opcodes for GISel combiners. We want a more precise
  // handling of MIFlags so we require them to be explicitly preserved.
  //
  // TODO: We don't mutate very often, if at all in combiners, but it'd be nice
  // to re-enable this. We'd then need to always clear MIFlags when mutating
  // opcodes, and never mutate an inst that we copy flags from.
  // DstMI.chooseInsnToMutate(M);
  declareInstExpansion(CE, DstMI, P.getName());

  return true;
}

bool CombineRuleBuilder::emitCodeGenInstructionApplyImmOperand(
    RuleMatcher &M, BuildMIAction &DstMI, const CodeGenInstructionPattern &P,
    const InstructionOperand &O) {
  // If we have a type, we implicitly emit a G_CONSTANT, except for G_CONSTANT
  // itself where we emit a CImm.
  //
  // No type means we emit a simple imm.
  // G_CONSTANT is a special case and needs a CImm though so this is likely a
  // mistake.
  const bool isGConstant = P.is("G_CONSTANT");
  const auto Ty = O.getType();
  if (!Ty) {
    if (isGConstant) {
      PrintError("'G_CONSTANT' immediate must be typed!");
      PrintNote("while emitting pattern '" + P.getName() + "' (" +
                P.getInstName() + ")");
      return false;
    }

    DstMI.addRenderer<ImmRenderer>(O.getImmValue());
    return true;
  }

  auto ImmTy = getLLTCodeGenOrTempType(Ty, M);

  if (isGConstant) {
    DstMI.addRenderer<ImmRenderer>(O.getImmValue(), ImmTy);
    return true;
  }

  unsigned TempRegID = M.allocateTempRegID();
  // Ensure MakeTempReg & the BuildConstantAction occur at the beginning.
  auto InsertIt = M.insertAction<MakeTempRegisterAction>(M.actions_begin(),
                                                         ImmTy, TempRegID);
  M.insertAction<BuildConstantAction>(++InsertIt, TempRegID, O.getImmValue());
  DstMI.addRenderer<TempRegRenderer>(TempRegID);
  return true;
}

bool CombineRuleBuilder::emitBuiltinApplyPattern(
    CodeExpansions &CE, RuleMatcher &M, const BuiltinPattern &P,
    StringMap<unsigned> &OperandToTempRegID) {
  const auto Error = [&](Twine Reason) {
    PrintError("cannot emit '" + P.getInstName() + "' builtin: " + Reason);
    return false;
  };

  switch (P.getBuiltinKind()) {
  case BI_EraseRoot: {
    // Root is always inst 0.
    M.addAction<EraseInstAction>(/*InsnID*/ 0);
    return true;
  }
  case BI_ReplaceReg: {
    StringRef Old = P.getOperand(0).getOperandName();
    StringRef New = P.getOperand(1).getOperandName();

    if (!ApplyOpTable.lookup(New).Found && !MatchOpTable.lookup(New).Found)
      return Error("unknown operand '" + Old + "'");

    auto &OldOM = M.getOperandMatcher(Old);
    if (auto It = OperandToTempRegID.find(New);
        It != OperandToTempRegID.end()) {
      // Replace with temp reg.
      M.addAction<ReplaceRegAction>(OldOM.getInsnVarID(), OldOM.getOpIdx(),
                                    It->second);
    } else {
      // Replace with matched reg.
      auto &NewOM = M.getOperandMatcher(New);
      M.addAction<ReplaceRegAction>(OldOM.getInsnVarID(), OldOM.getOpIdx(),
                                    NewOM.getInsnVarID(), NewOM.getOpIdx());
    }
    // checkSemantics should have ensured that we can only rewrite the root.
    // Ensure we're deleting it.
    assert(MatchOpTable.getDef(Old) == MatchRoot);
    return true;
  }
  }

  llvm_unreachable("Unknown BuiltinKind!");
}

bool isLiteralImm(const InstructionPattern &P, unsigned OpIdx) {
  if (const auto *CGP = dyn_cast<CodeGenInstructionPattern>(&P)) {
    StringRef InstName = CGP->getInst().TheDef->getName();
    return (InstName == "G_CONSTANT" || InstName == "G_FCONSTANT") &&
           OpIdx == 1;
  }

  llvm_unreachable("TODO");
}

bool CombineRuleBuilder::emitCodeGenInstructionMatchPattern(
    CodeExpansions &CE, const PatternAlternatives &Alts, RuleMatcher &M,
    InstructionMatcher &IM, const CodeGenInstructionPattern &P,
    DenseSet<const Pattern *> &SeenPats, OperandDefLookupFn LookupOperandDef,
    OperandMapperFnRef OperandMapper) {
  auto StackTrace = PrettyStackTraceEmit(RuleDef, &P);

  if (SeenPats.contains(&P))
    return true;

  SeenPats.insert(&P);

  IM.addPredicate<InstructionOpcodeMatcher>(&P.getInst());
  declareInstExpansion(CE, IM, P.getName());

  // Check flags if needed.
  if (const auto *FI = P.getMIFlagsInfo()) {
    assert(FI->copy_flags().empty());

    if (const auto &SetF = FI->set_flags(); !SetF.empty())
      IM.addPredicate<MIFlagsInstructionPredicateMatcher>(SetF.getArrayRef());
    if (const auto &UnsetF = FI->unset_flags(); !UnsetF.empty())
      IM.addPredicate<MIFlagsInstructionPredicateMatcher>(UnsetF.getArrayRef(),
                                                          /*CheckNot=*/true);
  }

  for (const auto &[Idx, OriginalO] : enumerate(P.operands())) {
    // Remap the operand. This is used when emitting InstructionPatterns inside
    // PatFrags, so it can remap them to the arguments passed to the pattern.
    //
    // We use the remapped operand to emit immediates, and for the symbolic
    // operand names (in IM.addOperand). CodeExpansions and OperandTable lookups
    // still use the original name.
    //
    // The "def" flag on the remapped operand is always ignored.
    auto RemappedO = OperandMapper(OriginalO);
    assert(RemappedO.isNamedOperand() == OriginalO.isNamedOperand() &&
           "Cannot remap an unnamed operand to a named one!");

    const auto OpName =
        RemappedO.isNamedOperand() ? RemappedO.getOperandName().str() : "";
    OperandMatcher &OM =
        IM.addOperand(Idx, OpName, AllocatedTemporariesBaseID++);
    if (!OpName.empty())
      declareOperandExpansion(CE, OM, OriginalO.getOperandName());

    // Handle immediates.
    if (RemappedO.hasImmValue()) {
      if (isLiteralImm(P, Idx))
        OM.addPredicate<LiteralIntOperandMatcher>(RemappedO.getImmValue());
      else
        OM.addPredicate<ConstantIntOperandMatcher>(RemappedO.getImmValue());
    }

    // Handle typed operands, but only bother to check if it hasn't been done
    // before.
    //
    // getOperandMatcher will always return the first OM to have been created
    // for that Operand. "OM" here is always a new OperandMatcher.
    //
    // Always emit a check for unnamed operands.
    if (OpName.empty() ||
        !M.getOperandMatcher(OpName).contains<LLTOperandMatcher>()) {
      if (const auto Ty = RemappedO.getType()) {
        // TODO: We could support GITypeOf here on the condition that the
        // OperandMatcher exists already. Though it's clunky to make this work
        // and isn't all that useful so it's just rejected in typecheckPatterns
        // at this time.
        assert(Ty.isLLT() && "Only LLTs are supported in match patterns!");
        OM.addPredicate<LLTOperandMatcher>(getLLTCodeGen(Ty));
      }
    }

    // Stop here if the operand is a def, or if it had no name.
    if (OriginalO.isDef() || !OriginalO.isNamedOperand())
      continue;

    const auto *DefPat = LookupOperandDef(OriginalO.getOperandName());
    if (!DefPat)
      continue;

    if (OriginalO.hasImmValue()) {
      assert(!OpName.empty());
      // This is a named immediate that also has a def, that's not okay.
      // e.g.
      //    (G_SEXT $y, (i32 0))
      //    (COPY $x, 42:$y)
      PrintError("'" + OpName +
                 "' is a named immediate, it cannot be defined by another "
                 "instruction");
      PrintNote("'" + OpName + "' is defined by '" + DefPat->getName() + "'");
      return false;
    }

    // From here we know that the operand defines an instruction, and we need to
    // emit it.
    auto InstOpM =
        OM.addPredicate<InstructionOperandMatcher>(M, DefPat->getName());
    if (!InstOpM) {
      // TODO: copy-pasted from GlobalISelEmitter.cpp. Is it still relevant
      // here?
      PrintError("Nested instruction '" + DefPat->getName() +
                 "' cannot be the same as another operand '" +
                 OriginalO.getOperandName() + "'");
      return false;
    }

    auto &IM = (*InstOpM)->getInsnMatcher();
    if (const auto *CGIDef = dyn_cast<CodeGenInstructionPattern>(DefPat)) {
      if (!emitCodeGenInstructionMatchPattern(CE, Alts, M, IM, *CGIDef,
                                              SeenPats, LookupOperandDef,
                                              OperandMapper))
        return false;
      continue;
    }

    if (const auto *PFPDef = dyn_cast<PatFragPattern>(DefPat)) {
      if (!emitPatFragMatchPattern(CE, Alts, M, &IM, *PFPDef, SeenPats))
        return false;
      continue;
    }

    llvm_unreachable("unknown type of InstructionPattern");
  }

  return true;
}

//===- GICombinerEmitter --------------------------------------------------===//

/// Main implementation class. This emits the tablegenerated output.
///
/// It collects rules, uses `CombineRuleBuilder` to parse them and accumulate
/// RuleMatchers, then takes all the necessary state/data from the various
/// static storage pools and wires them together to emit the match table &
/// associated function/data structures.
class GICombinerEmitter final : public GlobalISelMatchTableExecutorEmitter {
  RecordKeeper &Records;
  StringRef Name;
  const CodeGenTarget &Target;
  Record *Combiner;
  unsigned NextRuleID = 0;

  // List all combine rules (ID, name) imported.
  // Note that the combiner rule ID is different from the RuleMatcher ID. The
  // latter is internal to the MatchTable, the former is the canonical ID of the
  // combine rule used to disable/enable it.
  std::vector<std::pair<unsigned, std::string>> AllCombineRules;

  // Keep track of all rules we've seen so far to ensure we don't process
  // the same rule twice.
  StringSet<> RulesSeen;

  MatchTable buildMatchTable(MutableArrayRef<RuleMatcher> Rules);

  void emitRuleConfigImpl(raw_ostream &OS);

  void emitAdditionalImpl(raw_ostream &OS) override;

  void emitMIPredicateFns(raw_ostream &OS) override;
  void emitI64ImmPredicateFns(raw_ostream &OS) override;
  void emitAPFloatImmPredicateFns(raw_ostream &OS) override;
  void emitAPIntImmPredicateFns(raw_ostream &OS) override;
  void emitTestSimplePredicate(raw_ostream &OS) override;
  void emitRunCustomAction(raw_ostream &OS) override;

  void emitAdditionalTemporariesDecl(raw_ostream &OS,
                                     StringRef Indent) override;

  const CodeGenTarget &getTarget() const override { return Target; }
  StringRef getClassName() const override {
    return Combiner->getValueAsString("Classname");
  }

  StringRef getCombineAllMethodName() const {
    return Combiner->getValueAsString("CombineAllMethodName");
  }

  std::string getRuleConfigClassName() const {
    return getClassName().str() + "RuleConfig";
  }

  void gatherRules(std::vector<RuleMatcher> &Rules,
                   const std::vector<Record *> &&RulesAndGroups);

public:
  explicit GICombinerEmitter(RecordKeeper &RK, const CodeGenTarget &Target,
                             StringRef Name, Record *Combiner);
  ~GICombinerEmitter() {}

  void run(raw_ostream &OS);
};

void GICombinerEmitter::emitRuleConfigImpl(raw_ostream &OS) {
  OS << "struct " << getRuleConfigClassName() << " {\n"
     << "  SparseBitVector<> DisabledRules;\n\n"
     << "  bool isRuleEnabled(unsigned RuleID) const;\n"
     << "  bool parseCommandLineOption();\n"
     << "  bool setRuleEnabled(StringRef RuleIdentifier);\n"
     << "  bool setRuleDisabled(StringRef RuleIdentifier);\n"
     << "};\n\n";

  std::vector<std::pair<std::string, std::string>> Cases;
  Cases.reserve(AllCombineRules.size());

  for (const auto &[ID, Name] : AllCombineRules)
    Cases.emplace_back(Name, "return " + to_string(ID) + ";\n");

  OS << "static std::optional<uint64_t> getRuleIdxForIdentifier(StringRef "
        "RuleIdentifier) {\n"
     << "  uint64_t I;\n"
     << "  // getAtInteger(...) returns false on success\n"
     << "  bool Parsed = !RuleIdentifier.getAsInteger(0, I);\n"
     << "  if (Parsed)\n"
     << "    return I;\n\n"
     << "#ifndef NDEBUG\n";
  StringMatcher Matcher("RuleIdentifier", Cases, OS);
  Matcher.Emit();
  OS << "#endif // ifndef NDEBUG\n\n"
     << "  return std::nullopt;\n"
     << "}\n";

  OS << "static std::optional<std::pair<uint64_t, uint64_t>> "
        "getRuleRangeForIdentifier(StringRef RuleIdentifier) {\n"
     << "  std::pair<StringRef, StringRef> RangePair = "
        "RuleIdentifier.split('-');\n"
     << "  if (!RangePair.second.empty()) {\n"
     << "    const auto First = "
        "getRuleIdxForIdentifier(RangePair.first);\n"
     << "    const auto Last = "
        "getRuleIdxForIdentifier(RangePair.second);\n"
     << "    if (!First || !Last)\n"
     << "      return std::nullopt;\n"
     << "    if (First >= Last)\n"
     << "      report_fatal_error(\"Beginning of range should be before "
        "end of range\");\n"
     << "    return {{*First, *Last + 1}};\n"
     << "  }\n"
     << "  if (RangePair.first == \"*\") {\n"
     << "    return {{0, " << AllCombineRules.size() << "}};\n"
     << "  }\n"
     << "  const auto I = getRuleIdxForIdentifier(RangePair.first);\n"
     << "  if (!I)\n"
     << "    return std::nullopt;\n"
     << "  return {{*I, *I + 1}};\n"
     << "}\n\n";

  for (bool Enabled : {true, false}) {
    OS << "bool " << getRuleConfigClassName() << "::setRule"
       << (Enabled ? "Enabled" : "Disabled") << "(StringRef RuleIdentifier) {\n"
       << "  auto MaybeRange = getRuleRangeForIdentifier(RuleIdentifier);\n"
       << "  if (!MaybeRange)\n"
       << "    return false;\n"
       << "  for (auto I = MaybeRange->first; I < MaybeRange->second; ++I)\n"
       << "    DisabledRules." << (Enabled ? "reset" : "set") << "(I);\n"
       << "  return true;\n"
       << "}\n\n";
  }

  OS << "static std::vector<std::string> " << Name << "Option;\n"
     << "static cl::list<std::string> " << Name << "DisableOption(\n"
     << "    \"" << Name.lower() << "-disable-rule\",\n"
     << "    cl::desc(\"Disable one or more combiner rules temporarily in "
     << "the " << Name << " pass\"),\n"
     << "    cl::CommaSeparated,\n"
     << "    cl::Hidden,\n"
     << "    cl::cat(GICombinerOptionCategory),\n"
     << "    cl::callback([](const std::string &Str) {\n"
     << "      " << Name << "Option.push_back(Str);\n"
     << "    }));\n"
     << "static cl::list<std::string> " << Name << "OnlyEnableOption(\n"
     << "    \"" << Name.lower() << "-only-enable-rule\",\n"
     << "    cl::desc(\"Disable all rules in the " << Name
     << " pass then re-enable the specified ones\"),\n"
     << "    cl::Hidden,\n"
     << "    cl::cat(GICombinerOptionCategory),\n"
     << "    cl::callback([](const std::string &CommaSeparatedArg) {\n"
     << "      StringRef Str = CommaSeparatedArg;\n"
     << "      " << Name << "Option.push_back(\"*\");\n"
     << "      do {\n"
     << "        auto X = Str.split(\",\");\n"
     << "        " << Name << "Option.push_back((\"!\" + X.first).str());\n"
     << "        Str = X.second;\n"
     << "      } while (!Str.empty());\n"
     << "    }));\n"
     << "\n\n"
     << "bool " << getRuleConfigClassName()
     << "::isRuleEnabled(unsigned RuleID) const {\n"
     << "    return  !DisabledRules.test(RuleID);\n"
     << "}\n"
     << "bool " << getRuleConfigClassName() << "::parseCommandLineOption() {\n"
     << "  for (StringRef Identifier : " << Name << "Option) {\n"
     << "    bool Enabled = Identifier.consume_front(\"!\");\n"
     << "    if (Enabled && !setRuleEnabled(Identifier))\n"
     << "      return false;\n"
     << "    if (!Enabled && !setRuleDisabled(Identifier))\n"
     << "      return false;\n"
     << "  }\n"
     << "  return true;\n"
     << "}\n\n";
}

void GICombinerEmitter::emitAdditionalImpl(raw_ostream &OS) {
  OS << "bool " << getClassName() << "::" << getCombineAllMethodName()
     << "(MachineInstr &I) const {\n"
     << "  const TargetSubtargetInfo &ST = MF.getSubtarget();\n"
     << "  const PredicateBitset AvailableFeatures = "
        "getAvailableFeatures();\n"
     << "  B.setInstrAndDebugLoc(I);\n"
     << "  State.MIs.clear();\n"
     << "  State.MIs.push_back(&I);\n"
     << "  " << MatchDataInfo::StructName << " = "
     << MatchDataInfo::StructTypeName << "();\n\n"
     << "  if (executeMatchTable(*this, State, ExecInfo, B"
     << ", getMatchTable(), *ST.getInstrInfo(), MRI, "
        "*MRI.getTargetRegisterInfo(), *ST.getRegBankInfo(), AvailableFeatures"
     << ", /*CoverageInfo*/ nullptr)) {\n"
     << "    return true;\n"
     << "  }\n\n"
     << "  return false;\n"
     << "}\n\n";
}

void GICombinerEmitter::emitMIPredicateFns(raw_ostream &OS) {
  auto MatchCode = CXXPredicateCode::getAllMatchCode();
  emitMIPredicateFnsImpl<const CXXPredicateCode *>(
      OS, "", ArrayRef<const CXXPredicateCode *>(MatchCode),
      [](const CXXPredicateCode *C) -> StringRef { return C->BaseEnumName; },
      [](const CXXPredicateCode *C) -> StringRef { return C->Code; });
}

void GICombinerEmitter::emitI64ImmPredicateFns(raw_ostream &OS) {
  // Unused, but still needs to be called.
  emitImmPredicateFnsImpl<unsigned>(
      OS, "I64", "int64_t", {}, [](unsigned) { return ""; },
      [](unsigned) { return ""; });
}

void GICombinerEmitter::emitAPFloatImmPredicateFns(raw_ostream &OS) {
  // Unused, but still needs to be called.
  emitImmPredicateFnsImpl<unsigned>(
      OS, "APFloat", "const APFloat &", {}, [](unsigned) { return ""; },
      [](unsigned) { return ""; });
}

void GICombinerEmitter::emitAPIntImmPredicateFns(raw_ostream &OS) {
  // Unused, but still needs to be called.
  emitImmPredicateFnsImpl<unsigned>(
      OS, "APInt", "const APInt &", {}, [](unsigned) { return ""; },
      [](unsigned) { return ""; });
}

void GICombinerEmitter::emitTestSimplePredicate(raw_ostream &OS) {
  if (!AllCombineRules.empty()) {
    OS << "enum {\n";
    std::string EnumeratorSeparator = " = GICXXPred_Invalid + 1,\n";
    // To avoid emitting a switch, we expect that all those rules are in order.
    // That way we can just get the RuleID from the enum by subtracting
    // (GICXXPred_Invalid + 1).
    unsigned ExpectedID = 0;
    (void)ExpectedID;
    for (const auto &ID : keys(AllCombineRules)) {
      assert(ExpectedID++ == ID && "combine rules are not ordered!");
      OS << "  " << getIsEnabledPredicateEnumName(ID) << EnumeratorSeparator;
      EnumeratorSeparator = ",\n";
    }
    OS << "};\n\n";
  }

  OS << "bool " << getClassName()
     << "::testSimplePredicate(unsigned Predicate) const {\n"
     << "    return RuleConfig.isRuleEnabled(Predicate - "
        "GICXXPred_Invalid - "
        "1);\n"
     << "}\n";
}

void GICombinerEmitter::emitRunCustomAction(raw_ostream &OS) {
  const auto ApplyCode = CXXPredicateCode::getAllApplyCode();

  if (!ApplyCode.empty()) {
    OS << "enum {\n";
    std::string EnumeratorSeparator = " = GICXXCustomAction_Invalid + 1,\n";
    for (const auto &Apply : ApplyCode) {
      OS << "  " << Apply->getEnumNameWithPrefix(CXXApplyPrefix)
         << EnumeratorSeparator;
      EnumeratorSeparator = ",\n";
    }
    OS << "};\n";
  }

  OS << "void " << getClassName()
     << "::runCustomAction(unsigned ApplyID, const MatcherState &State, "
        "NewMIVector &OutMIs) const "
        "{\n";
  if (!ApplyCode.empty()) {
    OS << "  switch(ApplyID) {\n";
    for (const auto &Apply : ApplyCode) {
      OS << "  case " << Apply->getEnumNameWithPrefix(CXXApplyPrefix) << ":{\n"
         << "    " << join(split(Apply->Code, '\n'), "\n    ") << '\n'
         << "    return;\n";
      OS << "  }\n";
    }
    OS << "}\n";
  }
  OS << "  llvm_unreachable(\"Unknown Apply Action\");\n"
     << "}\n";
}

void GICombinerEmitter::emitAdditionalTemporariesDecl(raw_ostream &OS,
                                                      StringRef Indent) {
  OS << Indent << "struct " << MatchDataInfo::StructTypeName << " {\n";
  for (const auto &[Type, VarNames] : AllMatchDataVars) {
    assert(!VarNames.empty() && "Cannot have no vars for this type!");
    OS << Indent << "  " << Type << " " << join(VarNames, ", ") << ";\n";
  }
  OS << Indent << "};\n"
     << Indent << "mutable " << MatchDataInfo::StructTypeName << " "
     << MatchDataInfo::StructName << ";\n\n";
}

GICombinerEmitter::GICombinerEmitter(RecordKeeper &RK,
                                     const CodeGenTarget &Target,
                                     StringRef Name, Record *Combiner)
    : Records(RK), Name(Name), Target(Target), Combiner(Combiner) {}

MatchTable
GICombinerEmitter::buildMatchTable(MutableArrayRef<RuleMatcher> Rules) {
  std::vector<Matcher *> InputRules;
  for (Matcher &Rule : Rules)
    InputRules.push_back(&Rule);

  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.count(Opcode) == 0)
      OpcodeOrder[Opcode] = CurrentOrdering++;
  }

  llvm::stable_sort(InputRules, [&OpcodeOrder](const Matcher *A,
                                               const Matcher *B) {
    auto *L = static_cast<const RuleMatcher *>(A);
    auto *R = static_cast<const RuleMatcher *>(B);
    return std::make_tuple(OpcodeOrder[L->getOpcode()], L->getNumOperands()) <
           std::make_tuple(OpcodeOrder[R->getOpcode()], R->getNumOperands());
  });

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

  std::vector<std::unique_ptr<Matcher>> MatcherStorage;
  std::vector<Matcher *> OptRules =
      optimizeRules<GroupMatcher>(InputRules, MatcherStorage);

  for (Matcher *Rule : OptRules)
    Rule->optimize();

  OptRules = optimizeRules<SwitchMatcher>(OptRules, MatcherStorage);

  return MatchTable::buildTable(OptRules, /*WithCoverage*/ false,
                                /*IsCombiner*/ true);
}

/// Recurse into GICombineGroup's and flatten the ruleset into a simple list.
void GICombinerEmitter::gatherRules(
    std::vector<RuleMatcher> &ActiveRules,
    const std::vector<Record *> &&RulesAndGroups) {
  for (Record *Rec : RulesAndGroups) {
    if (!Rec->isValueUnset("Rules")) {
      gatherRules(ActiveRules, Rec->getValueAsListOfDefs("Rules"));
      continue;
    }

    StringRef RuleName = Rec->getName();
    if (!RulesSeen.insert(RuleName).second) {
      PrintWarning(Rec->getLoc(),
                   "skipping rule '" + Rec->getName() +
                       "' because it has already been processed");
      continue;
    }

    AllCombineRules.emplace_back(NextRuleID, Rec->getName().str());
    CombineRuleBuilder CRB(Target, SubtargetFeatures, *Rec, NextRuleID++,
                           ActiveRules);

    if (!CRB.parseAll()) {
      assert(ErrorsPrinted && "Parsing failed without errors!");
      continue;
    }

    if (StopAfterParse) {
      CRB.print(outs());
      continue;
    }

    if (!CRB.emitRuleMatchers()) {
      assert(ErrorsPrinted && "Emission failed without errors!");
      continue;
    }
  }
}

void GICombinerEmitter::run(raw_ostream &OS) {
  InstructionOpcodeMatcher::initOpcodeValuesMap(Target);
  LLTOperandMatcher::initTypeIDValuesMap();

  Records.startTimer("Gather rules");
  std::vector<RuleMatcher> Rules;
  gatherRules(Rules, Combiner->getValueAsListOfDefs("Rules"));
  if (ErrorsPrinted)
    PrintFatalError(Combiner->getLoc(), "Failed to parse one or more rules");

  if (StopAfterParse)
    return;

  Records.startTimer("Creating Match Table");
  unsigned MaxTemporaries = 0;
  for (const auto &Rule : Rules)
    MaxTemporaries = std::max(MaxTemporaries, Rule.countRendererFns());

  llvm::stable_sort(Rules, [&](const RuleMatcher &A, const RuleMatcher &B) {
    if (A.isHigherPriorityThan(B)) {
      assert(!B.isHigherPriorityThan(A) && "Cannot be more important "
                                           "and less important at "
                                           "the same time");
      return true;
    }
    return false;
  });

  const MatchTable Table = buildMatchTable(Rules);

  Records.startTimer("Emit combiner");

  emitSourceFileHeader(getClassName().str() + " Combiner Match Table", OS);

  // Unused
  std::vector<StringRef> CustomRendererFns;
  // Unused
  std::vector<Record *> ComplexPredicates;

  SmallVector<LLTCodeGen, 16> TypeObjects;
  append_range(TypeObjects, KnownTypes);
  llvm::sort(TypeObjects);

  // Hack: Avoid empty declarator.
  if (TypeObjects.empty())
    TypeObjects.push_back(LLT::scalar(1));

  // GET_GICOMBINER_DEPS, which pulls in extra dependencies.
  OS << "#ifdef GET_GICOMBINER_DEPS\n"
     << "#include \"llvm/ADT/SparseBitVector.h\"\n"
     << "namespace llvm {\n"
     << "extern cl::OptionCategory GICombinerOptionCategory;\n"
     << "} // end namespace llvm\n"
     << "#endif // ifdef GET_GICOMBINER_DEPS\n\n";

  // GET_GICOMBINER_TYPES, which needs to be included before the declaration of
  // the class.
  OS << "#ifdef GET_GICOMBINER_TYPES\n";
  emitRuleConfigImpl(OS);
  OS << "#endif // ifdef GET_GICOMBINER_TYPES\n\n";
  emitPredicateBitset(OS, "GET_GICOMBINER_TYPES");

  // GET_GICOMBINER_CLASS_MEMBERS, which need to be included inside the class.
  emitPredicatesDecl(OS, "GET_GICOMBINER_CLASS_MEMBERS");
  emitTemporariesDecl(OS, "GET_GICOMBINER_CLASS_MEMBERS");

  // GET_GICOMBINER_IMPL, which needs to be included outside the class.
  emitExecutorImpl(OS, Table, TypeObjects, Rules, ComplexPredicates,
                   CustomRendererFns, "GET_GICOMBINER_IMPL");

  // GET_GICOMBINER_CONSTRUCTOR_INITS, which are in the constructor's
  // initializer list.
  emitPredicatesInit(OS, "GET_GICOMBINER_CONSTRUCTOR_INITS");
  emitTemporariesInit(OS, MaxTemporaries, "GET_GICOMBINER_CONSTRUCTOR_INITS");
}

} // end anonymous namespace

//===----------------------------------------------------------------------===//

static void EmitGICombiner(RecordKeeper &RK, raw_ostream &OS) {
  EnablePrettyStackTrace();
  CodeGenTarget Target(RK);

  if (SelectedCombiners.empty())
    PrintFatalError("No combiners selected with -combiners");
  for (const auto &Combiner : SelectedCombiners) {
    Record *CombinerDef = RK.getDef(Combiner);
    if (!CombinerDef)
      PrintFatalError("Could not find " + Combiner);
    GICombinerEmitter(RK, Target, Combiner, CombinerDef).run(OS);
  }
}

static TableGen::Emitter::Opt X("gen-global-isel-combiner", EmitGICombiner,
                                "Generate GlobalISel Combiner");