/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp

Bug Summary

File:	utils/TableGen/GlobalISelEmitter.cpp
Warning:	line 3222, column 10 Called C++ object pointer is null
Annotated Source Code

Press '?' to see keyboard shortcuts
Show analyzer invocation
clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name GlobalISelEmitter.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-eagerly-assume -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/utils/TableGen -I /build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen -I /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn338205/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/x86_64-linux-gnu/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/x86_64-linux-gnu/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/backward -internal-isystem /usr/include/clang/7.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.0.0/include -internal-externc-isystem /usr/lib/gcc/x86_64-linux-gnu/8/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/utils/TableGen -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-07-29-043837-17923-1 -x c++ /build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp -faddrsig
1//===- GlobalISelEmitter.cpp - Generate an instruction selector -----------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10/// \file
11/// This tablegen backend emits code for use by the GlobalISel instruction
12/// selector. See include/llvm/CodeGen/TargetGlobalISel.td.
13///
14/// This file analyzes the patterns recognized by the SelectionDAGISel tablegen
15/// backend, filters out the ones that are unsupported, maps
16/// SelectionDAG-specific constructs to their GlobalISel counterpart
17/// (when applicable: MVT to LLT;  SDNode to generic Instruction).
18///
19/// Not all patterns are supported: pass the tablegen invocation
20/// "-warn-on-skipped-patterns" to emit a warning when a pattern is skipped,
21/// as well as why.
22///
23/// The generated file defines a single method:
24///     bool <Target>InstructionSelector::selectImpl(MachineInstr &I) const;
25/// intended to be used in InstructionSelector::select as the first-step
26/// selector for the patterns that don't require complex C++.
27///
28/// FIXME: We'll probably want to eventually define a base
29/// "TargetGenInstructionSelector" class.
30///
31//===----------------------------------------------------------------------===//

33#include "CodeGenDAGPatterns.h"
34#include "SubtargetFeatureInfo.h"
35#include "llvm/ADT/Optional.h"
36#include "llvm/ADT/SmallSet.h"
37#include "llvm/ADT/Statistic.h"
38#include "llvm/Support/CodeGenCoverage.h"
39#include "llvm/Support/CommandLine.h"
40#include "llvm/Support/Error.h"
41#include "llvm/Support/LowLevelTypeImpl.h"
42#include "llvm/Support/MachineValueType.h"
43#include "llvm/Support/ScopedPrinter.h"
44#include "llvm/TableGen/Error.h"
45#include "llvm/TableGen/Record.h"
46#include "llvm/TableGen/TableGenBackend.h"
47#include <numeric>
48#include <string>
49using namespace llvm;

51#define DEBUG_TYPE"gisel-emitter" "gisel-emitter"

53STATISTIC(NumPatternTotal, "Total number of patterns")static llvm::Statistic NumPatternTotal = {"gisel-emitter", "NumPatternTotal"
, "Total number of patterns", {0}, {false}};
54STATISTIC(NumPatternImported, "Number of patterns imported from SelectionDAG")static llvm::Statistic NumPatternImported = {"gisel-emitter",
 "NumPatternImported", "Number of patterns imported from SelectionDAG"
, {0}, {false}};
55STATISTIC(NumPatternImportsSkipped, "Number of SelectionDAG imports skipped")static llvm::Statistic NumPatternImportsSkipped = {"gisel-emitter"
, "NumPatternImportsSkipped", "Number of SelectionDAG imports skipped"
, {0}, {false}};
56STATISTIC(NumPatternsTested, "Number of patterns executed according to coverage information")static llvm::Statistic NumPatternsTested = {"gisel-emitter", "NumPatternsTested"
, "Number of patterns executed according to coverage information"
, {0}, {false}};
57STATISTIC(NumPatternEmitted, "Number of patterns emitted")static llvm::Statistic NumPatternEmitted = {"gisel-emitter", "NumPatternEmitted"
, "Number of patterns emitted", {0}, {false}};

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

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

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

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

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

82namespace {
83//===- Helper functions ---------------------------------------------------===//

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

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

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

104public:
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 << "GILLT_v" << Ty.getNumElements() << "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")::llvm::llvm_unreachable_internal("Unhandled LLT", "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 131);
}

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;
  }
  if (Ty.isPointer() && Ty.getSizeInBits() > 0) {
    OS << "LLT::pointer(" << Ty.getAddressSpace() << ", "
       << Ty.getSizeInBits() << ")";
    return;
  }
  llvm_unreachable("Unhandled LLT")::llvm::llvm_unreachable_internal("Unhandled LLT", "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 149);
}

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.getNumElements() != Other.Ty.getNumElements())
    return Ty.getNumElements() < Other.Ty.getNumElements();

  return Ty.getSizeInBits() < Other.Ty.getSizeInBits();
}

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

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

185class InstructionMatcher;
186/// Convert an MVT to an equivalent LLT if possible, or the invalid LLT() for
187/// MVTs that don't map cleanly to an LLT (e.g., iPTR, *any, ...).
188static 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;
198}

200static std::string explainPredicates(const TreePatternNode *N) {
std::string Explanation = "";
StringRef Separator = "";
for (const auto &P : N->getPredicateFns()) {
  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 (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;
255}

257std::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();
275}

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

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

bool HasUnsupportedPredicate = false;
for (const auto &Predicate : N->getPredicateFns()) {
  if (Predicate.isAlwaysTrue())
    continue;

  if (Predicate.isImmediatePattern())
    continue;

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

  if (Predicate.isNonTruncStore())
    continue;

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

  if (Predicate.isLoad() || Predicate.isStore()) {
    if (Predicate.isUnindexed())
      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);
340}

342static 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;
350}

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

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

362class MatchTable;

364/// A record to be stored in a MatchTable.
365///
366/// This class represents any and all output that may be required to emit the
367/// MatchTable. Instances  are most often configured to represent an opcode or
368/// value that will be emitted to the table with some formatting but it can also
369/// represent commas, comments, and other formatting instructions.
370struct 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;

400private:
/// 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;

406public:
/// 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_.hasValue() ? LabelID_.getValue() : ~0u),
      EmitStr(EmitStr), NumElements(NumElements), Flags(Flags),
      RawValue(RawValue) {

  assert((!LabelID_.hasValue() || LabelID != ~0u) &&(static_cast <bool> ((!LabelID_.hasValue() || LabelID !=
 ~0u) && "This value is reserved for non-labels") ? void
 (0) : __assert_fail ("(!LabelID_.hasValue() || LabelID != ~0u) && \"This value is reserved for non-labels\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 421, __extension__ __PRETTY_FUNCTION__))
         "This value is reserved for non-labels")(static_cast <bool> ((!LabelID_.hasValue() || LabelID !=
 ~0u) && "This value is reserved for non-labels") ? void
 (0) : __assert_fail ("(!LabelID_.hasValue() || LabelID != ~0u) && \"This value is reserved for non-labels\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 421, __extension__ __PRETTY_FUNCTION__));
}
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; }
442};

444class Matcher;

446/// Holds the contents of a generated MatchTable to enable formatting and the
447/// necessary index tracking needed to support GIM_Try.
448class 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;

464public:
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")(static_cast <bool> (I != LabelMap.end() && "Use of undeclared label"
) ? void (0) : __assert_fail ("I != LabelMap.end() && \"Use of undeclared label\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 536, __extension__ __PRETTY_FUNCTION__));
  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";
}
571};

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

577void 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";
608}

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

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

617class OperandMatcher;
618class MatchAction;
619class PredicateMatcher;
620class RuleMatcher;

622class Matcher {
623public:
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;
631};

633MatchTable 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;
640}

642class 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;

653public:
/// 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() &&(static_cast <bool> (!Conditions.empty() && "Trying to pop a condition from a condition-less group"
) ? void (0) : __assert_fail ("!Conditions.empty() && \"Trying to pop a condition from a condition-less group\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 695, __extension__ __PRETTY_FUNCTION__))
         "Trying to pop a condition from a condition-less group")(static_cast <bool> (!Conditions.empty() && "Trying to pop a condition from a condition-less group"
) ? void (0) : __assert_fail ("!Conditions.empty() && \"Trying to pop a condition from a condition-less group\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 695, __extension__ __PRETTY_FUNCTION__));
  std::unique_ptr<PredicateMatcher> P = std::move(Conditions.front());
  Conditions.erase(Conditions.begin());
  return P;
}
const PredicateMatcher &getFirstCondition() const override {
  assert(!Conditions.empty() &&(static_cast <bool> (!Conditions.empty() && "Trying to get a condition from a condition-less group"
) ? void (0) : __assert_fail ("!Conditions.empty() && \"Trying to get a condition from a condition-less group\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 702, __extension__ __PRETTY_FUNCTION__))
         "Trying to get a condition from a condition-less group")(static_cast <bool> (!Conditions.empty() && "Trying to get a condition from a condition-less group"
) ? void (0) : __assert_fail ("!Conditions.empty() && \"Trying to get a condition from a condition-less group\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 702, __extension__ __PRETTY_FUNCTION__));
  return *Conditions.front();
}
bool hasFirstCondition() const override { return !Conditions.empty(); }

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

713class 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;

733public:
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")::llvm::llvm_unreachable_internal("Trying to pop a condition from a condition-less group"
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 749);
}
const PredicateMatcher &getFirstCondition() const override {
  llvm_unreachable("Trying to pop a condition from a condition-less group")::llvm::llvm_unreachable_internal("Trying to pop a condition from a condition-less group"
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 752);
}
bool hasFirstCondition() const override { return false; }

756private:
/// 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);
765};

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

773protected:
/// 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;

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

uint64_t RuleID;
static uint64_t NextRuleID;

824public:
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")(static_cast <bool> (R && "Reserving a mutatable insn that isn't available"
) ? void (0) : __assert_fail ("R && \"Reserving a mutatable insn that isn't available\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 870, __extension__ __PRETTY_FUNCTION__));
  (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 defineComplexSubOperand(StringRef SymbolicName, Record *ComplexPattern,
                             unsigned RendererID, unsigned SubOperandID) {
  assert(ComplexSubOperands.count(SymbolicName) == 0 && "Already defined")(static_cast <bool> (ComplexSubOperands.count(SymbolicName
) == 0 && "Already defined") ? void (0) : __assert_fail
 ("ComplexSubOperands.count(SymbolicName) == 0 && \"Already defined\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 884, __extension__ __PRETTY_FUNCTION__));
  ComplexSubOperands[SymbolicName] =
      std::make_tuple(ComplexPattern, RendererID, SubOperandID);
}
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;

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

931uint64_t RuleMatcher::NextRuleID = 0;

933using action_iterator = RuleMatcher::action_iterator;

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

941protected:
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;

949public:
/// Construct a new predicate and add it to the matcher.
template <class Kind, class... Args>
Optional<Kind *> addPredicate(Args &&... args);

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)...);
}
1001};

1003class PredicateMatcher {
1004public:
/// 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_AtomicOrderingMMO,
  IPM_MemoryLLTSize,
  IPM_MemoryVsLLTSize,
  IPM_GenericPredicate,
  OPM_SameOperand,
  OPM_ComplexPattern,
  OPM_IntrinsicID,
  OPM_Instruction,
  OPM_Int,
  OPM_LiteralInt,
  OPM_LLT,
  OPM_PointerToAny,
  OPM_RegBank,
  OPM_MBB,
};

1035protected:
PredicateKind Kind;
unsigned InsnVarID;
unsigned OpIdx;

1040public:
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; }

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!")(static_cast <bool> (hasValue() && "Can not get a value of a value-less predicate!"
) ? void (0) : __assert_fail ("hasValue() && \"Can not get a value of a value-less predicate!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 1064, __extension__ __PRETTY_FUNCTION__));
  llvm_unreachable("Not implemented yet")::llvm::llvm_unreachable_internal("Not implemented yet", "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 1065);
}
virtual bool hasValue() const { return false; }

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

1074/// Generates code to check a predicate of an operand.
1075///
1076/// Typical predicates include:
1077/// * Operand is a particular register.
1078/// * Operand is assigned a particular register bank.
1079/// * Operand is an MBB.
1080class OperandPredicateMatcher : public PredicateMatcher {
1081public:
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;
1091};

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

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

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

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) &&
         MatchingName == cast<SameOperandMatcher>(&B)->MatchingName;
}
1120};

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

1127public:
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;
}
1171};

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

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

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

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

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

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

unsigned getAllocatedTemporariesBaseID() const;

1217public:
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;
}
1244};

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

1251public:
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;
}
1274};

1276/// Generates code to check that an operand is a basic block.
1277class MBBOperandMatcher : public OperandPredicateMatcher {
1278public:
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;
}
1292};

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

1300public:
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;
}
1320};

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

1328public:
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;
}
1349};

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

1356public:
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;
}
1378};

1380/// Generates code to check that a set of predicates match for a particular
1381/// operand.
1382class OperandMatcher : public PredicateListMatcher<OperandPredicateMatcher> {
1383protected:
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;

1393public:
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")(static_cast <bool> (SymbolicName.empty() && "Operand already has a symbolic name"
) ? void (0) : __assert_fail ("SymbolicName.empty() && \"Operand already has a symbolic name\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 1403, __extension__ __PRETTY_FUNCTION__));
  SymbolicName = 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(llvm::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;
}
1489};

1491Error 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
  addPredicate<LLTOperandMatcher>(*OpTyOrNone);
return Error::success();
1510}

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

1516/// Generates code to check a predicate on an instruction.
1517///
1518/// Typical predicates include:
1519/// * The opcode of the instruction is a particular value.
1520/// * The nsw/nuw flag is/isn't set.
1521class InstructionPredicateMatcher : public PredicateMatcher {
1522public:
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;
};
1534};

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

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

static DenseMap<const CodeGenInstruction *, unsigned> OpcodeValues;

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

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

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

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

bool isIdentical(const PredicateMatcher &B) const override {
  return InstructionPredicateMatcher::isIdentical(B) &&
         I == cast<InstructionOpcodeMatcher>(&B)->I;
}
MatchTableRecord getValue() const override {
  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());
}
bool hasValue() const override { return OpcodeValues.count(I); }

void emitPredicateOpcodes(MatchTable &Table,
                          RuleMatcher &Rule) const override {
  Table << MatchTable::Opcode("GIM_CheckOpcode") << MatchTable::Comment("MI")
        << MatchTable::IntValue(InsnVarID) << getValue()
        << 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 I->TheDef->getName() < BO->I->TheDef->getName();

  return false;
};

bool isConstantInstruction() const {
  return I->TheDef->getName() == "G_CONSTANT";
}

StringRef getOpcode() const { return I->TheDef->getName(); }
unsigned getNumOperands() const { return I->Operands.size(); }

StringRef getOperandType(unsigned OpIdx) const {
  return I->Operands[OpIdx].OperandType;
}
1615};

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

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

1623public:
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;
}
1644};

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

1676public:
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(getMatchOpcodeForPredicate(Predicate))
        << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
        << MatchTable::Comment("Predicate")
        << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
        << MatchTable::LineBreak;
}
1701};

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

1713protected:
StringRef Order;
AOComparator Comparator;

1717public:
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;
}
1748};

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

1756public:
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;
}
1778};

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

1790protected:
unsigned MMOIdx;
RelationKind Relation;
unsigned OpIdx;

1795public:
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;
}
1824};

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

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

static bool classof(const InstructionPredicateMatcher *P) {
  return P->getKind() == IPM_GenericPredicate;
}
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;
}
1848};

1850/// Generates code to check that a set of predicates and operands match for a
1851/// particular instruction.
1852///
1853/// Typical predicates include:
1854/// * Has a specific opcode.
1855/// * Has an nsw/nuw flag or doesn't.
1856class InstructionMatcher final : public PredicateListMatcher<PredicateMatcher> {
1857protected:
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;

1870public:
InstructionMatcher(RuleMatcher &Rule, StringRef SymbolicName)
    : Rule(Rule), 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(
      llvm::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 = std::find_if(Operands.begin(), Operands.end(),
                        [&OpIdx](const std::unique_ptr<OperandMatcher> &X) {
                          return X->getOpIdx() == OpIdx;
                        });
  if (I != Operands.end())
    return **I;
  llvm_unreachable("Failed to lookup operand")::llvm::llvm_unreachable_internal("Failed to lookup operand",
 "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 1908);
}

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

  emitPredicateListOpcodes(Table, Rule);

  for (const auto &Operand : Operands)
    Operand->emitPredicateOpcodes(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 (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() {
  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")::llvm::llvm_unreachable_internal("Didn't find an opcode matcher"
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 1991);
}

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

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

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

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

2009LLTCodeGen 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 {};
2017}

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

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

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

2075void 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.getNumOperands() < getNumOperands())
    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")(static_cast <bool> (!Operands.empty() && "Nested instruction is expected to def a vreg"
) ? void (0) : __assert_fail ("!Operands.empty() && \"Nested instruction is expected to def a vreg\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 2096, __extension__ __PRETTY_FUNCTION__));
  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());
2109}

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

2127protected:
RendererKind Kind;

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

RendererKind getKind() const { return Kind; }

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

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

2148public:
CopyRenderer(unsigned NewInsnID, StringRef SymbolicName)
    : OperandRenderer(OR_Copy), NewInsnID(NewInsnID),
      SymbolicName(SymbolicName) {
  assert(!SymbolicName.empty() && "Cannot copy from an unspecified source")(static_cast <bool> (!SymbolicName.empty() && "Cannot copy from an unspecified source"
) ? void (0) : __assert_fail ("!SymbolicName.empty() && \"Cannot copy from an unspecified source\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 2152, __extension__ __PRETTY_FUNCTION__));
}

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

const 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;
}
2170};

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

2182public:
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_cast <bool> (!SymbolicName.empty() && "Cannot copy from an unspecified source"
) ? void (0) : __assert_fail ("!SymbolicName.empty() && \"Cannot copy from an unspecified source\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 2187, __extension__ __PRETTY_FUNCTION__));
}

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

const 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;
}
2211};

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

2222public:
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;
}

const StringRef getSymbolicName() const { return SymbolicName; }

void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
  InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
  unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
  Table << MatchTable::Opcode(Signed ? "GIR_CopyConstantAsSImm"
                                     : "GIR_CopyConstantAsUImm")
        << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
        << MatchTable::Comment("OldInsnID")
        << MatchTable::IntValue(OldInsnVarID)
        << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
}
2243};

2245/// A CopyFConstantAsFPImmRenderer emits code to render a G_FCONSTANT
2246/// instruction to an extended immediate operand.
2247class CopyFConstantAsFPImmRenderer : public OperandRenderer {
2248protected:
unsigned NewInsnID;
/// The name of the operand.
const std::string SymbolicName;

2253public:
CopyFConstantAsFPImmRenderer(unsigned NewInsnID, StringRef SymbolicName)
    : OperandRenderer(OR_CopyFConstantAsFPImm), NewInsnID(NewInsnID),
      SymbolicName(SymbolicName) {}

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

const StringRef getSymbolicName() const { return SymbolicName; }

void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
  InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
  unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
  Table << MatchTable::Opcode("GIR_CopyFConstantAsFPImm")
        << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
        << MatchTable::Comment("OldInsnID")
        << MatchTable::IntValue(OldInsnVarID)
        << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
}
2273};

2275/// A CopySubRegRenderer emits code to copy a single register operand from an
2276/// existing instruction to the one being built and indicate that only a
2277/// subregister should be copied.
2278class CopySubRegRenderer : public OperandRenderer {
2279protected:
unsigned NewInsnID;
/// The name of the operand.
const StringRef SymbolicName;
/// The subregister to extract.
const CodeGenSubRegIndex *SubReg;

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

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

const 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_CopySubReg")
        << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
        << MatchTable::Comment("OldInsnID")
        << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
        << MatchTable::IntValue(Operand.getOpIdx())
        << MatchTable::Comment("SubRegIdx")
        << MatchTable::IntValue(SubReg->EnumValue)
        << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
}
2310};

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

2319public:
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(MatchTable &Table, RuleMatcher &Rule) const override {
  Table << MatchTable::Opcode("GIR_AddRegister")
        << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
        << MatchTable::NamedValue(
               (RegisterDef->getValue("Namespace")
                    ? RegisterDef->getValueAsString("Namespace")
                    : ""),
               RegisterDef->getName())
        << MatchTable::LineBreak;
}
2338};

2340/// Adds a specific temporary virtual register to the instruction being built.
2341/// This is used to chain instructions together when emitting multiple
2342/// instructions.
2343class TempRegRenderer : public OperandRenderer {
2344protected:
unsigned InsnID;
unsigned TempRegID;
bool IsDef;

2349public:
TempRegRenderer(unsigned InsnID, unsigned TempRegID, bool IsDef = false)
    : OperandRenderer(OR_Register), InsnID(InsnID), TempRegID(TempRegID),
      IsDef(IsDef) {}

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

void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
  Table << MatchTable::Opcode("GIR_AddTempRegister")
        << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
        << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID)
        << MatchTable::Comment("TempRegFlags");
  if (IsDef)
    Table << MatchTable::NamedValue("RegState::Define");
  else
    Table << MatchTable::IntValue(0);
  Table << MatchTable::LineBreak;
}
2369};

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

2377public:
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(MatchTable &Table, RuleMatcher &Rule) const override {
  Table << MatchTable::Opcode("GIR_AddImm") << MatchTable::Comment("InsnID")
        << MatchTable::IntValue(InsnID) << MatchTable::Comment("Imm")
        << MatchTable::IntValue(Imm) << MatchTable::LineBreak;
}
2390};

2392/// Adds operands by calling a renderer function supplied by the ComplexPattern
2393/// matcher function.
2394class RenderComplexPatternOperand : public OperandRenderer {
2395private:
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;
/// When provided, this is the suboperand of the ComplexPattern operand to
/// render. Otherwise all the suboperands will be rendered.
Optional<unsigned> SubOperand;

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

2411public:
RenderComplexPatternOperand(unsigned InsnID, const Record &TheDef,
                            StringRef SymbolicName, unsigned RendererID,
                            Optional<unsigned> SubOperand = None)
    : OperandRenderer(OR_ComplexPattern), InsnID(InsnID), TheDef(TheDef),
      SymbolicName(SymbolicName), RendererID(RendererID),
      SubOperand(SubOperand) {}

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

void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
  Table << MatchTable::Opcode(SubOperand.hasValue() ? "GIR_ComplexSubOperandRenderer"
                                                    : "GIR_ComplexRenderer")
        << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
        << MatchTable::Comment("RendererID")
        << MatchTable::IntValue(RendererID);
  if (SubOperand.hasValue())
    Table << MatchTable::Comment("SubOperand")
          << MatchTable::IntValue(SubOperand.getValue());
  Table << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
}
2434};

2436class CustomRenderer : public OperandRenderer {
2437protected:
unsigned InsnID;
const Record &Renderer;
/// The name of the operand.
const std::string SymbolicName;

2443public:
CustomRenderer(unsigned InsnID, const Record &Renderer,
               StringRef SymbolicName)
    : OperandRenderer(OR_Custom), InsnID(InsnID), Renderer(Renderer),
      SymbolicName(SymbolicName) {}

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

void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
  InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
  unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
  Table << MatchTable::Opcode("GIR_CustomRenderer")
        << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
        << MatchTable::Comment("OldInsnID")
        << MatchTable::IntValue(OldInsnVarID)
        << MatchTable::Comment("Renderer")
        << MatchTable::NamedValue(
               "GICR_" + Renderer.getValueAsString("RendererFn").str())
        << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
}
2465};

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

/// Emit the MatchTable opcodes to implement the action.
virtual void emitActionOpcodes(MatchTable &Table,
                               RuleMatcher &Rule) const = 0;
2479};

2481/// Generates a comment describing the matched rule being acted upon.
2482class DebugCommentAction : public MatchAction {
2483private:
std::string S;

2486public:
DebugCommentAction(StringRef S) : S(S) {}

void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
  Table << MatchTable::Comment(S) << MatchTable::LineBreak;
}
2492};

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

/// True if the instruction can be built solely by mutating the opcode.
bool canMutate(RuleMatcher &Rule, const InstructionMatcher *Insn) const {
  if (!Insn)
    return false;

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

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

  return true;
}

2524public:
BuildMIAction(unsigned InsnID, const CodeGenInstruction *I)
    : InsnID(InsnID), I(I), Matched(nullptr) {}

unsigned getInsnID() const { return InsnID; }
const CodeGenInstruction *getCGI() const { return I; }

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

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

void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
  if (Matched) {
    assert(canMutate(Rule, Matched) &&(static_cast <bool> (canMutate(Rule, Matched) &&
 "Arranged to mutate an insn that isn't mutatable") ? void (0
) : __assert_fail ("canMutate(Rule, Matched) && \"Arranged to mutate an insn that isn't mutatable\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 2552, __extension__ __PRETTY_FUNCTION__))
           "Arranged to mutate an insn that isn't mutatable")(static_cast <bool> (canMutate(Rule, Matched) &&
 "Arranged to mutate an insn that isn't mutatable") ? void (0
) : __assert_fail ("canMutate(Rule, Matched) && \"Arranged to mutate an insn that isn't mutatable\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 2552, __extension__ __PRETTY_FUNCTION__));

    unsigned RecycleInsnID = Rule.getInsnVarID(*Matched);
    Table << MatchTable::Opcode("GIR_MutateOpcode")
          << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
          << MatchTable::Comment("RecycleInsnID")
          << MatchTable::IntValue(RecycleInsnID)
          << MatchTable::Comment("Opcode")
          << MatchTable::NamedValue(I->Namespace, I->TheDef->getName())
          << MatchTable::LineBreak;

    if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) {
      for (auto Def : I->ImplicitDefs) {
        auto Namespace = Def->getValue("Namespace")
                             ? Def->getValueAsString("Namespace")
                             : "";
        Table << MatchTable::Opcode("GIR_AddImplicitDef")
              << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
              << MatchTable::NamedValue(Namespace, Def->getName())
              << MatchTable::LineBreak;
      }
      for (auto Use : I->ImplicitUses) {
        auto Namespace = Use->getValue("Namespace")
                             ? Use->getValueAsString("Namespace")
                             : "";
        Table << MatchTable::Opcode("GIR_AddImplicitUse")
              << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
              << MatchTable::NamedValue(Namespace, Use->getName())
              << MatchTable::LineBreak;
      }
    }
    return;
  }

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

  Table << MatchTable::Opcode("GIR_BuildMI") << MatchTable::Comment("InsnID")
        << MatchTable::IntValue(InsnID) << MatchTable::Comment("Opcode")
        << MatchTable::NamedValue(I->Namespace, I->TheDef->getName())
        << MatchTable::LineBreak;
  for (const auto &Renderer : OperandRenderers)
    Renderer->emitRenderOpcodes(Table, Rule);

  if (I->mayLoad || I->mayStore) {
    Table << MatchTable::Opcode("GIR_MergeMemOperands")
          << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
          << MatchTable::Comment("MergeInsnID's");
    // Emit the ID's for all the instructions that are matched by this rule.
    // TODO: Limit this to matched instructions that mayLoad/mayStore or have
    //       some other means of having a memoperand. Also limit this to
    //       emitted instructions that expect to have a memoperand too. For
    //       example, (G_SEXT (G_LOAD x)) that results in separate load and
    //       sign-extend instructions shouldn't put the memoperand on the
    //       sign-extend since it has no effect there.
    std::vector<unsigned> MergeInsnIDs;
    for (const auto &IDMatcherPair : Rule.defined_insn_vars())
      MergeInsnIDs.push_back(IDMatcherPair.second);
    llvm::sort(MergeInsnIDs.begin(), MergeInsnIDs.end());
    for (const auto &MergeInsnID : MergeInsnIDs)
      Table << MatchTable::IntValue(MergeInsnID);
    Table << MatchTable::NamedValue("GIU_MergeMemOperands_EndOfList")
          << MatchTable::LineBreak;
  }

  // FIXME: This is a hack but it's sufficient for ISel. We'll need to do
  //        better for combines. Particularly when there are multiple match
  //        roots.
  if (InsnID == 0)
    Table << MatchTable::Opcode("GIR_EraseFromParent")
          << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
          << MatchTable::LineBreak;
}
2625};

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

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

void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
  Table << MatchTable::Opcode("GIR_ConstrainSelectedInstOperands")
        << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
        << MatchTable::LineBreak;
}
2640};

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

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

void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
  Table << MatchTable::Opcode("GIR_ConstrainOperandRC")
        << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
        << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
        << MatchTable::Comment("RC " + RC.getName())
        << MatchTable::IntValue(RC.EnumValue) << MatchTable::LineBreak;
}
2661};

2663/// Generates code to create a temporary register which can be used to chain
2664/// instructions together.
2665class MakeTempRegisterAction : public MatchAction {
2666private:
LLTCodeGen Ty;
unsigned TempRegID;

2670public:
MakeTempRegisterAction(const LLTCodeGen &Ty, unsigned TempRegID)
    : Ty(Ty), TempRegID(TempRegID) {}

void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
  Table << MatchTable::Opcode("GIR_MakeTempReg")
        << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID)
        << MatchTable::Comment("TypeID")
        << MatchTable::NamedValue(Ty.getCxxEnumValue())
        << MatchTable::LineBreak;
}
2681};

2683InstructionMatcher &RuleMatcher::addInstructionMatcher(StringRef SymbolicName) {
Matchers.emplace_back(new InstructionMatcher(*this, SymbolicName));
MutatableInsns.insert(Matchers.back().get());
return *Matchers.back();
2687}

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

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

2697// Emplaces an action of the specified Kind at the end of the action list.
2698//
2699// Returns a reference to the newly created action.
2700//
2701// Like std::vector::emplace_back(), may invalidate all iterators if the new
2702// size exceeds the capacity. Otherwise, only invalidates the past-the-end
2703// iterator.
2704template <class Kind, class... Args>
2705Kind &RuleMatcher::addAction(Args &&... args) {
Actions.emplace_back(llvm::make_unique<Kind>(std::forward<Args>(args)...));
return *static_cast<Kind *>(Actions.back().get());
2708}

2710// Emplaces an action of the specified Kind before the given insertion point.
2711//
2712// Returns an iterator pointing at the newly created instruction.
2713//
2714// Like std::vector::insert(), may invalidate all iterators if the new size
2715// exceeds the capacity. Otherwise, only invalidates the iterators from the
2716// insertion point onwards.
2717template <class Kind, class... Args>
2718action_iterator RuleMatcher::insertAction(action_iterator InsertPt,
                                        Args &&... args) {
return Actions.emplace(InsertPt,
                       llvm::make_unique<Kind>(std::forward<Args>(args)...));
2722}

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

2730unsigned RuleMatcher::getInsnVarID(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")::llvm::llvm_unreachable_internal("Matched Insn was not captured in a local variable"
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 2734);
2735}

2737void RuleMatcher::defineOperand(StringRef SymbolicName, OperandMatcher &OM) {
if (DefinedOperands.find(SymbolicName) == DefinedOperands.end()) {
  DefinedOperands[SymbolicName] = &OM;
  return;
}

// If the operand is already defined, then we must ensure both references in
// the matcher have the exact same node.
OM.addPredicate<SameOperandMatcher>(OM.getSymbolicName());
2746}

2748InstructionMatcher &
2749RuleMatcher::getInstructionMatcher(StringRef SymbolicName) const {
for (const auto &I : InsnVariableIDs)
  if (I.first->getSymbolicName() == SymbolicName)
    return *I.first;
llvm_unreachable(::llvm::llvm_unreachable_internal(("Failed to lookup instruction "
 + SymbolicName).str().c_str(), "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 2754)
    ("Failed to lookup instruction " + SymbolicName).str().c_str())::llvm::llvm_unreachable_internal(("Failed to lookup instruction "
 + SymbolicName).str().c_str(), "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 2754);
2755}

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

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

return *I->second;
2765}

2767void RuleMatcher::emit(MatchTable &Table) {
if (Matchers.empty())
  llvm_unreachable("Unexpected empty matcher!")::llvm::llvm_unreachable_internal("Unexpected empty matcher!"
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 2769);

// 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")(static_cast <bool> (Matchers.size() == 1 && "Cannot handle multi-root matchers yet"
) ? void (0) : __assert_fail ("Matchers.size() == 1 && \"Cannot handle multi-root matchers yet\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 2780, __extension__ __PRETTY_FUNCTION__));

unsigned LabelID = Table.allocateLabelID();
Table << MatchTable::Opcode("GIM_Try", +1)
      << MatchTable::Comment("On fail goto")
      << MatchTable::JumpTarget(LabelID)
      << MatchTable::Comment(("Rule ID " + Twine(RuleID) + " //").str())
      << MatchTable::LineBreak;

if (!RequiredFeatures.empty()) {
  Table << MatchTable::Opcode("GIM_CheckFeatures")
        << MatchTable::NamedValue(getNameForFeatureBitset(RequiredFeatures))
        << MatchTable::LineBreak;
}

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

// 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);
  }
  llvm::sort(InsnIDs.begin(), InsnIDs.end());

  for (const auto &InsnID : InsnIDs) {
    // Reject the difficult cases until we have a more accurate check.
    Table << MatchTable::Opcode("GIM_CheckIsSafeToFold")
          << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
          << MatchTable::LineBreak;

    // 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 &PM : EpilogueMatchers)
  PM->emitPredicateOpcodes(Table, *this);

for (const auto &MA : Actions)
  MA->emitActionOpcodes(Table, *this);

if (Table.isWithCoverage())
  Table << MatchTable::Opcode("GIR_Coverage") << MatchTable::IntValue(RuleID)
        << MatchTable::LineBreak;
else
  Table << MatchTable::Comment(("GIR_Coverage, " + Twine(RuleID) + ",").str())
        << MatchTable::LineBreak;

Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak
      << MatchTable::Label(LabelID);
++NumPatternEmitted;
2870}

2872bool 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;
2887}

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

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

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

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

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

return Kind < B.Kind;
2927}

2929void SameOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
                                            RuleMatcher &Rule) const {
const OperandMatcher &OtherOM = Rule.getOperandMatcher(MatchingName);
unsigned OtherInsnVarID = Rule.getInsnVarID(OtherOM.getInstructionMatcher());
assert(OtherInsnVarID == OtherOM.getInstructionMatcher().getInsnVarID())(static_cast <bool> (OtherInsnVarID == OtherOM.getInstructionMatcher
().getInsnVarID()) ? void (0) : __assert_fail ("OtherInsnVarID == OtherOM.getInstructionMatcher().getInsnVarID()"
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 2933, __extension__ __PRETTY_FUNCTION__));

Table << MatchTable::Opcode("GIM_CheckIsSameOperand")
      << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
      << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx)
      << MatchTable::Comment("OtherMI")
      << MatchTable::IntValue(OtherInsnVarID)
      << MatchTable::Comment("OtherOpIdx")
      << MatchTable::IntValue(OtherOM.getOpIdx())
      << MatchTable::LineBreak;
2943}

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

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

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

/// Keep track of the equivalence between SDNodes and Instruction by mapping
/// SDNodes to the GINodeEquiv mapping. We need to map to the GINodeEquiv to
/// check for attributes on the relation such as CheckMMOIsNonAtomic.
/// This is defined using 'GINodeEquiv' in the target description.
DenseMap<Record *, Record *> NodeEquivs;

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

/// Keep track of the equivalence between SDNodeXForm's and
/// GICustomOperandRenderer. Map entries are specified by subclassing
/// GISDNodeXFormEquiv.
DenseMap<const Record *, const Record *> SDNodeXFormEquivs;

/// Keep track of Scores of PatternsToMatch similar to how the DAG does.
/// This adds compatibility for RuleMatchers to use this for ordering rules.
DenseMap<uint64_t, int> RuleMatcherScores;

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

// Rule coverage information.
Optional<CodeGenCoverage> RuleCoverage;

void gatherOpcodeValues();
void gatherTypeIDValues();
void gatherNodeEquivs();
// Instruction predicate code that will be emitted in generated functions.
SmallVector<std::string, 2> InstructionPredicateCodes;
unsigned getOrCreateInstructionPredicateFnId(StringRef Code);

Record *findNodeEquiv(Record *N) const;
const CodeGenInstruction *getEquivNode(Record &Equiv,
                                       const TreePatternNode *N) const;

Error importRulePredicates(RuleMatcher &M, ArrayRef<Predicate> Predicates);
Expected<InstructionMatcher &>
createAndImportSelDAGMatcher(RuleMatcher &Rule,
                             InstructionMatcher &InsnMatcher,
                             const TreePatternNode *Src, unsigned &TempOpIdx);
Error importComplexPatternOperandMatcher(OperandMatcher &OM, Record *R,
                                         unsigned &TempOpIdx) const;
Error importChildMatcher(RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
                         const TreePatternNode *SrcChild,
                         bool OperandIsAPointer, unsigned OpIdx,
                         unsigned &TempOpIdx);

Expected<BuildMIAction &>
createAndImportInstructionRenderer(RuleMatcher &M,
                                   const TreePatternNode *Dst);
Expected<action_iterator> createAndImportSubInstructionRenderer(
    action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst,
    unsigned TempReg);
Expected<action_iterator>
createInstructionRenderer(action_iterator InsertPt, RuleMatcher &M,
                          const TreePatternNode *Dst);
void importExplicitDefRenderers(BuildMIAction &DstMIBuilder);
Expected<action_iterator>
importExplicitUseRenderers(action_iterator InsertPt, RuleMatcher &M,
                           BuildMIAction &DstMIBuilder,
                           const llvm::TreePatternNode *Dst);
Expected<action_iterator>
importExplicitUseRenderer(action_iterator InsertPt, RuleMatcher &Rule,
                          BuildMIAction &DstMIBuilder,
                          TreePatternNode *DstChild);
Error importDefaultOperandRenderers(BuildMIAction &DstMIBuilder,
                                    DagInit *DefaultOps) const;
Error
importImplicitDefRenderers(BuildMIAction &DstMIBuilder,
                           const std::vector<Record *> &ImplicitDefs) const;

void emitCxxPredicateFns(raw_ostream &OS, StringRef CodeFieldName,
                         StringRef TypeIdentifier, StringRef ArgType,
                         StringRef ArgName, StringRef AdditionalDeclarations,
                         std::function<bool(const Record *R)> Filter);
void emitImmPredicateFns(raw_ostream &OS, StringRef TypeIdentifier,
                         StringRef ArgType,
                         std::function<bool(const Record *R)> Filter);
void emitMIPredicateFns(raw_ostream &OS);

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

MatchTable buildMatchTable(MutableArrayRef<RuleMatcher> Rules, bool Optimize,
                           bool WithCoverage);

3049public:
/// Takes a sequence of \p Rules and group them based on the predicates
/// they share. \p MatcherStorage is used as a memory container
/// for the group that are created as part of this process.
///
/// What this optimization does looks like if GroupT = GroupMatcher:
/// Output without optimization:
/// \verbatim
/// # R1
///  # predicate A
///  # predicate B
///  ...
/// # R2
///  # predicate A // <-- effectively this is going to be checked twice.
///                //     Once in R1 and once in R2.
///  # predicate C
/// \endverbatim
/// Output with optimization:
/// \verbatim
/// # Group1_2
///  # predicate A // <-- Check is now shared.
///  # R1
///   # predicate B
///  # R2
///   # predicate C
/// \endverbatim
template <class GroupT>
static std::vector<Matcher *> optimizeRules(
    ArrayRef<Matcher *> Rules,
    std::vector<std::unique_ptr<Matcher>> &MatcherStorage);
3079};

3081void GlobalISelEmitter::gatherOpcodeValues() {
InstructionOpcodeMatcher::initOpcodeValuesMap(Target);
3083}

3085void GlobalISelEmitter::gatherTypeIDValues() {
LLTOperandMatcher::initTypeIDValuesMap();
3087}
3088unsigned GlobalISelEmitter::getOrCreateInstructionPredicateFnId(StringRef Code) {
// There's not very many predicates that need to be here at the moment so we
// just maintain a simple set-like vector. If it grows then we'll need to do
// something more efficient.
const auto &I = std::find(InstructionPredicateCodes.begin(),
                          InstructionPredicateCodes.end(),
                          Code);
if (I == InstructionPredicateCodes.end()) {
  unsigned ID = InstructionPredicateCodes.size();
  InstructionPredicateCodes.push_back(Code);
  return ID;
}
return std::distance(InstructionPredicateCodes.begin(), I);
3101}

3103void GlobalISelEmitter::gatherNodeEquivs() {
assert(NodeEquivs.empty())(static_cast <bool> (NodeEquivs.empty()) ? void (0) : __assert_fail
 ("NodeEquivs.empty()", "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 3104, __extension__ __PRETTY_FUNCTION__));
for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv"))
  NodeEquivs[Equiv->getValueAsDef("Node")] = Equiv;

assert(ComplexPatternEquivs.empty())(static_cast <bool> (ComplexPatternEquivs.empty()) ? void
 (0) : __assert_fail ("ComplexPatternEquivs.empty()", "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 3108, __extension__ __PRETTY_FUNCTION__));
for (Record *Equiv : RK.getAllDerivedDefinitions("GIComplexPatternEquiv")) {
  Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
  if (!SelDAGEquiv)
    continue;
  ComplexPatternEquivs[SelDAGEquiv] = Equiv;
}

assert(SDNodeXFormEquivs.empty())(static_cast <bool> (SDNodeXFormEquivs.empty()) ? void (
0) : __assert_fail ("SDNodeXFormEquivs.empty()", "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 3116, __extension__ __PRETTY_FUNCTION__));
for (Record *Equiv : RK.getAllDerivedDefinitions("GISDNodeXFormEquiv")) {
 Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
 if (!SelDAGEquiv)
   continue;
 SDNodeXFormEquivs[SelDAGEquiv] = Equiv;
}
3123}

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

3129const CodeGenInstruction *
3130GlobalISelEmitter::getEquivNode(Record &Equiv, const TreePatternNode *N) const {
for (const auto &Predicate : N->getPredicateFns()) {
  if (!Equiv.isValueUnset("IfSignExtend") && Predicate.isLoad() &&
      Predicate.isSignExtLoad())
    return &Target.getInstruction(Equiv.getValueAsDef("IfSignExtend"));
  if (!Equiv.isValueUnset("IfZeroExtend") && Predicate.isLoad() &&
      Predicate.isZeroExtLoad())
    return &Target.getInstruction(Equiv.getValueAsDef("IfZeroExtend"));
}
return &Target.getInstruction(Equiv.getValueAsDef("I"));
3140}

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

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

3148Error
3149GlobalISelEmitter::importRulePredicates(RuleMatcher &M,
                                      ArrayRef<Predicate> Predicates) {
for (const Predicate &P : Predicates) {
  if (!P.Def)
    continue;
  declareSubtargetFeature(P.Def);
  M.addRequiredFeature(P.Def);
}

return Error::success();
3159}

3161Expected<InstructionMatcher &> GlobalISelEmitter::createAndImportSelDAGMatcher(
  RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
  const TreePatternNode *Src, unsigned &TempOpIdx) {
Record *SrcGIEquivOrNull = nullptr;
1
'SrcGIEquivOrNull' initialized to a null pointer value→
const CodeGenInstruction *SrcGIOrNull = nullptr;

// Start with the defined operands (i.e., the results of the root operator).
if (Src->getExtTypes().size() > 1)
2
←
Assuming the condition is false→
3
←
Taking false branch→
  return failedImport("Src pattern has multiple results");

if (Src->isLeaf()) {
4
←
Taking true branch→
  Init *SrcInit = Src->getLeafValue();
  if (isa<IntInit>(SrcInit)) {
5
←
Taking true branch→
    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 {
  SrcGIEquivOrNull = findNodeEquiv(Src->getOperator());
  if (!SrcGIEquivOrNull)
    return failedImport("Pattern operator lacks an equivalent Instruction" +
                        explainOperator(Src->getOperator()));
  SrcGIOrNull = getEquivNode(*SrcGIEquivOrNull, Src);

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

unsigned OpIdx = 0;
for (const TypeSetByHwMode &VTy : Src->getExtTypes()) {
  // 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);
  if (auto Error = OM.addTypeCheckPredicate(VTy, false /* OperandIsAPointer */))
    return failedImport(toString(std::move(Error)) +
                        " for result of Src pattern operator");
}

for (const auto &Predicate : Src->getPredicateFns()) {
  if (Predicate.isAlwaysTrue())
6
←
Assuming the condition is false→
7
←
Taking false branch→
    continue;

  if (Predicate.isImmediatePattern()) {
8
←
Assuming the condition is false→
9
←
Taking false branch→
    InsnMatcher.addPredicate<InstructionImmPredicateMatcher>(Predicate);
    continue;
  }

  // G_LOAD is used for both non-extending and any-extending loads. 
  if (Predicate.isLoad() && Predicate.isNonExtLoad()) {
10
←
Assuming the condition is false→
    InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
        0, MemoryVsLLTSizePredicateMatcher::EqualTo, 0);
    continue;
  }
  if (Predicate.isLoad() && Predicate.isAnyExtLoad()) {
11
←
Assuming the condition is false→
    InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
        0, MemoryVsLLTSizePredicateMatcher::LessThan, 0);
    continue;
  }

  // No check required. We already did it by swapping the opcode.
  if (!SrcGIEquivOrNull->isValueUnset("IfSignExtend") &&
12
←
Called C++ object pointer is null
      Predicate.isSignExtLoad())
    continue;

  // No check required. We already did it by swapping the opcode.
  if (!SrcGIEquivOrNull->isValueUnset("IfZeroExtend") &&
      Predicate.isZeroExtLoad())
    continue;

  // No check required. G_STORE by itself is a non-extending store.
  if (Predicate.isNonTruncStore())
    continue;

  if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
    if (Predicate.getMemoryVT() != nullptr) {
      Optional<LLTCodeGen> MemTyOrNone =
          MVTToLLT(getValueType(Predicate.getMemoryVT()));

      if (!MemTyOrNone)
        return failedImport("MemVT could not be converted to LLT");

      // MMO's work in bytes so we must take care of unusual types like i1
      // don't round down.
      unsigned MemSizeInBits =
          llvm::alignTo(MemTyOrNone->get().getSizeInBits(), 8);

      InsnMatcher.addPredicate<MemorySizePredicateMatcher>(
          0, MemSizeInBits / 8);
      continue;
    }
  }

  if (Predicate.isLoad() || Predicate.isStore()) {
    // No check required. A G_LOAD/G_STORE is an unindexed load.
    if (Predicate.isUnindexed())
      continue;
  }

  if (Predicate.isAtomic()) {
    if (Predicate.isAtomicOrderingMonotonic()) {
      InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
          "Monotonic");
      continue;
    }
    if (Predicate.isAtomicOrderingAcquire()) {
      InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("Acquire");
      continue;
    }
    if (Predicate.isAtomicOrderingRelease()) {
      InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("Release");
      continue;
    }
    if (Predicate.isAtomicOrderingAcquireRelease()) {
      InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
          "AcquireRelease");
      continue;
    }
    if (Predicate.isAtomicOrderingSequentiallyConsistent()) {
      InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
          "SequentiallyConsistent");
      continue;
    }

    if (Predicate.isAtomicOrderingAcquireOrStronger()) {
      InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
          "Acquire", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
      continue;
    }
    if (Predicate.isAtomicOrderingWeakerThanAcquire()) {
      InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
          "Acquire", AtomicOrderingMMOPredicateMatcher::AO_WeakerThan);
      continue;
    }

    if (Predicate.isAtomicOrderingReleaseOrStronger()) {
      InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
          "Release", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
      continue;
    }
    if (Predicate.isAtomicOrderingWeakerThanRelease()) {
      InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
          "Release", AtomicOrderingMMOPredicateMatcher::AO_WeakerThan);
      continue;
    }
  }

  if (Predicate.hasGISelPredicateCode()) {
    InsnMatcher.addPredicate<GenericInstructionPredicateMatcher>(Predicate);
    continue;
  }

  return failedImport("Src pattern child has predicate (" +
                      explainPredicates(Src) + ")");
}
if (SrcGIEquivOrNull && SrcGIEquivOrNull->getValueAsBit("CheckMMOIsNonAtomic"))
  InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("NotAtomic");

if (Src->isLeaf()) {
  Init *SrcInit = Src->getLeafValue();
  if (IntInit *SrcIntInit = dyn_cast<IntInit>(SrcInit)) {
    OperandMatcher &OM =
        InsnMatcher.addOperand(OpIdx++, Src->getName(), TempOpIdx);
    OM.addPredicate<LiteralIntOperandMatcher>(SrcIntInit->getValue());
  } else
    return failedImport(
        "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
} else {
  assert(SrcGIOrNull &&(static_cast <bool> (SrcGIOrNull && "Expected to have already found an equivalent Instruction"
) ? void (0) : __assert_fail ("SrcGIOrNull && \"Expected to have already found an equivalent Instruction\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 3330, __extension__ __PRETTY_FUNCTION__))
         "Expected to have already found an equivalent Instruction")(static_cast <bool> (SrcGIOrNull && "Expected to have already found an equivalent Instruction"
) ? void (0) : __assert_fail ("SrcGIOrNull && \"Expected to have already found an equivalent Instruction\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 3330, __extension__ __PRETTY_FUNCTION__));
  if (SrcGIOrNull->TheDef->getName() == "G_CONSTANT" ||
      SrcGIOrNull->TheDef->getName() == "G_FCONSTANT") {
    // imm/fpimm still have operands but we don't need to do anything with it
    // here since we don't support ImmLeaf predicates yet. However, we still
    // need to note the hidden operand to get GIM_CheckNumOperands correct.
    InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
    return InsnMatcher;
  }

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

    // SelectionDAG allows pointers to be represented with iN since it doesn't
    // distinguish between pointers and integers but they are different types in GlobalISel.
    // Coerce integers to pointers to address space 0 if the context indicates a pointer.
    bool OperandIsAPointer = SrcGIOrNull->isOperandAPointer(i);

    // For G_INTRINSIC/G_INTRINSIC_W_SIDE_EFFECTS, the operand immediately
    // following the defs is an intrinsic ID.
    if ((SrcGIOrNull->TheDef->getName() == "G_INTRINSIC" ||
         SrcGIOrNull->TheDef->getName() == "G_INTRINSIC_W_SIDE_EFFECTS") &&
        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(Rule, InsnMatcher, SrcChild, OperandIsAPointer,
                               OpIdx++, TempOpIdx))
      return std::move(Error);
  }
}

return InsnMatcher;
3372}

3374Error GlobalISelEmitter::importComplexPatternOperandMatcher(
  OperandMatcher &OM, Record *R, unsigned &TempOpIdx) const {
const auto &ComplexPattern = ComplexPatternEquivs.find(R);
if (ComplexPattern == ComplexPatternEquivs.end())
  return failedImport("SelectionDAG ComplexPattern (" + R->getName() +
                      ") not mapped to GlobalISel");

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

3386Error GlobalISelEmitter::importChildMatcher(RuleMatcher &Rule,
                                          InstructionMatcher &InsnMatcher,
                                          const TreePatternNode *SrcChild,
                                          bool OperandIsAPointer,
                                          unsigned OpIdx,
                                          unsigned &TempOpIdx) {
OperandMatcher &OM =
    InsnMatcher.addOperand(OpIdx, SrcChild->getName(), TempOpIdx);
if (OM.isSameAsAnotherOperand())
  return Error::success();

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

if (auto Error =
        OM.addTypeCheckPredicate(ChildTypes.front(), OperandIsAPointer))
  return failedImport(toString(std::move(Error)) + " for Src operand (" +
                      to_string(*SrcChild) + ")");

// Check for nested instructions.
if (!SrcChild->isLeaf()) {
  if (SrcChild->getOperator()->isSubClassOf("ComplexPattern")) {
    // When a ComplexPattern is used as an operator, it should do the same
    // thing as when used as a leaf. However, the children of the operator
    // name the sub-operands that make up the complex operand and we must
    // prepare to reference them in the renderer too.
    unsigned RendererID = TempOpIdx;
    if (auto Error = importComplexPatternOperandMatcher(
            OM, SrcChild->getOperator(), TempOpIdx))
      return Error;

    for (unsigned i = 0, e = SrcChild->getNumChildren(); i != e; ++i) {
      auto *SubOperand = SrcChild->getChild(i);
      if (!SubOperand->getName().empty())
        Rule.defineComplexSubOperand(SubOperand->getName(),
                                     SrcChild->getOperator(), RendererID, i);
    }

    return Error::success();
  }

  auto MaybeInsnOperand = OM.addPredicate<InstructionOperandMatcher>(
      InsnMatcher.getRuleMatcher(), SrcChild->getName());
  if (!MaybeInsnOperand.hasValue()) {
    // This isn't strictly true. If the user were to provide exactly the same
    // matchers as the original operand then we could allow it. However, it's
    // simpler to not permit the redundant specification.
    return failedImport("Nested instruction cannot be the same as another operand");
  }

  // Map the node to a gMIR instruction.
  InstructionOperandMatcher &InsnOperand = **MaybeInsnOperand;
  auto InsnMatcherOrError = createAndImportSelDAGMatcher(
      Rule, InsnOperand.getInsnMatcher(), SrcChild, TempOpIdx);
  if (auto Error = InsnMatcherOrError.takeError())
    return Error;

  return Error::success();
}

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

// 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 ValueType.
  if (ChildRec->isSubClassOf("ValueType")) {
    // We already added a type check as standard practice so this doesn't need
    // to do anything.
    return Error::success();
  }

  // Check for ComplexPattern's.
  if (ChildRec->isSubClassOf("ComplexPattern"))
    return importComplexPatternOperandMatcher(OM, ChildRec, TempOpIdx);

  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");
3500}

3502Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderer(
  action_iterator InsertPt, RuleMatcher &Rule, BuildMIAction &DstMIBuilder,
  TreePatternNode *DstChild) {

const auto &SubOperand = Rule.getComplexSubOperand(DstChild->getName());
if (SubOperand.hasValue()) {
  DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
      *std::get<0>(*SubOperand), DstChild->getName(),
      std::get<1>(*SubOperand), std::get<2>(*SubOperand));
  return InsertPt;
}

if (!DstChild->isLeaf()) {

  if (DstChild->getOperator()->isSubClassOf("SDNodeXForm")) {
    auto Child = DstChild->getChild(0);
    auto I = SDNodeXFormEquivs.find(DstChild->getOperator());
    if (I != SDNodeXFormEquivs.end()) {
      DstMIBuilder.addRenderer<CustomRenderer>(*I->second, Child->getName());
      return InsertPt;
    }
    return failedImport("SDNodeXForm " + Child->getName() +
                        " has no custom renderer");
  }

  // We accept 'bb' here. It's an operator because BasicBlockSDNode isn't
  // inline, but in MI it's just another operand.
  if (DstChild->getOperator()->isSubClassOf("SDNode")) {
    auto &ChildSDNI = CGP.getSDNodeInfo(DstChild->getOperator());
    if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
      DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
      return InsertPt;
    }
  }

  // Similarly, imm is an operator in TreePatternNode's view but must be
  // rendered as operands.
  // FIXME: The target should be able to choose sign-extended when appropriate
  //        (e.g. on Mips).
  if (DstChild->getOperator()->getName() == "imm") {
    DstMIBuilder.addRenderer<CopyConstantAsImmRenderer>(DstChild->getName());
    return InsertPt;
  } else if (DstChild->getOperator()->getName() == "fpimm") {
    DstMIBuilder.addRenderer<CopyFConstantAsFPImmRenderer>(
        DstChild->getName());
    return InsertPt;
  }

  if (DstChild->getOperator()->isSubClassOf("Instruction")) {
    ArrayRef<TypeSetByHwMode> ChildTypes = DstChild->getExtTypes();
    if (ChildTypes.size() != 1)
      return failedImport("Dst pattern child has multiple results");

    Optional<LLTCodeGen> OpTyOrNone = None;
    if (ChildTypes.front().isMachineValueType())
      OpTyOrNone =
          MVTToLLT(ChildTypes.front().getMachineValueType().SimpleTy);
    if (!OpTyOrNone)
      return failedImport("Dst operand has an unsupported type");

    unsigned TempRegID = Rule.allocateTempRegID();
    InsertPt = Rule.insertAction<MakeTempRegisterAction>(
        InsertPt, OpTyOrNone.getValue(), TempRegID);
    DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID);

    auto InsertPtOrError = createAndImportSubInstructionRenderer(
        ++InsertPt, Rule, DstChild, TempRegID);
    if (auto Error = InsertPtOrError.takeError())
      return std::move(Error);
    return InsertPtOrError.get();
  }

  return failedImport("Dst pattern child isn't a leaf node or an MBB" + llvm::to_string(*DstChild));
}

// It could be a specific immediate in which case we should just check for
// that immediate.
if (const IntInit *ChildIntInit =
        dyn_cast<IntInit>(DstChild->getLeafValue())) {
  DstMIBuilder.addRenderer<ImmRenderer>(ChildIntInit->getValue());
  return InsertPt;
}

// Otherwise, we're looking for a bog-standard RegisterClass operand.
if (auto *ChildDefInit = dyn_cast<DefInit>(DstChild->getLeafValue())) {
  auto *ChildRec = ChildDefInit->getDef();

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

  Optional<LLTCodeGen> OpTyOrNone = None;
  if (ChildTypes.front().isMachineValueType())
    OpTyOrNone = MVTToLLT(ChildTypes.front().getMachineValueType().SimpleTy);
  if (!OpTyOrNone)
    return failedImport("Dst operand has an unsupported type");

  if (ChildRec->isSubClassOf("Register")) {
    DstMIBuilder.addRenderer<AddRegisterRenderer>(ChildRec);
    return InsertPt;
  }

  if (ChildRec->isSubClassOf("RegisterClass") ||
      ChildRec->isSubClassOf("RegisterOperand") ||
      ChildRec->isSubClassOf("ValueType")) {
    if (ChildRec->isSubClassOf("RegisterOperand") &&
        !ChildRec->isValueUnset("GIZeroRegister")) {
      DstMIBuilder.addRenderer<CopyOrAddZeroRegRenderer>(
          DstChild->getName(), ChildRec->getValueAsDef("GIZeroRegister"));
      return InsertPt;
    }

    DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
    return InsertPt;
  }

  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 = Rule.getOperandMatcher(DstChild->getName());
    DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
        *ComplexPattern->second, DstChild->getName(),
        OM.getAllocatedTemporariesBaseID());
    return InsertPt;
  }

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

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

3638Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer(
  RuleMatcher &M, const TreePatternNode *Dst) {
auto InsertPtOrError = createInstructionRenderer(M.actions_end(), M, Dst);
if (auto Error = InsertPtOrError.takeError())
  return std::move(Error);

action_iterator InsertPt = InsertPtOrError.get();
BuildMIAction &DstMIBuilder = *static_cast<BuildMIAction *>(InsertPt->get());

importExplicitDefRenderers(DstMIBuilder);

if (auto Error = importExplicitUseRenderers(InsertPt, M, DstMIBuilder, Dst)
                     .takeError())
  return std::move(Error);

return DstMIBuilder;
3654}

3656Expected<action_iterator>
3657GlobalISelEmitter::createAndImportSubInstructionRenderer(
  const action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst,
  unsigned TempRegID) {
auto InsertPtOrError = createInstructionRenderer(InsertPt, M, Dst);

// TODO: Assert there's exactly one result.

if (auto Error = InsertPtOrError.takeError())
  return std::move(Error);

BuildMIAction &DstMIBuilder =
    *static_cast<BuildMIAction *>(InsertPtOrError.get()->get());

// Assign the result to TempReg.
DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID, true);

InsertPtOrError =
    importExplicitUseRenderers(InsertPtOrError.get(), M, DstMIBuilder, Dst);
if (auto Error = InsertPtOrError.takeError())
  return std::move(Error);

M.insertAction<ConstrainOperandsToDefinitionAction>(InsertPt,
                                                    DstMIBuilder.getInsnID());
return InsertPtOrError.get();
3681}

3683Expected<action_iterator> GlobalISelEmitter::createInstructionRenderer(
  action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst) {
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);

// 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"));
else if (DstI->TheDef->getName() == "EXTRACT_SUBREG")
  DstI = &Target.getInstruction(RK.getDef("COPY"));
else if (DstI->TheDef->getName() == "REG_SEQUENCE")
  return failedImport("Unable to emit REG_SEQUENCE");

return M.insertAction<BuildMIAction>(InsertPt, M.allocateOutputInsnID(),
                                     DstI);
3705}

3707void GlobalISelEmitter::importExplicitDefRenderers(
  BuildMIAction &DstMIBuilder) {
const CodeGenInstruction *DstI = DstMIBuilder.getCGI();
for (unsigned I = 0; I < DstI->Operands.NumDefs; ++I) {
  const CGIOperandList::OperandInfo &DstIOperand = DstI->Operands[I];
  DstMIBuilder.addRenderer<CopyRenderer>(DstIOperand.Name);
}
3714}

3716Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderers(
  action_iterator InsertPt, RuleMatcher &M, BuildMIAction &DstMIBuilder,
  const llvm::TreePatternNode *Dst) {
const CodeGenInstruction *DstI = DstMIBuilder.getCGI();
CodeGenInstruction *OrigDstI = &Target.getInstruction(Dst->getOperator());

// EXTRACT_SUBREG needs to use a subregister COPY.
if (OrigDstI->TheDef->getName() == "EXTRACT_SUBREG") {
  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())) {
    Record *RCDef = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
    if (!RCDef)
      return failedImport("EXTRACT_SUBREG child #0 could not "
                          "be coerced to a register class");

    CodeGenRegisterClass *RC = CGRegs.getRegClass(RCDef);
    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")(static_cast <bool> (SrcRCDstRCPair->second &&
 "Couldn't find a matching subclass") ? void (0) : __assert_fail
 ("SrcRCDstRCPair->second && \"Couldn't find a matching subclass\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 3740, __extension__ __PRETTY_FUNCTION__));
      if (SrcRCDstRCPair->first != RC)
        return failedImport("EXTRACT_SUBREG requires an additional COPY");
    }

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

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

// Render the explicit uses.
unsigned DstINumUses = OrigDstI->Operands.size() - OrigDstI->Operands.NumDefs;
unsigned ExpectedDstINumUses = Dst->getNumChildren();
if (OrigDstI->TheDef->getName() == "COPY_TO_REGCLASS") {
  DstINumUses--; // Ignore the class constraint.
  ExpectedDstINumUses--;
}

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

  auto InsertPtOrError = importExplicitUseRenderer(InsertPt, M, DstMIBuilder,
                                                   Dst->getChild(Child));
  if (auto Error = InsertPtOrError.takeError())
    return std::move(Error);
  InsertPt = InsertPtOrError.get();
  ++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 InsertPt;
3796}

3798Error 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>(DefaultDefOp->getDef());
    continue;
  }

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

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

return Error::success();
3824}

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

3834Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
// Keep track of the matchers and actions to emit.
int Score = P.getPatternComplexity(CGP);
RuleMatcher M(P.getSrcRecord()->getLoc());
RuleMatcherScores[M.getRuleID()] = Score;
M.addAction<DebugCommentAction>(llvm::to_string(*P.getSrcPattern()) +
                                "  =>  " +
                                llvm::to_string(*P.getDstPattern()));

if (auto Error = importRulePredicates(M, P.getPredicates()))
  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)) + ")");

// The different predicates and matchers created during
// addInstructionMatcher use the RuleMatcher M to set up their
// instruction ID (InsnVarID) that are going to be used when
// M is going to be emitted.
// However, the code doing the emission still relies on the IDs
// returned during that process by the RuleMatcher when issuing
// the recordInsn opcodes.
// Because of that:
// 1. The order in which we created the predicates
//    and such must be the same as the order in which we emit them,
//    and
// 2. We need to reset the generation of the IDs in M somewhere between
//    addInstructionMatcher and emit
//
// FIXME: Long term, we don't want to have to rely on this implicit
// naming being the same. One possible solution would be to have
// explicit operator for operation capture and reference those.
// The plus side is that it would expose opportunities to share
// the capture accross rules. The downside is that it would
// introduce a dependency between predicates (captures must happen
// before their first use.)
InstructionMatcher &InsnMatcherTemp = M.addInstructionMatcher(Src->getName());
unsigned TempOpIdx = 0;
auto InsnMatcherOrError =
    createAndImportSelDAGMatcher(M, InsnMatcherTemp, Src, TempOpIdx);
if (auto Error = InsnMatcherOrError.takeError())
  return std::move(Error);
InstructionMatcher &InsnMatcher = InsnMatcherOrError.get();

if (Dst->isLeaf()) {
  Record *RCDef = getInitValueAsRegClass(Dst->getLeafValue());

  const CodeGenRegisterClass &RC = Target.getRegisterClass(RCDef);
  if (RCDef) {
    // We need to replace the def and all its uses with the specified
    // operand. However, we must also insert COPY's wherever needed.
    // For now, emit a copy and let the register allocator clean up.
    auto &DstI = Target.getInstruction(RK.getDef("COPY"));
    const auto &DstIOperand = DstI.Operands[0];

    OperandMatcher &OM0 = InsnMatcher.getOperand(0);
    OM0.setSymbolicName(DstIOperand.Name);
    M.defineOperand(OM0.getSymbolicName(), OM0);
    OM0.addPredicate<RegisterBankOperandMatcher>(RC);

    auto &DstMIBuilder =
        M.addAction<BuildMIAction>(M.allocateOutputInsnID(), &DstI);
    DstMIBuilder.addRenderer<CopyRenderer>(DstIOperand.Name);
    DstMIBuilder.addRenderer<CopyRenderer>(Dst->getName());
    M.addAction<ConstrainOperandToRegClassAction>(0, 0, RC);

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

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

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

  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);
  M.defineOperand(OM.getSymbolicName(), OM);
  OM.addPredicate<RegisterBankOperandMatcher>(
      Target.getRegisterClass(DstIOpRec));
  ++OpIdx;
}

auto DstMIBuilderOrError = createAndImportInstructionRenderer(M, Dst);
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);

DstMIBuilder.chooseInsnToMutate(M);

// 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 &&(static_cast <bool> (Src->getExtTypes().size() == 1 &&
 "Expected Src of EXTRACT_SUBREG to have one result type") ? void
 (0) : __assert_fail ("Src->getExtTypes().size() == 1 && \"Expected Src of EXTRACT_SUBREG to have one result type\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4029, __extension__ __PRETTY_FUNCTION__))
           "Expected Src of EXTRACT_SUBREG to have one result type")(static_cast <bool> (Src->getExtTypes().size() == 1 &&
 "Expected Src of EXTRACT_SUBREG to have one result type") ? void
 (0) : __assert_fail ("Src->getExtTypes().size() == 1 && \"Expected Src of EXTRACT_SUBREG to have one result type\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4029, __extension__ __PRETTY_FUNCTION__));

  const auto &SrcRCDstRCPair =
      SrcRC->getMatchingSubClassWithSubRegs(CGRegs, SubIdx);
  assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass")(static_cast <bool> (SrcRCDstRCPair->second &&
 "Couldn't find a matching subclass") ? void (0) : __assert_fail
 ("SrcRCDstRCPair->second && \"Couldn't find a matching subclass\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4033, __extension__ __PRETTY_FUNCTION__));
  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);
4048}

4050// Emit imm predicate table and an enum to reference them with.
4051// The 'Predicate_' part of the name is redundant but eliminating it is more
4052// trouble than it's worth.
4053void GlobalISelEmitter::emitCxxPredicateFns(
  raw_ostream &OS, StringRef CodeFieldName, StringRef TypeIdentifier,
  StringRef ArgType, StringRef ArgName, StringRef AdditionalDeclarations,
  std::function<bool(const Record *R)> Filter) {
std::vector<const Record *> MatchedRecords;
const auto &Defs = RK.getAllDerivedDefinitions("PatFrag");
std::copy_if(Defs.begin(), Defs.end(), std::back_inserter(MatchedRecords),
             [&](Record *Record) {
               return !Record->getValueAsString(CodeFieldName).empty() &&
                      Filter(Record);
             });

if (!MatchedRecords.empty()) {
  OS << "// PatFrag predicates.\n"
     << "enum {\n";
  std::string EnumeratorSeparator =
      (" = GIPFP_" + TypeIdentifier + "_Invalid + 1,\n").str();
  for (const auto *Record : MatchedRecords) {
    OS << "  GIPFP_" << TypeIdentifier << "_Predicate_" << Record->getName()
       << EnumeratorSeparator;
    EnumeratorSeparator = ",\n";
  }
  OS << "};\n";
}

OS << "bool " << Target.getName() << "InstructionSelector::test" << ArgName
   << "Predicate_" << TypeIdentifier << "(unsigned PredicateID, " << ArgType << " "
   << ArgName << ") const {\n"
   << AdditionalDeclarations;
if (!AdditionalDeclarations.empty())
  OS << "\n";
if (!MatchedRecords.empty())
  OS << "  switch (PredicateID) {\n";
for (const auto *Record : MatchedRecords) {
  OS << "  case GIPFP_" << TypeIdentifier << "_Predicate_"
     << Record->getName() << ": {\n"
     << "    " << Record->getValueAsString(CodeFieldName) << "\n"
     << "    llvm_unreachable(\"" << CodeFieldName
     << " should have returned\");\n"
     << "    return false;\n"
     << "  }\n";
}
if (!MatchedRecords.empty())
  OS << "  }\n";
OS << "  llvm_unreachable(\"Unknown predicate\");\n"
   << "  return false;\n"
   << "}\n";
4100}

4102void GlobalISelEmitter::emitImmPredicateFns(
  raw_ostream &OS, StringRef TypeIdentifier, StringRef ArgType,
  std::function<bool(const Record *R)> Filter) {
return emitCxxPredicateFns(OS, "ImmediateCode", TypeIdentifier, ArgType,
                           "Imm", "", Filter);
4107}

4109void GlobalISelEmitter::emitMIPredicateFns(raw_ostream &OS) {
return emitCxxPredicateFns(
    OS, "GISelPredicateCode", "MI", "const MachineInstr &", "MI",
    "  const MachineFunction &MF = *MI.getParent()->getParent();\n"
    "  const MachineRegisterInfo &MRI = MF.getRegInfo();\n"
    "  (void)MRI;",
    [](const Record *R) { return true; });
4116}

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

std::vector<Matcher *> OptRules;
std::unique_ptr<GroupT> CurrentGroup = make_unique<GroupT>();
assert(CurrentGroup->empty() && "Newly created group isn't empty!")(static_cast <bool> (CurrentGroup->empty() &&
 "Newly created group isn't empty!") ? void (0) : __assert_fail
 ("CurrentGroup->empty() && \"Newly created group isn't empty!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4125, __extension__ __PRETTY_FUNCTION__));
unsigned NumGroups = 0;

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

  // If the group isn't large enough to provide any benefit, move all the
  // added rules out of it and make sure to re-create the group to properly
  // re-initialize it:
  if (CurrentGroup->size() < 2)
    for (Matcher *M : CurrentGroup->matchers())
      OptRules.push_back(M);
  else {
    CurrentGroup->finalize();
    OptRules.push_back(CurrentGroup.get());
    MatcherStorage.emplace_back(std::move(CurrentGroup));
    ++NumGroups;
  }
  CurrentGroup = make_unique<GroupT>();
};
for (Matcher *Rule : Rules) {
  // Greedily add as many matchers as possible to the current group:
  if (CurrentGroup->addMatcher(*Rule))
    continue;

  ProcessCurrentGroup();
  assert(CurrentGroup->empty() && "A group wasn't properly re-initialized")(static_cast <bool> (CurrentGroup->empty() &&
 "A group wasn't properly re-initialized") ? void (0) : __assert_fail
 ("CurrentGroup->empty() && \"A group wasn't properly re-initialized\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4153, __extension__ __PRETTY_FUNCTION__));

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

LLVM_DEBUG(dbgs() << "NumGroups: " << NumGroups << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gisel-emitter")) { dbgs() << "NumGroups: " << NumGroups
 << "\n"; } } while (false);
assert(CurrentGroup->empty() && "The last group wasn't properly processed")(static_cast <bool> (CurrentGroup->empty() &&
 "The last group wasn't properly processed") ? void (0) : __assert_fail
 ("CurrentGroup->empty() && \"The last group wasn't properly processed\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4164, __extension__ __PRETTY_FUNCTION__));
return OptRules;
4166}

4168MatchTable
4169GlobalISelEmitter::buildMatchTable(MutableArrayRef<RuleMatcher> Rules,
                                 bool Optimize, bool WithCoverage) {
std::vector<Matcher *> InputRules;
for (Matcher &Rule : Rules)
  InputRules.push_back(&Rule);

if (!Optimize)
  return MatchTable::buildTable(InputRules, WithCoverage);

unsigned CurrentOrdering = 0;
StringMap<unsigned> OpcodeOrder;
for (RuleMatcher &Rule : Rules) {
  const StringRef Opcode = Rule.getOpcode();
  assert(!Opcode.empty() && "Didn't expect an undefined opcode")(static_cast <bool> (!Opcode.empty() && "Didn't expect an undefined opcode"
) ? void (0) : __assert_fail ("!Opcode.empty() && \"Didn't expect an undefined opcode\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4182, __extension__ __PRETTY_FUNCTION__));
  if (OpcodeOrder.count(Opcode) == 0)
    OpcodeOrder[Opcode] = CurrentOrdering++;
}

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

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

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

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

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

return MatchTable::buildTable(OptRules, WithCoverage);
4210}

4212void GroupMatcher::optimize() {
// Make sure we only sort by a specific predicate within a range of rules that
// all have that predicate checked against a specific value (not a wildcard):
auto F = Matchers.begin();
auto T = F;
auto E = Matchers.end();
while (T != E) {
  while (T != E) {
    auto *R = static_cast<RuleMatcher *>(*T);
    if (!R->getFirstConditionAsRootType().get().isValid())
      break;
    ++T;
  }
  std::stable_sort(F, T, [](Matcher *A, Matcher *B) {
    auto *L = static_cast<RuleMatcher *>(A);
    auto *R = static_cast<RuleMatcher *>(B);
    return L->getFirstConditionAsRootType() <
           R->getFirstConditionAsRootType();
  });
  if (T != E)
    F = ++T;
}
GlobalISelEmitter::optimizeRules<GroupMatcher>(Matchers, MatcherStorage)
    .swap(Matchers);
GlobalISelEmitter::optimizeRules<SwitchMatcher>(Matchers, MatcherStorage)
    .swap(Matchers);
4238}

4240void GlobalISelEmitter::run(raw_ostream &OS) {
if (!UseCoverageFile.empty()) {
  RuleCoverage = CodeGenCoverage();
  auto RuleCoverageBufOrErr = MemoryBuffer::getFile(UseCoverageFile);
  if (!RuleCoverageBufOrErr) {
    PrintWarning(SMLoc(), "Missing rule coverage data");
    RuleCoverage = None;
  } else {
    if (!RuleCoverage->parse(*RuleCoverageBufOrErr.get(), Target.getName())) {
      PrintWarning(SMLoc(), "Ignoring invalid or missing rule coverage data");
      RuleCoverage = None;
    }
  }
}

// Track the run-time opcode values
gatherOpcodeValues();
// Track the run-time LLT ID values
gatherTypeIDValues();

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

  if (RuleCoverage) {
    if (RuleCoverage->isCovered(MatcherOrErr->getRuleID()))
      ++NumPatternsTested;
    else
      PrintWarning(Pat.getSrcRecord()->getLoc(),
                   "Pattern is not covered by a test");
  }
  Rules.push_back(std::move(MatcherOrErr.get()));
}

// Comparison function to order records by name.
auto orderByName = [](const Record *A, const Record *B) {
  return A->getName() < B->getName();
};

std::vector<Record *> ComplexPredicates =
    RK.getAllDerivedDefinitions("GIComplexOperandMatcher");
llvm::sort(ComplexPredicates.begin(), ComplexPredicates.end(), orderByName);

std::vector<Record *> CustomRendererFns =
    RK.getAllDerivedDefinitions("GICustomOperandRenderer");
llvm::sort(CustomRendererFns.begin(), CustomRendererFns.end(), orderByName);

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 "
      "ComplexRendererFns("
   << Target.getName()
   << "InstructionSelector::*ComplexMatcherMemFn)(MachineOperand &) const;\n"

   << "  typedef void(" << Target.getName()
   << "InstructionSelector::*CustomRendererFn)(MachineInstrBuilder &, const "
      "MachineInstr&) "
      "const;\n"
   << "  const ISelInfoTy<PredicateBitset, ComplexMatcherMemFn, "
      "CustomRendererFn> "
      "ISelInfo;\n";
OS << "  static " << Target.getName()
   << "InstructionSelector::ComplexMatcherMemFn ComplexPredicateFns[];\n"
   << "  static " << Target.getName()
   << "InstructionSelector::CustomRendererFn CustomRenderers[];\n"
   << "  bool testImmPredicate_I64(unsigned PredicateID, int64_t Imm) const "
      "override;\n"
   << "  bool testImmPredicate_APInt(unsigned PredicateID, const APInt &Imm) "
      "const override;\n"
   << "  bool testImmPredicate_APFloat(unsigned PredicateID, const APFloat "
      "&Imm) const override;\n"
   << "  const int64_t *getMatchTable() const override;\n"
   << "  bool testMIPredicate_MI(unsigned PredicateID, const MachineInstr &MI) "
      "const override;\n"
   << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n\n";

OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n"
   << ", State(" << MaxTemporaries << "),\n"
   << "ISelInfo(TypeObjects, NumTypeObjects, FeatureBitsets"
   << ", ComplexPredicateFns, CustomRenderers)\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;
for (const auto &Ty : KnownTypes)
  TypeObjects.push_back(Ty);
llvm::sort(TypeObjects.begin(), TypeObjects.end());
OS << "// LLT Objects.\n"
   << "enum {\n";
for (const auto &TypeObject : TypeObjects) {
  OS << "  ";
  TypeObject.emitCxxEnumValue(OS);
  OS << ",\n";
}
OS << "};\n";
OS << "const static size_t NumTypeObjects = " << TypeObjects.size() << ";\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());
llvm::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 << "// Feature bitsets.\n"
   << "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?")(static_cast <bool> (I != SubtargetFeatures.end() &&
 "Didn't import predicate?") ? void (0) : __assert_fail ("I != SubtargetFeatures.end() && \"Didn't import predicate?\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4443, __extension__ __PRETTY_FUNCTION__));
    OS << I->second.getEnumBitName() << ", ";
  }
  OS << "},\n";
}
OS << "};\n\n";

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

emitImmPredicateFns(OS, "I64", "int64_t", [](const Record *R) {
  bool Unset;
  return !R->getValueAsBitOrUnset("IsAPFloat", Unset) &&
         !R->getValueAsBit("IsAPInt");
});
emitImmPredicateFns(OS, "APFloat", "const APFloat &", [](const Record *R) {
  bool Unset;
  return R->getValueAsBitOrUnset("IsAPFloat", Unset);
});
emitImmPredicateFns(OS, "APInt", "const APInt &", [](const Record *R) {
  return R->getValueAsBit("IsAPInt");
});
emitMIPredicateFns(OS);
OS << "\n";

OS << Target.getName() << "InstructionSelector::ComplexMatcherMemFn\n"
   << Target.getName() << "InstructionSelector::ComplexPredicateFns[] = {\n"
   << "  nullptr, // GICP_Invalid\n";
for (const auto &Record : ComplexPredicates)
  OS << "  &" << Target.getName()
     << "InstructionSelector::" << Record->getValueAsString("MatcherFn")
     << ", // " << Record->getName() << "\n";
OS << "};\n\n";

OS << "// Custom renderers.\n"
   << "enum {\n"
   << "  GICR_Invalid,\n";
for (const auto &Record : CustomRendererFns)
  OS << "  GICR_" << Record->getValueAsString("RendererFn") << ", \n";
OS << "};\n";

OS << Target.getName() << "InstructionSelector::CustomRendererFn\n"
   << Target.getName() << "InstructionSelector::CustomRenderers[] = {\n"
   << "  nullptr, // GICP_Invalid\n";
for (const auto &Record : CustomRendererFns)
  OS << "  &" << Target.getName()
     << "InstructionSelector::" << Record->getValueAsString("RendererFn")
     << ", // " << Record->getName() << "\n";
OS << "};\n\n";

std::stable_sort(Rules.begin(), Rules.end(), [&](const RuleMatcher &A,
                                                 const RuleMatcher &B) {
  int ScoreA = RuleMatcherScores[A.getRuleID()];
  int ScoreB = RuleMatcherScores[B.getRuleID()];
  if (ScoreA > ScoreB)
    return true;
  if (ScoreB > ScoreA)
    return false;
  if (A.isHigherPriorityThan(B)) {
    assert(!B.isHigherPriorityThan(A) && "Cannot be more important "(static_cast <bool> (!B.isHigherPriorityThan(A) &&
 "Cannot be more important " "and less important at " "the same time"
) ? void (0) : __assert_fail ("!B.isHigherPriorityThan(A) && \"Cannot be more important \" \"and less important at \" \"the same time\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4510, __extension__ __PRETTY_FUNCTION__))
                                         "and less important at "(static_cast <bool> (!B.isHigherPriorityThan(A) &&
 "Cannot be more important " "and less important at " "the same time"
) ? void (0) : __assert_fail ("!B.isHigherPriorityThan(A) && \"Cannot be more important \" \"and less important at \" \"the same time\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4510, __extension__ __PRETTY_FUNCTION__))
                                         "the same time")(static_cast <bool> (!B.isHigherPriorityThan(A) &&
 "Cannot be more important " "and less important at " "the same time"
) ? void (0) : __assert_fail ("!B.isHigherPriorityThan(A) && \"Cannot be more important \" \"and less important at \" \"the same time\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4510, __extension__ __PRETTY_FUNCTION__));
    return true;
  }
  return false;
});

OS << "bool " << Target.getName()
   << "InstructionSelector::selectImpl(MachineInstr &I, CodeGenCoverage "
      "&CoverageInfo) 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"
   << "  if (executeMatchTable(*this, OutMIs, State, ISelInfo"
   << ", getMatchTable(), TII, MRI, TRI, RBI, AvailableFeatures"
   << ", CoverageInfo)) {\n"
   << "    return true;\n"
   << "  }\n\n"
   << "  return false;\n"
   << "}\n\n";

const MatchTable Table =
    buildMatchTable(Rules, OptimizeMatchTable, GenerateCoverage);
OS << "const int64_t *" << Target.getName()
   << "InstructionSelector::getMatchTable() const {\n";
Table.emitDeclaration(OS);
OS << "  return ";
Table.emitUse(OS);
OS << ";\n}\n";
OS << "#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";
4566}

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

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

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

4613const PredicateMatcher &RuleMatcher::getFirstCondition() const {
assert(!insnmatchers_empty() &&(static_cast <bool> (!insnmatchers_empty() && "Trying to get a condition from an empty RuleMatcher"
) ? void (0) : __assert_fail ("!insnmatchers_empty() && \"Trying to get a condition from an empty RuleMatcher\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4615, __extension__ __PRETTY_FUNCTION__))
       "Trying to get a condition from an empty RuleMatcher")(static_cast <bool> (!insnmatchers_empty() && "Trying to get a condition from an empty RuleMatcher"
) ? void (0) : __assert_fail ("!insnmatchers_empty() && \"Trying to get a condition from an empty RuleMatcher\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4615, __extension__ __PRETTY_FUNCTION__));

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

llvm_unreachable("Trying to get a condition from an InstructionMatcher with "::llvm::llvm_unreachable_internal("Trying to get a condition from an InstructionMatcher with "
 "no conditions", "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4628)
                 "no conditions")::llvm::llvm_unreachable_internal("Trying to get a condition from an InstructionMatcher with "
 "no conditions", "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4628);
4629}

4631std::unique_ptr<PredicateMatcher> RuleMatcher::popFirstCondition() {
assert(!insnmatchers_empty() &&(static_cast <bool> (!insnmatchers_empty() && "Trying to pop a condition from an empty RuleMatcher"
) ? void (0) : __assert_fail ("!insnmatchers_empty() && \"Trying to pop a condition from an empty RuleMatcher\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4633, __extension__ __PRETTY_FUNCTION__))
       "Trying to pop a condition from an empty RuleMatcher")(static_cast <bool> (!insnmatchers_empty() && "Trying to pop a condition from an empty RuleMatcher"
) ? void (0) : __assert_fail ("!insnmatchers_empty() && \"Trying to pop a condition from an empty RuleMatcher\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4633, __extension__ __PRETTY_FUNCTION__));

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

llvm_unreachable("Trying to pop a condition from an InstructionMatcher with "::llvm::llvm_unreachable_internal("Trying to pop a condition from an InstructionMatcher with "
 "no conditions", "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4649)
                 "no conditions")::llvm::llvm_unreachable_internal("Trying to pop a condition from an InstructionMatcher with "
 "no conditions", "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4649);
4650}

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

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

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

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

const PredicateMatcher &Predicate = Candidate.getFirstCondition();
if (!candidateConditionMatches(Predicate))
  return false;

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

4685void GroupMatcher::finalize() {
assert(Conditions.empty() && "Already finalized?")(static_cast <bool> (Conditions.empty() && "Already finalized?"
) ? void (0) : __assert_fail ("Conditions.empty() && \"Already finalized?\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4686, __extension__ __PRETTY_FUNCTION__));
if (empty())
  return;

Matcher &FirstRule = **Matchers.begin();
for (;;) {
  // All the checks are expected to succeed during the first iteration:
  for (const auto &Rule : Matchers)
    if (!Rule->hasFirstCondition())
      return;
  const auto &FirstCondition = FirstRule.getFirstCondition();
  for (unsigned I = 1, E = Matchers.size(); I < E; ++I)
    if (!Matchers[I]->getFirstCondition().isIdentical(FirstCondition))
      return;

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

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

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

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

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

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

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

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

const auto Value = Predicate.getValue();
// ... but be unique with respect to the actual value they check:
return Values.count(Value) == 0;
4764}

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

const PredicateMatcher &Predicate = Candidate.getFirstCondition();
if (!candidateConditionMatches(Predicate))
  return false;
const auto Value = Predicate.getValue();
Values.insert(Value);

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

4780void SwitchMatcher::finalize() {
assert(Condition == nullptr && "Already finalized")(static_cast <bool> (Condition == nullptr && "Already finalized"
) ? void (0) : __assert_fail ("Condition == nullptr && \"Already finalized\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4781, __extension__ __PRETTY_FUNCTION__));
assert(Values.size() == Matchers.size() && "Broken SwitchMatcher")(static_cast <bool> (Values.size() == Matchers.size() &&
 "Broken SwitchMatcher") ? void (0) : __assert_fail ("Values.size() == Matchers.size() && \"Broken SwitchMatcher\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4782, __extension__ __PRETTY_FUNCTION__));
if (empty())
  return;

std::stable_sort(Matchers.begin(), Matchers.end(),
                 [](const Matcher *L, const Matcher *R) {
                   return L->getFirstCondition().getValue() <
                          R->getFirstCondition().getValue();
                 });
Condition = Matchers[0]->popFirstCondition();
for (unsigned I = 1, E = Values.size(); I < E; ++I)
  Matchers[I]->popFirstCondition();
4794}

4796void SwitchMatcher::emitPredicateSpecificOpcodes(const PredicateMatcher &P,
                                               MatchTable &Table) {
assert(isSupportedPredicateType(P) && "Predicate type is not supported")(static_cast <bool> (isSupportedPredicateType(P) &&
 "Predicate type is not supported") ? void (0) : __assert_fail
 ("isSupportedPredicateType(P) && \"Predicate type is not supported\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4798, __extension__ __PRETTY_FUNCTION__));

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

llvm_unreachable("emitPredicateSpecificOpcodes is broken: can not handle a "::llvm::llvm_unreachable_internal("emitPredicateSpecificOpcodes is broken: can not handle a "
 "predicate type that is claimed to be supported", "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4814)
                 "predicate type that is claimed to be supported")::llvm::llvm_unreachable_internal("emitPredicateSpecificOpcodes is broken: can not handle a "
 "predicate type that is claimed to be supported", "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4814);
4815}

4817void SwitchMatcher::emit(MatchTable &Table) {
assert(Values.size() == Matchers.size() && "Broken SwitchMatcher")(static_cast <bool> (Values.size() == Matchers.size() &&
 "Broken SwitchMatcher") ? void (0) : __assert_fail ("Values.size() == Matchers.size() && \"Broken SwitchMatcher\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4818, __extension__ __PRETTY_FUNCTION__));
if (empty())
  return;
assert(Condition != nullptr &&(static_cast <bool> (Condition != nullptr && "Broken SwitchMatcher, hasn't been finalized?"
) ? void (0) : __assert_fail ("Condition != nullptr && \"Broken SwitchMatcher, hasn't been finalized?\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4822, __extension__ __PRETTY_FUNCTION__))
       "Broken SwitchMatcher, hasn't been finalized?")(static_cast <bool> (Condition != nullptr && "Broken SwitchMatcher, hasn't been finalized?"
) ? void (0) : __assert_fail ("Condition != nullptr && \"Broken SwitchMatcher, hasn't been finalized?\""
, "/build/llvm-toolchain-snapshot-7~svn338205/utils/TableGen/GlobalISelEmitter.cpp"
, 4822, __extension__ __PRETTY_FUNCTION__));

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

const int64_t LowerBound = Values.begin()->getRawValue();
const int64_t UpperBound = Values.rbegin()->getRawValue() + 1;

emitPredicateSpecificOpcodes(*Condition, Table);

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

int64_t J = LowerBound;
auto VI = Values.begin();
for (unsigned I = 0, E = Values.size(); I < E; ++I) {
  auto V = *VI++;
  while (J++ < V.getRawValue())
    Table << MatchTable::IntValue(0);
  V.turnIntoComment();
  Table << MatchTable::LineBreak << V << MatchTable::JumpTarget(LabelIDs[I]);
}
Table << MatchTable::LineBreak;

for (unsigned I = 0, E = Values.size(); I < E; ++I) {
  Table << MatchTable::Label(LabelIDs[I]);
  Matchers[I]->emit(Table);
  Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
}
Table << MatchTable::Label(Default);
4855}

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

4859} // end anonymous namespace

4861//===----------------------------------------------------------------------===//

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