utils/TableGen/GlobalISelEmitter.cpp

//===- GlobalISelEmitter.cpp - Generate an instruction selector -----------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
/// \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/CodeGen/MachineValueType.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Error.h"
#include "llvm/Support/LowLevelTypeImpl.h"
#include "llvm/Support/ScopedPrinter.h"
#include "llvm/TableGen/Error.h"
#include "llvm/TableGen/Record.h"
#include "llvm/TableGen/TableGenBackend.h"
#include <string>
#include <numeric>
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(NumPatternEmitted, "Number of patterns emitted");
/// A unique identifier for a MatchTable.
static unsigned CurrentMatchTableID = 0;

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));

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

/// 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(const LLT &Ty) : Ty(Ty) {}

  void emitCxxEnumValue(raw_ostream &OS) const {
    if (Ty.isScalar()) {
      OS << "GILLT_s" << Ty.getSizeInBits();
      return;
    }
    if (Ty.isVector()) {
      OS << "GILLT_v" << Ty.getNumElements() << "s" << Ty.getScalarSizeInBits();
      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.getNumElements() << ", "
         << Ty.getScalarSizeInBits() << ")";
      return;
    }
    llvm_unreachable("Unhandled LLT");
  }

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

  /// This ordering is used for std::unique() and std::sort(). There's no
  /// particular logic behind the order.
  bool operator<(const LLTCodeGen &Other) const {
    if (!Ty.isValid())
      return Other.Ty.isValid();
    if (Ty.isScalar()) {
      if (!Other.Ty.isValid())
        return false;
      if (Other.Ty.isScalar())
        return Ty.getSizeInBits() < Other.Ty.getSizeInBits();
      return false;
    }
    if (Ty.isVector()) {
      if (!Other.Ty.isValid() || Other.Ty.isScalar())
        return false;
      if (Other.Ty.isVector()) {
        if (Ty.getNumElements() < Other.Ty.getNumElements())
          return true;
        if (Ty.getNumElements() > Other.Ty.getNumElements())
          return false;
        return Ty.getSizeInBits() < Other.Ty.getSizeInBits();
      }
      return false;
    }
    llvm_unreachable("Unhandled LLT");
  }
};

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.getVectorNumElements() != 1)
    return LLTCodeGen(
        LLT::vector(VT.getVectorNumElements(), 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 auto &P : N->getPredicateFns()) {
    Explanation +=
        (Separator + P.getOrigPatFragRecord()->getRecord()->getName()).str();
    if (P.isAlwaysTrue())
      Explanation += " always-true";
    if (P.isImmediatePattern())
      Explanation += " immediate";
  }
  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();

  return " (Operator not understood)";
}

/// 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 = "";
  if (N->isLeaf()) {
    if (isa<IntInit>(N->getLeafValue()))
      return Error::success();

    Explanation = "Is a leaf";
    Separator = ", ";
  }

  if (N->hasAnyPredicate()) {
    Explanation = Separator + "Has a predicate (" + explainPredicates(N) + ")";
    Separator = ", ";
  }

  if (N->getTransformFn()) {
    Explanation += Separator + "Has a transform function";
    Separator = ", ";
  }

  if (!N->isLeaf() && !N->hasAnyPredicate() && !N->getTransformFn())
    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;
}
//===- Matchers -----------------------------------------------------------===//

class OperandMatcher;
class MatchAction;

/// Generates code to check that a match rule matches.
class RuleMatcher {
  /// 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.
  std::vector<std::unique_ptr<InstructionMatcher>> Matchers;

  /// A list of actions that need to be taken when all predicates in this rule
  /// have succeeded.
  std::vector<std::unique_ptr<MatchAction>> Actions;

  /// A map of instruction matchers to the local variables created by
  /// emitCaptureOpcodes().
  std::map<const InstructionMatcher *, unsigned> InsnVariableIDs;

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

  std::vector<Record *> RequiredFeatures;

public:
  RuleMatcher()
      : Matchers(), Actions(), InsnVariableIDs(), NextInsnVarID(0) {}
  RuleMatcher(RuleMatcher &&Other) = default;
  RuleMatcher &operator=(RuleMatcher &&Other) = default;

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

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

  /// Define an instruction without emitting any code to do so.
  /// This is used for the root of the match.
  unsigned implicitlyDefineInsnVar(const InstructionMatcher &Matcher);
  /// Define an instruction and emit corresponding state-machine opcodes.
  unsigned defineInsnVar(raw_ostream &OS, const InstructionMatcher &Matcher,
                         unsigned InsnVarID, unsigned OpIdx);
  unsigned getInsnVarID(const InstructionMatcher &InsnMatcher) const;

  void emitCaptureOpcodes(raw_ostream &OS);

  void emit(raw_ostream &OS);

  /// 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;

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

template <class PredicateTy> class PredicateListMatcher {
private:
  typedef std::vector<std::unique_ptr<PredicateTy>> PredicateVec;
  PredicateVec Predicates;

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

  typename PredicateVec::const_iterator predicates_begin() const {
    return Predicates.begin();
  }
  typename PredicateVec::const_iterator predicates_end() const {
    return Predicates.end();
  }
  iterator_range<typename PredicateVec::const_iterator> predicates() const {
    return make_range(predicates_begin(), predicates_end());
  }
  typename PredicateVec::size_type predicates_size() const {
    return Predicates.size();
  }

  /// Emit MatchTable opcodes that tests whether all the predicates are met.
  template <class... Args>
  void emitPredicateListOpcodes(raw_ostream &OS, Args &&... args) const {
    if (Predicates.empty()) {
      OS << "// No predicates\n";
      return;
    }

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

/// 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:
  /// 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.
  enum PredicateKind {
    OPM_ComplexPattern,
    OPM_Instruction,
    OPM_IntrinsicID,
    OPM_Int,
    OPM_LiteralInt,
    OPM_LLT,
    OPM_RegBank,
    OPM_MBB,
  };

protected:
  PredicateKind Kind;

public:
  OperandPredicateMatcher(PredicateKind Kind) : Kind(Kind) {}
  virtual ~OperandPredicateMatcher() {}

  PredicateKind getKind() const { return Kind; }

  /// Return the OperandMatcher for the specified operand or nullptr if there
  /// isn't one by that name in this operand predicate matcher.
  ///
  /// InstructionOperandMatcher is the only subclass that can return non-null
  /// for this.
  virtual Optional<const OperandMatcher *>
  getOptionalOperand(StringRef SymbolicName) const {
    assert(!SymbolicName.empty() && "Cannot lookup unnamed operand");
    return None;
  }

  /// Emit MatchTable opcodes to capture instructions into the MIs table.
  ///
  /// Only InstructionOperandMatcher needs to do anything for this method the
  /// rest just walk the tree.
  virtual void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule,
                                  unsigned InsnVarID, unsigned OpIdx) const {}

  /// Emit MatchTable opcodes that check the predicate for the given operand.
  virtual void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
                                    unsigned InsnVarID,
                                    unsigned OpIdx) const = 0;

  /// 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 {
    return Kind < B.Kind;
  };

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

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

public:
  LLTOperandMatcher(const LLTCodeGen &Ty)
      : OperandPredicateMatcher(OPM_LLT), Ty(Ty) {}

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

  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
                            unsigned InsnVarID, unsigned OpIdx) const override {
    OS << "    GIM_CheckType, /*MI*/" << InsnVarID << ", /*Op*/" << OpIdx
       << ", /*Type*/";
    Ty.emitCxxEnumValue(OS);
    OS << ", \n";
  }
};

/// 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:
  ComplexPatternOperandMatcher(const OperandMatcher &Operand,
                               const Record &TheDef)
      : OperandPredicateMatcher(OPM_ComplexPattern), Operand(Operand),
        TheDef(TheDef) {}

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

  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
                            unsigned InsnVarID, unsigned OpIdx) const override {
    unsigned ID = getAllocatedTemporariesBaseID();
    OS << "    GIM_CheckComplexPattern, /*MI*/" << InsnVarID << ", /*Op*/"
       << OpIdx << ", /*Renderer*/" << ID << ", GICP_"
       << TheDef.getName() << ",\n";
  }

  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(const CodeGenRegisterClass &RC)
      : OperandPredicateMatcher(OPM_RegBank), RC(RC) {}

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

  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
                            unsigned InsnVarID, unsigned OpIdx) const override {
    OS << "    GIM_CheckRegBankForClass, /*MI*/" << InsnVarID << ", /*Op*/"
       << OpIdx << ", /*RC*/" << RC.getQualifiedName() << "RegClassID,\n";
  }
};

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

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

  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
                            unsigned InsnVarID, unsigned OpIdx) const override {
    OS << "    GIM_CheckIsMBB, /*MI*/" << InsnVarID << ", /*Op*/" << OpIdx << ",\n";
  }
};

/// 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(int64_t Value)
      : OperandPredicateMatcher(OPM_Int), Value(Value) {}

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

  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
                            unsigned InsnVarID, unsigned OpIdx) const override {
    OS << "    GIM_CheckConstantInt, /*MI*/" << InsnVarID << ", /*Op*/"
       << OpIdx << ", " << Value << ",\n";
  }
};

/// 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(int64_t Value)
      : OperandPredicateMatcher(OPM_LiteralInt), Value(Value) {}

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

  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
                            unsigned InsnVarID, unsigned OpIdx) const override {
    OS << "    GIM_CheckLiteralInt, /*MI*/" << InsnVarID << ", /*Op*/"
       << OpIdx << ", " << Value << ",\n";
  }
};

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

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

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

  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
                            unsigned InsnVarID, unsigned OpIdx) const override {
    OS << "    GIM_CheckIntrinsicID, /*MI*/" << InsnVarID << ", /*Op*/"
       << OpIdx << ", Intrinsic::" << II->EnumName << ",\n";
  }
};

/// 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(); }
  const StringRef getSymbolicName() const { return SymbolicName; }
  void setSymbolicName(StringRef Name) {
    assert(SymbolicName.empty() && "Operand already has a symbolic name");
    SymbolicName = Name;
  }
  unsigned getOperandIndex() const { return OpIdx; }

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

  Optional<const OperandMatcher *>
  getOptionalOperand(StringRef DesiredSymbolicName) const {
    assert(!DesiredSymbolicName.empty() && "Cannot lookup unnamed operand");
    if (DesiredSymbolicName == SymbolicName)
      return this;
    for (const auto &OP : predicates()) {
      const auto &MaybeOperand = OP->getOptionalOperand(DesiredSymbolicName);
      if (MaybeOperand.hasValue())
        return MaybeOperand.getValue();
    }
    return None;
  }

  InstructionMatcher &getInstructionMatcher() const { return Insn; }

  /// Emit MatchTable opcodes to capture instructions into the MIs table.
  void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule,
                          unsigned InsnVarID) const {
    for (const auto &Predicate : predicates())
      Predicate->emitCaptureOpcodes(OS, Rule, InsnVarID, OpIdx);
  }

  /// Emit MatchTable opcodes that test whether the instruction named in
  /// InsnVarID matches all the predicates and all the operands.
  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
                            unsigned InsnVarID) const {
    OS << "    // MIs[" << InsnVarID << "] ";
    if (SymbolicName.empty())
      OS << "Operand " << OpIdx;
    else
      OS << SymbolicName;
    OS << "\n";
    emitPredicateListOpcodes(OS, Rule, InsnVarID, OpIdx);
  }

  /// Compare the priority of this object and B.
  ///
  /// Returns true if this object is more important than B.
  bool isHigherPriorityThan(const OperandMatcher &B) const {
    // 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 (const 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() const {
    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;
  }
};

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 {
protected:
  /// 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.
  enum PredicateKind {
    IPM_Opcode,
  };

  PredicateKind Kind;

public:
  InstructionPredicateMatcher(PredicateKind Kind) : Kind(Kind) {}
  virtual ~InstructionPredicateMatcher() {}

  PredicateKind getKind() const { return Kind; }

  /// Emit MatchTable opcodes that test whether the instruction named in
  /// InsnVarID matches the predicate.
  virtual void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
                                    unsigned InsnVarID) const = 0;

  /// 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;
  };

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

/// Generates code to check the opcode of an instruction.
class InstructionOpcodeMatcher : public InstructionPredicateMatcher {
protected:
  const CodeGenInstruction *I;

public:
  InstructionOpcodeMatcher(const CodeGenInstruction *I)
      : InstructionPredicateMatcher(IPM_Opcode), I(I) {}

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

  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
                            unsigned InsnVarID) const override {
    OS << "    GIM_CheckOpcode, /*MI*/" << InsnVarID << ", " << I->Namespace
       << "::" << I->TheDef->getName() << ",\n";
  }

  /// 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 I->TheDef->getName() < BO->I->TheDef->getName();

    return false;
  };
};

/// 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
    : public PredicateListMatcher<InstructionPredicateMatcher> {
protected:
  typedef std::vector<std::unique_ptr<OperandMatcher>> OperandVec;

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

public:
  /// 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));
    return *Operands.back();
  }

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

  Optional<const OperandMatcher *>
  getOptionalOperand(StringRef SymbolicName) const {
    assert(!SymbolicName.empty() && "Cannot lookup unnamed operand");
    for (const auto &Operand : Operands) {
      const auto &OM = Operand->getOptionalOperand(SymbolicName);
      if (OM.hasValue())
        return OM.getValue();
    }
    return None;
  }

  const OperandMatcher &getOperand(StringRef SymbolicName) const {
    Optional<const OperandMatcher *>OM = getOptionalOperand(SymbolicName);
    if (OM.hasValue())
      return *OM.getValue();
    llvm_unreachable("Failed to lookup operand");
  }

  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());
  }

  /// Emit MatchTable opcodes to check the shape of the match and capture
  /// instructions into the MIs table.
  void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule,
                          unsigned InsnID) {
    OS << "    GIM_CheckNumOperands, /*MI*/" << InsnID << ", /*Expected*/"
       << getNumOperands() << ",\n";
    for (const auto &Operand : Operands)
      Operand->emitCaptureOpcodes(OS, Rule, InsnID);
  }

  /// Emit MatchTable opcodes that test whether the instruction named in
  /// InsnVarName matches all the predicates and all the operands.
  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
                            unsigned InsnVarID) const {
    emitPredicateListOpcodes(OS, Rule, InsnVarID);
    for (const auto &Operand : Operands)
      Operand->emitPredicateOpcodes(OS, Rule, InsnVarID);
  }

  /// Compare the priority of this object and B.
  ///
  /// Returns true if this object is more important than B.
  bool isHigherPriorityThan(const InstructionMatcher &B) const {
    // 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 (const 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;
    }

    for (const 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() const {
    return std::accumulate(predicates().begin(), predicates().end(), 0,
                           [](unsigned A,
                              const std::unique_ptr<InstructionPredicateMatcher>
                                  &Predicate) {
                             return A + Predicate->countRendererFns();
                           }) +
           std::accumulate(
               Operands.begin(), Operands.end(), 0,
               [](unsigned A, const std::unique_ptr<OperandMatcher> &Operand) {
                 return A + Operand->countRendererFns();
               });
  }
};

/// 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()
      : OperandPredicateMatcher(OPM_Instruction),
        InsnMatcher(new InstructionMatcher()) {}

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

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

  Optional<const OperandMatcher *>
  getOptionalOperand(StringRef SymbolicName) const override {
    assert(!SymbolicName.empty() && "Cannot lookup unnamed operand");
    return InsnMatcher->getOptionalOperand(SymbolicName);
  }

  void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule,
                          unsigned InsnID, unsigned OpIdx) const override {
    unsigned InsnVarID = Rule.defineInsnVar(OS, *InsnMatcher, InsnID, OpIdx);
    InsnMatcher->emitCaptureOpcodes(OS, Rule, InsnVarID);
  }

  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
                            unsigned InsnVarID_,
                            unsigned OpIdx_) const override {
    unsigned InsnVarID = Rule.getInsnVarID(*InsnMatcher);
    InsnMatcher->emitPredicateOpcodes(OS, Rule, InsnVarID);
  }
};

//===- Actions ------------------------------------------------------------===//
class OperandRenderer {
public:
  enum RendererKind {
    OR_Copy,
    OR_CopySubReg,
    OR_Imm,
    OR_Register,
    OR_ComplexPattern
  };

protected:
  RendererKind Kind;

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

  RendererKind getKind() const { return Kind; }

  virtual void emitRenderOpcodes(raw_ostream &OS, 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 matcher for the instruction that this operand is copied from.
  /// This provides the facility for looking up an a operand by it's name so
  /// that it can be used as a source for the instruction being built.
  const InstructionMatcher &Matched;
  /// The name of the operand.
  const StringRef SymbolicName;

public:
  CopyRenderer(unsigned NewInsnID, const InstructionMatcher &Matched,
               StringRef SymbolicName)
      : OperandRenderer(OR_Copy), NewInsnID(NewInsnID), Matched(Matched),
        SymbolicName(SymbolicName) {}

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

  const StringRef getSymbolicName() const { return SymbolicName; }

  void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
    const OperandMatcher &Operand = Matched.getOperand(SymbolicName);
    unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
    OS << "    GIR_Copy, /*NewInsnID*/" << NewInsnID << ", /*OldInsnID*/"
       << OldInsnVarID << ", /*OpIdx*/" << Operand.getOperandIndex() << ", // "
       << SymbolicName << "\n";
  }
};

/// A CopySubRegRenderer emits code to copy a single register operand from an
/// existing instruction to the one being built and indicate that only a
/// subregister should be copied.
class CopySubRegRenderer : public OperandRenderer {
protected:
  unsigned NewInsnID;
  /// The matcher for the instruction that this operand is copied from.
  /// This provides the facility for looking up an a operand by it's name so
  /// that it can be used as a source for the instruction being built.
  const InstructionMatcher &Matched;
  /// The name of the operand.
  const StringRef SymbolicName;
  /// The subregister to extract.
  const CodeGenSubRegIndex *SubReg;

public:
  CopySubRegRenderer(unsigned NewInsnID, const InstructionMatcher &Matched,
                     StringRef SymbolicName, const CodeGenSubRegIndex *SubReg)
      : OperandRenderer(OR_CopySubReg), NewInsnID(NewInsnID), Matched(Matched),
        SymbolicName(SymbolicName), SubReg(SubReg) {}

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

  const StringRef getSymbolicName() const { return SymbolicName; }

  void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
    const OperandMatcher &Operand = Matched.getOperand(SymbolicName);
    unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
    OS << "    GIR_CopySubReg, /*NewInsnID*/" << NewInsnID
       << ", /*OldInsnID*/" << OldInsnVarID << ", /*OpIdx*/"
       << Operand.getOperandIndex() << ", /*SubRegIdx*/" << SubReg->EnumValue
       << ", // " << SymbolicName << "\n";
  }
};

/// Adds a specific physical register to the instruction being built.
/// This is typically useful for WZR/XZR on AArch64.
class AddRegisterRenderer : public OperandRenderer {
protected:
  unsigned InsnID;
  const Record *RegisterDef;

public:
  AddRegisterRenderer(unsigned InsnID, const Record *RegisterDef)
      : OperandRenderer(OR_Register), InsnID(InsnID), RegisterDef(RegisterDef) {
  }

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

  void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
    OS << "      GIR_AddRegister, /*InsnID*/" << InsnID << ", "
       << (RegisterDef->getValue("Namespace")
               ? RegisterDef->getValueAsString("Namespace")
               : "")
       << "::" << RegisterDef->getName() << ",\n";
  }
};

/// Adds a specific immediate to the instruction being built.
class ImmRenderer : public OperandRenderer {
protected:
  unsigned InsnID;
  int64_t Imm;

public:
  ImmRenderer(unsigned InsnID, int64_t Imm)
      : OperandRenderer(OR_Imm), InsnID(InsnID), Imm(Imm) {}

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

  void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
    OS << "      GIR_AddImm, /*InsnID*/" << InsnID << ", /*Imm*/" << Imm
       << ",\n";
  }
};

/// Adds operands by calling a renderer function supplied by the ComplexPattern
/// matcher function.
class RenderComplexPatternOperand : public OperandRenderer {
private:
  unsigned InsnID;
  const Record &TheDef;
  /// The name of the operand.
  const StringRef SymbolicName;
  /// The renderer number. This must be unique within a rule since it's used to
  /// identify a temporary variable to hold the renderer function.
  unsigned RendererID;

  unsigned getNumOperands() const {
    return TheDef.getValueAsDag("Operands")->getNumArgs();
  }

public:
  RenderComplexPatternOperand(unsigned InsnID, const Record &TheDef,
                              StringRef SymbolicName, unsigned RendererID)
      : OperandRenderer(OR_ComplexPattern), InsnID(InsnID), TheDef(TheDef),
        SymbolicName(SymbolicName), RendererID(RendererID) {}

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

  void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
    OS << "    GIR_ComplexRenderer, /*InsnID*/" << InsnID << ", /*RendererID*/"
       << RendererID << ",\n";
  }
};

/// An action taken when all Matcher predicates succeeded for a parent rule.
///
/// Typical actions include:
/// * Changing the opcode of an instruction.
/// * Adding an operand to an instruction.
class MatchAction {
public:
  virtual ~MatchAction() {}

  /// Emit the C++ statements to implement the action.
  ///
  /// \param RecycleInsnID If given, it's an instruction to recycle. The
  ///                      requirements on the instruction vary from action to
  ///                      action.
  virtual void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
                                  unsigned RecycleInsnID) const = 0;
};

/// Generates a comment describing the matched rule being acted upon.
class DebugCommentAction : public MatchAction {
private:
  const PatternToMatch &P;

public:
  DebugCommentAction(const PatternToMatch &P) : P(P) {}

  void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
                          unsigned RecycleInsnID) const override {
    OS << "    // " << *P.getSrcPattern() << "  =>  " << *P.getDstPattern()
       << "\n";
  }
};

/// Generates code to build an instruction or mutate an existing instruction
/// into the desired instruction when this is possible.
class BuildMIAction : public MatchAction {
private:
  unsigned InsnID;
  const CodeGenInstruction *I;
  const InstructionMatcher &Matched;
  std::vector<std::unique_ptr<OperandRenderer>> OperandRenderers;

  /// True if the instruction can be built solely by mutating the opcode.
  bool canMutate() const {
    if (OperandRenderers.size() != Matched.getNumOperands())
      return false;

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

    return true;
  }

public:
  BuildMIAction(unsigned InsnID, const CodeGenInstruction *I,
                const InstructionMatcher &Matched)
      : InsnID(InsnID), I(I), Matched(Matched) {}

  template <class Kind, class... Args>
  Kind &addRenderer(Args&&... args) {
    OperandRenderers.emplace_back(
        llvm::make_unique<Kind>(std::forward<Args>(args)...));
    return *static_cast<Kind *>(OperandRenderers.back().get());
  }

  void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
                          unsigned RecycleInsnID) const override {
    if (canMutate()) {
      OS << "    GIR_MutateOpcode, /*InsnID*/" << InsnID
         << ", /*RecycleInsnID*/ " << RecycleInsnID << ", /*Opcode*/"
         << I->Namespace << "::" << I->TheDef->getName() << ",\n";

      if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) {
        for (auto Def : I->ImplicitDefs) {
          auto Namespace = Def->getValue("Namespace")
                               ? Def->getValueAsString("Namespace")
                               : "";
          OS << "    GIR_AddImplicitDef, " << InsnID << ", " << Namespace
             << "::" << Def->getName() << ",\n";
        }
        for (auto Use : I->ImplicitUses) {
          auto Namespace = Use->getValue("Namespace")
                               ? Use->getValueAsString("Namespace")
                               : "";
          OS << "    GIR_AddImplicitUse, " << InsnID << ", " << Namespace
             << "::" << Use->getName() << ",\n";
        }
      }
      return;
    }

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

    OS << "    GIR_BuildMI, /*InsnID*/" << InsnID << ", /*Opcode*/"
       << I->Namespace << "::" << I->TheDef->getName() << ",\n";
    for (const auto &Renderer : OperandRenderers)
      Renderer->emitRenderOpcodes(OS, Rule);

    OS << "    GIR_MergeMemOperands, /*InsnID*/" << InsnID << ",\n"
       << "    GIR_EraseFromParent, /*InsnID*/" << RecycleInsnID << ",\n";
  }
};

/// Generates code to constrain the operands of an output instruction to the
/// register classes specified by the definition of that instruction.
class ConstrainOperandsToDefinitionAction : public MatchAction {
  unsigned InsnID;

public:
  ConstrainOperandsToDefinitionAction(unsigned InsnID) : InsnID(InsnID) {}

  void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
                          unsigned RecycleInsnID) const override {
    OS << "    GIR_ConstrainSelectedInstOperands, /*InsnID*/" << InsnID << ",\n";
  }
};

/// Generates code to constrain the specified operand of an output instruction
/// to the specified register class.
class ConstrainOperandToRegClassAction : public MatchAction {
  unsigned InsnID;
  unsigned OpIdx;
  const CodeGenRegisterClass &RC;

public:
  ConstrainOperandToRegClassAction(unsigned InsnID, unsigned OpIdx,
                                   const CodeGenRegisterClass &RC)
      : InsnID(InsnID), OpIdx(OpIdx), RC(RC) {}

  void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
                          unsigned RecycleInsnID) const override {
    OS << "    GIR_ConstrainOperandRC, /*InsnID*/" << InsnID << ", /*Op*/"
       << OpIdx << ", /*RC " << RC.getName() << "*/ " << RC.EnumValue << ",\n";
  }
};

InstructionMatcher &RuleMatcher::addInstructionMatcher() {
  Matchers.emplace_back(new InstructionMatcher());
  return *Matchers.back();
}

void RuleMatcher::addRequiredFeature(Record *Feature) {
  RequiredFeatures.push_back(Feature);
}

const std::vector<Record *> &RuleMatcher::getRequiredFeatures() const {
  return RequiredFeatures;
}

template <class Kind, class... Args>
Kind &RuleMatcher::addAction(Args &&... args) {
  Actions.emplace_back(llvm::make_unique<Kind>(std::forward<Args>(args)...));
  return *static_cast<Kind *>(Actions.back().get());
}

unsigned
RuleMatcher::implicitlyDefineInsnVar(const InstructionMatcher &Matcher) {
  unsigned NewInsnVarID = NextInsnVarID++;
  InsnVariableIDs[&Matcher] = NewInsnVarID;
  return NewInsnVarID;
}

unsigned RuleMatcher::defineInsnVar(raw_ostream &OS,
                                    const InstructionMatcher &Matcher,
                                    unsigned InsnID, unsigned OpIdx) {
  unsigned NewInsnVarID = implicitlyDefineInsnVar(Matcher);
  OS << "    GIM_RecordInsn, /*DefineMI*/" << NewInsnVarID << ", /*MI*/"
     << InsnID << ", /*OpIdx*/" << OpIdx << ", // MIs[" << NewInsnVarID
     << "]\n";
  return NewInsnVarID;
}

unsigned RuleMatcher::getInsnVarID(const InstructionMatcher &InsnMatcher) const {
  const auto &I = InsnVariableIDs.find(&InsnMatcher);
  if (I != InsnVariableIDs.end())
    return I->second;
  llvm_unreachable("Matched Insn was not captured in a local variable");
}

/// Emit MatchTable opcodes to check the shape of the match and capture
/// instructions into local variables.
void RuleMatcher::emitCaptureOpcodes(raw_ostream &OS) {
  assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
  unsigned InsnVarID = implicitlyDefineInsnVar(*Matchers.front());
  Matchers.front()->emitCaptureOpcodes(OS, *this, InsnVarID);
}

void RuleMatcher::emit(raw_ostream &OS) {
  if (Matchers.empty())
    llvm_unreachable("Unexpected empty matcher!");

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

  OS << "  const static int64_t MatchTable" << CurrentMatchTableID << "[] = {\n";
  if (!RequiredFeatures.empty()) {
    OS << "    GIM_CheckFeatures, " << getNameForFeatureBitset(RequiredFeatures)
       << ",\n";
  }

  emitCaptureOpcodes(OS);

  Matchers.front()->emitPredicateOpcodes(OS, *this,
                                         getInsnVarID(*Matchers.front()));

  // We must also check if it's safe to fold the matched instructions.
  if (InsnVariableIDs.size() >= 2) {
    // Invert the map to create stable ordering (by var names)
    SmallVector<unsigned, 2> InsnIDs;
    for (const auto &Pair : InsnVariableIDs) {
      // Skip the root node since it isn't moving anywhere. Everything else is
      // sinking to meet it.
      if (Pair.first == Matchers.front().get())
        continue;

      InsnIDs.push_back(Pair.second);
    }
    std::sort(InsnIDs.begin(), InsnIDs.end());

    for (const auto &InsnID : InsnIDs) {
      // Reject the difficult cases until we have a more accurate check.
      OS << "    GIM_CheckIsSafeToFold, /*InsnID*/" << InsnID << ",\n";

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

  for (const auto &MA : Actions)
    MA->emitCxxActionStmts(OS, *this, 0);
  OS << "    GIR_Done,\n"
     << "  };\n"
     << "  State.MIs.resize(1);\n"
     << "  DEBUG(dbgs() << \"Processing MatchTable" << CurrentMatchTableID
     << "\\n\");\n"
     << "  if (executeMatchTable(*this, OutMIs, State, MatcherInfo, MatchTable"
     << CurrentMatchTableID << ", TII, MRI, TRI, RBI, AvailableFeatures)) {\n"
     << "    return true;\n"
     << "  }\n\n";
}

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

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

  return false;
}

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

//===- GlobalISelEmitter class --------------------------------------------===//

class GlobalISelEmitter {
public:
  explicit GlobalISelEmitter(RecordKeeper &RK);
  void run(raw_ostream &OS);

private:
  const RecordKeeper &RK;
  const CodeGenDAGPatterns CGP;
  const CodeGenTarget &Target;
  CodeGenRegBank CGRegs;

  /// Keep track of the equivalence between SDNodes and Instruction.
  /// This is defined using 'GINodeEquiv' in the target description.
  DenseMap<Record *, const CodeGenInstruction *> NodeEquivs;

  /// Keep track of the equivalence between ComplexPattern's and
  /// GIComplexOperandMatcher. Map entries are specified by subclassing
  /// GIComplexPatternEquiv.
  DenseMap<const Record *, const Record *> ComplexPatternEquivs;

  // Map of predicates to their subtarget features.
  SubtargetFeatureInfoMap SubtargetFeatures;

  void gatherNodeEquivs();
  const CodeGenInstruction *findNodeEquiv(Record *N) const;

  Error importRulePredicates(RuleMatcher &M, ArrayRef<Init *> Predicates);
  Expected<InstructionMatcher &>
  createAndImportSelDAGMatcher(InstructionMatcher &InsnMatcher,
                               const TreePatternNode *Src,
                               unsigned &TempOpIdx) const;
  Error importChildMatcher(InstructionMatcher &InsnMatcher,
                           const TreePatternNode *SrcChild, unsigned OpIdx,
                           unsigned &TempOpIdx) const;
  Expected<BuildMIAction &>
  createAndImportInstructionRenderer(RuleMatcher &M, const TreePatternNode *Dst,
                                     const InstructionMatcher &InsnMatcher);
  Error importExplicitUseRenderer(BuildMIAction &DstMIBuilder,
                                  TreePatternNode *DstChild,
                                  const InstructionMatcher &InsnMatcher) const;
  Error importDefaultOperandRenderers(BuildMIAction &DstMIBuilder,
                                      DagInit *DefaultOps) const;
  Error
  importImplicitDefRenderers(BuildMIAction &DstMIBuilder,
                             const std::vector<Record *> &ImplicitDefs) const;

  /// Analyze pattern \p P, returning a matcher for it if possible.
  /// Otherwise, return an Error explaining why we don't support it.
  Expected<RuleMatcher> runOnPattern(const PatternToMatch &P);

  void declareSubtargetFeature(Record *Predicate);
};

void GlobalISelEmitter::gatherNodeEquivs() {
  assert(NodeEquivs.empty());
  for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv"))
    NodeEquivs[Equiv->getValueAsDef("Node")] =
        &Target.getInstruction(Equiv->getValueAsDef("I"));

  assert(ComplexPatternEquivs.empty());
  for (Record *Equiv : RK.getAllDerivedDefinitions("GIComplexPatternEquiv")) {
    Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
    if (!SelDAGEquiv)
      continue;
    ComplexPatternEquivs[SelDAGEquiv] = Equiv;
 }
}

const CodeGenInstruction *GlobalISelEmitter::findNodeEquiv(Record *N) const {
  return NodeEquivs.lookup(N);
}

GlobalISelEmitter::GlobalISelEmitter(RecordKeeper &RK)
    : RK(RK), CGP(RK), Target(CGP.getTargetInfo()), CGRegs(RK) {}

//===- Emitter ------------------------------------------------------------===//

Error
GlobalISelEmitter::importRulePredicates(RuleMatcher &M,
                                        ArrayRef<Init *> Predicates) {
  for (const Init *Predicate : Predicates) {
    const DefInit *PredicateDef = static_cast<const DefInit *>(Predicate);
    declareSubtargetFeature(PredicateDef->getDef());
    M.addRequiredFeature(PredicateDef->getDef());
  }

  return Error::success();
}

Expected<InstructionMatcher &>
GlobalISelEmitter::createAndImportSelDAGMatcher(InstructionMatcher &InsnMatcher,
                                                const TreePatternNode *Src,
                                                unsigned &TempOpIdx) const {
  const CodeGenInstruction *SrcGIOrNull = nullptr;

  // Start with the defined operands (i.e., the results of the root operator).
  if (Src->getExtTypes().size() > 1)
    return failedImport("Src pattern has multiple results");

  if (Src->isLeaf()) {
    Init *SrcInit = Src->getLeafValue();
    if (isa<IntInit>(SrcInit)) {
      InsnMatcher.addPredicate<InstructionOpcodeMatcher>(
          &Target.getInstruction(RK.getDef("G_CONSTANT")));
    } else
      return failedImport(
          "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
  } else {
    SrcGIOrNull = findNodeEquiv(Src->getOperator());
    if (!SrcGIOrNull)
      return failedImport("Pattern operator lacks an equivalent Instruction" +
                          explainOperator(Src->getOperator()));
    auto &SrcGI = *SrcGIOrNull;

    // The operators look good: match the opcode
    InsnMatcher.addPredicate<InstructionOpcodeMatcher>(&SrcGI);
  }

  unsigned OpIdx = 0;
  for (const EEVT::TypeSet &Ty : Src->getExtTypes()) {
    auto OpTyOrNone = MVTToLLT(Ty.getConcrete());

    if (!OpTyOrNone)
      return failedImport(
          "Result of Src pattern operator has an unsupported type");

    // Results don't have a name unless they are the root node. The caller will
    // set the name if appropriate.
    OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
    OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone);
  }

  if (Src->isLeaf()) {
    Init *SrcInit = Src->getLeafValue();
    if (IntInit *SrcIntInit = dyn_cast<IntInit>(SrcInit)) {
      OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
      OM.addPredicate<LiteralIntOperandMatcher>(SrcIntInit->getValue());
    } else
      return failedImport(
          "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
  } else {
    assert(SrcGIOrNull &&
           "Expected to have already found an equivalent Instruction");
    // Match the used operands (i.e. the children of the operator).
    for (unsigned i = 0, e = Src->getNumChildren(); i != e; ++i) {
      TreePatternNode *SrcChild = Src->getChild(i);

      // For G_INTRINSIC, the operand immediately following the defs is an
      // intrinsic ID.
      if (SrcGIOrNull->TheDef->getName() == "G_INTRINSIC" && i == 0) {
        if (const CodeGenIntrinsic *II = Src->getIntrinsicInfo(CGP)) {
          OperandMatcher &OM =
              InsnMatcher.addOperand(OpIdx++, SrcChild->getName(), TempOpIdx);
          OM.addPredicate<IntrinsicIDOperandMatcher>(II);
          continue;
        }

        return failedImport("Expected IntInit containing instrinsic ID)");
      }

      if (auto Error =
              importChildMatcher(InsnMatcher, SrcChild, OpIdx++, TempOpIdx))
        return std::move(Error);
    }
  }

  return InsnMatcher;
}

Error GlobalISelEmitter::importChildMatcher(InstructionMatcher &InsnMatcher,
                                            const TreePatternNode *SrcChild,
                                            unsigned OpIdx,
                                            unsigned &TempOpIdx) const {
  OperandMatcher &OM =
      InsnMatcher.addOperand(OpIdx, SrcChild->getName(), TempOpIdx);

  if (SrcChild->hasAnyPredicate())
    return failedImport("Src pattern child has predicate (" +
                        explainPredicates(SrcChild) + ")");

  ArrayRef<EEVT::TypeSet> ChildTypes = SrcChild->getExtTypes();
  if (ChildTypes.size() != 1)
    return failedImport("Src pattern child has multiple results");

  // Check MBB's before the type check since they are not a known type.
  if (!SrcChild->isLeaf()) {
    if (SrcChild->getOperator()->isSubClassOf("SDNode")) {
      auto &ChildSDNI = CGP.getSDNodeInfo(SrcChild->getOperator());
      if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
        OM.addPredicate<MBBOperandMatcher>();
        return Error::success();
      }
    }
  }

  auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete());
  if (!OpTyOrNone)
    return failedImport("Src operand has an unsupported type (" + to_string(*SrcChild) + ")");
  OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone);

  // Check for nested instructions.
  if (!SrcChild->isLeaf()) {
    // Map the node to a gMIR instruction.
    InstructionOperandMatcher &InsnOperand =
        OM.addPredicate<InstructionOperandMatcher>();
    auto InsnMatcherOrError = createAndImportSelDAGMatcher(
        InsnOperand.getInsnMatcher(), SrcChild, TempOpIdx);
    if (auto Error = InsnMatcherOrError.takeError())
      return Error;

    return Error::success();
  }

  // Check for constant immediates.
  if (auto *ChildInt = dyn_cast<IntInit>(SrcChild->getLeafValue())) {
    OM.addPredicate<ConstantIntOperandMatcher>(ChildInt->getValue());
    return Error::success();
  }

  // Check for def's like register classes or ComplexPattern's.
  if (auto *ChildDefInit = dyn_cast<DefInit>(SrcChild->getLeafValue())) {
    auto *ChildRec = ChildDefInit->getDef();

    // Check for register classes.
    if (ChildRec->isSubClassOf("RegisterClass") ||
        ChildRec->isSubClassOf("RegisterOperand")) {
      OM.addPredicate<RegisterBankOperandMatcher>(
          Target.getRegisterClass(getInitValueAsRegClass(ChildDefInit)));
      return Error::success();
    }

    // Check for ComplexPattern's.
    if (ChildRec->isSubClassOf("ComplexPattern")) {
      const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
      if (ComplexPattern == ComplexPatternEquivs.end())
        return failedImport("SelectionDAG ComplexPattern (" +
                            ChildRec->getName() + ") not mapped to GlobalISel");

      OM.addPredicate<ComplexPatternOperandMatcher>(OM,
                                                    *ComplexPattern->second);
      TempOpIdx++;
      return Error::success();
    }

    if (ChildRec->isSubClassOf("ImmLeaf")) {
      return failedImport(
          "Src pattern child def is an unsupported tablegen class (ImmLeaf)");
    }

    return failedImport(
        "Src pattern child def is an unsupported tablegen class");
  }

  return failedImport("Src pattern child is an unsupported kind");
}

Error GlobalISelEmitter::importExplicitUseRenderer(
    BuildMIAction &DstMIBuilder, TreePatternNode *DstChild,
    const InstructionMatcher &InsnMatcher) const {
  // The only non-leaf child we accept is 'bb': it's an operator because
  // BasicBlockSDNode isn't inline, but in MI it's just another operand.
  if (!DstChild->isLeaf()) {
    if (DstChild->getOperator()->isSubClassOf("SDNode")) {
      auto &ChildSDNI = CGP.getSDNodeInfo(DstChild->getOperator());
      if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
        DstMIBuilder.addRenderer<CopyRenderer>(0, InsnMatcher,
                                               DstChild->getName());
        return Error::success();
      }
    }
    return failedImport("Dst pattern child isn't a leaf node or an MBB");
  }

  // Otherwise, we're looking for a bog-standard RegisterClass operand.
  if (DstChild->hasAnyPredicate())
    return failedImport("Dst pattern child has predicate (" +
                        explainPredicates(DstChild) + ")");

  if (auto *ChildDefInit = dyn_cast<DefInit>(DstChild->getLeafValue())) {
    auto *ChildRec = ChildDefInit->getDef();

    ArrayRef<EEVT::TypeSet> ChildTypes = DstChild->getExtTypes();
    if (ChildTypes.size() != 1)
      return failedImport("Dst pattern child has multiple results");

    auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete());
    if (!OpTyOrNone)
      return failedImport("Dst operand has an unsupported type");

    if (ChildRec->isSubClassOf("Register")) {
      DstMIBuilder.addRenderer<AddRegisterRenderer>(0, ChildRec);
      return Error::success();
    }

    if (ChildRec->isSubClassOf("RegisterClass") ||
        ChildRec->isSubClassOf("RegisterOperand")) {
      DstMIBuilder.addRenderer<CopyRenderer>(0, InsnMatcher,
                                             DstChild->getName());
      return Error::success();
    }

    if (ChildRec->isSubClassOf("ComplexPattern")) {
      const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
      if (ComplexPattern == ComplexPatternEquivs.end())
        return failedImport(
            "SelectionDAG ComplexPattern not mapped to GlobalISel");

      const OperandMatcher &OM = InsnMatcher.getOperand(DstChild->getName());
      DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
          0, *ComplexPattern->second, DstChild->getName(),
          OM.getAllocatedTemporariesBaseID());
      return Error::success();
    }

    if (ChildRec->isSubClassOf("SDNodeXForm"))
      return failedImport("Dst pattern child def is an unsupported tablegen "
                          "class (SDNodeXForm)");

    return failedImport(
        "Dst pattern child def is an unsupported tablegen class");
  }

  return failedImport("Dst pattern child is an unsupported kind");
}

Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer(
    RuleMatcher &M, const TreePatternNode *Dst,
    const InstructionMatcher &InsnMatcher) {
  Record *DstOp = Dst->getOperator();
  if (!DstOp->isSubClassOf("Instruction")) {
    if (DstOp->isSubClassOf("ValueType"))
      return failedImport(
          "Pattern operator isn't an instruction (it's a ValueType)");
    return failedImport("Pattern operator isn't an instruction");
  }
  CodeGenInstruction *DstI = &Target.getInstruction(DstOp);

  unsigned DstINumUses = DstI->Operands.size() - DstI->Operands.NumDefs;
  unsigned ExpectedDstINumUses = Dst->getNumChildren();
  bool IsExtractSubReg = false;

  // COPY_TO_REGCLASS is just a copy with a ConstrainOperandToRegClassAction
  // attached. Similarly for EXTRACT_SUBREG except that's a subregister copy.
  if (DstI->TheDef->getName() == "COPY_TO_REGCLASS") {
    DstI = &Target.getInstruction(RK.getDef("COPY"));
    DstINumUses--; // Ignore the class constraint.
    ExpectedDstINumUses--;
  } else if (DstI->TheDef->getName() == "EXTRACT_SUBREG") {
    DstI = &Target.getInstruction(RK.getDef("COPY"));
    IsExtractSubReg = true;
  }

  auto &DstMIBuilder = M.addAction<BuildMIAction>(0, DstI, InsnMatcher);

  // Render the explicit defs.
  for (unsigned I = 0; I < DstI->Operands.NumDefs; ++I) {
    const CGIOperandList::OperandInfo &DstIOperand = DstI->Operands[I];
    DstMIBuilder.addRenderer<CopyRenderer>(0, InsnMatcher, DstIOperand.Name);
  }

  // EXTRACT_SUBREG needs to use a subregister COPY.
  if (IsExtractSubReg) {
    if (!Dst->getChild(0)->isLeaf())
      return failedImport("EXTRACT_SUBREG child #1 is not a leaf");

    if (DefInit *SubRegInit =
            dyn_cast<DefInit>(Dst->getChild(1)->getLeafValue())) {
      CodeGenRegisterClass *RC = CGRegs.getRegClass(
          getInitValueAsRegClass(Dst->getChild(0)->getLeafValue()));
      CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());

      const auto &SrcRCDstRCPair =
          RC->getMatchingSubClassWithSubRegs(CGRegs, SubIdx);
      if (SrcRCDstRCPair.hasValue()) {
        assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
        if (SrcRCDstRCPair->first != RC)
          return failedImport("EXTRACT_SUBREG requires an additional COPY");
      }

      DstMIBuilder.addRenderer<CopySubRegRenderer>(
          0, InsnMatcher, Dst->getChild(0)->getName(), SubIdx);
      return DstMIBuilder;
    }

    return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
  }

  // Render the explicit uses.
  unsigned Child = 0;
  unsigned NumDefaultOps = 0;
  for (unsigned I = 0; I != DstINumUses; ++I) {
    const CGIOperandList::OperandInfo &DstIOperand =
        DstI->Operands[DstI->Operands.NumDefs + I];

    // If the operand has default values, introduce them now.
    // FIXME: Until we have a decent test case that dictates we should do
    // otherwise, we're going to assume that operands with default values cannot
    // be specified in the patterns. Therefore, adding them will not cause us to
    // end up with too many rendered operands.
    if (DstIOperand.Rec->isSubClassOf("OperandWithDefaultOps")) {
      DagInit *DefaultOps = DstIOperand.Rec->getValueAsDag("DefaultOps");
      if (auto Error = importDefaultOperandRenderers(DstMIBuilder, DefaultOps))
        return std::move(Error);
      ++NumDefaultOps;
      continue;
    }

    if (auto Error = importExplicitUseRenderer(
            DstMIBuilder, Dst->getChild(Child), InsnMatcher))
      return std::move(Error);
    ++Child;
  }

  if (NumDefaultOps + ExpectedDstINumUses != DstINumUses)
    return failedImport("Expected " + llvm::to_string(DstINumUses) +
                        " used operands but found " +
                        llvm::to_string(ExpectedDstINumUses) +
                        " explicit ones and " + llvm::to_string(NumDefaultOps) +
                        " default ones");

  return DstMIBuilder;
}

Error GlobalISelEmitter::importDefaultOperandRenderers(
    BuildMIAction &DstMIBuilder, DagInit *DefaultOps) const {
  for (const auto *DefaultOp : DefaultOps->getArgs()) {
    // Look through ValueType operators.
    if (const DagInit *DefaultDagOp = dyn_cast<DagInit>(DefaultOp)) {
      if (const DefInit *DefaultDagOperator =
              dyn_cast<DefInit>(DefaultDagOp->getOperator())) {
        if (DefaultDagOperator->getDef()->isSubClassOf("ValueType"))
          DefaultOp = DefaultDagOp->getArg(0);
      }
    }

    if (const DefInit *DefaultDefOp = dyn_cast<DefInit>(DefaultOp)) {
      DstMIBuilder.addRenderer<AddRegisterRenderer>(0, DefaultDefOp->getDef());
      continue;
    }

    if (const IntInit *DefaultIntOp = dyn_cast<IntInit>(DefaultOp)) {
      DstMIBuilder.addRenderer<ImmRenderer>(0, DefaultIntOp->getValue());
      continue;
    }

    return failedImport("Could not add default op");
  }

  return Error::success();
}

Error GlobalISelEmitter::importImplicitDefRenderers(
    BuildMIAction &DstMIBuilder,
    const std::vector<Record *> &ImplicitDefs) const {
  if (!ImplicitDefs.empty())
    return failedImport("Pattern defines a physical register");
  return Error::success();
}

Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
  // Keep track of the matchers and actions to emit.
  RuleMatcher M;
  M.addAction<DebugCommentAction>(P);

  if (auto Error = importRulePredicates(M, P.getPredicates()->getValues()))
    return std::move(Error);

  // Next, analyze the pattern operators.
  TreePatternNode *Src = P.getSrcPattern();
  TreePatternNode *Dst = P.getDstPattern();

  // If the root of either pattern isn't a simple operator, ignore it.
  if (auto Err = isTrivialOperatorNode(Dst))
    return failedImport("Dst pattern root isn't a trivial operator (" +
                        toString(std::move(Err)) + ")");
  if (auto Err = isTrivialOperatorNode(Src))
    return failedImport("Src pattern root isn't a trivial operator (" +
                        toString(std::move(Err)) + ")");

  if (Dst->isLeaf())
    return failedImport("Dst pattern root isn't a known leaf");

  // Start with the defined operands (i.e., the results of the root operator).
  Record *DstOp = Dst->getOperator();
  if (!DstOp->isSubClassOf("Instruction"))
    return failedImport("Pattern operator isn't an instruction");

  auto &DstI = Target.getInstruction(DstOp);
  if (DstI.Operands.NumDefs != Src->getExtTypes().size())
    return failedImport("Src pattern results and dst MI defs are different (" +
                        to_string(Src->getExtTypes().size()) + " def(s) vs " +
                        to_string(DstI.Operands.NumDefs) + " def(s))");

  InstructionMatcher &InsnMatcherTemp = M.addInstructionMatcher();
  unsigned TempOpIdx = 0;
  auto InsnMatcherOrError =
      createAndImportSelDAGMatcher(InsnMatcherTemp, Src, TempOpIdx);
  if (auto Error = InsnMatcherOrError.takeError())
    return std::move(Error);
  InstructionMatcher &InsnMatcher = InsnMatcherOrError.get();

  // The root of the match also has constraints on the register bank so that it
  // matches the result instruction.
  unsigned OpIdx = 0;
  for (const EEVT::TypeSet &Ty : Src->getExtTypes()) {
    (void)Ty;

    const auto &DstIOperand = DstI.Operands[OpIdx];
    Record *DstIOpRec = DstIOperand.Rec;
    if (DstI.TheDef->getName() == "COPY_TO_REGCLASS") {
      DstIOpRec = getInitValueAsRegClass(Dst->getChild(1)->getLeafValue());

      if (DstIOpRec == nullptr)
        return failedImport(
            "COPY_TO_REGCLASS operand #1 isn't a register class");
    } else if (DstI.TheDef->getName() == "EXTRACT_SUBREG") {
      if (!Dst->getChild(0)->isLeaf())
        return failedImport("EXTRACT_SUBREG operand #0 isn't a leaf");

      // We can assume that a subregister is in the same bank as it's super
      // register.
      DstIOpRec = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());

      if (DstIOpRec == nullptr)
        return failedImport(
            "EXTRACT_SUBREG operand #0 isn't a register class");
    } else if (DstIOpRec->isSubClassOf("RegisterOperand"))
      DstIOpRec = DstIOpRec->getValueAsDef("RegClass");
    else if (!DstIOpRec->isSubClassOf("RegisterClass"))
      return failedImport("Dst MI def isn't a register class" +
                          to_string(*Dst));

    OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
    OM.setSymbolicName(DstIOperand.Name);
    OM.addPredicate<RegisterBankOperandMatcher>(
        Target.getRegisterClass(DstIOpRec));
    ++OpIdx;
  }

  auto DstMIBuilderOrError =
      createAndImportInstructionRenderer(M, Dst, InsnMatcher);
  if (auto Error = DstMIBuilderOrError.takeError())
    return std::move(Error);
  BuildMIAction &DstMIBuilder = DstMIBuilderOrError.get();

  // Render the implicit defs.
  // These are only added to the root of the result.
  if (auto Error = importImplicitDefRenderers(DstMIBuilder, P.getDstRegs()))
    return std::move(Error);

  // Constrain the registers to classes. This is normally derived from the
  // emitted instruction but a few instructions require special handling.
  if (DstI.TheDef->getName() == "COPY_TO_REGCLASS") {
    // COPY_TO_REGCLASS does not provide operand constraints itself but the
    // result is constrained to the class given by the second child.
    Record *DstIOpRec =
        getInitValueAsRegClass(Dst->getChild(1)->getLeafValue());

    if (DstIOpRec == nullptr)
      return failedImport("COPY_TO_REGCLASS operand #1 isn't a register class");

    M.addAction<ConstrainOperandToRegClassAction>(
        0, 0, Target.getRegisterClass(DstIOpRec));

    // We're done with this pattern!  It's eligible for GISel emission; return
    // it.
    ++NumPatternImported;
    return std::move(M);
  }

  if (DstI.TheDef->getName() == "EXTRACT_SUBREG") {
    // EXTRACT_SUBREG selects into a subregister COPY but unlike most
    // instructions, the result register class is controlled by the
    // subregisters of the operand. As a result, we must constrain the result
    // class rather than check that it's already the right one.
    if (!Dst->getChild(0)->isLeaf())
      return failedImport("EXTRACT_SUBREG child #1 is not a leaf");

    DefInit *SubRegInit = dyn_cast<DefInit>(Dst->getChild(1)->getLeafValue());
    if (!SubRegInit)
      return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");

    // Constrain the result to the same register bank as the operand.
    Record *DstIOpRec =
        getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());

    if (DstIOpRec == nullptr)
      return failedImport("EXTRACT_SUBREG operand #1 isn't a register class");

    CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
    CodeGenRegisterClass *SrcRC = CGRegs.getRegClass(DstIOpRec);

    // It would be nice to leave this constraint implicit but we're required
    // to pick a register class so constrain the result to a register class
    // that can hold the correct MVT.
    //
    // FIXME: This may introduce an extra copy if the chosen class doesn't
    //        actually contain the subregisters.
    assert(Src->getExtTypes().size() == 1 &&
             "Expected Src of EXTRACT_SUBREG to have one result type");

    const auto &SrcRCDstRCPair =
        SrcRC->getMatchingSubClassWithSubRegs(CGRegs, SubIdx);
    assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
    M.addAction<ConstrainOperandToRegClassAction>(0, 0, *SrcRCDstRCPair->second);
    M.addAction<ConstrainOperandToRegClassAction>(0, 1, *SrcRCDstRCPair->first);

    // We're done with this pattern!  It's eligible for GISel emission; return
    // it.
    ++NumPatternImported;
    return std::move(M);
  }

  M.addAction<ConstrainOperandsToDefinitionAction>(0);

  // We're done with this pattern!  It's eligible for GISel emission; return it.
  ++NumPatternImported;
  return std::move(M);
}

void GlobalISelEmitter::run(raw_ostream &OS) {
  // Track the GINodeEquiv definitions.
  gatherNodeEquivs();

  emitSourceFileHeader(("Global Instruction Selector for the " +
                       Target.getName() + " target").str(), OS);
  std::vector<RuleMatcher> Rules;
  // Look through the SelectionDAG patterns we found, possibly emitting some.
  for (const PatternToMatch &Pat : CGP.ptms()) {
    ++NumPatternTotal;
    auto MatcherOrErr = runOnPattern(Pat);

    // The pattern analysis can fail, indicating an unsupported pattern.
    // Report that if we've been asked to do so.
    if (auto Err = MatcherOrErr.takeError()) {
      if (WarnOnSkippedPatterns) {
        PrintWarning(Pat.getSrcRecord()->getLoc(),
                     "Skipped pattern: " + toString(std::move(Err)));
      } else {
        consumeError(std::move(Err));
      }
      ++NumPatternImportsSkipped;
      continue;
    }

    Rules.push_back(std::move(MatcherOrErr.get()));
  }

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

  std::vector<Record *> ComplexPredicates =
      RK.getAllDerivedDefinitions("GIComplexOperandMatcher");
  std::sort(ComplexPredicates.begin(), ComplexPredicates.end(),
            [](const Record *A, const Record *B) {
              if (A->getName() < B->getName())
                return true;
              return false;
            });
  unsigned MaxTemporaries = 0;
  for (const auto &Rule : Rules)
    MaxTemporaries = std::max(MaxTemporaries, Rule.countRendererFns());

  OS << "#ifdef GET_GLOBALISEL_PREDICATE_BITSET\n"
     << "const unsigned MAX_SUBTARGET_PREDICATES = " << SubtargetFeatures.size()
     << ";\n"
     << "using PredicateBitset = "
        "llvm::PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>;\n"
     << "#endif // ifdef GET_GLOBALISEL_PREDICATE_BITSET\n\n";

  OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n"
     << "  mutable MatcherState State;\n"
     << "  typedef "
        "ComplexRendererFn("
     << Target.getName()
     << "InstructionSelector::*ComplexMatcherMemFn)(MachineOperand &) const;\n"
     << "const MatcherInfoTy<PredicateBitset, ComplexMatcherMemFn> "
        "MatcherInfo;\n"
     << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n\n";

  OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n"
     << ", State(" << MaxTemporaries << "),\n"
     << "MatcherInfo({TypeObjects, FeatureBitsets, {\n"
     << "  nullptr, // GICP_Invalid\n";
  for (const auto &Record : ComplexPredicates)
    OS << "  &" << Target.getName()
       << "InstructionSelector::" << Record->getValueAsString("MatcherFn")
       << ", // " << Record->getName() << "\n";
  OS << "}})\n"
     << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n";

  OS << "#ifdef GET_GLOBALISEL_IMPL\n";
  SubtargetFeatureInfo::emitSubtargetFeatureBitEnumeration(SubtargetFeatures,
                                                           OS);

  // Separate subtarget features by how often they must be recomputed.
  SubtargetFeatureInfoMap ModuleFeatures;
  std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
               std::inserter(ModuleFeatures, ModuleFeatures.end()),
               [](const SubtargetFeatureInfoMap::value_type &X) {
                 return !X.second.mustRecomputePerFunction();
               });
  SubtargetFeatureInfoMap FunctionFeatures;
  std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
               std::inserter(FunctionFeatures, FunctionFeatures.end()),
               [](const SubtargetFeatureInfoMap::value_type &X) {
                 return X.second.mustRecomputePerFunction();
               });

  SubtargetFeatureInfo::emitComputeAvailableFeatures(
      Target.getName(), "InstructionSelector", "computeAvailableModuleFeatures",
      ModuleFeatures, OS);
  SubtargetFeatureInfo::emitComputeAvailableFeatures(
      Target.getName(), "InstructionSelector",
      "computeAvailableFunctionFeatures", FunctionFeatures, OS,
      "const MachineFunction *MF");

  // Emit a table containing the LLT objects needed by the matcher and an enum
  // for the matcher to reference them with.
  std::vector<LLTCodeGen> TypeObjects = {
      LLT::scalar(8),      LLT::scalar(16),     LLT::scalar(32),
      LLT::scalar(64),     LLT::scalar(80),     LLT::vector(8, 1),
      LLT::vector(16, 1),  LLT::vector(32, 1),  LLT::vector(64, 1),
      LLT::vector(8, 8),   LLT::vector(16, 8),  LLT::vector(32, 8),
      LLT::vector(64, 8),  LLT::vector(4, 16),  LLT::vector(8, 16),
      LLT::vector(16, 16), LLT::vector(32, 16), LLT::vector(2, 32),
      LLT::vector(4, 32),  LLT::vector(8, 32),  LLT::vector(16, 32),
      LLT::vector(2, 64),  LLT::vector(4, 64),  LLT::vector(8, 64),
  };
  std::sort(TypeObjects.begin(), TypeObjects.end());
  OS << "enum {\n";
  for (const auto &TypeObject : TypeObjects) {
    OS << "  ";
    TypeObject.emitCxxEnumValue(OS);
    OS << ",\n";
  }
  OS << "};\n"
     << "const static LLT TypeObjects[] = {\n";
  for (const auto &TypeObject : TypeObjects) {
    OS << "  ";
    TypeObject.emitCxxConstructorCall(OS);
    OS << ",\n";
  }
  OS << "};\n\n";

  // Emit a table containing the PredicateBitsets objects needed by the matcher
  // and an enum for the matcher to reference them with.
  std::vector<std::vector<Record *>> FeatureBitsets;
  for (auto &Rule : Rules)
    FeatureBitsets.push_back(Rule.getRequiredFeatures());
  std::sort(
      FeatureBitsets.begin(), FeatureBitsets.end(),
      [&](const std::vector<Record *> &A, const std::vector<Record *> &B) {
        if (A.size() < B.size())
          return true;
        if (A.size() > B.size())
          return false;
        for (const auto &Pair : zip(A, B)) {
          if (std::get<0>(Pair)->getName() < std::get<1>(Pair)->getName())
            return true;
          if (std::get<0>(Pair)->getName() > std::get<1>(Pair)->getName())
            return false;
        }
        return false;
      });
  FeatureBitsets.erase(
      std::unique(FeatureBitsets.begin(), FeatureBitsets.end()),
      FeatureBitsets.end());
  OS << "enum {\n"
     << "  GIFBS_Invalid,\n";
  for (const auto &FeatureBitset : FeatureBitsets) {
    if (FeatureBitset.empty())
      continue;
    OS << "  " << getNameForFeatureBitset(FeatureBitset) << ",\n";
  }
  OS << "};\n"
     << "const static PredicateBitset FeatureBitsets[] {\n"
     << "  {}, // GIFBS_Invalid\n";
  for (const auto &FeatureBitset : FeatureBitsets) {
    if (FeatureBitset.empty())
      continue;
    OS << "  {";
    for (const auto &Feature : FeatureBitset) {
      const auto &I = SubtargetFeatures.find(Feature);
      assert(I != SubtargetFeatures.end() && "Didn't import predicate?");
      OS << I->second.getEnumBitName() << ", ";
    }
    OS << "},\n";
  }
  OS << "};\n\n";

  // Emit complex predicate table and an enum to reference them with.
  OS << "enum {\n"
     << "  GICP_Invalid,\n";
  for (const auto &Record : ComplexPredicates)
    OS << "  GICP_" << Record->getName() << ",\n";
  OS << "};\n"
     << "// See constructor for table contents\n\n";

  OS << "bool " << Target.getName()
     << "InstructionSelector::selectImpl(MachineInstr &I) const {\n"
     << "  MachineFunction &MF = *I.getParent()->getParent();\n"
     << "  MachineRegisterInfo &MRI = MF.getRegInfo();\n"
     << "  // FIXME: This should be computed on a per-function basis rather "
        "than per-insn.\n"
     << "  AvailableFunctionFeatures = computeAvailableFunctionFeatures(&STI, "
        "&MF);\n"
     << "  const PredicateBitset AvailableFeatures = getAvailableFeatures();\n"
     << "  NewMIVector OutMIs;\n"
     << "  State.MIs.clear();\n"
     << "  State.MIs.push_back(&I);\n\n";

  for (auto &Rule : Rules) {
    Rule.emit(OS);
    ++CurrentMatchTableID;
    ++NumPatternEmitted;
    assert(CurrentMatchTableID == NumPatternEmitted &&
           "Statistic deviates from number of emitted tables");
  }

  OS << "  return false;\n"
     << "}\n"
     << "#endif // ifdef GET_GLOBALISEL_IMPL\n";

  OS << "#ifdef GET_GLOBALISEL_PREDICATES_DECL\n"
     << "PredicateBitset AvailableModuleFeatures;\n"
     << "mutable PredicateBitset AvailableFunctionFeatures;\n"
     << "PredicateBitset getAvailableFeatures() const {\n"
     << "  return AvailableModuleFeatures | AvailableFunctionFeatures;\n"
     << "}\n"
     << "PredicateBitset\n"
     << "computeAvailableModuleFeatures(const " << Target.getName()
     << "Subtarget *Subtarget) const;\n"
     << "PredicateBitset\n"
     << "computeAvailableFunctionFeatures(const " << Target.getName()
     << "Subtarget *Subtarget,\n"
     << "                                 const MachineFunction *MF) const;\n"
     << "#endif // ifdef GET_GLOBALISEL_PREDICATES_DECL\n";

  OS << "#ifdef GET_GLOBALISEL_PREDICATES_INIT\n"
     << "AvailableModuleFeatures(computeAvailableModuleFeatures(&STI)),\n"
     << "AvailableFunctionFeatures()\n"
     << "#endif // ifdef GET_GLOBALISEL_PREDICATES_INIT\n";
}

void GlobalISelEmitter::declareSubtargetFeature(Record *Predicate) {
  if (SubtargetFeatures.count(Predicate) == 0)
    SubtargetFeatures.emplace(
        Predicate, SubtargetFeatureInfo(Predicate, SubtargetFeatures.size()));
}

} // end anonymous namespace

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

namespace llvm {
void EmitGlobalISel(RecordKeeper &RK, raw_ostream &OS) {
  GlobalISelEmitter(RK).run(OS);
}
} // End llvm namespace