llvm/utils/TableGen/GlobalISelEmitter.cpp

//===- GlobalISelEmitter.cpp - Generate an instruction selector -----------===//
//
// 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
/// This tablegen backend emits code for use by the GlobalISel instruction
/// selector. See include/llvm/CodeGen/TargetGlobalISel.td.
///
/// This file analyzes the patterns recognized by the SelectionDAGISel tablegen
/// backend, filters out the ones that are unsupported, maps
/// SelectionDAG-specific constructs to their GlobalISel counterpart
/// (when applicable: MVT to LLT;  SDNode to generic Instruction).
///
/// Not all patterns are supported: pass the tablegen invocation
/// "-warn-on-skipped-patterns" to emit a warning when a pattern is skipped,
/// as well as why.
///
/// The generated file defines a single method:
///     bool <Target>InstructionSelector::selectImpl(MachineInstr &I) const;
/// intended to be used in InstructionSelector::select as the first-step
/// selector for the patterns that don't require complex C++.
///
/// FIXME: We'll probably want to eventually define a base
/// "TargetGenInstructionSelector" class.
///
//===----------------------------------------------------------------------===//

#include "CodeGenDAGPatterns.h"
#include "SubtargetFeatureInfo.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/CodeGenCoverage.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Error.h"
#include "llvm/Support/LowLevelTypeImpl.h"
#include "llvm/Support/MachineValueType.h"
#include "llvm/Support/ScopedPrinter.h"
#include "llvm/TableGen/Error.h"
#include "llvm/TableGen/Record.h"
#include "llvm/TableGen/TableGenBackend.h"
#include <numeric>
#include <string>
using namespace llvm;

#define DEBUG_TYPE "gisel-emitter"

STATISTIC(NumPatternTotal, "Total number of patterns");
STATISTIC(NumPatternImported, "Number of patterns imported from SelectionDAG");
STATISTIC(NumPatternImportsSkipped, "Number of SelectionDAG imports skipped");
STATISTIC(NumPatternsTested, "Number of patterns executed according to coverage information");
STATISTIC(NumPatternEmitted, "Number of patterns emitted");

cl::OptionCategory GlobalISelEmitterCat("Options for -gen-global-isel");

static cl::opt<bool> WarnOnSkippedPatterns(
    "warn-on-skipped-patterns",
    cl::desc("Explain why a pattern was skipped for inclusion "
             "in the GlobalISel selector"),
    cl::init(false), cl::cat(GlobalISelEmitterCat));

static cl::opt<bool> GenerateCoverage(
    "instrument-gisel-coverage",
    cl::desc("Generate coverage instrumentation for GlobalISel"),
    cl::init(false), cl::cat(GlobalISelEmitterCat));

static cl::opt<std::string> UseCoverageFile(
    "gisel-coverage-file", cl::init(""),
    cl::desc("Specify file to retrieve coverage information from"),
    cl::cat(GlobalISelEmitterCat));

static cl::opt<bool> OptimizeMatchTable(
    "optimize-match-table",
    cl::desc("Generate an optimized version of the match table"),
    cl::init(true), cl::cat(GlobalISelEmitterCat));

namespace {
//===- Helper functions ---------------------------------------------------===//

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

/// Get the opcode used to check this predicate.
std::string getMatchOpcodeForImmPredicate(const TreePredicateFn &Predicate) {
  return "GIM_Check" + Predicate.getImmTypeIdentifier().str() + "ImmPredicate";
}

/// This class stands in for LLT wherever we want to tablegen-erate an
/// equivalent at compiler run-time.
class LLTCodeGen {
private:
  LLT Ty;

public:
  LLTCodeGen() = default;
  LLTCodeGen(const LLT &Ty) : Ty(Ty) {}

  std::string getCxxEnumValue() const {
    std::string Str;
    raw_string_ostream OS(Str);

    emitCxxEnumValue(OS);
    return OS.str();
  }

  void emitCxxEnumValue(raw_ostream &OS) const {
    if (Ty.isScalar()) {
      OS << "GILLT_s" << Ty.getSizeInBits();
      return;
    }
    if (Ty.isVector()) {
      OS << (Ty.isScalable() ? "GILLT_nxv" : "GILLT_v")
         << Ty.getElementCount().getKnownMinValue() << "s"
         << Ty.getScalarSizeInBits();
      return;
    }
    if (Ty.isPointer()) {
      OS << "GILLT_p" << Ty.getAddressSpace();
      if (Ty.getSizeInBits() > 0)
        OS << "s" << Ty.getSizeInBits();
      return;
    }
    llvm_unreachable("Unhandled LLT");
  }

  void emitCxxConstructorCall(raw_ostream &OS) const {
    if (Ty.isScalar()) {
      OS << "LLT::scalar(" << Ty.getSizeInBits() << ")";
      return;
    }
    if (Ty.isVector()) {
      OS << "LLT::vector("
         << (Ty.isScalable() ? "ElementCount::getScalable("
                             : "ElementCount::getFixed(")
         << Ty.getElementCount().getKnownMinValue() << "), "
         << Ty.getScalarSizeInBits() << ")";
      return;
    }
    if (Ty.isPointer() && Ty.getSizeInBits() > 0) {
      OS << "LLT::pointer(" << Ty.getAddressSpace() << ", "
         << Ty.getSizeInBits() << ")";
      return;
    }
    llvm_unreachable("Unhandled LLT");
  }

  const LLT &get() const { return Ty; }

  /// This ordering is used for std::unique() and llvm::sort(). There's no
  /// particular logic behind the order but either A < B or B < A must be
  /// true if A != B.
  bool operator<(const LLTCodeGen &Other) const {
    if (Ty.isValid() != Other.Ty.isValid())
      return Ty.isValid() < Other.Ty.isValid();
    if (!Ty.isValid())
      return false;

    if (Ty.isVector() != Other.Ty.isVector())
      return Ty.isVector() < Other.Ty.isVector();
    if (Ty.isScalar() != Other.Ty.isScalar())
      return Ty.isScalar() < Other.Ty.isScalar();
    if (Ty.isPointer() != Other.Ty.isPointer())
      return Ty.isPointer() < Other.Ty.isPointer();

    if (Ty.isPointer() && Ty.getAddressSpace() != Other.Ty.getAddressSpace())
      return Ty.getAddressSpace() < Other.Ty.getAddressSpace();

    if (Ty.isVector() && Ty.getElementCount() != Other.Ty.getElementCount())
      return std::make_tuple(Ty.isScalable(),
                             Ty.getElementCount().getKnownMinValue()) <
             std::make_tuple(Other.Ty.isScalable(),
                             Other.Ty.getElementCount().getKnownMinValue());

    assert((!Ty.isVector() || Ty.isScalable() == Other.Ty.isScalable()) &&
           "Unexpected mismatch of scalable property");
    return Ty.isVector()
               ? std::make_tuple(Ty.isScalable(),
                                 Ty.getSizeInBits().getKnownMinSize()) <
                     std::make_tuple(Other.Ty.isScalable(),
                                     Other.Ty.getSizeInBits().getKnownMinSize())
               : Ty.getSizeInBits().getFixedSize() <
                     Other.Ty.getSizeInBits().getFixedSize();
  }

  bool operator==(const LLTCodeGen &B) const { return Ty == B.Ty; }
};

// Track all types that are used so we can emit the corresponding enum.
std::set<LLTCodeGen> KnownTypes;

class InstructionMatcher;
/// Convert an MVT to an equivalent LLT if possible, or the invalid LLT() for
/// MVTs that don't map cleanly to an LLT (e.g., iPTR, *any, ...).
static Optional<LLTCodeGen> MVTToLLT(MVT::SimpleValueType SVT) {
  MVT VT(SVT);

  if (VT.isVector() && !VT.getVectorElementCount().isScalar())
    return LLTCodeGen(
        LLT::vector(VT.getVectorElementCount(), VT.getScalarSizeInBits()));

  if (VT.isInteger() || VT.isFloatingPoint())
    return LLTCodeGen(LLT::scalar(VT.getSizeInBits()));

  return None;
}

static std::string explainPredicates(const TreePatternNode *N) {
  std::string Explanation;
  StringRef Separator = "";
  for (const TreePredicateCall &Call : N->getPredicateCalls()) {
    const TreePredicateFn &P = Call.Fn;
    Explanation +=
        (Separator + P.getOrigPatFragRecord()->getRecord()->getName()).str();
    Separator = ", ";

    if (P.isAlwaysTrue())
      Explanation += " always-true";
    if (P.isImmediatePattern())
      Explanation += " immediate";

    if (P.isUnindexed())
      Explanation += " unindexed";

    if (P.isNonExtLoad())
      Explanation += " non-extload";
    if (P.isAnyExtLoad())
      Explanation += " extload";
    if (P.isSignExtLoad())
      Explanation += " sextload";
    if (P.isZeroExtLoad())
      Explanation += " zextload";

    if (P.isNonTruncStore())
      Explanation += " non-truncstore";
    if (P.isTruncStore())
      Explanation += " truncstore";

    if (Record *VT = P.getMemoryVT())
      Explanation += (" MemVT=" + VT->getName()).str();
    if (Record *VT = P.getScalarMemoryVT())
      Explanation += (" ScalarVT(MemVT)=" + VT->getName()).str();

    if (ListInit *AddrSpaces = P.getAddressSpaces()) {
      raw_string_ostream OS(Explanation);
      OS << " AddressSpaces=[";

      StringRef AddrSpaceSeparator;
      for (Init *Val : AddrSpaces->getValues()) {
        IntInit *IntVal = dyn_cast<IntInit>(Val);
        if (!IntVal)
          continue;

        OS << AddrSpaceSeparator << IntVal->getValue();
        AddrSpaceSeparator = ", ";
      }

      OS << ']';
    }

    int64_t MinAlign = P.getMinAlignment();
    if (MinAlign > 0)
      Explanation += " MinAlign=" + utostr(MinAlign);

    if (P.isAtomicOrderingMonotonic())
      Explanation += " monotonic";
    if (P.isAtomicOrderingAcquire())
      Explanation += " acquire";
    if (P.isAtomicOrderingRelease())
      Explanation += " release";
    if (P.isAtomicOrderingAcquireRelease())
      Explanation += " acq_rel";
    if (P.isAtomicOrderingSequentiallyConsistent())
      Explanation += " seq_cst";
    if (P.isAtomicOrderingAcquireOrStronger())
      Explanation += " >=acquire";
    if (P.isAtomicOrderingWeakerThanAcquire())
      Explanation += " <acquire";
    if (P.isAtomicOrderingReleaseOrStronger())
      Explanation += " >=release";
    if (P.isAtomicOrderingWeakerThanRelease())
      Explanation += " <release";
  }
  return Explanation;
}

std::string explainOperator(Record *Operator) {
  if (Operator->isSubClassOf("SDNode"))
    return (" (" + Operator->getValueAsString("Opcode") + ")").str();

  if (Operator->isSubClassOf("Intrinsic"))
    return (" (Operator is an Intrinsic, " + Operator->getName() + ")").str();

  if (Operator->isSubClassOf("ComplexPattern"))
    return (" (Operator is an unmapped ComplexPattern, " + Operator->getName() +
            ")")
        .str();

  if (Operator->isSubClassOf("SDNodeXForm"))
    return (" (Operator is an unmapped SDNodeXForm, " + Operator->getName() +
            ")")
        .str();

  return (" (Operator " + Operator->getName() + " not understood)").str();
}

/// Helper function to let the emitter report skip reason error messages.
static Error failedImport(const Twine &Reason) {
  return make_error<StringError>(Reason, inconvertibleErrorCode());
}

static Error isTrivialOperatorNode(const TreePatternNode *N) {
  std::string Explanation;
  std::string Separator;

  bool HasUnsupportedPredicate = false;
  for (const TreePredicateCall &Call : N->getPredicateCalls()) {
    const TreePredicateFn &Predicate = Call.Fn;

    if (Predicate.isAlwaysTrue())
      continue;

    if (Predicate.isImmediatePattern())
      continue;

    if (Predicate.isNonExtLoad() || Predicate.isAnyExtLoad() ||
        Predicate.isSignExtLoad() || Predicate.isZeroExtLoad())
      continue;

    if (Predicate.isNonTruncStore() || Predicate.isTruncStore())
      continue;

    if (Predicate.isLoad() && Predicate.getMemoryVT())
      continue;

    if (Predicate.isLoad() || Predicate.isStore()) {
      if (Predicate.isUnindexed())
        continue;
    }

    if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
      const ListInit *AddrSpaces = Predicate.getAddressSpaces();
      if (AddrSpaces && !AddrSpaces->empty())
        continue;

      if (Predicate.getMinAlignment() > 0)
        continue;
    }

    if (Predicate.isAtomic() && Predicate.getMemoryVT())
      continue;

    if (Predicate.isAtomic() &&
        (Predicate.isAtomicOrderingMonotonic() ||
         Predicate.isAtomicOrderingAcquire() ||
         Predicate.isAtomicOrderingRelease() ||
         Predicate.isAtomicOrderingAcquireRelease() ||
         Predicate.isAtomicOrderingSequentiallyConsistent() ||
         Predicate.isAtomicOrderingAcquireOrStronger() ||
         Predicate.isAtomicOrderingWeakerThanAcquire() ||
         Predicate.isAtomicOrderingReleaseOrStronger() ||
         Predicate.isAtomicOrderingWeakerThanRelease()))
      continue;

    if (Predicate.hasGISelPredicateCode())
      continue;

    HasUnsupportedPredicate = true;
    Explanation = Separator + "Has a predicate (" + explainPredicates(N) + ")";
    Separator = ", ";
    Explanation += (Separator + "first-failing:" +
                    Predicate.getOrigPatFragRecord()->getRecord()->getName())
                       .str();
    break;
  }

  if (!HasUnsupportedPredicate)
    return Error::success();

  return failedImport(Explanation);
}

static Record *getInitValueAsRegClass(Init *V) {
  if (DefInit *VDefInit = dyn_cast<DefInit>(V)) {
    if (VDefInit->getDef()->isSubClassOf("RegisterOperand"))
      return VDefInit->getDef()->getValueAsDef("RegClass");
    if (VDefInit->getDef()->isSubClassOf("RegisterClass"))
      return VDefInit->getDef();
  }
  return nullptr;
}

std::string
getNameForFeatureBitset(const std::vector<Record *> &FeatureBitset) {
  std::string Name = "GIFBS";
  for (const auto &Feature : FeatureBitset)
    Name += ("_" + Feature->getName()).str();
  return Name;
}

static std::string getScopedName(unsigned Scope, const std::string &Name) {
  return ("pred:" + Twine(Scope) + ":" + Name).str();
}

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

class MatchTable;

/// A record to be stored in a MatchTable.
///
/// This class represents any and all output that may be required to emit the
/// MatchTable. Instances  are most often configured to represent an opcode or
/// value that will be emitted to the table with some formatting but it can also
/// represent commas, comments, and other formatting instructions.
struct MatchTableRecord {
  enum RecordFlagsBits {
    MTRF_None = 0x0,
    /// Causes EmitStr to be formatted as comment when emitted.
    MTRF_Comment = 0x1,
    /// Causes the record value to be followed by a comma when emitted.
    MTRF_CommaFollows = 0x2,
    /// Causes the record value to be followed by a line break when emitted.
    MTRF_LineBreakFollows = 0x4,
    /// Indicates that the record defines a label and causes an additional
    /// comment to be emitted containing the index of the label.
    MTRF_Label = 0x8,
    /// Causes the record to be emitted as the index of the label specified by
    /// LabelID along with a comment indicating where that label is.
    MTRF_JumpTarget = 0x10,
    /// Causes the formatter to add a level of indentation before emitting the
    /// record.
    MTRF_Indent = 0x20,
    /// Causes the formatter to remove a level of indentation after emitting the
    /// record.
    MTRF_Outdent = 0x40,
  };

  /// When MTRF_Label or MTRF_JumpTarget is used, indicates a label id to
  /// reference or define.
  unsigned LabelID;
  /// The string to emit. Depending on the MTRF_* flags it may be a comment, a
  /// value, a label name.
  std::string EmitStr;

private:
  /// The number of MatchTable elements described by this record. Comments are 0
  /// while values are typically 1. Values >1 may occur when we need to emit
  /// values that exceed the size of a MatchTable element.
  unsigned NumElements;

public:
  /// A bitfield of RecordFlagsBits flags.
  unsigned Flags;

  /// The actual run-time value, if known
  int64_t RawValue;

  MatchTableRecord(Optional<unsigned> LabelID_, StringRef EmitStr,
                   unsigned NumElements, unsigned Flags,
                   int64_t RawValue = std::numeric_limits<int64_t>::min())
      : LabelID(LabelID_.getValueOr(~0u)), EmitStr(EmitStr),
        NumElements(NumElements), Flags(Flags), RawValue(RawValue) {
    assert((!LabelID_.hasValue() || LabelID != ~0u) &&
           "This value is reserved for non-labels");
  }
  MatchTableRecord(const MatchTableRecord &Other) = default;
  MatchTableRecord(MatchTableRecord &&Other) = default;

  /// Useful if a Match Table Record gets optimized out
  void turnIntoComment() {
    Flags |= MTRF_Comment;
    Flags &= ~MTRF_CommaFollows;
    NumElements = 0;
  }

  /// For Jump Table generation purposes
  bool operator<(const MatchTableRecord &Other) const {
    return RawValue < Other.RawValue;
  }
  int64_t getRawValue() const { return RawValue; }

  void emit(raw_ostream &OS, bool LineBreakNextAfterThis,
            const MatchTable &Table) const;
  unsigned size() const { return NumElements; }
};

class Matcher;

/// Holds the contents of a generated MatchTable to enable formatting and the
/// necessary index tracking needed to support GIM_Try.
class MatchTable {
  /// An unique identifier for the table. The generated table will be named
  /// MatchTable${ID}.
  unsigned ID;
  /// The records that make up the table. Also includes comments describing the
  /// values being emitted and line breaks to format it.
  std::vector<MatchTableRecord> Contents;
  /// The currently defined labels.
  DenseMap<unsigned, unsigned> LabelMap;
  /// Tracks the sum of MatchTableRecord::NumElements as the table is built.
  unsigned CurrentSize = 0;
  /// A unique identifier for a MatchTable label.
  unsigned CurrentLabelID = 0;
  /// Determines if the table should be instrumented for rule coverage tracking.
  bool IsWithCoverage;

public:
  static MatchTableRecord LineBreak;
  static MatchTableRecord Comment(StringRef Comment) {
    return MatchTableRecord(None, Comment, 0, MatchTableRecord::MTRF_Comment);
  }
  static MatchTableRecord Opcode(StringRef Opcode, int IndentAdjust = 0) {
    unsigned ExtraFlags = 0;
    if (IndentAdjust > 0)
      ExtraFlags |= MatchTableRecord::MTRF_Indent;
    if (IndentAdjust < 0)
      ExtraFlags |= MatchTableRecord::MTRF_Outdent;

    return MatchTableRecord(None, Opcode, 1,
                            MatchTableRecord::MTRF_CommaFollows | ExtraFlags);
  }
  static MatchTableRecord NamedValue(StringRef NamedValue) {
    return MatchTableRecord(None, NamedValue, 1,
                            MatchTableRecord::MTRF_CommaFollows);
  }
  static MatchTableRecord NamedValue(StringRef NamedValue, int64_t RawValue) {
    return MatchTableRecord(None, NamedValue, 1,
                            MatchTableRecord::MTRF_CommaFollows, RawValue);
  }
  static MatchTableRecord NamedValue(StringRef Namespace,
                                     StringRef NamedValue) {
    return MatchTableRecord(None, (Namespace + "::" + NamedValue).str(), 1,
                            MatchTableRecord::MTRF_CommaFollows);
  }
  static MatchTableRecord NamedValue(StringRef Namespace, StringRef NamedValue,
                                     int64_t RawValue) {
    return MatchTableRecord(None, (Namespace + "::" + NamedValue).str(), 1,
                            MatchTableRecord::MTRF_CommaFollows, RawValue);
  }
  static MatchTableRecord IntValue(int64_t IntValue) {
    return MatchTableRecord(None, llvm::to_string(IntValue), 1,
                            MatchTableRecord::MTRF_CommaFollows);
  }
  static MatchTableRecord Label(unsigned LabelID) {
    return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 0,
                            MatchTableRecord::MTRF_Label |
                                MatchTableRecord::MTRF_Comment |
                                MatchTableRecord::MTRF_LineBreakFollows);
  }
  static MatchTableRecord JumpTarget(unsigned LabelID) {
    return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 1,
                            MatchTableRecord::MTRF_JumpTarget |
                                MatchTableRecord::MTRF_Comment |
                                MatchTableRecord::MTRF_CommaFollows);
  }

  static MatchTable buildTable(ArrayRef<Matcher *> Rules, bool WithCoverage);

  MatchTable(bool WithCoverage, unsigned ID = 0)
      : ID(ID), IsWithCoverage(WithCoverage) {}

  bool isWithCoverage() const { return IsWithCoverage; }

  void push_back(const MatchTableRecord &Value) {
    if (Value.Flags & MatchTableRecord::MTRF_Label)
      defineLabel(Value.LabelID);
    Contents.push_back(Value);
    CurrentSize += Value.size();
  }

  unsigned allocateLabelID() { return CurrentLabelID++; }

  void defineLabel(unsigned LabelID) {
    LabelMap.insert(std::make_pair(LabelID, CurrentSize));
  }

  unsigned getLabelIndex(unsigned LabelID) const {
    const auto I = LabelMap.find(LabelID);
    assert(I != LabelMap.end() && "Use of undeclared label");
    return I->second;
  }

  void emitUse(raw_ostream &OS) const { OS << "MatchTable" << ID; }

  void emitDeclaration(raw_ostream &OS) const {
    unsigned Indentation = 4;
    OS << "  constexpr static int64_t MatchTable" << ID << "[] = {";
    LineBreak.emit(OS, true, *this);
    OS << std::string(Indentation, ' ');

    for (auto I = Contents.begin(), E = Contents.end(); I != E;
         ++I) {
      bool LineBreakIsNext = false;
      const auto &NextI = std::next(I);

      if (NextI != E) {
        if (NextI->EmitStr == "" &&
            NextI->Flags == MatchTableRecord::MTRF_LineBreakFollows)
          LineBreakIsNext = true;
      }

      if (I->Flags & MatchTableRecord::MTRF_Indent)
        Indentation += 2;

      I->emit(OS, LineBreakIsNext, *this);
      if (I->Flags & MatchTableRecord::MTRF_LineBreakFollows)
        OS << std::string(Indentation, ' ');

      if (I->Flags & MatchTableRecord::MTRF_Outdent)
        Indentation -= 2;
    }
    OS << "};\n";
  }
};

MatchTableRecord MatchTable::LineBreak = {
    None, "" /* Emit String */, 0 /* Elements */,
    MatchTableRecord::MTRF_LineBreakFollows};

void MatchTableRecord::emit(raw_ostream &OS, bool LineBreakIsNextAfterThis,
                            const MatchTable &Table) const {
  bool UseLineComment =
      LineBreakIsNextAfterThis || (Flags & MTRF_LineBreakFollows);
  if (Flags & (MTRF_JumpTarget | MTRF_CommaFollows))
    UseLineComment = false;

  if (Flags & MTRF_Comment)
    OS << (UseLineComment ? "// " : "/*");

  OS << EmitStr;
  if (Flags & MTRF_Label)
    OS << ": @" << Table.getLabelIndex(LabelID);

  if ((Flags & MTRF_Comment) && !UseLineComment)
    OS << "*/";

  if (Flags & MTRF_JumpTarget) {
    if (Flags & MTRF_Comment)
      OS << " ";
    OS << Table.getLabelIndex(LabelID);
  }

  if (Flags & MTRF_CommaFollows) {
    OS << ",";
    if (!LineBreakIsNextAfterThis && !(Flags & MTRF_LineBreakFollows))
      OS << " ";
  }

  if (Flags & MTRF_LineBreakFollows)
    OS << "\n";
}

MatchTable &operator<<(MatchTable &Table, const MatchTableRecord &Value) {
  Table.push_back(Value);
  return Table;
}

//===- Matchers -----------------------------------------------------------===//

class OperandMatcher;
class MatchAction;
class PredicateMatcher;
class RuleMatcher;

class Matcher {
public:
  virtual ~Matcher() = default;
  virtual void optimize() {}
  virtual void emit(MatchTable &Table) = 0;

  virtual bool hasFirstCondition() const = 0;
  virtual const PredicateMatcher &getFirstCondition() const = 0;
  virtual std::unique_ptr<PredicateMatcher> popFirstCondition() = 0;
};

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

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

class GroupMatcher final : public Matcher {
  /// Conditions that form a common prefix of all the matchers contained.
  SmallVector<std::unique_ptr<PredicateMatcher>, 1> Conditions;

  /// All the nested matchers, sharing a common prefix.
  std::vector<Matcher *> Matchers;

  /// An owning collection for any auxiliary matchers created while optimizing
  /// nested matchers contained.
  std::vector<std::unique_ptr<Matcher>> MatcherStorage;

public:
  /// Add a matcher to the collection of nested matchers if it meets the
  /// requirements, and return true. If it doesn't, do nothing and return false.
  ///
  /// Expected to preserve its argument, so it could be moved out later on.
  bool addMatcher(Matcher &Candidate);

  /// Mark the matcher as fully-built and ensure any invariants expected by both
  /// optimize() and emit(...) methods. Generally, both sequences of calls
  /// are expected to lead to a sensible result:
  ///
  /// addMatcher(...)*; finalize(); optimize(); emit(...); and
  /// addMatcher(...)*; finalize(); emit(...);
  ///
  /// or generally
  ///
  /// addMatcher(...)*; finalize(); { optimize()*; emit(...); }*
  ///
  /// Multiple calls to optimize() are expected to be handled gracefully, though
  /// optimize() is not expected to be idempotent. Multiple calls to finalize()
  /// aren't generally supported. emit(...) is expected to be non-mutating and
  /// producing the exact same results upon repeated calls.
  ///
  /// addMatcher() calls after the finalize() call are not supported.
  ///
  /// finalize() and optimize() are both allowed to mutate the contained
  /// matchers, so moving them out after finalize() is not supported.
  void finalize();
  void optimize() override;
  void emit(MatchTable &Table) override;

  /// Could be used to move out the matchers added previously, unless finalize()
  /// has been already called. If any of the matchers are moved out, the group
  /// becomes safe to destroy, but not safe to re-use for anything else.
  iterator_range<std::vector<Matcher *>::iterator> matchers() {
    return make_range(Matchers.begin(), Matchers.end());
  }
  size_t size() const { return Matchers.size(); }
  bool empty() const { return Matchers.empty(); }

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

private:
  /// See if a candidate matcher could be added to this group solely by
  /// analyzing its first condition.
  bool candidateConditionMatches(const PredicateMatcher &Predicate) const;
};

class SwitchMatcher : public Matcher {
  /// All the nested matchers, representing distinct switch-cases. The first
  /// conditions (as Matcher::getFirstCondition() reports) of all the nested
  /// matchers must share the same type and path to a value they check, in other
  /// words, be isIdenticalDownToValue, but have different values they check
  /// against.
  std::vector<Matcher *> Matchers;

  /// The representative condition, with a type and a path (InsnVarID and OpIdx
  /// in most cases)  shared by all the matchers contained.
  std::unique_ptr<PredicateMatcher> Condition = nullptr;

  /// Temporary set used to check that the case values don't repeat within the
  /// same switch.
  std::set<MatchTableRecord> Values;

  /// An owning collection for any auxiliary matchers created while optimizing
  /// nested matchers contained.
  std::vector<std::unique_ptr<Matcher>> MatcherStorage;

public:
  bool addMatcher(Matcher &Candidate);

  void finalize();
  void emit(MatchTable &Table) override;

  iterator_range<std::vector<Matcher *>::iterator> matchers() {
    return make_range(Matchers.begin(), Matchers.end());
  }
  size_t size() const { return Matchers.size(); }
  bool empty() const { return Matchers.empty(); }

  std::unique_ptr<PredicateMatcher> popFirstCondition() override {
    // SwitchMatcher doesn't have a common first condition for its cases, as all
    // the cases only share a kind of a value (a type and a path to it) they
    // match, but deliberately differ in the actual value they match.
    llvm_unreachable("Trying to pop a condition from a condition-less group");
  }
  const PredicateMatcher &getFirstCondition() const override {
    llvm_unreachable("Trying to pop a condition from a condition-less group");
  }
  bool hasFirstCondition() const override { return false; }

private:
  /// See if the predicate type has a Switch-implementation for it.
  static bool isSupportedPredicateType(const PredicateMatcher &Predicate);

  bool candidateConditionMatches(const PredicateMatcher &Predicate) const;

  /// emit()-helper
  static void emitPredicateSpecificOpcodes(const PredicateMatcher &P,
                                           MatchTable &Table);
};

/// Generates code to check that a match rule matches.
class RuleMatcher : public Matcher {
public:
  using ActionList = std::list<std::unique_ptr<MatchAction>>;
  using action_iterator = ActionList::iterator;

protected:
  /// A list of matchers that all need to succeed for the current rule to match.
  /// FIXME: This currently supports a single match position but could be
  /// extended to support multiple positions to support div/rem fusion or
  /// load-multiple instructions.
  using MatchersTy = std::vector<std::unique_ptr<InstructionMatcher>> ;
  MatchersTy Matchers;

  /// A list of actions that need to be taken when all predicates in this rule
  /// have succeeded.
  ActionList Actions;

  using DefinedInsnVariablesMap = std::map<InstructionMatcher *, unsigned>;

  /// A map of instruction matchers to the local variables
  DefinedInsnVariablesMap InsnVariableIDs;

  using MutatableInsnSet = SmallPtrSet<InstructionMatcher *, 4>;

  // The set of instruction matchers that have not yet been claimed for mutation
  // by a BuildMI.
  MutatableInsnSet MutatableInsns;

  /// A map of named operands defined by the matchers that may be referenced by
  /// the renderers.
  StringMap<OperandMatcher *> DefinedOperands;

  /// A map of anonymous physical register operands defined by the matchers that
  /// may be referenced by the renderers.
  DenseMap<Record *, OperandMatcher *> PhysRegOperands;

  /// ID for the next instruction variable defined with implicitlyDefineInsnVar()
  unsigned NextInsnVarID;

  /// ID for the next output instruction allocated with allocateOutputInsnID()
  unsigned NextOutputInsnID;

  /// ID for the next temporary register ID allocated with allocateTempRegID()
  unsigned NextTempRegID;

  std::vector<Record *> RequiredFeatures;
  std::vector<std::unique_ptr<PredicateMatcher>> EpilogueMatchers;

  ArrayRef<SMLoc> SrcLoc;

  typedef std::tuple<Record *, unsigned, unsigned>
      DefinedComplexPatternSubOperand;
  typedef StringMap<DefinedComplexPatternSubOperand>
      DefinedComplexPatternSubOperandMap;
  /// A map of Symbolic Names to ComplexPattern sub-operands.
  DefinedComplexPatternSubOperandMap ComplexSubOperands;
  /// A map used to for multiple referenced error check of ComplexSubOperand.
  /// ComplexSubOperand can't be referenced multiple from different operands,
  /// however multiple references from same operand are allowed since that is
  /// how 'same operand checks' are generated.
  StringMap<std::string> ComplexSubOperandsParentName;

  uint64_t RuleID;
  static uint64_t NextRuleID;

public:
  RuleMatcher(ArrayRef<SMLoc> SrcLoc)
      : Matchers(), Actions(), InsnVariableIDs(), MutatableInsns(),
        DefinedOperands(), NextInsnVarID(0), NextOutputInsnID(0),
        NextTempRegID(0), SrcLoc(SrcLoc), ComplexSubOperands(),
        RuleID(NextRuleID++) {}
  RuleMatcher(RuleMatcher &&Other) = default;
  RuleMatcher &operator=(RuleMatcher &&Other) = default;

  uint64_t getRuleID() const { return RuleID; }

  InstructionMatcher &addInstructionMatcher(StringRef SymbolicName);
  void addRequiredFeature(Record *Feature);
  const std::vector<Record *> &getRequiredFeatures() const;

  template <class Kind, class... Args> Kind &addAction(Args &&... args);
  template <class Kind, class... Args>
  action_iterator insertAction(action_iterator InsertPt, Args &&... args);

  /// Define an instruction without emitting any code to do so.
  unsigned implicitlyDefineInsnVar(InstructionMatcher &Matcher);

  unsigned getInsnVarID(InstructionMatcher &InsnMatcher) const;
  DefinedInsnVariablesMap::const_iterator defined_insn_vars_begin() const {
    return InsnVariableIDs.begin();
  }
  DefinedInsnVariablesMap::const_iterator defined_insn_vars_end() const {
    return InsnVariableIDs.end();
  }
  iterator_range<typename DefinedInsnVariablesMap::const_iterator>
  defined_insn_vars() const {
    return make_range(defined_insn_vars_begin(), defined_insn_vars_end());
  }

  MutatableInsnSet::const_iterator mutatable_insns_begin() const {
    return MutatableInsns.begin();
  }
  MutatableInsnSet::const_iterator mutatable_insns_end() const {
    return MutatableInsns.end();
  }
  iterator_range<typename MutatableInsnSet::const_iterator>
  mutatable_insns() const {
    return make_range(mutatable_insns_begin(), mutatable_insns_end());
  }
  void reserveInsnMatcherForMutation(InstructionMatcher *InsnMatcher) {
    bool R = MutatableInsns.erase(InsnMatcher);
    assert(R && "Reserving a mutatable insn that isn't available");
    (void)R;
  }

  action_iterator actions_begin() { return Actions.begin(); }
  action_iterator actions_end() { return Actions.end(); }
  iterator_range<action_iterator> actions() {
    return make_range(actions_begin(), actions_end());
  }

  void defineOperand(StringRef SymbolicName, OperandMatcher &OM);

  void definePhysRegOperand(Record *Reg, OperandMatcher &OM);

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

    ComplexSubOperands[SymbolicName] =
        std::make_tuple(ComplexPattern, RendererID, SubOperandID);
    ComplexSubOperandsParentName[SymbolicName] = ParentName;

    return Error::success();
  }

  Optional<DefinedComplexPatternSubOperand>
  getComplexSubOperand(StringRef SymbolicName) const {
    const auto &I = ComplexSubOperands.find(SymbolicName);
    if (I == ComplexSubOperands.end())
      return None;
    return I->second;
  }

  InstructionMatcher &getInstructionMatcher(StringRef SymbolicName) const;
  const OperandMatcher &getOperandMatcher(StringRef Name) const;
  const OperandMatcher &getPhysRegOperandMatcher(Record *) const;

  void optimize() override;
  void emit(MatchTable &Table) override;

  /// Compare the priority of this object and B.
  ///
  /// Returns true if this object is more important than B.
  bool isHigherPriorityThan(const RuleMatcher &B) const;

  /// Report the maximum number of temporary operands needed by the rule
  /// matcher.
  unsigned countRendererFns() const;

  std::unique_ptr<PredicateMatcher> popFirstCondition() override;
  const PredicateMatcher &getFirstCondition() const override;
  LLTCodeGen getFirstConditionAsRootType();
  bool hasFirstCondition() const override;
  unsigned getNumOperands() const;
  StringRef getOpcode() const;

  // FIXME: Remove this as soon as possible
  InstructionMatcher &insnmatchers_front() const { return *Matchers.front(); }

  unsigned allocateOutputInsnID() { return NextOutputInsnID++; }
  unsigned allocateTempRegID() { return NextTempRegID++; }

  iterator_range<MatchersTy::iterator> insnmatchers() {
    return make_range(Matchers.begin(), Matchers.end());
  }
  bool insnmatchers_empty() const { return Matchers.empty(); }
  void insnmatchers_pop_front() { Matchers.erase(Matchers.begin()); }
};

uint64_t RuleMatcher::NextRuleID = 0;

using action_iterator = RuleMatcher::action_iterator;

template <class PredicateTy> class PredicateListMatcher {
private:
  /// Template instantiations should specialize this to return a string to use
  /// for the comment emitted when there are no predicates.
  std::string getNoPredicateComment() const;

protected:
  using PredicatesTy = std::deque<std::unique_ptr<PredicateTy>>;
  PredicatesTy Predicates;

  /// Track if the list of predicates was manipulated by one of the optimization
  /// methods.
  bool Optimized = false;

public:
  typename PredicatesTy::iterator predicates_begin() {
    return Predicates.begin();
  }
  typename PredicatesTy::iterator predicates_end() {
    return Predicates.end();
  }
  iterator_range<typename PredicatesTy::iterator> predicates() {
    return make_range(predicates_begin(), predicates_end());
  }
  typename PredicatesTy::size_type predicates_size() const {
    return Predicates.size();
  }
  bool predicates_empty() const { return Predicates.empty(); }

  std::unique_ptr<PredicateTy> predicates_pop_front() {
    std::unique_ptr<PredicateTy> Front = std::move(Predicates.front());
    Predicates.pop_front();
    Optimized = true;
    return Front;
  }

  void prependPredicate(std::unique_ptr<PredicateTy> &&Predicate) {
    Predicates.push_front(std::move(Predicate));
  }

  void eraseNullPredicates() {
    const auto NewEnd =
        std::stable_partition(Predicates.begin(), Predicates.end(),
                              std::logical_not<std::unique_ptr<PredicateTy>>());
    if (NewEnd != Predicates.begin()) {
      Predicates.erase(Predicates.begin(), NewEnd);
      Optimized = true;
    }
  }

  /// Emit MatchTable opcodes that tests whether all the predicates are met.
  template <class... Args>
  void emitPredicateListOpcodes(MatchTable &Table, Args &&... args) {
    if (Predicates.empty() && !Optimized) {
      Table << MatchTable::Comment(getNoPredicateComment())
            << MatchTable::LineBreak;
      return;
    }

    for (const auto &Predicate : predicates())
      Predicate->emitPredicateOpcodes(Table, std::forward<Args>(args)...);
  }

  /// Provide a function to avoid emitting certain predicates. This is used to
  /// defer some predicate checks until after others
  using PredicateFilterFunc = std::function<bool(const PredicateTy&)>;

  /// Emit MatchTable opcodes for predicates which satisfy \p
  /// ShouldEmitPredicate. This should be called multiple times to ensure all
  /// predicates are eventually added to the match table.
  template <class... Args>
  void emitFilteredPredicateListOpcodes(PredicateFilterFunc ShouldEmitPredicate,
                                        MatchTable &Table, Args &&... args) {
    if (Predicates.empty() && !Optimized) {
      Table << MatchTable::Comment(getNoPredicateComment())
            << MatchTable::LineBreak;
      return;
    }

    for (const auto &Predicate : predicates()) {
      if (ShouldEmitPredicate(*Predicate))
        Predicate->emitPredicateOpcodes(Table, std::forward<Args>(args)...);
    }
  }
};

class PredicateMatcher {
public:
  /// This enum is used for RTTI and also defines the priority that is given to
  /// the predicate when generating the matcher code. Kinds with higher priority
  /// must be tested first.
  ///
  /// The relative priority of OPM_LLT, OPM_RegBank, and OPM_MBB do not matter
  /// but OPM_Int must have priority over OPM_RegBank since constant integers
  /// are represented by a virtual register defined by a G_CONSTANT instruction.
  ///
  /// Note: The relative priority between IPM_ and OPM_ does not matter, they
  /// are currently not compared between each other.
  enum PredicateKind {
    IPM_Opcode,
    IPM_NumOperands,
    IPM_ImmPredicate,
    IPM_Imm,
    IPM_AtomicOrderingMMO,
    IPM_MemoryLLTSize,
    IPM_MemoryVsLLTSize,
    IPM_MemoryAddressSpace,
    IPM_MemoryAlignment,
    IPM_VectorSplatImm,
    IPM_GenericPredicate,
    OPM_SameOperand,
    OPM_ComplexPattern,
    OPM_IntrinsicID,
    OPM_CmpPredicate,
    OPM_Instruction,
    OPM_Int,
    OPM_LiteralInt,
    OPM_LLT,
    OPM_PointerToAny,
    OPM_RegBank,
    OPM_MBB,
    OPM_RecordNamedOperand,
  };

protected:
  PredicateKind Kind;
  unsigned InsnVarID;
  unsigned OpIdx;

public:
  PredicateMatcher(PredicateKind Kind, unsigned InsnVarID, unsigned OpIdx = ~0)
      : Kind(Kind), InsnVarID(InsnVarID), OpIdx(OpIdx) {}

  unsigned getInsnVarID() const { return InsnVarID; }
  unsigned getOpIdx() const { return OpIdx; }

  virtual ~PredicateMatcher() = default;
  /// Emit MatchTable opcodes that check the predicate for the given operand.
  virtual void emitPredicateOpcodes(MatchTable &Table,
                                    RuleMatcher &Rule) const = 0;

  PredicateKind getKind() const { return Kind; }

  bool dependsOnOperands() const {
    // Custom predicates really depend on the context pattern of the
    // instruction, not just the individual instruction. This therefore
    // implicitly depends on all other pattern constraints.
    return Kind == IPM_GenericPredicate;
  }

  virtual bool isIdentical(const PredicateMatcher &B) const {
    return B.getKind() == getKind() && InsnVarID == B.InsnVarID &&
           OpIdx == B.OpIdx;
  }

  virtual bool isIdenticalDownToValue(const PredicateMatcher &B) const {
    return hasValue() && PredicateMatcher::isIdentical(B);
  }

  virtual MatchTableRecord getValue() const {
    assert(hasValue() && "Can not get a value of a value-less predicate!");
    llvm_unreachable("Not implemented yet");
  }
  virtual bool hasValue() const { return false; }

  /// Report the maximum number of temporary operands needed by the predicate
  /// matcher.
  virtual unsigned countRendererFns() const { return 0; }
};

/// Generates code to check a predicate of an operand.
///
/// Typical predicates include:
/// * Operand is a particular register.
/// * Operand is assigned a particular register bank.
/// * Operand is an MBB.
class OperandPredicateMatcher : public PredicateMatcher {
public:
  OperandPredicateMatcher(PredicateKind Kind, unsigned InsnVarID,
                          unsigned OpIdx)
      : PredicateMatcher(Kind, InsnVarID, OpIdx) {}
  virtual ~OperandPredicateMatcher() {}

  /// Compare the priority of this object and B.
  ///
  /// Returns true if this object is more important than B.
  virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) const;
};

template <>
std::string
PredicateListMatcher<OperandPredicateMatcher>::getNoPredicateComment() const {
  return "No operand predicates";
}

/// Generates code to check that a register operand is defined by the same exact
/// one as another.
class SameOperandMatcher : public OperandPredicateMatcher {
  std::string MatchingName;
  unsigned OrigOpIdx;

public:
  SameOperandMatcher(unsigned InsnVarID, unsigned OpIdx, StringRef MatchingName,
                     unsigned OrigOpIdx)
      : OperandPredicateMatcher(OPM_SameOperand, InsnVarID, OpIdx),
        MatchingName(MatchingName), OrigOpIdx(OrigOpIdx) {}

  static bool classof(const PredicateMatcher *P) {
    return P->getKind() == OPM_SameOperand;
  }

  void emitPredicateOpcodes(MatchTable &Table,
                            RuleMatcher &Rule) const override;

  bool isIdentical(const PredicateMatcher &B) const override {
    return OperandPredicateMatcher::isIdentical(B) &&
           OrigOpIdx == cast<SameOperandMatcher>(&B)->OrigOpIdx &&
           MatchingName == cast<SameOperandMatcher>(&B)->MatchingName;
  }
};

/// Generates code to check that an operand is a particular LLT.
class LLTOperandMatcher : public OperandPredicateMatcher {
protected:
  LLTCodeGen Ty;

public:
  static std::map<LLTCodeGen, unsigned> TypeIDValues;

  static void initTypeIDValuesMap() {
    TypeIDValues.clear();

    unsigned ID = 0;
    for (const LLTCodeGen &LLTy : KnownTypes)
      TypeIDValues[LLTy] = ID++;
  }

  LLTOperandMatcher(unsigned InsnVarID, unsigned OpIdx, const LLTCodeGen &Ty)
      : OperandPredicateMatcher(OPM_LLT, InsnVarID, OpIdx), Ty(Ty) {
    KnownTypes.insert(Ty);
  }

  static bool classof(const PredicateMatcher *P) {
    return P->getKind() == OPM_LLT;
  }
  bool isIdentical(const PredicateMatcher &B) const override {
    return OperandPredicateMatcher::isIdentical(B) &&
           Ty == cast<LLTOperandMatcher>(&B)->Ty;
  }
  MatchTableRecord getValue() const override {
    const auto VI = TypeIDValues.find(Ty);
    if (VI == TypeIDValues.end())
      return MatchTable::NamedValue(getTy().getCxxEnumValue());
    return MatchTable::NamedValue(getTy().getCxxEnumValue(), VI->second);
  }
  bool hasValue() const override {
    if (TypeIDValues.size() != KnownTypes.size())
      initTypeIDValuesMap();
    return TypeIDValues.count(Ty);
  }

  LLTCodeGen getTy() const { return Ty; }

  void emitPredicateOpcodes(MatchTable &Table,
                            RuleMatcher &Rule) const override {
    Table << MatchTable::Opcode("GIM_CheckType") << MatchTable::Comment("MI")
          << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
          << MatchTable::IntValue(OpIdx) << MatchTable::Comment("Type")
          << getValue() << MatchTable::LineBreak;
  }
};

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

/// Generates code to check that an operand is a pointer to any address space.
///
/// In SelectionDAG, the types did not describe pointers or address spaces. As a
/// result, iN is used to describe a pointer of N bits to any address space and
/// PatFrag predicates are typically used to constrain the address space. There's
/// no reliable means to derive the missing type information from the pattern so
/// imported rules must test the components of a pointer separately.
///
/// If SizeInBits is zero, then the pointer size will be obtained from the
/// subtarget.
class PointerToAnyOperandMatcher : public OperandPredicateMatcher {
protected:
  unsigned SizeInBits;

public:
  PointerToAnyOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
                             unsigned SizeInBits)
      : OperandPredicateMatcher(OPM_PointerToAny, InsnVarID, OpIdx),
        SizeInBits(SizeInBits) {}

  static bool classof(const PredicateMatcher *P) {
    return P->getKind() == OPM_PointerToAny;
  }

  bool isIdentical(const PredicateMatcher &B) const override {
    return OperandPredicateMatcher::isIdentical(B) &&
           SizeInBits == cast<PointerToAnyOperandMatcher>(&B)->SizeInBits;
  }

  void emitPredicateOpcodes(MatchTable &Table,
                            RuleMatcher &Rule) const override {
    Table << MatchTable::Opcode("GIM_CheckPointerToAny")
          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
          << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
          << MatchTable::Comment("SizeInBits")
          << MatchTable::IntValue(SizeInBits) << MatchTable::LineBreak;
  }
};

/// Generates code to record named operand in RecordedOperands list at StoreIdx.
/// Predicates with 'let PredicateCodeUsesOperands = 1' get RecordedOperands as
/// an argument to predicate's c++ code once all operands have been matched.
class RecordNamedOperandMatcher : public OperandPredicateMatcher {
protected:
  unsigned StoreIdx;
  std::string Name;

public:
  RecordNamedOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
                            unsigned StoreIdx, StringRef Name)
      : OperandPredicateMatcher(OPM_RecordNamedOperand, InsnVarID, OpIdx),
        StoreIdx(StoreIdx), Name(Name) {}

  static bool classof(const PredicateMatcher *P) {
    return P->getKind() == OPM_RecordNamedOperand;
  }

  bool isIdentical(const PredicateMatcher &B) const override {
    return OperandPredicateMatcher::isIdentical(B) &&
           StoreIdx == cast<RecordNamedOperandMatcher>(&B)->StoreIdx &&
           Name == cast<RecordNamedOperandMatcher>(&B)->Name;
  }

  void emitPredicateOpcodes(MatchTable &Table,
                            RuleMatcher &Rule) const override {
    Table << MatchTable::Opcode("GIM_RecordNamedOperand")
          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
          << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
          << MatchTable::Comment("StoreIdx") << MatchTable::IntValue(StoreIdx)
          << MatchTable::Comment("Name : " + Name) << MatchTable::LineBreak;
  }
};

/// Generates code to check that an operand is a particular target constant.
class ComplexPatternOperandMatcher : public OperandPredicateMatcher {
protected:
  const OperandMatcher &Operand;
  const Record &TheDef;

  unsigned getAllocatedTemporariesBaseID() const;

public:
  bool isIdentical(const PredicateMatcher &B) const override { return false; }

  ComplexPatternOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
                               const OperandMatcher &Operand,
                               const Record &TheDef)
      : OperandPredicateMatcher(OPM_ComplexPattern, InsnVarID, OpIdx),
        Operand(Operand), TheDef(TheDef) {}

  static bool classof(const PredicateMatcher *P) {
    return P->getKind() == OPM_ComplexPattern;
  }

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

  unsigned countRendererFns() const override {
    return 1;
  }
};

/// Generates code to check that an operand is in a particular register bank.
class RegisterBankOperandMatcher : public OperandPredicateMatcher {
protected:
  const CodeGenRegisterClass &RC;

public:
  RegisterBankOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
                             const CodeGenRegisterClass &RC)
      : OperandPredicateMatcher(OPM_RegBank, InsnVarID, OpIdx), RC(RC) {}

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

  static bool classof(const PredicateMatcher *P) {
    return P->getKind() == OPM_RegBank;
  }

  void emitPredicateOpcodes(MatchTable &Table,
                            RuleMatcher &Rule) const override {
    Table << MatchTable::Opcode("GIM_CheckRegBankForClass")
          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
          << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
          << MatchTable::Comment("RC")
          << MatchTable::NamedValue(RC.getQualifiedName() + "RegClassID")
          << MatchTable::LineBreak;
  }
};

/// Generates code to check that an operand is a basic block.
class MBBOperandMatcher : public OperandPredicateMatcher {
public:
  MBBOperandMatcher(unsigned InsnVarID, unsigned OpIdx)
      : OperandPredicateMatcher(OPM_MBB, InsnVarID, OpIdx) {}

  static bool classof(const PredicateMatcher *P) {
    return P->getKind() == OPM_MBB;
  }

  void emitPredicateOpcodes(MatchTable &Table,
                            RuleMatcher &Rule) const override {
    Table << MatchTable::Opcode("GIM_CheckIsMBB") << MatchTable::Comment("MI")
          << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
          << MatchTable::IntValue(OpIdx) << MatchTable::LineBreak;
  }
};

class ImmOperandMatcher : public OperandPredicateMatcher {
public:
  ImmOperandMatcher(unsigned InsnVarID, unsigned OpIdx)
      : OperandPredicateMatcher(IPM_Imm, InsnVarID, OpIdx) {}

  static bool classof(const PredicateMatcher *P) {
    return P->getKind() == IPM_Imm;
  }

  void emitPredicateOpcodes(MatchTable &Table,
                            RuleMatcher &Rule) const override {
    Table << MatchTable::Opcode("GIM_CheckIsImm") << MatchTable::Comment("MI")
          << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
          << MatchTable::IntValue(OpIdx) << MatchTable::LineBreak;
  }
};

/// Generates code to check that an operand is a G_CONSTANT with a particular
/// int.
class ConstantIntOperandMatcher : public OperandPredicateMatcher {
protected:
  int64_t Value;

public:
  ConstantIntOperandMatcher(unsigned InsnVarID, unsigned OpIdx, int64_t Value)
      : OperandPredicateMatcher(OPM_Int, InsnVarID, OpIdx), Value(Value) {}

  bool isIdentical(const PredicateMatcher &B) const override {
    return OperandPredicateMatcher::isIdentical(B) &&
           Value == cast<ConstantIntOperandMatcher>(&B)->Value;
  }

  static bool classof(const PredicateMatcher *P) {
    return P->getKind() == OPM_Int;
  }

  void emitPredicateOpcodes(MatchTable &Table,
                            RuleMatcher &Rule) const override {
    Table << MatchTable::Opcode("GIM_CheckConstantInt")
          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
          << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
          << MatchTable::IntValue(Value) << MatchTable::LineBreak;
  }
};

/// Generates code to check that an operand is a raw int (where MO.isImm() or
/// MO.isCImm() is true).
class LiteralIntOperandMatcher : public OperandPredicateMatcher {
protected:
  int64_t Value;

public:
  LiteralIntOperandMatcher(unsigned InsnVarID, unsigned OpIdx, int64_t Value)
      : OperandPredicateMatcher(OPM_LiteralInt, InsnVarID, OpIdx),
        Value(Value) {}

  bool isIdentical(const PredicateMatcher &B) const override {
    return OperandPredicateMatcher::isIdentical(B) &&
           Value == cast<LiteralIntOperandMatcher>(&B)->Value;
  }

  static bool classof(const PredicateMatcher *P) {
    return P->getKind() == OPM_LiteralInt;
  }

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

/// Generates code to check that an operand is an CmpInst predicate
class CmpPredicateOperandMatcher : public OperandPredicateMatcher {
protected:
  std::string PredName;

public:
  CmpPredicateOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
                             std::string P)
    : OperandPredicateMatcher(OPM_CmpPredicate, InsnVarID, OpIdx), PredName(P) {}

  bool isIdentical(const PredicateMatcher &B) const override {
    return OperandPredicateMatcher::isIdentical(B) &&
           PredName == cast<CmpPredicateOperandMatcher>(&B)->PredName;
  }

  static bool classof(const PredicateMatcher *P) {
    return P->getKind() == OPM_CmpPredicate;
  }

  void emitPredicateOpcodes(MatchTable &Table,
                            RuleMatcher &Rule) const override {
    Table << MatchTable::Opcode("GIM_CheckCmpPredicate")
          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
          << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
          << MatchTable::Comment("Predicate")
          << MatchTable::NamedValue("CmpInst", PredName)
          << MatchTable::LineBreak;
  }
};

/// Generates code to check that an operand is an intrinsic ID.
class IntrinsicIDOperandMatcher : public OperandPredicateMatcher {
protected:
  const CodeGenIntrinsic *II;

public:
  IntrinsicIDOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
                            const CodeGenIntrinsic *II)
      : OperandPredicateMatcher(OPM_IntrinsicID, InsnVarID, OpIdx), II(II) {}

  bool isIdentical(const PredicateMatcher &B) const override {
    return OperandPredicateMatcher::isIdentical(B) &&
           II == cast<IntrinsicIDOperandMatcher>(&B)->II;
  }

  static bool classof(const PredicateMatcher *P) {
    return P->getKind() == OPM_IntrinsicID;
  }

  void emitPredicateOpcodes(MatchTable &Table,
                            RuleMatcher &Rule) const override {
    Table << MatchTable::Opcode("GIM_CheckIntrinsicID")
          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
          << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
          << MatchTable::NamedValue("Intrinsic::" + II->EnumName)
          << MatchTable::LineBreak;
  }
};

/// Generates code to check that this operand is an immediate whose value meets
/// an immediate predicate.
class OperandImmPredicateMatcher : public OperandPredicateMatcher {
protected:
  TreePredicateFn Predicate;

public:
  OperandImmPredicateMatcher(unsigned InsnVarID, unsigned OpIdx,
                             const TreePredicateFn &Predicate)
      : OperandPredicateMatcher(IPM_ImmPredicate, InsnVarID, OpIdx),
        Predicate(Predicate) {}

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

  static bool classof(const PredicateMatcher *P) {
    return P->getKind() == IPM_ImmPredicate;
  }

  void emitPredicateOpcodes(MatchTable &Table,
                            RuleMatcher &Rule) const override {
    Table << MatchTable::Opcode("GIM_CheckImmOperandPredicate")
          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
          << MatchTable::Comment("MO") << MatchTable::IntValue(OpIdx)
          << MatchTable::Comment("Predicate")
          << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
          << MatchTable::LineBreak;
  }
};

/// Generates code to check that a set of predicates match for a particular
/// operand.
class OperandMatcher : public PredicateListMatcher<OperandPredicateMatcher> {
protected:
  InstructionMatcher &Insn;
  unsigned OpIdx;
  std::string SymbolicName;

  /// The index of the first temporary variable allocated to this operand. The
  /// number of allocated temporaries can be found with
  /// countRendererFns().
  unsigned AllocatedTemporariesBaseID;

public:
  OperandMatcher(InstructionMatcher &Insn, unsigned OpIdx,
                 const std::string &SymbolicName,
                 unsigned AllocatedTemporariesBaseID)
      : Insn(Insn), OpIdx(OpIdx), SymbolicName(SymbolicName),
        AllocatedTemporariesBaseID(AllocatedTemporariesBaseID) {}

  bool hasSymbolicName() const { return !SymbolicName.empty(); }
  StringRef getSymbolicName() const { return SymbolicName; }
  void setSymbolicName(StringRef Name) {
    assert(SymbolicName.empty() && "Operand already has a symbolic name");
    SymbolicName = std::string(Name);
  }

  /// Construct a new operand predicate and add it to the matcher.
  template <class Kind, class... Args>
  Optional<Kind *> addPredicate(Args &&... args) {
    if (isSameAsAnotherOperand())
      return None;
    Predicates.emplace_back(std::make_unique<Kind>(
        getInsnVarID(), getOpIdx(), std::forward<Args>(args)...));
    return static_cast<Kind *>(Predicates.back().get());
  }

  unsigned getOpIdx() const { return OpIdx; }
  unsigned getInsnVarID() const;

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

  InstructionMatcher &getInstructionMatcher() const { return Insn; }

  Error addTypeCheckPredicate(const TypeSetByHwMode &VTy,
                              bool OperandIsAPointer);

  /// Emit MatchTable opcodes that test whether the instruction named in
  /// InsnVarID matches all the predicates and all the operands.
  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) {
    if (!Optimized) {
      std::string Comment;
      raw_string_ostream CommentOS(Comment);
      CommentOS << "MIs[" << getInsnVarID() << "] ";
      if (SymbolicName.empty())
        CommentOS << "Operand " << OpIdx;
      else
        CommentOS << SymbolicName;
      Table << MatchTable::Comment(CommentOS.str()) << MatchTable::LineBreak;
    }

    emitPredicateListOpcodes(Table, Rule);
  }

  /// Compare the priority of this object and B.
  ///
  /// Returns true if this object is more important than B.
  bool isHigherPriorityThan(OperandMatcher &B) {
    // Operand matchers involving more predicates have higher priority.
    if (predicates_size() > B.predicates_size())
      return true;
    if (predicates_size() < B.predicates_size())
      return false;

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

    return false;
  };

  /// Report the maximum number of temporary operands needed by the operand
  /// matcher.
  unsigned countRendererFns() {
    return std::accumulate(
        predicates().begin(), predicates().end(), 0,
        [](unsigned A,
           const std::unique_ptr<OperandPredicateMatcher> &Predicate) {
          return A + Predicate->countRendererFns();
        });
  }

  unsigned getAllocatedTemporariesBaseID() const {
    return AllocatedTemporariesBaseID;
  }

  bool isSameAsAnotherOperand() {
    for (const auto &Predicate : predicates())
      if (isa<SameOperandMatcher>(Predicate))
        return true;
    return false;
  }
};

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

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

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

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

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

/// Generates code to check a predicate on an instruction.
///
/// Typical predicates include:
/// * The opcode of the instruction is a particular value.
/// * The nsw/nuw flag is/isn't set.
class InstructionPredicateMatcher : public PredicateMatcher {
public:
  InstructionPredicateMatcher(PredicateKind Kind, unsigned InsnVarID)
      : PredicateMatcher(Kind, InsnVarID) {}
  virtual ~InstructionPredicateMatcher() {}

  /// Compare the priority of this object and B.
  ///
  /// Returns true if this object is more important than B.
  virtual bool
  isHigherPriorityThan(const InstructionPredicateMatcher &B) const {
    return Kind < B.Kind;
  };
};

template <>
std::string
PredicateListMatcher<PredicateMatcher>::getNoPredicateComment() const {
  return "No instruction predicates";
}

/// Generates code to check the opcode of an instruction.
class InstructionOpcodeMatcher : public InstructionPredicateMatcher {
protected:
  // Allow matching one to several, similar opcodes that share properties. This
  // is to handle patterns where one SelectionDAG operation maps to multiple
  // GlobalISel ones (e.g. G_BUILD_VECTOR and G_BUILD_VECTOR_TRUNC). The first
  // is treated as the canonical opcode.
  SmallVector<const CodeGenInstruction *, 2> Insts;

  static DenseMap<const CodeGenInstruction *, unsigned> OpcodeValues;


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

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

    unsigned OpcodeValue = 0;
    for (const CodeGenInstruction *I : Target.getInstructionsByEnumValue())
      OpcodeValues[I] = OpcodeValue++;
  }

  InstructionOpcodeMatcher(unsigned InsnVarID,
                           ArrayRef<const CodeGenInstruction *> I)
      : InstructionPredicateMatcher(IPM_Opcode, InsnVarID),
        Insts(I.begin(), I.end()) {
    assert((Insts.size() == 1 || Insts.size() == 2) &&
           "unexpected number of opcode alternatives");
  }

  static bool classof(const PredicateMatcher *P) {
    return P->getKind() == IPM_Opcode;
  }

  bool isIdentical(const PredicateMatcher &B) const override {
    return InstructionPredicateMatcher::isIdentical(B) &&
           Insts == cast<InstructionOpcodeMatcher>(&B)->Insts;
  }

  bool hasValue() const override {
    return Insts.size() == 1 && OpcodeValues.count(Insts[0]);
  }

  // TODO: This is used for the SwitchMatcher optimization. We should be able to
  // return a list of the opcodes to match.
  MatchTableRecord getValue() const override {
    assert(Insts.size() == 1);

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

  void emitPredicateOpcodes(MatchTable &Table,
                            RuleMatcher &Rule) const override {
    StringRef CheckType = Insts.size() == 1 ?
                          "GIM_CheckOpcode" : "GIM_CheckOpcodeIsEither";
    Table << MatchTable::Opcode(CheckType) << MatchTable::Comment("MI")
          << MatchTable::IntValue(InsnVarID);

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

  /// Compare the priority of this object and B.
  ///
  /// Returns true if this object is more important than B.
  bool
  isHigherPriorityThan(const InstructionPredicateMatcher &B) const override {
    if (InstructionPredicateMatcher::isHigherPriorityThan(B))
      return true;
    if (B.InstructionPredicateMatcher::isHigherPriorityThan(*this))
      return false;

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

    return false;
  };

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

  // The first opcode is the canonical opcode, and later are alternatives.
  StringRef getOpcode() const {
    return Insts[0]->TheDef->getName();
  }

  ArrayRef<const CodeGenInstruction *> getAlternativeOpcodes() {
    return Insts;
  }

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

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

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

class InstructionNumOperandsMatcher final : public InstructionPredicateMatcher {
  unsigned NumOperands = 0;

public:
  InstructionNumOperandsMatcher(unsigned InsnVarID, unsigned NumOperands)
      : InstructionPredicateMatcher(IPM_NumOperands, InsnVarID),
        NumOperands(NumOperands) {}

  static bool classof(const PredicateMatcher *P) {
    return P->getKind() == IPM_NumOperands;
  }

  bool isIdentical(const PredicateMatcher &B) const override {
    return InstructionPredicateMatcher::isIdentical(B) &&
           NumOperands == cast<InstructionNumOperandsMatcher>(&B)->NumOperands;
  }

  void emitPredicateOpcodes(MatchTable &Table,
                            RuleMatcher &Rule) const override {
    Table << MatchTable::Opcode("GIM_CheckNumOperands")
          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
          << MatchTable::Comment("Expected")
          << MatchTable::IntValue(NumOperands) << MatchTable::LineBreak;
  }
};

/// Generates code to check that this instruction is a constant whose value
/// meets an immediate predicate.
///
/// Immediates are slightly odd since they are typically used like an operand
/// but are represented as an operator internally. We typically write simm8:$src
/// in a tablegen pattern, but this is just syntactic sugar for
/// (imm:i32)<<P:Predicate_simm8>>:$imm which more directly describes the nodes
/// that will be matched and the predicate (which is attached to the imm
/// operator) that will be tested. In SelectionDAG this describes a
/// ConstantSDNode whose internal value will be tested using the simm8 predicate.
///
/// The corresponding GlobalISel representation is %1 = G_CONSTANT iN Value. In
/// this representation, the immediate could be tested with an
/// InstructionMatcher, InstructionOpcodeMatcher, OperandMatcher, and a
/// OperandPredicateMatcher-subclass to check the Value meets the predicate but
/// there are two implementation issues with producing that matcher
/// configuration from the SelectionDAG pattern:
/// * ImmLeaf is a PatFrag whose root is an InstructionMatcher. This means that
///   were we to sink the immediate predicate to the operand we would have to
///   have two partial implementations of PatFrag support, one for immediates
///   and one for non-immediates.
/// * At the point we handle the predicate, the OperandMatcher hasn't been
///   created yet. If we were to sink the predicate to the OperandMatcher we
///   would also have to complicate (or duplicate) the code that descends and
///   creates matchers for the subtree.
/// Overall, it's simpler to handle it in the place it was found.
class InstructionImmPredicateMatcher : public InstructionPredicateMatcher {
protected:
  TreePredicateFn Predicate;

public:
  InstructionImmPredicateMatcher(unsigned InsnVarID,
                                 const TreePredicateFn &Predicate)
      : InstructionPredicateMatcher(IPM_ImmPredicate, InsnVarID),
        Predicate(Predicate) {}

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

  static bool classof(const PredicateMatcher *P) {
    return P->getKind() == IPM_ImmPredicate;
  }

  void emitPredicateOpcodes(MatchTable &Table,
                            RuleMatcher &Rule) const override {
    Table << MatchTable::Opcode(getMatchOpcodeForImmPredicate(Predicate))
          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
          << MatchTable::Comment("Predicate")
          << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
          << MatchTable::LineBreak;
  }
};

/// Generates code to check that a memory instruction has a atomic ordering
/// MachineMemoryOperand.
class AtomicOrderingMMOPredicateMatcher : public InstructionPredicateMatcher {
public:
  enum AOComparator {
    AO_Exactly,
    AO_OrStronger,
    AO_WeakerThan,
  };

protected:
  StringRef Order;
  AOComparator Comparator;

public:
  AtomicOrderingMMOPredicateMatcher(unsigned InsnVarID, StringRef Order,
                                    AOComparator Comparator = AO_Exactly)
      : InstructionPredicateMatcher(IPM_AtomicOrderingMMO, InsnVarID),
        Order(Order), Comparator(Comparator) {}

  static bool classof(const PredicateMatcher *P) {
    return P->getKind() == IPM_AtomicOrderingMMO;
  }

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

  void emitPredicateOpcodes(MatchTable &Table,
                            RuleMatcher &Rule) const override {
    StringRef Opcode = "GIM_CheckAtomicOrdering";

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

    Table << MatchTable::Opcode(Opcode) << MatchTable::Comment("MI")
          << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Order")
          << MatchTable::NamedValue(("(int64_t)AtomicOrdering::" + Order).str())
          << MatchTable::LineBreak;
  }
};

/// Generates code to check that the size of an MMO is exactly N bytes.
class MemorySizePredicateMatcher : public InstructionPredicateMatcher {
protected:
  unsigned MMOIdx;
  uint64_t Size;

public:
  MemorySizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx, unsigned Size)
      : InstructionPredicateMatcher(IPM_MemoryLLTSize, InsnVarID),
        MMOIdx(MMOIdx), Size(Size) {}

  static bool classof(const PredicateMatcher *P) {
    return P->getKind() == IPM_MemoryLLTSize;
  }
  bool isIdentical(const PredicateMatcher &B) const override {
    return InstructionPredicateMatcher::isIdentical(B) &&
           MMOIdx == cast<MemorySizePredicateMatcher>(&B)->MMOIdx &&
           Size == cast<MemorySizePredicateMatcher>(&B)->Size;
  }

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

class MemoryAddressSpacePredicateMatcher : public InstructionPredicateMatcher {
protected:
  unsigned MMOIdx;
  SmallVector<unsigned, 4> AddrSpaces;

public:
  MemoryAddressSpacePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
                                     ArrayRef<unsigned> AddrSpaces)
      : InstructionPredicateMatcher(IPM_MemoryAddressSpace, InsnVarID),
        MMOIdx(MMOIdx), AddrSpaces(AddrSpaces.begin(), AddrSpaces.end()) {}

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

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

    Table << MatchTable::LineBreak;
  }
};

class MemoryAlignmentPredicateMatcher : public InstructionPredicateMatcher {
protected:
  unsigned MMOIdx;
  int MinAlign;

public:
  MemoryAlignmentPredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
                                  int MinAlign)
      : InstructionPredicateMatcher(IPM_MemoryAlignment, InsnVarID),
        MMOIdx(MMOIdx), MinAlign(MinAlign) {
    assert(MinAlign > 0);
  }

  static bool classof(const PredicateMatcher *P) {
    return P->getKind() == IPM_MemoryAlignment;
  }

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

  void emitPredicateOpcodes(MatchTable &Table,
                            RuleMatcher &Rule) const override {
    Table << MatchTable::Opcode("GIM_CheckMemoryAlignment")
          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
          << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
          << MatchTable::Comment("MinAlign") << MatchTable::IntValue(MinAlign)
          << MatchTable::LineBreak;
  }
};

/// Generates code to check that the size of an MMO is less-than, equal-to, or
/// greater than a given LLT.
class MemoryVsLLTSizePredicateMatcher : public InstructionPredicateMatcher {
public:
  enum RelationKind {
    GreaterThan,
    EqualTo,
    LessThan,
  };

protected:
  unsigned MMOIdx;
  RelationKind Relation;
  unsigned OpIdx;

public:
  MemoryVsLLTSizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
                                  enum RelationKind Relation,
                                  unsigned OpIdx)
      : InstructionPredicateMatcher(IPM_MemoryVsLLTSize, InsnVarID),
        MMOIdx(MMOIdx), Relation(Relation), OpIdx(OpIdx) {}

  static bool classof(const PredicateMatcher *P) {
    return P->getKind() == IPM_MemoryVsLLTSize;
  }
  bool isIdentical(const PredicateMatcher &B) const override {
    return InstructionPredicateMatcher::isIdentical(B) &&
           MMOIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->MMOIdx &&
           Relation == cast<MemoryVsLLTSizePredicateMatcher>(&B)->Relation &&
           OpIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->OpIdx;
  }

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

// Matcher for immAllOnesV/immAllZerosV
class VectorSplatImmPredicateMatcher : public InstructionPredicateMatcher {
public:
  enum SplatKind {
    AllZeros,
    AllOnes
  };

private:
  SplatKind Kind;

public:
  VectorSplatImmPredicateMatcher(unsigned InsnVarID, SplatKind K)
      : InstructionPredicateMatcher(IPM_VectorSplatImm, InsnVarID), Kind(K) {}

  static bool classof(const PredicateMatcher *P) {
    return P->getKind() == IPM_VectorSplatImm;
  }

  bool isIdentical(const PredicateMatcher &B) const override {
    return InstructionPredicateMatcher::isIdentical(B) &&
           Kind == static_cast<const VectorSplatImmPredicateMatcher &>(B).Kind;
  }

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

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

/// Generates code to check an arbitrary C++ instruction predicate.
class GenericInstructionPredicateMatcher : public InstructionPredicateMatcher {
protected:
  TreePredicateFn Predicate;

public:
  GenericInstructionPredicateMatcher(unsigned InsnVarID,
                                     TreePredicateFn Predicate)
      : InstructionPredicateMatcher(IPM_GenericPredicate, InsnVarID),
        Predicate(Predicate) {}

  static bool classof(const InstructionPredicateMatcher *P) {
    return P->getKind() == IPM_GenericPredicate;
  }
  bool isIdentical(const PredicateMatcher &B) const override {
    return InstructionPredicateMatcher::isIdentical(B) &&
           Predicate ==
               static_cast<const GenericInstructionPredicateMatcher &>(B)
                   .Predicate;
  }
  void emitPredicateOpcodes(MatchTable &Table,
                            RuleMatcher &Rule) const override {
    Table << MatchTable::Opcode("GIM_CheckCxxInsnPredicate")
          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
          << MatchTable::Comment("FnId")
          << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
          << MatchTable::LineBreak;
  }
};

/// Generates code to check that a set of predicates and operands match for a
/// particular instruction.
///
/// Typical predicates include:
/// * Has a specific opcode.
/// * Has an nsw/nuw flag or doesn't.
class InstructionMatcher final : public PredicateListMatcher<PredicateMatcher> {
protected:
  typedef std::vector<std::unique_ptr<OperandMatcher>> OperandVec;

  RuleMatcher &Rule;

  /// The operands to match. All rendered operands must be present even if the
  /// condition is always true.
  OperandVec Operands;
  bool NumOperandsCheck = true;

  std::string SymbolicName;
  unsigned InsnVarID;

  /// PhysRegInputs - List list has an entry for each explicitly specified
  /// physreg input to the pattern.  The first elt is the Register node, the
  /// second is the recorded slot number the input pattern match saved it in.
  SmallVector<std::pair<Record *, unsigned>, 2> PhysRegInputs;

public:
  InstructionMatcher(RuleMatcher &Rule, StringRef SymbolicName,
                     bool NumOpsCheck = true)
      : Rule(Rule), NumOperandsCheck(NumOpsCheck), SymbolicName(SymbolicName) {
    // We create a new instruction matcher.
    // Get a new ID for that instruction.
    InsnVarID = Rule.implicitlyDefineInsnVar(*this);
  }

  /// Construct a new instruction predicate and add it to the matcher.
  template <class Kind, class... Args>
  Optional<Kind *> addPredicate(Args &&... args) {
    Predicates.emplace_back(
        std::make_unique<Kind>(getInsnVarID(), std::forward<Args>(args)...));
    return static_cast<Kind *>(Predicates.back().get());
  }

  RuleMatcher &getRuleMatcher() const { return Rule; }

  unsigned getInsnVarID() const { return InsnVarID; }

  /// Add an operand to the matcher.
  OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName,
                             unsigned AllocatedTemporariesBaseID) {
    Operands.emplace_back(new OperandMatcher(*this, OpIdx, SymbolicName,
                                             AllocatedTemporariesBaseID));
    if (!SymbolicName.empty())
      Rule.defineOperand(SymbolicName, *Operands.back());

    return *Operands.back();
  }

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

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

  ArrayRef<std::pair<Record *, unsigned>> getPhysRegInputs() const {
    return PhysRegInputs;
  }

  StringRef getSymbolicName() const { return SymbolicName; }
  unsigned getNumOperands() const { return Operands.size(); }
  OperandVec::iterator operands_begin() { return Operands.begin(); }
  OperandVec::iterator operands_end() { return Operands.end(); }
  iterator_range<OperandVec::iterator> operands() {
    return make_range(operands_begin(), operands_end());
  }
  OperandVec::const_iterator operands_begin() const { return Operands.begin(); }
  OperandVec::const_iterator operands_end() const { return Operands.end(); }
  iterator_range<OperandVec::const_iterator> operands() const {
    return make_range(operands_begin(), operands_end());
  }
  bool operands_empty() const { return Operands.empty(); }

  void pop_front() { Operands.erase(Operands.begin()); }

  void optimize();

  /// Emit MatchTable opcodes that test whether the instruction named in
  /// InsnVarName matches all the predicates and all the operands.
  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) {
    if (NumOperandsCheck)
      InstructionNumOperandsMatcher(InsnVarID, getNumOperands())
          .emitPredicateOpcodes(Table, Rule);

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

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

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

  /// Compare the priority of this object and B.
  ///
  /// Returns true if this object is more important than B.
  bool isHigherPriorityThan(InstructionMatcher &B) {
    // Instruction matchers involving more operands have higher priority.
    if (Operands.size() > B.Operands.size())
      return true;
    if (Operands.size() < B.Operands.size())
      return false;

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

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

    return false;
  };

  /// Report the maximum number of temporary operands needed by the instruction
  /// matcher.
  unsigned countRendererFns() {
    return std::accumulate(
               predicates().begin(), predicates().end(), 0,
               [](unsigned A,
                  const std::unique_ptr<PredicateMatcher> &Predicate) {
                 return A + Predicate->countRendererFns();
               }) +
           std::accumulate(
               Operands.begin(), Operands.end(), 0,
               [](unsigned A, const std::unique_ptr<OperandMatcher> &Operand) {
                 return A + Operand->countRendererFns();
               });
  }

  InstructionOpcodeMatcher &getOpcodeMatcher() {
    for (auto &P : predicates())
      if (auto *OpMatcher = dyn_cast<InstructionOpcodeMatcher>(P.get()))
        return *OpMatcher;
    llvm_unreachable("Didn't find an opcode matcher");
  }

  bool isConstantInstruction() {
    return getOpcodeMatcher().isConstantInstruction();
  }

  StringRef getOpcode() { return getOpcodeMatcher().getOpcode(); }
};

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

unsigned RuleMatcher::getNumOperands() const {
  return Matchers.front()->getNumOperands();
}

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

/// Generates code to check that the operand is a register defined by an
/// instruction that matches the given instruction matcher.
///
/// For example, the pattern:
///   (set $dst, (G_MUL (G_ADD $src1, $src2), $src3))
/// would use an InstructionOperandMatcher for operand 1 of the G_MUL to match
/// the:
///   (G_ADD $src1, $src2)
/// subpattern.
class InstructionOperandMatcher : public OperandPredicateMatcher {
protected:
  std::unique_ptr<InstructionMatcher> InsnMatcher;

public:
  InstructionOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
                            RuleMatcher &Rule, StringRef SymbolicName,
                            bool NumOpsCheck = true)
      : OperandPredicateMatcher(OPM_Instruction, InsnVarID, OpIdx),
        InsnMatcher(new InstructionMatcher(Rule, SymbolicName, NumOpsCheck)) {}

  static bool classof(const PredicateMatcher *P) {
    return P->getKind() == OPM_Instruction;
  }

  InstructionMatcher &getInsnMatcher() const { return *InsnMatcher; }

  void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const {
    const unsigned NewInsnVarID = InsnMatcher->getInsnVarID();
    Table << MatchTable::Opcode("GIM_RecordInsn")
          << MatchTable::Comment("DefineMI")
          << MatchTable::IntValue(NewInsnVarID) << MatchTable::Comment("MI")
          << MatchTable::IntValue(getInsnVarID())
          << MatchTable::Comment("OpIdx") << MatchTable::IntValue(getOpIdx())
          << MatchTable::Comment("MIs[" + llvm::to_string(NewInsnVarID) + "]")
          << MatchTable::LineBreak;
  }

  void emitPredicateOpcodes(MatchTable &Table,
                            RuleMatcher &Rule) const override {
    emitCaptureOpcodes(Table, Rule);
    InsnMatcher->emitPredicateOpcodes(Table, Rule);
  }

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

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

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

  Stash.push_back(predicates_pop_front());
  if (Stash.back().get() == &OpcMatcher) {
    if (NumOperandsCheck && OpcMatcher.isVariadicNumOperands())
      Stash.emplace_back(
          new InstructionNumOperandsMatcher(InsnVarID, getNumOperands()));
    NumOperandsCheck = false;

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

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

//===- Actions ------------------------------------------------------------===//
class OperandRenderer {
public:
  enum RendererKind {
    OR_Copy,
    OR_CopyOrAddZeroReg,
    OR_CopySubReg,
    OR_CopyPhysReg,
    OR_CopyConstantAsImm,
    OR_CopyFConstantAsFPImm,
    OR_Imm,
    OR_SubRegIndex,
    OR_Register,
    OR_TempRegister,
    OR_ComplexPattern,
    OR_Custom,
    OR_CustomOperand
  };

protected:
  RendererKind Kind;

public:
  OperandRenderer(RendererKind Kind) : Kind(Kind) {}
  virtual ~OperandRenderer() {}

  RendererKind getKind() const { return Kind; }

  virtual void emitRenderOpcodes(MatchTable &Table,
                                 RuleMatcher &Rule) const = 0;
};

/// A CopyRenderer emits code to copy a single operand from an existing
/// instruction to the one being built.
class CopyRenderer : public OperandRenderer {
protected:
  unsigned NewInsnID;
  /// The name of the operand.
  const StringRef SymbolicName;

public:
  CopyRenderer(unsigned NewInsnID, StringRef SymbolicName)
      : OperandRenderer(OR_Copy), NewInsnID(NewInsnID),
        SymbolicName(SymbolicName) {
    assert(!SymbolicName.empty() && "Cannot copy from an unspecified source");
  }

  static bool classof(const OperandRenderer *R) {
    return R->getKind() == OR_Copy;
  }

  StringRef getSymbolicName() const { return SymbolicName; }

  void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
    const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
    unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
    Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID")
          << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID")
          << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
          << MatchTable::IntValue(Operand.getOpIdx())
          << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
  }
};

/// A CopyRenderer emits code to copy a virtual register to a specific physical
/// register.
class CopyPhysRegRenderer : public OperandRenderer {
protected:
  unsigned NewInsnID;
  Record *PhysReg;

public:
  CopyPhysRegRenderer(unsigned NewInsnID, Record *Reg)
      : OperandRenderer(OR_CopyPhysReg), NewInsnID(NewInsnID),
        PhysReg(Reg) {
    assert(PhysReg);
  }

  static bool classof(const OperandRenderer *R) {
    return R->getKind() == OR_CopyPhysReg;
  }

  Record *getPhysReg() const { return PhysReg; }

  void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
    const OperandMatcher &Operand = Rule.getPhysRegOperandMatcher(PhysReg);
    unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
    Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID")
          << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID")
          << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
          << MatchTable::IntValue(Operand.getOpIdx())
          << MatchTable::Comment(PhysReg->getName())
          << MatchTable::LineBreak;
  }
};

/// A CopyOrAddZeroRegRenderer emits code to copy a single operand from an
/// existing instruction to the one being built. If the operand turns out to be
/// a 'G_CONSTANT 0' then it replaces the operand with a zero register.
class CopyOrAddZeroRegRenderer : public OperandRenderer {
protected:
  unsigned NewInsnID;
  /// The name of the operand.
  const StringRef SymbolicName;
  const Record *ZeroRegisterDef;

public:
  CopyOrAddZeroRegRenderer(unsigned NewInsnID,
                           StringRef SymbolicName, Record *ZeroRegisterDef)
      : OperandRenderer(OR_CopyOrAddZeroReg), NewInsnID(NewInsnID),
        SymbolicName(SymbolicName), ZeroRegisterDef(ZeroRegisterDef) {
    assert(!SymbolicName.empty() && "Cannot copy from an unspecified source");
  }

  static bool classof(const OperandRenderer *R) {
    return R->getKind() == OR_CopyOrAddZeroReg;
  }

  StringRef getSymbolicName() const { return SymbolicName; }

  void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
    const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
    unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
    Table << MatchTable::Opcode("GIR_CopyOrAddZeroReg")
          << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
          << MatchTable::Comment("OldInsnID")
          << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
          << MatchTable::IntValue(Operand.getOpIdx())
          << MatchTable::NamedValue(
                 (ZeroRegisterDef->getValue("Namespace")
                      ? ZeroRegisterDef->getValueAsString("Namespace")
                      : ""),
                 ZeroRegisterDef->getName())
          << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
  }
};

/// A CopyConstantAsImmRenderer emits code to render a G_CONSTANT instruction to
/// an extended immediate operand.
class CopyConstantAsImmRenderer : public OperandRenderer {
protected:
  unsigned NewInsnID;
  /// The name of the operand.
  const std::string SymbolicName;
  bool Signed;

public:
  CopyConstantAsImmRenderer(unsigned NewInsnID, StringRef SymbolicName)
      : OperandRenderer(OR_CopyConstantAsImm), NewInsnID(NewInsnID),
        SymbolicName(SymbolicName), Signed(true) {}

  static bool classof(const OperandRenderer *R) {
    return R->getKind() == OR_CopyConstantAsImm;
  }

  StringRef getSymbolicName() const { return SymbolicName; }

  void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
    InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
    unsigned OldInsnVarID =